1、20212021 年广东暨南大学计算机基础综合考研真题年广东暨南大学计算机基础综合考研真题 招生专业与代码：计算机系统结构 081201、计算机软件与理论 081202、计算机应用技术 081203、电子信息(专业学位) 085400 考试科目名称及代码：计算机基础综合 848 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 第一部分第一部分 数据结构（数据结构（7 75 5 分）分） 一一、 单项单项选择题选择题( (每题每题 2 2 分，共分，共 2020 分分) ) 1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采 用（ ）存储方式最
2、节省运算时间。 A.单链表 B.仅有头指针的单向循环链表 C.双链表 D.仅有尾指针的单向循环链表 2. 一个栈的输入序列为1， 2， 3.， n， 若输出序列的第一个元素是n， 那么输出第i （1=i=n） 个元素是（ ） 。 A. n-i B. i C. n-i+1 D. 不确定 3. 若一颗二叉树具有 15 个度为 2 的结点，10 个度为 1 的结点，则度为 0 的结点个数是 （ ） 。 A. 16 B. 25 C. 40 D. 不确定 4. 根据使用频率，为 5 个字符设计的哈夫曼编码不可能是（ ） 。 A. 000，001，010，011，1 B. 000，001，01，10，11
3、 C. 00，100，101，110，111 D. 0000，0001，001，01，1 5. 设 a，b 为一棵二叉树上的两个结点，在中序遍历时，a 在 b 前面的条件是（ ） 。 A.a 在 b 的右方 B. a 在 b 的左方 C. a 是 b 的祖先 D. a 是 b 的子 孙 6. 对一棵二叉排序树按（ ）遍历，可得到结点值从小到大的排序序列。 A. 先序 B. 中序 C. 后序 D. 层次 7. 已知一个有序表为(5，13，19，21，37，56，64，75，80，88，92)，则折半查找 64 需 要比较（ ）次。 A. 1 B. 2 C. 3 D. 4 8. 在一个图中，所有顶
4、点的度数之和等于所有边数的（ ）倍。 A. 1/2 B. 1 C. 2 D. 3 9. 一个序列中有 100000 个元素，若只想得到其中前 10 个最大元素，则最好采用（ ）方 法。 A. 快速排序 B. 堆排序 C. 插入排序 D. 归并排序 10. 下列四个序列中，哪一个是堆（ ） 。 A. 70，60，40，10，30，25，20，15 B. 70，60，30，15，25，40，20，10 C. 70，40，60，10，25，30，20，15 D. 70，40，60，30，15，25，20，10 二二判断判断题题( (每每题题 1 1 分，共分，共 1010 分分，正确的打正确的打，错
5、误的打，错误的打) ) 1. 数据结构研究的是数据的物理结构、逻辑结构以及它们之间的相互关系。 2. 线性表的顺序存储结构适用于频繁插入或删除数据元素的情况。 3. 一颗满二叉树同时又是一颗平衡树。 4. 一棵 m 阶 B-树中每个结点最多有 m 棵子树，非终端结点最少有 2 棵子树。 5. 带权无向图的最小生成树是唯一的。 6. 在各种查找方法中，平均查找长度与结点个数无关的查找方法是哈希查找。 7. 拓扑排序是按AOE网中每个结点事件的最早发生事件对结点进行排序。 8. 存在这样的二叉树，对它采用任何次序进行遍历，结果相同。 9. 对于n个记录的集合进行冒泡排序，在最坏情况下的时间复杂度是
6、O(n 2) 。 10. 若网中有几条关键路径， 提高一条关键路径上的活动的速度， 不能导致整个工程缩短工 期。 三三简答题简答题（共共 3 3 小题，每题小题，每题 8 8 分，共分，共 2424 分分） 1. 请按照关键字 24，13，20，32，29，53 的次序构造一棵二叉平衡树，并给出过程。 （8 分） 2. 由 n 个权值构成的哈夫曼树共有多少个结点？（4 分）为什么？（4 分） 3. 一个有六个顶点V0,V1,V2,V3,V4,V5的网络的邻接矩阵如图 1 所示，求出从顶点 V0到 其他各顶点之间的最短路径，并写出计算过程。 （8 分） 四四. . 编写算编写算法法（共共 2 2
7、 小题，第小题，第 1 1 小题小题 1010 分，第分，第 2 2 小题小题 1111 分，共分，共 2121 分分） 1. 设树的存储结构为孩子兄弟链表，试编写算法，输出树中所有从根到叶子的路径。 （10 分） 2. 设一个带头结点的单链表 L，数据元素为整数，其中大部分为正数，少数为负数，编写 函数，实现将负数结点移到链表尾部，并返回调整后链表中第一个负数结点的位置。要求先 给出算法思想，再写出相应算法。 （11 分） 第二部分第二部分 操作系统（操作系统（7 75 5 分）分） 一、一、 判断题判断题( (每小题每小题 1 1 分，共分，共 1010 分，正确的打分，正确的打，错误的打
8、，错误的打) ) 1. 设备的独立性是指 I/O 设备具有独立执行 I/O 功能的一种特性。 2. 并行程序设计中，使用信号量比使用管程更能保证程序的正确性。 3. 避免死锁的方法一般是以降低资源利用率为代价的。 4. 对一个具有三级索引表的文件，存储一条记录通常需要三次访问磁盘。 5. 分页存储管理比分段管理更适合动态链接的存储方式。 6. SPOOLing 系统允许用户随时将数据送入到输出井中。 7. UNIX 系统中，所有的设备、磁盘目录都被看作是文件。 8. 虚拟存储器的最大容量由计算机地址结构确定。 9. 分页式存储管理中，页面越小，存储器的利用率就越高。 10.分页存储管理比分段存
9、储管理在内存利用率更高些。 二、二、 填空题填空题( (每空每空 1 1 分，共分，共 1010 分分) ) 1. 进程由程序、数据集合和 （1） 组成。 2. 同步机制要遵循的四条规则分别是空闲让进、忙则等待、有限等待及 （2） 等待。 0 20 60 5 0 9 0 30831 0 3. 若系统中有 n 个用户进程，且当前 CPU 在用户态下执行，最多可有 （3） 个用户进程处 于就绪态。 4. 分时操作系统的主要特点是：交互性、多路性、 （4） 。 5. 产生死锁的根本原因是可共享资源不足，另一个基本原因是 （5） 。 6. 影响缺页次数的因素主要有： （6） 及页面本身的大小，程序的编
10、制方法和 （7） 。 7. Shell 的主要功能是 （8） 。 8. 某页式存储管理系统中，地址寄存器的长度为 24 位，其中页号占 14 位，主存的块大小 应是 （9） 字节，程序最多占 （10） 页。 三、三、 单选题单选题( (每小题每小题 1 1 分，共分，共 1010 分分) ) 1. 使用共享文件进行通信的方式属于( )通信。 A. 共享存储 B. 实时 C. 消息缓冲 D. 管道 2. 若作业采用动态重定位装入技术，该作业在内存中起始地址是 10000，作业中一条指令 是“Load A,5000” ，即把 5000 单元中的数据装入 A 寄存器，则该指令装入内存后，操作数 50
11、00 ( ) 。 A. 不变 B. 变为 15000 C. 变为 10000 D. 是随机数 3. 某设备的串行通信速率是 10000b/s(b:bit)，为该设备接口设置一个 4 字节的缓冲寄存 器，每隔( ) 需要 CPU 中断一次。 A. 2.5ms B. 3.2ms C. 8ms D. 0.1ms 4. 树形目录结构中，用户对文件的首次访问通常采用( )方式。 A. 文件路径名 B. 文件符号名 C. 用户文件描述符 D. 文件存储的物理位置 5. 实时系统的引入是为了使计算机( )响应外部事件的请求。 A. 快速 B. 按对象要求时间 C. 按人反应速度 D. 按人动作的速度 6.
12、分页式存储管理中，地址转换工作是由( )完成的。 A. 硬件 B. 地址转换程序 C. 用户程序 D. 装入程序 7. 计算机操作系统中，若 WAIT、SIGNAL 操作的信号量 S 初值为 3，当前值为-2，则表示当 前有( ) 个等待信号量 S 的进程。 A. 1 B. 2 C. 3 D. 0 8. 银行家算法是一种( )算法。 A. 死锁避免 B. 死锁预防 C. 死锁检测 D. 死锁解除 9. 假设磁头当前位于第 105 道，正在向磁道序号增加的方向移动。现有一个磁道访问请求 序列为 35，45，12，68，110，180，170，195，采用 SCAN 调度(电梯调度)算法得到的磁道
13、 访问序列是( ) 。 A. 110，170，180，195，68，45，35，12 B. 110，68，45，35，12，170，180，195 C. 110，170，180，195，12，35，45，68 D. 12，35，45，68，110，170，180，195 10. 分时系统中，CPU 进程切换需要 2ms，为使得 100 个用户均能在 1 秒内得到响应，应该 选择的时间片是（ ） 。 A. 2ms B. 50 ms C. 10ms D. 8 ms 四、四、 简答题简答题( (每小题每小题 5 5 分，共分，共 2525 分分) ) 1. 什么是信号（Signal） ，有什么用途？
14、 2. 实时操作系统与分时操作系统的本质区别是什么？ 3. 多线程系统与传统多进程系统相比有哪些优点？ 4. 为什么说多级反馈队列调度算法能较好地满足各类用户的需求？ 5. 分析并给出下面程序的输出结果？ int main(void) printf(“1111n”); fork(); printf(“2222n”); fork(); printf(“3333n”); fork(); printf(“4444n”); 五、五、 应用题应用题( (每小题每小题 1010 分，共分，共 2020 分分) ) 1. 某文件系统的一个文件控制块（FCB）占 64 个字节，盘块大小为 2K 字节，则每个盘
15、块可 存放的 FCB 数目是多少？如果一个文件目录中有 384 个 FCB，则查找一个文件平均需要启动 磁盘多少次？引入索引结点（i 结点）后，如果文件名占 14 个字节，索引结点占 2 个字节， 大小为 2K 字节的盘块可存放的目录项数目是多少？为找到一个文件，平均需要启动磁盘多 少次？（10 分） 2. 某银行在两个门口分别放置了排队取号机，客户进门时在取号机上按取号键，取号机打 印输出含有排队序号和前面等待人数的纸条给客户。 若干柜员每人桌面放有一台已设好窗口 号的叫号机， 按下叫号键若有客户等待就播放排在最前面的客户的号码和窗口号， 没有客户 则程序等待。请用信号量机制模拟叫号系统的功能。 （10 分）