5．简述进程的三种状态及其转化过程。
参考答案
第一章
一、选择题 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--; 三、判断题
√╳╳√√ ╳√╳╳╳
四、简答应用题 1.
BCDCB ╳╳√√╳ CBADD BABAB ╳√╳√√ DBBDC ╳
2.
1 2 3 4 5
k POS NUM 1 2 1 2 3 0 3 3 2 4 5 1 行号域 4 1 3 3 4 列号域 5 1 2 4 4 值域 4 4 3 6 5 3.
前序遍历：DEABC 中序遍历：EDBAC 后序遍历：DACBE 4.
A BCDFE
5.
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.
序号 关键字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 636182034
需要查找3次才能找到18 3.
冒泡法排序过程：
选择法排序过程：
原始： 12 6 第一趟：[6] 12 第二趟：[6 10] 第三趟：[6 10 第四趟：[6 10 第五趟：[6 10
插入法排序过程：
原始： [12] 第一趟：(6) [6 第二趟：(20) [6 第三趟：(18) [6 第四趟：(34) [6 第五趟：(10) [6
第四章
一、选择题
BACDC BBC 二、填空题 1. 软件
2. 高效地工作 3. 分时操作系统 4. 作业 5. 主存储器 6. 工作效率 7. 时间片
12666612121220181810182010183410202010343434原始序列第一趟第二趟第三趟20 18 34 10 20 18 34 10 20 18 34 12 18 34 20 18] 34 20 18 20] 34 6 20 18 34 10 12] 20 18 34 10 12 20] 18 34 10 12 18 20] 34 10 12 18 20 34] 10 10 12 18 20 34] 6610101212181820203434第四趟第五趟
12] 12 12
2016现代科技学院《软件技术基础》练习题+答案
