北京联合大学《数据结构》2023-2024学年期末试卷.doc
学校________________班级____________姓名____________考场____________准考证号
学校________________班级____________姓名____________考场____________准考证号
…………密…………封…………线…………内…………不…………要…………答…………题…………
第PAGE1页，共NUMPAGES3页
北京联合大学
《数据结构》2023-2024学年期末试卷
题号
一
二
三
总分
得分
批阅人
一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）
1、以下哪种数据结构常用于实现文件系统的目录结构？
A.二叉树
B.多叉树
C.链表
D.栈
2、对于一个具有n个节点的二叉树，若每个节点都有左子树和右子树，则其叶子节点的个数至少为？
A.n/2
B.(n+1)/2
C.n-1
D.logn
3、对于一个具有n个元素的顺序存储的循环队列，队尾指针rear指向队尾元素的下一个位置，队头指针front指向队头元素，若队列非空，则队列中元素的个数为？（）
A.(rear-front+n)%n
B.(rear-front)%n
C.rear-front
D.rear-front+1
4、在数据结构中，对于一个具有n个元素的有序数组，使用二分查找算法查找一个特定元素，其平均时间复杂度为（）
A.O(n)
B.O(logn)
C.O(nlogn)
D.O(n^2)
5、对于一个具有n个节点的完全二叉树，若按照层次遍历的顺序将节点编号为1到n，已知编号为i的节点有左孩子，则其左孩子的编号为？
A.2i
B.2i+1
C.i*2
D.i/2
6、对于一个循环队列，若队列的最大容量为m，当前front指针为5，rear指针为2，则队列中的元素个数为（）
A.7
B.3
C.m-3
D.m-7
7、对于一个具有n个元素的有序数组，若采用折半插入排序算法进行排序，其时间复杂度为？（）
A.O(n)
B.O(nlogn)
C.O(n2)
D.O(logn)
8、对于一个用数组实现的小根堆，进行删除堆顶元素操作后，需要重新调整堆以保持堆的性质。以下关于删除操作的时间复杂度的描述，哪一个是正确的？
A.O(1)
B.O(logn)
C.O(n)
D.O(nlogn)
9、在一个有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比较的次数是：
A.1
B.2
C.3
D.4
10、在一个带头结点的循环链表中，若要判断链表是否为空，应检查？（）
A.头结点的指针是否为空
B.头结点的下一个结点的指针是否指向头结点
C.尾结点的指针是否为空
D.尾结点的下一个结点的指针是否指向头结点
11、对于一个采用链表存储的栈，若要获取栈的大小（元素数量），以下关于操作的时间复杂度的描述，哪一个是准确的？
A.O(1)
B.O(logn)
C.O(n)
D.O(nlogn)
12、在一棵二叉搜索树中，删除一个有两个子节点的节点时，通常采用的方法是：
A.用左子树的最大值替代该节点
B.用右子树的最小值替代该节点
C.随机选择左子树或右子树的节点替代
D.不进行替代，直接删除
13、若一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则其先序遍历序列为？（）
A.CEDBA
B.CEABD
C.ABCDE
D.EDCAB
14、对于一个具有n个元素的双向循环链表，若要删除第i个节点（1=i=n），平均需要修改多少个指针？（）
A.2
B.3
C.4
D.5
15、以下哪种排序算法在最坏情况下的时间复杂度最低？
A.冒泡排序
B.插入排序
C.选择排序
D.归并排序
16、对于一个具有n个元素的有序数组，使用二分查找算法查找一个特定元素。以下关于二分查找的时间复杂度的描述，哪一个是恰当的？
A.O(1)
B.O(logn)
C.O(n)
D.O(nlogn)
17、已知一个带权有向图G=(V,E)，顶点集合V={1,2,3,4,5}，边集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求从顶点1到顶点5的最短路径，经过的中间顶点依次为？（）
A.2,4
B.3,4
C.2,3
D.3,5
18、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为（）。
A.n
B.n^2
C.n(n-1)
D.n(n+1)
19、对于一个具有n个元素的无序链表，若要对其进行排序，以下哪种排序算法较为合适？（）
A.冒泡排序
B.快