北京联合大学《数据结构与算法》2022-2023学年期末试卷.doc
装订线
装订线
PAGE2
第PAGE1页，共NUMPAGES3页
北京联合大学
《数据结构与算法》2022-2023学年期末试卷
院(系)_______班级_______学号_______姓名_______
题号
一
二
三
总分
得分
批阅人
一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）
1、设栈的初始状态为空，元素1、2、3、4、5依次入栈，出栈序列不可能是？（）
A.54321
B.21543
C.21345
D.15432
2、在一个具有n个节点的二叉排序树中，进行查找操作的平均时间复杂度是多少？
A.O(n)
B.O(logn)
C.O(nlogn)
D.取决于树的形态
3、在数据结构中，双向循环链表相较于单向链表，以下优势描述错误的是（）
A.可以方便地反向遍历
B.插入和删除节点的操作更简单
C.查找前一个节点的时间复杂度更低
D.空间复杂度更低
4、若要在一个已排序的数组中使用二分查找算法查找一个特定元素，以下关于时间复杂度的描述，哪一项是正确的？
A.O(n)
B.O(logn)
C.O(nlogn)
D.O(n^2)
5、在一个具有n个节点的完全二叉树中，若底层从左到右第x个节点为叶子节点，则x的取值范围是（）
A.[2^(h-1),2^h-1]
B.[2^(h-2),2^(h-1)-1]
C.[2^(h-1)-1,2^h-2]
D.[2^(h-2)-1,2^(h-1)-1]
6、已知一个哈希表的长度为11，哈希函数为H(key)=key%11，采用二次探测法处理冲突。若依次插入关键字15、38、61、84，则在查找关键字61时需要进行几次探测？（）
A.1
B.2
C.3
D.4
7、以下哪种数据结构常用于实现操作系统中的进程调度？
A.队列
B.栈
C.树
D.图
8、对于一个具有n个节点的无向连通图，其生成树的边数为（）
A.n-1
B.n
C.n+1
D.2n
9、设有一个栈，元素进栈的次序为A、B、C、D、E，下列不可能的出栈序列是（）。
A.EDCBA
B.DECBA
C.DCEAB
D.ABCDE
10、在一个容量为10的顺序存储的循环队列中，若front=4，rear=8，则此时队列中元素的个数为：
A.4
B.5
C.6
D.7
11、在一个具有n个元素的队列中，若要获取队头元素的前一个元素但不删除，以下操作不可行的是？（）
A.遍历整个队列
B.使用辅助数据结构
C.直接获取
D.以上都不可行
12、在图的存储结构中，十字链表主要用于存储有向图，以下关于十字链表的特点，描述不正确的是（）
A.既能方便地访问出边，也能方便地访问入边
B.存储空间比邻接表节省
C.对于删除边的操作比较复杂
D.不适合用于稀疏有向图
13、对于一个具有n个元素的顺序存储的循环队列，队尾指针rear指向队尾元素的下一个位置，队头指针front指向队头元素，若队列非空，则队列中元素的个数为？（）
A.(rear-front+n)%n
B.(rear-front)%n
C.rear-front
D.rear-front+1
14、在一个具有n个元素的顺序表中，要在中间位置插入一个新元素，平均移动元素的个数约为？
A.n/2
B.n
C.logn
D.1
15、在一棵平衡二叉树中，插入一个新结点后，可能需要进行的调整操作是：
A.左旋
B.右旋
C.左旋和右旋
D.不需要调整
16、对于一个具有n个元素的无序数组，使用选择排序进行排序，其交换次数最多为？
A.n-1
B.n
C.n(n-1)/2
D.n^2
17、在一个具有n个顶点和e条边的有向图中，采用邻接表存储，求顶点的入度的时间复杂度为？（）
A.O(n)
B.O(e)
C.O(n+e)
D.O(n2)
18、若一棵二叉树的层次遍历序列为ABCDEFGHI，则其可能的中序遍历序列有多少种？（）
A.1
B.n!
C.2^n
D.不确定
19、图的最短路径算法有多种，以下关于它们的说法中，错误的是？（）
A.迪杰斯特拉算法用于求解单源最短路径问题，即从一个源点到其他所有顶点的最短路径。
B.弗洛伊德算法用于求解任意两点之间的最短路径问题。
C.贝尔曼-福特算法也可以用于求解单源最短路径问题，但它的时间复杂度比迪杰斯特拉算法高。
D.图的最短路径算法只有迪杰斯特拉算法和弗洛伊德算法两种。
20、对于一个具有n个顶点和e条边的带权无向图，若采用克鲁斯卡尔（Kruskal）算法生成最小生成树，其时间复杂度为？（）
A.O(n2)
B.O(eloge)
C.O(nlogn)
D.O(e2)
二、简答题（本大题共4个小题，共40分)
1、