python数据结构考试题库

第一章概论   自测题答案

一、填空题

1.  数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。

2. 数据结构被形式地定义为(D, R)，其中D是数据元素的有限集合，R是D上的关系有限集合。

3.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。

4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。

5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

6． 在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。

8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序  、 链式 、 索引  和  散列。

10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。

11. 一个算法的效率可分为时间效率和空间效率。

二、单项选择题

(B)1. 非线性结构是数据元素之间存在一种：

A)一对多关系B)多对多关系C)多对一关系D)一对一关系

(C)2.数据结构中，与所使用的计算机无关的是数据的结构；

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

(C)3. 算法分析的目的是：

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

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

(A)4. 算法分析的两个主要方面是：

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

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

(C)5. 计算机算法指的是：

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

(B)6. 计算机算法必须具备输入、输出和等5个特性。

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

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

三、简答题

1. 简述线性结构与非线性结构的不同点。

答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。

2．数据结构的常见的四种存储方式。

答：顺序  、 链式 、 索引  和  散列。

3. 数据结构的逻辑结构主要有哪两大类，具体是什么？

答：主要分为线性结构和非线性结构，其中线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。非线性结构又包含树结构和图结构

四、分析下面各程序段的时间复杂度

五、设有数据逻辑结构S=(D,R)，试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？

1.

D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4)}

答：d1→d2→d3→d4d1—无直接前驱，是首结点d4—无直接后继是尾结点

2。D={d1,d2,…,d9}

R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}

答： 此图为树形结构d1—无直接前驱，是根结点d2,d5,d7,d9—无直接后继是叶子结点

3．D={d1,d2,…,d9}

R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)}

答： 此图为图形结构d1，d2—无直接前驱，是开始结点d6,d7—无直接后继是终端结点

(2)                                      (3)

第3章  栈和队列 自测卷答案

一、填空题(每空1分，共15分)

1.【李春葆】向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。

3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 在一个循环队列中，队首指针指向队首元素的前一个位置。

5. 在具有n个单元的循环队列中，队满时共有n-1个元素。

6. 向栈中压入元素的操作是先移动栈顶指针，后存入元素。

7. 从循环队列中删除一个元素时，其操作是 先移动队首指针，后取出元素。

8. 〖00年统考题〗带表头结点的空循环双向链表的长度等于0。

解：

二、判断正误(判断下列概念的正确性，并作出简要的说明。)(每小题1分，共10分)

(   ×  )1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

(  ×   )2. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU中也用队列。

(  √   )3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

(  √   )4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

( ×  )5. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

(  ×  )6. 栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

(  √   )7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

(  √   )8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

( ×  )9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

错，后半句不对。

(  × )10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

错，有可能。

三、单项选择题(每小题1分，共20分)

(   B   )1. 〖00年元月统考题〗栈中元素的进出原则是

Ａ．先进先出    Ｂ．后进先出      Ｃ．栈空则进       Ｄ．栈满则出

(   C   )2. 〖李春葆〗若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为

Ａ．i    Ｂ．n=i      Ｃ．n-i+1       Ｄ．不确定

解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的(事实上题目已经表明了)，那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。

(若不要求顺序出栈，则输出序列不确定)

(   B   )3. 〖李春葆〗判定一个栈ST(最多元素为m0)为空的条件是

Ａ．ST->top0    Ｂ．ST->top=0       Ｃ．ST->topm0       Ｄ．ST->top=m0

(   A   )4. 〖李春葆〗判定一个队列QU(最多元素为m0)为满队列的条件是

Ａ．QU->rear － QU->front = = m0    Ｂ．QU->rear － QU->front －1= = m0

Ｃ．QU->front = = QU->rear           Ｄ．QU->front = = QU->rear+1

解：队满条件是元素个数为m0。由于约定满队时队首指针与队尾指针相差1，所以不必再减1了，应当选A。当然，更正确的答案应该取模，即：QU->front = = (QU->rear+1)% m0

(   D   )5．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为

(Ａ)r－f;     (Ｂ)(n＋f－r)% n;  (Ｃ)n＋r－f;         (Ｄ)(n＋r－f)% n

6. 【98初程P71】 从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。

设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。

现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是A，第二次出栈得到的元素是B是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是C，第二次出队得到的元素是D。经操作后，最后在栈中或队中的元素还有E个。

供选择的答案：

A～D：①a1  ②a2    ③ a3   ④a4

E： ①1    ②2    ③ 3     ④ 0

答：ABCDE＝2,    4,  1,  2,   2

7. 【94初程P75】 从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。

栈是一种线性表，它的特点是A。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入(PUSH)一个新元素时，变量T的值B；从栈中弹出(POP)一个元素时，变量T的值C。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是D，变量T的值是E。

供选择的答案：

A： ① 先进先出    ②后进先出  ③进优于出       ④出优于进 ⑤ 随机进出

B，C： ① 加1②减1③不变          ④清0⑤ 加2⑥减2

D：①a,b    ②b,c  ③c,a ④b,a     ⑤ c,b     ⑥ a,c

E：①n+1②n+2③n ④ n-1⑤n-2

答案：ABCDE=2,2,1,6,4

注意，向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈，本题中底部为n，向地址的低端递减生成，称为向下生成堆栈。

8. 【91初程P77】从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。

在做进栈运算时，应先判别栈是否A；在做退栈运算时，应先判别栈是否B。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为C。

为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的D分别设在这片内存空间的两端，这样，只有当E时，才产生上溢。

供选择的答案：

A，B：①空       ②  满       ③ 上溢     ④ 下溢

C：    ①n-1      ② n         ③ n+1      ④ n/2

D：   ① 长度    ②深度       ③ 栈顶     ④ 栈底

E：①两个栈的栈顶同时到达栈空间的中心点     ②其中一个栈的栈顶到达栈空间的中心点

③两个栈的栈顶在达栈空间的某一位置相遇   ④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底

答案：ABCDE＝2,  1,  2,  4,  3

四、简答题(每小题4分，共20分)

1. 【严题集3.2①和3.11①】说明线性表、栈与队的异同点。

刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。

不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

2. 【统考书P60 4-11，难于严题集3.1①】设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。

刘答：至少有14种。

① 全进之后再出情况，只有1种：4，3，2，1

② 进3个之后再出的情况，有3种，3,4,2,1  3,2,4,1  3,2,1,4

③ 进2个之后再出的情况，有5种，2,4,3,1   2,3,4,1   2,1, 3,4  2,1,4,32,1,3,4

④ 进1个之后再出的情况，有5种，1,4,3,2  1,3,2,4  1,3,4,2  1, 2,3,41,2,4,3

3.【刘自编】假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？

答：线性表是随机存储，可以实现，靠循环变量(j--)从表尾开始打印输出；

堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可；

队列是先进先出，不易实现。

哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。(但堆栈是先减后压还是……)

若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。

4. 【统考书P60 4-13】顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。

采用循环队列是解决假溢出的途径。

另外，解决队满队空的办法有三：

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

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

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

我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。

判断循环队列队空标志是： f=rear      队满标志是：f=(r+1)%N

5. 【统考书P60 4-14】设循环队列的容量为40(序号从0到39)，现经过一系列的入队和出队运算后，有

① front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

答：用队列长度计算公式：  (N＋r－f)% N

① L=(40＋19－11)% 40=8②L=(40＋11－19)% 40=32

五、阅读理解(每小题5分，共20分。至少要写出思路)

1. 【严题集3.7①】按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿照教材例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：

A－B×C/D+E↑F

答：

2． 【严题集3.3②】写出下列程序段的输出结果(栈的元素类型SElem Type为char)。

void main( ){

Stack S;

Char x,y;

InitStack(S);

X=’c’;y=’k’;

Push(S,x); Push(S,’a’);  Push(S,y);

Pop(S,x); Push(S,’t’); Push(S,x);

Pop(S,x); Push(S,’s’);

while(!StackEmpty(S)){ Pop(S,y);printf(y); };

Printf(x);

}

答：输出为“stack”。

2. 【严题集3.12②】写出下列程序段的输出结果(队列中的元素类型QElem Type为char)。

void main( ){

Queue Q;  Init Queue (Q);

Char x=’e’; y=’c’;

EnQueue (Q,’h’); EnQueue (Q,’r’);  EnQueue (Q, y);

DeQueue (Q,x); EnQueue (Q,x);

DeQueue (Q,x); EnQueue (Q,’a’);

while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); };

Printf(x);

}

答：输出为“char”。

3. 【严题集3.13②】简述以下算法的功能(栈和队列的元素类型均为int)。

void algo3(Queue &Q){

Stack S; int d;

InitStack(S);

while(!QueueEmpty(Q)){

DeQueue (Q,d);  Push(S,d);

};

while(!StackEmpty(S)){

Pop(S,d); EnQueue (Q,d);

}

}

答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。

六、算法设计(每小题5分，共15分。至少要写出思路)

1. 【李春葆及严题集3.19④】假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，编写一个判别表达式中括弧是否正确配对的函数correct(exp,tag)；其中：exp为字符串类型的变量(可理解为每个字符占用一个数组元素)，表示被判别的表达式，tag为布尔型变量。

答：用堆栈st进行判定，将 ( 、 [ 或 { 入栈，当遇到 }  、 ]  或 ) 时，检查当前栈顶元素是否是对应的( 、 [ 或 {，若是则退栈，否则返回表示不配对。当整个算术表达式检查完毕时，若栈为空表示括号正确配对，否则不配对。

编程后的整个函数如下(李书P31—32)

#define m0 100     /*m0为算术表达式中最多字符个数*/

correct(exp,tag)

char exp[m0];

int tag;

{char st[m0];

int top=0, i=1;

tag=1;

while (i0)tag=0;  /*若栈不空，则不配对*/

}

严题集对应答案：

3.19

Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配

{

InitStack(s);

for(p=str;*p;p++)

{

if(*p=='('||*p=='['||*p=='{') push(s,*p);

else if(*p==')'||*p==']'||*p=='}')

{

if(StackEmpty(s)) return ERROR;

pop(s,c);

if(*p==')'&&c!='(') return ERROR;

if(*p==']'&&c!='[') return ERROR;

if(*p=='}'&&c!='{') return ERROR; //必须与当前栈顶括号匹配

}

}//for

if(!StackEmpty(s)) return ERROR;

return OK;

}//AllBrackets_Test

2001级通信6班张沐同学答案(已上机通过)

#include

#include

void push(char x);

void pop();

void correct(enum Boolean &tag);

//原来的定义是void correct(struct Stack* head,enum Boolean &tag);

typedef struct Stack

{

char data;

struct Stack *next;

};

struct Stack *head,*p;

enum Boolean{FALSE,TRUE}tag;

void main()

{

head=(struct Stack*)malloc(sizeof(struct Stack));

head->data='S';

head->next=NULL;

// head's data has not been initialized!!

correct(tag);

if(tag)

printf("Right!");

else

printf("Wrong!");

}

void push(char x)

{

p=(struct Stack*)malloc(sizeof(struct Stack));

if(!p)

printf("There's no space.\n");

else

{

p->data=x;

p->next=head;

head=p;

}

}

// if you define the "Correct" function like that

//Debug will show that the Push action doesn’t take effection

void pop()

{

if(head->next==NULL)

printf("The stack is empty.\n");

else

{

p=head;

head=head->next;

free(p);

}

}

//void correct(struct Stack* head,enum Boolean &tag)

void correct(enum Boolean &tag)

{

int i;

char y;

printf("Please enter a bds:");

for(i=0;y!='\n';i++)

{

scanf("%c",&y);

if((y==')'&&head->data=='(')||(y==']'&&head->data=='[')||(y=='}'&&head->data=='{'))

pop();

else if((y=='(')||(y=='[')||(y=='{'))

push(y);

/*调试程序显示，y并没有被推入堆栈中。即head->data的值在Push中显示为y的值，但是出Push函数。马上变成Null。*/

else

continue;

}

if(head->next==NULL)       //原来的程序是if(head ==NULL) tag=TRUE;

tag=TRUE;

else

tag=FALSE;

}

/*总结： 由于head为全局变量，所以不应该将其再次作为函数的变量。因为C语言的函数变量是传值机制，所以在函数中对参数进行了拷贝复本，所以不能改变head的数值。*/

2. 【统考书P60 4-15】假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。

解：这就是解决队满队空的三种办法之① 设置一个布尔变量以区别队满还是队空(其他两种见简答题)；

思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令tag=1；

若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。

3.【严题集3.31③】试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

答：编程如下：

int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0

{

InitStack(S);InitQueue(Q);

while((c=getchar())!='@')

{

Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b) return ERROR;

}

return OK;

}//Palindrome_Test

第6章   树和二叉树 自测卷解答

一、下面是有关二叉树的叙述，请判断正误(每小题1分，共10分)

( √ )1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

( × )2.二叉树中每个结点的两棵子树的高度差等于1。

( √ )3.二叉树中每个结点的两棵子树是有序的。

( × )4.二叉树中每个结点有两棵非空子树或有两棵空子树。

( × )5.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值，且小于其右非空子树(若存在的话)所有结点的关键字值。(应当是二叉排序树的特点)

( × )6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。(应2i-1)

( × )7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

( × )8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。(应2i-1)

( √ )9.用二叉链表法(link-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

(正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。)即有后继链接的指针仅n-1个。

( √ )10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5

二、填空(每空1分，共15分)

1． 由３个结点所构成的二叉树有5种形态。

2.【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31个分支结点和26-1=32个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

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

( 注：用ë log2(n) û+1= ë 8.xx û+1=9

4. 【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。

答：最快方法：用叶子数＝[n/2]＝350

5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。

答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.

6.【严题集6.7③】一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为2。

答：当k=1(单叉树)时应该最深，深度＝n(层)；当k=n-1(n-1叉树)时应该最浅，深度＝2(层)，但不包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。)

7.【96程试题1】  二叉树的基本组成部分是：根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种：前序法(即按N L R次序)，后序法(即按L R N次序)和中序法(也称对称序法，即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是F E G H D C B。解：法1：先由已知条件画图，再后序遍历得到结果；

法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中，根结点在最前面，是B；则后序遍历中B一定在最后面。

法3：递归计算。如B在前序序列中第一，中序中在中间(可知左右子树上有哪些元素)，则在后序中必为最后。如法对B的左右子树同样处理，则问题得解。

8.【全国专升本统考题】中序遍历的递归算法平均空间复杂度为O(n)。

答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1，包括叶子的空域也递归了一次。

9.【计算机研2001】用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是33。

解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝(4＋5＋3)×2＋(1＋2)×3=33

(15)

(9)(6)(注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一)

45    3     (3)(注：合并值应排在叶子值之后)

1        2

(注：原题为选择题：Ａ．32            Ｂ．33Ｃ．34Ｄ．15)

三、单项选择题(每小题1分，共11分)

( C  )1． 不含任何结点的空树。

(Ａ)是一棵树;(Ｂ)是一棵二叉树;

(Ｃ)是一棵树也是一棵二叉树;(Ｄ)既不是树也不是二叉树

答：以前的标答是B，因为那时树的定义是n≥1

( C  )2．二叉树是非线性数据结构，所以。

(Ａ)它不能用顺序存储结构存储;(Ｂ)它不能用链式存储结构存储;

(Ｃ)顺序存储结构和链式存储结构都能存储;(Ｄ)顺序存储结构和链式存储结构都不能使用

( C )3. 〖01年计算机研题〗 具有n(n>0)个结点的完全二叉树的深度为。

(Ａ) élog2(n)ù   (Ｂ) ë log2(n)û   (Ｃ) ë log2(n) û+1     (Ｄ) élog2(n)+1ù

注1：éx ù表示不小于x的最小整数；ë xû表示不大于x的最大整数，它们与[ ]含义不同！

注2：选(A)是错误的。例如当n为2的整数幂时就会少算一层。似乎ë log2(n) +1û是对的？

( A  )4．把一棵树转换为二叉树后，这棵二叉树的形态是。

(Ａ)唯一的                          (Ｂ)有多种

(Ｃ)有多种，但根结点都没有左孩子    (Ｄ)有多种，但根结点都没有右孩子

5.【94程P11】  从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。

树是结点的有限集合，它A根结点，记为T。其余的结点分成为m(m≥0)个B

的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。一个结点的子结点个数为该结点的C。

供选择的答案

A：①有0个或1个②有0个或多个      ③有且只有1个      ④有1个或1个以上

B:   ①互不相交② 允许相交③ 允许叶结点相交    ④ 允许树枝结点相交

C： ①权② 维数③ 次数(或度)④ 序

答案：ABC＝1，1，3

6. 【95程P13】  从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。

二叉树A。在完全的二叉树中，若一个结点没有B，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的C，而N的右子女是它在原树里对应结点的D。

供选择的答案

A： ①是特殊的树   ②不是树的特殊形式   ③是两棵树的总称   ④有是只有二个根结点的树形结构

B:   ①左子结点   ② 右子结点  ③ 左子结点或者没有右子结点    ④ 兄弟

C～D： ①最左子结点         ② 最右子结点    ③ 最邻近的右兄弟        ④ 最邻近的左兄弟

⑤ 最左的兄弟     ⑥ 最右的兄弟

答案：A=B=C=D＝

答案：ABCDE＝2，1，1，3

四、简答题(每小题4分，共20分)

1. 【严题集6.2①】一棵度为2的树与一棵二叉树有何区别？

答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

2.〖01年计算机研题〗设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：(lchild,data,rchild)。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：

1. 对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果；

2. 假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。(共8分)

二叉树B

解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：A B C C E E B A D F F D G G

特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A，B，D等结点。反之马上就会重复出现。如C，E，F，G等结点。

时间复杂度以访问结点的次数为主，精确值为2*n，时间渐近度为O(n).

3. 〖01年计算机研题〗【严题集6.27③】给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I；  中序遍历序列：D，C，B，E，H，A，G，I，F，

试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。

D

A

C                  F

E           G

B      H           I

4.【计算机研2000】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。

解：要遵循中序遍历的轨迹来画出每个前驱和后继。

中序遍历序列：55  40  25  60  28  08  33  54

28

25 33

40      60    08        54

55

五、阅读分析题(每题5分，共20分)

1. (P60 4-26)试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

答：DLR：A B D F J G K C E H I L M

LDR:  B F J D G K A C H E L I M

LRD：J F K G D B H L M I E C A

2. (P60 4-27)把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线(包括度为2的兄弟),并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。

A

B

EC

KFHD

LGI

MJ

3.【严题集6.17③】阅读下列算法，若有错，改正之。

4.【严题集6.21②】画出和下列二叉树相应的森林。

答：注意根右边的子树肯定是森林，

而孩子结点的右子树均为兄弟。

六、算法设计题(前5题中任选2题，第6题必做，每题8分，共24分)

1.【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。

解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。

法一：核心部分为：

DLR(liuyu *root)     /*中序遍历   递归函数*/

{if(root!=NULL)

{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);}

DLR(root->lchild);

DLR(root->rchild); }

return(0);

}

法二：

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目

{

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加

上右子树的叶子数

}//LeafCount_BiTree

注：上机时要先建树！例如实验二的方案一。

① 打印叶子结点值(并求总数)

思路：先建树，再从遍历过程中打印结点值并统计。

步骤1  键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。叶子结点值应该是4，9, 13, 21,总数应该是4.

12

7 17

2     11        16    21

4   9        13

编程：  生成二叉树排序树之后，再中序遍历排序查找结点的完整程序如下：

说明部分为：

#include

#include

typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test;

liuyu *root;

int sum=0;int m=sizeof(test);

void insert_data(int x)        /*如何生成二叉排序树？参见教材P43C程序*/

{ liuyu *p,*q,*s;

s=(test*)malloc(m);

s->data=x;

s->lchild=NULL;

s->rchild=NULL;

if(!root){root=s; return;}

p=root;

while(p)                 /*如何接入二叉排序树的适当位置*/

{q=p;

if(p->data==x){printf("data already exist! \n");return;}

else if(xdata)p=p->lchild;  else p=p->rchild;

}

if(xdata)q->lchild=s;

else q->rchild=s;

}

DLR(liuyu *root)     /*中序遍历   递归函数*/

{if(root!=NULL)

{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf("%d\n",root->data);}

DLR(root->lchild);

DLR(root->rchild); }

return(0);

}

main()            /*先生成二叉排序树，再调用中序遍历递归函数进行排序输出*/

{int i,x;

i=1;

root=NULL;            /*千万别忘了赋初值给root!*/

do{printf("please input data%d:",i);

i++;

scanf("%d",&x);           /*从键盘采集数据，以-9999表示输入结束*/

if(x==-9999){

DLR(root);

printf("\nNow output count value:%d\n",sum);

return(0);  }

else insert_data(x);}           /*调用插入数据元素的函数*/

while(x!=-9999);

return(0);}

执行结果：

若一开始运行就输入-9999，则无叶子输出，sum=0。

2.【全国专升本统考题】写出求二叉树深度的算法，先定义二叉树的抽象数据类型。   (10分)

或【严题集6.44④】编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。

答；设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。

但注意，递归时应当从叶子开始向上计数，否则不易确定层数。

int depth(liuyu*root)     /*统计层数*/

{int d,p;                   /*注意每一层的局部变量d,p都是各自独立的*/

p=0;

if(root==NULL)return(p);      /*找到叶子之后才开始统计*/

else{

d=depth(root->lchild);

if(d>p) p=d;              /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/

d=depth(root->rchild);

if(d>p)p=d;

}

p=p+1;

return(p);

}

法二：

int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度

{

if(T->data==x)

{

printf("%d\n",Get_Depth(T)); //找到了值为x的结点,求其深度

exit 1;

}

}

else

{

if(T->lchild) Get_Sub_Depth(T->lchild,x);

if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找

}

}//Get_Sub_Depth

int Get_Depth(Bitree T)//求子树深度的递归算法

{

if(!T) return 0;

else

{

m=Get_Depth(T->lchild);

n=Get_Depth(T->rchild);

return (m>n?m:n)+1;

}

}//Get_Depth

附：上机调试过程

步骤1  键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。层数应当为4

步骤2： 执行求深度的函数，并打印统计出来的深度值。

完整程序如下：

#include

#include

typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test;

liuyu *root;

int sum=0;int m=sizeof(test);

void insert_data(int x)        /*如何生成二叉排序树？参见教材P43C程序*/

{ liuyu *p,*q,*s;

s=(test*)malloc(m);

s->data=x;

s->lchild=NULL;

s->rchild=NULL;

if(!root){root=s; return;}

p=root;

while(p)                 /*如何接入二叉排序树的适当位置*/

{q=p;

if(p->data==x){printf("data already exist! \n");return;}

else if(xdata)p=p->lchild;  else p=p->rchild;

}

if(xdata)q->lchild=s;

else q->rchild=s;

}

int depth(liuyu*root)     /*统计层数*/

{int d,p;                   /*注意每一层的局部变量d,p都是各自独立的*/

p=0;

if(root==NULL)return(p);      /*找到叶子之后才开始统计*/

else{

d=depth(root->lchild);

if(d>p) p=d;              /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/

d=depth(root->rchild);

if(d>p)p=d;

}

p=p+1;

return(p);

}

void  main()            /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/

{int i,x;

i=1;

root=NULL;            /*千万别忘了赋初值给root!*/

do{printf("please input data%d:",i);

i++;

scanf("%d",&x);           /*从键盘采集数据，以-9999表示输入结束*/

if(x==-9999){

printf("\nNow output depth value=%d\n", depth (root)); return; }

else insert_data(x);}           /*调用插入数据元素的函数*/

while(x!=-9999);

return;}

执行结果：

3.【严题集6.47④】编写按层次顺序(同一层自左至右)遍历二叉树的算法。

或：按层次输出二叉树中所有结点；

解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。

这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。

技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。

level(liuyu*T)

/* liuyu *T,*p,*q[100];   假设max已知*/

{int f,r;

f=0; r=0;             /*置空队*/

r=(r+1)%max;

q[r]=T;             /*根结点进队*/

while(f!=r)        /*队列不空*/

{f=(f+1%max);

p=q[f];            /*出队*/

printf("%d",p->data);         /*打印根结点*/

if(p->lchild){r=(r+1)%max; q[r]=p->lchild;}     /*若左子树不空，则左子树进队*/

if(p->rchild){r=(r+1)%max; q[r]=p->rchild;}     /*若右子树不空，则右子树进队*/

}

return(0);

}

法二：

void LayerOrder(Bitree T)//层序遍历二叉树

{

InitQueue(Q); //建立工作队列

EnQueue(Q,T);

while(!QueueEmpty(Q))

{

DeQueue(Q,p);

visit(p);

if(p->lchild) EnQueue(Q,p->lchild);

if(p->rchild) EnQueue(Q,p->rchild);

}

}//LayerOrder

可以用前面的函数建树，然后调用这个函数来输出。

完整程序如下(已上机通过)

#include

#include

#define max 50

typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test;

liuyu *root,*p,*q[max];

int sum=0;int m=sizeof(test);

void insert_data(int x)        /*如何生成二叉排序树？参见教材P43C程序*/

{ liuyu *p,*q,*s;

s=(test*)malloc(m);

s->data=x;

s->lchild=NULL;

s->rchild=NULL;

if(!root){root=s; return;}

p=root;

while(p)                 /*如何接入二叉排序树的适当位置*/

{q=p;

if(p->data==x){printf("data already exist! \n");return;}

else if(xdata)p=p->lchild;  else p=p->rchild;

}

if(xdata)q->lchild=s;

else q->rchild=s;

}

level(liuyu*T)

/* liuyu *T,*p,*q[100];   假设max已知*/

{int f,r;

f=0; r=0;             /*置空队*/

r=(r+1)%max;

q[r]=T;             /*根结点进队*/

while(f!=r)        /*队列不空*/

{f=(f+1%max);

p=q[f];            /*出队*/

printf("%d",p->data);         /*打印根结点*/

if(p->lchild){r=(r+1)%max; q[r]=p->lchild;}     /*若左子树不空，则左子树进队*/

if(p->rchild){r=(r+1)%max; q[r]=p->rchild;}     /*若右子树不空，则右子树进队*/

}

return(0);

}

void  main()            /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/

{int i,x;

i=1;

root=NULL;            /*千万别忘了赋初值给root!*/

do{printf("please input data%d:",i);

i++;

scanf("%d",&x);           /*从键盘采集数据，以-9999表示输入结束*/

if(x==-9999){

printf("\nNow output data value:\n", level(root)); return; }

else insert_data(x);}           /*调用插入数据元素的函数*/

while(x!=-9999);

return;}

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

答：首先，由于是完全二叉树，不必担心中途会出现孩子为null的情况。

其次分析：结点i的左孩子为2i，右孩子为2i+1;直接打印即可。

Printf(“Left_child=”, %d, v[2*i].data; “Right_child=”, %d, v[2*i+1].data;);

但其双亲是i/2，需先判断i为奇数还是偶数。若i为奇数，则应当先i-- ，然后再除以2。

If(i/2!=0)i--;

Printf(“Parents=”, %d, v[i/2].data;);

5.【严题集6.49④】编写算法判别给定二叉树是否为完全二叉树。

答：int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0

{

InitQueue(Q);

flag=0;

EnQueue(Q,T); //建立工作队列

while(!QueueEmpty(Q))

{

{

DeQueue(Q,p);

if(!p) flag=1;

else if(flag) return 0;

else

{

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列

}

}//while

return 1;

}//IsFull_Bitree

分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点

是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空

指针的序列.反之,则序列中会含有空指针.

6. 【严题集6.26③】假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。

解：方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[(2,3)，6], (7,10)】,……19,21,32

(100)

(40)      (60)

19     21     32   (28)

(17) (11)

7     10  6    (5)

23

方案比较：

方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61

方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3

结论：哈夫曼编码优于等长二进制编码

第7章 图 自测卷解答

一、单选题(每题1分，共16分)前两大题全部来自于全国自考参考书！

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

A．1/2            B.  1             C.  2             D.  4

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

A．1/2            B.  1             C.  2             D.  4

(B)3. 有8个结点的无向图最多有条边。

A．14B.28C.56D.112

(C)4. 有8个结点的无向连通图最少有条边。

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

(C)5. 有8个结点的有向完全图有条边。

A．14B.28C.56D.112

(B)6. 用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

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

(A)7. 用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

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

(C)8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是

(D)9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是

A．0 2 4 3 1 5 6B.0 1 3 5 6 4 2     C.  0 4 2 3 1 6 5D.0 1 3 4 2 5 6

(B)10.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是

A．0 2 4 3 6 5 1B.0 1 3 6 4 2 5      C.  0 4 2 3 1 5 6D.0 1 3 4 2 5 6

(建议：0 1 2 3 4 5 6)

(C)11.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是

A．0 2 4 3 1 6 5B.0 1 3 5 6 4 2     C.  0 1 2 3 4 6 5D.0 1 2 3 4 5 6

(D)12. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是

(A)13.  已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是

(A)14. 深度优先遍历类似于二叉树的

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

(D)15. 广度优先遍历类似于二叉树的

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

(A)16. 任何一个无向连通图的最小生成树

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

(注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一)

二、填空题(每空1分，共20分)

1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。

3. 如果n个顶点的图是一个环，则它有n棵生成树。  (以任意一顶点为起点，得到n-1条边)

4.  n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)。

5.  n个顶点e条边的图，若采用邻接表存储，则空间复杂度为O(n+e)。

6. 设有一稀疏图G，则G采用邻接表存储较省空间。

7. 设有一稠密图G，则G采用邻接矩阵存储较省空间。

8. 图的逆邻接表存储结构只适用于有向图。

9. 已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是将邻接矩阵的第i行全部置0。

10. 图的深度优先遍历序列不是惟一的。

11.  n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O(n2)；若采用邻接表存储时，该算法的时间复杂度为O(n+e)。

12. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为O(n2)；若采用邻接表存储，该算法的时间复杂度为O(n+e)

13. 图的BFS生成树的树高比DFS生成树的树高小或相等。

14. 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(n2)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是O(elog2e)。

15. 若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔(Kruskal)算法来求解。

16. 若要求一个稠密图G的最小生成树，最好用普里姆(Prim)算法来求解。

17. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。

18.  拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。

三、简答题(每题6分，共24分)

1.【严题集7.1①】已知如图所示的有向图，请给出该图的:

(1)

每个顶点的入/出度；

(2) 邻接矩阵；

(3) 邻接表；

(4) 逆邻接表。

答案：

2.【严题集7.7②】请对下图的无向带权图：

(1) 写出它的邻接矩阵，并按普里姆算法求其最小生成树；

(2) 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种(类)!

邻接矩阵为：

PRIM算法(横向变化)：

V

b

c

d

e

f

g

h

U

V-U

Vex

lowcost

a

4

a

3

a

∞

a

∞

a

∞

a

∞

a

∞

{a}

{b,c,d,e,f,g,h}

Vex

lowcost

a

4

0

c

5

a

∞

a

∞

a

∞

c

5

{a,c}

{b, d,e,f,g,h}

Vex

lowcost

0

0

c

5

b

9

a

∞

a

∞

c

5

{a,c,b}

{d,e,f,g,h}

Vex

lowcost

0

0

0

d

7

d

6

d

5

d

4

{a,c,b,d }

{e,f,g,h}

Vex

lowcost

0

0

0

d

7

d

6

d

5

0

{a,c,b,d ,h }

{e,f,g }

Vex

lowcost

0

0

0

d

7

g

2

0

0

{a,c,b,d ,h ,g}

{ f,e }

Vex

lowcost

0

0

0

f

3

0

0

0

{a,c,b,d ,h ,g, f }

{e }

Vex

lowcost

0

0

0

0

0

0

0

{a,c,b,d ,h ,g, f, e }

{ }

邻接表为：

a

→

b

4

→

c

3

b

→

a

4

→

c

5

→

d

5

→

e

9

^

c

→

a

3

→

b

5

→

d

5

→

h

5

^

d

→

b

5

→

c

5

→

e

7

→

f

6

→

g

5

→

h

4^

e

→

b

9

→

d

7

→

f

3

^

f

→

d

6

→

e

3

→

g

2

^

g

→

d

5

→

f

2

→

h

6

^

h

→

c

5

→

d

4

→

g

6

^

先罗列：f---2---ga—3--cf—3—ea—4---b   d—4—h

(a,b,c)   (e,f,g)   (d,h)取b—5—d,  g—5--d就把三个连通分量连接起来了。

3.【严题集7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

4.【严题集7.11②】试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。

解：最短路径为：(a,c,f,e,d,g,b)

四、【2001年计考研题】给定下列网G: (10分)

1 试着找出网G的最小生成树，画出其逻辑结构图；

2 用两种不同的表示法画出网G的存储结构图；

3 用C语言(或其他算法语言)定义其中一种表示法(存储结构)的数据类型。

解：1.最小生成树可直接画出，如右图所示。

2.可用邻接矩阵和邻接表来描述：

邻接表为：

a

→

b

12

→

e

4

^

b

→

a

12

→

c

20

→

e

8

→

f

9

^

c

→

b

20

→

d

15

→

g

12

^

d

→

c

15

→

g

10

^

e

→

a

4

→

b

8

→

f

6

^

f

→

b

9

→

e

6

^

g

→

c

12

→

d

10

五、算法设计题(每题10分，共30分)

1.【严题集7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

解：Status Build_AdjList(ALGraph &G)  //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表

{

InitALGraph(G);

scanf("%d",&v);

if(v

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);

q->nextarc=p;

}

p->adjvex=j;p->nextarc=NULL;

}//while

return OK;

}//Build_AdjList

2.【严题集7.15③】试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。(如果要删除所有从第i个顶点出发的边呢？  提示：将邻接矩阵的第i行全部置0)

解：//本题中的图G均为有向无权图。

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w)

{

if((i=LocateVex(G,v))

if(i==j) return 1; //i就是j

else

{

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

{

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

}//for

}//else

}//exist_path_DFS

解2：(以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。)

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int level＝1;//递归进行的层数

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j

是否有路径,是则返回1,否则返回0

{

if(i==j) return 1; //i就是j

else

{

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--)

{ level++;

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

}//for

}//else

if (level==1)  return 0;

}//exist_path_DFS

附加题：【严题集7.27④】采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。

(注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。

注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。)

int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G

的顶点i到j是否存在长度为k的简单路径

{

{

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求

else if(k>0)

{

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

{

l=p->adjvex;

if(!visited[l])

if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一

}//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中

}//else

return 0; //没找到

}//exist_path_len

第8章 查找  自测卷答案A

一、填空题(每空1分，共10分)

1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找(线性查找)。

2. 线性有序表(a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索8次。设有100个结点，用二分法查找时，最大比较次数是7。

3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为8；平均查找长度为3.7。

解：显然，平均查找长度＝O(log2n)

if(T->lchild&&flag) Is_BSTree(T->lchild);

if(T->data

last=T->data;

if(T->rchild&&flag) Is_BSTree(T->rchild);

return flag;

}//Is_BSTree

3. 【严题集9.22④】已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。

解：设计哈希表的步骤为：

a) 根据所选择的处理冲突的方法求出装载因子a的上界；

b) 由a值设计哈希表的长度m；

c) 根据关键字的特性和表长m选定合适的哈希函数。

刘注：要求ASL≤3，则m必然要尽量长，以减少冲突；

4. 【严题集9.44④】已知某哈希表的装载因子小于1，哈希函数H(key)为关键字(标识符)的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

解：注意此题给出的条件：装载因子a〈1,则哈希表未填满。由此可写出下列形式简明的算法：

void PrintWord(Hash Table ht)

{//按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。

for(i=1; i

if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key);

j=(j+1)%m;

}

}

}//PrintWord

第9章   排序  自测卷

一、填空题(每空1分，共24分)

1. 大多数排序算法都有两个基本的操作：比较和移动。

2.在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较6次。

3.在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用选择。

4.在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无序，则最好选用快速排序。

5.对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2)。若对其进行快速排序，在最坏的情况下所需要的时间是O(n2)。

6.对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)

，所需要的附加空间是O(n)。

7． 对于n个记录的表进行2路归并排序，整个归并排序需进行┌log2n┐趟(遍)。

8. 设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列，则：

冒泡排序一趟扫描的结果是H C Q P A M S R D F X Y；

初始步长为4的希尔(shell)排序一趟的结果是P A C S Q H F X R D M Y；

二路归并排序一趟扫描的结果是H Q C Y A P M S D R F X；

快速排序一趟扫描的结果是F H C D P A M Q R S Y X；

堆排序初始建堆的结果是A D C R F Q M S Y P H X。

9. 在堆排序、快速排序和归并排序中，

若只从存储空间考虑，则应首先选取方法，其次选取快速排序方法，最后选取归并排序方法；

若只从排序结果的稳定性考虑，则应 选取归并排序方法；

若只从平均情况下最快考虑，则应选取堆排序、快速排序和归并排序方法；

若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。

二、单项选择题(每小题1分，共18分)

(C)1．将5个不同的数据进行排序，至多需要比较次。

Ａ.8                Ｂ.9             Ｃ. 10Ｄ. 25

(C)2． 排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为

Ａ.希尔排序      Ｂ.冒泡排序Ｃ. 插入排序       Ｄ.选择排序

(D)3．从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为

Ａ.希尔排序      Ｂ.归并排序Ｃ. 插入排序       Ｄ.选择排序

(B)4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。

Ａ.从小到大排列好的   Ｂ.从大到小排列好的Ｃ. 元素无序   Ｄ.元素基本有序

(D)5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为

Ａ.n+1                Ｂ. nＣ.n-1Ｄ.n(n-1)/2

(C)6．快速排序在下列哪种情况下最易发挥其长处。

Ａ.被排序的数据中含有多个相同排序码   Ｂ.被排序的数据已基本有序

Ｃ.被排序的数据完全无序Ｄ.被排序的数据中的最大值和最小值相差悬殊

(B)7．  对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是

A．O(n)     B．O(n2)    C．O(nlog2n)     D．O(n3)

(C)8．若一组记录的排序码为(46, 79, 56, 38, 40, 84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为

Ａ.38,  40,  46,  56,  79,  84            Ｂ.40, 38,  46 ,  79,  56,  84

Ｃ.   40,  38，46,  56,  79,  84Ｄ.  40,  38, 46,  84,  56,  79

(D)9．下列关键字序列中，是堆。

Ａ.16,72,31,23,94,53Ｂ.94,23, 31, 72, 16, 53

Ｃ.16, 53, 23,94，31,72Ｄ.16, 23, 53,31, 94, 72

(B)10．堆是一种排序。

Ａ.插入          Ｂ.选择Ｃ. 交换       Ｄ.归并

(C)11．堆的形状是一棵

Ａ.二叉排序树       Ｂ.满二叉树Ｃ. 完全二叉树       Ｄ.平衡二叉树

(B)12．若一组记录的排序码为(46, 79, 56, 38, 40, 84)，则利用堆排序的方法建立的初始堆为

Ａ.79, 46, 56, 38, 40, 84       Ｂ.84, 79, 56, 38, 40, 46

Ｃ. 84, 79, 56, 46, 40, 38       Ｄ. 84, 56, 79, 40, 46, 38

(C)17． 下述几种排序方法中，要求内存最大的是

Ａ.插入排序      Ｂ.快速排序Ｃ. 归并排序       Ｄ.选择排序