【考研真题】新祥旭权威发布中国科学院研究生院计算机软件基础2012年考研真题

新祥旭高硕网站：第一部分：数据结构(共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-16.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为【】。科目名称：计算机软件基础第1页共5页8.设有6个结点的无向图，该图至少应有【】条边才能确保是一个连通图。(A)5(B)6(C)7(D)8新祥旭高硕网站：设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有【】个空指针域。(A)2m-1(B)2m(C)2m+1(D)4m10.设某棵二叉树的中序遍历序列为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)1，2，3(B)9，5，2，3(C)9，5，3(D)9，4，2，32.设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。3.已知待散列的线性表为(36，15，40，63，22)，散列用的一维地址空间为[0..6]，假新祥旭高硕网站：定选用的散列函数是H(K)=Kmod7，若发生冲突采用线性探查法处理，试：(1)计算出每一个元素的散列地址并在下图中填写出散列表：(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的次数频繁，增加了系统开销新祥旭高硕网站：二、填空题(每空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为终结符，则A→α·aβ为【】项目新祥旭高硕网站：(A)归约(B)移进(C)接受(D)待约4.四元式之间的联系是通过【】实现的。(A)指示器(B)临时变量(C)符号表(D)程序变量5.对一个基本块来说，【】是正确的。(A)只有一个入口语句和一个出口语句;(B)有一个入口语句和多个出口语句;(C)有多个入口语句和一个出口语句;(D)有多个入口语句和多个出口语句.二、简答题(每题4分，共12分)1.给出下述文法所对应的正规式：S→0A|1BA→1S|1B→0S|02.将文法G[S]改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]：S→bSAe|bAA→Ab|d3.写出表达式(a+b*c)/(a+b)-d的逆波兰表示及三元式序列。三、已知文法G[S]：(10分)S→MH|aH→LSo|εK→dML|εL→eHf新祥旭高硕网站：→K|bLM判断G是否是LL(1)文法，如果是，构造LL(1)分析表。四、过程参数的传递方式有几种?简述传地址和传值的实现原理。(8分)