数据结构期末试卷及答案

《数据结构期末试卷及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、单项选择题（本大题共15小题，第小题2分，共30分）在每小题列出的四个选项中只有一个符合题目要求，请将其代码填在题后的括号内。错选或未选均无分。1.算法必须具备输入、输出和　　　　　　　　　　　　　　[　C]A.计算方法　　　　　　　　　B.排序方法C．解决问题的有限运算步骤　　D.程序设计方法2.有n个节点的顺序表中，算法的时间复杂度是O(1)的操作是　[　A]A.访问第i个节点（1≤i≤n）B.在第i个节点后插入一个新节点（1≤i≤n）C.删除第i个节点（1≤i≤n）D.将n个节点从小到大排序3．单链表的存储密度　　　　　　　　　　　　　　　　　　　[C　]A．大于1　　　　　　　　B

2、.等于1C．小于1　　　　　　　　D.不能确定4．设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是　　　　　　　　　　　　　[B　]A．23415　　　　　　　　B.54132C．23145D.154325.循环队列SQ的存储空间是数组d[m]，队头、队尾指针分别是front和rear，则执行出队后其头指针front值是　　　　　　　　　　　　　　[　D]A．front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m6.在一个具有n个结点的有序单链表

3、中插入一个新结点并仍然保持有序的时间复杂度是[B]A.O(1)B.O(n)C.O(n2)D.O(nlogn)7.设二维数组A[0..m-1][0..n-1]按行优先顺序存储，则元素A[i][j]的地址为　　　　　　　　　　　　　　　　　　　　　　　　　　　　[B]A．LOC(A[0][0])+(i*m+j)　B．LOC(A[0][0])+(i*n+j)C.LOC(A[0][0])+[(i-1)*n+j-1]D.LOC(A[0][0])+[(i-1)*m+j-1]8.一个非空广义表的表头　　　　　　　　　　　　　　　　　[D]A．一定是子表　　　　　　　B.一定是原子13C．不能是子表　　　　　

4、　　D.可以是原子，也可以是子表9．具有n个节点的完全二叉树的深度为　　　　　　　　　　　[A]A．élog2(n+1)ù-1B.log2n+1C.log2nD.ëlog2nû10.若要惟一地确定一棵二叉树，只需知道该二叉树的　　　　　[D]A．前序序列　　　　　　　　　B.中序序列C．前序和后序序列　　　　　　D.中序和后序序列11．在一个无向图中，所有顶点的度数之和等于图的边数的　　　倍[C]A．1/2B.1C.2D.412.拓扑排序运算只能用于　　　　　　　　　　　　　　　　[C]A．带权有向图　　　　　　　　　B.连通无向图C．有向无环图　　　　　　　　　D.无向图13．在所有排序方法

5、中，关键字比较的次数与记录的初始排列次序无关的是　　　　　　　　　　　　　　　　　　　　　　　　　　[D]A．希尔排序　　　　　　　　　　B.冒泡排序C．插入排序　　　　　　　　　　D.选择排序14．下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是　　　　　　　　　　　　　　　　　　　　　　　　　　　[C]A．堆排序　　　　　　　　　　　B.冒泡排序C．直接选择排序　　　　　　　　D.快速排序15．二分查找要求节点[A]A．有序、顺序存储　　　　　　　　B.有序、链接存储C．无序、顺序存储　　　　　　　　D.无序、链接存储一、填空题（本大题共10小题，每小题2分，共20分）不写

6、解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。16．数据的逻辑结构分为两大类，它们是线性结构和　　　非线性结构　。17．在单链表中（假设结点指针域名称为next），删除指针P所指结点的后继结点的语句是13p->next=p->next->next。18．已知循环队列用数组data[n]存储元素值，用front,rear分别作为头尾指针，则当前元素个数为(rear-front+n)%n。19．若n为主串长，m为子串长，则串的朴素匹配算法最坏的情况下需要比较字符的总次数为_______（n-m+1）×m__。20．广义表((a),((b),j,(((d)))))的表尾是____(((

7、b),j,(((d)))))________。21．已知二叉树有61个叶子节点，且仅有一个孩子的节点数为45，则总节点数为____166__。22．解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应是一个　队列结构。23．n个顶点e条边的图采用邻接表存储，深度优先遍历算法的时间复杂度为_________O(n+e)___________。24．对于n个关键字的集合进行冒泡排序，在最坏