软件技术基础-周大为全11章练习题

第一章软件工程

一、填空题

1.软件生存周期是指一个软件从提出开发要求开始，直到为止的整个时期。

2.数据流图中的箭头表示o

3.当A模块调用B模块时，若两个模块之间的参数传递是数值型参数，则这两个模块的耦合方式是。

4.某软件结构图分为4层，从顶层到底层，各层的模块个数分别为1、3、5、4,那么该软件结构图的宽度是，

5.软件的详细设计的主要任务是确定每个模块的o

6.程序员在编写程序时所体现出的特点、习惯、逻辑思路等，反映了这个程序员的。

7.在集成测试中，采用自顶向下的渐增式测试，需要程序。

8.软件的集成测试（联合测试）的目的是发现阶段的错误。

9.在软件生存期的各个阶段中跨越时间最长的阶段是阶段。

10.软件维护工作的生产性活动包括分析评价、修改设计和等。

11.子类自动共享父类数据结构和方法的机制是，这是类之间的一种关系。

12.面向对象分析的目的是对进行建模。

13.面向对象分析阶段所使用的三种模型是、动态模型和功能模型。

二、选择题

1.软件产品管理包括版本管理和（）。

A.质量管理B.性能管理C.配置管理D.开发过程管理

2.螺旋模型是种将（）和增量模型结合起来的软件开发模型。

A.瀑布模型B.专家系统C.喷泉模型D.变换模型

3.软件开发可行性分析研究的目的是（）。

A.争取软件项目B.软件项目值得开发否C.设计软件D.规划软件项目

4.软件需求分析的主要任务是确定所要开发的软件系统（）。

A.如何做B.怎么做C.做什么D.对谁做

5.在（）方法中，采用数据流图（DFD）表示系统的逻辑模型。

A.SAB.SDC.SPD.SC

6.软件需求分析阶段的工作是系统分析员了解用户的要求，认真细致地调研、分析，最终建立目标系统的逻辑模型并写出（）的过程。

A.模块说明书B.软件规格说明C.项目开发计划D.合同文档

7.模块之间的耦合度应当尽可能低。当一个模块直接使用另一个模块的内部数据，这种模块之间的耦合称为（）。

A.数据耦合B.公共耦合C.标记耦合D.内容耦合

8.模块的内聚性应当尽可能高，通信内聚、逻辑内聚、顺序内聚和时间内聚的内聚性从高到低顺序是（）。

A.通信、逻辑、顺序、时间B.通信、时间、顺序、逻辑C.顺序、通信、时间、逻辑D.顺序、通信、逻辑、时间

9.信息隐蔽概念与（）直接相关。

A.模块的独立性B.模块类型的划分C.软件结构定义D.软件生命周期

10.结构化程序设计的三种基本结构的共同特点是（）。

A.只能用来描述简单程序B.不能嵌套使用C.具有单入口和单出口D.仅用于自动控制系统

11.源程序文档化要求在每个模块之前加序言性注释，该注释内容不应有（）。

A.模块的功能B.语句的功能C.模块的接口D.开发历史

12.软件的静态测试方法之一为（）。

A.计算机辅助静态分析B.黑盒法C.因果图D.路径覆盖

13.软件测试的目的是（）。

A.为了证明软件中没有错误B.为了说明软件能够正确地执行C.为了发现软件中的错误D.为了评价软件的质量

14.单元测试针对（）阶段进行测试。

A.需求分析B.详细设计和编码C.详细设计D.概要设计

15.随着计算机软、硬件环境变化而对软件修改的过程，称为（）。

A.校正性维护B.适应性维护C.完善性维护D.预防性维护

三、问答题

1.软件作为一种产品，其特性是什么？

2.简述程序流程图的缺点和克服方法。

3.在软件开发过程中，为增加软件的可移植性，应注意哪些方面？

4.简述快速原型模型的开发步骤。

5.简述软件结构的设计优化准则。

6.需求分析阶段的基本任务是什么？要进行哪几方面的工作？

7.软件测试要经过哪些步骤？简述这些测试的基本任务。

8.面向对象的主要特征有哪些？简要说明其含义。

9.根据下列条件使用边界值分析法设计测试用例。

八进制常数定义为：以零开头的数是八进制整数。某一8位微机，8位带符号数值的范围是一177〜177,如：05,0127,一065表示八进制整型

常数。

10.简述可以在哪些方面提高软件的可维护性。

11.某学校将学生的基本情况文件（简称学生情况文件）和学生期末考试成绩文件（简称成绩文件）合并成一个新文件。学生情况文件包含学生的

学号、姓名、通信地址。成绩文件包含学号和成绩。这两个文件均由学生记录重复组成,学生记录包含以上数据项。新文件的数据结构包含学号、

姓名、通信地址和成绩。

要求：

(1)给出Jackson输入、输出的数据结构图。

(2)用Jackson方法设计该程序结构图。

12.银行柜取款系统有如下功能：

(1)用户用取款卡到柜取款；

(2)如是不合法取款卡，则退回并显示出错；

(3)对用户输入的密码进行确认检杳，非法密码将被拒绝；

(4)核查用户的取款额，超支将被拒绝；

(5)登录一笔合法取款，更新账卡；

(6)生成付款通知，经确认后支付现金。

试根据要求画出该问题的数据流图，并将其转换为软件结构图。

13.下图是一个被测程序的流程图，采用条件覆盖方法为它设计足够的测试用例，使每个条件至少取真、假各一次。试根据所给出的X的4个

取值，将下表填写完整。

14.采用白盒测试法设计，有语句覆盖、条件覆盖.、判定覆盖、路径覆盖等。为了对下图所示的程序段进行覆盖测试，须适当选取测试数据。

若x、y是两个变量，则可供选择的测试数据组共有①、②、③、④四组(如表所示)。试给出：

(1)实现判定覆盖至少应采用的测试数据组；

(2)实现条件覆盖至少应采用的测试数据组。

第二章数据结构概述

一、名词解释数据，数据元索，逻辑结构，存储结构，线性结构，非线性结构，顺序存储结构，链式存储结构，索引存储结构，散列存储结构，

算法，时间复杂度

二、填空题

1.从某种意义上说，数据、数据元素和数据项反映了数据组织的三个层次，数据可由若干个构成，数据元索可由若干个构成。

2.从逻辑关系上讲，数据结构主要分为两大类，它们是和o

3.把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构是。

4.通常从、、等几方面评价算法的质量。

5.常见时间复杂性的量级有：常数阶0()、对数阶0()、线性阶0()、平方阶0()和指数阶0(

6.在一般情况下，一个算法的时间复杂性是的函数。

7.一个算法的时空性能是指该算法的和,前者是算法包含的,后者是算法需要的。三、问答题分析下列

程序段的时间复杂度。

(1)i=l;k=0;

while(i<n){

k=k+10*i;i++;

)

⑵i=l;j=0;

while(i+j<=n){

if(i>j)j++；

elsei++;

)

・第三章线性表

•一、名词解释线性结构，非线性结构，顺序存储结构，链式存储结构，存储密度

二、填空题1.为了便于讨论，有时将含n(n20)个结点的线性结构表示成(由，a?,…，①)，其中每个主代表一个。由称为结点，

a,；称为——结点，i称为ai在线性表中的—对于任意一对相邻结点为、ai称为的直接称为ai的直接

2.线性结构的基本特征是：若至少含有一个结点，则除开始结点没有直接外，其他结点有且仅有一个直接：除终端结点没有直接

______外，其它结点有且仅有一个直接o

3.线性表的逻辑结构是结构。其所含结点的个数称为线性表的,简称o

4.表长为0的线性表称为。5.顺序表的特点是__o

6.假定顺序表的每个datatype类型的结点占用k(k21)个内存单元，b是顺序表的第•个存储结点的第-个单元的内存地址，那么第i个结点

ai的存储地址为o

7.以下为顺序表的删除运算，分析算法，请在处填上正确的语句。

voiddelete_sqlist(sqlist*L,inti)//删除顺序表L中的第iT个位置上的结点

{if((i<l)Tl(i>L->last))error("非法位置”)；

for(j=i+l;j=L->last;j++);

L->last=L->last-l;

)

8.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为，其它结点称为。

9.以下是求带头结点的单链表长度的运算，分析算法，请在处填上正确的语句。

intlength_linklist(linklist*head)〃求表head的长度

2

j=0;

while(p->next!=NULL)

j++；

)

return(j);〃返回表长度

)

10.以下为带头结点的单链表的定位运算，分析算法，请在处填上正确的语句。

intlocate_lklist(Ikiisthead,datatypex)

〃求表head中第个值等于x的结点的序号。不存在这种结点时结果为0

{p=head->next;j=0;

while(){p=p->next;j++;}

if(p->data==x)return(j);

elsereturn(0);

)

11.循环链表与单链表的区别仅仅在于其终端结点的指针域值不是，而是一个指向的指针。

三、选择题1.线性结构中的一个结点代表一个()o

A.数据元素B.数据项C.数据D.数据结构

2.对于顺序表，以下说法错误的是()。

A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址

B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列

C.顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻

D.顺序表的特点是：逻辑上相邻的元素存储在物理位置也相邻的单元中

3.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以()为标准操作。

A.条件判断B.结点移动C.算术表达式D.赋值语句

4.对于顺序表的优缺点，以下说法错误的是()。

A.无需为表示结点间的逻辑关系而增加额外的存储空间B.可以方便地随机存取表中的任•结点

C.插入和删除运算较为方便D.容易造成一部分空间长期闲置而得不到充分利用

5.在循环链表中，将头指针改设为尾指针(rear)后，其头结点和尾结点的存储位置分别是()。

A.real和rear->next->nextB.rear->next和realC.rear->next->next和rearD.rear和rear->next

6.设指针P指向双向链表的某一结点，则双向链表结构的对称性可用()来描述。

A.p->prior->next->==p->next->nextB.p->prior->prior->==p->next->prior

C.p->prior->next->==p->next->priorD.p->next->next==p->prior->prior

7.循环链表的主要优点是()o

A.不再需要头指针B.已知某个结点的位置后，能够容易找到它的直接前趋

C.在进行插入、删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表

8.设rear是指向非空带头结点的循环单链表的尾指针，则删除表首结点的操作可表示为()。

A.p=rear;B.rear=rear->next;

rear=rear->next;free(rear);

free(p)

C.rear=rear->next->next;D.p=rear->next->next;

free(rear);rear->next->next=p->next;

free(p);

9.双向链.结点结构.下：

LLink|data|RLink

其中:LLink是指向前驱结点的指针域：

data是存放数据元素的数据域：

Rlink是指向后继结点的指针域。

F面给出的算法段是要把一个新结点*q作为非空双向链表中的结点*P的前驱，插入到此双向链表中。不能正确完成要求的算法段是()。

A.q->LLink=p->LLink;B.p->LLink=q;

q->Rlink=p;q->Rlink=p;

p->LLink=q;p->LLink->Rlink=q;

p->LLink->Rlink=q;q->LLink=p->LLink;

C.q->LLink=p->LLink;

q->Rlink=p;

p->LLink->Rlink=q;

p->LLink=q;

10.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用()存储方式最节省时间。

A.顺序表B.单链表C.双链表D.单循环链表

四、算法设计1.设A二⑶,a%瓯…出)和B=(E,b%…,b")是两个线性表(假定所含数据元素均为整数)。若n初且吁b(i=l,…，n),则称A二B；

3

若母山（i=l,…，j）J@LaJ+i<bJ+i（j<n<=in）,则称A〈B；在其他情况下均称A>B。试编写一个比较A和B的算法，当A<B,A=B或A>B时，分别输出-1,

0或1。

2.分别以顺序表和单链表作存储结构，各写一个实现线性表的就地（即使用尽可能少的附加空间）逆置的算法，在原表的存储空间内将线性表⑶,

a2••,a）皆[（a.***a?aJ。

’3：g知单链表L'中而结'是按值非递减有序排列的，试写一算法，将值为x的结点插入表L中，使得L仍然有序。

4.已知单链表L是一个递增有序表，试编写一高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除结点

的空间，这里min和max是两个给定的参数。请分析算法的时间复杂度。

5.设A和B是两个单链表，表中元素递增有序。试编写一个算法，将A和B归并成一个按元素值递减有序的单链表C,并要求辅助空间为0（1）,

C表的头结点可另辟空间。请分析算法的时间复杂度。

6.已知一单链表中的数据元素含有三个字符（即字母字符、数字字符和其它字符）。试编写算法，构造三个循环链表，使每个循环链表中只含

同•类的字符，且利用原表中的结点空间作为这三个表的结点空间（头结点可另辟空间）。

7.已知A、B和C为三个元索值递增有序的线性表，现要求对表A作如下运算：删去那些既在表B中出现又在表C中出现的元素。试分别以两

种存储结构（顺序结构和链式结构）编写实现上述运算的算法。

8.假设在长度大于1的循环链表中，既无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。

第四章栈和队列

一、名词解释栈，顺序栈，链栈，队列，顺序队列，循环列队，链队

二、填空题1.栈修改的原则是,因此，栈又称为线性表。在栈顶进行插入运算，被称为,在栈顶进行删除运

算，被称为_______o

2.对于顺序栈而言，top=0表示，此时作退栈运算，则产生“"；top=stack_maxsize-l表示，此时作进栈运算，

则产生“”。

3.以下运算实现在顺序栈上的进栈，请在处用适当的语句予以填充。

intPush（SqStackTp*sq,DataTypex）

{if（sp->top=sqstack_maxsize-1}{printf（"栈满"）;retum（0）;}

else{;

retum(l);

4.顺序队列的出、入队操作会产生“

5.以下运算实现循环队列的初始化，请在处用适当句子予以填充。

voidInitCycQueue（Cycqueue*&sq）

_________________;sq->rear=0;

广

6.链队在一定范围内不会出现的情况。当lq->front==lq->rcar时，称为—

7.以下运算实现在链队上取队头元素，请在处用适当句子予以填充。

intGetFront（LinkQ*lq,DataType*x）

{LinkQ*p；

if（lq->rear==lq->front）return（0）;

else{;

_________________=p->data;

return(1);

)

)

三、选择题1.设有•顺序栈S,元素S],S2,S3,S4,S3,So依次进栈,如果6个元素出栈的顺序是s?,S3,S4,S6,S5,S),则栈的容

量至少应该是()。A.2B.3C.5D.6

2.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）o

A.edcbaB.decbaC.dceabD.abcde

3.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。

A.edcbaB.decbaC.dceabD.abcde

4.设有一顺序栈sq已含3个元素，如下图所乐，元素a4正等待进栈。那么下列4个序

列中不可能出现的出栈序列是（）。

0123maxsize-1

ala2a3

ttop

A.a3,al,a4,a2B.a3,a2,a4,alC.a3,a4,a2,alD.a4,a3,a2,al

4

5.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为（）o

A.Top->next=sB.s->next=Top->next;Top->next=s

C.s->next=Top;Top=sD.s->next=Top;Top=Top->next

6.从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为（）o

A.x=Top->data;Top=Top->nextB.Top=Top->next;x=Top->data

C.x=Top;Top=Top->nextD.x=Top->data

7.循环队列的入队操作应为（）。

A.sq.rear=sq.rear+l;sq.data[sq.rearl=x;B.sq.data[sq.rear]=x;sq.rear=sq.rear+1;

C.sq.rear=（sq.rear+l）%maxsize;sq.data[sq.rear]=x;D.sq.data[sq.rear]二x;sq.rear=（sq.rear+l）%maxsize;

8.循环队列的队空条件为（）o

A.（sq.rear+l）%maxsize==（sq.front+l）%maxsizeB.（sq.rear+l）%maxsize==sq.front+1

C.（sp.rear+l）%maxsize=sq.frontD.sq.rear==sq.front

四、算法设计

1.回文是指从左向右读和从右向左读均相同的字符序列，如“level”是回文，但“good”不是回文。试写•个算法判定给定的字符向量是否

为回文。（提示：将一半字符入栈，然后出栈与另一半字符进行比较。）

2.借助栈（可用栈的基本运算）来实现单链表的逆置运算。

3.利用栈的基本运算将栈S中值为m的元素全部删除。

4.假设一个算术表达式中包含三种括号：圆括号“（”和“）”，方括号和以及花括号和“}”，且这三种括号可按任意的次

序嵌套使用，如.

（试利用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法intcorrect（exp）；其中exp为字符串类型的变量。

如果括号正确配对,则返回值正否则返回值0。（提示：对表达式进行扫描,凡遇到“正、T或就入栈，当遇到“）”、或“}”时,

检查当前栈顶元素是否是对应的左括号，若是就退掉栈顶的“（”、或“{"，否则不配对。表达式扫描完毕，栈应为空。）

5.设函数f（m,n）按下式定义（m,n为大于0的整数）：

m+n+1当m*n=0时

f(m,n)=

f(m-l,f(m,n-1))当m*nw()时

试写出递归算法。

6.假设以数组cycque[m]（假设数组范围在存放循环队列的元素，同时设变量

rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并

写出相应的入队列和出队列的算法。

第五章串和数组

一、名词解释

串，顺序串，链串，特殊矩阵，稀疏矩阵，对称方阵，上（下）三角矩阵

二、填空题

1.含零个字符的串称为串，用表示。其他串称为串。任何串中所含的个数称为该串的长度。

2.当且仅当两个串的相等并且各个前应位置上的字符都时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的—

串，该串称为它所有子串的串。

3.通常将链串中每个存储结点所存储的字符个数称为。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占

满，此时，应在这些未用的数据域里补上0

4.一般地，一个n维数组可视为其数据元素为维数组的线性表。数组通常只有和两种基本运算。

5.通常采用——存储结构来存放数组。对二维数组可有两种存储方法：一种是以——为主序的存储方式，另一种是以—为匕序的存

储方式。C语言数组用的是以序为主序的存储方法。

6.数组M中每个元素的长度是3个字节，行下标i从1到8,列下标j从1到10,从首地址EA开始连续存放在存储器中。若按行方式存放，

则元素M[8][5]的起始地址为：若按列优先方式存放，则元素的地址为。

7.二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需

要个字节；M的第8列和第5行共占个字节：若M按行方式存储，元索M[8][5]的起始地址与当M按列优先方式存储时的元素

的起始地址一致。

8.需要压缩存储的矩阵可分为矩阵和矩阵两种。

9.对称方阵中有近半的元素重复，若为每一对元素只分配一个存储空间，则可将n2个元索压缩存储到个元素的存储空间中。

10.假设以一维数组M（l..n（n+l）/2）作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组M和矩阵A间

对应的关系为。

11.上三角矩阵中，主对角线上的第t行（lWtWn）有个元素，按行优先顺序在一维数组M中存放上三角矩阵中的元素加时，a-i之前的

前iT行共有_______个元素，在第i行上，a.是该行的第个元素，M[k]和以的对应关系是C当i>j时，a『c（c表示常量），c存放

在M[]中。

三、选择题

1.在串的基本运算中，能够改变串值的运算有（）o

A.EQAL（S,T）B.LENGTH（S）C.C0NCAT（S,T）D.REPLACE（S,T,R）E.INDEX（S,T）

2.在串的基本运算中，不能够改变串值的运算有（）o

5

A.ASSIGN(S,T)B.INSERT(SI,i,S2)C.DELETE(S,i,j)D.SUBSTR(S,i,j)E.REPLACE(S,T,R)

3.对于以行序为主序的存储结构来说，在数组A[cl..dl,c2..d2]中，cl和di分别为数组A的第一个下标的下界和上界，c2和d2分别为第

二个下标的下界和上界，每个数据元素占K个存储单元，二维数组中任一元素a[i,j]的存储位置可由()式确定。

A.Loc(i,j)=Loc(cl,c2)+[(i-cl)*(d2-c2)+(j-c2)]*kB.Loc(i,j)=Loc(cl,c2)+[(i-cl)*(d2-c2+l)+(j-c2)]*k

C.Loc(i,j)=Loc(cl,c2)+[(j-c2)*(d1-c1+1)+(i-cl)]*kD.Loc(i,j)=Loc(cl,c2)+[(j-c2)*(dl-cl)+(i-cl)]*k

4.对于C语言的二维数组DataType每个数据元素占K个存储单元，二维数组中任意元素a[i,j]的存储位置可山()式确定。

A.Loc(i,j)=Loc(0,0)+[i*(n+l)+j]*kB.Loc(i,j)=Loc(0,0)+[j*(m+l)+i]*k

C.Loc(i,j)=Loc(0,0)+(i*n+j)*kD.Loc(i,j)=Loc(0,0)+(j*m+i)*k

5.稀疏矩阵的压缩存储方法是只存储()o

A.非零元素B.三元组（i,j,an）C.aijD.i,j

6.基于三元组表的稀疏矩阵，对每个非零元素aij,可以用•个（）唯•确定。

A.非零元素B.三元组（i,j,aQC.adD.i,j

7.二维数组的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从。到4,列下标j的范围从0到5。若M按行存

储，元素M[3,5]的起始地址与M按列存储时，元素（）的起始地址相同。

A.M[2,4]B.M[3,4]C.M[3,5]D.M[4,4]

8.常对数组进行的两种基本操作是（）o

A.建立与删除B.建立与修改C.查找与修改D.查找与索引

四、问答及算法设计

1.简述下列各对术语的区别。

空用和空格串；串变量和串常量；主串和子串；串变量的名字与串变量的值

2.设有A=""，B="mule"，C="old”,D="my”，试计算下列运算的结果（注：A+B是C0NCAT（A,B）的简写，A=””表示含有两个空

格的字符串）。

(a)A+B(b)B+A

(c)D+C+B(d)SUBSTR(B,3,2)

(e)SUBSTR(C,1,0)(f)LENGTH(A)

(g)LENGTH(D)(h)INDEX(B,D)

⑴INDEX©“d”)(j)INSERT(D,2,C)

(k)INSERT(B,1,A)(1)DELETE(B,2,2)

(m)DELETE(B,2,0)

3.分别在顺序串和链串上实现串的判相等运算EQUAL（S,T）o

4.若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针）,设计一个算法将串S中首次与串T匹配的子串逆置。

5.用串的其他运算构造串的子串定位运算indexo

6.利用C的库函数strlen>strcpy和streat写一算法voidStrTnsert（char*S,char*T）,将串T插入到串S的第i个位置上。若i大于S的

长度，则插入不执行。

7.利用C的库函数strlen、strcpy和strnepy写一算法voidStrDelete（char*S,inti,intm）,删去串S中从位置i开始的连续m个字符。

若i2strlen（S）,则没有字符被删除；若i+m，strlen（S）,则将S中从位置i开始直至末尾的字符均删去。

8.设有三对角矩阵A,”将其三条对角线上的元素逐行存于数组A（1..3n-2）中，使得A[k]二即。求：

（1）用i、j表示k的下标变换公式；

（2）用k表示i、j的下标变换公式。

9.编写算法：将稀疏矩阵按行优先的顺序存储到三元组表中。

10.稀疏矩阵以三元组表作为存储结构，试写一算法实现两个稀疏矩阵相加，结果仍存放在三元组表中。

11.若在矩阵Ax。中存在•个元素满足：是第i行元素中的最小值，且又是第j列元素中的最大值，则称此元素为该矩阵的•个马鞍点。

假设以二维数组存储矩阵A,.x„,试设计求出矩阵中所有马鞍点的算法。

第六章树

一、名词解释

树，结点的度，叶子，树的度，父结点，子结点，兄弟，结点的层数，树的高度，二叉树，左孩子，右孩子，满二叉树，完全二叉树，哈夫曼树

二、填空题

1.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为o

2.假定一棵二叉树的结点数为18个，则它的坡小高度是,最大高度是o

3.在一棵二叉树中第4层上的结点数最多为。

4.山分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为o

5.如果结点A有三个兄弟，而且B是A的双亲，则B的出度是o

6.在完全二叉树中，当i为奇数且不等于1时，结点i的左兄弟是结点,否则没有左兄弟。

7.对于一棵具有n个结点的树，该树中所有结点的度之和为o

8.在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为；若它存在左孩子，则左孩子结点的下标为:若它存

在右孩子，则右孩子结点的下标为

9.在一棵二叉排序树中，按遍历得到的结点序列是一个有序序列。

三、选择题

1.以下说法错误的是（）。

A.树形结构的特点是一个结点可以有多个直接前趋B.树形结构可以表达（组织）更复杂的数据

C.树（及一切树形结构）是一种“分支层次”结构D.任何只含一个结点的集合是一棵树

6

2.以下说法错误的是()。

A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点

C.若初始森林中共有n棵二叉树，则最终求得的哈夫曼树共有2nT个结点

D.若初始森林中共有n棵二叉树，则进行2nT次合并后才能剩下一棵最终的哈夫曼树

3.深度为6的二叉树最多有()个结点。

A.64B.63C.32D.31

4.任何一棵二叉树的叶结点在其先序、中序、后序遍历序列中的相对位置()。

A.肯定发生变化B.有时发生变化C.肯定不发生变化D.无法确定

5.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少为()个。

A.k+1B.2kC.2k-1D.2k+l

6.•棵二叉树满足下列条件：对于任意结点，其值都大于它的左子树上所有结点的值，而小于右子树上所有结点的值。现采用()遍历方式

就可以得到这棵二叉树所有结点的递增序列。

A.先序B.中序C.后序D.层次

7.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的先序遍历序列是()。

A.acbedB.deabcC.decabD.cedba

四、简答及算法设计

1.画出山3个结点所构成的所有形态的树(假设是无序树)。

2.一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次自顶向下，同一

层自左向右从1开始对全部结点进行编号，试问：

(1)各层的结点个数是多少？

(2)编号为i的结点的双亲结点(若存在)的编号是多少？

(3)编号为i的结点的第m个孩子结点(若存在)的编号是多少？

(4)编号为i的结点有右兄弟的条件是什么？右兄弟结点的编号是多少？

3.分别描述满足下面条件的二叉树的特征：

(1)先序序列和中序序列相同。

(2)先序序列和后序序列相同。

(3)中序序列和后序序列相同。

4.已知某二叉树的先序遍历序列为ABC,试画出能得到这一结果的所有二叉树。

5.已知二叉树的后序序列DECBGIHFA和中序序列DCEBAFHGL画出这棵二叉树。

6.分别设计出先序和后序遍历二叉树的非递归算法。

7.已知二叉树采用二叉链表存储结构，编写•个算法，交换二叉树所有左、右子树的位置，即结点的左r树变为结点的右子树，右子树变为左

子树。

8.采用二叉链表结构存储一棵二叉树，编写一个算法，删除该二叉树中数据值为x的结点及其子树，并且输出被删除的子树。

9.试以三种遍历为基础，分别写出在二叉树上杳找指定结点的直接前趋或直接后继的算法。

10.已知树(森林)的高度为4,所对应的二叉树的先序序列为ABCDE,请构造出所有满足这一条件的树或森林。

H.将深度为4的满二叉树转换为对应的树或森林。

12.已知结点序列{21,18,37,42,65,24,19,26,45,25},画出相应的二叉排序树,并画出删除结点37后的二叉排序树。

13.试编写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。

14.设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7、19、2、6、32、3、21、10,试为这8个字母设计相应的哈夫曼编码。

第七章图

一、名词解释

图，无向完全图，有向完全图，子图，连通分量，图的遍历，图的最小生成树，拓扑排序

二、填空题

1.一个具有n个顶点的完全无向图的边数为o一个具有n个顶点的完全有向图的弧度数为o

2.设x,y£V,若<x,y>£E,贝U<x,y>表示有向图G中从x到y的一条,x称为点，y称为点。若(x,y)EE,则在无向图

G中x和y间有一条o

3.在无向图中，如果从顶点v到顶点v'有路径，则称v和g是的。如果对于图中的任意两个顶点v“Vj£V,且H和巧都是连通的，

则称G为o

4.连通分量是无向图中的连通子图。

5.若连通图G的顶点个数为n,则G的生成树的边数为o如果G的一个子图G'的边数,则G'中一定有环。相反，如果G'的

边数,则C一定不连通。

6.对于无向图的邻接矩阵，顶点v.的度是。对于有向图的邻接矩阵，顶点心的出度OD(v)为,顶点v,的入度ID(v)为o

7.图的深度优先搜索遍历类似于树的遍历，它所用到的数据结构是;图的广度优先搜索遍历类似于树的

遍历，它所用到的数据结构是o

8.一个图的表示法是唯一的，而表示法是不唯一的。

9.在有向图的邻接矩阵上，由第i行可得到第个结点的出度，而由第j列可得到第个结点的入度。

10.在无向图中，所有顶点的度数之和是所有边数的

倍，在有向图中，所有顶点的入度之和是所有顶点出度之和的倍。

11.以下是图的深度优先算法，请在处填充

当的语句。

voidDFS(GraphTpg,intv)7

{ArcNodeTp*p;

printf("%d",v);

三、选择题

1.设有无向图G=(V,E)和G'=(『，E'),如G'为G的生成树，则下面不正确的说法是()。

A.G'为G的子图B.G'为G的连通分量C.G'为G的极小连通子图且小二VD.G'是G的无环子图

2.任何一个带权的无向连通图的最小生成树()。

A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在

3.在无向图中，所有顶点的度数之和是所有边数的()倍。

A.0.5B.1C.2D.4

4.在有向图中，所有顶点的入度之和是所有顶点出度之和的()倍。

A.0.5B.1C.2D.4

5.设有6个结点的无向图，该图至少应有()条边能确保是一个连通图。

A.5B.6C.7D.8

6.以下说法中错误的是()。

A.用相邻矩阵法存储一个图时;在不考虑压缩存储的情况下，所占用的存储空间的大小只与图中结点个数有关，而与图的边数无关

B.邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用

C.存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下(或上)三角部分就可以了

D.用相邻矩阵A表示图，判定任意两个结点v,和明之间是否有长度为m的路径相连，则只要检查A的第i行第j列的元素是否为0即可

四、简答及算法设计

1.写出将一个无向图的邻接矩阵转换成邻接表的算法。

2.写出将一个无向图的邻接表转换成邻接矩阵的算法。