2013-2014第二学期数据结构期末考试试卷b卷.doc

合肥学院20 13 至20 14 学年第 2 学期 数据结构与算法设计 课程考试（B）卷 系 级 专业 学号 姓名 题号 一 二 三 四 五 六 七 八 九 十 总 分 得分 阅卷 大题得分 一、选择题：（2分×15=30分） 1．下面关于线性表的叙述错误的是（ ）。 A、 线性表采用顺序存储必须占用一片连续的存储空间 B、 线性表采用链式存储不必占用一片连续的存储空间 C、 线性表采用链式存储便于插入和删除操作的实现 D、 线性表采用顺序存储便于插入和删除操作的实现 2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。 A、 2m-1 B、 2m C、 2m+1 D、 4m 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。 A、 R-F B、 F-R C、(R-F+M)％M D、(F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。 A、 BADC B、 BCDA C、 CDAB D、CBDA 5．设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 A、 n(n-1)/2 B、 n(n-1) C、 n2 D、 n2-1 6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。 A、 9 B、 10 C、 11 D、 12 7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。 A、 n-1 B、 n C、n+1 D、2n-1 8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。 A、 2，3，5，8，6 B、 3，2，5，8，6 C、 3，2，5，6，8 D、 2，3，6，5，8 9. 设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4; r(38)=5; r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是（ ）。 A、 8 B、 3 C、 5 D、 9 10．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，则数据结构A是（ ）。 A、线性结构 B、 树型结构 C、 物理结构 D、图型结构 ．下面程序的时间复杂为（ ） for（i=1，s=0； i=n； i++） {t=1；for(j=1；j=i；j++) t=t*j；s=s+t；} A、 O(n) B、 O(n2) C、 O(n3) D、 O(n4) 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。 A、 O(1) B、 O(log2n) C、O(n) D、 O(n2) 13．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。 A、 n，e B、 e，n C、 2n，e D、 n，2e 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。 A、 N0=N1+1 B、 N0=Nl+N2 C、 N0=N2+1 D、 N0=2N1+l 15.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ ）。 A、 log2n+1 B、 log2n-1 C、 log2n D、 log2(n+1) 在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2． 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用 二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。 小题得分 小题得分 3．下图所示的森林：　　 (1) 求树（a）的先根序列和后根序列； (2) 求森林