资源描述
中国科学院研究生院 2012年招收攻读硕士学位研究生入学统一考试试题 科目名称：计算机软件基础 考生须知： 1本试卷满分为150分，全部考试时间总计180分钟。 2所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。 第一部分：数据结构（共70分） 一、单选题（每题 2 分，共20分） 1下面关于线性表的叙述错误的是【 】。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2. 栈和队列的共同特点是【 】。 (A) 只允许在端点处插入和删除元素 (B) 都是先进后出 (C) 都是先进先出 (D) 没有共同点 3. 以下数据结构中【 】是非线性结构。 (A) 队列 (B) 栈 (C) 线性表 (D) 二叉树 4. 树最适合用来表示【 】。 (A) 有序数据元素 (B) 无序数据元素 (C) 元素之间具有分支层次关系的数据 (D) 元素之间无联系的数据 5. 二叉树的第k层的结点数最多为【 】。 (A)2k-1 (B)2k+1 (C)2k-1 (D) 2k-1 6若有 18 个元素的有序表存放在一维数组 A19中，第一个元素放 A1中，现进行二分查找，则查找A3的比较序列的下标依次为【 】。 科目名称：计算机软件基础 第 1 页 共 5 页 ( A) 1，2，3 (B) 9，5，2，3 (C) 9，5，3 (D) 9，4，2，3 7. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为【 】。 (A) O（1） (B) O（n） (C) O（1og2n） (D) O（n2） 8设有 6 个结点的无向图，该图至少应有【 】条边才能确保是一个连通图。 （A）5 （B）6 （C）7 （D）8 9设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有【 】个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 10设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为 CABD，则后序遍历该二叉树得到序列为【 】。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 二、填空题（每空2分，共20分） 1. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为【 】。 2. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有【 】个指针域，其中有【 】个指针域是存放了地址，有【 】个指针是空指针。 3. 在一个具有 n 个顶点的无向完全图中，包含有【 】条边，在一个具有 n个顶点的有向完全图中，包含有【 】条边。 4. 向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度【 】。 5. 为了能有效地应用HASH查找技术，必须解决的两个问题是【 】和【 】。 6. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为【 】。 三、计算题（每题 10分，共30分） 1. 在如下数组 A中链接存储了一个线性表，表头指针为 A 0.next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 科目名称：计算机软件基础 第 2 页 共 5 页 2. 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字 62 时的比较次数并计算出查找成功时的平均查找长度。 3已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试： （1）计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6 （2）求出在查找每一个元素概率相等情况下的平均查找长度。 第二部分：操作系统（共40分） 一、单选题（每题 2 分，共10分） 1把逻辑地址转变为内存的物理地址的过程称做【 】。 (A) 编译 (B) 连接 (C) 运行 (D) 重定位 2进程和程序的一个本质区别是【 】。 (A) 前者分时使用 CPU，后者独占 CPU (B) 前者存储在内存，后者存储在外存 (C) 前者在一个文件中，后者在多个文件中 (D) 前者为动态的，后者为静态的 3. 在操作系统中，P、V操作是一种【 】。 (A) 机器指令 (B) 系统调用命令 (C) 作业控制命令 (D) 低级进程通信原语 4. 分页式虚拟存储管理系统中，一般来说页面的大小与可能产生缺页中断的次数【 】。 (A) 成正比 (B) 成反比 (C) 无关 (D) 成固定比值 5. 下列关于时间片轮转算法的叙述中，不正确的是【 】。 (A) 在时间片轮转算法中，系统将 CPU 的处理时间划分成一个个时间段 (B) 就绪队列中的各个进程轮流在 CPU 上运行，每次运行一个时间片 (C) 时间片结束时，运行进程自动让出 CPU 并进入等待队列 (D) 如果时间片长度很小，则调度程序抢占 CPU 的次数频繁，增加了系统开销 科目名称：计算机软件基础 第 3 页 共 5 页 二、填空题（每空2分，共10分） 1. 当某个正在执行的进程需要进行 I/O 操作时，可以通过调用【 】原语将自己从运行状态变为等待状态。 2. 主存储器与外围设备之间的信息传送操作称为【 】。 3. 在单 CPU 系统中，如果同时存在 12 个并发进程，则处于就绪队列中的进程最多有【 】。 4. 文件系统中，当用户进程打开一个文件时，操作系统将该文件的文件描述符保存在内存的【 】表中。 5. 访问磁盘时，当磁头到达指定磁道后，必须等待所需要的扇区到达读写头下，这一部分时间称为【 】时间。 三、简答题（每题 5分，共20分） 1简述中断装置的主要职能。 2. 简述死锁的防止与死锁的避免的区别。 3. 为建立虚拟存储系统需要哪些条件？ 4. 试给出两种 I/O 调度算法，并说明为什么 I/O 调度中不能采用时间片轮转法？ 第三部分：编译原理（共40分） 一、选择题(每题2分，共10分) 1编译程序绝大多数时间花在【 】上。 (A) 出错处理 (B) 词法分析 (C) 目标代码生成 (D) 管理表格 2词法分析器的输出结果是【 】。 (A) 单词的种别编码 (B) 单词在符号表中的位置 (C) 单词的种别编码和自身值 (D) 单词自身值 3若 a 为终结符，则 Aa 为【 】项目 (A) 归约 (B) 移进 (C) 接受 (D) 待约 科目名称：计算机软件基础 第 4 页 共 5 页 4四元式之间的联系是通过【 】实现的。 (A) 指示器 (B) 临时变量 (C) 符号表 (D) 程序变量 5对一个基本块来说，【 】是正确的。 (A) 只有一个入口语句和一个出口语句；(B) 有一个入口语句和多个出口语句; (C) 有多个入口语句和一个出口语句; (D) 有多个入口语句和多个出口语句. 二、简答题 (每题4分，共12分) 1给出下述文法所对应的正规式： S0A|1B A1S|1 B0S|0 2将文法GS 改写为等价的GS，使GS不含左递归和左公共因子。 GS： SbSAe | bA AAb | d 3写出表达式(ab*c)/(ab)d 的逆波兰表示及三元式序列。 三、已知文法GS：(10分) SMH|a HLSo| KdML| LeHf MK|bLM 判断G是否是LL(1)文法，如果是，构造 LL(1)分析表。 四、过程参数的传递方式有几种?简述“传地址“和“传值“的实现原理。(8 分) 科目名称：计算机软件基础 第 5 页 共 5 页
展开阅读全文