2018年江苏省培养单位苏州纳米技术与纳米仿生研究所866计算机原理之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 在支持多线程的系统中, 进程P 创建的若干个线程不能共享的是（ ）。
A. 进程P 的代码段
B. 进程P 中打开的文件
C. 进程P 的全局变量
D. 进程P 中某线程的栈指针
【答案】D
【解析】现代操作系统中, 进程是资源分配的基本单位, 线程是处理机调度的基本单位。因此, 进程是线程运行的容器, 本题中, 进程的代码段, 进程打开的文件, 进程的全局变量等都是进程的资源, 唯有进程中某线程的栈指针是属于线程的, 那么, 属于进程的资源可以共享, 属于线程的栈是独享的, 不能共享。
2． 要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n －1
B.n
C.n+1
D.2n
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n －1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
3． 对下图进行拓扑排序, 可以得到不同的拓扑序列的个数是（ ）。
图
A.4
B.3
C.2
D.1
【答案】B
【解析】拓扑排序的步骤为:
(1)在有向图中选一个没有前驱的顶点并且输出它;
(2)从图中删除该顶点和以它为尾的弧。重复上述两步, 直至全部顶点均已输出。由于没有前驱的顶点可能不唯一, 所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列, 分别为abced , abecd , aebcd 。
4． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
【答案】A
【解析】归并排序的辅助空间为O(n)，快速排序所占用的辅助空间为，堆排序所占用的辅助空间为O(1)。
5． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表
B. 双向链表
C. 单循环链表
D. 顺序表
【答案】D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
6． 单处理机系统中，可并行的是（ ）.
(1)进程与进程
(2)处理机与设备
(3)处理机与通道
(4)设备与设备
A. (1)、(2)和(3)
B. (1)、(2)和(4)
C. (1)、(3)和(4)
D. (2)、(3)和(4)
【答案】D
【解析】注意区分并发和并行. 在单处理机系统中，进程只能并发. 微观上同一时刻占用处理机
的进程只有一个，因此，进程之间不是并行的. 通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行. 显然，设备和设备之间也是可以并行的.
7． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现栈满的情况
B. 通常不会出现栈空的情况
C. 插入操作更容易实现
D. 删除操作更容易实现
【答案】A
8． 假定变量i 、f 和d 的数据类型分为int 、float 和double(int用补码表示, float 和double 分别用IEEE754单精度和双精度浮点数格式表示) , 已知
器中执行下列关系表达式, 则结果为“真”的是（ ）。
(Ⅰ)
(Ⅱ)
(Ⅲ)
(Ⅳ)
A. 仅Ⅰ和Ⅱ
B. 仅Ⅰ和Ⅲ
C. 仅Ⅱ和Ⅲ
D. 仅Ⅲ和Ⅳ
【答案】B
【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。Ⅱ中, f 的数据类型从float 转换为int 时, 小数点后面4位会丢失, 故Ⅱ的结果不为真; Ⅳ中, d+f时需要对阶, 对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故Ⅳ的结果也不为真。
Ⅰ和Ⅱ进行数据类型的转换的时候并没有改变其值。
9． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。 A.
B.
C.
D. 。若在32位机
【答案】D
【解析】二叉树结点总数n ＝n 0＋n 1＋n 2(n0，n 1，n 2分别代表度为0，度为1，度为2的结点