2018年东南大学学习科学中心935计算机专业基础之数据结构考研基础五套测试题
● 摘要
目录
2018年东南大学学习科学中心935计算机专业基础之数据结构考研基础五套测试题（一） ... 2 2018年东南大学学习科学中心935计算机专业基础之数据结构考研基础五套测试题（二） . 16 2018年东南大学学习科学中心935计算机专业基础之数据结构考研基础五套测试题（三） . 28 2018年东南大学学习科学中心935计算机专业基础之数据结构考研基础五套测试题（四） . 37 2018年东南大学学习科学中心935计算机专业基础之数据结构考研基础五套测试题（五） . 48
一、单项选择题
1． 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 元素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
2． 分区分配内存管理方式的主要保护措施是（ ）.
A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护
【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护. 通常的界地址保护方法采用软硬件结合的方法. 考生要注意本题与虚拟存储方法的区别.
3． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。 A.
B.O(1)
C.O(n) D.
【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为O(1)。
4． 对如下所示的有向图进行拓扑排序, 得到的拓扑序列可能是（ ）
A.3, 1, 2, 4, 5, 6
B.3, 1, 2, 4, 6, 5
C.3, 1, 4, 2, 5, 6
D.3, 1, 4, 2, 6, 5
图
【答案】D
【解析】拓扑排序方法如下:
(1)从有向图中选择一个没有前驱(即入度为0) 的顶点并且输出它;
(2)从图中删去该顶点, 并且删去从该顶点发出的全部有向边;
(3)重复上述两步, 直到剩余的网中不再存在没有前趋的顶点为止。
对于此有向图进行拓扑排序所有序列为:3, 1, 4, 6, 2, 5和3, 1, 4, 2, 6, 5。所以选D
5． 对同一待排序列分别进行折半插入排序和直接插入排序, 两者之间可能的不同之处是 （ ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
【答案】D 。
【解析】折半插入排序所需附加存储空间和直接插入排序相同, 从时间上比较, 折半插入排序仅减少了关键字间的比较次数, 而记录的移动次数不变。折半插入排序的时间复杂度仍为, 所以两者之间的不同只可能是元素之间的比较次数。
6． 假定变量i 、f 和d 的数据类型分为int 、float 和double(int用补码表示, float 和double 分别用IEEE754单精度和双精度浮点数格式表示) , 已知
器中执行下列关系表达式, 则结果为“真”的是（ ）。
(Ⅰ)
(Ⅱ)
。若在32位机
(Ⅲ)
(Ⅳ)
A. 仅Ⅰ和Ⅱ
B. 仅Ⅰ和Ⅲ
C. 仅Ⅱ和Ⅲ
D. 仅Ⅲ和Ⅳ
【答案】B
【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。Ⅱ中, f 的数据类型从float 转换为int 时, 小数点后面4位会丢失, 故Ⅱ的结果不为真; Ⅳ中, d+f时需要对阶, 对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故Ⅳ的结果也不为真。
Ⅰ和Ⅱ进行数据类型的转换的时候并没有改变其值。
7． 在支持多线程的系统中, 进程P 创建的若干个线程不能共享的是（ ）。
A. 进程P 的代码段
B. 进程P 中打开的文件
C. 进程P 的全局变量
D. 进程P 中某线程的栈指针
【答案】D
【解析】现代操作系统中, 进程是资源分配的基本单位, 线程是处理机调度的基本单位。因此, 进程是线程运行的容器, 本题中, 进程的代码段, 进程打开的文件, 进程的全局变量等都是进程的资源, 唯有进程中某线程的栈指针是属于线程的, 那么, 属于进程的资源可以共享, 属于线程的栈是独享的, 不能共享。
8． 假设某计算机按字编址, Cache 有4个行, Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空, 采用2路组相联映射方式和LRU 替换算法, 当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数是（ ）。
A.1
B.2
C.3
D.4
【答案】C 。
【解析】Cache 有4个行, 2路组相联, 即Cache 被分成2组, 每组2行。主存地址为0〜1、4〜5、8〜9可映射到第0组Cache 中, 主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空, 采用LRU 替换算法, 当访问主存的10个地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数共有3次, 分别发生在第7、8和10步时。