第 1 学期
《 数据结构 》期末考试试卷（A卷）
一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题后的括号内。每题2分，共20分） 01． 以下序列不是堆的是( )。
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) 02． 当采用分快查找时，数据的组织方式为 ( ) A． B．
数据分成若干块，每块内数据有序
数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索
引块
C． 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D． 数据分成若干块，每块（除最后一块外）中数据个数需相同
03. 二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是 ( )
A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．以上答案都不对 04. 有n个叶子的哈夫曼树的结点总数为（ ）。
A．2n-1 B．2n C．2n+1 D．不确定 05. 有一个具有n个顶点的连通图生成的最小生成树中,具有( )条边 A、n B、n-1 C、n+1 D、2n-1 06. 下面的二叉树中，（ ） 不是平衡二叉树。
A B C D
07. 知U=‘xyxyxyxxyxy’；t=‘xxy’；依次执行下列运算后，ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（s，t），LEN（t）+1））；ASSIGN（m，‘ww’），则REPLACE（S，V，m）结果为( )。
A．’xyxywwyxy’ B．’xyxyxywwy’ C．’xyxyxwwxy’ D．’xyxywwxyx’ .
08. 设有数组A[i,j]，数组的每个元素长度为5字节，i的值为0 到5 ，j的值为0 到6，数组从内存首地址BA开始顺序存放，当用以行为主序存放时，元素A[5，5]的存储首地址为( )。
A. BA+180 B. BA+175 C. BA+200 D. BA+205
1
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(n2) 二、填空题（每空2分，共20分）
1. 与链式存储结构不同，顺序存储结构是通过____ ____表示元素之间的逻辑关系的。 2. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用 遍历方法最合适。
3. 在完全二叉树中，编号为i和j的两个结点处于同一层的条件是___ ___。 4.对于17个元素的有序表A[1]-A[17]作二分查找,在查找其等于A[8]的元素时需比较_____次. 5.树的三种存储结构是 双亲表示法、孩子表示法和 。
6. 若不考虑基数排序，则在内部排序过程中，主要进行的两种基本操作是关键字的比较和记录的 。
7.一个“好”的算法要考虑以下标准：正确性 、可读性 、 和效率与低存储量需求 。 8.已知一个无向图的邻接表如下图所示: 则从顶点1出发进行深度优先搜索遍历 得到的顶点序列为_____________和广度 优先搜索得到的顶点序列为______ __ ___ ____。
9. 在含有n个结点的二叉链表 中，其空链域个数是 。
第二题，第8小题图
三、分析计算题（1、3、5每题8分,2题6分,4题10分，共40分）
1．对于如下的连通图，请给出从顶点0出发，利用普里姆（Prim）算法求出它的最小生成树的过程中得到的顶点集和边集及最小生成树的权，并画出所得到的最小生成树。 0 12 5 2
1 4
6 8 4
3 2
5 6 16
15 13
12 9 20 10
（第三大题第1题图）
2．设F={T1，T2，T3}是森林（如下图所示），试将它转换为二叉树，画出所对应的二叉树。 A H I D E F B T1 T2 T3 J K 森林（第三大题第2题图）
3. 记录的关键字集合K={23，9，39，5，68，12，62，48，33 }，请给出采用快速排序法进行排序时每趟划分后的排序结果（选第一个记录为枢轴（支点）分割）。
4．给定关键字序列15,38,61,84,49,60,71,33,24,29,36，试分别用顺序查找、二分查找、二叉排序树查找、散列查找(其中，散列函数H(k)=k，用线性探查法和拉链法来解决冲突)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及两种散列查找的散列表)，并求出每一种查找的成功平均查找长度。
3
C G