软件技术基础总复习题及参考答案

参考答案：

特点：并发性 共享性 虚拟性

功能：处理器管理 存储器管理 作业管理 设备管理 文件管理

24、 比较进程与程序的异同。

参考答案： 程序是静态的，而进程是动态的。

进程是程序的执行过程，因而进程是有生命周期的，有诞生，也有消亡。因此，程序 的存在是永久的，而进程的存在是暂时的，它动态地产生和消亡。一个进程可以执 行一个或几个程序，一个程序亦可以构成多个进程。

四、 综合题

1、 以下为单链表的删除运算，请分析算法 void delete_lklist(lklist head,int i)

{

p=find_lklist(head,i-1);

if( (p!=NULL)&&(p->next!=NULL) ) // ① {

q= p->next ; p->next=p->next; free(q); }

else error(“不存在第 i 个结点”)

}

（1） 请在 处填上正确的语句； （2） 解释①处语句的含义。

参考答案：

（1）见上； （2）判断第 i-1 个和第 i 个结点是否为空。

2、 已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ, 中序遍历的结果是

EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。 参考答案：

根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图：

A

B F

E

C G

D H J 这棵二叉树的后序遍历序列为：

EDCBIHJGFA

I

3、 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分

别进行深度，广度优先遍历的结果。

1

2

3 4

5

参考答案：

1 2 3 4 5 2 1 1 2 3 3 3 2 5 4 4 5

深度优先遍历：12534 广度优先遍历：12354

4、 已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写

出冒泡排序每趟的结果。

参考答案： 冒泡排序的每趟的结果：

初始键值序列 [12 5 9 20 6 31 24]

第一趟之后 [5 9 12 6 20 24] 31 第二趟之后 [5 9 6 12 20] 24 31 第三趟之后 [5 6 9 12] 20 24 31 第四趟之后 5 6 9 12 20 24 31

5、 以下为单链表的插入运算，请分析算法

void insert_lklist(lklist head,datatype x,int i)

/*在表 head 的第 i 个位置上插入一个以 x 为值的新结点*/ {

p=find_lklist(head,i-1);

if(p==NULL) error(“不存在第 i 个位置”)； else { s= malloc(sizeof(*p)) ;s->data=x; //①

s->next= p->next ; p->next=s; }

}

（1） 请在 处填上正确的语句； （2） 解释①处语句的含义。

参考答案：

（1） 见上

（2） 分配链表结点大小的内存，并将指针赋给 s

6、 对于如下图 A：

（1）写出按深度优先搜索结果 （2）写出按广度优先搜索结果

V2

v1

V6

V3

V4 V7

参考答案：

（1）V1、V2、V3、V5、V4、V6、V7 （2）V1、V2、V6、V3、V4、V7、V5

V5

图 A

7、 有一棵树如下图 B 所示，回答下列问题：

（1）这棵树的根结点是（ ）； （2）这棵树的叶子结点是（ ） （3）结点 C 的度是（ ），这棵树的度是（ （4）结点 C 的子女是（ ） （5）结点 C 的父结点是（ ）

）

图 B