2018年云南大学信息学院831数据结构与操作系统之数据结构考研基础五套测试题
● 摘要
目录
2018年云南大学信息学院831数据结构与操作系统之数据结构考研基础五套测试题（一） ... 2 2018年云南大学信息学院831数据结构与操作系统之数据结构考研基础五套测试题（二） . 10 2018年云南大学信息学院831数据结构与操作系统之数据结构考研基础五套测试题（三） . 19 2018年云南大学信息学院831数据结构与操作系统之数据结构考研基础五套测试题（四） . 27 2018年云南大学信息学院831数据结构与操作系统之数据结构考研基础五套测试题（五） . 35
一、单项选择题
1． 处理外部中断时, 应该由操作系统保存的是（ ）。
A. 程序计数器(PC)的内容
B. 通用寄存器的内容
C. 快表(TLB)的内容
D.Cache 中的内容
【答案】B
【解析】外部中断处理过程首先要保护现场, 使得中断处理完后能够恢复程序的状态继续执行。保护现场有两个含义:
①由中断隐指令保存程序的断点(程序计数器) ;
②由中断服务程序保存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
2． —组记录的关键码为(46，79，56，38，40，84) ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A.(38，40，46，56，79，84)
B.(40，38，46，79，56，84)
C.(40，38，46，56，79，84)
D.(40，38，46，84，56，79)
【答案】C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较:46比84小，不交换；
第二次比较:40比46小，交换，此时为(40，79，56，38，46，84) ;
第三次比较:46比79小，交换，此时为(40，46，56，38，79，84) ;
第四次比较:38比46小，交换，此时为(40，38，56，46，79，84) ;
第五次比较:56比46大，交换，此时为(40，38，46，56，79，84) ;
一次划分结束。
3． 若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则下列选项中, 与单个文件长度无关的因素是（ ）
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
【答案】A
【解析】根据文件长度与索引结构的关系可知, 只有选项A 是与单个文件长度无关的。
4． 用直接插入排序方法对下面4个序列进行排序(由小到大) ，元素比较次数最少的是（ ）。
A.94，32，40，90，80，46，21，69
B.32，40，21，46，69，94，90，80
C.21，32，46，40，80，69，90，94
D.90，69，80，46，21，32，94，40
【答案】C
5． 主机甲和主机乙间已建立一个TCP 连接，主机甲向主机乙发送了两个连续的TCP 段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 主机乙正确接收到两个段后，发送给主机甲的确认序列号是（ ）。
A.500
B.700
C.800
D.1000
【答案】D
【解析】TCP 使用滑动窗口流控协议，窗口大小的单位是字节，本题中分别包含300字节和500字节的有效载荷，第一个段的序列号为200, 那么确认序列号为200＋300＋500＝1000。
6． 某计算机存储器按字节编址, 主存地址空间大小为64MB ,
现用位的RAM 芯片组成32MB 的主存储器, 则存储器地址寄存器MAR 的位数至少是（ ）。
A.22位
B.23位
C.25位
D.26位
【答案】D
【解析】虽然实际的主存储器(RAM区) 只有32MB , 但不排除还有ROM 区, 考虑到存储器扩展的需要, MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。
7． 下列选项中, 用于设备和控制器(
A.PCI
B.USB
C.AGP D. 接口) 之间互连的接口标准是（ ）
【答案】B
【解析】设备和设备控制器之间的接口是USB 接口, 其余选项不符合, 故答案为B 。
8． 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 元素a , b , c , d , e 依次入此队列后再进行出队操作, 则不可能得到的出队序列是（ ）。
A.b , a , c , d , e
B.d , b , a , c , e
C.d , b , c , a , e
D.e , c , b , a , d
【答案】C
【解析】根据题意, 队列两端都可以输入数据元素, 但是只能在一端输出数据元素, 这种队列为
输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队, 从而得出不可能的情况。
假设L 代表从左端入队, R 代表从右端入队, 出队都是从左端L 出。四个选项所给序列的进队操作序列分别为:
选项A.aL(或aR) , bL , cR , dR , eR
选项B.aL(或aR) , bL , cR , dL , eR
选项C. 不可能出现选项
D.aL(或aR) , bL , cL , dR , eL
9． 若一个栈以向量 存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
A.top :＝top ＋l ；V[top]:＝x
B.V[top]:＝x ；top :＝top ＋l
C.top :＝top ﹣l ；V[top]:＝x
D.V[top]:＝x ；top :＝top ﹣l
【答案】C
【解析】题中初始栈顶指针top 为n ＋1，而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
10．将森林F 转换为对应的二叉树T , F 中叶结点的个数等于（ ）
A.T 中叶结点的个数
B.T 中度为1的结点个数
C.T 中左孩子指针为空的结点个数
D.T 中右孩子指针为空的结点个数
【答案】C
【解析】森林转化为对应的二叉树是„孩子-兄弟‟存储的, 即左孩子指针指向当前节点的孩子节点, 右孩子指针指向当前节点的兄弟节点, 所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C