参考答案
第一章
一、选择题 DADDC 二、填空题
1.列举法、归纳法、递推法、递归法、减半递推法 2.可行性、确定性 3. O(n) 4. O(n2) 5. O(log2n)
6. n、n(n+1)/2、O(n2) 7. 1、log2n、n、n2、2n 三、判断题 ╳
第二章
一、选择题
BDCDBD CABCA DBBBD CADB
二、填空题
1.顺序、链式、索引、散列 2.7、59 3. 指针
4. 后进先出、先进先出 5. 栈 6. 队尾
7. 加1、减1、c 8. 层次、根 9. 2i-1 10. 2k-1
11. 顺序、链式 12. 根
13. 主对角线
14. v.elem[k+1] = v.elem[k]; 15. v.last--; 16. s.top++; 17. s.top--; 三、判断题
√╳╳√√ ╳√╳╳╳
四、简答应用题
BCDCB ╳╳√√╳
CBADD BABAB ╳√╳√√ DBBDC ╳ 17
1.
2.
行号域 列号域 值域 1 4 5 4 2 1 1 4 3 3 2 3 4 3 4 6 5 4 4 5
k 1 2 3 4 POS 2 3 3 5 NUM 1 0 2 1 3.
前序遍历：DEABC 中序遍历：EDBAC 后序遍历：DACBE 4.
A BECDF
5.
18
0110001011?1?110011100?1R?10010 V?11?100110001000?1?113812? 113120?18?1?10
6. 答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。
7. 答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。
8. 答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。
9. 答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。 10. 答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。 11. 答：int number(Linkedlist *head) {//计算单链表中结点的个数 p=head—>next； i=0；
while(p!=NULL) {i++；p=p->next；} return i； }
12. 答：前序遍历序列：ABCDEFGH
第三章
一、选择题
CCBBB CBCAC BDBD 二、填空题
1. 确定元素所在的块、在块内查找元素、分块 2. 大、小 3. 递增
4. 元素个数、输入序列 5. 有序、顺序存储 6. 内部、外部 7. v.elem[i]==k
8. i=v.last、v.elem[i]!=k
9. low<=high、x==v.elem[mid]、v.elem[mid]>x、low =mid + 1; 10. j=i+1、k=j; 三、判断题 √╳╳
四、简答应用题 1.
19
序号 关键字k 冲突次数 1 3 0 2 6 0 3 7 1 4 12 0 5 6 7 8 9 10 11 12 26 25 24 38 0 1 2 0 2.
12 6203618
需要查找3次才能找到18 3.
冒泡法排序过程：
12666612121220181810182010183410202010343434原始序列第一趟第二趟第三趟选择法排序过程：
原始： 12 6 20 18 34 10 第一趟：[6] 12 20 18 34 10 第二趟：[6 10] 20 18 34 12 第三趟：[6 10 12] 18 34 20 第四趟：[6 10 12 18] 34 20 第五趟：[6 10 12 18 20] 34
插入法排序过程：
原始： [12] 6 20 18 34 10 第一趟：(6) [6 12] 20 18 34 10 第二趟：(20) [6 12 20] 18 34 10 第三趟：(18) [6 12 18 20] 34 10 第四趟：(34) [6 12 18 20 34] 10 第五趟：(10) [6 10 12 18 20 34]
第四章
一、选择题
BACDC BBC 二、填空题
34
6610101212181820203434第四趟第五趟
20
1. 软件
2. 高效地工作 3. 分时操作系统 4. 作业 5. 主存储器 6. 工作效率 7. 时间片 8. 交互性 9. 死锁
10. 互斥、同步 三、简答题
1、答：计算机系统的资源包括两大类:硬件资源和软件资源。硬件资源主要有中央处理器、主存储器、辅助存储器和各种输入输出设备。软件资源有编译程序、编辑程序等各种程序以及有关数据。 2、答：操作系统是一种系统程序，其目的是为其他程序的执行提供一个良好的环境。它有两个主要设计目标：一是使计算机系统使用方便，二是使计算机系统能高效地工作。
3、答：从资源管理的观点出发，操作系统具有五大功能：(1)处理器管理。为用户合理分配处理器时间，提高处理器工作效率。(2)存储管理。为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率。(3)文件管理。管理用户信息，为用户提供按文件名存取功能，合理分配文件的存储空间。(4)设备管现。负责设备的分配、启动以及虚拟设备的实现等.(5)作业管理。实现作业调度和控制。
4、答：①．进程是动态概念，程序是静态概念；
②．进程的存在是暂时的，而程序的存在是永久的； ③．进程是程序的执行过程，进程的组成包括程序； ④．一个程序可能对应多个进程； ⑤．一个进程可以包含多个程序。
5、答：运行状态：处于该状态下的进程正占据着CPU。
就绪状态：该状态下的进程已获得了除CPU外的一切所需资源，只是因为缺少CPU而不能
运行，一旦获得CPU，就立即转入运行状态投入运行。
等待状态：一个进程正在等待某一事件（如等待某输入操作的完成）的发生而暂时停止执
行。此时即使把CPU分配给它，该进程也不能运行，即处于等待状态，又称为阻塞状态或封锁状态。
21
