中国科学院大学中国科学院大学2013年招收攻读硕士学位研究生入学统一考试试题科目名称：科目名称：计算机软件基础考生须知： 考生须知1．本试卷满分为150分，全部考试时间总计180分钟。 2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。 第一部分：数据结构第一部分数据结构（数据结构（共70分）一、单选题单选题（每题2分，共20分）1. 下列关于数据的逻辑结构的叙述中，不正确的是【 】。(A) 数据的逻辑结构是数据间关系的描述(B) 线性表是典型的线性结构(C) 数据的逻辑结构分为线性结构和非线性结构(D) 数据的逻辑结构不仅反映数据间的逻辑关系，而且包含其在计算机中的存储方式2. 下列关于数据运算的叙述中，不正确的是【 】。(A) 数据运算是数据结构的一个重要方面(B) 数据运算的具体实现是在数据的逻辑结构上进行(C) 检索是一种常用的运算(D) 插入是一种常用的运算3. 在包含1000个元素的线性表中实现如下各运算，所需执行时间最长的是【 】。(A) 线性表按顺序方式存储，删除线性表的第900个结点(B) 线性表按链式方式存储，删除指针P所指向的结点(C) 线性表按顺序方式存储，在线性表的第100个结点后面插入一个新结点(D) 线性表按链式方式存储，在线性表的第100个结点后面插入一个新结点 科目名称：计算机软件基础 第 1 页 共 7 页4. 设某散列表的当前状态如下0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19075 194 768559 582 208该散列表的负载因子约为【 】。(A) 0.37 (B) 0.42 (C) 0.58 (D) 0.73 5. 设有关键码序列（Q,G,M,Z,A,N,B,P,X,H,Y,S,T,L,K,E），采用堆排序法进行排序，经过初试建堆后关键码值A在序列中的序号是【 】。(A) 1 (B) 4 (C) 8 (D) 12 6. 栈和队列的共同特点是【 】。(A) 只允许在端点处插入和删除元素 (B) 都是先进后出 (C) 都是先进先出 (D) 没有共同点 7. 用链接方式存储的队列，在进行插入运算时【 】。(A) 仅修改头指针 (B) 头、尾指针都要修改(C) 仅修改尾指针 (D) 头、尾指针可能都要修改8. 以下数据结构中哪一个是非线性结构？【 】 (A) 队列 (B) 栈 (C) 线性表 (D) 二叉树9. 设有6个结点的无向图，该图至少应有【 】条边才能确保是一个连通图。 (A) 5 (B) 6 (C) 7 (D) 8 10. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有【 】个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 二、填空题（填空题（每题2分，共20分） 1．数据逻辑结构中非线性结构包括______结构和______结构两种类型。2. 按行优先顺序存储一个下三角矩阵Ann的非零元素，则计算非零元素aij(1≤j ≤i ≤ n)的地址的公式为Locaij) =______ + i*i-1)/2 +j-1)。3. m阶B+树的根结点至多有______个子结点。4. 能够成功完成拓扑排序的图一定是一个______。 科目名称：计算机软件基础 第 2 页 共 7 页5. 如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用______较为适当。6．空串的长度是______；空格串的长度是______的数目。 7. 已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用是______。8. 产生冲突现象的两个关键字称为该散列函数的______。 9. 有29条边的无向连通图，至少有______个顶点，至多有______个顶点。10．设有100个元素的排序顺序文件中，采用折半查找，最大比较次数为______最小为______。三、问答题（问答题（每题5分，30分）1. 评价一个好的算法，您是从哪几方面来考虑的？ 2. 试说明一棵二叉树无论进行前序、中序或后序遍历，其叶结点的相对次序不发生改变。 3. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化（每加入一个数据后，都需要进行调整成为小根堆）。4. 设有以下三个函数： f(n)=21n4+n2+1000请判断以下断言正确与否： (1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n3.5) (5) h(n)是O(nlogn) 5. 一棵度为2的树与一棵二叉树有何区别？ 6. 证明：一棵满k叉树上的叶子结点数n0和非叶子结点数n之间满足以下关系： g(n)=15n4+500n3h(n)=500n3.5+nlognn0=(k−1)n+1 科目名称：计算机软件基础 第 3 页 共 7 页 第二部分：操作系统第二部分操作系统（操作系统（共40分）一、单选题（单选题（每题 2 分，共10分）1. 下列有关进程的描述中，不正确的是【 】。(A)进程是资源拥有的基本单位，一个进程可以有多个线程(B) 进程因时间片用完而被暂停执行，该进程便由执行状态转变为阻塞状态(C) 进程通信的任务是实现在相互合作进程之间的信息交换(D)一个进程可以执行一个或几个程序，多个进程也可以执行同一个程序2. 【 】是未开启分页机制的CPU访问存储器内信息时所用的地址。(A)逻辑地址 (B) 相对地址(C) 物理地址 (D)基地址3. 下列有关文件组织管理的描述，不正确的是【 】。(A) 记录是对文件进行存取操作的单位，一个文件中诸记录的长度可以不等(B) 采用链接块方式分配的文件，它的物理块必须顺序排列(C) 创建一个文件时，可以分配连续的区域，也可以分配不连续的物理块(D) Hash结构文件的优点是能够实现物理块的动态分配和回收4. 从作业提交至系统开始，到作业完成时结束的这段时间称为【 】。(A)响应时间 (B) 调度时间(C) 作业时间 (D) 周转时间5. 下列有关操作系统中缓冲机制的说法，不正确的是【 】。(A) 增加对CPU的中断频率(B) 缓和CPU与I/O设备间速度不匹配的矛盾(C) 放宽对中断响应时间的限制(D) 提高CPU与I/O设备之间的并行性二、填空题（填空题（每空2分，共10分）1. 操作系统最基本的特征是_________和共享。2. 系统中有种资源，它们一次仅允许一个进程使用，这种资源称为_______。3. 在操作系统中_______是指把一个物理实体，变为若干逻辑上的对应物。 科目名称：计算机软件基础 第 4 页 共 7 页4. 程序装入存储空间时逻辑地址到物理地址的转换过程称为_______。5. 程序在一个短的时间内运行时，程序的执行仅限于某个部分；相应地，它所访问的存储空间也局限于某个区域，此现象是_______原理。三、问答题（问答题（每题 5分，共20分）1. 为什么要在操作系统中引入线程？线程具有哪些属性？2. 假设系统中有4个相同类型的资源被3个进程共享，每个进程最多需要2个资源。请问这个系统是否会发生死锁？并说明原因。3. 在段页式虚拟存储管理系统中，假设有如下段表结构信息。段号0 1 2 3 4 基地址219 2300 90 1327 1952 段长600 14 100 580 96 请回答下面5个逻辑地址的物理地址分别是多少？(1).0520 (2).111 (3).2800 (4).3480 (5).41564. 描述如下两种磁盘调度算法及其优缺点(1). 先来先服务 (FCFS) (2). 最短寻道时间优先 (SSTF) 第三部分：编译原理部分编译原理（编译原理（共40分）一、单选题（单选题（每题2分，共10分）1．编译程序是对【 】。 (A) 汇编程序的翻译 (C) 机器语言的执行 (B) 高级语言的解释执行(D) 高级语言的翻译2．词法分析的任务是【 】。(A) 识别单词 (B) 分析句子的含义 科目名称：计算机软件基础 第 5 页 共 7 页 (C) 识别句子 (D) 生成目标代码3．有一语法制导翻译如下所示S→bAb {print“1”} A→(B {print“2”} A→a {print“3”} B→Aa) {print“4”} 若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为【 】。(A) 32224441 (B) 34242421 (C) 12424243 (D) 34442212 4．过程的DISPLAY表中记录了【 】。(A) 过程的连接数据 (C) 过程的返回地址 (B) 过程的嵌套层次 (D) 过程的入口地址 5．编译程序中错误的局部化是指【 】。 (A) 把错误理解成局部的错误(B) 对错误在局部范围内纠正(C) 当发现错误时，跳过错误所在的语法单位继续分析下去(D) 当发现错误时立即停止编译，待用户纠正后再继续编译二、问答题（问答题（共30分）1．（4分）给出下述文法所对应的正规式： S→0S|S1|ε 科目名称：计算机软件基础 第 6 页 共 7 页 2．（4分）将文法G[A] 改写为等价的G′[A]，使G′[A]不含左递归和左公共因子。 G[A]： A→aAB1 | a B→Bb | d 3．（4分）将语句 if (A ∧ B) then while C>0 do C:=C+D;翻译成四元式。4．（10分）文法G[E] E→E+T∣T T→T*P∣P P→i （1） 构造该文法的优先关系表（不考虑语句括号#）,并证明此文法是否为算符优先文法。 （2） 构造该文法的优先函数。 （3） 试用算符优先分析法分析句子i+i*i。 5．（8分）运行时的DISPLAY表的内容是什么？它的作用是什么？如果不采用DISPLAY表，请说明其它一种实现方法。 科目名称：计算机软件基础 第 7 页 共 7页