资源描述
科目名称：计算机技术基础 第 1 页 共 7 页 中国科 学院 大学 2013 年招 收攻 读硕士 学位研 究生入 学统一 考试试 题 科目名 称：计 算机技 术基础 考 生须 知： 1本试卷满分为 150 分，全部考试时间总计 180 分钟。 2所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。 一、单选题（每小题 2 分，共 80 分） 1. 操作系统负责管理和控制计算机系统的_。 A. 软件资源 B. 硬件资源和软件资源 C. 对用户有用的资源 D. 硬件资源 2. UNIX 操作系统产生于_年。 A. 1965 B. 1970 C. 1973 D. 1975 3. 进程和程序的本质区别是_。 A. 前者分时使用 CPU ，后者独占 CPU B. 前者存储在内存， 后者存储在外存 C. 前者在一个文件中，后者在多个文件中 D. 前者是动态的，后者是静态的 4. _置换算法会产生 Belady 现象。 A. 最不常用 B. 先进先出 C. 最近最久未使用 D. 最佳 5. 下列关于管程的叙述中，错误的是_。 A. 管程有数据结构，但不包含对数据的操作 B. 管程内部定义函数 的具体实现对于外部来说是不可见的 C. 管程是一个基本程序单位，可以单独编译 D. 管程中引入了面向对象的思想 6. 如果 P 、V 操作的信号 量 S 的初值为 3，当前 值为-2，则表示有_ 科目名称：计算机技术基础 第 2 页 共 7 页 个等待进程。 A. 0 个 B. 1 个 C. 2 个 D. 3 个 7. 进程和线程的本质区别是_。 A. 前者存储在外存，后者存储在内存 B. 前者有地址空间， 后者没有地址空间 C. 前者在一个文件中，后者在多个文件中 D. 前者是拥有资源的基本单位，后者是程序执行的基本单位 8. 关于线程的优点，描述不正确的是_。 A. 线程是具有最少开销的程序执行实体 B. 撤销线程比撤销进 程花费的时间短 C. 线程间切换比进程间切换花费的时间短 D. 由于共享资源，一个进程中的线程不能并发执行 9. 关于内核线程和用户线程，描述不正确的是_。 A. 在多机系统中， 调度可以为一个进程中的多个内核线程分配多个 CPU B. 当进程中的一个用 户线程被阻塞时，整个进程并不用等待 C. 采用轮转调度算法， 进程中设置内核线程和用户线程的效果完全不同 D. 当内核线程阻塞时，CPU 将会调度同一进程中的其他内核线程执行 10. 分页存储管理的目的是_。 A. 回收空白区方便 B. 便于多个进程共享内存 C. 解决碎片问题 D. 摆脱用户干预 11. _算法不是调度算法。 A. 先来先服务 B. 鸵鸟算法 C. 多级队列算法 D. 优先级算法 12. 不属于进程共享资源三个层次的是_。 A. 互斥 B. 并发 C. 饥饿 D. 死锁 13. 关于分段系统与分页系统的区别，描述不正确的是_。 A. 页帧是信息的物理单位，段是信息的逻辑单位 B. 页和段的大小都是 固定的 科目名称：计算机技术基础 第 3 页 共 7 页 C. 分页对用户是透明的，分段对用户是可见的 D. 分段存储管理容易实现内存共享，分页存储管理较难实现内存共享 14. 使用虚拟存储器的目的是实现_。 A. 程序浮动 B. 存储保护 C. 扩充内存 D. 扩充辅存 15. 关于分区式存储管理技术，描述不正确的是_。 A. 固定分区限制了系统中并发进程的数目，并会产生内碎片 B. 动态分区管理复杂 ，会产生外碎片 C. 伙伴系统是固定分区和动态分区的折中方案，克服了两者的缺陷 D. 伙伴系统没有内存回收机制，所以目前使用较少 16. _不是系统总线。 A. SCI 总线 B. PCI 总线 C. ISA 总线 D. VESA 总线 17. 不是专用缓冲的是_。 A. 单缓冲 B. 循环缓冲 C. 双缓冲 D. 缓冲池 18. 容易产生饥饿现象的磁盘调度算法是_。 A. 最短寻道时间优先 B. 扫描 C. 先来先服务 D. 单向扫描 19. 银行家算法是一种_算法。 A. 死锁避免 B. 死锁预防 C. 死锁解除 D. 死锁检测 20. 文件系统中用_管理文件。 A. 进程控制块 B. 目录 C. 外页表 D. 软硬件结合的方法 21. 数组的逻辑结构不同于_的逻辑结构。 A. 线性表 B. 栈 C. 队列 D. 树 22. 栈和队列的主要区别在于_。 A. 逻辑结构不一样 科目名称：计算机技术基础 第 4 页 共 7 页 B. 存储结构不一样 C. 所包含的运算不一样 D. 插入和删除运算的限定不一样 23. 设一维数组中有 n 个数组元素，则读取第 i 个数组元素的平均时间复杂 度为_。 A. O(n) B. O(nlog 2 n) C. O(1) D. O(n 2 ) 24. 设有 n 个待 排序 的记 录关键 字， 则在 堆排 序 中需要_个辅 助记录 单 元。 A. 1 B. n C. nlog 2 n D. n 225. 设一条单链表的头指针变量为 head 且该链表 没有头结点， 则其判空条件 是_。 A. head=0 B. head-next=0 C. head-next=head D. head!=0 26. 假设栈的容量为 3，入栈的队列为 5,4,3,2,1，则出栈的序列可能为_。 A. 3,4,5,1,2 B. 5,1,2,3,4 C. 1,2,3,4,5 D. 2,3,4,5,1 27. 利用栈求表达式的值时 ，设立运算数栈 OPERATER 。假设 OPERATER 只有两个存储单元，则在下列表达式中，不会发生溢出的是_。 A. (A-B*C)-D B. A-B*(C-D) C. (A-B)*C-D D. (A-B)*(C-D) 28. 设顺序循环队列 Q0 : M-1 的头指针和尾指针分别为 F 和 R ，头指针 F 总是指向队头元素的前一位置， 尾指针 R 总是指向队尾元素的当前位置， 则该循环队列中的元素个数为_。 A. (F-R+M)%M B. (R-F+M)%M C. F-R D. R-F 29. 关于二叉树，下列说法正确的是_。 A. 二叉树的度为2 B. 一颗二叉树的度可 以小于 2 C. 二叉树中至少有一个结点的度为2 D. 二叉树就是度为 2 的有序树 科目名称：计算机技术基础 第 5 页 共 7 页 30. 设某棵二 叉树的 中序遍 历序列为 ABCD, 后序 遍历序列为 BADC, 则前 序遍历该二叉树得到的序列为_。 A. CABD B. CBAD C. CDAB D. CDBA 31. 设哈夫曼树中的叶子结点总数为 m ，若用二叉 链表作为存储结构，则该 哈夫曼树中总共有_个空指针域。 A. 2m-1 B. 2m C. 2m+1 D. 4m 32. 以下关于二叉排序树的说法中，错误的有_个。 （1）对一颗二叉排序树按前序遍历得出的结点序列是从小到大的序列。 （2） 每个结点的值都比它左孩子的值大且比它右孩子结点的值小， 则这 样的一颗二叉树就是二叉排序树。 （3）在二叉排序树中，新插入的关键字总是处于最底层。 （4） 删除二叉排序树中的一个结点再重新插入， 得到的二叉树和原来的 相同。 A. 1 B. 2 C. 3 D. 4 33. 设一棵 m 叉树中度数 为 0 的结点数为 N 0，度 数 为 1 的结点数为 N l ， ， 度数为 m 的结点数为 N m ，则 N 0 =_。 A. N l +N 2 +N mB. N 2 +2N 3 +3N 4 +(m-1)N mC. l+N 2 +2N 3 +3N 4 +(m-1)N mD. 2N l +3N 2 +(m+1)N m34. 设某完全无向图中有 n 个顶点，则该完全无向图中有_条边。 A. n(n-1)/2 B. n(n-1) C. n 2D. n 2 -1 35. 以下关于图的说法中，正确的是_。 A. 强连通有向图的任何顶点到其他顶点都有弧 B. 图与树的区别在于 图的边数大于或等于顶点数 C. 无向图的连通分量指的是无向图中的极大连通子图 D. 无向图中，各顶点度的和等于该图的总边数 36. 设用邻接矩阵 A 表示有向图 G 的存储结构， 则有向图 G 中顶点 i 的入度 为_。 科目名称：计算机技术基础 第 6 页 共 7 页 A. 第 i 行非 0 元素的个数之和 B. 第 i 列非 0 元素的个 数之和 C. 第 i 行 0 元素的个数之和 D. 第 i 列 0 元素的个数之和 37. 折半查找有序表（2,10,25,35,40,65,70,73,75,81,82,88,100 ） ，若查找元素 75，需依次与表中元素_进行比较。 A. 70, 81, 75 B. 70, 82, 75 C. 70, 82, 75,73 D. 70, 81, 73, 75 38. 设一组初始记录关键字序列为 （45,80,55,40,42,85 ） ，则以第一个记录关 键字 45 为基准而得到一趟快速排序的结果是_。 A. 40, 42, 45, 55, 80, 83 B. 42, 40, 45, 80, 85, 88 C. 42, 40, 45, 55, 80, 85 D. 42, 40, 45, 85, 55, 80 39. 设有 5000 个待排序的记录关键字， 如果需要用最快的方法选出其中最小 的 10 个记录关键字，则用_方法可以达到此目的。 A. 快速排序 B. 堆排序 C. 归并排序 D. 插入排序 40. 在以下四种排序方法中，_的空间复杂度最大。 A. 插入排序 B. 冒泡排序 C. 堆排序 D. 归并排序 二、简答题（每小题 5 分，共 15 分） 1. 简要叙述一下哲学家就餐问题， 并利用信号量、 wait 操作、 signal 操作编 程描述一下该问题。 2. 进程通信类型有几种方式？哪种方式适合计算机网络通信？ 3. 简要说明预防 CPU 死锁和解除死锁的方法。 三 、（ 8 分）使用伙伴系统管理 1MB 的内存 分区： 1. 画图说明下面进程顺序执行的结果： （1） 进程 A 请求 80KB ； （2） 进程 B 请求 55KB ； （3） 进程 C 请求 90KB ； 科目名称：计算机技术基础 第 7 页 共 7 页 （4） 进程 A 结束； （5） 进程 D 请求 70KB ； （6） 进程 B 结束； （7） 进程 D 结束； （8） 进程 C 结束。 2. 给出进程 B 结束后的二 叉树表示。 四 、（ 8 分） 在一个请求分页系统中， 采用 LRU 页面置换算法， 例如一个作业的 页面走向 为 4，3，2 ，1，4，3，5 ，4，3，2 ，1，5 ，当分 配给该 作 业的物理块 数 M 分别为 3 和 4 时，试计算访问过程中所发生的缺页次数和缺页率（注意， 所有内 存块最 初都 是空 的，第 一次用 到的 页面 都产生 一次缺 页） ，并 比较所 得的 结果。 五 、（ 8 分）给定一个权值集合 W=(3 ，5，7，9，11) ，要求根据给 定的权值集合 构造一棵哈夫曼树并计算该哈夫曼树的带权路径长度 WPL 。 六 、（ 10 分） 设有两个 集合 A 和集合 B ， 设计 生成集合 C=A B 的算 法， 其中集 合 A 、B 和 C 用数组存 储表示。 1. 给出算法的基本设计思想； 2. 根据设计思想，采用 C 或 C+或 java 语言表述 算法，关键之处给出注释； 3. 说明你所设计算法的时间复杂度。 七、 （9 分） 设散列表的 长度为 8， 散列函数 H(k)=k mod 7， 初始记录 关键字序列 为（18 ，17，15 ，34 ，20，40 ） ，要 求分 别用 线性探 测和链 地址 法作 为解决 冲突 的方法设计哈希表，并求出查找成功的平均查找长度。 八、 （12 分） 下图所示是一带权有向图的邻接表。 其中出边表中的每个结点均包 含 3 个字段， 依次为边的另一顶点在顶点表中的序号、 边上的权值和指向下一个 边结点的指针，试求： 1. 该带权有向图的图形； 2. 从顶点 V1 为起点的广度优先搜索的顶点序列及对应的生成树； 3. 以顶点 V1 为起点的深度优先搜索的生成树； 4. 由顶点 V1 到顶点 V3 的最短路径。
展开阅读全文