附录习题参考答案
习题1参考答案
1.1.选择题
(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.)
A.
1.2.填空题
(1). 数据关系
(2). 逻辑结构物理结构
(3). 线性数据结构树型结构图结构
(4). 顺序存储链式存储索引存储散列表（Hash）存储
(5). 变量的取值范围操作的类别
(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系
(7). 关系网状结构树结构
(8). 空间复杂度和时间复杂度
数据结构与算法c++版 pdf(9). 空间时间
(10). Ο(n)
1.3 名词解释如下：
数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。
数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。
数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。
数据类型：是指变量的取值范围和所能够进行的操作的总和。
算法：是对特定问题求解步骤的一种描述，是指令的有限序列。
1.4 语句的时间复杂度为：
(1) Ο(n2)
(2) Ο(n2)
(3) Ο(n2)
(4) Ο(n-1)
(5) Ο(n3)
1.5 参考程序：
main()
{
int X,Y,Z；
scanf(“%d, %d, %d”,&X,&Y,Z)；
if (X>=Y)
if(X>=Z)
if (Y>=Z)
{ printf(“%d, %d, %d”,X,Y,Z);}
else
{ printf(“%d, %d, %d”,X,Z,Y);}
else
{ printf(“%d, %d, %d”,Z,X,Y);}
else
if(Z>=X)
if (Y>=Z)
{ printf(“%d, %d, %d”,Y,Z,X);}
else
{ printf(“%d, %d, %d”,Z,Y,X);}
else
{ printf(“%d, %d, %d”,Y,X,Z);}
}
1.6 参考程序：
main()
{
int i,n;
float x,a[],p;
printf(“\nn=”);scanf(“%f”,&n);
printf(“\nx=”);scanf(“%f”,&x);
for(i=0;i<=n;i++)
scanf(“%f ”,&a[i]);
p=a[0];
for(i=1;i<=n;i++)
{ p=p+a[i]*x;
x=x*x;}
printf(“%f”,p)’
}
习题2参考答案
2.1选择题
(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.
2.2.填空题
(1). 有限序列
(2). 顺序存储和链式存储
(3). Ｏ(n) O(n)
(4). n-i+1 n-i
(5). 链式
(6). 数据指针
(7). 前驱后继
(8). Ο(1) Ο(n)
(9). s->next=p->next; p->next=s ;
(10). s->next
2.3. 解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n，将下标为0，
1,2,…,（n-1）/2的元素依次与下标为n,n-1,…, （n-1）/2的元素交换，输出数组a的元素。
参考程序如下：
main()
{
int i,n;
float t,a[];
printf(“\nn=”);scanf(“%f”,&n);
for(i=0;i<=n-1;i++)
scanf(“%f ”,&a[i]);
for(i=0;i<=(n-1)/2;i++)
{ t=a[i]; a[i] =a[n-1-i]; a[n-1-i]=t;}
for(i=0;i<=n-1;i++)
printf(“%f”,a[i]);
}
2.4 算法与程序：
main()
{
int i,n;
float t,a[];
printf(“\nn=”);scanf(“%f”,&n);
for(i=0;i<n;i++)
scanf(“%f ”,&a[i]);
for(i=1;i<n;i++)
if(a[i]>a[0])
{ t=a[i]; a[i] =a[0]; a[0]=t;}
printf(“%f”,a[0]);
for(i=2;i<n;i++)
if(a[i]>a[1])
{ t=a[i]; a[i] =a[1]; a[1]=t;}
printf(“%f”,a[0]);
}
2.5 算法与程序：
main()
{
int i,j,k,n;
float x,t,a[];
printf(“\nx=”);scanf(“%f”,&x);
printf(“\nn=”);scanf(“%f”,&n);
for(i=0;i<n;i++)
scanf(“%f ”,&a[i]); // 输入线性表中的元素
for (i=0; i<n; i++) { // 对线性表中的元素递增排序
k=i;
for (j=i+1; j<n; j++) if (a[j]<a[k]) k=j;
if (k<>j) {t=a[i];a[i]=a[k];a[k]=t;}
}
for(i=0;i<n;i++) // 在线性表中到合适的位置
if(a[i]>x) break;
for(k=n-1;k>=i;i--) // 移动线性表中元素，然后插入元素x
a[k+1]=a[k];
a[i]=x;
for(i=0;i<=n;i++) // 依次输出线性表中的元素
printf(“%f”,a[i]);
}
2.6 算法思路：依次扫描A和B的元素，比较A、B当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，最后将未扫描完顺序表中的余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。
有序表的合并算法：
void merge (SeqList A, SeqList B, SeqList *C)
{ int i，j，k；
i=0；j=0；k=0；
while ( i<=A.last && j<=B.last )
if (A.data[i]<=B.data[j])
C->data[k++]=A.data[i++]；
else
C->data[k++]=B.data[j++]；
while (i<=A.last )
C->data[k++]= A.data[i++]；
while (j<=B.last )
C->data[k++]=B.data[j++]；
C->last=k-1；
}
2.7 算法思路：依次将A中的元素和B的元素比较，将值相等的元素赋给C，如此直到线性
表扫描完毕，线性表C就是所求递增有序线性表。
算法：
void merge (SeqList A, SeqList B, SeqList *C)
{ int i，j，k；
i=0；j=0；k=0；
while ( i<=A.last)
while（j<=B.last )
if (A.data[i]=B.data[j])
C->data[k++]=A.data[i++]；
C->last=k-1；
}
习题3参考答案
3.1.选择题
(1). D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB (11). D (12). B (13). D (14). C (15). C (16). D(17). D (18). C (19). C (20). C 3.2.填空题
（1）FILO, FIFO
（2）-1, 3 4 X * + 2 Y * 3 / -
（3）p, stack.p]=x
（4）p>llink->rlink=p->rlink, p->rlink->llink=p->rlink
（5）(R-F+M)%M
（6）top1+1=top2
（7）F==R
（8）front==rear
（9）front==(rear+1)%n
（10） N-1
3.3 答：一般线性表使用数组来表示的
线性表一般有插入、删除、读取等对于任意元素的操作
而栈只是一种特殊的线性表
栈只能在线性表的一端插入（称为入栈,push）或者读取栈顶元素或者称为“弹出、出栈”(pop)。
3.4 答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。
不同点：栈只在一端（栈顶）进行插入，删除操作；队列在一端（top）删除，一端(rear)插入。
3.5 答：可能序列有14种：ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA。
3.6 答：不能得到4，3，5，6，1，2，最先出栈的是4，则按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式进行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), pop(), push(6), pop()。
3.7 答：stack
3.8 非递归:
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论