安徽大学2014数据结构期末考试试卷(a卷)

《安徽大学2014数据结构期末考试试卷(a卷)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、安徽大学2014-2015学年第一学期《数据结构》期末考试试卷(A卷)(含参考答案)一、单项选择题(本大题共15小题，第小题2分，共30分)在每小题列出的四个选项中只有一个符合题目要求，请将其代码填在题后的括号内。错选或未选均无分。1.算法必须具备输入、输出和[C1A.计算方法B.排序方法C.解决问题的有限运算步骤D.程序设计方法2.有n个节点的顺序表中，算法的时间复杂度是0(1)的操作是[A]A.访问第i个节点B.在第i个节点后插入一个新节点(KiSn)C.删除第i个节点D.将n个节点从小到大排序3.单链表的存储密度[C]A.大于1B.等于1C.小于1D.不能确定4.循环队列SQ的

2、存储空间是数组d[m]，队头、队尾指针分别是front和rear,则执行出队后其头指针front值是[DJA.front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m5.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是[B]A.0(1)B.0(n)C.0(n2)D.O(nlogn)6设二维数组A[0..m-l][0..n-l]按行优先顺序存储，则元素A[i]U]的地址为[B]A.LOC(A[0ir01)+(i*m+j)B.LOC(A問[01)+(i*n+j)C.LOC

3、(A[0][0])+[(i-l)*n+j-l]D.LOC(A[0][0])+[(i-1)*m+j-l]7.设将整数1，2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻(只要栈不空)进行，则出栈序列不可能是[B]B.54132A.234158.一个非空广义表的表头A.定是子表B.—定是原子[D1C.不能是子表D.可以是原子，也可以是子表9.具有n个节点的完全二叉树的深度为[A]A.riog2(n+1)1-1B.Iog2n+1C.Iog2nD.Llog2nJ10.若要惟一地确定一棵二叉树,只需知道该二叉树的[D]A.前序序列B.中序序列C.前序和后序序列D.中序和后序序列11.在一

4、个无向图中，所有顶点的度数之和等于图的边数的倍[C]A.1/2B.1C.2D.412.拓扑排序运算只能用于1CJA.带权有向图B.连通无向图C.有向无环图D.无向图13.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是[D]A.希尔排序B.冒泡排序C.插入排序D.选择排序14.下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是[C1A.堆排序B.冒泡排序C.直接选择排序D.快速排序15.二分查找要求节点[A]A.有序、顺序存储B.有序、链接存储C.无序、顺序存储D.无序、链接存储二、填空题(本大题共10小题，每小题2分，共20分)不写解答过程，将正确的答案

5、写在每小题的空格内。错填或不填均无分。16.数据的逻辑结构分为两大类，它们是线性结构和非线性结构。17.在单链表中(假设结点指针域名称为next),删除指针P所指结点的后继结点的语句是p-〉next=p-〉next-〉next018.已知循环队列用数组data[n]存储元素值，用front,rear分别作为头尾指针，则当前元素个数为(rear-front+n)%n。19.若n力主串长，m为子串长，则串的朴素匹配算法最坏的情况下耑要比较字符的总次数为(n-m+1)Xm。20.广义表的表尾是(((b)'i，(((d)))))。21.已知二叉树有61个叶子节点,且仅有一个孩子的节点数为45

6、,则总节点数为166。22.解决计算机与打印机之间速度不匹配W题，须要设置一个数据缓冲区，应是一个队列结构。23.n个顶点e条边的阁采用邻接表存储，深度优先遍历算法的时间复杂度为0(n+e)o24.对于n个关键字的集合进行冒泡排序，在最坏情况下所需要的时间为_0(n2)25.在一个长度为n的顺序表中的第i个元素(Ki^n)之前插入一个元素时，需向后移n-i+1个元素。三、解答题(本大题共4小题，共25分)26.对于下面的稀疏矩阵，画出其三元组法存储表示(假设下标从0开始)。(5分)001400070000001500000-6000241800000答案:2345021414•620

7、7252433184115行号列号值16.已知一棵二叉树的中序序列和后序序列分别如下，请画山该二叉树。（5分）巾序序列：DIGJLKBAECHF后序序列：ILKJGDBEHFCA答案:29.己知一个图的邻接表如下所示。（8分）（1）画出该阁的阁形；（4分）（2）根据邻接表分别画出从顶点a出发进行深度优先和广度优先遍历所生成的生成树。（4分）A答案:深度优先生成树:广度优先生成树:aU!算法阅读题（本大题共3小题，每小题5分，共15分）29.设线性表的n个结