江西农业大学数据结构2024年期末试卷
一、单项选择题（每题2分，共20题，共40分）
1.数据结构中，与所用的计算机无关的是数据的（）
A,存储结构B.物理结构C.逻辑结构D.物理和存储结构
2.在一个长度为n的顺序表中，在第i个元素（lWiWn+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-l）x（n-l）C.nxnD.（n+l）x（n+l）
6.已知一棵二叉树的前序遍历序列为ABDCE,中序遍历序列为BDAEC,则该二叉
树的后序遍历序列为（）
A.DBEACB.DEBACC.EDCBAD.DBECA
7.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结
点有2个，则该树的叶子结点个数为（）
A.4B.5C.6D.7
.下列查找算法中，平均查找长度与元素个数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层）有个叶子结点，则该完全二叉树的
结点个数最多是（）
A.39B.52C.IllD.119
15.下列关于图的说法，正确的是（）
A,无向图的连通分量是其极大连通子图B.有向图的强连通分量是其极大强连通子
图C,图的遍历有深度优先遍历和广度优先遍历D.以上说法都正确
16.哈希表的平均查找长度与（）有关。
A.哈希函数B,装填因子C,处理冲突的方法D,以上都是
17.对n个元素进行快速排序，在最坏情况下，算法的时间复杂度是（）
A.0（n）B.0（nlog2n）C.0（n2）D.0（log2n）
1.已知某二叉树的后序遍历序列是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.快速排序是一种不稳定的排序算法。（）
.在顺序表中插入和删除元素的时间复杂度都是0（n）。（）
9.线索二叉树的优点是可以加快查找结点前驱和后继的速度。（）