计算机软件基础（二） 习题答案

《计算机软件基础（二）》习题解答

第1章 概论复习题答案

1． 怎样的计算机被称为裸机？什么是虚拟计算机？

【解答】：对于一台只有硬件构成（通常包括：中央处理器cpu，储存器，输入和输出设备），而没有安装任何软件的计算机被称为裸机。而虚拟计算机则是指以硬件为物质基础，加装软件后的扩充后的计算机系统。

2． 计算机软件资源的作用如何？在你使用的计算机上有那些软件资源？

【解答】：计算机软件资源的作用是只有在软件资源的支持下，用户所使用的计算机才能极大程度上满足用户需要的虚拟计算机。软件资源有：汇编程序；各种高级语言；各种语言的解释或编译程序；各种标准程序库；操作系统；数据库系统软件；计算机网络软件；各种应用软件等。

3． 汇编语言和高级语言有什么不同？

【解答】：汇编语言是面向机器的语言，即不同型号的计算机的汇编语言是各不相同的，进行程序设计时必须了解所使用的计算机的结构性能和指令系统，而且编好的程序也只是针对一类机器，不能通用。高级语言是面对过程的语言，用户不必了解具体机器的细节就能编写程序，方便了程序的设计，提高了效率，同时也便于人们的交流。

4． 我们知道计算机只能执行机器指令，为什么它能运行汇编语言和高级语言编写的程序？

【解答】：计算机之所以能运行汇编语言编写的程序是因为计算机系统中装有汇编程序，汇编程序的作用是将源程序翻译成用机器语言组成的目标程序，从而计算机能运行汇编语言编写的程序。计算机之所以能运行高级语言编写的程序是因为计算机系统中装有解释程序或编译程序，它们将用高级语言编写的程序翻译成用机器语言组成的目标程序，从而计算机能运行高级语言编写的程序。

5． 你学习过那些高级语言?试分析它们的特点和适用的范围？

【解答】：fortran语言主要用于科学和工程计算；pascal语言则具有良好的程序结构，cobol语言则是面向事务处理的；lisp语言是人工智能语言；c语言则是通用的程序设计语言；c＋＋语言是面向对象的程序设计语言。

6．计算机软件的定义是什么？ 【解答】：计算机软件是指：计算机程序，实现程序功能所采用的方法，规则以及相关联

的文档和在机器上运行它所需要的数据。

7． 操作系统的作用是什么？

【解答】：操作系统控制和管理计算机的硬件、软件资源，实现对处理机，存储器，I/O设备，文件等四类资源的管理，同时操作系统还作为用户和计算机系统之间的接口，方便了人机交互。

1

8． 计算机操作系统在发展中经历了那些阶段？试简述它们的特点?

【解答】：主要经历了：手工操作阶段、成批处理系统阶段、执行程序阶段、多道程序系统和分时系统阶段。手工操作阶段的特点：计算机的全部资源归一个用户的一个程序独占操作过程有人工来干预。成批处理系统阶段：相对于手工操作阶段，它提高了计算机资源的利用率和增强了系统的处理能力，但由于处理机和I/O设备是串行工作的，大部分时间被消耗在输入输出上，处理机的大部分时间处于等待状态，故处理机和I/O设备的速度不匹配的矛盾成为进一步提高计算机的效率的关键。执行程序阶段：使系统实现了模块化结构，易于设计、修改和扩充，但由于计算机本身的顺序性，计算机并不能完全消除对外设传输的等待。多道程序系统：它需要一个调度算法来解决cpu的分配问题，需要有一个储存管理程序来解决多道程序在内存中的定位，分配和免遭破坏，需要有一个设备管理程序来解决外设的分配，释放和信息交换，此外还需要有一个文件管理程序来解决以文件形式存放于外存中的程序和数据。分时系统阶段：分时系统阶段采用划分时间片的方法来接受和处理各个用户从终端输入的命令，由于计算机运行的高速性和并行性，使每个用户感觉不到别的用户的存在，好像独占整台机器。

9． 计算机应用软件有那些？

【解答】：主要有以下三大领域：事务处理软件，工程和科学计算软件，实时应用软件。随着计算机技术的发展一些新的领域异军突起，如：嵌入式应用软件，微型机工具软件，人工智能软件。

2

第2章 数据结构复习题答案

一、选择题

1．线性表L在 情况下适用于使用链式结构实现。 （A）：需经常修改L中的结点值 ；（B）：需不断对L进行删除和插入； （C）： L中含有大量的结点； （D）： L 中结点结构复杂； 【答案】：应选B．

2．线性表在采用链表存储时其地址 。 （A）： 必须是连续的； （B）：部分地址是连续的； （C）：一定不是连续的； （D）：连续不连续都可以； 【答案】：应选D．

3．数组Q[n] 用来表示一个循环队列，f为当前队列头元素的前一个位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为 。 （A）：r-f ；（B）： (n+f-r)%n ；（C）： n+r-f ；（D）：(n+r-f)%n ； 【答案】：应选D．

4．若入栈序列为1，2，3，4，在入栈的过程中允许出栈，则 不可能是一个出栈序列。 （A）：1，4，3，2； （B）： 2，3，4，1；（C）：3，1，4，2 ；（D）：3，4，2，1； 【答案】：应选C．

5．一个二维数组M，行下标的范围是1到8，列下标的范围是0到9，每个数组元素用相邻的5个字节存储，存储器按字节编址，设存储数组元素M（1，0）的第一个字节的地址是98，且按列存储，则M（3，7）的第一个字节的地址是 。 （A）：135； （B）：233； （C）： 290； （D）：388； 【答案】：应选D。

6．由3个结点所构成的二叉树有 种形态，由3个结点构成的树有 种形态。 （A）：3； （B）：4 ；（C）： 5； （D）： 6 ； 【答案】：应选C和 A；

7．不含任何结点的空树 。 （A）： 是一棵树； （B）：是一棵二叉树； （C）： 是一棵树也是一棵二叉树；（D）：既不是一棵树也不是一棵二叉树； 【答案】：应选B。

8．一棵深度为k的满二叉树中结点的个数是 。

kkk-1k+1

（A）： 2-1；（B）：2；（C）：2；（D）：2； 【答案】：应选A．

9．一棵具有257个结点的完全二叉树，它的深度为 。

3

（A）： 8 ；（B）：9 ；（C）： 7； （D）：10； 【答案】：应选B．

10．二叉树是非线性数据结构，所以 。 （A）：它不能用顺序存储结构存储； （B）：它不能用链式存储结构存储； （C）：用顺序存储结构和链式存储结构都能存储； （D）：顺序存储结构和链式存储结构都不能存储； 【答案】：应选C．

11．把一棵树转换为二叉树后，这棵二叉树的形态是 。 （A）： 唯一的； （B）：有多种； （C）：有多种，但根结点都没有左孩子；（D）：有多种，但根结点都没有右孩子； 【答案】：应选A．

12．在表长为n的链表中进行线性查找，它的平均查找长度为 。

（A）：ASL= n ； （B）：ASL= (n+1)/2 ； （C）：ASL= +1 ；（D）：ASL ? log2 (n+1)-1； n 【答案】：应选B．

二、填空题

1．数据的基本单位是 ，它可以由 组成。 【答案】：数据元素； 数据项。

2．把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构是 。 【答案】：顺序存储结构。

3．顺序表结构适宜于进行 存取；链表适宜于进行 存取。 【答案】：随机存取；顺序存取。

4．栈是一种特殊的线性表，允许插入和删除运算的一端为 ，不允许插入和删除运算的一端为 。 【答案】：栈顶；栈底。 5． 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 【答案】：队列。

6． 三元组表中的每个结点对应与稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 ， 和 。 【答案】：行下标；列下标；元素值。

7． 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层最多能有 个结点。

4

【答案】：2。

8． 把一棵树转化为二叉树以后，这棵二叉树的根结点没有 。

【答案】：右子树。

9． 在数据的存放无规律而言的线性表中进行检索的最佳方法是 。

【答案】：线性检索。

10．有一个表长为m的散列表，初始状态为空，现将n (n

11．线性有序表（a1，a2，a3，??，a256）是从小到大排列的 ，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。 【答案】：9．

i-1

三、判断下列概念的正确性，并做出简要的说明。

1．线性表在物理存储空间中也一定是连续的。 【答案】：错误。

线性表的存储方式分两种，顺序存储和链式存储。顺序存储的物理空间是连续的，但链式存储的物理空间可以不连续。

2．栈和队列是一种非线性数据结构。 【答案】：错误。 栈和对列均为操作上受限制的线性表。

3．链表的物理存储结构具有同链表一样的顺序。 【答案】：错误。 链表的物理存储空间是任意的。

4．链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 【答案】：错误。

计算机不会自动地将后续的各个单元向前移动，当删除链表中某个结点时，需要用语句来修改相应的指针。

5．栈和链表是两种不同的数据结构。 【答案】：错误。

栈和链表是两个不同的概念，栈表示后进先出的线性表，它可以用顺序表来存储，也可以用链表来存储。而链表是一种物理存储方法。

6．一个矩阵也是一个线性表。 【答案】：正确。 矩阵是数据元素为线性表的线性表。

7．线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

5

【答案】：错误。

线性表的每个结点可以是简单类型，也可以是一个复杂类型。 而链表的每个结点因为是结构类型，所以它是一个复杂类型。

8．对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表. 【答案】：正确。

9．在表结构中最常用的是线性表，栈和队列不太常用。 【答案】：错误。 线性表、栈和队列都是最常用的线性结构。

四、问答题

1．试比较顺序存储结构和链式存储结构的优缺点。 【答案】： 顺序存储结构的优点是：能实现随机存取；存储密度大，存储空间利用率高。缺点是：插入元素时会有表溢出的情况；在插入和删除元素时将要引起大量元素的移动。 链式存储结构的优点是：插入元素时不会有表溢出的情况；在插入和删除元素时不需要移动任何元素，只需改变指针域中的指针值就可以了。缺点是：只能实现顺序存取；存储密度小，存储空间利用率不高。

2． 写出一个计算单链表中结点个数的算法，其中指针p指向该链表的第一个结点。 【分析】：根据单链表的特性，从单链表第一个结点开始计数，只要是非空结点，计数器加1，直到所有结点都走过一遍。 【答案】：

typedef struct snode{char data； struct snode *link；} NODE； int length(NODE *p){ NODE *q； int i；

q=p； i=0； /* 初始化 */

while (q!= NULL){ i++； q=q->link； } return (i)； }

3． 给定一个n项元素的线性表V，写一个算法，将元素排列的次序颠倒过来，要求仍占用

原来的空间，并且用顺序表和单链表两种方法表示。 【分析】：将V[1]与V[n]交换，V[2]与V[n-1]交换，??，V[n/2]与V[n/2+1]交换. 【答案】：顺序表结构下的实现： #define M 1000 int v[M]； int n；

void invert( ){ int temp；

for(i=0；i<=n/2；i++){ temp=v[i]； v[i]=v[n-i-1]； v[n-i-1]=temp； } }

6

【分析】：依次从原单链表的头部删除一个结点，在插入到另一个从空链表开始的单链表的头部。 【答案】：单链表结构下的实现：

typedef struct snode{char data； struct snode *link；} NODE； void invert(NODE *head ){ NODE *p，*u； p=NULL;

while (head!=NULL){

u=head； /*在头部删除一个结点 */ head=head->link；

u->link=p；/*将删除的结点插入到另一个链表中 */ p=u； }

head=p；/* 新链表的头指针 */ }

4．试设计实现在单链表中删除值相同的多余结点的算法。 【答案】：

typedef struct snode{char data； struct snode *link；} NODE； void purge_lklist(NODE *head){

NODE *p，*q，*r；

p=head->link；/* p指向当前检查结点的位置，先将其初始化 */ if(p==NULL) return；/* 空表返回 */

while(p->linkt!=NULL){ /* 当前结点不是尾结点 */ q=p；

while(q->link!=NULL) /* 删除值与p所指结点的值相同的结点 */ if(q->link->data==p->data){ /* 若有值相同的结点*q */ r=q->link；

q->link = q->link->link； /* 删除多余结点 */ free(r )； }

else q=q->link；/* 找下一个可以的多余结点 */ p=p->link； } /* 更新检查结点 */ }

5．描述以下三个概念的区别：头指针、头结点、首元元素结点。 【答案】：头指针：是指向单链表的第一个结点的指针。

头结点：在链表的首元元素结点之前附设的一个结点。 首元元素结点：是指用于存储线性表中第一个数据的结点。

6．写出计算线性链表长度的算法。 【分析】：：根据单链表的特性，从单链表第一个结点开始访问，只要是非空结点，计数一次，直到所有结点访问一遍。 【答案】：

typedef struct snode{char data； struct snode *link；} NODE；

7

int length(NODE *head){ NODE *p； int i；

p=head； i=0； /*初始化 */ while (p!=NULL){

i++； p = p->link； } return (i)； }

7．设有一个线性链表，其结点为正整数，且按值从小到大链接。试写出一个算法，将此线性链表分解成两个线性链表，其中一个链表中的结点值均为奇数，而另一个链表中的结点值均为偶数，且这两个链表均按值从小到大链接。 【分析】：在链表head中依次取元素(s->data)，若取出的元素是奇数，把它插入到奇数链表ahead中，若取出的元素是偶数，把它插入到偶数链表bhead中，继续取下一个元素，直到链表的尾部，头指针ahead和bhead分别指向奇数链表和偶数链表。 【答案】：

typedef struct snode{int data； struct snode *link；} NODE； void examp7(NODE *head，*ahead，*bhead){ NODE *p，*q，*s；

ahead=(NODE *)malloc(sizeof(NODE))；/* 建立奇数链表的头结点 */ p=ahead；， /* 工作指针p初始化。*/

bhead=(NODE *)malloc(sizeof(NODE))；/* 建立偶数链表的头结点 */ q=bhead； /*工作指针q初始化。*/

s= head->link； free(head)；/* s为原表中的工作指针，释放原表中的头结点 */ while (s!= NULL){

if( s->data % 2==0) /*是偶数 */

{ q->link = s ； q = q->link ；} else / * 是奇数 * /

{ p->link = s ； p = p->link； } s = s->link ； /* 取下一个结点 */ }

p->link = NULL； /* 置奇数表的表尾 */ q->link = NULL； /* 置偶数表的表尾 */ }

8．假设有一个循环单链表的长度大于1，且表中既无头结点也无头指针。已知S为指向链表中某结点的指针，试编写算法，在链表中删除S指针所指结点的前驱结点。 【分析】：：设置一个指针p，指向S结点的前驱结点的前驱结点。 【答案】：

typedef struct snode{char data； struct snode *link；} NODE； NODE *s；

void deleteprior( ){ NODE *p， *q； p = s；

while(p->link->link!=s)p=p->link；/*让p指向s结点的前驱结点的前驱结点 */

8

q=p->link； /* q指向被删除结点 */ p->link = q->link； /* 删除 */ free(q)； } 9．已知指针ha和hb分别指向两个单链表的头结点，且头结点的数据域中存放链表的长度，试写出一个算法将这两个链表连接在一起，并要求算法以尽可能短的时间内完成运算。 【分析】：：令表hb的首元结点连在表ha中的最后一个结点之后，首先想将工作指针p从ha的首元结点开始遍历到表ha中的最后一个结点，hc指向连接后的链表的头结点。 【答案】：

typedef struct snode{char data； struct snode *link；} NODE； NODE *ha，*hb，*hc； void example9( ){ NODE *p； int i；

hc = ha ； /* hc指向连接后的链表的头结点 */ p = ha->link；

i=1； /* 用于表ha中结点的计数器 */

while(idata) p = p->link；/* ha->data是表ha的长度 */ p->link = hb->link； /* 连接表hb的首元结点 */

hc->data = ha->data + hb->data； /* 连接后的链表的长度 */ }

10．对于下面的每一步，画出栈元素和栈顶指针示意图。

（1）栈空；（2）在栈中入栈一个元素A；（3）在栈中入栈一个元素B； （4）出栈中一个元素；（5）在栈中入栈一个元素C； （6）出栈中一个元素；（7）出栈中一个元素； 【答案】： A B A A C A A

（1） （2） （3） （4） （5） （6） （7）

11．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。 【答案】：

1，2，3，4； 1，2，4，3； 1，3，1，4； 1，3，4，2； 1，4，3，2；

2，1，3，4； 2，1，3，3； 2，3，1，4； 2，3，4，1； 2，4，3，1；

3，2，1，4； 3，2，4，1； 3，4，2，1； 4，3，2，1；

12．说明栈和队列的异同点。

9

【答案】：

相同点：栈和队列都是线性表结构； 不同点：栈是限定在线性表的一端进行插入和删除的操作；而队列的插入和删除在线性表的两端进行；

13．顺序队的“假溢出”是怎样产生的？如何知道循环队是空还是满？ 【答案】：

队列的尾指针已经到了数组的上界，此时如果还要执行入队运算，就要发生“上溢”，但是数组中还有空位置，这种现象称为“假溢出”。

在循环队中， 当rear==front时，表示队空；当 (rear+1)%M= =front时，表示队满。

14．设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 （1）front = 11， rear=19；（2）front = 19， rear = 11；问在这两种情况下，循环队

列中的各有多少个元素？ 【答案】： （1）：8个 ； （2）：32 ；

15．假设一数组squ[m]存放循环队列的元素。若要使m个分量都得到利用，则需要另一个标志tag，以tag为0或1来区分队尾指针和队头指针值相同时队列的状态是“空”还是“满”。试编写与此结构相应的入队和出队的算法。 【答案】： #define M 100

int squ[M]，front，rear，tag；/* 队列中加一个标志域tag */ int addque(int x) { /* 入队运算 */ if ((tag==1)&&(front==rear))

{ printf(“full queuer!\\n”)； return (-1) ； }

else

{ rear = (rear+1)%M； squ[rear] = x；

if (rear==front) tag=1 ； /* 如果插入后队列满，则置标志 */ } }

int delque( ) { /* 出队运算 */

if( tag==0) &&(front==rear))

{printf (“empty queuer !\\n”)； return(-1)； } else

{ front = （front+1}% M；

if(front==rear) tag=0；/* 如果删除后队列空，则置标志 */

return (squ[front])； } }

16．假设以带头结点的循环单链表表示队列，并且只设一个指针指向队尾元素结点，不设头

10

指针，试编写相应的入队和出队算法。

【答案】：

typedef struct snode{int data； struct snode *link；} NODE； NODE *rear； /* 定义结点的类型和指向队尾的指针*/

void addqueue (int x){ NODE *p；

p = (NODE *)malloc(sizeof(NODE))；/* 申请结点空间 */ p->data = x；

p->link = rear->next； rear->next = p； /* 在队尾插入结点 */ rear = p； /* 修改队尾指针 */ }

int delequeue( ) { /*从链队中出列，返回出队的数据元素 */ NODE *p；

if (rear->link==rear)

{ printf(“queue is empty!\\n”)； return(-1)； } else { p=rear->link； /* p指向头结点 */

q=p->link； /* q指向被删除结点 */

if(q==rear) rear=p； /* 队列中仅有一个结点时，先修改尾指针*/ p->link=q->link； x=q->data；

free(q)； return(x)； /* 删除结点并返回 */ } }

17．已知二维数组Am，m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为LOC（a11），请写出LOC（aij）的计算公式。如果采用列优先顺序存放呢？

【答案】：

按行优先顺序存放：LOC(aij)=LOC(a11)+((i-1)*m + (j-1))*K； 按列优先顺序存放：LOC(aij)=LOC(a11)+((j-1)*m + (i-1))*K；

18．用三元组表表示下列稀疏矩阵：

0 0 0 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 0 0 9 0

0 3 0 0 0 8 0 0 0 0 0 0 0 0 （1） 0 0 0 0 0 0 0 0 （2） 0 0 5 0 0 0

0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 5 2 0 0 0 0 0 0 0 【答案】： （1） （2）

行下标61246

11

列下标66535元素值4-2953行下标833578列下标826481元素值538652

19．下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。

6 4 6

1 2 2 4 5 5 1 3 12 1 1 1 （1） 3 1 3 （2） 2 4 9

4 4 4 3 2 8 5 3 6 3 5 6

6 1 16 4 3 7

【答案】：

0 2 12 0 1 0 0 0 0 0 0 0 0 0 0 0 9 0 （1）： 3 0 0 0 （2）： 0 8 0 0 6

0 0 0 4 0 0 7 0 0 0 0 6 0 16 0 0 0

20．什么样的二叉树不是树？一棵度为2的树与一棵二叉树有何区别？ 【答案】：

空树是二叉树，但不是树。树一定是非空的。 在一棵度为2 的树中至少有一个结点的度为2；但在一棵二叉树中每个结点的度可以都

小于2，比如单枝树。

21．试分别画出具有3个结点的树和有3个结点的二叉树的所有不同形态。 【分析】：无序树的子树没有顺序之分，而二叉树的子树分为左子树和右子树。 【答案】：具有3个结点的树 ：

12

有3个结点的二叉树：

22．设一棵完全二叉树具有1000个结点，问此完全二叉树 （1）有多少个叶子结点？ （2）有多少个度为2的结点？

（3）有多少个结点只有非空左子树？ （4）有多少个结点只有非空右子树？

9

【分析】：有1000个结点的完全二叉树共有10层，在第10层有1000-（2-1）=1000-511=489个结点；都是叶子结点，它们共有244+1个双亲结点在第9层，其中有一个双亲结点只有一个孩子，其他共244个双亲结点的度均为2，所以在第9层还有256-245=11个结点的度为0，既为叶子结点。 【答案】：

（1）有500个叶子结点。

（2）有255+244=499个度为2的结点； （3）有1个结点只有非空左子树； （4）没有结点只有非空右子树；

23．下面是有关二叉树的叙述，哪些是正确的？

（1）二叉树中每个结点的两棵子树的高度差不大于1。 （2）二叉树中每个结点的两棵子树的高度差等于1。 （3）二叉树中每个结点的两棵子树是有序的。

（4）二叉树中每个结点的两棵非空或有两棵空子树。

（5）二叉树中每个结点的关键字值大于左子树（若存在的话）上所有结点的关键字值，

且小于其右非空子树（若存在的话）上所有结点的关键字值。

k-1

（6）二叉树中所有结点个数是2–1，其中k是树的深度。

（7）二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 【答案】：

（1）错误。AVL树中每个结点的两棵子树的高度差不大于1。 （2）错误。 （3）正确。

（4）错误。二叉树中有些结点可以有一棵空子树，一棵非空子树。 （5）错误。二叉排序树满足所叙述的条件。

k

（6）错误。二叉树中所有结点个数至多是2–1 。

（7）错误。二叉树中的结点，可以没有非空左子树，但有非空右子树。

24．用链式结构存储二叉树，试写出下列算法： （1）按层次输入所有结点； （2）输出所有叶子结点。 【答案】：

/* 先定义二叉树的二叉链表结构*/

13

typedef struct node {int data； struct node *lchild，*rchild；} NODE； （1）按层次输入所有结点：

【分析】： 本算法要借用队列来完成，其基本思想是，只要队列不为空，就出队列，然后判断该结点是否有左孩子和右孩子，如有就依次输出左、右孩子的值，然后让左、右孩子进队列。

void layorder(NODE *root){

/* 设q是一个队列，函数initqueue(q)、addqueue(q，x)、delqueue(q)、empty(q)

在2.4.2队列中已实现 */

initqueue(q)； /* 初始化一个队列 */ if (root!=NULL) {

printf(“%d”，root->data)； /* 输出结点值 */ addqueue(q，root)； /* 根结点入队 */ while( NOT empty(q)) { /* 如果队列不空 */ p=delqueue(q)； /* 对头元素出队 */ if (p->lchild!=NULL)

{ printf(“%d”，p->lchild->data)； /* 输出左孩子的值 */ addqueue(q，p->lchild)； /* 左孩子入队 */ }

if (p->rchild!=NULL)

{ printf(“%d”，p->rchild->data)； /* 输出右孩子的值 */ addqueue(q，p->rchild)； /* 右孩子入队 */

} } }

}

（2）输出所有叶子结点： 【分析】： ： 本算法为先根遍历的递归算法。如果树不空，分三步进行：第一步，判断根结点是否为叶子结点，若是，则输出；第二步，调用该算法输出根结点的左子树上的所有叶子结点；第三步，调用该算法输出根结点的右子树上的所有叶子结点； 【答案】：

typedef struct node {int data； struct node *lchild，*rchild；} NODE； void printleaf(NODE *root){ if (root!=NULL){

if((root->lchild==NULL)&&(root->rchild==NULL))

printf(“%d”，root->data)； /* 如根结点是叶子结点，则输出 */

printleaf(root->lchild)； /* 输出左子树上的所有叶子结点 */ printleaf(root->rchild)； /* 输出右子树上的所有叶子结点 */

} } 25．已知一棵具有n个结点的完全二叉树被顺序存储于一维数组btree中，试编写一个算法打印出编号为i的结点的双亲和所以孩子。

14

【答案】： #define N 100

int btree[N] /* 定义完全二叉树的存储结构 */

void print_parent_child(int n，int i){ /*n为结点个数 */

if(n==0) { printf(“ Tree is empty!”)； return；} /* 空树 */

else if((i<1)||(i>n)) {printf(“ order i error!”)； return；} /* 编号出错 */

else if(i==1) /* 根结点无双亲 */

{ printf(“ No parents\\n”)；

if(2*i<=n)printf(“Lchild is:%d\\n”，btree[2*i])； if(2*i+1<=n)printf(“Rchild is:%d\\n”，btree[2*i+1])； }

else {

printf(“Parent is:%d\\n”，btree[i/2])； /*双亲*/

if(2*i<=n)printf(“Lchild is:%d\\n”，btree[2*i])；/*左孩子*/ if(2*i+1<=n)printf(“Rchild is:%d\\n”，btree[2*i+1])；/*右孩子*/ } }

26．试写出如下所示的二叉树分别按先序、中序、后序遍历得到的结点序列。 A

B C

D E

F G H I

J K L M 【答案】：

先序序列：ABDFJGKCEHILM 中序序列：BFJDGKACHELIM 后序序列：JFKGDBHLMIECA

27．把如图所示的树转化为二叉树。

A B C D

E F G H I J K L M 【答案】： A B E C K F H D L G I M J 15

图书预订系统 输入 分类统计订单 输出对出版社订单 检验订单

输出不合格订单

15．软件测试有哪些基本原则？ 【解答】：软件测试的基本原则是：

（1） 最好由一个独立的部门或组织来测试软件系统。

（2） 测试用例应该由输入数据和预期的输出结果两部分组成。

（3） 不仅要选用合理的输入数据，还应该选用不合理的输入数据作为测试用

例。

（4） 除了检查程序是否做了它应该做的工作外，还要检查程序是否做了它不应

该做的事情。

（5） 长期保留所有测试用例，直到这个软件系统被废弃不用为止。 （6） 在对程序做了修改之后要进行再测试。 （7） 重点测试容易出错的程序段。

16．白盒法和黑盒法有什么不同？它们各用于什么地方？

【解答】：白盒测试法把程序看成是装在一个透明的白盒子中，既完全了解程序的结构和处理过程，并以此为基础设计测试用例，检查程序中的每条路径是否都能按照预定的要求正确工作。模块测试以白盒测试为主，辅之以黑盒测试，同时白盒测试也适用于对软件详细设计阶段的软件文档进行测试。黑盒法把程序看成一个黑盒子，即完全不考虑程序的内部结构和处理过程，只检查程序的功能是否能按照规格说明书正常使用，程序是否能够适当的接受输入数据，产生正确的输出信息，并且保持外部信息的完整性。黑盒测试主要用于联合测试和验收测试，除了测试程序外，还适用于对需求分析阶段的软件文档进行测试。

17．设一个要被测试的源程序如下：

float solut (x,y,z) float x,y,z;

{ if (x>3&&y==2) z=1;

if (x==4||z>3)

z=z+1; return z;}

试设计测试用例，满足条件组合覆盖标准。

46

【解答】：本题共有八中可能的条件组合，它们是： (1) x<3 , y≠2 (5) x≠4 , z<3 (2) x<3 , y==2 (6) x≠4 , z>3 (3) x>3 , y≠2 (7) x==4 , z<3 (4) x>3 , y==2 (8) x==4 , z>3

可以选择以下四组测试数据，使得上述八种组合至少出现一次：

输入 输出 覆盖标准 x=2,y=1,z=2 x=2 ,y=1 ,z=2 覆盖(1)(5)两种组合 x=2,y=2,z=4 x=2 ,y=2 ,z=5 覆盖(2)(6)两种组合 x=4,y=1,z=4 x=4 ,y=1 ,z=5 覆盖(3)(8)两种组合 x=4,y=2,z=2 x=4 ,y=2 ,z=2 覆盖(4)(7)两种组合

18．软件测试有哪几个步骤？简述每一步的目标和特点。 【解答】：软件测试可分为以下三个步骤进行：模块测试、联合测试、验收测试。 模块测试的目标是发现模块内部可能的各种错误，这些错误通常是在编码阶段产生的错误，因此为模块测试设计测试用例时多以白盒测试为主。

联合测试是把各模块连接起来进行测试，测试的依据是模块说明书。联合测试可以查找与接口有关的错误，这一步的目标是发现设计阶段产生的错误。验收测试是把软件系统当作单一的实体进行的测试，验收测试的过程和结果应当是客观的且符合实际。因此验收测试应在软件投入后的实际环境下进行，并由用户主持进行，测试用例应为实际数据。验收的依据是系统说明书，这一步的目标是发现分析阶段的错误。

19．软件维护的含义是什么？有哪几种类型的维护？

【解答】：软件维护是指软件投入运行后，解决发生的各种故障（错误），增加其功能，使之适应新的环境等软件工程活动。主要分为以下四种类型的维护：

（1） 改正性维护：为排除故障，使系统能正常运行，需要进行诊断和改正错误，

这样的维护工作称为改正性维护.

（2） 适应性维护：为适应各种环境的变化而修改软件的维护工作，称之为适应性

维护。

（3） 完善性维护：为满足用户的新需要，而对软件进行的修改和扩充，这样的维

护工作称之为完善性维护。

（4） 预防性维护：为了改进软件未来的易维护性和可靠性，或者为了给未来的改

进提供更好的基础而对软件进行的修改，称之为预防性维护。

20．什么是“易维护性”？为什么“易维护性”是软件的一个重要的质量标准？

【解答】：软件的易维护性是指软件易阅读、易发现和纠正错误、易修改扩充的能力。软件的易维护性是衡量软件的一个重要标准，这是因为随着软件规模的扩充和复杂性的增加，用于软件维护的成本不断的上升；同时由于合理的改错和修改要求不能及时满足而引起用户的不满；由于维护的副作用，在软件中引入新的错误而降低软件的可靠性等等，这些都说明软件维护的问题显得越来越重要。软件易维护性的三个特性：可测试性、可理解性和可修改性都是衡量软件质量的基本特性，因此软件的易维护性是软件的一个重要的质量标准？

47

实验一至实验四的实验环境要求：TURBOC 2.0

上机步骤：以WINDOWS 98为例（1）进入WINDOWS 98（2）进入MSDOS方式（3）执行命令PDOS95，进入汉字系统（4）进入TURBOC 2.0的集成环境。

实验一

（一） 实验名称

线性表的插入和删除 （二） 实验目的与要求

掌握线性表在链接存储结构下的插入与删除运算，其数据是用随机数的方法来得到随机数。

（三）程序清单

#include #include

typedef struct ss{int x; struct ss*next;} node; /*插入一个结点*/

node *insert(node *head,int a) {node *p1,*new; p1=head->next;

new=(node *)malloc(sizeof(node)); new->x=a;new->next=NULL; head->next=new; new->next=p1; return head;} /*删除一个结点*/

node *dele(node *head,int a) {node *p1,*p2; p1=head->next; p2=head;

if(head->next==NULL){printf(\else

{while(a!=p1->x && p1->next!=NULL){p2=p1;p1=p1->next;}

if(a==p1->x && p1->next!=NULL){p2->next=p1->next;free(p1);} if(a==p1->x && p1->next==NULL){p2->next=NULL;free(p1);} }

return head;} /*显示链表*/

void display(node *head) {node *p1;

printf(“链表如下：\\n”); p1=head->next;

while(p1){printf(\ printf(\/*主函数*/ main()

48

{int w,n,i; node *head;

head=(node *)malloc(sizeof(node)); head->next=NULL;

printf(\输入数据的个数:\scanf(\for(i=1;i<=n;i++){

w=rand();/*用函数rand()随机产生一个整数*/ head=insert(head,w);} display(head);

printf(\插入一个数:\

scanf(\display(head);

printf(\删除一个数：\

scanf(\display(head); getch(); }

实验二

（一） 实验名称

二叉排序树

（二） 实验目的与要求

掌握二叉树的链式存储结构，二叉树的遍历方法和二叉排序树的查找方法。 （三）程序清单

#include typedef struct node{ int key;

struct node *lchild,*rchild;}BSTNode; /*插入一个结点*/

BSTNode *insertBST(BSTNode *Tptr,int key) {BSTNode *f,*p=Tptr; while(p){

if(p->key==key)return Tptr; f=p;

p=(keykey)?p->lchild:p->rchild;} p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=key;p->lchild=p->rchild=NULL; if(Tptr==NULL)Tptr=p; else

if(keykey)f->lchild=p; else f->rchild=p; return Tptr; }

49

/*建立二叉排序树*/ BSTNode *CreateBST() {BSTNode *T=NULL; int key;

scanf(\

while(key){T=insertBST(T,key);scanf(\ return T; }

/*遍历二叉排序树*/

void inorder(BSTNode *T) {if(T){inorder(T->lchild); printf(\ inorder(T->rchild);} }

/*查找*/

BSTNode *serchBST(BSTNode *T,int key) {if(T==NULL||key==T->key)return T;

if(keykey)return serchBST(T->lchild,key); else return serchBST(T->rchild,key);} /*主函数*/ main()

{BSTNode *BSTree,*p; int a; BSTree=CreateBST();

inorder(BSTree);printf(\ printf(“输入待查找的关键字：”); scanf(“%d”,&a);

p=serchBST(BSTree,a);

if(p==NULL)printf(\ else printf(\ }

实验三

（一） 实验名称

排序

（二） 实验目的与要求

掌握选择排序法、冒泡排序法和快速排序法。 （三）程序清单

/*选择排序*/

void xzsort(int p[],int n) {int i,j,min,t; for(i=0;i

for(j=i+1;jp[j])min=j;

50

本文来源：https://www.bwwdw.com/article/2662.html