中国科学院大学2015年招收攻读硕士学位研究生入学统一考试试题：科目名称：计算机软件基础

中国科学院大学

2015年招收攻读硕士学位研究生入学统一考试试题

科目名称：计算机软件基础

考生须知：

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. 按行优先顺序存储一个下三角矩阵Ann的非零元素，则计算非零元素aij(1 ?j ? i ? n)的地址的公式为Loc(aij) =______ + 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，g?n??15n4?500n3，h?n??500n3.5?nlogn 请判断以下断言正确与否：

(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和非叶子结点数n1之间满足以下关系：

n0??k?1?n1?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).4156 4. 描述如下两种磁盘调度算法及其优缺点：

(1). 先来先服务 (FCFS) (2). 最短寻道时间优先 (SSTF)

第三部分：编译原理（共40分）

一、单选题（每题2分，共10分） 1．编译程序是对【 】。 (A) 汇编程序的翻译 (C) 机器语言的执行

(B) 高级语言的解释执行 (D) 高级语言的翻译

2．词法分析的任务是【 】。

(A) 识别单词 (B) 分析句子的含义

科目名称：计算机软件基础 第 5 页 共 7 页

本文来源：https://www.bwwdw.com/article/5lbd.html