北京中国科学院大学2013年考研计算机软件基础真题.doc-资料库

北京中国科学院大学2013年考研计算机软件基础真题.doc.pdf-第1页.jpg

第1页 / 共6页

北京中国科学院大学2013年考研计算机软件基础真题.doc.pdf-第2页.jpg

第2页 / 共6页

北京中国科学院大学2013年考研计算机软件基础真题.doc.pdf-第3页.jpg

第3页 / 共6页

北京中国科学院大学2013年考研计算机软件基础真题.doc.pdf-第4页.jpg

第4页 / 共6页

北京中国科学院大学2013年考研计算机软件基础真题.doc.pdf-第5页.jpg

第5页 / 共6页

北京中国科学院大学2013年考研计算机软件基础真题.doc.pdf-第6页.jpg

第6页 / 共6页

（北京）中国科学院大学 2013 年考研计算机软件基础真题中国科学院大学 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 个结点后面插入一个新结点 4. 设某散列表的当前状态如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

该散列表的负载因子约为【】。 (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)的地址的公式为 Loc(aij) =______ + i*(i-1)/2 +(j-1)。 3. m 阶 B+树的根结点至多有______个子结点。 4. 能够成功完成拓扑排序的图一定是一个______。 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. 设有以下三个函数：请判断以下断言正确与否： (1) f(n)是 O(g(n)) (2) h(n)是 O(f(n)) (3) g(n)是 O(h(n)) (4) h(n)是 O (5) h(n)是 O(nlogn) 5. 一棵度为 2 的树与一棵二叉树有何区别？ 6. 证明：一棵满 k 叉树上的叶子结点数 n0 和非叶子结点数 n1 之间满足以下关系：第二部分：操作系统（共 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. 程序装入存储空间时逻辑地址到物理地址的转换过程称为_______。 5. 程序在一个短的时间内运行时，程序的执行仅限于某个部分；相应地，它所访问的存储空间也局限于某个区域，此现象是_______原理。三、问答题（每题 5 分，共 20 分） 1. 为什么要在操作系统中引入线程？线程具有哪些属性？ 2. 假设系统中有 4 个相同类型的资源被 3 个进程共享，每个进程最多需要 2 个资源。请问这个系统是否会发生死锁？并说明原因。 3. 在段页式虚拟存储管理系统中，假设有如下段表结构信息。

请回答下面 5 个逻辑地址的物理地址分别是多少？ (1).0520 (2).111 (3).2800 (4).3480 (5).4156 4. 描述如下两种磁盘调度算法及其优缺点： (1). 先来先服务 (FCFS) (2). 最短寻道时间优先 (SSTF) 第三部分：编译原理（共 40 分）一、单选题（每题 2 分，共 10 分） 1．编译程序是对【】。 (A) 汇编程序的翻译 (B) 高级语言的解释执行 (C) 机器语言的执行 (D) 高级语言的翻译 2．词法分析的任务是【】。 (A) 识别单词 (B) 分析句子的含义 (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) 过程的连接数据 (B) 过程的嵌套层次

(C) 过程的返回地址 (D) 过程的入口地址 5．编译程序中错误的局部化是指【】。 (A) 把错误理解成局部的错误 (B) 对错误在局部范围内纠正 (C) 当发现错误时，跳过错误所在的语法单位继续分析下去 (D) 当发现错误时立即停止编译，待用户纠正后再继续编译二、问答题（共 30 分） 1．（4 分）给出下述文法所对应的正规式： S→0S|S1|ε 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 表，请说明其它一种实现方法。

资料库

北京中国科学院大学2013年考研计算机软件基础真题.doc

相关推荐

考研

热门标签

最新资料