2018年东北大学软件学院858C语言程序设计与数据结构之数据结构考研核心题库
● 摘要
目录
2018年东北大学软件学院858C 语言程序设计与数据结构之数据结构考研核心题库（一） .... 2
2018年东北大学软件学院858C 语言程序设计与数据结构之数据结构考研核心题库（二） .. 10
2018年东北大学软件学院858C 语言程序设计与数据结构之数据结构考研核心题库（三） .. 19
2018年东北大学软件学院858C 语言程序设计与数据结构之数据结构考研核心题库（四） .. 27
2018年东北大学软件学院858C 语言程序设计与数据结构之数据结构考研核心题库（五） .. 37
第 1 页，共 44 页
一、单项选择题
1． 某系统正在执行三个进程P1、P2和P3, 各进程的计算(CPUCPUCPU)时间和
如下表所示。
时间比例
为提高系统资源利用率, 合理的进程优先级设置应（ ） A. B. C. D.
【答案】B
【解析】为了合理地设置进程优先级, 应该将进程的CPU 利用时间和
答案选B 。
2． 在系统总线的数据线上, 不可能传输的是（ ）。
A. 指令
B. 操作数
C. 握手(应答) 信号
D. 中断类型号型号
【答案】C
【解析】握手(应答) 信号属于通信联络控制信号应该在通信总线上传输, 不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
3． 将森林F 转换为对应的二叉树T , F 中叶结点的个数等于（ ）
A.T 中叶结点的个数
B.T 中度为1的结点个数
C.T 中左孩子指针为空的结点个数
D.T 中右孩子指针为空的结点个数
【答案】C
【解析】森林转化为对应的二叉树是„孩子-兄弟‟存储的, 即左孩子指针指向当前节点的孩子节
第 2 页，共 44 页 时间做综合考虑, 故
点, 右孩子指针指向当前节点的兄弟节点, 所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C
4． 用希尔排序方法对一个数据序列进行排序时, 若第1趟排序结果为9, 1, 4, 13, 7, 8, 20, 23, 15, 则该趟排序采用的增量(间隔) 可能是（ ）
A.2
B.3 C.4
D.5
【答案】B
【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组, 而它们是无序的, 所以A 错误
对于C , 增量为4, 那么9, 7, 15是一组, 而它们是无序的, 所以C 错误
对于D , 增量为5, 那么9, 8是一组, 降序, 1, 20是一组, 而它们是升序, 所以D 也错误。对于B , 分为3组:9, 13, 20; 1, 7, 23; 4, 8, 15都是升序有序, 所以B 正确
5． 某计算机存储器按字节编址, 主存地址空间大小为64MB ,
现用
32MB 的主存储器, 则存储器地址寄存器MAR 的位数至少是（ ）。
A.22位
B.23位
C.25位
D.26位
【答案】D
【解析】虽然实际的主存储器(RAM区) 只有32MB , 但不排除还有ROM 区, 考虑到存储器扩展的需要, MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。
6． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7 B.
C.15
D.16
【答案】C
【解析】Hanoi 问题总移动次数为:2M 次。
7． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N －1
C.2N
D.N －1
第 3 页，共 44 页 位的RAM 芯片组成
【答案】A
【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。
8． 已知广义表LS ＝((a，b ，c) ，(d，e ，f)) ， 用head 和tail 数取出LS 中原子e 的运算是（ ）。
A.head(tail(LS))
B.tail(head(LS))
C.head(tail(head(tail(LS)))
D.head(tail(tail(head(LS))))
【答案】C
【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下元素构成的表。tail(LS)得到((d，e ，f)) ，head(tail(LS))得到(d，e ，f)tail(head(tail(LS)))得到(e，f) ，head(tail(head(tail(LS))) 得到e 。
9． 在一棵度为4的树T 中, 若有20个度为4的结点, 10个度为3的结点, 1个度为2的结点, 10个度为1的结点, 则树T 的叶结点个数是（ ）。
A.41
B.82
C.113
D.122
【答案】B
【解析】根据二叉树的性质3的推广公式:
式, 即
。
树T 的叶子结点的个数是82。
10．对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。
A. 每次分区后，先处理较短的部分
B. 每次分区后，先处理较长的部分
C. 与算法每次分区后的处理顺序无关
D. 以上三者都不对
【答案】A
【解析】令递归函数为f ，第一次进行递归函数认为递归深度为1，以后从深度为n 的递归函数f 中再调用递归函数f ，此时深度为n+1。整个f 的最大深度为递归深度。
11．算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
第 4 页，共 44 页 可直接在将数据带入公
相关内容
相关标签