烟台大学数据结构试题2010~2011年度

数据结构 试卷B

（考试时间为120分钟）

题号 得分 阅卷人 一 二 三 四 五 合分人 总分 （注：第三大题答案请写在后面的空白答题纸上） 一、单项选择题(每小题2分，共20分)

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( d )

A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构

2.在长度为n的顺序表的第i (1≤i≤n+1)个位置上删除一个元素，元素的移动次数为( B ) A.n-i+1 B.n-i C.i D.i-1 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( c )

A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的出栈的不同排列个数为( b ) A.4 B.5 C.6 D.7

5.已给下图1，哪一项是该图的拓扑排序序列 ① （ a ） ② ③

④ ⑤

(图1)

A．1，2，3，4，5 B．1，3，2，4，5 C．1，2，4，3，5 D．1，2，3，5，4 6. 一组记录的值为(12,38,35,25,74,50,63,90),按2路归并排序方法对序列进行一趟归并后的结果为( a )。

A.12,38,25,35,50,74,63,90 B.12,38,35,25,74,50,63,90 C.12,25,35,38,50,74,63,90 D.12,35,38,25,63,50,74,90 7.n个顶点的有向图中含有向边的数目最多为 ( d )

A.n-1 B.n C.n(n-1)/2 D.n(n-1)

8.AVL树是一种平衡的二叉排序树，树中任一结点的( b )

A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 9.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 10.为查找某一特定单词在文本中出现的位置，可应用的串运算是( d )

A.插入 B.删除 C.串联接 D.子串定位

二、填空题(每小题2分，共20分)

1. 存储结构是逻辑结构的____物理______实现。 2. 若一个算法中的语句频度之和为T(n)=n+4nlogn，则算法的时间复杂度为___ nlogn _____。

1

3. 设二维数组A[1..10,1..20]按行优先顺序存储,每个元素占4个存储单元，A[1，1]的存储地址是1000，则A[5，6]的存储地址是 1260 。

4. 在无向图的邻接矩阵A中，若A〔i,j〕等于1，则A〔j,i〕等于__1______。 5.在具有n个单元的循环队列中，队满时共有___ n-1______个元素。

6.在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找查找元素24，需进行 4 次元素之间的比较。

7.深度为h的完全二叉树至少有___ 2______个结点，至多有__2-1_______个结点。 8.直接插入排序需要____ O(1)_____个记录的辅助空间。

9.在直接插入排序和快速排序中，若初始数据基本有序，则选用_直接插入________；在冒泡排序和堆排序中，若要求数据的稳定性，则选用__冒泡_______。

10．广义表运算式TAIL(((a,b)，(c,d))) 的运算结果为 ((c,d)) 。

h-1

h

三．应用题（每小题5分，共40分）

1． 设有序列(45，24，53，12，28，90)，请构成一棵二叉排序树，并求其查找成功时的平均

查找长度。

2． 对关键字序列(42，13，24，91，23，16，05，58)进行堆排序，使之按关键字递增次序排

列，请写出排序过程中建初始堆的过程。

3． 已知散列表长度为11，散列函数为H(key)=key％9，处理冲突的方法为拉链法，请画出依

次插入关键字（8,10,14,19,21,23,28,32,48）以后的散列表。

4． 已知某二叉树按中序遍历次序是BDCEAFHG，按后序遍历次序是 DECBHGFA，试画出

该二叉树的形状，并写出它的前序扫描序列。

5． 以数据集（7，19，2，6，32，3，21，10）为叶结点的权值，构造一棵哈夫曼树。 6． 已给无向图如图2所示，用Prim算法画出该图从顶点1开始的最小生成树。 A 6 2 1 1 2 3 C B 5 10 3 2 3 4 D E F G 4 5 6 7 8 H （图2）

5 6 (图4)

（图3）

７．无向图如图3所示，要求：写出该图从顶点1开始的广度优先和深度优先搜索序列。 ８．将图4所示的二叉树转化为森林。

四．算法设计题（共2小题，共20分）

1． 设有两个栈s1和s2共享同一数组存储空间stack［m］，请编写栈s1和s2的进栈操作push(i,x)和退栈操作pop(i)， 其中i=1、2，分别表示栈s1和s2。要求：仅当整个空间stack［m］占满时才产生上溢。（10分）

2．写出求一棵二叉树的叶子结点个数的算法。二叉树的存储结构为二叉链表，要求写出二叉链表的类型定义。（10分）

2

烟台大学20 1o ～20 11 学年第 二 学期 数据结构试卷A参考答案及评分标准 考试方式： 闭卷 （开卷、闭卷、其他） 院系： 计算机学院 年级： 02级专 专业： 计算机 …………………………………………………………………………………………….. 注：标准答案、参考答案要点及评分标准须写清题号、每小题得分、共得分等。 此格式为题头，如本页不够，后面请附相同规格（A4）的纸张。 …………………………………………………………………………………………….. 一、选择题(每小题2分，共20分) 1.A 2.D 3.A 4.C 5.C 6.D 7.D 8.D 9.A 10.D 二、填空题(每小题2分，共30分) 1. 物理 2. nlogn 3. 913 4. 1 5. lq->front->next==lq->rear 6. (sq.front+1)%(m+1) 7. sq.front=(sq.front+1)%(m+1) 8. 4 9. top==0 10. 3 11. 2h-1 12. 4 13. 直接插入、冒泡 14. ((c,d)) 15.(10,28,36,42,59,84) 三、应用题(每小题5分，共35分) 45 1. 24 12 28 53 90 ASLsucc=(1*1+2*2+3*3)/6=7/3 2. 20 75 87 56 23 36 75 87 20 56 56 23 20 87 75 61 36 29 61 29 61 36 29 23 3

56 87 75 20 61 36 20 56 75 87 61 36 29 23 29 23 3. 地址 元素 0 1 23 2 57 3 46 4 56 5 27 6 7 40 8 8 9 19 10 10 11 21 12 查找成功时的ASLsucc(1124111212)101610 查找不成功时的ASLun(1654321654321)134313 4. 5. A F B 前序序列：ABCDEFGH D C E G H 2 3 6 17 9 24 10 6. 1 7. 1 16 2 1 16 2 5 3 1 16 2 4 4 5 3 1 16 2 4 4 5 3 1 16 2 5 3 6 11 4 5 7 4 5 7 V1 0 V2 2/V1 V3 3 3/V1 V4 12 7 6/V3 V5   13 13 13/V3 V6   11 10/V4 4

四．算法设计题（共2小题，共15分） 1. void DeleteEqual2(LinkekList L) 2. int BinTreeDepth(BitTree T) {//删除元素非递减排列的链表L中所有值相同的元素 {if(T==NULL)return 0; p=L->next;q=p->next; else{l=BinTreeDepth(T->lchild); while(p->next) r=BinTreeDepth(T->rchild); {if(p->data!=q->data) return((l>r?l:r)+1); { p=p->next;q=p->next; } } else } { //当相邻元素相等时删除多余元素 p->next=q->next; free(q);q=p->next; } } } 5

6