数据结构专项试题及答案12

数据结构专项试题及答案12考试时间：______分钟总分：______分姓名：______一、单项选择题（在每小题的备选答案中，只有一个是正确的，请将正确答案的字母序号填在题后的括号内。每小题1分，共20分）1.下列数据结构中，属于非线性结构的是（）。A.队列B.栈C.双向链表D.二叉树2.在线性表中进行插入和删除操作时，效率最高的存储结构是（）。A.顺序表B.双向链表C.单向链表D.线性链表3.一个顺序存储的线性表L，假设表长为n，则在第i个位置（1≤i≤n）插入一个新元素的平摊时间为（）。A.O(1)B.O(n)C.O(i)D.O(n-i)4.删除顺序存储的线性表L中第i个位置（1≤i≤n）的元素，需要向前移动（）个元素。A.i-1B.iC.n-iD.n-i+15.设栈S和队列Q的初始状态均为空，依次对栈S和队列Q进行以下操作：向S中压入元素a,b,c；将S中的所有元素依次出栈并入队Q；向Q中出队一个元素。此时Q中剩下的元素是（）。A.a,bB.b,cC.cD.空6.一个栈的输入序列为1,2,3,4,5，则通过栈可以实现输出序列2,3,4,5,1的输出，所使用的辅助结构是（）。A.另一个栈B.队列C.双端队列D.顺序表7.队列的“先进先出”特性是指（）。A.只能在队头插入元素B.只能在队尾删除元素C.先插入的元素先被删除D.先插入的元素最后被删除8.对于一个具有n个结点的二叉树，其深度最多为（）。A.nB.log2(n)C.n!D.2^n9.在二叉树的遍历中，先访问根结点，然后遍历左子树，最后遍历右子树，这种遍历方式称为（）。A.中序遍历B.前序遍历C.后序遍历D.层次遍历10.设一棵二叉树的先序遍历序列为ABCD，中序遍历序列为BCAD，则其后序遍历序列为（）。A.BCADB.CDABC.DCBAD.CBAD11.判断一棵树是否为二叉搜索树，需要满足的条件是（）。A.左子树为空或其根值小于父节点值，右子树为空或其根值大于父节点值B.所有节点的左子树和右子树的高度差不超过1C.树中所有节点的值都唯一D.树中存在一个根节点12.在各种查找方法中，平均查找长度与元素个数n无关的是（）。A.顺序查找B.二分查找C.哈希查找D.B-树查找13.当哈希表发生冲突时，常用的处理方法有（）。A.线性探测法B.平方探测法C.双散列法D.以上都是14.下列排序算法中，不稳定排序算法是（）。A.冒泡排序B.插入排序C.快速排序D.堆排序15.在所有n个元素的排序算法中，平均时间复杂度最低的是（）。A.O(nlogn)B.O(n^2)C.O(n)D.O(n!)16.下列数据结构中，适合表示稀疏矩阵的是（）。A.顺序表B.稀疏矩阵压缩存储（如三元组表）C.完全二叉树D.堆17.图G采用邻接矩阵存储，其第i行（或第j列）中非零元素的个数是顶点i（或j）的（）。A.度B.邻接点数C.出度（有向图）D.入度（有向图）18.对于有向图，其邻接矩阵中第i行第j列的元素为1表示（）。A.顶点i和顶点j有边相连B.顶点i邻接到顶点jC.顶点j邻接到顶点iD.顶点i和顶点j没有边相连19.使用深度优先搜索算法遍历一个连通无向图，必定能访问到图中所有顶点。（）A.正确B.错误20.Dijkstra算法解决的是图中的（）问题。A.最短路径B.最小生成树C.所有顶点对之间的最短路径D.拓扑排序二、多项选择题（在每小题的备选答案中，有二个或二个以上是正确的，请将正确答案的字母序号填在题后的括号内。每小题2分，共10分）1.下列关于栈的叙述中，正确的有（）。A.栈是先进后出的线性表B.栈具有记忆性C.栈顶元素总是最后被插入的元素D.栈底元素总是最后被删除的元素E.栈的插入和删除操作都在栈底进行2.下列关于二叉树的叙述中，正确的有（）。A.二叉树是度为2的有序树B.二叉树的结点可以有零个、一个或两个子结点C.二叉树可以是空树D.深度为k的二叉树最多有2^k-1个结点E.完全二叉树中，若一个结点没有左子结点，则它一定没有右子结点3.下列关于线性表的叙述中，正确的有（）。A.线性表是n个数据元素的有限序列B.线性表中的每个元素都有且只有一个直接前驱和直接后继（除首尾元素外）C.顺序表是线性表的顺序存储结构D.链表是线性表的链式存储结构E.线性表可以是空表4.下列关于查找的叙述中，正确的有（）。A.顺序查找适用于无序线性表B.二分查找适用于有序线性表C.哈希查找的平均查找长度与元素个数有关D.B-树是一种平衡的多路查找树E.查找成功的平均查找长度小于查找不成功的平均查找长度5.下列关于排序的叙述中，正确的有（）。A.排序算法的稳定性是指排序后关键字相同的元素保持原来的相对位置不变B.归并排序是一种稳定的排序算法C.快速排序的平均时间复杂度是O(n^2)D.堆排序的空间复杂度是O(1)E.基数排序适用于元素范围较大的排序问题三、填空题（请将答案填写在题后的横线上。每空1分，共15分）1.在栈的运算中，插入元素的操作称为_______，删除元素的操作称为_______。2.队列的运算特性是“先进先出”，通常将_______端称为队头，将_______端称为队尾。3.对于一棵具有n个结点的二叉树，其所有结点的度数之和为_______。4.在二叉树的遍历中，若先遍历根的左子树，再遍历根结点，最后遍历根的右子树，称为_______遍历。5.哈希表是通过计算元素的_______来确定其在表中的存储位置。6.堆是一种特殊的_______树，它满足堆的性质：任何一个结点的值均不大于（或不小于）其子结点的值。7.对于具有n个顶点和e条边的无向图，其邻接矩阵是一个_______矩阵，且矩阵中第i行（或第j列）的元素之和等于顶点i（或j）的_______。8.图的遍历方法主要有_______遍历和_______遍历。9.在快速排序算法中，通常采用_______方法来选取基准元素。10.算法的时间复杂度通常用_______和_______两种方法来表示。四、简答题（请简要回答下列问题。每小题5分，共20分）1.简述线性表和栈的区别与联系。2.简述二叉树和树的区别。3.简述哈希查找的基本原理及其优缺点。4.简述快速排序算法的基本思想。五、综合应用题（请根据题目要求完成下列问题。每小题10分，共30分）1.设线性表L为（1,2,3,4,5），请分别写出对L进行以下操作后的结果：a.在第3个元素之后插入元素6。b.删除第2个元素。c.将L逆置。2.已知一棵二叉搜索树的前序遍历序列为E,A,C,B,D,F,G,H，请画出该二叉搜索树的结构图。3.假设哈希表H的大小为11（即H[0]到H[10]），采用线性探测法解决冲突，哈希函数为H(key)=keymod11。现要将关键字序列（22,41,53,46,30,13,12,67）依次插入哈希表H中，请写出哈希表H最终的状态，并指出每个关键字插入后可能遇到的冲突及解决方法。试卷答案一、单项选择题1.D2.B3.B4.C5.B6.A7.C8.A9.B10.D11.A12.C13.D14.C15.A16.B17.B18.B19.A20.A二、多项选择题1.A,B,C2.A,B,C,D3.A,C,D,E4.A,B,D,E5.A,B,D,E三、填空题1.入栈，出栈2.队头，队尾3.n-14.前序5.关键字（或散列值）6.二叉7.n*n，度8.深度优先，广度优先9.随机10.大O表示法，大Ω表示法（或渐近上界，渐近下界）四、简答题1.线性表是逻辑上相邻的元素组成的序列，元素间一对一关系，两端均可访问；栈是后进先出的线性表，元素间一对一关系，只允许一端（栈顶）访问。联系：栈可以看作是线性表的一种特殊形式。2.二叉树是每个结点最多有两个子结点的树，有严格的左右子树区分；树是包含根结点且每个结点最多有一个父结点的层次结构，结点度数无限制，无严格左右子树区分。3.哈希查找通过哈希函数将关键字映射到存储地址，优点是平均查找速度快（O(1)）；缺点是存在冲突问题，需要解决冲突方法，且空间利用率可能不高，查找不成功需要和查找成功一样多的比较。4.快速排序的基本思想是：选择一个基准元素，将线性表划分为两个子表，使得左子表中所有元素小于等于基准元素，右子表中所有元素大于等于基准元素，然后分别对左右子表递归进行快速排序。五、综合应用题1.a.(1,2,3,6,4,5)b.(1,3,4,5)c.(5,4,3,2,1)2.（根据前序遍历E,A,C,B,D,F,G,H，构建二叉搜索树如下：E/\AG/\/\CBFH/D3.插入过程及哈希表状态：-H[0]=22-H[1]=41-H[2]=53-H[3]=46(冲突，探测H[4])-H[4]=30-H[5]=13(冲突，探测H[6])-H[6]=12(冲突，探测