北京联合大学《数据结构A》2021-2022学年期末试卷.doc
学校________________班级____________姓名____________考场____________准考证号
学校________________班级____________姓名____________考场____________准考证号
…………密…………封…………线…………内…………不…………要…………答…………题…………
第PAGE1页，共NUMPAGES3页
北京联合大学
《数据结构A》2021-2022学年期末试卷
题号
一
二
三
总分
得分
一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）
1、在一个具有n个元素的循环队列中，若队头指针为front，队尾指针为rear，且rearfront，则队列中的元素个数为？
A.rear-front
B.front-rear
C.(rear-front+n)%n
D.(front-rear+n)%n
2、在一个具有n个顶点和e条边的无向图中，采用邻接表存储，其时间复杂度为？（）
A.O(n+e)
B.O(n2)
C.O(e2)
D.O(ne)
3、若要对一组无序的整数进行排序，使其最终变为一个递增的有序序列，以下哪种排序算法在平均情况下性能最优？
A.冒泡排序
B.插入排序
C.选择排序
D.希尔排序
4、对于一个具有n个顶点和e条边的无向连通图，利用Prim算法构造最小生成树时，其时间复杂度为：
A.O(n^2)
B.O(elogn)
C.O(nlogn)
D.O(e^2)
5、在一个用邻接矩阵存储的图中，若要判断两个节点是否相邻，时间复杂度是多少？
A.O(1)
B.O(n)
C.O(logn)
D.O(nlogn)
6、对于一个具有n个顶点和e条边的有向完全图，其弧的条数为（）。
A.n(n-1)
B.n(n-1)/2
C.n(n+1)
D.n(n+1)/2
7、以下关于串的描述，错误的是：
A.串是一种特殊的线性表
B.串的长度是指串中字符的个数
C.空串和空格串是相同的概念
D.串的存储方式有顺序存储和链式存储
8、在一个具有n个顶点的带权无向图中，若采用普里姆（Prim）算法生成最小生成树，其时间复杂度为？（）
A.O(n2)
B.O(eloge)
C.O(nlogn)
D.O(e2)
9、对于一个具有n个元素的有序链表，进行二分查找的时间复杂度为（）
A.O(n)
B.O(logn)
C.O(nlogn)
D.不能进行二分查找
10、对于一个具有n个元素的堆，进行堆排序。以下关于堆排序的平均时间复杂度和空间复杂度的描述，哪一个是准确的？
A.平均时间复杂度为O(nlogn)，空间复杂度为O(1)
B.平均时间复杂度为O(n^2)，空间复杂度为O(n)
C.平均时间复杂度为O(logn)，空间复杂度为O(logn)
D.平均时间复杂度为O(n)，空间复杂度为O(n)
11、在数据结构中，跳表的索引层数是根据数据量动态调整的，以下关于索引层数调整的描述，错误的是（）
A.当数据量增加时，可能增加索引层数
B.索引层数越多，查找效率越高
C.调整索引层数的过程比较复杂
D.索引层数的调整不会影响数据的存储结构
12、在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的方法。以下关于它们的描述，错误的是（）
A.DFS使用栈来保存未访问的节点
B.BFS使用队列来保存未访问的节点
C.DFS可能会陷入死循环
D.BFS一定能找到最短路径
13、在一个具有n个元素的顺序表中，若要在第i个元素（1=i=n）之前插入一个新元素，需要向后移动多少个元素？（）
A.n-i
B.i
C.n-i+1
D.n-i-1
14、在一个具有n个节点的二叉排序树中，删除一个节点后，为了保持二叉排序树的性质，可能需要进行哪些操作？
A.仅调整删除节点的子树
B.从根节点开始重新调整
C.调整整个树的结构
D.以上都有可能
15、以下哪种数据结构常用于实现字符串的最长公共子序列问题？
A.二维数组
B.栈
C.队列
D.树
16、设有一个栈，元素进栈的次序为A、B、C、D、E，下列不可能的出栈序列是（）。
A.EDCBA
B.DECBA
C.DCEAB
D.ABCDE
17、以下哪种数据结构常用于实现优先级队列？
A.链表
B.队列
C.栈
D.堆
18、以下哪种数据结构常用于实现图的深度优先遍历的栈？
A.顺序栈
B.链栈
C.共享栈
D.以上均可
19、在一个长度为n的顺序表中，删除第i个元素（1=i=n）时，需要移动的元素个数为：
A.n-i
B.i-1
C.n-i+1
D.i
20、在数据结构中，链表的每个节点通