2013中国科学院大学考研真题之计算机软件基础.pdf
中国科 学院 大学 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 190 75 194 768 559 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. 按行优先顺序存储一个下三角矩阵 A nn 的非零元素, 则计算非零元素 a ij (1 j i n)的地址的公式为 Loc(a ij ) =_ + 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. 设有以下三个函数: ( ) 1000 21 2 4 + + = n n n f , ( ) 3 4 500 15 n n n g + = , ( ) n n n n h log 500 5 . 3 + = 请判断以下断言正确与否: (1) f(n)是O(g(n) (2) h(n)是O(f(n) (3) g(n)是O(h(n) (4) h(n)是O(n 3.5 ) (5) h(n)是O(nlogn) 5. 一棵度为2 的树与一棵二叉树有何区别? 6. 证明: 一棵满k 叉树上的叶子结点数 0 n 和非叶子结点数 1 n 之间满足以下关系: ( ) 1 1 1 0 + = n k n 科目名称:计算机软件基础 第 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 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96 请回答下面 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) 分析句子的含义 科目名称:计算机软件基础 第 5 页 共 7 页 (C) 识别句子 (D) 生成目标代码 3 有一语法制导翻译如下所示: SbAb print“1” A(B print“2” Aa print“3” BAa) 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 分) 给出下述文 法所对应的正规式: S0S|S1| 科目名称:计算机软件基础 第 6 页 共 7 页 2 (4 分) 将文法GA 改写为等价的 GA,使 GA不含左递归和左公共因 子。 GA: AaAB1 | a BBb | d 3 (4 分)将语句 if (A B) then while C0 do C:=C+D; 翻 译成四元式。 4 (10 分) 文法GE EE+TT TT*PP Pi (1) 构造该文法的优先关系表 (不考虑语句括号#),并证明此文法是 否为算符优先文法。 (2) 构造该文法的优先函数。 (3) 试用算符优先分析法分析句子i+i*i。 5 (8 分) 运行时的 DISPLAY 表的内容 是什 么?它的作用是什么?如果不采用 DISPLAY 表,请说明其 它一种实现方法。 科目名称:计算机软件基础 第 7 页 共 7 页