《数据结构习题参考答案.doc》由会员分享，可在线阅读，更多相关《数据结构习题参考答案.doc（29页珍藏版）》请在金锄头文库上搜索。
1、 附录 习题参考答案习题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). 空间复杂度和时间复杂度(9). 空间 时间(10). (n)1.3 名词解
2、释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述，是指令的有限序列。1.4 语句的时间复杂度为：(1) (n2) (2) (n2)(3) (n2)
3、(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()
4、 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,&ai); p=a0;for(i=1;inext=p-next; p-next=s ;(10). s-next 1参考程序如下：main() int i,n;float t,a;printf(nn=);scanf(%f,&n);for(i=0;i=n-1;i+)scanf(%f,&ai); for(i=0;i=(n-1)/2;i+) t=ai; ai =an-1-i; an-1-i=t; for(i=0;i
5、=n-1;i+) printf(%f,ai);2.4 算法与程序：main() int i,n;float t,a;printf(nn=);scanf(%f,&n);for(i=0;in;i+)scanf(%f,&ai); for(i=1;ia0 t=ai; ai =a0; a0=t; printf(%f,a0);for(i=2;ia1 t=ai; ai =a1; a1=t; printf(%f,a0);2.5 算法与程序：main() int i,j,k,n;float x,t,a;printf(nx=);scanf(%f,&x);printf(nn=);scanf(%f,&n);for(i
6、=0;in;i+)scanf(%f,&ai); /* 输入线性表中的元素*/for (i=0; in; i+) /* 对线性表中的元素递增排序 */ k=i; for (j=i+1; jn; j+) if (ajak) k=j; if (k!=j) t=ai;ai=ak;ak=t; for(i=0;ix) break;for(k=n-1;k=i;i-) /* 移动线性表中元素，然后插入元素x*/ ak+1=ak; ai=x; for(i=0;i=n;i+) /* 依次输出线性表中的元素 */printf(%f,ai);2.6 算法思路：依次扫描A和B的元素，比较A、B当前的元素的值，将较小值的
7、元素赋给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.dataidatak+=A.datai+； else C-datak+=B.dataj+；while (idatak+= A.datai+；while (jdatak+=B.dataj+；C-last=k-1； 2.7 算法思路：依次将A中
8、的元素和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（jdatak+=A.datai+； 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
9、(16). D(17). D (18). C (19). C (20). C 3.2.填空题（1） FILO, FIFO（2） -1, 3 4 X * + 2 Y * 3 / -（3） stack.top, stack.sstack.top=x（4） pllink-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-13.3 答：一般线性表使用数组来表示的线性表一般有插入、删除、读取等对于任意元素的操作而栈只是一种特殊的线性
10、表栈只能在线性表的一端插入（称为入栈,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
11、，按如下方式进行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), pop(), push(6), pop()。 3.7 答：stack3.8 非递归:int vonvert (int no,int a) /将十进制数转换为2进制存放在a，并返回位数int r;SeStack s,*p;P=&s;Init_stack(p);while(no)push(p,no%2);no/=10;r=0;while(!empty_stack(p)pop(p,a+r);r+;return r;递归算法:void convert(int no)if(no/20)Convert(no/2);Printf(“%d”,no%2);elseprintf(“%d”,no); 3.9 参考程序：void view(SeStack s)SeStack *p; /假设栈元素为字符型 char c;p=&s;while(!empty_stack(p)c=pop(p);printf(“%c”,c);printf(”n”);3.10 答：char3.11 参考程序：voi
