2010-2011 学年第2 学期课号BT11107
课程名称数据结构（B卷; 闭卷）适用班级（或年级、专业）08011103、104、105
一、填空题（每小题2分，共20分）
(1) 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的
（）和运算等的学科。
(2)在一个长度为n的顺序表中第i个元素（1 ≤i ≤n）之前插入一个元素时，需向后
移动（）个元素。
(3）假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（）。
（4）数据的逻辑结构在计算机存储器内的表示，称为数据的（）。
（5）在具有n个单元的循环队列中，队满时共有____个元素。
（6）二叉树有（）种基本形态。
（7）在具有n个结点的完全二叉树中，若结点i有左孩子，则结点i的左孩子编号为（）。
（8）若用二叉树表示具有n个结点的二叉树，则有（）个空链域。
（9）深度为k（k>0）的二叉树，至多有（）个结点，第i层上之多有（）结点。
(10) 一个有n个顶点的无向图最多有____条边。
二、选择题（每小题2分，共20分）
1.研究数据结构就是研究（）。
(A) 数据的逻辑结构 (B) 数据的存储结构
(C) 数据的逻辑结构和存储结构 (D) 数据的逻辑结构、存储结构及其数据的运算
2.下列算法的时间复杂度是（）
s=0;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
s+=B[i][j];
sum=s;
（A）O（m2） (B) O（n2） (C) O（m×n） (D) O（m+n）
3.计算机识别、存储和加工处理的对象被统称为( )
（A）数据（B）数据元素
（C）数据结构（D）数据类型
4.在一个单链表中，若删除p所指结点的后续结点，则执行____。
（A）p—＞next= p—＞next—＞next； (B) p—＞next= p—＞next;
(C) p= p—＞next; p—＞next= p—＞next—＞next； (D) p= p—＞next—＞next；
5.在一非空二叉树的中序遍历序列中，根结点的右边____。
（A）只有右子树上的所有结点（B）只有右子树上的部分结点
（C）只有左子树上的部分结点（D）只有左子树上的所有结点
6.队和栈的主要区别是( )
（A）逻辑结构不同（B）存储结构不同
（C）所包含的运算个数不同（D）限定插入和删除的位置不同
7.设有两个串p和q，求q在p中首次出现的位置的运算称作____。
（A）连接（B）. 模式匹配
（C）求子串（D）求串长
8. 具有35个结点的完全二叉树的深度为（）。
（A）5 （B）6
（C）7 （D）8
9.下列编码中属前缀码的是( )
（A）{1,01,000,001} （B）{1,01,011,010}
（C）{0,10,110,11} （D）{0,1,00,11}
10．用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
⑴25，84，21，47，15，27，68，35，20
⑵20，15，21，25，47，27，68，35，84
⑶15，20，21，25，35，27，47，68，84
⑷15，20，21，25，27，35，47，68，84
则所采用的排序方法是____。
（A）选择排序（B）希尔排序
（C）归并排序（D）快速排序
三、简答题（8小题，共50分）
1．对于如图1所示的树，请问：（5分） （1）树的根结点是哪个结点？ （2）结点E 的父结点是哪个结点？ （3）E 的兄弟结点是有哪些结点？ （4）树的深度是多少？ （5）树的度是多少？
2. 写出图2所示二叉树的先根遍历、中根遍历、后根遍历的结点序列，并将其转换为森林。
（8分）
3. 有一份电文中共使用7个字符：a 、b 、c 、d 、e 、f 、g ，它们的出现频率依次为4，5，6，12，8,10,18。
要求：（9分） （1）试画出对应的哈夫曼树； （2）每个字符的哈夫曼编码；
（3）在对该电文进行最优二进制编码处理后，电文的二进制位数。
J ○B ○
C ○
D ○
E ○ ○ ○A H ○I 图
1
4. 分别给出图3所示图的深度优先搜索和广度优先搜索得到的顶点序列。
（5分）
5. 应用普里姆算法求图4所示带权连通图的最小生成树，要求画出最小生成树的生成过程。
（5分）
6．已知一组关键字{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的二叉排序树。
（5分）
7．设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34，40），散列函数H （k ）=k mod 6，采用线性探测法解决冲突，d i =i ，要求：（8分） （1）构造散列表；
（2）等概率情况下查找成功时的平均查找长度。
8．写出图5所有可能的拓扑序列。
（5分）
⑥
⑤
④ ①
②
③
⑦ ⑧
⑨ 图3
图5
四、算法填空题（10分）
void selectsort (int R[ ] ){
// 按递增序对R[ 0 ]～R[n-1] 进行直接选择排序 int i, j, k, temp ;
for (i=0; i<= ⑴ ; i++)
{ k=i ;
for (j= ⑵ ; j<=n-1; j++) if (R[ j ] ⑶ R[ k ] ) k=j;
if （⑷）{ temp=R[ i ];
R[ i ] = ⑸ ;
R[ k ]=temp;
}
}
}//selectsort
答案
一、填空题（每小题2分，共20分）
二、选择题（每小题2分，共20分）
三、简答题：（每小题5分，共50）
1．（5分）
（1）树的根结点是：A ――――（1分） （2）结点E 的父结点是：B ―――（1分） （3）E 的兄弟结点是有：D ―――（1分） （4）树的深度是：4――――――（1分） （5）树的度是：3―――――――（1分）
2. （8分） 先根遍历序列：ABCDEFGHI (1.5分)
中根遍历序列：BCDAFEHIG
(1.5分)
后根遍历序列：DCBFIHGEA (1.5分)
图2 3．（共9分） （1）（5分）
（2）（2分） a: 0110 b: 0111 c: 100 d: 11 e: 101 f: 010
注：哈夫曼树不唯一。
各字符的编码也不唯一。
但所有字符的编码应该是一组前缀码。
4．图3的深度优先搜索序列：0 1 3 7 8 4 9 5 2 6 （2.5分） 广度优先搜索序列：0 1 2 3 4 5 6 7 8 9 （2.5分） 注：答案不唯一。
5. 用普里姆算法生成最小生成树的过程：（5分）
0 0 0 0 0
1
1
1
1
1 1
（3）（2分）
(4+5)*4+(10+6+8)*3+(12+18)*2=168
6. 得到的二叉排序树：（5分）
7.（8分）
(1) (5分)
散列函数H(k)=k mod 6；采用线性探测方法解决冲突：Hi=(H(k)+di) mod m ，其中i=1,2,…,m-1，m 为表长。
因此本题得到的散列表为：
（2）等概率情况下查找成功的平均查找长度：（3分）
ASL=）（161312316
1⨯+⨯+⨯+⨯=14/6=7/3 8. 所有可能的拓扑序列：(5分) V1,V5,V6,V2,V3,V4
四、 算法填空题（10分，每空2分）
(1) n-1 (2) k+1 (3) < (4) k ≠i (5) R[k ]。