第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
最全数据结构课后习题答案(耿国华版.doc
2.(1)×(2)×(3)√
3.（1）A（2）C（3）C
5.计算下列程序中x=x+1的语句频度
（2）通过全局变量隐式传递
习 题
实习题
(2) 链栈（top为栈顶指针，指向当前栈顶元素前面的头结点）
{ return(FALSE); printf(“\nNO”);}
{ /*删除队头元素，用x返回其值*/
第4章串
(2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余）
{/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/
第 1 章 绪 论
2.(1)×(2)×(3)√
3.（1）A（2）C（3）C
5.计算下列程序中 x=x+1 的语句频度
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
【解答】x=x+1 的语句频度为：
T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6
6.编写算法，求 一元多项式 pn(x)=a0+a1x+a2x2+…….+anxn 的值 pn(x0),并确定算法中每一语
句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求
幂函数。注意：本题中的输入为 ai(i=0,1,…n)、x 和 n,输出为 Pn(x0)。 算法的输入和输出采
用下列方法
（1）通过参数表中的参数显式传递
（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实
现输入输出。
【解答】
（1）通过参数表中的参数显式传递
优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通
用性强，移置性强。
缺点：形参须与实参对应，且返回值数量有限。
（2）通过全局变量隐式传递
优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗
缺点：函数通用性降低，移植性差
算法如下：通过全局变量隐式传递参数
PolyValue()
{ int i,n;
float x,a[],p;
printf(“\nn=”);
scanf(“%f”,&n);
printf(“\nx=”);
scanf(“%f”,&x);
for(i=0;i
s=a[0];
for(i=1;i<=n;i++)
{s=s+a[i]*p;
p=p*x;}
return(p);
}
算法的时间复杂度：T(n)=O(n)
/*执行次数:n 次*/
第 2 章 线性表
习 题
1.填空：
(1)在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入
或删除的位置有关。
(2)线性表有顺序和链式两种存储结构。在顺序表中，线性表的长度在数组定义时就已经确
定，是静态保存，在链式表中，整个链表由“头指针”来表示，单链表的长度是动态保存。
(3)在顺序表中，逻辑上相邻的元素，其物理位置＿一定＿＿＿＿＿相邻。在单链表中，逻
辑上相邻的元素，其物理位置不一定相邻。
(4)在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置
由头结点指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的 next 域指
示。
2.选择题
(1) A
(2) 已知 L 是无表头结点的单链表，且 P 结点既不是首元素结点，也不是尾元素结点。按要
求从下列语句中选择合适的语句序列。
a. 在 P 结点后插入 S 结点的语句序列是：E、A。
b. 在 P 结点前插入 S 结点的语句序列是：H、L、I、E、A。
c. 在表首插入 S 结点的语句序列是：F、M。
d. 在表尾插入 S 结点的语句序列是：L、J、A、G。
供选择的语句有：
A P->next=S;
B P->next= P->next->next;
C P->next= S->next;
D S->next= P->next;
E S->next= L;
F S->next= NULL;
G Q= P;
H while (P->next!=Q) P=P->next;
I while (P->next!=NULL) P=P->next;
J P= Q;
K P= L;
L L= S;
2
7 试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表
（a1,a2,…,an）逆置为(an,an-1,…,a1)。
【解答】（1）用一维数组作为存储结构
*num)
void invert(SeqList
*L,
int
M L= P;
(3) D
(4) D
(5) D
(6) A
{
}
j;
int
ElemType tmp;
for(j=0;j<=(*num-1)/2;j++)
{ tmp=L[j];
L[j]=L[*num-j-1];
L[*num-j-1]=tmp;}
（2）用单链表作为存储结构
void invert(LinkList L)
{
Node *p, *q, *r;
if(L->next ==NULL)
p=L->next;
q=p->next;
p->next=NULL;
while(q!=NULL)
r=q->next;
q->next=L->next;
L->next=q;
q=r;
{
}
}
return;
/*链表为空*/
/* 摘下第一个结点，生成初始逆置表 */
/* 从第二个结点起依次头插入当前逆置表 */
11 将 线 性 表 A=(a1,a2,……am), B=(b1,b2,……bn) 合 并 成 线 性 表 C,
C=(a1,b1,……am,bm,bm+1,…….bn) 当 m<=n 时，或 C=(a1,b1, ……an,bn,an+1,……am)
当 m>n 时,线性表 A、B、C 以单链表作为存储结构，且 C 表利用 A 表和 B 表中的结点空间
构成。注意：单链表的长度值 m 和 n 均未显式存储。
【解答】算法如下：
LinkList merge(LinkList A, LinkList B, LinkList C)
{ Node *pa, *qa, *pb, *qb, *p;
/*pa 表示 A 的当前结点*/
/ *利用 p 来指向新连接的表的表尾，初始值指向表 A 的头结点*/
/*利用尾插法建立连接之后的链表*/
/*交替选择表 A 和表 B 中的结点连接到新链表中；*/
pa=A->next;
pb=B->next;
p=A;
while(pa!=NULL && pb!=NULL)
{ qa=pa->next;
qb=qb->next;
p->next=pa;
p=pa;
p->next=pb;
p=pb;
3
pa=qa;
pb=qb;
}
if(pa!=NULL) p->next=pa;
if(pb!=NULL) p->next=pb;
C=A;
Return(C);
}
实习题
/*A 的长度大于 B 的长度*/
/*B 的长度大于 A 的长度*/
约瑟夫环问题
约瑟夫问题的一种描述为：编号 1,2,…,n 的 n 个人按顺时针方向围坐一圈，每个人持有一
个密码（正整数）。一开始任选一个报数上限值 m,从第一个人开始顺时针自 1 开始顺序报
数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上
的下一个人开始重新从 1 报数，如此下去，直至所有的人全部出列为止。试设计一个程序，
求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编
号。
例如 m 的初值为 20；n=7，7 个人的密码依次是：3,1,7,2,4,8,4,出列顺序为 6,1,4,7,2,3,5。
【解答】算法如下：
typedef struct Node
{
int password;
int num;
struct Node *next;
} Node,*Linklist;
void Josephus()
{
/*初始化单向循环链表*/
Linklist L;
Node *p,*r,*q;
int m,n,C,j;
L=(Node*)malloc(sizeof(Node));
if(L==NULL) { printf("\n 链表申请不到空间!");return;}
L->next=NULL;
r=L;
printf("请输入数据 n 的值(n>0):");
scanf("%d",&n);
for(j=1;j<=n;j++)
{
/*建立链表*/
p=(Node*)malloc(sizeof(Node));
if(p!=NULL)
{
printf("请输入第%d 个人的密码:",j);
scanf("%d",&C);
p->password=C;
p->num=j;
r->next=p;
r=p;
}
}
r->next=L->next;
4
printf("请输入第一个报数上限值 m(m>0):");
scanf("%d",&m);
printf("*****************************************\n");
printf("出列的顺序为:\n");
q=L;
p=L->next;
while(n!=1)
{
/*计算出列的顺序*/
j=1;
while(jnext;
j++;
/*计算当前出列的人选 p*/
/*q 为当前结点 p 的前驱结点*/
/*获得新密码*/
/*p 出列*/
}
printf("%d->",p->num);
m=p->password;
n--;
q->next=p->next;
r=p;
p=p->next;
free(r);
}
printf("%d\n",p->num);
}
第 3 章 限定性线性表 — 栈和队列
第三章答案
1 按 3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：
（1） 如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？
（2） 如进站的车厢序列为 123456，能否得到 435612 和 135426 的出站序列，并说
明原因（即写出以“S”表示进栈、“X”表示出栈的栈序列操作）。
【解答】
（1）可能得到的出站车厢序列是：123、132、213、231、321。
(2)不能得到 435612 的出站序列。
因为有 S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此时按照“后进先出”的原
则，出栈的顺序必须为 X(2)X(1)。
能得到 135426 的出站序列。
因为有 S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。
3 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？
【解答】（1）顺序栈 （top 用来存放栈顶元素的下标）
判断栈 S 空：如果 S->top==-1 表示栈空。
判断栈 S 满：如果 S->top==Stack_Size-1 表示栈满。
(2) 链栈（top 为栈顶指针，指向当前栈顶元素前面的头结点）
判断栈空：如果 top->next==NULL 表示栈空。
判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。
4 照四则运算加、减、乘、除和幂运算的优先惯例，画出对下列表达式求值时操作数栈和
运算符栈的变化过程：A-B*C/D+E↑F
5
【解答】
*S;
ch,temp;
Stack
Char
InitStack(&S);
Printf(“\n 请输入字符序列：”);
Ch=getchar();
While( ch!=&)
{ Push(&S,ch);
ch=getchar();
}
do
{ ch=getchar();
Pop(&S,&temp);
if(ch!= temp)
{ return(FALSE); printf(“\nNO”);}
} while(ch!=@ && !IsEmpty(&S))
/*序列 1 入栈*/
/*判断序列 2 是否是序列 1 的逆序列*/
/*序列 2 不是序列 1 的逆序列*/
/*序列 2 是序列 1 的逆序列*/
5 写一个算法，判断依次读入的一个以@为结束符的字母序列，是否形如‘序列 1&序列 2’
的字符序列。序列 1 和序列 2 中都不含‘&’，且序列 2 是序列 1 的逆序列。例如，’a+b&b+a’
是属于该模式的字符序列，而’1+3&3-1’则不是。
【解答】算法如下：
IsHuiWen()
int
{
if(ch = = @ &&
IsEmpty(&S))
{ return(TRUE); printf(“\nYES”);}
{return(FALSE); printf(“\nNO”);}
else
}/*IsHuiWen()*/
8 要求循环队列不损失一个空间全部都能得到利用，设置一个标志 tag,以 tag 为 0 或 1 来
区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。
【解答】入队算法：
int EnterQueue(SeqQueue *Q, QueueElementType x)
{
/*将元素 x 入队*/
6
if(Q->front==Q->front && tag==1)
return(FALSE);
if(Q->front==Q->front && tag==0)
tag=1;
Q->elememt[Q->rear]=x;
Q->rear=(Q->rear+1)%MAXSIZE;
Return(TRUE);
/*队满*/
/*x 入队前队空，x 入队后重新设置标志*/
/*设置队尾指针*/
}
出队算法：
int DeleteQueue( SeqQueue *Q , QueueElementType *x)
{ /*删除队头元素，用 x 返回其值*/
if(Q->front==Q->rear && tag==0)
/*队空*/
return(FALSE);
*x=Q->element[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
if(Q->front==Q->rear)
Return(TUUE);
tag=0;
}
/*重新设置队头指针*/
/*队头元素出队后队列为空，重新设置标志域*/
第 4 章 串
第四章答案
1 设 s=’I AM A STUDENT’，t=’GOOD’， q=’WORKER’。给出下列操作的结果：
【解答】StrLength(s)=14;
SubString(sub1,s,1,7)
SubString(sub2,s,7,1)
StrIndex(s,4,’A’)=6;
StrReplace(s,’STUDENT’,q);
StrCat(StrCat(sub1,t),StrCat(sub2,q))
sub1=’I AM A ’;
sub2=’ ’;
s=’I AM A WORKER’;
sub1=’I AM A GOOD WORKER’。
2 编写算法，实现串的基本操作 StrReplace(S,T,V)。
【解答】算法如下：
strReplace(SString S,SString T, SString V)
int
{/*用串 V 替换 S 中的所有子串 T */
return(0);
int pos,i;
pos=strIndex(S,1,T);
if(pos = = 0)
while(pos!=0)
{
switch(T.len-V.len)
{
case 0:
/*求 S 中子串 T 第一次出现的位置*/
/*用串 V 替换 S 中的所有子串 T */
for(i=0;i<=V.len;i++)
S->ch[pos+i]=V.ch[i];
case >0:
for(i=pos+t.ien;ilen;i--)
S->ch[i-t.len+v.len]=S->ch[i];
for(i=0;i<=V.len;i++)
S->ch[pos+i]=V.ch[i];
7
/*串 T 的长度等于串 V 的长度*/
/*用 V 替换 T*/
/*串 T 的长度大于串 V 的长度*/
/*将 S 中子串 T 后的所有字符
前移 T.len-V.len 个位置*/
/*用 V 替换 T*/
S->len=S->len-T.len+V.len;
case <0:
/*串 T 的长度小于串 V 的长度*/
/*插入后串长小于 MAXLEN*/
if(S->len-T.len+V.len)<= MAXLEN
{ /*将 S 中子串 T 后的所有字符后移 V.len-T.len 个位置*/
for(i=S->len-T.len+V.len;i>=pos+T.len;i--)
S->ch[i]=S->ch[i-T.len+V.len];
/*用 V 替换 T*/
for(i=0;i<=V.len;i++)
S->ch[pos+i]=V.ch[i];
S->len=S->len-T.len+V.len; }
else
{
/*替换后串长>MAXLEN,但串 V 可以全部替换*/
if(pos+V.len<=MAXLEN)
{
for(i=MAXLEN-1;i>=pos+T.len; i--)
S->ch[i]=s->ch[i-T.len+V.len]
for(i=0;i<=V.len;i++)
S->ch[pos+i]=V.ch[i];
S->len=MAXLEN;}
else
{
for(i=0;ich[i+pos]=V.ch[i];
S->len=MAXLEN;}
/*用 V 替换 T*/
/*串 V 的部分字符要舍弃*/
/*求 S 中下一个子串 T 的位置*/
}/*switch()*/
pos=StrIndex(S,pos+V.len,T);
}/*while()*/
return(1);
}/*StrReplace()*/
第五章 数组和广义表
1.假设有 6 行 8 列的二维数组 A，每个元素占用 6 个字节，存储器按字节编址。已知 A 的
基地址为 1000，计算：
第五章答案
（1） 数组 A 共占用多少字节； （288）
（2） 数组 A 的最后一个元素的地址； （1282）
（3） 按行存储时，元素 A36 的地址； （1126）
（4） 按列存储时，元素 A36 的地址； （1192）
4.设有三对角矩阵 An×n,将其三条对角线上的元素逐行的存于数组 B[1..3n-2]中，使得
B[k]=aij，求：（1）用 i,j 表示 k 的下标变换公式；（2）用 k 表示 i、j 的下标变换公式。
【解答】（1）k=2(i-1)+j
(2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余）
5.在稀疏矩阵的快速转置算法 5.2 中，将计算 position[col]的方法稍加改动，使算法只占用
一个辅助向量空间。
【解答】算法（一）
FastTransposeTSMatrix(TSMartrix A, TSMatrix
{/*把矩阵 A 转置到 B 所指向的矩阵中去，矩阵用三元组表表示*/
*B)
int col,t,p,q;
int position[MAXSIZE];
B->len=A.len; B->n=A.m; B->m=A.n;
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
