共25套适用于计算机考研数据结构系统练习
（PS：其他正在整理，敬请期待）
数据结构试卷11
一、填空:
1. 设需要对5个不同的记录关键字进行排序，则至少需要比较
_____________次，至多需要比较_____________次。
2. 设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较
_________次。
3. 设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数
有_________个，比较两次查找成功有结点数有_________个。
4. 数据结构从逻辑上划分为三种基本类型：___________、__________和
___________。
5. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具
有n个顶点的有向完全图中，包含有________条边。
6. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比
原树的高度___________。
7. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为
________，整个堆排序过程的时间复杂度为________。
8. 在快速排序、堆排序、归并排序中，_________排序是稳定的。 9. 在有n个叶子结点的哈夫曼树中，总结点数是_______。
10. 一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉
链表BT中所对应的结点一定_______。
二、选择题：
1. 队列的特点是【 】。
A 先进后出 B 先进先出 C 任意位置进出 D 前面都不正确 2. 有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行【 】
遍分配与收集。 A n B d C r D n - d
3. 在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺
序【 】。 A 都不相同 B 完全相同 C 先序和中序相同，而与后序不同 D 中序和后序相同，而与先序不同 4. 设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为
【 】。 A 12 B 13 C 14 D 15 5. 下面关于广义表的叙述中，不正确的是【 】。
A 广义表可以是一个多层次的结构 B 广义表至少有一个元素 C 广义表可以被其他广义表所共享 D 广义表可以是一个递归表
6. 设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度
完全二叉树各有f个结点和c个结点，下列关系式不正确的是【 】。 A f>=c B c>f C f=2k+1-a D c>sk-1
7. 从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为【 】。
A head(tail(L)) B head(head(tail(L))) C tail(head(tail(L))) D head(tail(head(tail(L)))) 8. 下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是【 】。
A 顺序结构 B 链接结构 C 索引结构 D Hash结构 9. 在数据结构中，数据元素可由【 】。
A 实体 B 域 C 数据项 D 字段 10. 对于有n个顶点的有向图，由弗洛伊德（FloyD 算法求每一对顶之间的最短
路径的时间复杂度是【 】。 A O(1) B O(n) C O(n) D O(n3)
三、 计算与算法应用题：
1. 已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
2. 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出
来。试求出空格处的内容，并画出该二叉树。 先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A
四、阅读下列算法，分析它的作用：
1. int AA(LNode *HL , ElemType x)
{
int n=0;
LNode *p=HL;
while (p!=NULL) {
if (p->data= =x) n++; p=p->next;
}
return n; }
对于结点类型为LNode的单链表，以上算法的功能为：
2. int AA(LNode *HL , ElemType x) {
int n=0;
LNode *p=HL;
while (p!=NULL) {
if (p->data= =x) n++; p=p->next;
}
return n; }
对于结点类型为LNode的单链表，以上算法的功能为：
五、 算法设计题：
1. 编写复制一棵二叉树的非递归算法。
2. 假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，
试编写算法按如下图所示的树状显示二叉树。