数据结构C语言课后习题答案(耿国华版)

格式：ppt
大小：569.50 KB
文档页数：39

下载文档原格式

/ 39

《数据结构——C语言描述》习题及答案耿国华

第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

数据结构——C语言描述习题及答案耿国华

第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。

数据结构——C语言描述习题及答案耿国华

第1章绪论习题一、问答题1.什么是数据结构？2.四类基本数据结构的名称与含义。

3.算法的定义与特性。

4.算法的时间复杂度。

5.数据类型的概念。

6.线性结构与非线性结构的差别。

7.面向对象程序设计语言的特点。

8.在面向对象程序设计中，类的作用是什么？9.参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2.算法就是程序。

3.在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时： 1 = (1+1)×1/2 = (1+12)/2i=2时： 1+2= (1+2)×2/2 = (2+22)/2i=3时： 1+2+3= (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n= (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

数据结构-用C语言描述习题及答案-耿国华

第1章绪论习题一、问答题1.什么是数据结构？2.四类基本数据结构的名称与含义。

3.算法的定义与特性。

4.算法的时间复杂度。

5.数据类型的概念。

6.线性结构与非线性结构的差别。

7.面向对象程序设计语言的特点。

8.在面向对象程序设计中，类的作用是什么？9.参数传递的主要方式及特点。

10.抽象数据类型的概念。

二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2.算法就是程序。

3.在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时： 1 = (1+1)×1/2 = (1+12)/2i=2时： 1+2= (1+2)×2/2 = (2+22)/2i=3时： 1+2+3= (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n= (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。

《数据结构——C语言描述》习题及答案耿国华

第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。

《数据结构——C语言描述》习题及答案耿国华

第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。

《数据结构——C语言描述》习题及答案-耿国华

第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。

《数据结构——C语言描述》习题及答案耿国华

第1章绪论之蔡仲巾千创作习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的不同。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;[提示]：i=1时：1 = (1+1)×1/2 = (1+12)/2i=2时：1+2 = (1+2)×2/2 = (2+22)/2i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2…i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2=[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)) = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不克不及使用求幂函数。

注意：本题中的输入ai(i=0,1,…,n), x和n，输出为Pn(x0).通常算法的输入和输出可采取下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。

数据结构-用C语言描述习题及答案-耿国华

for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1;
[提示]： i=1 时： 1 = (1+1)×1/2 = (1+12)/2 i=2 时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3 时： 1+2+3 = (1+3)×3/2 = (3+32)/2
L－>elem[ m－k ] = L－>elem[ m ]; < 方法 2 > 同时以待移动元素下标 m 和应移入位置 j 为中心： < 方法 3 > 以应移入位置 j 增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于 mink 且小于 maxk 的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink 和 maxk 是给定的两个参变量，它们的值为任意的整数）。 [提示]：注意检查 mink 和 maxk 的合法性：mink < maxk
第1章绪论
习题
一、问答题 1. 什么是数据结构 2. 四类基本数据结构的名称与含义。 3. 算法的定义与特性。 4. 算法的时间复杂度。 5. 数据类型的概念。 6. 线性结构与非线性结构的差别。 7. 面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么 9. 参数传递的主要方式及特点。 10. 抽象数据类型的概念。二、判断题 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 2. 算法就是程序。 3. 在高级语言（如 C、或 PASCAL）中，指针类型是原子类型。三、计算下列程序段中 X=X+1 的语句频度

《数据结构——C语言描述》习题和答案耿国华

第1章绪论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。

3. 算法的定义与特性。

4. 算法的时间复杂度。

5. 数据类型的概念。

6. 线性结构与非线性结构的差别。

7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。

10. 抽象数据类型的概念。

二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

2. 算法就是程序。

3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

}
//两个串的比较 int StrCompare(LinkString *S,LinkString *T) { SNode *q,*p; p=S->head->next; q=T->head->next;
//p,q分别指向两个串的开始
while(p&&q) { if(p->ch!=q->ch) return(p->ch - q->ch); //如果当前字符不相等，返回它们的差 p=p->next; q=q->next; } return(S->len - T->len); 差 } //如果对应位置的字符都相等，返回串的长度
5.4利用一个辅助向量空间的矩阵快速转置法
FastTransposeMatrix( TSMatrix A , TSMatrix *B) {/* 利用一个辅助向量空间的矩阵快速转置法 */ int col, t, p, q, pos[MAXSIZE+1]; B->len=A.len; B->n=A.m; B->m=A.n; if( B->len) { for( t=1; t<=A.n; t++ ) pos[t]=0; for( t=1; t<A.len; t++) pos[ A.data[t].col ]++ ; pos[0]=1; for( t=1; t<A.n; t++) pos[t]=pos[t]+pos[t-1]; for( t=A.n; t>=1; t--) pos[t]=pos[t-1];
第一步：v1到v3的路径v1,v3；长度15；新 S={V1，v3}； v1 dist[ ] path[ ] 0 v2 19
v1,v3,v2
v3 15
v1,v3
v4 ∞
v5 25
v1,v3,v5
v6 ∞
第二步： v1到v2的路径v1,v3,v2；长度19；新 S={V1，v3，v2}；
v1
dist[ ] path[ ] 0
v2
19
v1,v3,v2
v3
15
v1,v3
v4
29
v1,v3,v2,v4
v5
25
v1,v3,v5
v6
∞
第三步： v1到v5的路径v1,v3,v5；长度25；新 S={V1，v3，v2，v5}；
v1
dist[ ] path[ ] 0
v2
19
v1,v3,v2
v3
15
v1,v3
v4
29
v1,v3,v2,v4
v5
25
v1,v3,v5
v6
45
v1,v3,v5,v6
第四步： v1到v4的路径v1,v3,v2,v4；长度29；新 S={V1，v3，v2，v5,v4}；
v1 dist[ ] path[ ] 0 v2 19
6.4
E B F
A
C
D
G
H I K J
6.5(1)右单枝树 (2)左单枝树 (3)单根树或者空树
6.9 设左1右0
0.32
0.19
0.21
0.06
0.10
0.07
0.02
0.03
0.02 11111 0.03 11110 0.06 1110 0.07 1100 0.10 1101 0.19 01 0.21 00 0.32 10
6.24交换左右子树算法 void exchangechild(BiTree t) { BiTNode *p; if(t) { p=t->lchild; t->lchild=t->rchild; t->rchild=p; exchangechild(t->lchild); exchangechild(t->rchild); } } /*注意：不能用中序遍历来交换*/
（3）邻接表
V1 V2 V3 V4 1 2 3 1 4 6 5 6
V5
V6
1
2
5
（4）逆邻接表
略
（6）强连通分量（三个分量）
6
2 3 4 1 5
7.3用Dijkstra算法求顶点1到其余顶点的最短路径的过程：
初始状态：S={V1}； v1 dist[ ] path[ ] 0 v2 20 v1,v2 v3 15 v1,v3 v4 ∞ v5 ∞ v6 ∞
int IsReverse() 3-->5 判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 { SeqStack s; char e; InitStack(&s); while((e=getchar())!='&') { if(e==’@’) return 0;//不允许在’&’之前出现’@’ push(&s,e); } while( (e=getchar())!='@') { if(IsEmpty(&s)) return 0; pop(&s,&c); if(e!=c) return 0; } if(!IsEmpty(s)) return 0; return 1; }//IsReverse
{if(Qtag==1&&Q-->front==Q-->rear)
return FALSE;//tag域的值为1表示“非空”
Qelement[Qrear]=x;
Qrear=(Q rear+1)%MAXSIZE;
if(Q tag==0) Q tag=1; //队列不空
return TRUE;
作业2.7 顺序表的就地逆置
void reverse(SeqList *L)//顺序表的就地逆置 { for(i=0,j=Llast; i<j; i++,j--) {t=Lelem[i]; Lelem[i]=Lelem[j]; Lelem[j]=t; } }//reverse
void LinkList_reverse(Linklist 作业 2.7链表的就地逆置 *L)
• 带tag域的循环队列类型定义：＃ define MAXSIZE 50 typedef struct { QueueElementType element[MAXSIZE]; int front, rear,tag; } SeqQueue;
注意：tag域的值为0表示“空”,1表示“非空 "
3-->8带tag域的循环队列入队算法 int EnterQueue(SeqQueue *Q,int x)
/*链表的就地逆置*/ { Node *p, *q;
p=L->next; L->next=NULL; while(p) { q=p; p=p->next; q->next=Lnext; /*把L的元素逐个插入新表表头之后*/ Lnext=q; } }/*LinkList_reverse*/
分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.
5.1,5.2
5.1(1) 6*8*6=288 (2) 1000+(5*8+7)*6=1282 (3) 1000+(2*8+5)*6=1126 (4) 1000+(5*6+2)*6=1192 5.2(1) k=(i-1)*3-1+(j-i+1)+1=2*(i-1)+j (2) i=k/3+1; j= (k/3+1)+(k%3-1)=k/3+k%3
4.3题参考答案
//串结点定义 typedef struct snode { char ch; struct snode *next; }SNode; //链串定义 typedef struct { SNode *head; SNode *tail; int len; }LinkString;
//将串常量chars赋值给串S int StriAsign(LinkString *S,char *chars) {SNode *new,*p; int i=0; //初始化串S为空链串 new=(SNode *)malloc(sizeof(SNode)); if(!new) return(ERROR); new->next=null; S->head=new; S->tail=p=new; //建立链串S，并将串chars复制到S中 while(chars[i]!='\0') { new=(SNode *)malloc(sizeof(SNode)); new->ch=chars[i]; p->next=new; p=new; i++; } p->next=null; //链表的表尾 S->tail=p; S->len=i; //串长度 return(OK);
作业2.11 A表和B表合并为C表
void merge1(LinkList *A,LinkList *B,LinkList *C)
/*链表A和B合并为C,A和B的元素间隔排列,且用原空间*/
{ Node *p, *q; p=A->next; q=B->next; C=A; while(p&&q) { s=p->next; p->next=q; /*将B的元素插入*/ if (s) { t=q->next; q->next=s; } /*如A非空,将A的元素插入*/ p=s;q=t; }/*while*/ }/*merge1 */
}//EnterQueue

数据结构C语言课后习题答案(耿国华版)

合集下载

《数据结构——C语言描述》习题及答案耿国华

数据结构——C语言描述习题及答案耿国华

数据结构——C语言描述习题及答案耿国华

数据结构-用C语言描述习题及答案-耿国华

《数据结构——C语言描述》习题及答案耿国华

《数据结构——C语言描述》习题及答案耿国华

《数据结构——C语言描述》习题及答案-耿国华

《数据结构——C语言描述》习题及答案耿国华

数据结构-用C语言描述习题及答案-耿国华

《数据结构——C语言描述》习题和答案耿国华

文档推荐

最新文档

数据结构C语言课后习题答案(耿国华版)

合集下载

《数据结构——C语言描述》习题及答案耿国华

数据结构——C语言描述习题及答案耿国华

数据结构——C语言描述习题及答案 耿国华

数据结构-用C语言描述习题及答案-耿国华

《数据结构——C语言描述》习题及答案 耿国华

《数据结构——C语言描述》习题及答案 耿国华

《数据结构——C语言描述》习题及答案-耿国华

《数据结构——C语言描述》习题及答案 耿国华

数据结构-用C语言描述习题及答案-耿国华

《数据结构——C语言描述》习题和答案 耿国华

文档推荐

最新文档

数据结构——C语言描述习题及答案耿国华

《数据结构——C语言描述》习题及答案耿国华

《数据结构——C语言描述》习题及答案耿国华

《数据结构——C语言描述》习题及答案耿国华

《数据结构——C语言描述》习题和答案耿国华