重庆理工大学硕士研究生试题专用纸 第 1 页（共 5 页） 重庆理工大学 2018 年攻读硕士学位研究生入学考试试题 学院名称： 计算机科学与工程学院 学科、 专业名称： 计算机科学与技术 考试科目（代码） ：计算机学科基础综合(816)A 卷 （试题共 5 页） 注意： 1 所有试题的答案均写在专用的答题纸上， 写在试题纸上一律无效。 2. 试题与答题纸装入原信封内交回。 一、单选题（每小题 2 分，共 40 分） 1 算法分析的目的是（ ）。 A 找出数据结构的合理性 B 研究算法中的输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和稳定性 2 设某算法完成对 n 个元素进行处理所需的时间是：T(n) = 200log 2n+ 1000n(log2n + 100) + 100000，则该算法的时间复杂度是（ ） 。 A O(1) B O(n) C O(nlog2n) D O(nlog 2n+log2n) 3 若某链 表最常用的 操作是在最 后一个结 点之后插入 一个元素和删除最后 一个元素，则采用（ ）存储方式最节省运算时间。 A 单链表 B 双链表 C 单循环链表 D 带头结点的双循环链表 4 在中 缀表达式转 化为后缀表 达式与后 缀表达式求 值算法中，都需要用到 哪种特殊的数据结构（ ）。 A 栈 B 队列 C 二叉树 D 堆 5 一个队列的入队序列是 1 ，2 ，3 ，4 ， 则队列的出队序列只能是 （ ） 。 A 4 ，3 ，2 ，1B 1 ，2 ，3 ，4C 1 ，4 ，3 ，2D 3 ，2 ，4 ，1 6 将 含有 100 个结 点的完全 二叉树从 根结点开 始编号，根为 0 号， 后面按 从上到 下、从左 到右的顺序对结点 编号，那 么编号为 41 的结点 的双亲结 点 编号为（ ）。 A 42 B 40 C 21 D 20 7如果在某二叉树的前序序列、中序序列和后序序列中，结点 b 都在结点 a 的后面（即形如ab ） ，则最有可能的情况是（ ） 。 A a 和 b 是兄弟 B a 是 b 的双亲 C a 是 b 的左孩子 D a 是 b 的右孩子 8 某二叉树的后 序遍历序列是 dabec ， 中序遍历序列 是 debac ， 其前序遍历 序列是（ ）。 A acbed B decab C deabc D cedba 9 下述编码中，哪一个不是前缀码（ ）。 A (0,10,110,111) B (11,10,001,101,000)重庆理工大学硕士研究生试题专用纸 第 2 页（共 5 页） C (00,010,011,1) D (1,01,000,001) 10 一个有 n 个顶点的无向图最多有（ ）条边。 A nB n(n-1) C n(n-1)/2 D 2n 11 在现代操作系统中，采用缓冲技术的主要目的是（ ） A 改善用户编程环境 B 提高 CPU 的处理速度 C 实现与设备无关 D 提高设备与 CPU 之间的并行程度 12 下列哪个事件不可能在用户态发生？（ ） A 系统调用 B 外部中断 C 进程切换 D 缺页 13 操作系统是对（ ）进行管理的软件。 A 软件 B 硬件 C 计算机资源 D 应用程序 14 子程序调用和中断处理子程序都是以压入堆栈 的方式来保护现场的， 下 面哪个寄存器中的内容是中断处理一定会保存而子程序调用不用保存的？ （） A 程序计数器 B 通用地址寄存器 C 通用数据寄存器 D 程序状态寄存器 15 进程和程序的一个本质区别是 （ ） A 进程是动态的， 程序是静态的 B 进程存储在内存， 程序存储在外存 C 进程在一 个文件中 ， 程序在多 个文件中 D 进程分时 使用 CPU，程 序 独占 CPU 16 下列不属于 I/O 控制方式的是（ ） A 程序查询方式 B 覆盖方式 C DMA 方式 D 中断方式 17 在内存采取分区管理方式时，分区的保护措施主要是（ ） A 界限寄存器进行地址保护 B 程序状态保护 C 用户权限保护 D 存取控制保护 18 在一个文件被用户进程首次打开的过程中，操作系统需做的是（ ） A 将文件内容读入内存 B 将文件控制块读入内存 C修改 文件控制 块 的读写权限 D 将文 件的数据 缓 冲区首指针返 回 给用 户进程 19 计算机系统的二级存储包括（ ） A CPU 寄存器和主存缓存 B 超高速缓存和内存储器 C 主存储器和辅助存储器 D ROM 和 RAM 20 在不同速度的设备之间传送数据（ ） A 必须采用同步控制方式 B 必须采用异步控制方式 C 可用同步方式，也可以用异步方式 D 必须采用应答方式 二、综合题(110 分)重庆理工大学硕士研究生试题专用纸 第 3 页（共 5 页） 21 ( 本小题共 5 分) 有如下递归函数 fact(n) ，分析其时间复杂度。 fact(int n) if(n ， ， ， ， ，画 出其逻辑 结 构表示 （3 分） ，指 出是什么 类型 的逻 辑结 构？（2 分） 23 ( 本小题共 10 分) 有数据43 ，54 ，90 ，46 ，31 ，列 出冒 泡排 序每 趟的 结果(6 分) 。 编写 冒泡排序 算法 BubbleSort(RecType R ，int n) 的实 现程 序(4 分) 。 24 ( 本小题共 10 分) 假设哈希 表长度m=13 ， 采用除留 余数法哈希函 数建立 如下关键字集合的 哈 希表：(16 ，74 ，60 ，43 ，54 ，90 ，46 ，31 ，29 ，88 ， 77) 。并采用线性探查法解决冲突。 25 ( 本小题共 5 分) 有一组关键 字序列66 ，89 ，8 ，123 ，9 ，44 ，55 ，37 ， 200 ，127 ，98 ，请将其调整成初始大根堆，画出初始大根堆的树型表示。 26 ( 本小题共 9 分)有一 份电 文中， 使用了 a 、b 、c 、d 这 4 个字符，各字 符出现频率如下表。 字符 a b c d 出现频率 23 11 3 5 试构造对应的哈夫曼树 （请按左子树根结点的权小于等于右子树根结点的权 的次序构造）(6 分) ，并求出每个字符的哈夫曼编码(3 分) 。 27 ( 本小题共 8 分) 对于如图所示的 带权无向图， 给出利用普里姆 算法 （ 从 顶点 0 开始构 造）构造 出的最小生成树的 结果 。 （注意 ：按求解 的顺序给 出 最小生成树的所有边，每条边用(i ，j) 表示，顺序错误不给分！ ）0 1 2 3 4 5 1 5 2 3 7 6 8 4 28 ( 本小题共 8 分) 有如下工程项目的 AOE 图，其中数字表示 该项活动需 要的天数：重庆理工大学硕士研究生试题专用纸 第 4 页（共 5 页） （1 ）列出图中各顶点（事件）的最早发生时间和最迟发生时间(4 分) 。 （2 ）计算完成该项目所需的时间，指出哪些是关键活动(2 分) 。 （3 ）缩短任一关键活动的时间，是否会缩短整个工程的时间？(2 分) 29 ( 本小 题共 8 分) 现代 操作系 统采用 分层设计，用 户程序 发出磁 盘 I/O 请 求后需经 过 4 个层次的 调用才能进行实际的 I/O 操作， 阐述系统 进行 I/O 操 作的 4 个层次和具体的处理流程。 30 ( 本小题共 8 分) 在多道系统中 ， 由于有多个进程 运行可能导致死锁， 阐 述什么是死锁，有哪些情况可能会导致死锁，并简要说明阐述死锁的条件。 31 ( 本小题共 10 分) 一个多道批处理系统中仅有 A1 和 A2 两个作业，A2 比 A1 晚 10ms 到达，它们的计算和 I/O 操作顺序如下： A1 ：计算 60ms ，I/O 80ms ，计算 20ms A2 ：计算 120ms ，I/O 40ms ，计算 40ms 若不考虑调度和切换时间， 则完成两个作业需要的时间最少是多少？说 明计算依据？并用示意图表示进程的运行时间图。 32 ( 本小题共 10 分) 解释什么是最佳适应分区分配算 法和最坏适应分区分 配算法？各自的空闲分区是怎样组织的？各有什么缺点？设主存的分配情 况如下图所 示。当有一个用户进程 U 需申请 45KB 的存 储区时，若采用最 佳适应和最坏适应进行分配，U 所分到的分区首地址分别为多少？重庆理工大学硕士研究生试题专用纸 第 5 页（共 5 页） 33 ( 本小题共 14 分) 某企业有多个生产线和多个销售 人员，他们共用可存 放 100 个产品的仓库， 当仓库未装满时， 生产线可以将生产的一 件产品放入 仓库， 否则等待； 当仓库不空时， 销售人员可以取 走一件产品出售， 否则等 待。 要求一个销售人员从仓 库连续取出 5 件产品后， 其他销售人员才可以取 产品， 请用信 号量 P ，V （wait ，signed ） 操作实 现进程间 的互斥和 同步， 要 求写出完整的过程；并指出所用信号量的含义和初值。