楼主
大 中
小 发表于 2007-7-19 09:53 PM 只看该作者
2000年北京邮电大学数据结构试题
北京邮电大学2000考研题
注意事项：
1.答案一律写在答题纸上；
2.答案应字迹清楚语义贴切 ；
3
.算法应说明基本思路，应对主要数据类型,
变量出说明，所写算法应思路清晰简明易懂，应加必要注释。
4．算法可用pascal语言,c语言等你所熟悉的高级语言编写，但要注明语种
一、判断对错（10分，每题1分）
1．
任何无向图都存在生成树。
2．
采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。
3．
强连通图的各顶点均可达。
4．
在任何情况下，归并排序都比简单插入排序快。
5．
在二叉树中插入结点，则此二叉树便不再是二叉树了。
6．
霍夫曼树的结点个数不能是偶数。
7．
抽象数据类型只是用来描述一些抽象的事。
8．
在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。
9．
二叉树是一般树的特殊情形。
10．
文件系统采用索引结构是为了节省存储空间。
二、选择填空（20分）
1．
栈和数组分别是线性表的_______和________结构。
A.
物理B.插入限制C.删除限制D.逻辑
2．
M阶B-树是一棵________
A.
m叉排序树B.m叉平衡排序树C.m-1平衡排序树D.m+1平衡排序树
3．
算法的计算量的大小称为计算的________。
A.
效率B.复杂性C.现实性D.难度
4．
设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为：_______
A.
求子串B.联接C.匹配D.求串长
5．
一个有n个结点的图，最少有_____个连通分量，最多有________个连通分量。
A.0
B.1
C.n-1
D.n
6．
在排序算法中每一项都与其它项进行比较，计算出小于该项的个数，已确定该项的位置叫：________
A.
插入排序B.枚举排序C.选择排序D.交换排序
7．
对图中每个结点都按以该结点为弧头的邻接点建立一个单链表的存储结构称为____
A.
邻接矩阵B.邻接表C.关联矩阵D.逆邻接矩阵
8．
顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用______的方法可降低所需的代价。
A.
附加文件B.按关键字大小排序C.按记录输入先后排序D.连续排序
三、简要计算（10分）
1．
给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。
2．
banana H()—Head()、T()—Tail()从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)
四、有一组关键字（8，20，35，12，39，10，16，19，15），给出下面再等概率情况下查找成功的平均查找长度（10分）
1．
按顺序建立一棵二叉排序数，画出该二叉排序树；
2．
按顺序建立一棵平衡二叉排序数，画出该平衡二叉排序树。
五、已知一图如右图所示（15分）
1．
写出该图的邻接矩阵；
2．
写出全部拓扑排序
3．
3
10
3
3
2
1
2
5
4
6
六、优两个长度相同的栈S1,S2，已知以下入栈、出栈、判栈满和判栈空操作：
Procedure
Push(Stack:Stacktype;x atatype);
Function
Pop(Stack:Stacktype )atatype;
Function
Full (Stack:Stacktype):Boolean;
现用此二栈构成一个队列，试写出下面入队列、出队列操作算法：
Procedure
EnQueue(xatatype);
Function
DeQueue: Datatype;(10分)
七、若待排序列用单链表存储，试给出其快速排序算法。（15分）
八、已知二叉树的数据结构定义如下：
试给出在不使用堆栈（也不使用递归）、不需保留原树的情况下后序遍历一棵二叉树的算法
我就是传说中的任哥大人。挣点回贴我容易吗？ 大家积极回帖啊~~~3Q
|
