【2017年整理】中国海洋大学数据结构期末试题A卷.docVIP

中国海洋大学全日制本科课程期末考试试卷 2014年 春 季学期 考试科目： 数据结构 学院： 信息科学与工程学院 试卷类型： A 卷 命题人: 张海燕 审核人：________ 考试说明：本课程为闭卷考试，共_3_页，除考场规定的必需用品外还可携带的文具有______________。 题号 一 二 三 四 五 六 七 八 九 总分 得分 一、填空题(1分，每空1.5分) 1、 二、选择题(2分，每题2分) 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 ? 4、以行序为主序方式，将n阶对称矩阵A的下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［0..(n(n+1))/2-1］中，则在B中确定aij（ij）的位置k的关系为(????)。 A. i*(i-1)/2+j???B. j*(j-1)/2+i?????C. i*(i+1)/2+j???D. j*(j+1)/2+i 5、深度为h的满m叉树的第k层有（??）个结点。(1=k=h) A．mk-1????????????B．mk-1?????? ?C．mh-1???? ??D．mh-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中有弧Vi,Vj????????????B．G中有一条从Vi到Vj的路径?? C．G中没有弧Vi,Vj????????????D．G中有一条从Vj到Vi的路径?? 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.??直接选择排序 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．?起泡排序 三、（分） 后序遍历序列：?G D B E I H F C