2016年湖南师范大学数学与计算机科学学院数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 若某文件系统索引结点（inode ）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（ ）
A. 索引结点的总数 B. 间接地址索引的级数 C. 地址项的个数 D. 文件块大小 【答案】A
【解析】根据文件长度与索引结构的关系可知，只有选项A 是与单个文件长度无关的。
2． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，起泡排序 【答案】D
3． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个 【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
4． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储B. 以顺序方式存储，且数据元素有序 C. 以链接方式存储D. 以链接方式存储，且数据元素有序 【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有
序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
5． 广义表 则式子的值为（ ）。
【答案】D
head 操作就是得到广义表中第一个的原子。【解析】
操作就是得到除第一个原子外剩下元
素构成的表。也就是toil 得到的元素需要在外层再加一个（ ）。
6． 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。
A. 执行P （wait ）操作 B. 申请内存失败 C. 启动I/O设备 D. 被尚优先级进程抢占 【答案】D
【解析】D 项，被高优先级进程抢占，进程会由执行态变为就绪态。ABC 三项，程序由于缺少资源而由执行态转为阻塞态。
7． —个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms 到达。它们的计算和P1:计算60ms ，作顺序如下：
计算
计算
计算
虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。
A.240ms B.260ms C.340ms D.360ms
【答案】B 。
【解析】考查处理系统的性能计算，由于P2比PI 晚5ms 到达，PI 先占用CPU ，根据PI 和P2的执行过程，作业运行的甘特图如下所示，故答案为B 。
操
若不考
8． 在一棵度为4的树T 中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T 的叶结点个数是（ ）。
A.41 B.82 C.113 D.122 【答案】B
【解析】根据二叉树的性质3的推广公式：入公式，
即
可直接在将数据带
树T 的叶子结点的个数是82。如果考生不
能熟练掌握二叉树的性质3的推广公式，得到本题的正确答案将费时费力。因此，需要熟练掌握二叉树的性质及推广。
9． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）。
A.1条，1条 B.1条，多条 C. 多条，1条 D. 多条，多条 【答案】A
【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A 。
10．输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，push 的数目始终大于等于pop 的数目。
二、填空题
11．对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
12．=_____
【答案】5
13．建立索引文件的目的是_____。
【答案】提高查找速度
相关内容
相关标签