(完整word版)数据结构期末复习资料
南京理工大学泰州科技学院课程考试试卷(学生考试用)
课程名称： 数据结构 A 学分： 4 教学大纲编号：
试卷编号： 考试方式： 闭卷 满分分值： 100 考试时间： 120 分钟
组卷日期： 2011年 12月 10 日 组卷教师(签字)： 朱保平 审定人(签字)：
学生班级：10计算机、10计信管 09专升本 学生学号： 学生姓名： 7. 设单链表中结点的结构为（data,next ）。已知指针p 所指结点不是尾结点，若在指针p 所指结点之后插入结点s ，则应执行下列哪一个操作？ A)s->next=p;p->next=s ； B)s->next=p->next; p->next=s ； C)s->next=p->next;p=s; D)p->next=s; s->next=p;
8. 具有1998个结点的二叉树的最小深度为( ).
A. 10
B.11
C.12
D. 13
9. 无向图G=（V ，E ），其中：V={ a,b,c,d,e,f} , E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行广度优先遍历，得到的顶点序列正确的是（ ）。
A. a,b,e,c,d,f
B. a,c,f,e,b,d
C. a,e,b,c,f,d
D. a,e,d,f,c,b
10. 在一棵二叉树中，度为2的结点有30个，度为1的结点有50个，则二叉树总的结点数有( )。
A. 109
B. 110
C.111
D. 112
11. 若用起泡排序对序列{11,14,8,29,12,5,70,8,10,1,20}从大到小排序,需要( )次比较。
A. 45
B.46
C.55
D. 66
12．一棵具有2092个结点的完全二叉树，其度数为2的结点数为（ ）。
A.1045
B. 1046
C.1047
D. 1048
13．已知一组数为 { 3,4,5, 6, 7},用这组数构成的哈夫曼树的带权路径长度（ ）。
A. 57
B.69
C.71
D. 72
14．一棵20阶B-树当插入一结点引起结点的分裂时，则右子树上有（ ）个结点。
A. 7
B. 8
C.9
D. 10
15．设哈希表长为13，哈希函数是H(key)=key%11,表中已有数据的关键字为15,27,17,51共四个，现要将关键字为37的结点加到表中，用二次探测再散列解决哈希表解决冲突，则放入的位置是（ ）。
A. 3
B. 4
C. 5
D.6
16．线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
一、选择题（每题2分，共40分） 1．树最适合用来表示（ ）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据 2．一个堆是一棵（ ）二叉树。
A. 普通
B. 排序
C. 满
D. 完全
3．已知关键字的序列}38,35,40,18,30{ ，依次构造二叉树，当插入38时引起二叉树的不平衡，则它的旋转类型为（ ）。
A. LR
B. RL
C. RR
D. LL
4．二叉树的先序和中序遍历序列分别是ABCDEFGH ，CBEDFAGH ，该二叉树是由（ ）棵树的森林转换而来的。
A. 2
B. 3
C. 4
D. 5
5．以下是平衡二叉树的是（ ）。
6．有一个有序表为{8,15,20,22,32,41,45,62,75,77,82,85,97}，当二分查找值为22的数据时要进行（ ）次比较。
A. 2
B.3
C.4
D. 5
第 1 页 共 2 页
A ．
B ．
C ．
D ．
课程名称： 数据结构A 学分： 试卷编号：
2．根据下图所示的AOE 网，顶点V 1,V 2,V 3,V 4,V 5,V 6, V 7,V 8,V 9表示事件，弧a 1,a 2,a 3,a 4,a 5,a 6,a 7,a 8,a 9,a 10,a 11,a 12表示活动，请回答以下问题：
a 7=4
a 11=2
a 10=5
a 9=4
a 8=1
a 6=3
a 5=3
a 3=3
a 2=6
a 1=5
a 4=6
V 1
V 4 V 3
V 2
V 5
V 9
V 6
V 8
V 7 a 12=4
(1) 去掉边的方向后，画出最小生成树。（2分）
(2) 求出所有事件和活动的最早发生时间与最迟发生时间。（4分） (3) 列出所有关键活动。（2分）
3．设关键字输入序列为{22，31，15, 13，41，70，56，27，54, 18, 11,49 } （1）（2分）试构造平衡二叉树；
（2）（４分）构造3阶B-树，并分别写出删除31和56后的B-树。
（3）（2分）HASH 表表长为12，HASH 函数为H （key ）=key%11，试用二次探测再散列解决冲突的方法构造哈希表。
4．（４分）试述顺序表和链表的定义，各有什么特点？当线性表很少进行插入和删除应采用何种表？为什么？当线性表经常进行插入和删除应采用何种表？为什么？ 四、算法设计（每题7分，共14分）
1．试写出二叉树拷贝的递归算法，函数原型为copy(bitnode *t,bitnode*&s)。已知二叉树结点定义如下：
typedef struct bitnode{ int data; bitnode *lt,*rt;
}bitnode;
2．已知一带表头结点的单链表，结点类型为（data,next ）。以 head 为头指针, 每个结点的 data 域存放的是一个整数, 且结点是按值非递增排列，请设计一个算法，插入结点x ，插入后仍然保持按值非递增排列。函数原型为int insertx(lnode *&head,int x)。
17. 在有n 个结点的二叉链表中,值为非空的链域的个数为( )。
A. n-1
B. 2n-1
C. n+1
D. 2n+1 18. 对图进行深度优先遍历时，通常采用（ ）来实现算法。 A. 栈 B. 队列 C. 树 D. 图
19. 以下不是堆的序列是（ ）。
A)100，85，98，77，80，60，82，40，20，10，66 B)100，98，85，82，80，77，66，60，40，20，10 C)10，20，40，60，66，77，80，82，85，98，100 D)100，85，40，77，80，60，66，98，82，10，20
20．已知关键字的序列}25,19,76,48,6,50,32,8,20,10{，将它们构造二叉排序树所得二叉树的树高为（ ）。
A. 3
B. 4
C.5
D. 6
二、填空题（每空2分，共20分）
1. 一个深度为k 的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号，则编号最小的叶子的序号是 ；编号是i 的结点所在的层次号是 （根所在的层次号规定为1层）。
2．已知关键字的集合}2,90,55,40,19,51,41,77,6,45,18,20{，增量为3，一趟希尔排序后的结果为 。
3．树根的层次是1，则深度为9的完全二叉树至少有 个结点，拥有2000个结点的二叉树的最大层次数是 。
4．已知有向图),(E V G =,其中},,,{d c b a V =，)},(),,(),,{(d c d b c a E =。写出一个拓扑序列 。
5. 已知四棵树的森林，其第一棵，第二棵，第三棵，第四棵树的结点数分别为10，9，8，7，由它们构造的二叉树，对应根的左子树上结点数为 ，右子树上的结点数为 。
6. 假定对数据序列{25,10,8,15,40,5,12,24,30,45,20}进行快速排序，第一趟快速排序后结果为 , 第二趟快速排序后结果为 。 三、问答题（共26分）
1．假设一棵二叉树的中序序列为DBFEGAJHKCNOLIM 和后序序列为DFGEBJKHNOLMICA 。 （1）画出该树；（2分）
（2）写出先序序列；（2分） （3）写出对应该二叉树的森林；（2分）
第 2 页 共 2 页
南京理工大学泰州科技学院课程考试答案
课程名称： 数据结构A 学分： 4 教学大纲编号：
试卷编号： 考试方式： 闭卷 满分分值： 100 考试时间： 120 分钟
组卷日期： 2011 年12 月 20 日 组卷教师： 审定人(签字)：
学生班级： 10计算机、10计信管 09专升本 学生学号： 学生姓名： ABDEFGCHJKILNOM
1(3)(2分 )A C I M / | \ / \ / \
B E G H K L O | | | | D F J N
2．（1）2分
4
2
4
1
3
3
3
5
V 1
V 4 V 3
V 2
V 5
V 9
V 6
V 8
V 7 （2）4分
（3）2分 111098642,,,,,,a a a a a a a
一、选择题（每是2分，共40分）
1． C 2．D 3．B 4．B 5．B 6．C 7．B 8．B 9．A 10．C
11．C 12．A 13．A 14．D 1 5．A 16．D 17．A 18．A 19．D 20．C 二、填空题（每空2分，共 20分）
1．12
2
+-K ??1log
2
+i
2．{6，18，2，20，19，40，51，77，41，55，90，45} 3．256 2000
4．abcd 或acbd 或bacd 5. 9 24
6.{20,10,8,15,24,5,12,25,30,45,40} {12,10,8,15,5,20,24,25,30,45,40} 三、问答题（共26分） 1(1)．（2分）
A / \
B
C / \ / \
D
E H I / \ / \ / \
F
G J K L M / \ N O
第 1 页 共 1 页
ve vl
V1 0 0 V2 5 9 V3 6
6
V4 12 12 V5 15 15 V6 16 17 V7 16 16 V8 20 19 V9 21 21
e l l-e a1 0 4 4 a2 0 0 0 a3 5 9 4 a4 6 6
a5 6
12 6
a6 12 12 0 a7 12 13 1 a8 15 15 0 a9
15 15 0
a10 16 16 0 a11 19 19 0 a12 16 17 1
课程名称：学分：试卷编号：4．4分
（1）试述顺序表和链表的定义，各有什么特点？当线性表很少进行插入和删除应采用何种表？为什么？当线性表经常进行插入和删除应采用何种表？为什么？
（1）顺序表是用一组地址连续的空间存放数据元素，逻辑相邻物理相邻；优点可以随机存取，缺点是插入和删除元素是大量移动数据元素；链表是用一组地址任意的空间存放数据元素，逻辑相邻物理不一定相邻；优点插入和删除元素时不需要移动数据元素；缺点是不能随机存取。
（2）当线性表很少进行插入和删除应采用顺序表，因为可发随机存取；
当线性表经常进行插入和删除应采用链表，因为插入和删除元素时不需要移动数据元素，只需修改指针值。
四、算法设计
1．7分
void copy(bitnode *t,bitnode *&s){
if(t==NULL)s=NULL;
else{
s=new bitnode;
s->data=t->data;
copy(t->lt,s->lt);
copy(t->rt,s->rt);
}
}
2.7分
int insertx(lnode *&head,int x){
lnode *pr,*p=head->next;
while(p&&p->data
lnode s=new lnode;
s->data=x;
s->next=p;
pr->next=s;
}
3．（1） 22
/ \
15 41
/ \ / \
13 18 31 56
/ / / \
11 27 54 70
/
49
(2)4分
41
/ \
15 22 56
/ | \ / \
11 13 18 27 31 49 54 70
41
/ \
15 22 56
/ | \ / \
11 13 18 27 49 54 70
41
/ \
15 22 54
/ | \ / \
11 13 18 27 49 70
(3)2分
22 56 13 49 15 70 27 18 41 31 54 11