《数据结构实验指导书》习题答案

习题一 绪 论

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

习题二 线性表

1、第一个（或首元）、最后一个（或尾元）、位置（或序号）、直接前驱、直接后继

2、n-i+1、n-i 3、A 4、B 5、随机存取、顺序存取 6、C 7、C 8、D 9、A 10、B 11、（1）s->next=p->next; p->next=s; （2）p->next=q->next （3）(a) s->next=L->next;L->next=s; (b) L->next==NULL （4）(a) s->next=L; L=s; (b) L==NULL 12、（a） p 、p->next->pre （b） p 、p->pre->next （c）q->next 、q->next->pre

（d）p->pre=q->pre、q->pre->next（e）p->pre->next、p->pre（f）s->pre、L->next->pre 13、(1)p->next=L->next、L->next=p (2)pa&&pb、pb=pb->next、pb (3) 0、p&&jnext; j=0;

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

14、int DeleteElem(int a[], int n, int i) //若删除成功，返回1，否则返回0

{ if(i>=n||i<1) return 0;

for(j=i;jvoid SetUnion(List &La, List Lb) //求La=La∪Lb

{ La_Len=ListLength(La); Lb_Len=ListLength(Lb); for(i=1;i<=Lb_Len; i++) { GetElem(Lb,i, e);

ListInsert(La,++La_Len,e) //在La尾端插入e } }

void SetJiao(List &La, List Lb) //求La=La∩Lb { La_Len=ListLength(La); i=1;

while(i<=La_len) { GetElem(La, i, e);

if(!LocateElem(Lb,e)) //若e不在Lb中 else i++； } }

if(!LocateElem(La,e)) //若e不在La中 { ListDelete(La, i, e); La_Len--; }

第二部分 习 题

习题三 栈与队列

1、后进先出(LIFO)表（或先进后出(FILO)表）、先进先出(FIFO)表（或后进后出(LILO)表） 2、C 3、C 4、C 5、B 6、B 7、C 8、A 9、(1)S.Top==-1、S.Elem[++S.Top]=e;、e=S.Elem[S.Top--]; (2) S.Top==0、S.Elem[S.Top++]=e;、e=S.Elem[--S.Top]; 10、对一带头结点的单链表实现逆置

11、Max、S.Top0+1==S.Top1、S.Elem[--S.Top1]=e、S.Top1==Max、S.Elem[S.Top1++] 13、(Q.rear+1)%MAX==Q.front、Q.rear==Q.front 、(Q.front+1)%MAX 14、Q.front->next=NULL(或Q.rear->next=NULL)、Q.rear->next=p、

Q.rear=p(或Q.rear=Q.rear->next)、Q.front==Q.rear(或Q.front->next==NULL)、 Q.rear=Q.front

15、Q、Q=q、Q==Q->next、Q=Q->next

习题四 树与二叉树

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

A 12、二叉树如右图1所示。 先序序列为：ABDEGCF 层次序列为：ABCDEFG

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

先序序列：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

B D E G 12题

C F 18、图1所示的森林转换成的二叉树如图下图（a)，图2所示的树转换成的二叉树如下图（b）所示。

E B C D I G G H H 18题（b)

D A B F E C A 18题（a)

第二部分 习 题

19、所得的二叉树如图19题（a）所示，对应的森林如图19题（b）所示。

G L D E H I J F K G 题19（a）

A B C B D H L 题19（b）

A E I C F J K 20、（1）BitreeDepth(T->lchild)、BitreeDepth(T->rchild)、dr+1

（2）PreOrder(T->lchild)、PreOrder(T->rchild)、InOrder(T->lchild)、InOrder(T->rchild) PostOrder(T->lchild)、PostOrder(T->rchild) 21、（1）所构造的哈夫曼树如下图所示。

（2）WPL=(16+17)*2+(9+15+14)*3+6*4+(2+3)*5=229

92

22、（1）哈夫曼树如上图。最小的作为左子树

（2）哈夫曼编码为：A：00 B：1010 C：100 D：1011 E：01 F：11

3 5 2 21题 6 22题

33 16 17 11 20 9 49 29 A E C B D F 15 14 习题五 图

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）深度优先搜索 广度优先搜索 （2）递增 （3）0 （4）e(i)==l(i)

第二部分 习 题

3、（1）图1的邻接矩阵 (2)图1的邻接表 v0 v1 v2 v3 v4

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

1 1 0 1 0

1 0 1 0 1

0 1 0 1 0 0 v0 1 v1 2 v2 3 v3 1 0 0 0 2 2 1 2 3 ^ 3 ^ 4 ^ 3 ^ 4 ^ 1 4 v4 4、（1）图2的邻接矩阵 (2)图2的邻接表 v0 v1 v2 v3 v4 v5 v0 v1 v2 v3 v4 v5 0 0 0 0 0 0 1 0 0 0 0 0

1 0 0 0 0 0

0 1 1 0 0 0

0 1 0 0 0 0

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

5、以下的任三个序列。

(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 6、邻接矩阵

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 ∞

7、(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 其中边上的标注①②③④⑤为选取的边的顺序。

第二部分 习 题

8、 //图的邻接表表示法的数据类型定义（参） #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;

void findIndegree(ALGraph &G, int indegree[]) //求每个顶点的入度，存于indegree数组中 { int i;

struct arcNode *p;

for(i=0;i{ indegree[p->adjVex]++; p=p->nextArc; } } }

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

for(i=0;iif(G.Arcs[v][i]==1) return i; return -1;

}

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

for(i=w+1;i}

第二部分 习 题

习题六 查 找

1、顺序 有序 2、9、4、6、7 3、low<=high、mid、low=mid+1 4、m、i 5、

12 37 97 24 45 53 6、 8、34、n3的左子孩 7、 p、p=p->rchild 8、（1）开放定址法的线性探测再散列；

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

15 8 43 10 19

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

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

43 15 8 9、

0 1 2 3 4 5 6 7 8 9 10 TN I K TA BA M D CI X ASL=20/9 10 19

习题七 排 序

1、D 2、（1）（4）（5）是稳定的，（2）（3）（6）（7）是非稳定的 3、O(nlog2n)、O(n2) 4、40,38,46,56,79,80 5、5 4 8 6、38,46,56,79,40,80 7、（3）为小顶堆；其余建成的初始堆略。8、答案略（参见教材271页图10.5） 9、答案略（参见教材283页图10.13） 10、n、a[j]、n、a[j]

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

{ low=1; high=n; a[0]=a[1];

while(low{ while(low=a[0]) high--; a[low]=a[high];

while(lowa[low]=a[0]; return low; }