山东省专升本《数据结构》试卷2
山东省专升本《数据结构》试卷2
一、单项选择题：（每小题2分，共10分）
对于下列各题，在备选答案中选出一个正确的，并将其编号填在“”位置上。
1. 折半查法要求查表中各元素的键值必须是。
贵州交通职业技术学院
四川自考登录系统A. 递增或递减
B. 递增
C. 递减
D. 无序
中公教师编制培训班价格表
2. 若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个
元素，则采用存储方式最节省运算时间。
英语四级查询准考证
A. 单链表
B. 双链表
C. 仅有头指针的单循环链表
D. 仅有尾指针的单循环链表
3. 有64个结点的完全二叉树的深度为（假设根结点的层次为1）。
A. 8
B. 7
C. 6
D. 5
招聘工作4. 对于键值序列（2，33，21，18，65，38，7，49，24，86），用筛选法
建堆，必须从键值为的结点开始。
A. 86
B. 2
C. 65
D. 38
5. 设图G 用邻接表存储，则求每个顶点入度的算法时间复杂度为。
A. O(n)
B. O(n+e)
C. O(n*n)
D. O(n*e)
二、判断题：（每小题2分，共10分）
判断下列各题是否正确，若正确，在题后的括号内填“T”，否则填“F”。
1. 在队满情况下不能作入队处理，否则，将产生“上溢”。（）造价师报名2022时间
2. 基于插入思想的排序算法都是稳定的。（）
3. 一个有向图的邻接表和逆邻接表中的结点个数不一定相等。（）
4. 若一棵二叉树的任一非叶子结点度为2，则该二叉树为满二叉树。（）
5. 广义表是线性表的推广，因此也可以采用顺序方式进行存储。（）
三、填空题：（每小题2分，共10分）
1.在单链表中，删除指针P 所指结点的后继结点的语句是：
。
2.有向图G 用邻接矩阵，1..n] 存储表示，其第i 行的所有元素
之和等于顶点i 的。
3.基数排序算法的时间复杂度为。
4.平衡二叉树中每个结点的平衡因子定义为
。
5.利用直接插入排序算法对有n 个元素的数据表进行排序，在最坏情况
下，元素的移动次数为。
四、解答下列各题：（每小题10分，共40分）
1. 写出采用顺序方式存储的栈的类型描述及相应的入栈、出栈操作的示意
图。
2. 已知数据表为（60，20，31，5，44，55，61，30，80，150，4，29），
写出采用希尔排序算法进行排序的详细过程和结果（假设增量序列dlta
[] ={6,3,1}）。
3. 已知图G 的邻接表存储结构示意图如下所示，画出它的逻辑关系示意
图，以及按深度优先搜索和广度优先搜索进行遍历所得到的顶点序列。
4. 设散列函数为H(K) = K mod 5，散列表的地址空间为0..6，初始时散列表为空，用线性探测法解决冲突，请写出依次插入23，14，9，6，30，12，18时散列地址的计算过程及结果，以及最后得到的散列表。
五、算法设计题：（前两题必做，每题15分，共30分；第三题为附加题，选做，10分）
1. 设计算法将一个带头结点的单循环链表A 分解为两个具有相同结构的
链表B、C，其中：B 表中的结点为 A 表中元素的顺序号为奇数的结
点，而 C 表中的结点为A 表中元素的顺序号为偶数的结点。（要求利
用原表结点。）
2. 已知S 为顺序栈。写出S 的存储结构类型描述。试编写算法实现将元
素x 插入栈S 的入栈操作Push(S,x) 和删除栈顶元素的出栈操作Po
p(S)。
3. 已知一棵完全二叉树存于顺序表sa 中，sa.elem[www./doc/8b4039076.html,st] 包含各结点
值。试编写算法根据此顺序存储结构建立该二叉树的二叉链表T