2018年桂林理工大学信息科学与工程学院878数据结构及程序设计之数据结构考研核心题库
● 摘要
一、单项选择题
1． 假设变址寄存器R 的内容为1000H , 指令中的形式地址为2000H ; 地址1000H 中的内容为2000H , 地址2000H 中的内容为3000H , 地址3000H 中的内容为4000H , 则变址寻方式下访问到的操作数是（ ）
A.1000H B.2000H C.3000H D.4000H 【答案】D
【解析】
根据变址寻址的操作数的实际地址,
由题可知
, 变址寄存器的内容与形式地址的内容相加之后得到
, 根据实际地址访问内存, 获取操作数
4000H 。
2． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。
A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 【答案】D
3． 系统为某进程分配了4个页框, 该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7, 依据LRU 算法, 应淘汰页的页号是（ ）。
A.2 B.3 C.4 D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框, 题中访问过程中页框的变化如下:
访问页号为7的页时, 内存中存在的页的页号是:3、8、4和5, 根据LRU 定义应淘汰的是3。
4． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 【答案】A
【解析】归并排序的辅助空间为O(n)，快速排序所占用的辅助空间为
，堆排序所占
用的辅助空间为O(1)。
5． 冯•诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）.
A. 指令操作码的译码结果 B. 指令和数据的寻址方式 C. 指令周期的不同阶段 D. 指令和数据所在的存储单元 【答案】C
【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段(分析取数阶段、执行阶段) 取出的是数据. 所以，CPU 区分指令和数据的依据是指令周期的不同阶段.
6． 下列关于中断
A. 中断
方式和DMA 方式比较的叙述中, 错误的是（ ）
方式请求的是方式请求的是CPU 处理时间, DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后, 中断响应发生在一条指令执行结束后, DMA 响应发生在一个总线事务完成后
C. 中断送由硬件完成
D. 中断设备
【答案】D
【解析】中断处理方式:在与
设备输入每个数据的过程中, 由于无需CPU 干预, 因而可使CPU
设备并行工作。仅当输完一个数据时, 才需CPU 花费极短的时间去做些中断处理。因此中断
方式适用于所有外部设备, 方式适用于所有外部设备, DMA 方式仅适用于快速外部方式下数据传送通过软件完成, 方式下数据传送通过软件完成, DMA 方式下数据传
申请使用的是CPU 处理时间, 发生的时间是在一条指令执行结束之后, 数据是在软件的控制下完
成传送。而DMA 方式与之不同。DMA 方式:数据传输的基本单位是数据块, 即在CPU 与设备
之间, 每次传送至少一个数据块, DMA 方式每次申请的是总线的使用权, 所传送的数据是从设备直接送入内存的或者相反; 仅在传送一个或多个数据块的开始和结束时, 才需CPU 干预, 整块数据的传送是在控制器的控制下完成的。答案D 的说法不正确。
7． 若元素a , b , c , d , e , f 依次进栈, 允许进栈、退栈操作交替进行, 但不允许连续三次进行退栈操作, 则不可能得到的出栈序列是（ ）。
A.d , c , e , b , f , a B.c , b , d , a , e , f C.b , c , a , e , f , d D.a , f , e , d , c , b
【答案】D
【解析】4个选项所给序列的进、出栈操作序列分别为: 选项A. 选项B. 选项C. 选项D.
按照题目要求, 不允许连续三次进行退栈操作, 所以选项D 所给序列为不可能得到的出栈顺序。
8． 在一棵度为4的树T 中, 若有20个度为4的结点, 10个度为3的结点, 1个度为2的结点, 10个度为1的结点, 则树T 的叶结点个数是（ ）。
A.41 B.82 C.113 D.122
【答案】B
【解析】根据二叉树的性质3的推广公式:式, 即
。
树T 的叶子结点的个数是82。
9． 有n(n＞0) 个分支结点的满二叉树的深度是（ ）。
A.n 2﹣l
B.log 2(n＋1) ＋1 C.log 2(n＋1) D.log 2(n—1) 【答案】C
【解析】满二叉树的结点总数＝分支的结点总数＋非分支的结点总数。由于此树为满二叉树，
可直接在将数据带入公