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