《 数据结构 》期末考试试卷（A卷）
一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题后的括号内。每题2分，共20分）
01． 堆是一种数据结构, ( ) 是堆.
A、(10,50,80,30,60,20,15,18) B、(10,18,15,20,50,80,30,60)
C、(10,15,18,50,80,30,60,20) D、(10,30,60,20,15,18,50,80)
02．广义表有两个重要的基本操作,取列表表头Head(Ls) ,和取列表表尾Tail(Ls),请利用这两个操作取出Ls中原子f的运算是( ),已知广义表Ls=((a,b,c,d),(e,f,g,h)).
A、Head(Tail(Ls)) B、Tai(Head(Ls))
C、. Head(Tail(Head(Tail(Ls)))) D、Head(Tail(Tai(Head(Ls))))
03.若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则他的后序序列是( )
A、EFGHBCD B、FEGHDCB C、FEGBHDC D、EFBGCHD
04.在下列常用内部排序方法中属于不稳定排序的是( )
A、希尔排序,快速排序,简单选择排序,堆排序
B、希尔排序,快速排序,2-路归并排序,堆排序
C、直接插入排序,起泡排序, 希尔排序, 简单选择排序
D、2-路归并排序,堆排序, 希尔排序, 起泡排序
05.有一个具有n个顶点的连通图生成的最小生成树中,具有( )条边
A、n B、n-1 C、n+1 D、2n-1
06. 下面的二叉树中，（ ） 不是平衡二叉树。
A B C D
07.如下图给出由七个顶点组成的无向图,从顶点1出发,对它进行深度优先遍历得到的顶点序列是( )
A、1354267 ① ②
B、1347625
C、1534276 ③ ④ ⑦
D、1247653
⑤ ⑥
.
08. 将pascal语言的数组A[0..8,0..8]按行优先次序存储在起始地址为1000的连续的内存单元中，每个存储单元的长度为2，则元素A[7,3]的地址是 ( )
A、1132 B、 1134 C、1114 D、1112
09.依次读入数据元素序列{a,b,c,d,e,f}进栈,每进一个元素机器可要求下一个元素进栈和出栈.如此进行,则栈空时弹出的元素构成的序列不可能出现( )
A、{c,d,b,e,f,a} B、{d,c,e,b,f,a} C、{b,d,c,e,a,f} D、{b,e,d,a,c,f}
10.从具有n 个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为( )
A、0(n) B、0(1) C、0(logn) D、O(n²)
二、填空题（每空2分，共20分）
1.对于双向链表,在两个结点之间插入一个新结点时需要修改的指针共有____个。
2.已知完全二叉树的第10层有10个叶子结点,则整个二叉树的结点数最多为_______个。
3. 有K个叶子结点的哈夫曼树，其结点的总数为 。
4.对于17个元素的有序表A[1..17]作二分查找,在查找其等于A[8]的元素时需比较_____次.
5.树的三种存储结构是 双亲表示法、 孩子表示法 和 。
6.对二叉排序树进行 遍历，就可以得到排好序的顶点序列。
7.一个“好”的算法要考虑以下标准：正确性 、可读性 、 和效率与低存储量需求 。
8.已知一个无向图的邻接表如下图所示:
则从顶点Vo出发进行深度优先搜索遍历得到的顶点序列为_____________和广度优先搜索得到的顶点序列为_______________.
0
1
2
3
4
5
6
9. 在含有n个结点的二叉链表中，其空链域个数是 。
三、分析计算题（第1,2,3每题7分，4,5,6每题8分，共45分）
1. 试以数据集{2，5，7，9，13}为权值构造一棵哈夫曼树，并计算其带权路径长度
2．对于如下的连通图，请给出从顶点Vo出发，利用普里姆（Prim）算法求出它的最小生成树的过程中得到的顶点集和边集及最小生成树的权，并画出所得到的最小生成树。
12
6 8 15 13
16
4
12 9 20 10
5
（第2题图）
3．设F={T1，T2，T3}是森林（如下图所示），试将它转换为二叉树，画出所对应的二叉树。
T1 T2 T3
森林（第3题图）
4．某赋权有向图如下图所示：
用迪杰斯特拉（Dijkstra）算法思想，求源点A到各其余顶点的最短路径及路径长度
1 3
2
3
3
1 1
2
1
5
（第4题图）
5. 已知一组关键字序列（35 21 32 44 15 54 86 71 110 13 24 130 ），请给出采用快速排序法进行排序时每趟划分后的排序结果（选第一个记录为枢轴（支点）分割）。
6．假定一个待散列存储的数据集合为｛15,38,61,84,49,60,71,33,24,29,36｝，散列表长m=11，散列地址为HT[11]，若采用除留余数法（哈希函数H（K）＝K MOD 11）和线性探测法处理冲突。（1）试求出每一元素在散列表中的存储地址，并画出最后得到的散列表。（2）求出查找成功条件下的平均查找长度。
四、算法设计题（第1题7分，第2题8分，共15分）
1. 二叉树以二叉链表存储，设计算法求二叉树中度为2的结点的个数。
2. 编写算法完成按递增次序打印给定的链表(数据域为整型)head中各结点的操作。打印的方法是每一次寻找链表中值最小的结点，打印该结点数据后，把该结点从链表中删除，重复此操作直到链表为空为止。
安徽大学2004-2005学年第2学期
《 数据结构》A试卷 参与评分标准
一、 单项选择（每小题2分，共20分）
1.B 2.C 3.B 4.A 5.B 6.A 7.C 8.A 9.D 10.A
二、填空题（每空2分，共24分）
1. 4 ； 2. 211-21或2027；3. 2K-1；4. 5； 5.孩子兄弟表示法； 6.中序； 7.健壮性；
8.Vo,V3,V6,V4,V1,V5,V2(或0-3-6-4-1-5-2) ； Vo,V3,V2,V6,V5,V4,V1(或0-3-2-6-5-4-1)；9．n+1
三、应用题(1、2、3每小题7分，4、5、6每小题8分，共45分)
1． 构造的哈夫曼树如图所示：
2．
（1） 画出2、5、7得2分，画出整个哈夫曼树得4分
（2）
（2）其带权路径长度WPL=（2+5）*3+（7+9+13）*2=79 （7分）
2．
（1）顶点集U={0,1,6,2,3,4,5} （2分）
（2）边集TE={（0，1）6，（1，6）4，（6，2）9，（2，3）5，
（3，4）10，（0，5）12} （4分）
（7分），正确画出最小生成树得7分。
3、所对应的二叉树如图所示
（1分） （3分） （5分） （7分）
若不完全正确，酌情给分。
4、用Dijkstra算法思想计算源点A到各顶点的最短路径如下表所示
其中A到B、C、D、E最短路径正确分别得1分，A到F、G最短路径正确分别得2分
5.
一次划分后{24，21，32，13，15}35{86，71，110，54，44，130} (2分)
二次划分后{15，21，13}24{32}35{44，71，54}86{110，130} （4分）
三次划分后{13}15{21}24{32}35， 44 {71，54，}86，110{130} （6分）
四次划分后{13}15{21}24{32}35，44，{54}71，86，110{130} （8分）
结束{13，15，21，24，32，35，44，54，71，86，110，130}
仅写出最终的排序序列，不得分。
6、（1）
（2）ASL=（1*7+4+5+6*2）/11=28/11
正确答出线性探测法给5分（其中正确计算哈希地址给2分，正确解决冲突给3分）
正确算出平均查找长度给3分。
四、算法设计题
1．Function getnumber(bt:link):intrger
Begin
If bt=nil then getnumber:=0 （1分）
Else if (bt^.lchild<>nil) and (bt^rchild<>nil)
Then getnumber :=getnumber(bt^.lchild)+getnumber(bt^.rchild)+1 （4分）
Else getnumber :=getnumber(bt^.lchild)+getnumber(bt^.rchild) （7分）
End
此题答案不唯一。算法设计不完全正确，可酌情给分。
2. Procedure print_order(head:linklistp);
Var p,s,:linklistp;
Temp:interger;
Begin
P:=head;temp:=p^.next.data;s:=p; （1分）
Repeat
While (p^.next.data<>nil) do
Begin
If p^.next.data S:=p; Temp:=p^.next.data; End （4分） P:=p^next End; （5分） P:=head; Write(s^.next.data); （6分） S:=p; Until p^.next=nil End. （8分） 此题答案不唯一。算法设计不完全正确，可酌情给分。下载本文
