自考 2365计算机软件基础（二）课后 习题

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

第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的满二叉树中结点的个数是 （A）： 2k-1；（B）：2k；（C）：2k-1；（D）：2k+1； 【答案】：应选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． 把一棵树转化为二叉树以后，这棵二叉树的根结点没有

【答案】：右子树。

。

i-1

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

【答案】：线性检索。

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

。

【答案】：1+2+3+??+n =n(n+1)/2。

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

次。

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

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 （6）

（7）

（1） （2） （3） （4） （5）

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

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

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

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

1，2，

3，2，1，4； 3，2，4，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 3

0 0 0 0 0 0 0

0 0 0 6 0 0 0

0 0 0 0 0 0 0

0 8 0 0 0 0 0

0 0 0 0 0 0 0

0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 5 0 0

0 0 0 0 0 0

0 9 0 0 0 3

-2 0 0 0 0 0

（1） 0 0 0 0 0 0 0 0 2 0

0 （2） 0 0 5 0

【答案】： （1） （2）

列下标66535元素值4-2953行下标61246

11

行下标833578列下标826481元素值538652

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

6 4 6

（1）

【答案】：

0 0

2 0 0 0

12 0 0 0 0 0

0 4

1 0

0 0 8 0

0 0 0 7

0 9 0 0

0 0 6 0

1 1 3 4 5

2 3 1 4 3

2

4 1 2 3 3 4

5 1 4 2 5 3

5 1 9 8 6 7

12 3 4 6

（2）

6 1 16

（1）： 3

0 （2）： 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）有多少个结点只有非空右子树？

【分析】：有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）二叉树中每个结点的关键字值大于左子树（若存在的话）上所有结点的关键字值，

且小于其右非空子树（若存在的话）上所有结点的关键字值。 （6）二叉树中所有结点个数是2k-1 –1，其中k是树的深度。

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

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

（3）正确。

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

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

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

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

【答案】：

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

13

9

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 F

D J G

K

C H

E I L

M 【答案】：

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

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

B

A C D J E F G 【答案】：

K

E L

B A C D I J H I K L M F H G M 15

28．已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，画出这棵二叉树。 【分析】： 由后序遍历序列能够得到的二叉树的根结点A（后序序列中最后一个结点）；在中序序列中，A的左边是A 的左子树上的结点，A的右边是A 的右子树上的结点；再到后序序列中找左子树和右子树的根结点，依次类推，直到画出该二叉树。 【答案】：

C

A B F G D E H

29．对以链表作存储结构的二叉树设计求二叉树的深度的算法。

typedef struct node {int data； struct node *lchild，*rchild；} NODE； 【分析】： ： 本算法为递归算法。空树的深度为0，如果树不空，分三步进行：第一步，判断根结点是否为叶子结点，若是，则深度为1；第二步，调用该算法求根结点的左子树的深度hl，第三步，调用该算法求根结点的右子树的深度hr；二叉树的深度为max(hl，hr)+1。

【答案】：

int depth(NODE *root){

if (root==NULL) return 0；

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

return (1)； /* 如根结点是叶子结点，则深度为1 */

else {

hl=depth(root->lchild)； /* 左子树的深度 */

hr=depth(root->rchild)； /* 右子树的深度 */

if(hl>hr) return(hl+1)；

else return(hr+1)； /*深度为max(hl，hr)+1 */ }

}

30．对序列12，7，17，11，16，2，13，9，21，4构成一棵二叉排序树。 【答案】：

2 7 12 17 21 11 16 4

9 13 16

31．从供选择的答案中找出应添入下列叙述中的（ ）内的正确答案。 （1）要进行线性查找，则线性表（ ）； （2）要进行二分查找，则线性表（ ）； （3）要进行散列查找，则线性表（ ）； （A）：必须以顺序方式存储； （B）：必须以链式方式存储； （C）：必须以散列方式存储；

（D）：既可以以顺序方式存储，也可以以链式方式存储； （E）：必须以顺序方式存储且数据元素已按值递增或递减的次序排好。 （F）：必须以链式方式存储且数据元素已按值递增或递减的次序排好。 【答案】：（1）选择D；（2）选择E；（3）选择A；

32．用二分查找的查找速度必然比线性查找的速度快。这说法对吗？为什么？ 【答案】：

正确。因为用二分查找法来查找时，在每一次比较之后，如查找不成功，是将待查范围缩小一半。而采用线性查找时，每次比较之后是将待查范围缩小一个元素。二分查找的平均查找长度为：log2n；而线性查找的平均查找长度为：（n+1）/2。

33．说明散列查找和其它查找方法的区别。

【答案】： 散列查找是希望平均查找长度与记录的个数无关，既不经过任何比较，“一次”存取就能得到所要查找的元素的查找方法。它要求在元素的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。而其它的查找方法的平均查找长度都与记录的个数有关，但不必在元素的存储位置和它的关键字之间建立一个确定的对应关系。

34．r是一个顺序表结构的有序表，编写一个查找算法，要求在查找失败时做插入操作并保持表r的有序性。 【分析】：：用二分查找方法，如查找成功，则返回待查元素在表中的位置，如果查找不成功，既low>high时，此时high+1的位置为待查元素所应插入的位置，这样可以保持表r的有序性。 【答案】：

#define M 500

typedef struct {int key； char info；} NODE；

NODE r[M]；

int binsrch_insert(int n，int k){ /* k为要查找的数据，n为实际的表长 */ int low，high，mid，k； NODE temp； low=1； high=n； while(low<=high){

mid=(low+high)/2；

if(k==r[mid].key) return(mid)； /* 查找成功 ，返回*/

else if(k

17

if(n==M) { printf(“ Table is full!\\n”)； return 0； } /* 表满不能插入 */ else { for(k=n；k>=high+1；k--)

r[k+1]=r[k]； /*从r[high+1]到r[n]的所有元素右移一个位置*/ r[high+1].key=k； r[high+1].info=??；/* 数据插入 */ } }

35．设记录的关键字集合为K=（32，13，49，55，22，39，17），用模除散列函数得到散列

地址，解决冲突的办法为线性探测法，按上述条件将集合中的各值依次添如下表中。

0

1 2 3 4 5 6 7

【答案】：

32 49 39 17 13 22 55 36．选取散列函数H（key）=（3*key）% 11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0~ 10，表长为11的散列表，（22，41，53，08，46，30，01，

31，66）。 22 01 41 30 66 53 46 31 08 0 1 2 3 4 5 6 7 8 9 10

37．关键字序列T={13，6，3，31，9，27，5，11}，分别写出选择排序和直接插入排序的

中间过程序列。 【答案】：

（1）选择排序： i k 初始序列： 13 6 3

31 9 27 5 k 27 5 11 /*T[1]与T[3]交换 */ 11] /*T[2]与T[7]交换 */

i 完成第一趟： 3 [6 13 31 9 i k 完成第二趟： 3 5 [13 31 9 27 6 11] /*T[3]与T[7]交换 */

i k 完成第三趟： 3 5 6 [31 9 27 13 11] /*T[4]与T[5]交换 */

i k 完成第四趟： 3 完成第五趟： 3 完成第六趟： 3

完成第七趟： 3

（2）直接插入排序：

初始序列： 13 6 3 31 9 27 5 11 第一趟： [13] 6 3 31 9 27 5 11 第二趟： [6 13] 3 31 9 27 5 11

5 6 9 [31 27 13 11] /*T[5]与T[8]交换 */ i k 5 6 9 11 [27 13 31] /*T[6]与T[7]交换 */ i=k 5 6 9 11 13 [ 27 31] /*不用交换 */ i=k 5 6 9 11 13 27 [ 31] 18

第三趟： 第四趟： 第五趟： 第六趟： 第七趟： 第八趟：

[3 [3 [3 [3 [3 [3

6 6 6 6 5 5

13] 31 9 13 9 9 6 6

27 5 11

31] 9 27 5 11 13 31] 27 5 11 13 27 31] 5 11 9 13 27 31] 11 9

11 13 27 31]

38．对于整数序列100，99，?，3，2，1，如果将它完全倒过来，分别用冒泡排序和快速

排序法，它们的比较次数和交换次数各是多少？ 【答案】：

对冒泡排序方法来说，这个序列是最坏的情况，n=100个数据，共进行99趟排序操作，第一趟要比较99次，第二趟要比较98次，??，第99趟要比较1次，每一次比较都

执行了一次交换，所以共进行了99+98+97+??+1=100*99/2=4950次比较和交换。

对快速排序方法来说，这个序列也是最坏的情况，与冒泡排序一样，共进行99趟排序。第一趟要比较99次，进行一次交换，第二趟要比较98次，不需要交换，第三趟要比较97次，进行一次交换，第四趟要比较96次，不需要交换，??，所以总的比较次数为4950次，交换的次数为50次。

39．对关键码值为{35，11，52， 69， 6， 17， 76，64，82}的序列执行以下排序算法，

画出执行过程中每个中间状态和结束时的状态： （1）直接插入排序；（2）二分插入排序；（3）直接选择排序；（4）冒泡排序；（5）快速排

序。

【答案】：

（1）直接插入排序：

初始序列： 35 11 52 69 6 第一趟： [35] 11 52 69 6

第二趟： [11 35] 52 69 6 第三趟： [11 35 52] 69 6 第四趟： [11 35 52 69] 6

17 76 64 82 17 76 64 82 17 76 64 82 17 76 64 82 17 76 64 82

第五趟： [6 11 35 52 69] 17 76 64 82 第六趟： [6 11 17 35 52 69] 76 64 82 第七趟： [6 11 17 35 52 69 76] 64 82 第八趟： [6 11 17 35 52 64 69 76] 82

第九趟： [6 11 17 35 52 64 69 76 82]

（2）二分插入排序：与直接插入排序类似，只是在找插入位置时用二分查找方法。 （3）直接选择排序：

初始序列： [ 第一趟： 第二趟： 第三趟： 第四趟： 第五趟：

第六趟：

35 11 52 69 6 17 76 64 82 ] 6 [ 11 52 69 35 17 76 64 82 ] 6 6 6 6 6

11 [ 52 69 35 17 76 64 82 ] 11 17 [ 69 35 52 76 64 82 ] 11 17 35 [69 52 76 64 82 ] 11 17 35 52 [ 69 76 64 82 ] 11 17 35 52 64 [ 76 69 82 ]

19

第七趟： 第八趟：

（4）冒泡排序：

初始序列：

6 6

11 17 35 52 64 69 [ 76 82 ]

82 ]

11 17 35 52 64 69 76 [

35 11 52 69 6 17 76 64 82

第一趟： 11 35 52 6 17 69 64 76 82 /* 4次交换 */ 第二趟： 11 35 6 17 52 64 69 76 82 /* 3次交换 */ 第三趟： 第四趟： 第五趟：

11 6 17 35 52 64 69 76 82 /* 2次交换 */ 6 11 17 35 52 64 69 76 82 /* 1次交换 */ 6

11 17 35 52 64 69 76 82 /* 没有任何交换，完

成*/

（5）快速排序：

初始序列： 35 11 52 69 6 i 第一次交换： 17 11 52 69 6 i 第二次交换： 17 11 35 69 6 i j 第三次交换： 17 11 6

第四次交换： 17 11 6 i j i j 17 76 64 82 /* 初始化i=1，j=9 */

j 35 76 64 82 /* j=6时与35交换 */

j 52 76 64 82 /* i=3 时与35交换*/

69 35 52 76 64 82 /* j=5 时与35交换*/

35 69 52 76 64 82 /* i=4 时与35交换*/

i=j 完成一趟排序：[17 11 6] 35 [69 52 76 64 82 ] /* i=j=4 */ i j i j 下一趟初始： [17 11 6] [69 52 76 64 82 ] i j i j 第一次交换： [6 11 17] [64 52 76 69 82 ] i= j i j 第二次交换： [64 52 69 76 82 ] i=j 完成第二趟排序： [6 11] 17 [64 52] 69 [76 82]

下一趟初始：

第一次交换：

完成第三趟排序： 6 [11]

排序完成：

[52] 64

76 [82]

69

76

82

i j i j i j i= j [6 11] [64 52] i= j [76 82]

i j [52 64] 6 11 17 35 52 64

20

R∪S

商品编号 1001 1005 1010 1006 1011 1022

R－S

商品编号 1005 1010

R∩S

商品编号 1001

R与S的笛卡尔积

商品编号 1001 1001 1001 1001 1005 1005 1005 1005 1010 1010 1010 1010

10．已知如下关系M，N，求M∪N，M－N，M∩N。

【解答】：

商品名称 奶粉 奶粉 奶粉 奶粉 酱油 酱油 酱油 酱油 饼干 饼干 饼干 饼干 生产厂家 北京 北京 北京 北京 天津 天津 天津 天津 青岛 青岛 青岛 青岛 商品编号 1001 1006 1011 1022 1001 1006 1011 1022 1001 1006 1011 1022 商品名称 奶粉 醋 曲奇 酒 奶粉 醋 曲奇 酒 奶粉 醋 曲奇 酒 生产厂家 北京 天津 青岛 河北 北京 天津 青岛 河北 北京 天津 青岛 河北 商品名称 奶粉 生产厂家 北京 商品名称 酱油 饼干 生产厂家 天津 青岛 商品名称 奶粉 酱油 饼干 醋 曲奇 酒 生产厂家 北京 天津 青岛 天津 青岛 河北 31

关系M

A a1 a1 a2 B b1 b2 b1 关系N

A a1 a2 a1 B b2 b1 b3 C c3 c2 c2 C c2 c3 c3 M∪N A a1 a1 a2 a2 a1 B b1 b2 b1 b1 b3 M－N

A a1 a2 B b1 b1 M∩N A a1

11．已知两个关系R、S。试求出R S的结果。

B>D 【解答】： R

A a b S

D 5 8

32

C c1 c3 c3 c2 c2 C c1 c3 B b2 C c3 B 4 6 C c d E e d F 9 6 结果

A b

12．已知两个关系G，H。试求出R S的结果。

【解答】： G

A a b d c B 6 3 8 4 C d c a d B 6 C D D 5 E e F 9 H

B 3 4 4 D 7 8 9 结果 A b c c

13．对于表4-12，请用关系代数运算，查找：

（1） 陈中金老师所教的学生的姓名。 （2） 选修英语的学生的年龄和成绩。

（3） 魏立同学选修的课程的名称和教师姓名。 【解答】；

教师情况关系T 教师号 T# 203 301 411 504 507

教师姓名 所属系 TN 王朝阳 刘子咏 张梅 陈中金 洪文源 TD 数学 物理 外语 计算机 计算机 B 3 4 4 C c d d D 7 8 9 33

课程关系C

课程号 C# 21 31 41 51 52 课程名 CN 教师号 T# 高等数学 203 普通物理 301 英语 411 微机原理 504 软件基础 507 学生情况关系S

学生号 T# 9031 9032 9033 9034 9035 9036 9037 学生姓名 年龄 SN 林强 高峰 孙锺 黄殷 陆伟 魏立 蔡军 SA 19 20 20 19 19 20 20 学生成绩关系SC

学生号 S# 9031 9031 9031 9032 9032 9032 9033 9033 9033 9034 9034 9034 9035 9035 9035 9036 课程号 CN 21 41 51 21 41 51 21 31 41 31 51 52 41 51 52 21 成绩 G A B B B A B B B A B A B A B B A 34

9036 9036 9037 9037 9037

31 52 41 51 52 B A B A A （1）①对T进行选择运算，条件是TN=陈中金，得到新的关系A。 关系A

T# 504 TN 陈中金 TD 计算机 ②把关系A和C进行自然连接，得到关系B。

关系B

T# TN TD 计算机 C# 51 CN 微机原理 504 陈中金 ③关系B在TN和C#上投影，得到关系D。 关系D TN 陈中金 C# 51 ④关系D和关系SC进行自然连接，得到关系E。

关系E

TN 陈中金 陈中金 陈中金 陈中金

⑤关系E和关系S进行自然连接的关系F。

关系F

TN 陈中金 陈中金 陈中金 陈中金

⑥关系E在SN上进行投影运算得关系G。

C# 51 51 51 51 S# 9031 9034 9035 9037 G B A B A SN 林强 黄殷 陆伟 蔡军 SA 19 19 19 20 C# 51 51 51 51 S# 9031 9034 9035 9037 G B A B A 35

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