北京中国科学院大学2013年考研计算机技术基础真题

《北京中国科学院大学2013年考研计算机技术基础真题》由会员分享，可在线阅读，更多相关《北京中国科学院大学2013年考研计算机技术基础真题（8页珍藏版）》请在装配图网上搜索。

1、（北京）中国科学院大学2013年考研计算机技术基础真题中国科学院大学2013 年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机技术基础考生须知：1本试卷满分为 150 分，全部考试时间总计 180 分钟。2所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。一、单选题（每小题 2 分，共 80 分）1. 操作系统负责管理和控制计算机系统的_。A. 软件资源 B. 硬件资源和软件资源C. 对用户有用的资源 D. 硬件资源2. UNIX 操作系统产生于_年。A. 1965 B. 1970C. 1973 D. 19753. 进程和程序的本质区别是_。A. 前者分时使用 CPU，后者独占

2、 CPUB. 前者存储在内存，后者存储在外存C. 前者在一个文件中，后者在多个文件中D. 前者是动态的，后者是静态的4. _置换算法会产生 Belady 现象。A. 最不常用 B. 先进先出C. 最近最久未使用 D. 最佳5. 下列关于管程的叙述中，错误的是_。A. 管程有数据结构，但不包含对数据的操作B. 管程内部定义函数的具体实现对于外部来说是不可见的C. 管程是一个基本程序单位，可以单独编译D. 管程中引入了面向对象的思想6. 如果 P、V 操作的信号量 S 的初值为 3，当前值为-2，则表示有_个等待进程。A. 0 个 B. 1 个C. 2 个 D. 3 个7. 进程和线程的本质区别是

3、_。A. 前者存储在外存，后者存储在内存B. 前者有地址空间，后者没有地址空间C. 前者在一个文件中，后者在多个文件中D. 前者是拥有资源的基本单位，后者是程序执行的基本单位8. 关于线程的优点，描述不正确的是_。A. 线程是具有最少开销的程序执行实体B. 撤销线程比撤销进程花费的时间短C. 线程间切换比进程间切换花费的时间短D. 由于共享资源，一个进程中的线程不能并发执行9. 关于内核线程和用户线程，描述不正确的是_。A. 在多机系统中，调度可以为一个进程中的多个内核线程分配多个 CPUB. 当进程中的一个用户线程被阻塞时，整个进程并不用等待C. 采用轮转调度算法，进程中设置内核线程和用户线

4、程的效果完全不同D. 当内核线程阻塞时，CPU 将会调度同一进程中的其他内核线程执行10. 分页存储管理的目的是_。A. 回收空白区方便 B. 便于多个进程共享内存C. 解决碎片问题 D. 摆脱用户干预11. _算法不是调度算法。A. 先来先服务 B. 鸵鸟算法C. 多级队列算法 D. 优先级算法12. 不属于进程共享资源三个层次的是_。A. 互斥 B. 并发C. 饥饿 D. 死锁13. 关于分段系统与分页系统的区别，描述不正确的是_。A. 页帧是信息的物理单位，段是信息的逻辑单位B. 页和段的大小都是固定的C. 分页对用户是透明的，分段对用户是可见的D. 分段存储管理容易实现内存共享，分页存

5、储管理较难实现内存共享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. 容易产生饥饿现象的磁盘调度算法是_。

6、A. 最短寻道时间优先 B. 扫描C. 先来先服务 D. 单向扫描19. 银行家算法是一种_算法。A. 死锁避免 B. 死锁预防C. 死锁解除 D. 死锁检测20. 文件系统中用_管理文件。A. 进程控制块 B. 目录C. 外页表 D. 软硬件结合的方法21. 数组的逻辑结构不同于_的逻辑结构。A. 线性表 B. 栈C. 队列 D. 树22. 栈和队列的主要区别在于_。A. 逻辑结构不一样B. 存储结构不一样C. 所包含的运算不一样D. 插入和删除运算的限定不一样23. 设一维数组中有 n 个数组元素，则读取第 i 个数组元素的平均时间复杂度为_。A. O(n) B. O(nlog2n)C.

7、O(1) D. O(n2)24. 设有 n 个待排序的记录关键字，则在堆排序中需要_个辅助记录单元。A. 1 B. nC. nlog2n D. n225. 设一条单链表的头指针变量为 head 且该链表没有头结点，则其判空条件是_。A. head=0 B. head-next=0C. head-next=head D. head!=026. 假设栈的容量为 3，入栈的队列为 5,4,3,2,1，则出栈的序列可能为_。A. 3,4,5,1,2 B. 5,1,2,3,4C. 1,2,3,4,5 D. 2,3,4,5,127. 利用栈求表达式的值时，设立运算数栈 OPERATER。假设 OPERAT

8、ER只有两个存储单元，则在下列表达式中，不会发生溢出的是_。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)%MC. F-R D. R-F29. 关于二叉树，下列说法正确的是_。A. 二叉树的度为 2B. 一颗二叉树的度可以小于 2C. 二叉树中至少有一个结点的度为 2D. 二叉树就是度为 2 的有序树30. 设

9、某棵二叉树的中序遍历序列为 ABCD, 后序遍历序列为 BADC, 则前序遍历该二叉树得到的序列为_。A. CABD B. CBADC. CDAB D. CDBA31. 设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有_个空指针域。A. 2m-1 B. 2mC. 2m+1 D. 4m32. 以下关于二叉排序树的说法中，错误的有_个。（1）对一颗二叉排序树按前序遍历得出的结点序列是从小到大的序列。（2）每个结点的值都比它左孩子的值大且比它右孩子结点的值小，则这样的一颗二叉树就是二叉排序树。（3）在二叉排序树中，新插入的关键字总是处于最底层。（4）删除二叉排序树中的

10、一个结点再重新插入，得到的二叉树和原来的相同。A. 1 B. 2C. 3 D. 433. 设一棵 m 叉树中度数为 0 的结点数为 N0 ，度数为 1 的结点数为 Nl，度数为 m 的结点数为 Nm，则 N0=_。A. Nl+N2+NmB. N2+2N3+3N4+(m-1)NmC. l+N2+2N3+3N4+(m-1)NmD. 2Nl+3N2+(m+1)Nm34. 设某完全无向图中有 n 个顶点，则该完全无向图中有_条边。A. n(n-1)/2 B. n(n-1)C. n2 D. n2-135. 以下关于图的说法中，正确的是_。A. 强连通有向图的任何顶点到其他顶点都有弧B. 图与树的区别在于

11、图的边数大于或等于顶点数C. 无向图的连通分量指的是无向图中的极大连通子图D. 无向图中，各顶点度的和等于该图的总边数36. 设用邻接矩阵 A 表示有向图 G 的存储结构，则有向图 G 中顶点 i 的入度为_。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, 75C. 70, 82, 75,73 D.

12、70, 81, 73, 7538. 设一组初始记录关键字序列为（45,80,55,40,42,85），则以第一个记录关键字 45 为基准而得到一趟快速排序的结果是_。A. 40, 42, 45, 55, 80, 83B. 42, 40, 45, 80, 85, 88C. 42, 40, 45, 55, 80, 85D. 42, 40, 45, 85, 55, 8039. 设有 5000 个待排序的记录关键字，如果需要用最快的方法选出其中最小的 10 个记录关键字，则用_方法可以达到此目的。A. 快速排序 B. 堆排序C. 归并排序 D. 插入排序40. 在以下四种排序方法中，_的空间复杂度最大

13、。A. 插入排序 B. 冒泡排序C. 堆排序 D. 归并排序二、简答题（每小题 5 分，共 15 分）1. 简要叙述一下哲学家就餐问题，并利用信号量、wait 操作、signal 操作编程描述一下该问题。2. 进程通信类型有几种方式？哪种方式适合计算机网络通信？3. 简要说明预防 CPU 死锁和解除死锁的方法。三、（8 分）使用伙伴系统管理 1MB 的内存分区：1. 画图说明下面进程顺序执行的结果：（1） 进程 A 请求 80KB；（2） 进程 B 请求 55KB；（3） 进程 C 请求 90KB；（4） 进程 A 结束；（5） 进程 D 请求 70KB；（6） 进程 B 结束；（7） 进程

14、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=AB

15、的算法，其中集合 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 的最短路径。