数据结构课程课后习题答案

《数据结构简明教程》练习题及参考答案

练习题工

1.单项选择题

（1）线性结构中数据元素之间是（）关系。

A.一对多B.多对多C.多对一D.一对一

答：D

（2）数据结构中与所使用的计算机无关的是数据的（）结构。

A.存储B.物理C.逻辑D.物理和存储

答：C

（3）算法分析的目的是（）»

A.找出数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性

答：C

（4）算法分析的两个主要方面是（）o

A.空间复杂性和时间复杂性B.正确性和简明性

C.可读性和文档性D.数据复杂性和程序复杂性

答：A

（5）计算机算法指的是（）o

A.计算方法B.排序方法C.求解问题的有限运算序列D.调度方法

答：C

（6）计算机算法必须具备输入、输出和（）等5个特性。

A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

答：B

2.填空题

（1）数据结构包括数据的巫、数据的且和数据的&这三个方面的内容。

答：①逻辑结构②存储结构③运算

（2）数据结构按逻辑结构可分为两大类，它们分别是①和②。

答：①线性结构②非线性结构

（3）数据结构被形式地定义为（D,R）,其中D是-QJ1勺有限集合，R是D上的②有

限集合。

答：①数据元素②关系

(4)在线性结构中，第一个结点巫前驱结点，其余每个结点有且只有1个前驱结点；

最后一个结点a后继结点，其余每个结点有且只有1个后继结点。

答：①没有②没有

(5)在树形结构中，树根结点没有上》结点，其余每个结点有且只有w个前驱结点;

叶子结点没有血，吉点，其余每个结点的后继结点数可以是

答：①前驱②1③后继④任意多个

(6)在图形结构中，每个结点的前驱结点数和后继结点数可以是()。

答：任意多个

(7)数据的存储结构主要有四种，它们分别是®_、a、⑶和⑷存储结构。

答：①顺序②链式③索引④哈希

(8)一个算法的效率可分为①效率和②效率。

1答：①时间②空间

3,简答题

(1)数据结构和数据类型两个概念之间有区别吗

答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据

类型不仅定义了一组数据元素，而且还在其上定义了一组操作。

(2)简述线性结构、树形结构和图形结构的不同点。

答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关

系是一对多的，图在结构反映结点间的逻辑关系是多对多的。

(3)设有采用二元组表示的数据逻辑结构S=(D,R),其中D={a,b,...,i},

^={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)},问相对于关系R,哪些结点是开始结点，哪些结

点是终端结点

答：该逻辑结构为树形结构，其中a结点没有前驱结点，称为根结点，b、e、g、/•结

点没有后继结点，是终端结点，也称为叶子结点。

(4)以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度：

T1(n)=nlog2n-1000log2n

/

T2(n)=/ilog25-1000log2n

T3(n)=/?2-1000log2n

T4(n)=2nlog2n-1000log2n

答：T1(n)=O(nlog2n),T2(n)=O(m°g:,T3(n)=O(nz),T4(n)=O(nlog2n)o

(5)分析下面程序段中循环语句的执行次数。

intj=Ozs=O,n=lOO;

do

{j=j+l;

s=s+10*j;

}while(j<n&&s<n);

皆：j=0,第1次循环：j=l,s=10o第2次循环：j=2,s=30o第3次循环：j=3,s=60。第

4次循环：7=4,s=100owhile条件不再满足。所以，其中循环语句的执行次数为4。

(6)执行下面的语句时，语句S++的执行次数为多少

ints=0;

for(i=l;i<n-l;i++)

for(j=n;j>=i;j-)

s++；

答：语句s的执行次数£21=它(〃-，+1)=〃+5-1)++3=(〃+3)5-2)。

2

f=lj=ni=\

(7)设n为问题规模，求以下算法的时间复杂度。

voidfunl(intn)

{intx=0J;

i

for(i=l;i<=n;i++)

for(j=i+l;j<=n;j++)

x++;

答：其中x++语句属基本运算语句，T(〃)=XZi=Z(〃_i)=M0=om2)。

2

islj=i+\i=l

(8)设n为问题规模，是一个正偶数，试计算以下算法结束时m的值，并给出该算

法的时间复杂度。

voidfun2(intn)

{intm=0;

for(i=l;i<=n;i++)

for(j=2*i;j<=n;j++)

(

m++;

)

答：由于内循场的取值范围，所以Wr?/2,则加=2}-⑵-1))="2/4,该程

z-1j=2ii=\

序段的时间复杂度为0(。2)。

上机实验题1

有一个整型数组a,其中含有n个元素，设计尽可能好的算法求其中的最大元素和次大

元素，并采用相关数据测试。

解：maxs算法用于返回数组a[O..n-l]中的最大元素值maxi和次大元素值max2,maxi和

max2设计为引用类型。对应的程序如下：

#include<>

voidmaxs（inta[],intn,int&maxl,int&max2）

{inti;

maxl=max2=a[0];

for（i=l;i<n;i++）

if（a[i]>maxl）

{max2=maxl;

maxl=a[i];

）

elseif（a[i]>max2）

max2=a[i];

）

voidmain（）

{inta口={1,4,10,6,8,3,5,7,9,2};

intn=10;

intmaxl,max2;

maxs（a,n,maxl,max2）;

printf（"最大元素值二％d，次大元素值=%d\n”,maxLmax2）;

}

练习题2

i.单项选择题

（1）数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序相同并且是连续的，

称之为（）。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构

答：C

'（2）在n个结点的顺序表中，算法的时间复杂度是。（1）的操作是（）0

A.访问第i个结点（l</<n）和求第i（24/Vn）个结点的前驱结点

B.在第/•（14必?）个结点后插入一个新结点

C.删除第i个结点（14必7）

D.将n个结点从小到大排序

答：A

（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要

移动（）个元素。

答：B

（4）链式存储结构所占存储空间（）0

A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

B.只有一部分，存放结点值

C.只有一部分，存储表示结点间关系的指针

D.分两部分，一部分存放结点值，另一部分存放结点所占单元数

答：A

（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）=

A.必须是连续的B.部分地址必须是连续的

C.一定是不连续的D.连续或不连续都可以

答：D

（6）一个线性表在（）情况下适用于采用链式存储结构。

'A.需经常修改其中的结点值B.需不断对其进行删除插入

C.其中含有大量的结点D.其中结点结构复杂

答：B

（7）单链表的存储密度（）

A.大于1B.等于1C.小于1D.不能确定

答：C

2.填空题

（1）在顺序表中插入或删除一个元素时，需要平均移动（①）元素，具体移动的元

素个数与（②）有关。

答：①表中一半②表长和该元素在表中的位置

（2）向一个长度为。的顺序表的第/•个元素（l</<n+l）之前插入一个元素时，需向后

移动（）个元素。

答：n-i+1

（3）向一个长度为。的顺序表中删除第，个元素（l</<n）时，需向前移动（）个元

素。

答：n-i

（4）在顺序表中访问任意一个元素的时间复杂度均为（①），因此顺序表也称为

（②）的数据结构。

答：①0（1）②随机存取

（5）顺序表中逻辑上相邻的元素的物理位置（①）相邻。单链表中逻辑上相邻的元

素的物理位置（②）相邻。

答：①一定②不一定

（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（）指示。

答：其前驱结点的链域的值

（7）在含有n个数据结点的单链表中要删除己知结点*p,需找到它的（①），其时

间复杂度为（②）o

'答：①前驱结点的地址②。（川

（8）含有n（n>l）个结点的循环双向链表中，为空的指针域数为（）。

答：0

3.简答题

（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好

答：顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元

的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素

时不方便。

链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放

结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用

灵活；缺点是存储密度小，存储空间利用率低。

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线

性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，

且其主要操作是插入、删除操作，则采用链表。

（2）对于表长为〃的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入

一个元素所需要移动的元素的平均个数为多少删除一个元素所需要移动的平均个数为多少

答：插入一个元素所需要移动的元素的平均个数为什1）/2,删除一个元素所需要移动

的平均个数为n/2。

（3）在链表中设置头结点的作用是什么

答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链

表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。

（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少

个

答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后

继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。

对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入

结点的next域。所以共修改两个指针。

（5）某含有n（n>l）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和

删除第一个结点，则采用以下哪种存储方式最节省运算时间。

①单链表；

②仅有头指针不带头结点的循环单链表；

③双链表；

④仅有尾指针的循环单链表。

答：在单链表中，删除第一个结点的时间复杂度为0(1)。插入结点需找到前驱结点，

所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为0(川。

在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度0(川，因为

删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也

为0(")。

在双链表中，删除第一个结点的时间复杂度为。⑴；在尾结点之后插入一个结点，也

需找到尾结点，对应的时间复杂度为om)。

在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第

一个结点的时间复杂度为。(1);在尾结点之后插入一个结点也就是在尾指针所指结点之后

插入一个结点，时间复杂度也为0(1)。因此④最节省运算时间。

4.算法设计题

(1)设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为0(1)。

解：遍历顺序表L的前半部分元素，对于元素W(0WY2),将其与后半部分对应元素

口进行交换。对应的算法如下：

voidreverse(SqList&L)

{inti;

ElemTypex;

[

for(i=0;i<2;i++)

{x=[i]；j]。的初值为o)中没有重复的元素。检测H(；</-<),若口

和[0/中任何一个元素都不相同，则将[/]存入[/+1]中。对应的算法如下：

voiddelsame(SqList&L)j]中所有元素都不相同

{j++；

[j]=[i]；

)

)

=j+l;0],置e=[0],用j从1开始遍历L的所有元素：当[Z]We时，

将它放在因中，k增1,置e=[/],最后将L的length置为鼠对应的算法如下：

voiddelsamel(SqList&L)单项选择题

(1)栈中元素的进出原则是()o

'A.先进先出B.后进先出C.栈空则进D.栈满则出

答：B

(2)设一个栈的进栈序列是A、B、C、D(即元素A〜D依次通过该栈)，则借助该栈

所得到的输出序列不可能是()。

,B,C,D,C,B,A,C,D,B,A,B,C

答：D

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

答：C

（4）已知一个栈的进栈序列是1,2,3,…，n,其输出序列的第一个元素是/.（lWi

则第j（lW/Wn）个出栈元素是（）。

+1D.不确定

&

答：D

（5）设顺序栈st的栈顶指针top的初始时为-1,栈空间大小为MaxSize,则判定st栈

为栈空的条件为（）o

答：A

（6）设顺序栈st的栈顶指针top的初始时为-1,栈空间大小为MaxSize,则判定st栈

为栈满的条件是o

答：D

（7）队列中元素的进出原则是（）。

A.先进先出B.后进先出C.栈空则进D.栈满则出

答：A

（8）元素A、B、C、D顺序连续进入队列qu后，队头元素是（①），队尾元素是

（②）o

}

答：①A②D。

（9）一个队列的入列序列为1234,则队列可能的输出序列是（）□

答：B

（10）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队

尾元素的位置）的队满条件是（）«

A.+l）%MaxSize==+l）%MaxSize

B.+l）%MaxSize==+l

C.+l）%MaxSize==

"答：c

（11）循环队列qu（队头指针front指向队首元素的前一位置，队尾指针rear指向队

尾元素的位置）的队空条件是（）。

A.+l）%MaxSize==+l）%MaxSize

B.+l）%MaxSize==+l

C.+l）%MaxSize==

答：D

（12）设循环队列中数组的下标是0〜N-l,其头尾指针分别为/和r（队头指针/指向

队首元素的前一位置，队尾指针r指向队尾元素的位置），则其元素个数为（）o

C.（r-/）%N+1D.（r->N）%N

答:D

"（13）设有4个数据元素a、b、c和d,对其分别进行栈操作或队操作。在进栈或进

队操作时，按a、b、c、d次序每次进入一个元素。假设栈或队的初始状态都是空。现要进

行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元

素是（①），第二次出栈得到的元素是（②）;类似地，考虑对这4个数据元素进行的

队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是

（③），第二次出队得到的元素是（④）。经操作后，最后在栈中或队中的元素还有（⑤）

个。

①〜④：

⑤：

答：①B②D③A④B⑤B

（）设栈和队列的初始状态为空，元素〜依次通过栈一个元素出后即

14SQq1OS,

进队列Q,若6个元素出队的序列是eZ,、戛4、q3、e«O、0e1.则栈S的容量至少应该是（）。

答：C

2.填空题

（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为（①）o不允许插入

和删除运算的一端称为（②）o

答：①栈顶②栈底

（2）一个栈的输入序列是12345,的输出序列为12345,其进栈出栈的操作为（）。

答：1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，5进栈，5

出栈。

（3）有5个元素，其进栈次序为A、B、C、D、E,在各种可能的出栈次序中，以元素

C、D最先出栈（即C第一个且D第二个出栈）的次序有（）。

答：CDBAE、CDEBA、CDBEA。

（4）顺序栈用data。.”叫存储数据，栈顶指针为top,其初始值为0,则元素x进栈

的操作是（）«

答：data[top]=x;top++;

（5）顺序栈用data。.存储数据，栈顶指针为top,其初始值为0,则出栈元素x

的操作是（）。

答：top-;x=data[top];

（6）（）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线

性表。

答：队列

,（7）设有数组作为循环队列的存储空间，front为队头指针（它指向队首元素

的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素x执行入队的操作是（）。

答：rear=（rear+l）%（m+l）;A[rear]=x;

（8）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素

的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素出队并保存到x中的操

作是（）。

答：front=（front+l）%（m+l）;x=A[rear];

3.简答题

（1）简要说明线性表、栈与队的异同点。

答：相同点：都属地线性结构，都可以用顺序存储或链表存储；栈和队列是两种特殊

的线性表，即受限的线性表，只是对插入、删除运算加以限制。

不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除

运算，因而是后进先出表UFO；队列是只允许在一端进行插入、另一端进行删除运算，因

而是先进先出表FIFO。②用途不同，栈用于子程调用和保护现场等，队列用于多道作业处

理、指令寄存及其他运算等等。

（2）顺序队的“假溢出”是怎样产生的如何知道循环队列是空还是满

答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有进队操作，但其实

数组中还有空位置，这就叫“假溢出”。

采用循环队列是解决假溢出的途径。另外，解决循环队列是空还是满的办法如下：

①设置一个布尔变量以区别队满还是队空；

②浪费一个元素的空间，用于区别队满还是队空。

③使用一个计数器记录队列中元素个数（即队列长度）。

通常采用法②，让队头指针front指向队首元素的前一位置，队尾指针rear指向队尾

元素的位置，这样判断循环队列队空标志是：front=rear,队满标志是：

（rear+l）%MaxSize=fronto

4.算法设计题

（1）假设采用顺序栈存储结构，设计一个算法，利用栈的基本运算返回指定栈中栈底

元素，要求仍保持栈中元素不变。这里只能使用栈st的基本运算来完成，不能直接用⑼

来得到栈底元素。

解：假定采用顺序栈结构。先退栈st中所有元素，利用一个临时栈tmpst存放从st栈

中退栈的元素，最后的一个元素即为所求，然后将临时栈tmpst中的元素逐一出栈并进栈

到St中，这样恢复St栈中原来的元素。对应算法如下:

intGetBottom(SqStackst,ElemType&x)

{ElemTypee;

队尾

2

SqStacktmpst;单项选

择题

（1）串是一种特殊的线性表，其特殊性体现在（）。

A.可以顺序存储B.数据元素是一个字符

C.可以链式存储D.数据元素可以是多个字符

答：B

（2）以下（）是2bcd32〃BCD"串的子串。

A.abedC."abcABC"D."21AB"

答：D

（3）两个串相等必有串长度相等且（）。

A.串的各位置字符任意B.串中各对应位置字符均相等

C.两个串含有相同的字符D.两个所含字符任意

答：B

2.填空题

（1）空串是指（①）,空白串是指（②）»

答：①不包含任何字符（长度为0）的串②由一个或多个空格（仅由空格符）组成的

（2）对于带头结点的链串s,串为空的条件是（）o

答：s->next==NULL0

（3）对于一个含有n个字符的链串s,查找第，・个元素的算法的时间复杂度为（）o

答：0（川

3.简答题

（1）设s为一个长度为n的串，其中的字符各不相同，则s中的互异的非平凡子串（非

空且不同于s本身）的个数是多少

答：由串s的特性可知，1个字符的子串有。个，2个字符的子串有力1个，3个字符

的子串有“2个，…，”2个字符的子串有3个，个字符的子串有2个。所以，非平凡

子串的个数=n+m-l）+m-2）+...+2=+D-1o

2

（2）若si和s2为串，给出使si算法设计题

（1）设计一个算法RepChar（s,x,y）,将顺序串s中所有字符x替换成字符y。要求空间

复杂度为。(1)。

解：因要求算法空间复杂度为0(1),所以只能对串s直接替换。从头开始遍历串s,一

旦找到字符x便将其替换成人对应算法如下：

voidRepStrfSqString&s,charx,chary)

{inti;

for(i=0;i<;i++)

if[i]==x)

[i]=y;

}

(2)设计一个算法，判断链串s中所有元素是否为递增排列的。

解：用p和q指向链串s的两个连续结点，p先指向开始结点，当q->data>p->data时，

P和q同步后移一个结点；否则返回0。当所有元素是递增排列时返回1。对应算法如下：

intincrease(LinkString*s)

{LinkString*p=s->next,*q;

if(p!=NULL)

{while(p->next!=NULL)

{q=p->next;单项选择题

(1)假设有60行70列的二维数组a[1..60,1..70](数组下标从1开始)以列序为主序

顺序存储，其基地址为10000,每个元素占2个存储单元,那么第32行第58列的元素仇32,58]

的存储地址为()。

D.以上都不对

答：A

(2)对特殊矩阵采用压缩存储的目的主要是为了()0

A.表达变得简单B.对矩阵元素的存取变得简单

C.去掉矩阵中的多余元素D.减少不必要的存储空间

答：D

(3)一个ex”的对称矩阵，如果采用压缩存储以行或列为主序放入内存，则压缩存储

的容量是()。

A.n2B.n2/2C.n(n+l)/2D.(n+l)2/2

答：C

(4)设矩阵。是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数

组团1..川小1)/2]中(数组下标均从1开始)，对下三角部分中任一元素%(均)在一维数组

b中下标k的值是()。

(/-1)Z2+J-1(/-1)/2+7(/+1)/2+;-1(/+1)/2+；

答：B

(5)有一个二维数组4行下标的范围是0~8,列下标的范围是1〜5,每个数组元

素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素40,1]的第一个字节的

地址是0o存储数组A的最后一个元素的第一个字节的地址是（①）«若按行存储，则

43,5]和祖5,3]的第一个字节的地址分别是（②）和（③）。若按列存储，则47,1]和

42,4]的第一个字节的地址分别是（④）和（⑤）。

答：①H②C③E④A⑤F

（6）有一个二维数组4行下标的范围是1~6,列下标的范围是0〜7,每个数组元

素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是（①）个字节。

假设存储数组元素4L0]的第一个字节的地址是0,则存储数组A的最后一个元素的第一个

字节的地址是（②）o若按行存储，则42,4]的第一个字节的地址是（③）o若按列存

储，则45,7]的第一个字节的地址是（④）o

答：①L②J③C④I

（7）稀疏矩阵一般的压缩存储方法有两种，即（）。

-A.二维数组和三维数组B.三元组和散列

C.三元组和十字链表D.散列和十字链表

答：C

2.填空题

（1）.三维数组4忙1..432.吊2了3..€13]C，C24d2，C34d3）共含有（1个元素。

（d^+ljxfd^+ljxfd^+ljo

（2）已知二维数组/涧㈤采用行序为主方式存储，每个元素占k个存储单元，并且

第一个元素的存储地址是LOC伏⑼⑼），则的地址是（）0

答：LOC（A[0][0]）+（nx/+7）x^o

（3）二维数组410][20]采用列序为主方式存储，每个元素占一个存储单元，并且40][0]

的存储地址是200,则A⑹[12]的地址是（）0

答:326

（4）二维数组410..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并

且410]⑸的存储地址是1000,则418][9]的地址是（）。

答：1208

（5）有一个10阶对称矩阵4,采用压缩存储方式（以行序为主存储下三角部分，且

A[0][0]存放在B⑴中）,则A⑻⑸在B中的地址是（）0

答：42

（6）设"阶下三角矩阵41..川[L.用已压缩到一维数组中，若按行序为主

存储，则人用切对应的S中的存储位置是（）。

答:i(i-l)/2+j0

(7)稀疏矩阵的三元组表示中，每个结点对应于稀疏矩阵的一个非零元素，它包含有

三个数据项，分别表示该元素的()o

答：行下标、列下标和元素值

3.算法设计题

(1)假定数组40..C-1]的n个元素中有多个零元素，设计一个算法将八中所有的非零

元素依次移到4的前端。

"解：从前向后找为零的元素/小从后向前找非零的元素A[/]，将人口和A[/]进行交换。

对应的算法如下：

voidmove(ElemTypeA[],intn)

{inti=O,j=n-l;

ElemTypetmp;

while(i<j)

{while(A[i]!=0)i++;

while(A[j]==O)j-;

ifg)

{tmp=A[i];

A[i]=AU];

)

A[j]=tmp;

}

}

}

(2)已知一个cx“矩阵8按行优先存于一个一维数组中，试给出一个就地

算法将原矩阵转置后仍存于数组人中。

解：矩阵转置是将矩阵中第/•行第j列的元素与第/行第j列的元素互换位置。因此先

应确定矩阵与一维数组的映射关系：％在一维数组八中的下标为，•〜"+/,如在一维数组A

中的下标为/xn+j。对应的算法如下：’

voidtrans(ElemTypeA[],intn)

{inti,j;

ElemTypetmp;

for(i=0;i<n;i++)

for(j=O;j<i;j++)

{tmp=A[i*n+j];

A[i*n+j]=A[j*n+i];

A[j*n+i]=tmp;

)

（3）如果矩阵人中存在这样的一个元素八口口满足条件：44U］是第/•行中值最小的元

素，且又是第/列中值最大的元素，则称之为该矩阵的一个马鞍点。设计一个算法求出mxn

的矩阵A的所有马鞍点。

解：先求出每行的最小值元素，放入min［m］之中，再求出每列的最大值元素，放入

max［c］之中,若某元素既在minp］中,又在max［/］中，则该元素川/］［/］便是马鞍点,找出所

有这样的元素，即找到了所有马鞍点。实现程序如下：

#include<>

#definem3

#definen4

voidminmax(intA[m][n])

{inti,j,have=0;

intmin[m],max[n];

for(i=0;i<m;i++)n]之中

{max[j]=A[O]0]；

for(i=l;i<m;i++)

if(A[i][j]>max[j])

max[j]=A[i][j];

}

for(i=0;i<m;i++)单项选择题

（1）树最适合用来表示（）o

A.有序数据元素B.无序数据元素

C.元素之间具有层次关系的数据D.元素之间无联系的数据

答：C

（2）树是结点的有限集合，它（①）根结点，记为T。其余的结点分成为m（m>0）

个（②）的集合Tj丁2、…、，每个集合又都是树，此时结点称为的双亲结点,

TmT।T,

立称为T的子树（14/Vm）。一个结点的子树个数为该结点的（③）o

①：A.有0个或1个B.有0个或多个C.有且只有1个D.有1个或1个以上

②：A.互不相交B.允许相交C.允许叶结点相交D.允许树枝结点相交

③：A.权B.维数C.次数（或度）D.序

答：①A②A③C

（3）二叉树（①）。在完全的二叉树中，若一个结点没有（（2））,则它必定是叶

子结点。每棵树都能唯一地转换成与它对应的二叉树，由一棵树转换成的二叉树中，一个

结点N的左孩子是N在原树里对应结点的（③），而N的右孩子是它在原树里对应结点

的（④）。

①：A.是特殊的树B.不是树的特殊形式

C.是两棵树的总称D.有是只有二个根结点的树形结构

②：A.左子结点B.右子结点

C.左子结点或者没有右子结点D.兄弟

③〜④：A.左孩子结点B.最右子结点C.最邻近的右兄弟

D.最邻近的左兄弟E.最左的兄弟F.最右的兄弟

答：①B②A③A④C

（4）把一棵树转换为二叉树后，这棵二叉树的形态是（）=

A.唯一的B.有多种

C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子

答：A

（5）假定一棵度为3的树中结点数为50,则其最小高度为（）o

A.3B.4C.5D.6

答：C

（6）若一棵度为7的树有7个度为2的结点，有6个度为3的结点，有5个度为4

的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有

（）个叶子结点。

A.35B.28C.77D.78

答：D

（7）下列叙述中，正确的是（）。

A.二叉树就是度为2的树B.二叉树中不存在度大于2的结点

C.二叉树是有序树D.二叉树中每个结点的度均为2

答：B

（8）深度为5的二叉树至多有（）个结点。

A.16B.32

答：C

（9）对一个满二叉树，有m个叶子结点，。个结点，深度为万，则（）＜,

A.n=h+mB.h+m=2nC.m=h-lD.n=2h-l

答：D

（10）完全二叉树中，编号为，的结点的层次是（）o

（）

A./B.Iog2；C.Iog2/+1D.C.Iog2/+1

答：D

（11）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A.250B.501C.254D.505

答：B

（12）一棵有124个叶结点的完全二叉树，最多有（）个结点。

A.247B.248C.249D.250

答：B

（13）若唯一确定一棵二叉树，只需要知道该二叉树的（）。

A.先序序列B,中序序列

C,中序和后序序列D.先序和后序序列

答：C

（14）一棵二叉树的先序遍历序列和其后序遍历序列正好相反，则该二叉树一定是（）o

A.空树或只有一个结点B.哈夫曼树

C.完全二叉树D.高度等于其结点数

答：D

（15）一棵二叉树的后序遍历序列为D、A、B、E、C,中序遍历序列为D、E、B、A、

C,则先序遍历序列为（）。

、C、B、E、D、E、C、B、A

、E、A、B、C、E、D、B、A

答：D

（16）在线索化二叉树中，p所指结点没有左子树的充要条件是（）。

>lchild==NULL>ltag==l

>ltag==l且p->lchild==NULLD.以上都不对

答：B

（17）根据使用频率为5个字符设计的哈夫曼编码不可能是（）o

A.111,110,10,01,00B,000,001,010,011,1

C.100,11,10,1,0D.001,000,01,11,10

答：C

2.填空题

（1）由3个结点所构成的二叉树有（）种形态。

答：5

（2）一棵深度为6的满二叉树有（①）个分支结点和（②）个叶子结点。

答：①31②32

（3）设一棵完全二叉树有700个结点，则共有（）个叶子结点。

答:350

（4）设一棵完全二叉树具有1000个结点，则此完全二叉树有（①）个叶子结点，

有（②）个度为2的结点，有（③）个单分支结点。

答：①500②499③1

（5）一棵二叉树的第/•（£1）层最多有（）个结点。

答：2i-l

（6）深度为力的完全二叉树至少有（①）个结点，至多有（②）个结点，若按

自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（③）。

答：①2卅1②2”1（3）2/）-io

（7）对含有。个结点的二叉树进行中序递归遍历，该算法平均空间复杂度为（）o

答：0（川

（8）用5个权值｛3,2,4,5,1｝构造的哈夫曼（Huffman）树的带权路径长度是（）。

答：33

3.简答题

（1）一棵度为2的树与一棵二叉树有何区别

答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序

的，即在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是

一个孩子也有左右之分。另外，一棵度为2的树至少有3个结点，而一棵二叉树的结点个

数可以为0。

（2）试求含有％个叶子结点的完全二叉树的总结点数。

答：由二叉树的性质可知，n=nQ-l,在完全二叉树中，度为1的结点数4至多为1,

所以具有。0个叶子结点的完全二叉树结点数是/70+（。0-1）+1=2/?0或2n0-lo

（3）某二叉树的结点数据采用顺序存储结构如下：

2345678910（121314151617181920

111

AF#D#H##C##G1####B

E#

①

画出该二叉树；

②

写出结点值为D的双亲结点及左、右子树。

③

将此二叉树还原为森林。

答①该二叉树如图所示。

图一棵二叉树图二叉树还原成的森林

②结点值为D的结点的双亲结点为结点值为A的结点，其左子树为以C为根结点的

子树，其右子树为空。

③由此二叉树还原成的森林如图所示。

（4）证明完全二叉树的每棵子树也都是完全二叉树。

证明：让T是一棵完全二叉树，S是它的一棵子树。由子树定义可知，S是由T中某个

结点及其所有子孙构成的。由于T是完全二叉树，T的所有叶子结点都在两个相邻的层次

上，因此，S的所有叶子结点都在两个相邻的层次上。类似的，如果在S中存在不位于底

层上结点层，那么，该层也不位于T的底层上，它必须在T中所有底层叶子结点的右边，

因此它也必须在S中所有底层叶子结点的右边。从而得到S是完全二叉树。

（5）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求

出空格处的内容，并画出该二叉树。

先序序列：_B_F_ICEH_G

中序序列：D_KFIA_EC_

后序序列：_K_FBHJ_G_A

答：由这些显示部分推出二叉树如图所示。则先序序列为ABDFKICEHJG；中序序列为

DBKFIAHEJCG；后序序列为DKIFBHJEGCA。

图一棵二叉树

（6）如果一棵哈夫曼树T有％个叶子结点，那么，树T有多少个结点要求给出求解过程。

答：一棵哈夫曼树中只有度为2和0的结点，没有度为1的结点，由非空二叉树的性质1

可知，n0=n2+l,Wn2=nQ-l,则总结点数公公今?/?。1。

4.算法设计题

>（1）己知一棵二叉树按顺序方式存储在数组41.川中。设计一个算法求出离下标分别

为/•和/（0<八jWn）的两个结点的最近的公共祖先结点的值。

解：由二叉树顺序存储结构特点，可得到以下求离，•和/的两个结点最近的公共祖先结

点的算法：

ElemTypeAncestor(ElemTypeA[],inti,intj)

intp=i,q=j;

while(p!=q)

if(p>q)p=p/2;

elseq=q/2;

returnA[p];

（2）已知一棵二叉树采用顺序方式存储在数组中。设计一个先序遍历的递归算

法。

解：先序遍历树中结点的递归算法如下：

voidPreOrderl(ElemTypeA[],intijntn)

{if(i<n)

if(A[i]!='#*)=bt;arent=-l;

arent;

while(i!=-l)

{d++;path[d]=qu[i].s->data;

i=qu[i].parent;

)

print"'%段path[d]);

for(i=d-l;i>=0;i-)

/

M

printf(->%c"zpath[i]);

printf("\n");

}

if(p->lchild!=NULL)=p->lchild;

qu[rear].parent=front;=p->rchild;

qu[rear].parent=front;单项选择题

(1)在一个图中，所有顶点的度数之和等于图的边数的()倍。

2

答：C

(2)在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的()倍。

答：B

（3）有8个顶点的无向图最多有（）条边。

答：B

（4）有8个顶点的无向连通图最少有（）条边。

答：C

（5）有8个顶点的有向完全图有（）条边。

答：C

（6）“个顶点的强连通图中至少有（）条边。

A.nB.n-1C.2nD.n（n-l）

答：A

（7）若一个图的邻接矩阵是对称矩阵，则该图一定是（）o

A.有向图B.无向图C.连通图D.无向图或有向图

答：D

（8）设无向图G=（V,E）和G'=（V,E'）,如果G，是G的生成树，则下面的说法中错误的是

（）。

'为G的子图’为G的连通分量

'为G的极小连通子图且V=V'是G的一个无环子图

答：B

（9）用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。

A.栈B.队列C.树D.图

答：B

（10）用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。

A.栈B.队列C.树D.图

答：A

（11）图的广度优先遍历算法中用到辅助队列，每个顶点最多进队（）次。

A.1B.2C.3D.不确定

答：A

（12）一个无向图中包含k个连通分量，若按深度优先搜索方法访问所有结点，则必

须调用（）次深度优先遍历算法。

A.kB,1C.k-1D.k+1

答：A

（13）已知一个图的邻接表如图所示，根据算法，则从顶点0出发按深度优先遍历的

结点序列是（）.，

图一个邻接表

132231321123

答：D

（14）已知一个图的邻接表如图所示，根据算法，则从顶点0出发按广度优先遍历的

结点序列是（）o

132231321123

答：D

(15)深度优先遍历类似于二叉树的()o

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