第一部分：数据结构(共 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-1
6.若有 18 个元素的有序表存放在一维数组 A[19]中，第一个元素放 A[1]中，
现进行二分查找，则查找 A[3]的比较序列的下标依次为【】。
科目名称：计算机软件基础 第 1 页共 5 页
8.设有 6 个结点的无向图，该图至少应有【 】条边才能确保是一个连通图。
(A)5 (B)6 (C)7 (D)8
9.设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫 曼树中总共有【 】个空指针域。
(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m
10.设某棵二叉树的中序遍历序列为 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，3
2. 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字 62 时的比较次数并计算出查找成 功时的平均查找长度。
3.已知待散列的线性表为(36，15，40，63，22)，散列用的一维地址空间为[0..6]， 假定选用的散列函数是 H(K)= K mod 7，若发生冲突采用线性探查法处理，试：
(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|1B
A→1S|1
B→0S|0
2.将文法 G[S] 改写为等价的 G′[S]，使 G′[S]不含左递归和左公共因子。
G[S]： S→bSAe | bA
A→Ab | d
3.写出表达式(a+b*c)/(a+b)-d 的逆波兰表示及三元式序列。
三、已知文法 G[S]：(10 分)
S→MH|a
H→LSo|ε
K→dML|ε
L→eHf
M→K|bLM
判断 G 是否是 LL(1)文法，如果是，构造 LL(1)分析表。
四、过程参数的传递方式有几种?简述"传地址"和"传值"的实现原理。(8 分)
