江西农业大学数据结构2023年期末试卷
一、单项选择题（每题2分，共20题，共40分）
1.数据结构中，与所使用的计算机无关的是数据的（）
A.存储结构B.物理结构C.逻辑结构D.物理和存储结构
2.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后移动（）个元素。
A.n-iB.n-i+1C.n-i-1D.i
3.以下关于栈的说法，错误的是（）
A.栈是一种先进后出的线性表B.栈只能采用顺序存储结构C.栈的插入和删除操作都在栈顶进行D.栈可以用来实现表达式求值
4.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）
A.1和5B.2和4C.4和2D.5和1
5.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小为（）
A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)
6.已知一棵二叉树的前序遍历序列为ABDCE，中序遍历序列为BDAEC，则该二叉树的后序遍历序列为（）
A.DBEACB.DEBACC.EDCBAD.DBECA
7.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则该树的叶子结点个数为（）
A.4B.5C.6D.7
8.下列查找算法中，平均查找长度与元素个数n无关的是（）
A.顺序查找B.折半查找C.哈希查找D.二叉排序树查找
9.对一组数据{55,30,35,15,45,25,95}进行冒泡排序，第一趟排序后的结果为（）
A.{30,35,15,45,25,55,95}B.{30,55,15,35,25,45,95}C.{30,15,35,25,45,55,95}D.{15,25,30,35,45,55,95}
10.以下排序算法中，稳定的排序算法是（）
A.快速排序B.希尔排序C.归并排序D.堆排序
11.线性表采用链式存储时，其地址（）
A.必须是连续的B.一定是不连续的C.部分地址必须是连续的D.连续与否均可以
12.栈和队列的共同点是（）
A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点
13.对于一个有n个顶点和e条边的有向图，若采用邻接表表示，则顶点表的大小为（）
A.nB.n+1C.n-1D.n+e
14.一棵完全二叉树的第6层（根为第1层）有8个叶子结点，则该完全二叉树的结点个数最多是（）
A.39B.52C.111D.119
15.下列关于图的说法，正确的是（）
A.无向图的连通分量是其极大连通子图B.有向图的强连通分量是其极大强连通子图C.图的遍历有深度优先遍历和广度优先遍历D.以上说法都正确
16.哈希表的平均查找长度与（）有关。
A.哈希函数B.装填因子C.处理冲突的方法D.以上都是
17.对n个元素进行快速排序，在最坏情况下，算法的时间复杂度是（）
A.O(n)B.O(nlog?n)C.O(n2)D.O(log?n)
18.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（）
A.acbedB.decabC.deabcD.cedba
19.若要在链表中删除一个指定结点，需要找到该结点的（）
A.直接前驱结点B.直接后继结点C.头结点D.尾结点
20.以下哪种数据结构适合实现优先队列（）
A.栈B.队列C.堆D.链表
二、判断题（每题2分，共10题，共20分。正确的打“√”，错误的打“×”）
1.数据的逻辑结构与数据元素本身的内容和形式无关。（）
2.顺序存储方式只能用于存储线性结构。（）
3.栈和队列都是特殊的线性表。（）
4.二叉树中每个结点的度最多为2，所以二叉树是一种特殊的树。（）
5.图的深度优先遍历和广度优先遍历都可以用来判断图是否连通。（）
6.哈希表是一种基于关键码值进行快速查找的数据结构。（）
7.快速排序是一种不稳定的排序算法。（）
8.在顺序表中插入和删除元素的时间复杂度都是O(n)。（）
9.线索二叉树的优点是可以加快查找结点前驱和后继的