《软件技术基础》练习题
太原理工大学现代科技学院2016
1
第一章 算法
一、选择题
1. 算法的复杂度包括【 】。
A、时间复杂度 B、空间复杂度
C、时间及空间复杂度 D、以上都不对
2. 若x在长度为n的无序线性顺序表中的概率为50%，则在该表中查找x的平均查找次数（平均性态分析）为【 】。
A、(n*3+1)/4 B、(n-1)/2 C、(n+1)/2 D、(n+1)*n/2
3. 若x在长度为n的无序线性顺序表中的概率为50%，则在该表中查找x的最坏情况分析为【 】。
A、n/2 B、(n-1)/2 C、(n+1)/2 D、n
4. 已知基本运算执行次数与n的关系，则下列哪个时间复杂度最大：【 】。
A. f(n) = 1 B. f(n) = 2n - 1
C. f(n) = 10000n+10000 D. f(n) = n2-10000
5. 算法分析的目的是【 】。
A．找出数据结构的合理性
B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性
二、填空题
1. 常用算法包括_________、_________、_________、_________、_________和回溯法。 2. 算法的基本特征有_________、_________、有穷性、输入和输出。 3. 下列程序段的时间复杂度是____。
for (i=1；i<=n；i++) A[i，i]=0；
4. 下列程序段的时间复杂度是____ s=0；
for(i=1；i<=2n；i++)
for(j=1；j<=n；j++) s=s+B[i][j]； sum=s；
5. 下列程序段的时间复杂度是____ i=1；
2
while (i<=n) i=i*2；
6. 在下面的程序段中，s= s + p；语句的执行次数为_________，p= p×j语句的执行次数为_________ ，该程序段的时间复杂度为________ 。 int i=0, s=0, p=1; while( ++i<=n ) { for(j=1; j<=i; j++ ) p = p×j; s = s + p; }
7. 常见时间复杂度的量级有：常数阶O(_________)、对数阶O(_________)、线性阶O(_________)、平方阶O(_________)和指数阶O(_________)。
三、判断题
1. 算法和程序没有区别，所以在数据结构中二者是通用的。
3
第二章 基本数据结构及其运算
一、选择题
1. 数据结构的逻辑结构被形式地定义为(D，R)，其中D是【 （1） 】的有限集合，R是D上【 （2） 】的有限集合。
(1) A．算法 B．数据元素 C．数据操作 D．逻辑结构 (2) A．操作 B．映像 C．存储 D．关系 2. 在数据结构中，从逻辑上可以把数据结构分为【 】。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构
3 设进栈的输入序列是1,2,3,4，则【 】不可能是其出栈序列。
A. 1243 B. 2134 C. 1432 D. 4312
4. 设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是【 】。 A．2 B．3 C．5 D．6
5. 线性表若采用链表存储结构，要求内存中可用存储单元的地址【 】。
A．必须是连续的 B．部分必须是连续的 C．一定是不连续的 D．连续不连续都可以
6. 有如下定义struct Snode { int data; struct Snode *next; } *p, *q; 则将新结点q插入到单链表的p结点之后，下面的操作【 】是正确的。
A. q=p-> next; p-> next =q-> next; B. p-> next =q-> next; q=p-> next;
C. q-> next =p-> next; p-> next =q; D. p-> next =q; q-> next =p-> next;
7. 一个线性顺序表第一个元素的存储地址是2000，每个元素长度为4个字节，则第3个元素的起始存储地址为【 】。
A. 2008 B. 2000 C. 2004 D. 2012
8. 下列关于二叉树的叙述中，正确的是【 】。
A. 叶子结点总是比度为2的结点少一个 B. 叶子结点总是比度为2的结点多一个 C. 叶子结点数是度为2的结点数的两倍
D. 度为2的结点数是度为1的结点数的两倍
9. 某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是【 】。
A. 10 B. 8 C. 6 D. 4
10. 一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为【 】。
A. 16 B. 10 C. 6 D. 4
11. 某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层) 【 】。
A. 3 B. 4 C. 6 D. 7
12. 某二叉树有7个度为2的结点，则该二叉树中的叶子结点数是【 】
A.10 B.8 C.4 D.6 13. 一棵深度为k的满二叉树中结点的个数是【 】
A. 2k B. 2k -1 C. 2k-1 D. 2k-1-1
4
14. 在以下的叙述中，正确的是【 】。
A．线性表的线性存储结构优于链式存储结构
B．二维数组是它的每个数据元素为一个线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 15. 以下说法正确的是【 】。
A．数据元素是数据的最小单位 B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合 D．数据结构是带有结构的数据元素的集合
16. 线性表L=(a1，a2，?，ai，?，an)，下列说法正确的是【 】。
A．每个元素都有一个直接前驱和直接后继 B．线性表中至少要有一个元素
C．表中诸元素的排列顺序必须是由小到大或由大到小的
D．除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 17. 对于顺序线性表的优缺点，以下说法错误的是【 】。
A．无需为表示结点间的逻辑关系而增加额外的存储空间 B．可以方便地随机存取表中的任一结点 C．插入和删除操作较方便
D．由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
18. 在含有n个结点的顺序存储的线性表中，在任一结点i前插入一个结点所需移动结点的次数为【 】。
A．n/2 B．i C．n-i D．n-i+1
19. 在含有n个结点的顺序存储的线性表中，删除第i个结点所需移动结点的次数为【 】。 A．n/2 B．i C．n-i D．n-i+1
20. 在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为【 】。
A．n B．n/2 C．(n-1)/2 D．(n+1)/2
21. 在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为【 】。 A．n B．n/2 C．(n-1)/2 D．(n+1)/2 22. 带头结点的单链表为空的条件是【 】。
A．head=NULL B．head->next=NULL C．head->next=head D．head!=NULL 23. 在一个单链表中，若删除*p结点的后继结点，则执行【 】。
A．q=p->next；p->next=q->next；free(q)；
B．p=p->next；p->next=p->next->next；free(p)； C．p->next=p->next；free(p->next)； D．p=p->next->next；free(p->next)； 24. 循环链表的主要优点是【 】。
A．不再需要头指针了
B．已知某个结点的位置后，容易找到它的直接前驱 C．在进行插入、删除操作时，能更好地保证链表不断开 D．从表中任一结点出发都能扫描到整个链表
25. 在线性表的下列存储结构中，读取元素花费时间最少的是【 】。
A．单链表 B．双链表 C．循环链表 D．顺序表
26. 设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为a2,a4,a3,a6,a5,a1，则栈S的容量至少应该为【 】。 A．2 B．3 C．5 D．6
27. 二维数组A[11，6]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[0，0]的存储地址是1000，则A[8，4]的存储地址是【 】。
5
A．1208 B．1212 C．1368 D．1364 28. 对矩阵压缩存储是为了【 】。
A．方便运算 B．节省空间 C．方便存储 D．提高运算速度 29. 以下说法错误的是【 】。
A．树形结构的特点是一个结点可以有多个直接前驱 B．线性结构中的一个结点至多只有一个直接后继 C．二叉树与树是两种不同的数据结构
D．树(及一切树形结构)是一种“分支层次’结构 30. 以下说法错误的是【 】。
A．二叉树可以是空集
B．二叉树的任一结点都有两棵子树 C．二叉树与树具有相同的树形结构
D、二叉树中任一结点的两棵子树有次序之分
31. 一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递减序列。
A．前序 B．中序 C．后序 D．层次
32. 对含有【 】个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A．0 B．1 C．2 D．不存在这样的二叉树
33. 已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是【 】。 A．acbed B．baedc C．dceab D．cedba
34. 某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是【 】。
A．bdgcefha B．gdbecfha C．bdgechfa D．gdbehfca 35. 在图6-2中的二叉树中，【 】不是完全二叉树。
36. 树最适合用来表示【 】。
A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据
37. 在计算递归函数时，如不使用递归过程，则一般情况下必须借助于【 】数据结构。 A．栈 B．树 C．双向队列 D．顺序表
38. 对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【 】。 A．N B．(N-1)*(N-1) C．N-1 D．N*N 39. 以下说法错误的是【 】。
A．用邻接矩阵法存储图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关
B．邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用 C．存储无向图的邻接矩阵是对称的，因此也可以只存储邻接矩阵的下(或上)三角部分 D．用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为0即可
6
二、填空题
1. 通常，数据在计算机中的存储结构有_____存储结构、______存储结构、______存储结构和_____存储结构四种基本存储结构。
2. 设循环队列的容量为70（序号为1~70），现经过一系列的入队与退队运算后，有： ①. front = 14，rear = 21，循环队列中有______个元素 ②. front = 23，rear = 12，循环队列中有______个元素
3. 单链表表示法的基本思想是用______表示结点间的逻辑关系。 4. 栈的逻辑特点是______，队列的逻辑特点是______ 5. ______可以作为实现递归函数调用的一种数据结构。 6. 在队列中，新插入的结点只能添加到______。
7. 设用一维数组A[n]来表示一个栈，令A[0]为栈底。用整型变量t来指示当前栈顶的位置，A[t]为栈顶元素。往栈中压入一个新元素时，变量t的值______，从栈中弹出一个元素时，变量t的值______。设空栈时，输入序列a，b，c经过push，pop，push，push，pop操作后，从栈中弹出的元素是_____。
8. 树(及一切树形结构)是一种_____结构。在树中，______结点没有直接前驱。 9. 二叉树第i(i>0)层上至多有______个结点。 10. 深度为k(k>0)的二叉树至多有______个结点。
11. 二叉树通常有_______存储结构和_____存储结构两类存储结构。 12. 对二叉链表的访问只能从______指针开始。
13. 对无向图，其邻接矩阵是一个关于_______对称的矩阵。
14. 请填空完成线性表在顺序存储下的插入运算程序：在线性表v中第i个位置插入值为x的元素 struct sqlist
{ int elem[MAXSIZE]; int last;
};
void insert(sqlist v, int i, int x) { int k; if (i<1 || i>v.last+1) printf( ''插入位置不合适！\\n'' ); else if (v.last>= MAXSIZE -1) printf( ''线性表已满！\\n'' ); else { for( k = v.last; k >= i; k-- ) _______________________ v.elem[i] = x; v.last++; }
}
15. 请填空完成线性表在顺序存储下的删除运算程序：在线性表v中删除第i个位置的元素
struct sqlist { int elem[MAXSIZE]; int last;
};
7
void delete(sqlist v, int i) { int k; if (i<1 || i>v.last)
printf( ''删除位置不合适！\\n'' ); else { for( k = i+1; k <= v.last; k++ ) v.elem[k-1] = v.elem[k]; _______________________ } }
16. 请填空完成栈在顺序存储下的入栈运算程序：将值为x的元素入栈s struct stack
{ int sData[MAXSIZE];
int top; //栈顶指针，指向当前栈顶的位置 };
void push(struct stack s, int x) //入栈运算 { if (s.top == MAXSIZE-1) { printf(''栈满溢出 \\n''); } else { _______________________ s.sData[top]=x; } }
17. 请填空完成栈在顺序存储下的出栈运算程序：栈s出栈，并将出栈元素作为函数返回值返回struct stack
{ int sData[MAXSIZE];
int top; //栈顶指针，指向当前栈顶的位置 };
int pop(struct stack s) //退（出）栈运算 { int x; if (s.top == -1) { printf(''栈空溢出 \\n''); exit(1); } else { x=s.sData[top]; _______________________ } return x; }
8
三、判断题
1．顺序存储的线性表可以随机存取。
2．顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。
3．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 4．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 5．在单链表中，可以从头结点开始查找任何一个元素。 6．线性表的链式存储结构优于顺序存储结构。
7．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。
8．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
9．顺序存储方式只能用于存储线性结构。 10．循环队列中元素个数为rear-front。
11．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2． 12．若以链表作为栈的存储结构，则入栈需要判断栈是否满． 13．数组是同类型值的集合。 14．数组是一组连续的内存单元。
15．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
16．插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。 17．使用三元组表示稀疏矩阵的元素，有时并不能节省存储空间。 18．二叉树是树的特殊形式。
19．树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
20．用邻接矩阵法存储图时，所占用的存储空间大小仅与图中结点个数有关。 21．存储有向图的邻接矩阵一定是对称的。
四、简答应用题
1. 有三个元素的进栈序列是1，2，3，举出此三个元素可能的出栈序列，并写出相应的进栈和出栈操作序列 (假设以I和O表示进栈和出栈操作)。 2. 试将下列稀疏矩阵A用三元组（三列二维表格）形式来表示，并写出对应的辅助向量POS和NUM。
40A?0000300000006500 00
3. 试写出对下图所示的二叉树分别按前序、中序和后序遍历时得到的结点序列。
E DA
BC
9
4. 画出下图所示的树对应的二叉树。
A BECFD
5. 请写出下图对应的关联矩阵R及求值矩阵V，结点A,B,C,D,E分别用1,2,3,4,5编号
10A811 B13ED12C
6. 逻辑结构与存储结构是什么关系？
7. 描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。 8. 何时选用顺序表，何时选用链表作为线性表的存储结构为宜？
9. 如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？
10. 若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？
11. 设计算法并写出程序，实现“计算带头结点的单链表的结点个数”。
12. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。
10
第三章 查找与排序
一、选择题
1. 对采用折半查找法进行查找操作的查找表，要求按【 】方式进行存储。
A．顺序存储 B．链式存储
C．顺序存储且结点按关键字有序 D．链式存储且结点按关键字有序
2. 设有序表的关键字序列为(1，4，6，10，18，35，42，53，67，71，78，84，92，99)，当用折半查找法查找键值为35的结点时，经【 】次比较后查找成功。
A．2 B．3 C．4 D．6 3. 分块查找的时间性能【 】。
A．低于折半查找
B．高于顺序查找而低于折半查找 C．高于顺序查找
D．低于顺序查找而高于折半查找
4. 设哈希函数为H(key)=key％7，一组关键字为(37，21，9，20，30，19，46)，哈希表T的地址空间为0..6，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为【 】。 A． 0 1 2 3 4 5 6 21 20 37 9 46 30 19 B． 0 1 2 3 4 5 6 21 46 37 9 30 19 20 C． 0 1 2 3 4 5 6 21 19 9 37 30 46 20 D．0 1 2 3 4 5 6 20 37 30 21 46 19 9
5. 设有一个用线性探测法解决冲突得到的哈希表：
0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14
哈希函数为H(key)=key％11，若要查找元素14，探测的次数是【 】。 A．3 B．6 C．7 D．9
6. 在哈希函数H(key)=key％m中，一般来讲，m应取【 】。
A．奇数 B．偶数 C．素数 D．充分大的数 7. 以下说法错误的是【 】。
A．哈希法存储的基本思想是由关键字的值决定数据的存储地址 B．哈希表的结点中只包含数据元素自身的信息，不包含任何指针 C．哈希表的基本思想与顺序查找、对分查找和分块查找都不同
D．哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法
8. 在关键字随机分布的情况下，用二叉排序树的方法进行查找，其平均查找长度与【 】查找方法量级相当。
A．分块 B．顺序 C．折半 D．散列
9. 在具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为【 】。
2
A．O(n) B．O(1) C．O(log2n) D．O(n) 10. 哈希表的平均查找长度( )。
A．与处理冲突的方法有关而与表的长度无关
11
B．与处理冲突的方法无关而与表的长度有关 C．与处理冲突的方法有关且与表的长度有关 D．与处理冲突的方法无关且与表的长度无关
11. 有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列【 】输入序列。
A．45，12，49，6，40，56，32 B．40，12，6，32，49，45，56 C．6，12，32，40，45，49，56 D．32，12，6，40，45，56，49
12. 在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为【 】。 A．n B．log2n C．(h+1)／2 D．h
13. 【 】方法是从未排序序列中依次取出元素与已经排序序列中的元素进行比较，将其放人已经排序序列的正确位置上。
A．双向冒泡排序 B．插入排序 C．冒泡排序 D．选择排序
14. 【 】方法是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。 A．双向冒泡排序 B．插入排序 C．冒泡排序 D．选择排序
二、填空题
1．索引顺序表上的查找分两个阶段：一、______________；二、____________。该查找方法称为________查找。
2．二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值___于其左孩子(及其子孙)的键值且____于其右孩子(及其子孙)的键值。
3．中序遍历一棵二叉排序树所得到的结点访问序列是键值的_____序列。
4．二叉排序树上的查找长度不仅与______有关，也与二叉排序树的________有关。
5．折半查找方法仅适用于这样的表：表中的记录必须______，其存储结构必须是_______。 6．按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 7．请填空完成顺序查找算法程序：在线性表v中查找值为k的元素 struct sqlist {
int elem[MAXSIZE]; int last; };
int seqsearch (struct sqlist v, int k) { int i;
for(i=1;i<=v.last;i++) if(______________) return i; /*查找成功，返回被查元素在表中相对位置*/ return 0; /*查找失败，返回0*/ }
8．请填空完成改进型的顺序查找算法程序：在线性表v中查找值为k的元素 struct sqlist {
int elem[MAXSIZE]; int last; };
int seqsearch (struct sqlist v, int k) { int i;
12
v.elem[0]=k; _____________
while(_____________) i--;
return i; /*返回被查元素在表中相对位置，0为失败，其他为成功*/ }
9. 请填空完成对分查找算法程序：在线性表v中查找值为x的元素 struct sqlist {
int elem[MAXSIZE]; int last; };
int search (struct sqlist v, int x ) { int low, high, mid; low = 1; high = v.last; while (_____________)
{ mid = ( low + high )/2; //中间位置元素下标 if (_____________)
return mid; //返回被查元素在表中相对位置 if (_____________)
high=mid - 1; //取前半部分 else
_____________ //取后半部分 }
return (-1); //查找失败，返回-1 }
10. 请填空完成选择排序算法程序：在具有n个元素的线性表R按关键字进行排序struct record {
int key;
int otheritem; };
void selectsort(struct record R[],int n)
{ /*注意待排记录放在R[1]到R[n]中*/ int i,j,k; struct record temp; for(i=1;i 13 三、判断题 1．分块查找方法的平均查找长度低于顺序查找，高于折半查找。 2．在任一二叉排序树上查找某个结点的查找时间都小于用顺序查找法查找同样结点的线性表的查找时间。 3．虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的。 四、简答应用题 1. 将关键字序列{26,25,3,38, 6,7,12,24}依次填入长度为n=12的线性哈希表中，哈希码为i=INT(k / 4) + 1，并指出各关键字元素在插入过程中的冲突次数。 2. 依次输入以下元素序列：12,6,3,20,18,34,6，请按照输入的顺序构造一棵二叉排序树，并计算出要在这棵二叉排序树中查找18，需要比较多少次？ 3. 有如下序列：12,6,20,18,34,10，请分别写出用冒泡法、选择法、插入法对该序列进行排序的过程，并作出适当的标示。 14 第四章 资源管理技术 一、选择题 1．操作系统是计算机系统的一种【 】。 A．应用软件 B．系统软件 c．通用软件 D．工具软件 2．允许多个用户以交互方式使用计算机的操作系统是【 】。 A．分时操作系统 B．批处理单道系统 C．实时操作系统 D．批处理多道系统 3．下列系统中【 】是实时系统。 A．计算机图像处理系统 B．办公自动化系统 C．化学反应堆控制系统 D．计算机辅助设计系统 4． 操作系统是一种系统软件，它【 】。 A．控制程序的执行 B．管理计算机系统的资源 C．方便用户使用计算机 D．管理计算机系统的资源和控制程序的执行 5． 实时操作系统对可靠性和安全性要求极高，它【 】。 A．十分注重系统资源的利用率 B．不强调响应速度 C．不强求系统资源的利用率 D．不必向用户反馈信息 6． 【 】为用户分配主存空间，保护主存中的程序和数据不被破坏，提高主存空间的利用率。 A．处理器管理 B．存储管理 C．文件管理 D．作业管理 7． 财务管理软件是一种专用程序,它属于【 】 A．系统软件 B．应用软件 C．接口软件 D．支援软件 8． 在多道程序设计技术的计算机系统中，中央处理器【 】。 A．只能被一个程序占用 B．可以被多个程序同时占用 C．可以被多个程序交替占用 D．可以被操作系统和另一个程序同时占用 二、填空题 1．计算机是由硬件系统和_______系统组成。 2．使计算机系统使用方便和______是操作系统的两个主要设计目标。 3．批处理操作系统、____________和实时操作系统是基本的操作系统。 4．用户要求计算机系统中进行处理的一个计算机问题称为________。 5．在多道操作系统控制下，允许多个作业同时装入________，使中央处理器轮流地执行各个作业。 6．批处理操作系统提高了计算机系统的_________，但在作业执行时用户不能直接干预作业的执行。 7．在分时系统中，每个终端用户每次可以使用一个由_______规定的CPU时间。 8．分时系统具有同时性、独立性、及时性和________等特点。 9．若干个进程均因互相等待对方所占有的资源而无限地等待，使计算机系统无法继续正常运行的现象，称之为________。 10．当多个进程需要对系统中的同一个数据块进行操作时，进程之间常用的通信方式有两种：当多个进程共享数据块或其他排他性使用的资源时，不能同时进入存取或使用，这种称为_________；进程之间为了合作完成一个任务，而需要互相等待和互相交换信息的相互制约关系称为_________。 三、简答题 1．计算机系统的资源包括哪些? 2．为计算机设计操作系统要达到什么目的?设计时应考虑哪些目标? 3．简述操作系统的五大功能。 15 4．简述程序和进程的区别。 5．简述进程的三种状态及其转化过程。 16 参考答案 第一章 一、选择题 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