2018年天津职业技术师范大学信息技术工程学院811数据结构考研仿真模拟五套题
● 摘要
目录
2018年天津职业技术师范大学信息技术工程学院811数据结构考研仿真模拟五套题（一） ... 2 2018年天津职业技术师范大学信息技术工程学院811数据结构考研仿真模拟五套题（二） . 13 2018年天津职业技术师范大学信息技术工程学院811数据结构考研仿真模拟五套题（三） . 24 2018年天津职业技术师范大学信息技术工程学院811数据结构考研仿真模拟五套题（四） . 37 2018年天津职业技术师范大学信息技术工程学院811数据结构考研仿真模拟五套题（五） . 50
第 1 页，共 61 页
一、填空题
1． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
2． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点
；
，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下
处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。
【答案】
3． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
4． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有 检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
第 2 页，共 61 页
5． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
6． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
7．
【答案】5
8． 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序找，每个元素占4个字节。
【答案】23；100CH
9． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；；O(1)；满足堆的性质
10．以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。
第 3 页，共 61 页 ＝_____
【答案】
二、单项选择题
11．单处理机系统中，可并行的是（ ）.
(1)进程与进程
(2)处理机与设备
(3)处理机与通道
(4)设备与设备
A. (1)、(2)和(3)
B. (1)、(2)和(4)
C. (1)、(3)和(4)
D. (2)、(3)和(4)
【答案】D
【解析】注意区分并发和并行. 在单处理机系统中，进程只能并发. 微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的. 通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行. 显然，设备和设备之间也是可以并行的.
12．下列选项中，降低进程优先级的合理时机是（ ）.
A. 进程的时间片用完
B. 进程刚完成I/O，进入就绪队列
C. 进程长期处于就绪队列
D. 进程从就绪状态转为运行态
【答案】A
【解析】进程时间片用完可以降低其优先级，完成I/O的进程应该提升其优先级，处于就绪队列等待调度的进程一般不会改变其优先级. 进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性. 采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是独享计算机(时间片轮转可以有效地防止计算繁忙型的进程独占计算机) ，时间片用完后降低其优先级是为了改善新进程的响应时间(新进程优先级较高，老进程降低优先级可以保证新进程具有优先权) ，对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和要求确定好优先级，不会随意改变. 而对于从阻塞状态唤醒的进程，由于阻塞带来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用户响应时间.
13．有n(n＞0) 个分支结点的满二叉树的深度是（ ）。
A.n 2﹣l
第 4 页，共 61 页
相关内容
相关标签