数据结构复习题1--和答案

说明：

此复习题为复习专用，其给定了期末考试的主要范围，并非给定考试原题，考试时相关的题目基本都要进行改动。因此同学们请注意，不要去背答案，要将题理解并做会。

（请注意这决不是原题，只有弄会才可能通过）

第1章 绪 论

※1、数据结构主要研究的三个内容为 、 以及定义在该结构上的 。

2、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于 。 3、数据结构被形式地定义为（D，R），其中D是 的有限集，R是D上的 有限集。 4、数据的结构在计算机内存中的表示是指（ ）

A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 ※5、给出以下给定的两个程序段中划波浪线的语句的执行频度（次数）。 （1） sum=0;

for(i=0;i

for(j=0; j

for(i=0;i

for(j=0; j<=i; j++) sum+=a[i][j]; (3) sum=0;

for(i=0;i

for(j=0; j

（2） i=1;

while(i<=n) i=i*3;

第2章 线性表

1、n(n>=0)个元素的线性结构表示成(a1，a2,……an)，a1称为______元素，an称为______元素，i称为ai在线性表中的____________。对任意一对相邻结点ai、ai+1(1<=i

2、在表长为n的顺序表的第i个位置插入一元素（1<=i<=n+1，插入的新元素作为第i个元素），则涉及到的元素的移动次数为 ；若删除第i（1<=i<=n）个元素，则涉及到的元素的移动次数为 。

※3、线性表的顺序存储结构（顺序表）其存储空间 。

A) 必须是连续的 B) 部分是连续的

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

4、一个顺序表的第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。

A）110 B）108 C）100 D）120

5、顺序表的存取特点为 ，单链表的存取特点为 。 6、对于顺序表的优缺点，以下说法错误的是（ ） ①无需为表示结点间的逻辑关系而增加额外的存储空间 ②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便

④容易造成一部分空间长期闲置而得不到充分利用

7、以下说法正确的是

①线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继

②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低 ③在顺序存储线性表中，插入和删除元素时，移动元素的个数与插入或删除位置有关 ④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动

8、以下说法正确的是（ ）

①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针 ③线性表的顺序存储结构优于链式存储结构

④顺序存储结构属于静态结构，链式结构属于动态结构 ※9、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。

①顺序表 ②单链表 ③双链表 ④单循环链表 10、单链表中，增加头结点的目的是为了 ( ) ①使单链表至少有一个结点

②标示表结点中首结点的位置

③使每个元素都能有前驱结点，从而方便运算的实现 ④说明单链表是线性表的链式存储实现

※11、对于一单链表L(L为头指针，且结点的后继指针分量为next),其p结点（p为链表中某结点的指针）既不是第一个结点，也不是最后一个结点。

（1）在p结点后插入s结点(s为某结点的指针)的语句序列是： 【1】 （2）删除p结点的直接后继结点的语句序列是：q=p->next; 【2】 ; free(q); （3）若L为带头结点的单链表，则：

a) 在表首插入s结点的语句序列是： 【3】 b) 单链表为空的判定条件为： 【4】 （4）若L为不带头结点的单链表，则：

a) 在表首插入s结点的语句序列是： 【5】 b) 单链表为空的判定条件为： 【6】

※12、已知L是带表头结点的双向链表(L为头指针，且结点的后继指针分量为next，前驱．．．．．指针为pre ),其p结点（p为链表中某结点的指针）既不是首元结点，也不是尾元结点。

a）在p结点后插入s结点(s为某结点的指针)的语句序列是：

s->next=p->next；s->pre= 【1】 ; 【2】 =s; p->next=s; b）在p结点前插入s结点(s为某结点的指针)的语句序列是： s->pre=p->pre;s->next= 【3】 ; 【4】 =s; p->pre=s; c）删除p结点的直接后继结点的语句序列是：

q=p->next; p->next= 【5】 ; 【6】 =p; free(q); d) 删除p结点的直接前驱结点的语句序列是：

q=p>pre; 【7】 ; 【8】 =p; free(q);

e) 删除该p结点语句序列是： 【9】 =p->next; p->next->pre= 【10】 ; free(p); f) 在表首插入s结点的语句序列是：

s->next=L->next; 【11】 =L; 【12】 ; L->next=s; 13、设带头结点的单链表类型定义如下：

typedef struct LNode

{ Elemtype data; //Elemtype 为数据元素类型 struct Lnode *next; //后继结点的指针 } *LinkedList;

（1）函数InverseList(L)的作用是将一带头结点的单链表实现就地逆置的算法（即利用原来链表的空间，将单链表中的结点按原来相反的顺序存储）。填写空缺位置，使此该算法完整。

InverseList(LinkedList &L)

{ p=L->next;

L->next= NULL; while ( p )

{ q=p->next; 【1】 ; 【2】 ; p=q;} }

（2） MergeList(La, Lb)函数的作用是将两个递增有序的带头结点的单链表La, Lb，利用原来的结点空间，合并成一个递增有序的链表La。填写空缺位置，使此该算法完整。

void MergeList (LinkedList &La, LinkedList &Lb) { pa=La->next; pb=Lb->next; s=La; while( 【3】 ) { if(pa->data<=pb->data)

{ s->next=pa; s=pa; pa=pa->next; } else { s->next=pb; s=pb; 【4】 ; } }

if (pa) s->next=pa;

else s->next= 【5】 ; free(Lb);

}

（3）函数Search(L,i)用来返回带头结点的单链表L的第i个元素的位置指针。填写空缺位置，使此该算法完整。

LinkedList Search(LinkedList L, int i) { p=L; j= 【6】 ; while( 【7】 ){ p=p->next; j++;} if( 【8】 ) return p; else return NULL; }

※（4）函数ListLength(L)用来求一带头结点的单链表L的长度。请写出此函数的算法代码。 14、函数DeleteElem(int a[], int n, int i)的作用为：在一个长度为n的数组中，删除其第i个元素。其中第数组的第一个元素为a[0]，第二个元素为a[1]，依次类推。请写出此函数的算法代码。

第3章 栈与队列

1、栈与队列是二种特殊的线性表，栈其亦称为 ；队列亦称为 。 2、现有一个空栈，现有4个元素其入栈顺序为a、b、c、d，则不可能得到了出栈顺序为 。

A）a,b,c,d B) d,c,b,a C) c,a,b,d D) a,c,b,d

3、现有一个空栈，已知其入栈序列为1, 2, 3, … , n，其输出序列为p1, p2, p3, …, pn。若p1=n，则pi（1≤i≤n）为

A）i B) n-i C) n-i+1 D) 不确定 4、栈与队列的共同点是 。

A）都是先进后出 B）都是先进先出

C）只允许在端点处插入和删除元素 D) 没有共同点 5、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（ ）

①2 ② 3 ③ 5 ④6 6、设有一顺序栈已含3个元素（当前栈顶元素为a3），如下图所示，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是（ ）

0 1 2 3 maxsize-1 sq a1 a2 a3

①a3,a1,a4,a2 ②a3,a2,a4,a1 ③ a3,a4,a2,a1 ④a4,a3,a2,a1 7、一个队列的入列序是1，2，3，4，则队列的输出系列是（ ）

① 4，3，2，1 ② 1，2，3，4， ③1，4，3，2 ④ 3，2，4，1

8、向一个栈顶指针为Top（Top指向栈顶元素）的链中插入一个s所指结点时，其操作步骤为（ ）

①Top->next=s ② s->next=Top->next;Top->next=s ③s->next=Top;Top=s ④ s->next=Top;Top=Top->next

9、在一个栈顶指针为Top（Top指向栈顶元素）的链栈中，进行出栈操作，并将被出栈元素的值保存到x中，其操作步骤为（ ）

①p=Top;x=Top->data;Top=Top->next; free(p); ②p=Top;Top=Top->next;x=Top->data;free(p); ③x=Top;Top=Top->next;free(Top); ④ x=Top->data; free(Top);

10、对于顺序存储的栈，其类型描述如下：

typedef struct

{ ElemType Elem[MAX]; /*ElemType为栈内元素类型，MAX为一预定义常量，数组

Elem的首端为栈底，另一端为栈顶*/

int Top; /*Top指示栈顶位置，其值为下标值*/

} SqStack;

若Top指示的位置为当前栈顶元素的位置，则栈空的判定条件为： ； 若Top指示的位置为当前栈顶元素的下一位置（即入栈位置），则栈空的判定条件为： ；

11、阅读下列算法，写出其完整的功能。 #define MAX 100

typedef struct LNode

{ DataType data; //DataType 为数据元素类型 struct Lnode *next; //后继结点的指针 } *LinkedList;

void RVList( LinkedList head) { DataType S[MAX]; int top=0;

LinkedList p; p=head->next; while(p)

{ S[top++]=p->data; p=p->next;}

p=head->next; while(top)

{ p->data=S[--top]; p=p-next;}

}

12、以下算法是以顺序存储结构实现一个双向栈（即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点）。以下给出了此双向栈类的定义及此双向栈的初始化操作和入栈操作与出栈的算法。填写空白位置，使此算法完整。（注：双向栈结构如下图所示）

0 a0

低下标处的栈 1 a1 2 a2 ?? ?? i ai ???? ???? 高下标处的栈

Max-j-1 bj Top1 ?? ?? Max-2 Max-1 b1 b0 Top0 #define Max 可用最大空间长度； typedef struct

{ElemType Elem[Max]；/*ElemType 为栈内数据元素的类型*/

int Top0,Top1; /*定义两个栈顶位置指针，分别存储两个栈的当前栈顶元素的下标*/ ．．．．．．} DStack;

void inistack(DStack &S )/*双向栈S的初始化操作*/ { S.Top0= -1; S.Top1= 【1】 ; }

Status push(DStack &S, int i ,ElemType e)

/*将e入栈；其中i为0或1，i为0表示对设在低下标处的栈进行操作，i为1，表示对设在高下标处的栈进行操作*/

{ if ( 【2】 ) /*若栈满*/

{printf(\ return(ERROR);} else if (i==0) S.Elem[++S.Top0]=e; else 【3】 ; retrun OK; }

Status pop(DStack &S, int i ,ElemType &e)

/*出栈操作，其中i为0或1，i为0表示对设在低下标处的栈进行操作，i为1，表示对设在高下标处的栈进行操作，并通过参数e返回出栈元素的值*/

{ if (i==0)

if( S.Top0==-1 ) return 0;

else { e=S.Elem[S.Top0--]; return 1; } else

if( 【4】 ) return 0; else {e= 【5】 ; return 1;} }

13、以下是有关循环队列的类型定义及其有关操作，填写上相应的空白位置。 ．．．．/*类型描述*/ #define MAX 100 typedef struct

{ ElemType base[MAX]; /*ElemType为元素的数据类型*/ int front; /*头指针，若队列不空，指向队列头元素*/

int rear;/*尾指针，若队列不空，指向队列尾元素的下一个位置*/ } SqQueue;/*说明：少用一个元素空间，以区别队列判空和判满条件*/ Status InitQueue(SqQueue &Q) /*初始化操作*/

{ Q.front=Q.rear=0;return OK; }

Status EnQueue(SqQueue &Q,ElemType e) /* 入队操作*/

{ if( 【1】 ) return ERROR;/*若队列满，返回出错*/ Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)% MAX; retrun OK; }

Status DeQueue(SqQueue &Q,ElemType &e) /*出队操作*/

{ if( 【2】 ) return ERROR;/*若队列空，则返回出错*/ e=Q.base[Q.front]; Q.front= 【3】 ; }

14、若用如下图所示一带头结点的单循环链表来表示队列，并且只设一个指针Q指向队尾．．．结点（注意不设头指针）。以下给出了此队列的类型描述、初始化操作、入队操作和出队操作，在空白处填写上正确答案。

（1）一般的队列形式

a1 a2 an Q

（2）空队列形式

Q typedef struct Lnode /*类型描述*/

{ ElemType data; /*ElemType为元素的数据类型*/ struct Lnode *next; } *CLinkQueue;

Status InitQueue(CLinkQueue &Q) /*初始化建立空队列Q,执行成功函数返回OK，否则返回FALSE*/

{ Q=(CLinkQueue) malloc(sizeof(struct Lnode)); if(!Q) return FALSE; Q->next= 【1】 ; return OK;

}

Status EnQueue(CLinkQueue &Q, ElemType e)

{ q=(CLinkQueue)malloc(sizeof(struct Lnode*)); if(!q) return FALSE;

q->data=e;

q->next=Q->next; Q->next=q; 【2】 ; return OK; }

Status DeQueue(CLinkQueue &Q, ElemType &e) /*出队操作, 操作成功返回OK，否则返回

FALSE*/

{ if( 【3】 ) return FALSE; /*空队时*/ p=Q->next->next;

Q->next->next=p->next;

if(p==Q) 【4】 ; e=p->data; free(p); return OK;

}

15、若用如下图所示一带头结点的单链表来表示队列。以下给出了此队列的类型描述、初．．．始化操作、入队操作和出队操作，在空白处填写上正确答案。 Q front （1）一般的队列形式

rear

Q front （2）空队列形式

rear

struct qnode //结点类型描述

{ ElemType data; //ElemType为元素的数据类型 struct qnode *next;

} ;

typedef struct //链队类型描述 { struct qnode *front; struct qnode *rear; } LinkQueue;

Status InitQueue(LinkQueue &Q) /*初始化建立空队列Q,执行成功函数返回OK，否则返回FALSE*/

{ Q.front=Q.rear=(LinkQueue) malloc(sizeof(struct Lnode)); if(!Q.front) return FALSE; 【1】 ; return OK;

}

Status EnQueue(LinkQueue &Q, ElemType e) { p=(LinkQueue)malloc(sizeof(struct Lnode*));

if(!p) return FALSE;

p->data=e; p->next=NULL;

【2】 ; 【3】 ; return OK; }

Status DeQueue(LinkQueue &Q, ElemType &e) /*出队操作, 操作成功返回OK，否则返回FALSE*/

a1 a2 an ^ ^

{ if( 【4】 ) return FALSE; /*空队时*/ p=Q.front->next;

Q.front->next=p->next;

if(p==Q.rear) 【5】 ; e=p->data; free(p); return OK;

}

第6章 树与二叉树

1、在一棵含有n个结点的二叉树中，其分支数（边数）为： ；若此二叉树只有度为2的分支结点，和度为0的叶子结点，则该树中叶子结点的数目为 ；若此二叉树的深度（根所在数为1，深度为树的最大层数）为d，且此树为满二叉树，则此树的结点数n为 。

2、对于一棵有n个结点的完全二叉树，其深度为（根所在数为1，深度为树的最大层数） ；若对其结点按层进行编号（根结点为1，每层从左到右），则对于一编号为i(1

3、在一棵二叉树中，叶子结点数为22,度为1的结点数为13，则该二叉树的结点总数为 。

4、具有n个结点的二叉树，其深度最大为 ，最小为 。 个结点，最多有 个结点。

6、一棵完全二叉树按层遍历得到结点序列为ABCDEFGH，则结点H的双亲为 ，结点C的左孩子为 。

7、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是 的二叉树。

A）空或只有一个结点 B）高度等于其结点数

C）任一结点无左孩子 D）任一结点无右孩子

8、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历序列中结点E的直接前驱为 ，后序遍历中节点B的直接后继为 。

9、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树的先序序列为 ，该二叉树对应的森林中包括 棵树。

10、一棵二叉树的节点数据采用顺序存储结构，存储于数组a中，如下图所示，则该二叉树的后序序列为 。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 E A F D G C J I H B 5、深度为k的二叉树至少有 个结点，至多有 个结点；深度k的完全二叉树，最少有

11、由n个权值构成的哈夫曼树共有 个节点。

12、若一棵二叉树的先序（根）遍历序列和中序（根）遍历序列分别是ABDEGCF和DBGEACF，请画出此二叉树，并给出其后序（根）遍历序列和层次遍历序列。

13、已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA，

请画出此二叉树，并将此二叉树转换为对应的森林

14、下列叙述正确的是（ ）

A．二叉树是度为2的有序树

B．二叉树中结点只有一个孩子时无左右之分 C．二叉树中必有度为2的节点

D．二叉树中每一个结点最多只有两棵子树，并且有左右之分 15、深度为k的完全二叉树所含叶结点的个数最多为（ ） A．2k B．2k-1 C．k D．2k

16、根据二叉树的定义，具有3个结点的二叉树共有（ ）种 A．3 B．4 C．5 D．6

17、深度为5的二叉树至多有（ ）结点

A．16 B．32 C．31 D．10

18、一棵二叉树的先序、中序和后序序列如下，其中一部分未标出，请将补充空缺位置给出完整遍历序列。

先序序列： C D E G H I K 中序序列：C B F A J K I G 后序序列： E F D B J I H A

19、给定权值集合{15，3，14，2，6，9，16，17}，请解答下列问题： （1）构造相应的哈夫曼树 （2）计算它的带权路经长度

20、对图4-1给定的森林和图4-2所示的树，将其转化成相应的二叉树。

21、 二叉树的二叉链表存储结构描述如下 ．．．．．．．．typedef struct bnode { ElemType data;

struct bnode *lchild,*rchild; /* lchild、rchild分别为左、右孩子的指针 */ }*BiTree;

（1）递归函数．．．．BiTreeDepth(T)的作用是求二叉树的深度，请填写空缺位置。 int BiTreeDepth (BiTree T ) /* T为根指针*/ { int dl,dr;

if ( T==NULL ) return 0; B A C E D G I 图4-1

F H B A C H D E G 图4-2

else { dl= 【1】 ; dr= 【2】 ; if(dl>=dr) return dl+1; else return 【3】 ; } }

（2）递归函数．．．．PreOrder(T)、InOrder(T)、PostOrder(T)的作用对以T为根指针的二叉树进行先根（序）遍历、中根（序）遍历、后根（序）遍历。

void PreOrder (BiTree T ) /*先序遍历以T为根指针的二叉树*/ { if ( T )

{ visit (T->data); /*其中visit()为结点数据的访问函数*/

【1】 ;

【2】 ; } }

void InOrder (BiTree T ) /*中序遍历以T为根指针的二叉树*/ { if ( T )

{ 【3】 ;

visit (T->data); /*其中visit()为结点数据的访问函数*/

【4】 ; } }

void PostOrder (BiTree T ) /*后序遍历以T为根指针的二叉树*/ { if ( T )

{ 【5】 ; 【6】 ;

visit (T->data); /*其中visit()为结点数据的访问函数*/

} }

22、假设用于通讯的电文仅由5个字母（A、B、C、D、E）组成，字母在电文中出现的频

率分别为0.25, 0.05,0.40, 0.20,0.10。试为这5个字母设计出哈夫曼编码。（要求：画出相应的哈夫曼树，并根据哈夫曼树给出每个字符的哈夫曼编码）

第7章 图

1、选择题

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

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

（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A．1/2 B. 1 C. 2 D. 4 （3）有8个结点的无向图最多有 条边。

A．14 B. 28 C. 56 D. 112 （4）有8个结点的无向连通图最少有 条边。

A．5 B. 6 C. 7 D. 8 （5）有8个结点的有向完全图有 条边。

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

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

A．栈 B. 队列 C. 二叉树 D. 树 （7）已知图的邻接矩阵，根据算法思想，则从顶点0出发，按深度优先遍历的结点序列是：

?0?1??1??1?1??0??1100100110001001100110101101000011011?1??0??0?0??1?0??

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

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

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

（9）已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是：

A．0 1 3 2 B. 0 2 3 1

C. 0 3 2 1 D. 0 1 2 3

（10）已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列

是：

A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2

（11） 图的简单路径是指（ ）不重复的路径。

A. 权值

B. 顶点

C. 边

D. 边与顶点均

（12） 设无向图的顶点个数为n，则该图最多有（ ）条边。

A. n-1 A. n-1

B. n(n-1)/2 B. n

C. n(n+1)/2 C. n+1

D. n(n-1) D. 0 D. 对称矩阵

（13） n个顶点的连通图至少有（ ）条边。

（14）若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。

A. 上三角矩阵

B. 稀疏矩阵

C. 对角矩阵

（15）设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 ? V2，E1 ? E2，则称（ ）。

A. G1是G2的子图

B. G2是G1的子图 D. G2是G1的连通分量

C. G1是G2的连通分量

（16）一个连通图的生成树是包含图中所有顶点的一个（ ）子图。

A. 极小

B. 连通

C. 极小连通

D. 无环

（17）对于具有e条边的无向图，它的邻接表中有（ ）个边结点。

A. e-1

B. e

C. 2(e-1)

D. 2e

（18）与邻接矩阵相比，邻接表更适合于存储（ ）图。

A. 无向 B.连通 C.稀疏 D. 稠密图 （19）在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是 。 A. G中有弧〈vi，vj〉 B. G中有一条从vi到vj的路径

C. G中没有弧〈vi，vj〉 D. G中有一条从vj到vi的路径 （20）有向图G用邻接矩阵A存储，则顶点i的出度等于 。

A. 第i行非0元素个数 B. 第i列非0元素个数

C. 第i行和第i列所有非0的元素个数 D. 矩阵A中所有非0元数个数

2、填空题

（1）具有n个顶点的无向连通图最多具有边数为： ，其生成树具有边数为： 。 （2）具有n个顶点的有向图最多具有弧数为： 。 （3）遍历图有 、 等方法。 （4）图的逆邻接表存储结构只适用于 图。

（5）用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来

得到最短路径的。

（6）拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完成的。 3、求出图1所示无向图中每个的度，及图2所示有向图每个顶点的出度与入度。 4、给出图1所示的无向图的邻接矩阵（邻接数组）。 5、给出图1所示的无向图的邻接表

V0 V1 V4 V2 V3 图1

6、对于图2所示的有向无环图给出其三种拓扑排序序列。 7、给出图3所示连通网的邻接矩阵。

8、对如图3所示连通网（边上的数值为此边的权值）： （1）从结点v1出发，利用普里姆算法构造其最小生成树。 （2）利用克鲁斯卡尔算法构造其最小生成树。

（只需画出最终的最小生成树，并在每条边的两侧分别注明边的权

5 6 v1 v2 5 1 5 v4 3 6 v3 4 2 v5 6 图3

v6 值和选边的顺序，并将选边的顺序用括号括起来以区别权值） ．．．．．．．．

9、用C语言分别定义图的邻点矩阵表示法和邻接表表示法的数据类型。 10、图的邻接矩阵表示如下： #define MaxVexNum 20 typedef struct

{ VexType Vexs[MaxVexNum]; //定义顶点数组，VexType为顶点类型

int Arcs[MaxVexNum][ MaxVexNum]; //定义邻接矩阵，有弧或边则值为1，否则为0 int vexnum,arcnum; //顶点数或边数 } MGraph;

函数FirstAdjVex(G,v)的作用为：在图G中，求顶点v(v为顶点在顶点数组中的下标，下同)的第一个邻接顶点；若存在函数返回所求得的邻接顶点（即其在顶点数组中的下标），否则返回-1。

函数NextAdjVex(G,v,w)的作用为：在图G中，已知顶点w是顶点v当前的一个邻接顶点，函数用来求相对于顶点w顶点v的下一个邻接顶点；若存在函数返回所求得的邻接顶点（即其在顶点数组中的下标），否则返回-1。

如下给出了这两个函数头的定义，请给出这两个函数的完整定义。

int FirstAdjVex(MGraph &G,int v) {...................................................} int NextAdjVex(MGraph &G, int v, int w) {...................................................}

第9章 查 找

1．以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为________，时间复杂度为________。

2．以折半查找方法查找一个线性表时，此线性表必须是________存储的________表。 3、在有序表A[1..18]中，采用二分查找算法查找元素值等于A[7]的元素，所比较过的元素的下标依次为 。

4、已知数组a中元素从a[1]至a[n]递增有序，Search_Bin函数采用折半查找(即二分法查找)的思想在a[1]~a[n]中查找值为m的元素。若找到，则函数返回相应元素的位置(下标)，否则返回0。填写空缺置，使算法完整。

int Search_Bin(int a[ ], int n, int m) { low=1;high=n; while ( 【1】 ) { mid=(low+high)/ 2;

if (m==a[mid] ) return 【2】 ; else if (m

5、函数Search_sq的作用是在a[1]~a[n]中采用顺序查找方法，查找值为m的元素。若找到，则函数返回相应元素的位置(下标)，否则返回0。其中利用0下标元素作为监哨岗。填写空缺置，使算法完整。

int Search_sq(int a[ ], int n, int m) { int i;

a[0]= 【1】 ; for(i=n;m!=a[i];i--); return 【2】 ;

}

6、给定序列为{45，53，97，24，37，12}，从空树开始依次将其插入建立一二叉排序树。 7、若如图6-1所示的二叉树为一二叉排序树（即二叉查找树），现有一菲波那契数列{1,2,3,5,8,13,21,34}填入该二叉树，则根结点（结点n1）的值为 ，结点n6的值为： 。若

n4 n7 n2 n5 n8 图6-1

n1

n3 n6

欲插入值为10的结点，插入结点应做为： 。 8、以下为二叉链表存储的二叉排序树

typedef struct bnode

{ int data; /*设树中元素类型为int类型*/

struct bnode *lchild,*rchild; /* lchild、rchild分别为左、右孩子的指针 */

}*BiTree;

Bitree Search (Bitree T, int m) /*在以T为根指针的二叉排序树中进行查找值为m的结点，找到则返回该结点的地址，否则返回NULL*/

{ p=T; while(p)

{ if(p->data==m) return 【1】 ; else if(mdata) p=p->lchild; else 【2】 ; }

return NULL;

}

9、对于给定的关键字序列（15，19，8，43，10），选取哈希函数为：H（key）=key%7，分别利用以下给出的解决冲突的方法，在0~6的地址空间上构造出哈希表（画出所构造的哈希表即可）,并求出在等概率查找的情况下查找成功时的平均查找长度。

（1）开放定址法的线性探测再散列； （2）开放定址法的二次探测再散列；

10、设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD 11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。

9、【1】n 【2】 a[j] 【3】n 【4】a[j] 10、利用一趟快速排序实现，算法略。

判断题

1、× 2、√ 3、√ 4、× 5、× 6、√ 7、√ 8、× 9、× 10、× 11、√ 12、√ 13、× 14、× 15、× 16、√ 17、√ 18、× 19、√ 20、× 21、√ 22、√ 23、√ 24、√ 25、√ 26、√ 27、√ 28、√ 29、× 30、× 31、× 32、× 33、√ 34、√ 35、√ 36、√ 37、× 38、√ 39、√ 40、√

第10章 排 序

1、外排序是指 。

A）用机器指令直接对硬盘中需排序数据排序。 B）把需排序数据，用其他大容量机器排序。

C）把外存中需排序数据一次性调入内存，排好序后，再输回外存。

D）对外存中大于内存允许空间需排序的数据，通过多次内外存间的交换实现的排序。 2、以下给定的序列，哪些是堆（是大顶堆还是小顶堆），哪些不是堆，若不是利用建立初始堆的方法将其建成一大顶堆。

A）19，75，34，26，97，56 B）97，26，34，75，19，56

C）19，56，26，97，34，75 D）19，34，26，97，56，75 3、以下给出的排序方法哪些是稳定的，哪些是非稳定的：

（1）直接插入排序 （2）希尔排序 （3）快速排序 （4）冒泡排序 （5）二路归并排序 （6）简单选择排序 （7）堆排序 3、快速排序在平均情况下的时间复杂度为_______，在最坏情况下的时间复杂度为______。 4、假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的一次划分的结果为_______________ _。

5、对20个记录进行归并排序时，共需要进行________趟归并，在第三趟归并时是把长度为________的有序表两两归并为长度为________的有序表。

6、假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为________________。

7、对于给定的待排序的关键字序列（49，38，65，97，76，13，27，49，55，4），利用希尔排序方法（设增量序列为5、3、1）给出其排序过程。不写算法，只需画出过程，给出每趟排序的结果。

8、对于给定的待排序的关键字序列（49，38，65，97，76，13，27），分别按下列排序方法给出排序过程。

（1）2-路归并排序； （2）直接插入排序 （3）冒泡排序

9、填写上相应的空白位置，使该算法完整。 void InsertSort( int a[], int n，)

/*本函数的作用是完成对数组a中的前n个数（a[1]~a[n]）作直接插入排序*/

{ for(i=2；i<= 【1】 ;i++) { a[0]=a[i]

for(j=i-1; a[0]

void ShellInsert( int a[], int n，int d)

/*本函数的作用是对数组a中的前n个数（a[1]~a[n]）进行一趟希尔排序，d为给定的．．增量*/

{ for(i=d+1；i<= 【3】 ;i++) { a[0]=a[i]

for(j=i-d; j>0&&a[0]

}

10、已知一整型数组a中包含有n个元素（下标1..n），设计一个算法，能在O(n)的时间内将a[1]放置到一适当位置k，将数组分成两个部分，其左半部分（下标1~k-1）的所有数据元素的值均小于等于初始a[1]的值，右半部分（下标k+1~n）的值均大于等于初始a[1]的值。例如：

初始数组a（n=8）：49 38 65 97 76 13 27 53 执行该算法后（k=4）：{27 38 13} 49 {76 97 65 53} 要求：（1）用C语言设计该算法；

（2）设实现该算法的函数名及返回值与参数如下：

int Partation( int a[], int n) //函数返回初始a[1]到达的最终位置k

判断题

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

k-1

2、深度为k的完全二叉树中的结点个数最少为2。

3、栈和队列的存储方式既可是顺序方式，也可是链接方式。

i

4、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2-1个结点。 5、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

6、用二叉链表法存储包含n个结点的二叉树，结点的2n个指针域中有n+1个为空指针。 7、具有12个结点的完全二叉树有5个度为2的结点。

8、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 9、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

10、线性表的每个数据元素只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 11、栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 12、对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 13、栈和队列是一种非线性数据结构。 14、一个栈的输入序列是12345，则栈的输出序列不可能是12345。 15、调用一次深度优先遍历可以访问到图中的所有顶点。

16、冒泡排序在初始元素序列为逆序的情况下执行的交换次数最多。 17、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

18、设有一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。 19、设一棵树T可以转化成二叉树BT，则二叉树BT的根一定没有右子树。 20、线性表的顺序存储结构比链式存储结构更好。 21、中序遍历二叉排序树可以得到一个有序的序列。 22、快速排序是排序算法中平均性能最好的一种排序。

23、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。 24、当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。 25、完全二叉树中的叶子结点只可能在最后两层中出现。 26、哈夫曼树中没有度数为1的结点。

27、对连通图进行深度优先遍历可以访问到该图中的所有顶点。 28、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。 29、由树转化成二叉树，该二叉树根的右子树不一定为空。 30、线性表中的所有元素都有一个前驱元素和后继元素。 31、带权无向图的最小生成树是唯一的。

32、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。 33、如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。 34、非空的双向循环链表中任何结点的前驱指针均不为空。

35、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为

O(n)。 36、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。 37、有向图的邻接表和逆邻接表中表结点的个数不一定相等。 38、对链表进行插入和删除操作时不必移动链表中结点。

39、若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍

历序列中的最后一个结点。

40、堆是完全二叉树，完全二叉树不一定是堆。

参考答案

第1章 绪论

1、数据的逻辑结构、数据的物理存储结构、数据的操作（或运算）及其实现。 2、非线性结构 3、数据元素、 关系 4、 A 5、 (1) n2 (2) n(n+1)/2 (3) n*m 6、（1）O(n)（3）O (log3n)

第2章 线性表

1、第一个（或首元）、最后一个（或尾元）、位置（或序号）、直接前驱、直接后继 2、 n-i+1 、 n-i 3、 A 4、 B 5、随机存取、顺序存取 6、③ 7、③ 8、④ 9、① 10、③

11、【1】 s->next=p->next; p->next=s; 【2】 p->next=q->next 【3】s->next=L->next;L->next=s; 【4】L->next==NULL 【5】 s->next=L; L=s; 【6】L==NULL

12、【1】p 【2】p->next->pre 【3】p 【4】p->pre->next 【5】q->next 【6】q->next->pre 【7】p->pre=q->pre【8】q->pre->nex【9】p->pre->next【10】p->pre【11】s->pre【12】L->next->pre 13、(1)【1】 p->next=L->next 【2】 L->next=p (2)【3】 pa&&pb 【4】pb=pb->next 【5】 pb

(3)【6】0 【7】 p&&jnext; j=0;

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

第3章 栈与队列

1、后进先出(LIFO)表或先进后出(FILO)表 、先进先出(FIFO)表或后进后出(LILO)表 2、C 3、C 4、C 5、② 6、① 7、②8、③ 9、① 10、Top==-1 Top==0 11、对一带头结点的单链表实现逆置

12、 【1】 Max 【2】 S.Top0+1==S.Top1 【3】 S.Elem[--S.Top1]=e 【4】S.Top1==Max 【5】 S.Elem[S.Top1++]

13、 【1】 (Q.rear+1)%MAX==Q.front 【2】Q.rear==Q.front 【3】(Q.front+1)%MAX 14、 【1】Q 【2】Q=q 【3】Q==Q->next 【4】Q=Q->next

15、【1】Q.front->next=NULL(或Q.rear->next=NULL) 【2】 Q.rear->next=p

【3】 Q.rear=p(或Q.rear=Q.rear->next) 【4】Q.front==Q.rear(或Q.front->next==NULL)

【5】Q.rear=Q.front

第6章 树与二叉树

1、 n-1 (n+1)/2 2d-1 2、 Log 2 n +1 i/2 2i 2i+1 3、56 4、n Log 2 n +1 5、 k 2k-1 2k-1 2k-1 6、 D F 7、 B 8、I F 9、EACBDGF 2 10、BCJDAIHGFE 11、2n-1

12、二叉树如图1所示。 13、所得的二叉树如图2所示，对应的森林如图3。 先序序列为：ABDEGCF 层次序列为：ABCDEFG D

14、D 15、B 16、C 17、C 18、完整的序列为：

先序序列：A B C D E F G H I J K 中序序列：C B E D F A H J K I G 后序序列：C E F D B K J I H G A 19、 （1）所构造的哈夫曼树如图4所示。

（2）WPL=229

20、图4-1所示的森林转换成的二叉树如图5所示，图4-2所示的树转换成的二叉树如图6所示。

3 5 2 图4 11 6 9 33 16 17 20 49 29 15 14 E B C D 图5

I G H H 图6

F E G 92 A B C D A E G 图1

A B C E H L I J F K G 图2

A B C D F G B D H L A E I C F J K 图3

21、（1）【1】 BitreeDepth(T->lchild) 【2】 BitreeDepth(T->rchild) 【3】dr+1 （2） 【1】 PreOrder(T->lchild) 【2】 PreOrder(T->rchild) 【3】InOrder(T->lchild)

【4】 InOrder(T->rchild) 【5】PostOrder(T->lchild) 【6】 PostOrder(T->rchild) 22、（1）哈夫曼树如下图

A D B C E （2）哈夫曼编码为：

A：10 B：1110

C：0 D：110 E：1111

第7章 图

1、（1）C （2）B （3）B （4）C （5）C （6）B （7）D （8）C （9）D （10）A （11）C（12）B（13）A（14）D（15）A（16）C（17）D（18）C（19）D（20）A 2、 (1) n(n-1)/2 n-1 (2) n (n-1) （3）深度优先搜索 广度优先搜索 （4）有向 （5）递增 （6）0 3、无向图中各顶点的度 顶点 v0 v1 v2 v3 v4 度 3 3 3 3 2 有向图各顶点的入度与出度

入度 0 1 1 2 1 2

出度 2 2 1 1 1 0

4、（1）图1的邻接矩阵 （2）图2的邻接矩阵

v0 v1 v2 v3 v0 v1 v2 v3 v4

v0 0 1 1 0 v0 0 1 1 1 0 v1 0 0 0 1 v1 1 0 1 0 1 v2 0 0 0 1 v2 1 1 0 1 0 v3 0 0 0 0 v3 1 0 1 0 1 v4 0 0 0 0 v4 0 1 0 1 0 v5 0 0 0 0

顶点 v0 v1 v2 v3 v4 v5 v4 v5 0 1 0 0 0 0

0 0 0 1 1 0 5、(1)图1的邻接表

0 v0 1 v1 2 v2 3 v3 4 v4 1 0 0 0 1 2 2 1 2 3 ^ 3 ^ 4 ^ 3 ^ 4 ^

(2)图2的邻接表 (3) 图2的逆邻接表 0 v0 1 v1 2 v2 3 v3 4 v4 5 v5 ^ 1 3 3 ^ 5 ^ 5 ^ 3 ^ 4 ^ 0 v0 ^ 1 v1 2 v2 3 v3 4 v4 5 v5 0 ^ 0 ^ 1 1 ^ 3 4 ^ 2 ^

6、对于图2所示的有向无环图给出其三种拓扑排序序列。

(1) v0,v1,v2,v3,v4,v5 (2) v0,v2,v1,v3,v4,v5 (3) v0,v2,v1,v4,v3,v5 (4) v0,v1,v2,v4,v3,v5 (5) v0,v1,v4,v2,v3,v5 7、邻接矩阵

v0 v1 v2 v3 v4 v5

v0 ∞ 6 1 5 ∞ ∞

v1 6 ∞ 5 ∞ 3 ∞

v2 1 5 ∞ 5 6 4

v3 5 ∞ 5 ∞ ∞ 2

v4 ∞ 3 6 ∞ ∞ 6

v5 ∞ ∞ 4 2 6 ∞ 8、(1) 普里姆（Prim）算法 (2) 克鲁斯卡尔算法

v1 v2 5 ① 1 v4 3 ④ v3 4 ③ 2 ⑤

② v5 v6 v1 v2 5 ① 1 v4 3 ⑤ v3 4 ② 2 ③

④ v5 v6 其中边上的标注①②③④⑤为选取的边的顺序。

9、（1）图的邻接矩阵表示法数据类型定义（参考答案） #define MaxVexNum 20 typedef struct

{ VexType Vexs[MaxVexNum]; //定义顶点数组，VexType为顶点类型 int Arcs[MaxVexNum][ MaxVexNum]; //定义邻接矩阵 int vexnum,arcnum; //顶点数或边数 int kind; //图的种类 } MGraph;

（2）图的邻接表表示法的数据类型定义（参考答案） #define MaxVexNum 20

struct ArcNode //表结点的定义 { int AdjVex;

struct ArcNode *nextarc; };

struct VexNode //头结点的定义

{ VexType data; //顶点信息，VexType为顶点类型 struct ArcNode *firstarc; };

typedef struct //图的类型定义

{ struct VexNode AdjLists[MaxVexNum]; int vexnum,arcnum; int kind; //图的种类 } ALGraph;

10、int FirstAdjVex(MGraph &G, int v) { int i;

for(i=0;i

if(G.Arcs[v][i]==1) return i; return -1;

}

int NextAdjVex(MGraph &G, int v, int w) { int i;

for(i=w+1;i

}

第9章 查找

1、(n+1)/2 O(n) 2、 顺序 有序 3、 9、4、6、7

4、【1】 low<=high 【2】 mid 【3】 low=mid+1 5、【1】 m 【2】 i 6、 45 53 24 37 12 97

7、 8 、 34 、 n3的左子孩 8、 【1】p 【2】p=p->rchild 【3】 p 【4】p=p->rchild 【5】 f 9、（1）开放定址法的线性探测再散列；

ASL=(1+2+3+2+1)/5=1.8 0 1 2 3 4 5 6

15 8 22 31 19

（2）开放定址法的二次探测再散列；

ASL=(1+2+3+1+1)/5=1.6 0 1 2 3 4 5 6

22 15 8 31 19

10、 0 K 1 TA ASL=20/9

2 BA 3 M 4 D 5 CI 6 X 7 8 9 TN 10 I 第10章 排 序

1、D 2、D为小顶堆；其余建成的初始堆略。 3、O(nlog2n)、O(n2) 4、40,38,46,56,79,80 5、5 4 8 6、38,46,56,79,40,80 7、答案略

8、（1）答案略； （2）与（3）答案略

9、【1】n 【2】 a[j] 【3】n 【4】a[j] 10、利用一趟快速排序实现，算法略。

判断题

1、× 2、√ 3、√ 4、× 5、× 6、√ 7、√ 8、× 9、× 10、× 11、√ 12、√ 13、× 14、× 15、× 16、√ 17、√ 18、× 19、√ 20、× 21、√ 22、√ 23、√ 24、√ 25、√ 26、√ 27、√ 28、√ 29、× 30、× 31、× 32、× 33、√ 34、√ 35、√ 36、√ 37、× 38、√ 39、√ 40、√