2018年福建师范大学软件学院841计算机专业基础综合之数据结构考研核心题库
● 摘要
一、单项选择题
1． 采用简单选择排序，比较次数与移动次数分别为（ ）。 A. B. C. D.
【答案】C
【解析】简单选择排序只在要交换的时候交换位置，及移动位置，共需移动n 次。而需要比较的次数为、
2． 设无向图的顶点个数为m 则该图最多有（ ）条边。
A.n-1 B. C.
D.0E.n2
【答案】B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为
3． 下列关于银行家算法的叙述中, 正确的是（ ）
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时, 系统中一定无死锁进程
C. 当系统处于不安全状态时, 系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件
【答案】B
【解析】银行家算法是避免死锁的方法。利用银行家算法, 系统处于安全状态时没有死锁进程, 故答案选B 。
4． 在下面的排序方法中，辅助空间为O(n)的是（ ）。
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
第 2 页，共 32 页 。
【答案】D
5． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为（ ）。 A.
B.n/2 C.
D.n
【答案】C
【解析】最快查找一次成功，最慢查找n
次成功。平均查找次数为
。
6． 若某单处理器多进程系统中有多个就绪态进程, 则下列关于处理机调度的叙述中, 错误的是（ ）。
A. 在进程结束时能进行处理机调度
B. 创建新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
【答案】C 。
【解析】对于A 、B 、D 显然是可以进行处理机调度的, 对于C , 当进程处于临界区时, 只要不破坏临界资源的使用规则, 是不会影响处理机调度的, 比如, 通常访问临界资源可能是慢速的外设(如打印机) , 如果在进程访问打印机时, 不能处理机调度, 那么系统的性能将是非常低的。几种不进行处理机调度的情况如下:
①在处理机中断的过程中;
②进程在操作系统内核程序临界区中;
③其他需要完全屏蔽中断的原子操作过程中。
7． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n
B.n ﹣2
C.n ﹣1
D.n ＋1
【答案】c
【解析】每个结点(除根节点外) 都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n ﹣1。
8． 设n 是描述问题规模的非负整数, 下面程序片段的时间复杂度是（ ）。
第 3 页，共 32 页 那么
A. B. C. D.
【答案】A
【解析】其中, 以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语
句, 设其执行时间为, 则有即。
时间比例 9． 某系统正在执行三个进程P1、P2和P3, 各进程的计算(CPUCPUCPU)时间和
如下表所示。
为提高系统资源利用率, 合理的进程优先级设置应（ ） A. B. C. D.
【答案】B
【解析】为了合理地设置进程优先级, 应该将进程的CPU 利用时间和时间做综合考虑, 故答案选B 。
10．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。
A.4
B.5
C.6
D.7
【答案】C
【解析】设度为0的结点数为x ，则度为3的树总结点数n ＝度为0的结点数＋度为1的结点数＋度为2的结点数＋度为3的结点数＝x ＋2＋l ＋2＝x ＋5；从每个结点所指向的结点数的和的角度来计算度为3的树总结点数n ＝2×3＋1×2＋2×1＋1＝11。两种方法所计算出来的n 相等，所以x ＝6。
二、应用题
11．设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素, 各表中元素按升序排列。要求通过5次两两合并, 将6个表最终合并成1个升序表, 并在最坏情况下比较的总次数达到最小。请回答下列问题。
(1)给出完整的合并过程, 并求出最坏情况下比较的总次数。
第 4 页，共 32 页