学号: 姓名: 专业年级: 授课教师： 张海燕 考场教室号: 座号: ----------------装---------------- -------------订--- ------------------------线------------------------ 中国海洋大学全日制本科课程期末考试试卷
2014年 春 季学期 考试科目： 数据结构 学院： 信息科学与工程学院
试卷类型： A 卷 命题人: 张海燕 审核人：________
考试说明：本课程为闭卷考试，共_3_页，除考场规定的必需用品外还可携带的文具有______________。
题号 得分
一 二 三 四 五 六 七 八 九 总分 一、填空题(15分，每空1.5分)
1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
2、对于双向链表,在两个结点之间插入一个新结点需修改的指针数共 ______个。
3、对于一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为________。
4、串是一种特殊的线性表，其特殊性表现在组成串的数据元素只能是________。 5、所谓稀疏矩阵指的是_______________________________________。 6、广义表（a,(b,c),d,e）的表尾为_____________________。 7、线索二叉树中结点的左线索指向其_____________。
8、Prim（普里姆）算法适用于求____________的网的最小生成树； 9、算法的时间复杂度是_________________________________。 10、树的后序遍历序列与其对应的二叉树______遍历序列相同。
二、选择题(28 分，每题2分)
1、设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 2、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），不能得到的出栈序列是( )。
A．XYZ B. YZX C. ZXY D. ZYX 3、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。 A．rear=front B. (rear+1) MOD n=front
C．rear+1=front D. (rear-l) MOD n=front
---------------------------------------------------------------------------------------------------------------- 第1页 共4页 ＋ ----------------------------------------------------------------------------------------------------------------＋----------------------------------------------------------------------------------------------------------------
4、以行序为主序方式，将n阶对称矩阵A的下三角形的元素(包括主对角线上所有元素)依次存
放于一维数组B［0..(n(n+1))/2-1］中，则在B中确定aij（i 5、深度为h的满m叉树的第k层有（ ）个结点。(1= k-1 kh-1h A．m B．m-1 C．m D．m-1 6、若一棵二叉树具有9个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。 A．9 B．10 C．15 D．不确定 7、下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。 A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆 8、 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 A．G中有弧 9、下面关于求关键路径的说法不正确的是（ ）。 A．求关键路径是以拓扑排序为基础的 B．一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同 C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续 时间之差 D．关键活动一定位于关键路径上 10、具有12个关键字的有序表，折半查找的平均查找长度为（ ）。 A. 3 B. 4 C. 2.5 D. 5 11、下列关于m阶B-树的说法错误的是( ) 。 A．根结点至多有m棵子树 B．所有叶子都在同一层次上 C. 非叶子结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D. 根结点中的数据是有序的 12、在下列排序算法中,哪一个算法的时间复杂度与初始序列无关（ ）。 A． 直接插入排序 B. 冒泡排序 C. 快速排序 D. 直接选择排序 ---------------------------------------------------------------------------------------------------------------- 第2页 共4页 ＋ ----------------------------------------------------------------------------------------------------------------＋---------------------------------------------------------------------------------------------------------------- 13、下列排序算法中，( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 14、有一随机数组(25,84,21,46,13,27,68,35,20),采用某种方法对它们进行排序,其每趟排序 结果如下, 则该排序方法是（ ）。 初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 A．基数排序 B．快速排序 C．堆排序 D． 起泡排序 三、（6分）已知某二叉树的后序遍历和中序遍历如下，构造出该二叉树。 后序遍历序列： G D B E I H F C A 中序遍历序列 ：D G B A E C H I F 由二叉树的前序遍历和后序遍历结果能否唯一确定一棵二叉树？ 四、（6分） 若叶子结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼 夫树的带权路径长度WPL。 授课教师： 张海燕 考场教室号: 座号: 五、（8分） -------订--- ------------------------线------------------------ （1）输入序列(46,88,45,39,70,58,101,10,66,34)，给出构造一棵二叉排序树的步骤。 （2）指出二叉排序树与平衡二叉树的区别。 六、（10分）设哈希函数H(k)=K mod 7, 哈希表的地址空间为0～6，对关键字序列 {32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找关键字21 需要进行几次比较。 七、（12分）对下图中的带权有向图， 1）写出其邻接表结构； 2）根据邻接表结构，写出从顶点a出发,深度优先遍历所得到的顶点序列； 3）利用Dijkstra算法，求图中顶点a到其它各顶点的最短路径，写出执行的过程。 10 a100 30 e60 d20 b50 c 10 ---------------------------------------------------------------------------------------------------------------- 第3页 共4页 ＋ ----------------------------------------------------------------------------------------------------------------＋---------------------------------------------------------------------------------------------------------------- 八、（10分）设计算法将一个带头结点的单链表A分解为两个带头结点的单链表B、C，其 中B表中的结点为A表值小于0的结点，而C表中的结点为A表值大于等于0的结点（链表A的元素类型为整型，要求B、C表利用A表的结点进行存储） 九、（5分） 假设非空二叉树采用二叉链表存储，请设计一个递归算法，输出二叉树中度为2的结点数目。 ＋------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 第4页 共4页 ＋
中国海洋大学2014数据结构期末试题A卷
