中国科学院研究生院

Size: px

Start display at page:

Download "中国科学院研究生院"

獭袁
7 years ago
Views:

1 中国科学院大学 2013 年招收攻读硕士学位研究生入学统一考试试题考生须知 : 1. 本试卷满分为 150 分, 全部考试时间总计 180 分钟 2. 所有答案必须写在答题纸上, 写在试题纸上或草稿纸上一律无效一单选题 ( 每小题 2 分, 共 80 分 ) 1. 操作系统负责管理和控制计算机系统的 A. 软件资源 B. 硬件资源和软件资源 C. 对用户有用的资源 D. 硬件资源 2. UNIX 操作系统产生于年 A B C D 进程和程序的本质区别是 A. 前者分时使用 CPU, 后者独占 CPU B. 前者存储在内存, 后者存储在外存 C. 前者在一个文件中, 后者在多个文件中 D. 前者是动态的, 后者是静态的 4. 置换算法会产生 Belady 现象 A. 最不常用 B. 先进先出 C. 最近最久未使用 D. 最佳 5. 下列关于管程的叙述中, 错误的是 A. 管程有数据结构, 但不包含对数据的操作 B. 管程内部定义函数的具体实现对于外部来说是不可见的 C. 管程是一个基本程序单位, 可以单独编译 D. 管程中引入了面向对象的思想 6. 如果 P V 操作的信号量 S 的初值为 3, 当前值为 -2, 则表示有第 1 页共 7 页

2 个等待进程 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. 页和段的大小都是固定的第 2 页共 7 页

3 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. 逻辑结构不一样第 3 页共 7 页

4 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 设一条单链表的头指针变量为 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. 设顺序循环队列 Q[0 : 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 的有序树第 4 页共 7 页

5 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 设一棵 m 叉树中度数为 0 的结点数为 N 0, 度数为 1 的结点数为 N l,, 度数为 m 的结点数为 N m, 则 N 0 = A. N l +N 2 + +N m B. N 2 +2N 3 +3N 4 + +(m-1)n m C. l+n 2 +2N 3 +3N 4 + +(m-1)n m D. 2N l +3N 2 + +(m+1)n m 34. 设某完全无向图中有 n 个顶点, 则该完全无向图中有条边 A. n(n-1)/2 B. n(n-1) C. n 2 D. n 以下关于图的说法中, 正确的是 A. 强连通有向图的任何顶点到其他顶点都有弧 B. 图与树的区别在于图的边数大于或等于顶点数 C. 无向图的连通分量指的是无向图中的极大连通子图 D. 无向图中, 各顶点度的和等于该图的总边数 36. 设用邻接矩阵 A 表示有向图 G 的存储结构, 则有向图 G 中顶点 i 的入度为第 5 页共 7 页

6 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, 设一组初始记录关键字序列为 (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, 设有 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; 第 6 页共 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 的最短路径第 7 页共 7 页

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程一单项选择题 ( 本题共 20 小题, 每题 2 分, 共 40 分 ) 1. 计算机所处理的数据一般具有某种内在联系, 这是指 ( ) A. 数据和数据之间存在某种联系 B. 数据项和数据项之间存在某种联系 C. 元素内部具有某种结构 D. 元素和元素之间存在某种联系 2. 在计算机中表示数据时, 数据的物理地址和逻辑地址相同并且连续, 称其为 ( ) A. 链式存储结构 B. 顺序存储结构 C.