2012《数据结构》期末试卷（A卷）

2012 A卷 【 字号： 大 中 小 】 2011－2012年 春 季学期计算机科学与技术、软件工程、网络工程专业 《数据结构》期末试卷（A卷） 卷面总分：100分 答题时间：120分钟 专业 年级 班级 姓名 学号 题一 二 三 四 五 六 七 八 九 十 总分 号 得分 一、 单项选择题（本大题共15小题，每小题1分，共15分 答案写在答题卡上） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答题卡 题号 答案 1. 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。 x=2; while(x0）。 A．表元素 B．数据元素 C．字符 D．数据项 3. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。 A. O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 4. 设栈的输入序列是1，2，3，4,则( )不可能是其出栈序列。 A. 1，2，4，3 B. 2，1，3，4 C. 1，4，3，2 D. 4，3，1，2

5. 设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是( )。

A. 4 B.3 C.2 D. 1

6. 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。

A. 栈 B. 队列 C. 树 D. 串 7. 串是一种特殊的线性表，下面哪个叙述体现了这种特殊性( )。 A. 可以顺序存储 B.数据元素是一个字符 C. 数据元素可以是多个字符 D. 可以链接存储

8.已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是( )。

A. 119 B. 111 C. 52 D. 39 9. 一个具有1025个结点的二叉树的高h为( )。 A．10至1024之间 B．11至1025之间 C. 10 D. 11 10. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )。 A．M1+M2 B．M2+M3 CM3 D. M1

11. 设无向图的顶点个数为n，则该图最多有( )条边。

A．n-1 B．n2 C．n(n+1)/2 D．n(n-1)/2 12. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A. (n-1)/2 B. n/2 C. n D. (n+1)/2 13. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。

A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90)

C. (100,60,80,90,120,110,130) D. (100,80,60,90,120,130,110)

14. 一组记录的关键字为{46、79、56、38、40、84},则利用快速排序的方法,以第一个记录为枢轴得到的一次划分结果是( ) A.38、40、46、56、79、84 B.40、38、46、79、56、84 C. 40、38、46、56、79、84 D. 40、38、46、84、56、79 15. 在下列排序方法中, ( )方法可能出现这种情况：在最后一趟开始之前,所有的元素都不在其最终应在的正确位置上。 A.快速排序 B.冒泡排序 C. 插入排序 D. 堆排序 二、判断题（本大题共 5小题，每小题 1 分，共 5 分正确的打“√”，错误打“×”）， 1. 所谓一个排序算法是否稳定,是指该算法在各种情况下的时间效率是否相差不大。( ) 2. 知道链表中结点的指针就可以访问该结点，所以链表是随机存取结构。( ) 3. 非空广义表的取尾操作的结果是除去广义表第一个元素后的剩余元素。( ) 4. 图的邻接矩阵存储结构所占空间只与图的顶点的个数有关，和边数无关。( ) 5. 具有n个关键字的有序表的判定树的树形是唯一的，而其二叉排序树的树形取决于输入次序。( ) 三、 应用题（本大题共6小题，各题的分数在小题中给出，共60分） 1. （5分）求串’ababaaababaa’ 的next函数值。 j 1 2 3 4 5 6 7 8 9 10 a b a b a a a b a b t串 next[j] 2.（15分）已知一个森林的先序序列和后序序列如下: 先序序列：ABDECFHIG 后序序列：DBEAHFICG 请（1）构造出该森林， （2）并画出该森林对应的二叉树， （3）写出对二叉树遍历的后序序列。

3. （10分）已知有向图G的顶点是编号1－5，其邻接矩阵如下。请画出其从顶点1开始遍历的（1）深度优先生成树和（2）宽度优先生成树。

4. （10分）设有序表L=(5,7,9,12,16,19,25,47,63,76,82,90)。（1）画出该有序表的判定树，（2）求其查找成功时的平均查找长度，（3）求其查找失败时的平均查找长度，（4）查找47时需经过哪几个结点。