2020 年广东暨南大学计算机基础综合考研真题
招生专业与代码:计算机系统结构 081201、计算机软件与理论 081202、计算机应用技术
081203、电子信息(专业学位) 085400
考试科目名称及代码:计算机基础综合 848
考生注意:所有答案必须写在答题纸(卷)上,写在本试题上一律不给分。
第一部分 数据结构(75 分)
一、 单项选择题(每题 2 分,共 20 分)
1. 含有 m 个结点的二叉树链式存储结构中空指针的个数为 (
)。
A.2m
B.m-1
C.m+1
D.m
2. 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是(
)。
A. 快速排序
B. 插入排序
C. 选择排序
D. 希尔排序
3. 一个栈的进栈序列是 a b c d e,则栈的输出序列不可能的是(
)。
A.a b c d e
B.e d c b a
C.d e c b a
D.d c e a b
4. 需要的辅助空间最多的排序算法为(
)。
A. 归并排序
C. 基数排序
B. 快速排序
D. 堆排序
5. 哈希表的平均查找长度说法错误的是 (
)。
A. 与处理冲突方法有关而与表的长度无关
B. 与选用的哈希函数有关
C. 与哈希表的饱和程度有关
D. 与表中填入的记录数有关
6. 有 n 个顶点 、e 条边且使用了邻接表存储的有向图进行深度优先遍历,其算法的时间复
杂度是(
)。
A.
O(n+e)
B.
O(n2)
C.
O(n+2e)
D.
O(n*e)
7. 已知一个长度为 11 的顺序表,其元素按关键字有序排列,若采用折半查找查找一个其中
不存存在的元素,则关键字的比较次数最多是(
)。
A.3
B.4
C.5
D.6
8. 一棵完全二叉树上有 3001 个结点,其中叶子结点的个数是(
)。
A. 1500
B.1501
C. 1000
D.1001
9. 若一棵二叉树度为 2 的结点有 18 个,度为 1 的结点有 10 个,则度为 0 的结点个数是
(
)。
A. 46
B. 28
C. 19
D. 17
10. m 阶 B-树是一棵(
)。
A .m 叉排序树
B. m-1 叉平衡排序树
C. m 叉平衡排序树
D. m+1 叉平衡排序
树
二、 填空题(每空 2 分,共 14 分)
1. 已知一棵二叉树的中序遍历序列为GDHBAECIF,后序遍历序列为GHDBEIFCA,那么先序遍
历序序列为
。
2. 若某记录的关键字序列是(491,77,572,16,996,101,863,258,689,325),以
第一
考试科目:计算机基础综合
个关键字为枢轴,写出采用快速排序算法第一趟排序的结果
共 4 页,第 1 页
。
3. 将对称矩阵 A[8][8]的下三角部分逐行存储到起始地址为 2000 的内存单元中,已知每个
元 素 占 4 个 单 元 , 假 设 第 一 个 元 素 是 A[0][0] , 则 A[4][6] 的 地 址
是
。
4. 在顺序表 中插入一个元素, 需要平均移动表中 一半元素,具体 移动元素的个数与
有关。
5.在哈希查找方法中,要解决两方面的问题,它们是
和
6. 循环队列中,Q.rear == Q.front表示循环队列空,表示循环队列满的条件是
。
。
三、 简答题(共 3 小题,每题 7 分,共 21 分)
1. 将下面的森林转换为二叉树(3 分),并给出该二叉树的中序线索链表(4 分)。
G
C
F
A
B
D
E
H
2. 设 Huffman 编码的长度不超过 4,若已对两个字符编码为 01 和 11,则最多还可以对多少
个字符编码,为什么?(7 分)
3. 假设图的顶点是 A、B、C、D、E,请根据下面的邻接矩阵画出相应的有向图(3 分),然
后画出图的邻接表和逆邻接表(4 分)。
0
0
1
1
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
四、 编写算法(共 2 小题,每题 10 分,共 20 分)
1. 试编写一个算法完成下面的功能:对于输入的任意一个非负十进制整数,输出与其等值
的八进制数。(10 分)
2. 试编写一个算法,在有向图 G 中,判定从顶点 Vi 到顶点 Vj 是否有通路。(10 分)
五、 判断题(每小题 1 分,共 10 分,正确的打√,错误的打×)
第二部分 操作系统(75 分)
1. 系统调用中的被调用程序运行在系统态。
2. 银行家算法采用了死锁预防的方法。
3. 文件系统采用树形目录结构可以节省内存空间。
4. 虚存管理允许用户程序大于主存容量,而且还可以提高系统的吞吐量。
5. SPOOLing 系统实现了设备的独立性。
考试科目:计算机基础综合
6. 分时系统的时间片越小,用户的满意度就越高。
共 4 页,第 2 页
7. 管程每次只允许一个进程进入。
8. 操作系统既可看作虚拟机,也可看作资源管理器。
9. 在作业调度时,采用最高响应比优先的作业调度算法可以得到最短的作业平均周转时间。
10. 并行程序设计中,使用信号量比使用管程更能保证程序的正确性。
六、 填空题 (每小题 1 分,共 10 分)
1. 对于速率为 9.6KB/s 的数据通信而言,如果设置一个具有 8 位的缓冲寄存器,则 CPU 中
断时间和响应时间分别大约为 (1) 、 (2) 。
2. 如果计算机连接了三个同类型的激光打印机及五个同类型的喷墨打印机,需要安装的驱
动程序数目是 (3) 。
3. 在具有 n 个进程的系统中,允许 m 个进程(n≥m≥1)同时进入它们的临界区,其信号量 S
的值的变化范围是 (4) ,处于等待状态的进程数最多有 (5) 个。
4. 动态分区的 (6) 算法可以使内存中的空闲分区分布得更均匀。
5. UNIX 的目录项由文件名和 (7) 构成。
6. 若干事件在同一时间间隔内发生称为 (8)
。
7. 虚拟存储器具有 (9) 、 (10)
和虚拟性三大特征。
七、 单选题(每小题 1 分,共 10 分)
1. 请求调页系统中,如下算法中,(
) 淘汰自上次访问以来经历时间最长的页面。
A. FIFO
B. OPT
C. NRU
D. LRU
2. 下列进程调度算法中,(
) 可能会出现进程长期得不到调度的情况。
A. 静态优先权法
B. 抢占式调度中采用动态优先权法
C. 分时处理中的时间片轮转调度算法 D. 非抢占式调度中采用 FIFO 算法
3. 分时系统中,CPU 进程切换需要 3ms,为使得 100 个用户均能在 1 秒内得到响应,可以选
择的时间片是(
)。
A. 2ms
B. 50 ms
C. 10ms
D. 7 ms
4. 磁盘的 I/O 控制主要采取(
) 方式。
A. 程序 I/O
B. 中断
C. DMA
D. SPOOLing
5. 系统产生死锁是指(
) 。
A. 系统发生重大故障
B. 若干进程同时处于阻塞状态
C. 请求的资源数大于系统提供的资源数
D. 若干进程等待被其他进程所占用而又不可能被释放的资源
6. 通道又称 I/O 处理机,它用于实现(
) 之间的信息传输。
A. CPU 与外存
B. CPU 与外设
C. 内存与外存
D. 内存与外设
7. 下面叙述正确的是(
) 。
A. 程序段是进程存在的唯一标志
B. 系统通过 PCB 来控制和管理进程,用户可以从 PCB 中读出与本身运行状态相关的信
息
C. 当进程有执行状态变为就绪状态时,CPU 现场信息必须被保存在 PCB 中
D. 当进程申请 CPU 得不到满足时,它将处于阻塞状态
8. 在没有快表的情况下,分页系统要访问(
)次内存。
A. 1
B. 2
C .3
D. 4
9. 计算机操作系统中,若 WAIT、SIGNAL 操作的信号量 S 初值为 3,当前值为-4,则表示当
考试科目:计算机基础综合
前有(
) 个等待信号量 S 的进程。
共 4 页,第 3 页
A. 1
B. 2
C. 3
D. 4
10. 有 10 个进程共享 5 个打印机,若信号量 S 的当前值是-2,则当前有(
)个进程提出了
打印请求?
A. 10
B. 7
C. 5
D. 2
八、 简答题(每小题 5 分,共 25 分)
1. 什么是文件目录、目录文件,各起什么作用?
2. 多级树形目录的文件系统,怎样才能提高查找文件的速度?
3. 多线程系统与传统多进程系统相比有哪些优点?
4. 分页存储管理和分段存储管理的主要区别有哪些?
5. 用伪代码或文字描述 fork()系统调用是如何创建进程的。
九、 应用题(每小题 10 分,共 20 分)
1. 某类 Unix 系统采用成组链接法来管理磁盘的空闲空间,目前磁盘的状态图如下(10 分):
(1)该磁盘中目前还有多少个空闲盘块?(4 分)
(2)给出该系统的磁盘块分配及回收算法(流程图或描述)。(6 分)
2. 分析下面给出的表达式的并行性,并用信号量机制实现该表达式的并行计算。(10 分)
(3 * a * b
+
4)/
( c + d )( e – f )