[数据结构-C语言描述]陈慧南主编答案

第一章 绪论

1．（第14页，第（18）题）

确定划线语句的执行次数，计算它们的渐近时间复杂度。 (1) i=1; k=0; do {

k=k+10*i; i++; } while(i

划线语句的执行次数为 n-1（n>=2），n=1时执行1次 。 (2）i=1; x=0; do{

x++; i=2*i; } while （i

划线语句的执行次数为 ⎡log 2n ⎤。 (3) for(int i=1;i

划线语句的执行次数为n(n+1)(n+2)/6 。 (4）x=n;y=0;

while(x>=(y+1)*(y+1)) y++; 划线语句的执行次数为⎣ √n ⎦。

第二章 两种基本的数据结构

2-4．

Loc(A[i][j][k])=134+(i*n*p+j*p+k)*2

2-9. 第34页 习题(2).9

void Invert(T elements[], int length) {//length数组长度 // elements[]为需要逆序的数组 T e;

for (int i=1;i

e=elements[i-1];

elements[i-1]=elements[length-i]; elements[length-i]=e; } }

2-12．第34页习题(12)

void pInvert(Node* first) {

Node *p=first,*q; first=NULL; while (p){

q=p->Link; p->Link=first;

}

first=p; p=q; }

第三章 栈与队列

1．第54页 习题(1）

设A 、B 、C 、D 、E 五个元素依次进栈(进栈后可立即出栈) ，问能否得到下列序列。若能得到，则给出相应的push 和pop 序列；若不能，则说明理由。 1）A,B,C,D,E 2) A,C,E,B,D

3) C,A,B,D,E 4) E,D,C,B,A 答：

（1） Push（A ）; Pop(A) ; Push(B); Pop(B);

Push(C) ; Pop(C); Push(D) ; Pop(D); Push(E) ; Pop(E);

2）不能得到，因为E ，B ，D 而言，E 最先出栈，则表明，此时B 和D 均在栈中，由于，B 先于D 进栈，所以应有D 先出栈。

3）不能得到，因为C, A, B 而言，C 最先出栈，则表明，此时A 和B 均在栈中，由于A 优先于B 近栈，所以B 应比A 先出栈。

(4) Push（A ）; Push（B ）; Push（C ）; Push（D ）；Push （E ）; Pop(E); Pop(D); Pop(C); Pop(B); Pop(A) ; 5.

TOP1 TOP2

栈满 Top2-Top1==1

Top1n-1 栈2空

9：void PrintQueue(Queue q) {

int first=q.Front+1;

while (((first)%q.MaxQueue)!=q.Rear)

{

printf("%d \n" ,q.Elements[first]); first=first+1; }

printf("%d \n" ,q.Elements[first]); }

void PrintQueue2(Queue q) {

for(int i=1; q.Front!=q.Rear; i++) {

printf("%d \n" ,q.Elements[(q.Front+1)%q.MaxQueue]); q.Front=(q.Front+1)%q.MaxQueue; } }

void PrintQueue3(Queue q) {

for(; q.Front!=q.Rear; q.Front=(q.Front+1)%q.MaxQueue) {

printf("%d \n" ,q.Elements[(q.Front+1)%q.MaxQueue]); } }

第四章 线性表与数组

1（85页）

int Search_Insert(List *lst, T x) {

int i, j;

j=lst->Size-1;

for (i=lst->Size-1; i>=0; i--) {

if(lst->Elements[i]==x) { return i; } }

if (lst->Size==lst->MaxList) {

return -1; }

while(lst->Elements[j]>x)

{ lst->Elements[j+1]=lst->Elements[j]; j--; } l st->Elements[j+1]=x; l st->Size++; r eturn j+1;

}

void Search_Delete(List *lst, T x, T y) {

int i=0;

if(lst->Size==0) { printf("the list is empty,can not be deleted!\n"); return; } f or (int j=0; jSize; j++) { if((lst->Elements[j]Elements[j]>y)) { lst->Elements[i]=lst->Elements[j]; i=i+1; } } l st->Size=i; }

13．（第86页，第13题）给出下列稀疏矩阵的

顺序三元组的行优先和列优先表示。 答：

14．（第86页，第14题）

对题图4-5的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。 答：

第五章 树

第2题，第141页，

对于三个结点A ，B 和C ，可分别组成多少不同的无序树、有序树和二叉树？ 答：（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵 第3题，P141

n 0=n2+2*n3+….+ (m-1)nm +1

第5题，P142

（1) 或者为空二叉树，或者所有结点的左子树都是空的单支树 （2）或者为空二叉树，或者只有根结点的二叉树

（3）或者为空二叉树，或者所有结点的右子树都是空的单支树

第7题，第142页，

给出对图6-31中的树的先序遍历和后序遍历的结果。

答：先序： D，E ，H, F，J ，G ，C, K ,A，B

中序：H ， E， J， F，G ， K ， C，D, A， B 后序：H ，J ，K ， C，G, F，E ， B，A, D

第6 题 第142页，

设对一棵二叉树进行中序遍历和后序遍历的结果分别为： （1）中序遍历 B D C E A F H G （2）后序遍历 D E C B H G F A 画出该二叉树。 答：

第8（3）题 第142页， int count=0；

void SizeOfLeaf(BTNode *t) { if (t){ if((!(t->RChild))&&(!(t->LChild))) { count=count+1; } SizeOfLeaf(t->LChild); SizeOfLeaf(t->RChild); }

}

第13题 第142页，

将图题6-32中的树转换成二叉树，

并将图6-31中的二叉树转换成森林。

第18题 第1438页，

设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W 为各字符的频率。

（1) 画出哈夫曼树 （2）计算带权路径长度

编码：A ：1010 B: 1011 C: 100 D: 00

E:01 F: 11

第六章 集合

第4题，P155

对半搜索算法要求其必须针对顺序存储的有序表。 顺序搜索从头搜到尾，所以不影响。

补充：

已知（1，2，3，4，5，6，7，8，9，10，11）找到9比较几次？ M=(1+11)/2=6 比较一次 6

9=9 比较2次 成功

所以一共比较2次成功

第七章 搜索树

1．第189页，第（1）,

建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依此删除76，45，则树形分别如何？

第八章 散列与跳表

第3题，第209页，

设散列表ht[11]，散列函数h(key)=key % 11。采用线性探查法解决冲突，试用关键字值序 列：70，25，80，35，60，45，50，55 建立散列表。

线性探查法：

伪随机探查法：P=13

对60： （5+13）%11=7

二次探查法

对35： （2+1*1）%11=3 （2-1*1）%11=1 对45： （1+1*1）%11=2 （12-1*1）%11=0 对55： （0+1*1）%11=1 （0-1*1）%11=10

第4题，第209页，

对45： （1+1*1）%11=2 （1+2*1）%11=3

（1+3*1）%11=4 （1+4*1）%11=5 （1+5*1）%11=6

对50： （6+1*6）%11=1 （6+2*6）%11=7

第九章 图

第（1）题 ， 第243页， 对下面的有向图求

(1) 每个顶点的入度和出度； (2) 强连通分量 (3) 邻接矩阵

第（2）题 ， 第243页，

当以边〈1，0〉，〈1，3〉，〈2，1〉，〈2，4〉，〈3，2〉，〈3，4〉，〈4，0〉，〈4，1〉，〈4，5〉， 〈5，0〉的次序从只有6个顶点没有边的图开始，通过依此插入这些边，建立邻接表结构。 画出该邻接表。

深度优先遍历：0，1，3，4，5，2 宽度优先遍历：0，1，3，4，2，5

第14题 P244

第11章

P11-2

直接插入排序：

初始序列（61）87 12 03 08 70 97 75 53 26 第1趟 （61 87）12 03 08 70 97 75 53 26 第2趟 （12 61 87）03 08 70 97 75 53 26 第3趟 （03 12 61 87）08 70 97 75 53 26 第4趟 （03 08 12 61 87）70 97 75 53 26 第5趟 （03 08 12 61 70 87） 97 75 53 26 第6趟 （03 08 12 61 70 87 97）75 53 26 第7趟 （03 08 12 61 70 75 87 97）53 26 第8趟 （03 08 12 53 61 70 75 87 97）26 第9趟 （03 08 12 26 53 61 70 75 87 97）

简单选择排序

初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 （03）87 12 61 08 70 97 75 53 26 第2趟 （03 08）12 61 87 70 97 75 53 26 第3趟 （03 08 12）61 87 70 97 75 53 26 第4趟 （03 08 12 26）87 70 97 75 53 61 第5趟 （03 08 12 26 53）70 97 75 87 61 第6趟 （03 08 12 26 53 61）97 75 87 70 第7趟 （03 08 12 26 53 61 70）75 87 97 第8趟 （03 08 12 26 53 61 70 75）87 97 第9趟 （03 08 12 26 53 61 70 75 87）97

冒泡排序

初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 61 12 03 08 70 87 75 53 26 97

第2趟 12 03 08 61 70 75 53 26 87 97 第3趟 03 08 12 61 70 53 26 75 87 97 第4趟 03 08 12 61 53 26 70 75 87 97 第5趟 03 08 12 53 26 61 70 75 87 97 第6趟 03 08 12 26 53 61 70 75 87 97 第7趟 03 08 12 26 53 61 70 75 87 97

快速排序：

初始序列 61 87 12 03 08 70 97 75 53 26 第1趟 53 26 12 03 08 61 97 75 70 87 第2趟 08 26 12 03 53 61 97 75 70 87 第3趟 03 08 12 26 53 61 97 75 70 87 第4趟 03 08 12 26 53 61 97 75 70 87 第5趟 03 08 12 26 53 61 87 75 70 97 第6趟 03 08 12 26 53 61 70 75 87 97 第7趟 03 08 12 26 53 61 70 75 87 97

第一章 绪论

1．（第14页，第（18）题）

确定划线语句的执行次数，计算它们的渐近时间复杂度。 (1) i=1; k=0; do {

k=k+10*i; i++; } while(i

划线语句的执行次数为 n-1（n>=2），n=1时执行1次 。 (2）i=1; x=0; do{

x++; i=2*i; } while （i

划线语句的执行次数为 ⎡log 2n ⎤。 (3) for(int i=1;i

划线语句的执行次数为n(n+1)(n+2)/6 。 (4）x=n;y=0;

while(x>=(y+1)*(y+1)) y++; 划线语句的执行次数为⎣ √n ⎦。

第二章 两种基本的数据结构

2-4．

Loc(A[i][j][k])=134+(i*n*p+j*p+k)*2

2-9. 第34页 习题(2).9

void Invert(T elements[], int length) {//length数组长度 // elements[]为需要逆序的数组 T e;

for (int i=1;i

e=elements[i-1];

elements[i-1]=elements[length-i]; elements[length-i]=e; } }

2-12．第34页习题(12)

void pInvert(Node* first) {

Node *p=first,*q; first=NULL; while (p){

q=p->Link; p->Link=first;

}

first=p; p=q; }

第三章 栈与队列

1．第54页 习题(1）

设A 、B 、C 、D 、E 五个元素依次进栈(进栈后可立即出栈) ，问能否得到下列序列。若能得到，则给出相应的push 和pop 序列；若不能，则说明理由。 1）A,B,C,D,E 2) A,C,E,B,D

3) C,A,B,D,E 4) E,D,C,B,A 答：

（1） Push（A ）; Pop(A) ; Push(B); Pop(B);

Push(C) ; Pop(C); Push(D) ; Pop(D); Push(E) ; Pop(E);

2）不能得到，因为E ，B ，D 而言，E 最先出栈，则表明，此时B 和D 均在栈中，由于，B 先于D 进栈，所以应有D 先出栈。

3）不能得到，因为C, A, B 而言，C 最先出栈，则表明，此时A 和B 均在栈中，由于A 优先于B 近栈，所以B 应比A 先出栈。

(4) Push（A ）; Push（B ）; Push（C ）; Push（D ）；Push （E ）; Pop(E); Pop(D); Pop(C); Pop(B); Pop(A) ; 5.

TOP1 TOP2

栈满 Top2-Top1==1

Top1n-1 栈2空

9：void PrintQueue(Queue q) {

int first=q.Front+1;

while (((first)%q.MaxQueue)!=q.Rear)

{

printf("%d \n" ,q.Elements[first]); first=first+1; }

printf("%d \n" ,q.Elements[first]); }

void PrintQueue2(Queue q) {

for(int i=1; q.Front!=q.Rear; i++) {

printf("%d \n" ,q.Elements[(q.Front+1)%q.MaxQueue]); q.Front=(q.Front+1)%q.MaxQueue; } }

void PrintQueue3(Queue q) {

for(; q.Front!=q.Rear; q.Front=(q.Front+1)%q.MaxQueue) {

printf("%d \n" ,q.Elements[(q.Front+1)%q.MaxQueue]); } }

第四章 线性表与数组

1（85页）

int Search_Insert(List *lst, T x) {

int i, j;

j=lst->Size-1;

for (i=lst->Size-1; i>=0; i--) {

if(lst->Elements[i]==x) { return i; } }

if (lst->Size==lst->MaxList) {

return -1; }

while(lst->Elements[j]>x)

{ lst->Elements[j+1]=lst->Elements[j]; j--; } l st->Elements[j+1]=x; l st->Size++; r eturn j+1;

}

void Search_Delete(List *lst, T x, T y) {

int i=0;

if(lst->Size==0) { printf("the list is empty,can not be deleted!\n"); return; } f or (int j=0; jSize; j++) { if((lst->Elements[j]Elements[j]>y)) { lst->Elements[i]=lst->Elements[j]; i=i+1; } } l st->Size=i; }

13．（第86页，第13题）给出下列稀疏矩阵的

顺序三元组的行优先和列优先表示。 答：

14．（第86页，第14题）

对题图4-5的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。 答：

第五章 树

第2题，第141页，

对于三个结点A ，B 和C ，可分别组成多少不同的无序树、有序树和二叉树？ 答：（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵 第3题，P141

n 0=n2+2*n3+….+ (m-1)nm +1

第5题，P142

（1) 或者为空二叉树，或者所有结点的左子树都是空的单支树 （2）或者为空二叉树，或者只有根结点的二叉树

（3）或者为空二叉树，或者所有结点的右子树都是空的单支树

第7题，第142页，

给出对图6-31中的树的先序遍历和后序遍历的结果。

答：先序： D，E ，H, F，J ，G ，C, K ,A，B

中序：H ， E， J， F，G ， K ， C，D, A， B 后序：H ，J ，K ， C，G, F，E ， B，A, D

第6 题 第142页，

设对一棵二叉树进行中序遍历和后序遍历的结果分别为： （1）中序遍历 B D C E A F H G （2）后序遍历 D E C B H G F A 画出该二叉树。 答：

第8（3）题 第142页， int count=0；

void SizeOfLeaf(BTNode *t) { if (t){ if((!(t->RChild))&&(!(t->LChild))) { count=count+1; } SizeOfLeaf(t->LChild); SizeOfLeaf(t->RChild); }

}

第13题 第142页，

将图题6-32中的树转换成二叉树，

并将图6-31中的二叉树转换成森林。

第18题 第1438页，

设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W 为各字符的频率。

（1) 画出哈夫曼树 （2）计算带权路径长度

编码：A ：1010 B: 1011 C: 100 D: 00

E:01 F: 11

第六章 集合

第4题，P155

对半搜索算法要求其必须针对顺序存储的有序表。 顺序搜索从头搜到尾，所以不影响。

补充：

已知（1，2，3，4，5，6，7，8，9，10，11）找到9比较几次？ M=(1+11)/2=6 比较一次 6

9=9 比较2次 成功

所以一共比较2次成功

第七章 搜索树

1．第189页，第（1）,

建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依此删除76，45，则树形分别如何？

第八章 散列与跳表

第3题，第209页，

设散列表ht[11]，散列函数h(key)=key % 11。采用线性探查法解决冲突，试用关键字值序 列：70，25，80，35，60，45，50，55 建立散列表。

线性探查法：

伪随机探查法：P=13

对60： （5+13）%11=7

二次探查法

对35： （2+1*1）%11=3 （2-1*1）%11=1 对45： （1+1*1）%11=2 （12-1*1）%11=0 对55： （0+1*1）%11=1 （0-1*1）%11=10

第4题，第209页，

对45： （1+1*1）%11=2 （1+2*1）%11=3

（1+3*1）%11=4 （1+4*1）%11=5 （1+5*1）%11=6

对50： （6+1*6）%11=1 （6+2*6）%11=7

第九章 图

第（1）题 ， 第243页， 对下面的有向图求

(1) 每个顶点的入度和出度； (2) 强连通分量 (3) 邻接矩阵

第（2）题 ， 第243页，

当以边〈1，0〉，〈1，3〉，〈2，1〉，〈2，4〉，〈3，2〉，〈3，4〉，〈4，0〉，〈4，1〉，〈4，5〉， 〈5，0〉的次序从只有6个顶点没有边的图开始，通过依此插入这些边，建立邻接表结构。 画出该邻接表。

深度优先遍历：0，1，3，4，5，2 宽度优先遍历：0，1，3，4，2，5

第14题 P244

第11章

P11-2

直接插入排序：

初始序列（61）87 12 03 08 70 97 75 53 26 第1趟 （61 87）12 03 08 70 97 75 53 26 第2趟 （12 61 87）03 08 70 97 75 53 26 第3趟 （03 12 61 87）08 70 97 75 53 26 第4趟 （03 08 12 61 87）70 97 75 53 26 第5趟 （03 08 12 61 70 87） 97 75 53 26 第6趟 （03 08 12 61 70 87 97）75 53 26 第7趟 （03 08 12 61 70 75 87 97）53 26 第8趟 （03 08 12 53 61 70 75 87 97）26 第9趟 （03 08 12 26 53 61 70 75 87 97）

简单选择排序

初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 （03）87 12 61 08 70 97 75 53 26 第2趟 （03 08）12 61 87 70 97 75 53 26 第3趟 （03 08 12）61 87 70 97 75 53 26 第4趟 （03 08 12 26）87 70 97 75 53 61 第5趟 （03 08 12 26 53）70 97 75 87 61 第6趟 （03 08 12 26 53 61）97 75 87 70 第7趟 （03 08 12 26 53 61 70）75 87 97 第8趟 （03 08 12 26 53 61 70 75）87 97 第9趟 （03 08 12 26 53 61 70 75 87）97

冒泡排序

初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 61 12 03 08 70 87 75 53 26 97

第2趟 12 03 08 61 70 75 53 26 87 97 第3趟 03 08 12 61 70 53 26 75 87 97 第4趟 03 08 12 61 53 26 70 75 87 97 第5趟 03 08 12 53 26 61 70 75 87 97 第6趟 03 08 12 26 53 61 70 75 87 97 第7趟 03 08 12 26 53 61 70 75 87 97

快速排序：

初始序列 61 87 12 03 08 70 97 75 53 26 第1趟 53 26 12 03 08 61 97 75 70 87 第2趟 08 26 12 03 53 61 97 75 70 87 第3趟 03 08 12 26 53 61 97 75 70 87 第4趟 03 08 12 26 53 61 97 75 70 87 第5趟 03 08 12 26 53 61 87 75 70 97 第6趟 03 08 12 26 53 61 70 75 87 97 第7趟 03 08 12 26 53 61 70 75 87 97


相关文章

  • 商务礼仪考核题目-礼仪培训师陈慧华推荐

    • 商务礼仪考试题目-礼仪培训师陈慧华推荐 三个备选项 1．当别人介绍的时候说错了你的名字,你应该( ). A .不要去纠正,免得对方难堪 B .礼貌地加以纠正,希望对方能够纠正 C .很生气,表示不予理睬 2．作为一名商务人员.在进入接见方的 ...查看


  • 二叉树的遍历 1

    • 课 程 设 计 课程设计名称: 数据结构课程设计 专 业 班 级 : 学 生 姓 名 : 学 号 : 指 导 教 师 : 课程设计时间: 2015.6.29-2015.7.10 1.需求分析 题目:二叉树的前序.中序.后序的递归非递归的遍历 ...查看


  • 计算机科学与技术专业 主要课程

    • 计算机科学与技术专业 03023001 高等数学 Higher Mathematics [192-11-1.2] 内容提要:作为本专业的重要基础课程,内容以微积分.中值定理.不定积分.定积分及其应用,多元 函数微分法及其应用.重积分.曲线积 ...查看


  • 考试科目-云南师范大学研究生部

    • 考试科目 211 翻译硕士英语 考试范围 211 张汉熙, <高级英语> ,外语教学与研究出版社,1995 修订本 333<教育学原理>,王道俊.郭文安主编,人民教育出版社 2009 年 <中国教育史>, ...查看


  • 本科毕业设计任务书

    • 江 西 理 工 大 学 本 科 毕 业 设 计(论文)任 务 书 电气工程与自动化学院电气工程及其自动化专业08级(12届)1班28号江浪 题 目:轧钢棒材生产线步进式冷床的PLC控制系统(软件设计) 专题题目(若无专题则不填) 原始依据( ...查看


  • 语文:第3课[山行]同步测试(北师大版七年级上)

    • <山行> 第二题 "霜叶红于二月花"为什么成为千古名句?"主编导读"及相关的参考资料已作了详尽的分析.引导学生理解.领会时,要把握几个要点: ①对比.比喻新异.一般而言,秋叶意味着飘零.衰 ...查看


  • 大学几乎所有学科的课本答案[2]

    • 大学几乎所有学科的课本答案! 来源: 任明嘉的日志 经济金融 [PDF格式]<会计学原理>同步练习题答案 [Word格式]<成本会计>习题及答案(自学推荐,23页) [Word格式]<成本会计>配套习题集 ...查看


  • 网络营销实务(高凤荣主编)课后习题及答案

    • 第一章 网络营销的理论基础 一.判断题 1. 网络营销是市场营销的未来发展方向.( ) 2. 网络营销就是利用互联网进行的销售行为.( ) 3. 电子商务是网络营销的 .( ) 4. 利用网络可以对传统营销关系进行整合.( ) 5. 企业对 ...查看


  • 论科学语言

    • 科学语言及科学语言的认知浅谈 摘 要: 科学语言要准确.严密.富有逻辑性,概念明确,善于推理判断,有理有据,不能有半点含糊,要有说服力,使人信服,以特定的语法.逻辑和数学规则建构的描述和说明科学理论的符号系统.科学本质上是语言的.本文集中论 ...查看


热门内容