数据结构习题参考答案

《数据结构习题参考答案》由会员分享，可在线阅读，更多相关《数据结构习题参考答案（32页珍藏版）》请在装配图网上搜索。

1、参考答案354参考答案第1章一、选择题1. B2. C 3. B4. C二、填空题1. 数据、数据2. 基本单位3. 数据项、数据项4. 相互关系、组织形式5. 逻辑关系、逻辑关系、数学模型6. 存储结构、存储结构7. 数据的运算、数据的运算、数据的运算8. 集合、集合9. 线性结构10. 树型结构11. 多对多12. 非线性结构、线性结构、非线性结构13. 顺序存储14. 链接存储15. 稠密索引、稀疏索引、稠密索引、稀疏索引、稠密索引、稀疏索引16. 散列存储17. 有限序列18. 有穷19. 确定、相同20. 可行、有限、具体实现21. 正确性、可读性、健壮性、效率22. 运行时间、所占

2、据空间23. 存储空间三、判断题1. 错误：树型结构也可以用顺序方式进行存储。2. 错误：数据元素是数据的基本单位，数据项是数据的最小单位。3. 错误：算法用各种计算机语言描述表现为一个程序，但是不等于程序，程序逻辑不一定能满足有穷性。4. 正确。5. 正确。6. 正确。7. 正确。8. 正确。四、综合题1. 该算法的时间复杂度为：O(mn)。2. 该算法的时间复杂度为：O()3. 该算法的时间复杂度为：O(mnt)。4. 该算法的时间复杂度为：log3(n)。5. 该算法的时间复杂度为：O()。第2章一、选择题1. A2. D3. A4. D5. D6. A7. B8. D9. B10. C

3、11. C12. C13. D14. D二、填空题1. 一对一2. 直接前驱、直接后继3. 有限序列、长度、空表4. 顺序存储结构、逻辑顺序、地址相邻5. 任意、任意、不连续、逻辑关系6. 数据域、指针域、链域7. 非顺序、非顺序映像8. 循环链表9. 双向链表10. 所指向的结点本身11. P-next=p-next-next12. P-next-prior=P-prior13. 线性表14. 双链表15. n-i+116. n-i17. S-next=P-next; P-next=S18. p-prior-next=S; s-prior=p-prior;s-next=p;p-prior=s

4、;19. head(tail(tail(head(tail(head(A)20. O(n)21. (L=L-Next) & (L=L-Prior)22. 线性23. 顶三、判断题1. 错误：链表存储中，结点之间可以连续也可以不连续，但结点内部是连续的。2. 错误：头指针指向头结点而不是数据结点。3. 错误：顺序存储的线性表可以随机存取。4. 正确。5. 错误。6. 错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。7. 错误：先行表的长度是线性表中结点的个数。8. 错误：注意最后一个结点。9. 错误：也可以有顺序存储的形式。四、综合题1. 将带头结点单链表逆置的算法如下：void

5、reverse_list( linklist * head )/*逆置带头结点的单链表*/linklist *s, *p;p=head-next;/*p指向线性表的第一个元素*/head-next=NULL; /*初始空表*/while ( p != NULL ) s=p;p=p-next;s-next=head-next;head-next=s; /*将s结点插入逆表*/ /*reverse_list*/2. 把这两个单链表合并成一个按升序排列的单链表，并用hc指向它的头结点的算法如下所示：linklist *combine_list( linklist *ha, linklist *hb

6、)/*ha, hb分别是两个按升序排列的,带有头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表,并用hc指向它的头结点*/linklist *hc, *pa, *pb, *pc, *p, *q, *r;hc=(linklist *)malloc(sizeof(linklist); /*建立hc头结点*/p=hc;pa=ha-next;free(ha); /*释放ha头结点*/pb=hb-next;free(hb);/*释放hb头结点*/while (pa!=NULL & pb!=NULL )q=(linklist *)malloc (sizeof (linkli

7、st); /*产生新结点*/if (pb-datadata)q-data=pb-data;pb=pb-next;elseq-data=pa-data;pa=pa-next;if (pa-data=pb-data) /*将相同的元素删除*/r=pb;pb=pb-next;free(r);p-next=q; /*将结点链入c链表*/p=q;while(pa!=NULL)/*a链表非空*/q=(linklist *)malloc (sizeof (linklist);q-data=pa-data;pa=pa-next;p-next=q;p=q;while(pb!=NULL) /*b链表非空*/q=(

8、linklist *)malloc (sizeof (linklist);q-data=pb-data;pb=pb-next;p-next=q;p=q;p-next=NULL;return(hc); /*返回*/3. 在带头结点的单链表中算法计算所有数据域为x的结点的个数的算法如下所示：int count_list(linklist *head )/*在带头结点的单链表中计算所有数据域为x的结点的个数*/linklist *p;int n;p=head-next; /*p指向链表的第一个结点*/n=0;while (p!=NULL)if (p-data=x)n+;p=p-next;return

9、(n);/*返回结点个数*/ /*count_list*/4. 在带头结点的单链表中插入值为x的元素，并使该链表仍然有序的算法如下所示：linklist *insertx_list(linklist *head, int x)/*在带头结点的单链表中插入值为x的元素，使该链表仍然有序*/linklist *s, *p, *q;s=(linklist *)malloc(sizeof(linklist); /*建立数据域为x的结点*/s-data=x;s-next=NULL;if (head-next=NULL | xnext-data ) /*若单链表为空或x小于链表第一个结点的数据域*/s-n

10、ext=head-next;head-next=s;elseq=head-next;p=q-next;while( p != NULL & xp-data )q=p;p=p-next;s-next=p;q-next=s; /*if*/ /*insertx_list*/5. 在带头结点的单链表中，实现p所指向的结点和p的后继结点相互交换的算法如下所示：linklist *swapin_list(linklist *head, linklist *p)/*在带头结点的单链表中，实现p所指向的结点和p的后继结点相互交换*/linklist *q, *r, *s;q=p-next; /*q为p的后继*

11、/if (q !=NULL) /*若p有后继结点*/if (p=head) /*若p指向头结点*/head=head-next;s=head-next;head-next=p;p-next=s;else /*p不指向头结点*/r=head; /*定位p所指向结点的前驱*/while (r-next != p)r=r-next;r-next=q; /*交换p和q所指向的结点*/p-next=q-next;q-next=p;return(head);else /*p不存在后继*/return(NULL);/*swapin_list*/6. 在带头结点的非递减有序单链表中，将该链表中多余的元素值相同

12、的结点删除的算法如下所示：linklist *deldy_list(linklist *head)/*在带头结点的非递减有序单链表，将该链表中多余的元素值相同的结点删除*/linklist *q;if (head-next!= NULL)/*判断链表是否为空*/p=head-next;while (p-next != NULL )if ( p-data != p-next-data )p=p-next;else q=p-next;/*q指向p的后继*/p-next=q-next; /*删除q所指向的结点*/free(q); /*释放结点空间*/ /*while*/ /*if*/return(h

13、ead); /*deldy_list*/7. 在带头结点的单链表中，删除所有数据域大于min，而小于max的所有元素的算法如下所示：linklist *dellist_maxmin(linklist *head, int min, int max )linklist *p, *q;q=head;p=head-next;while(p!=NULL) /*结点不空*/if (p-datadata=max) /*不满足删除条件*/q=p;p=p-next;else/*满足删除条件*/q-next=p-next;free(p);q=q-next; /*dellist_maxmin*/8. 将双链表逆置

14、的算法invert_dblinklist的算法如下所示：void invert_dblinklist( linklist *head )/*将head指向的双链表逆置*/dblinklist *p, *q;p=head;doq=p-next;p-next=p-prior;p-prior=q;p=q;while( p!=head ) /*invert_dblinklist*/第3章一、选择题1. C2. C3. B4. D5. B6. C7. C8. A9. A10. C 11. C12. A13. C14. C15. B二、填空题1. 表尾、栈顶、栈底、空栈2. 进栈、入栈、退栈、出栈3. 栈

15、顶元素、栈顶元素、栈顶元素、最先出栈、后进先出、LIFO4. 顺序、链式、顺序栈、链栈5. 溢出、上溢、溢出、下溢6. 链栈、特殊的单链表7. 中缀表达式8. 后缀表达式、波兰式9. 特殊的线性表、队尾、队头10. 先进先出、先进先出、FIFO11. 顺序存储结构、顺序队列12. 队头元素、队尾元素、队头指针、队尾指针13. 循环队列、取模运算14. 递归函数、自调用函数、直接递归调用、间接递归调用15. 空、满16. 链队列17. n-118. 不可能的19. 可能的20. top!=maxsize21. x=sqtop; top=top-122. 先进后出23. 栈顶指针24. top=m

16、ax25. top!=nil26. (n+r-f)mod n27. 前一个28. 队首29. n30. lq-front=lq-rear31. 栈顶指针32. 队尾三、判断题1. 正确。2. 错误：不同的入栈和出栈组合得到不同输出序列。3. 错误：某些情况如尾递归可以转换为递推的形式。4. 正确。5. 错误：循环队列不会产生假溢出。6. 错误。7. 正确。四、综合题1. 所有可能的出栈次序为：A、B、C、DA、B、D、CA、C、B、DA、C、D、BA、D、C、BB、A、C、DB、A、D、CB、C、A、DB、C、D、AB、D、C、AC、B、A、DC、B、D、AC、D、B、AD、C、B、A2. 多

17、队列排序的算法设计如下：#include #define MAX 10#define N 100 struct node int data; struct node *next;struct hnode struct node *link; queueMAX;main() int AN,n,i,first=1; struct node *p,*s,*head; printf(数值个数n:); scanf(%d,&n); for (i=0;iMAX;i+) /*队列初始化*/ queuei.link=NULL; for (i=0;in;i+)/*用户输入数据*/doprintf(第%d个数:,i

18、+1);scanf(%d,&Ai); while (Ai9); for(i=0;idata=Ai;s-next=NULL;if (queueAi.link=NULL) /*是相应队列的第一个结点*/ queueAi.link=s; else /*不是相应队列的第一个结点*/ p=queueAi.link;while (p-next!=NULL) p=p-next; /*p指向该链表的最后一个结点*/p-next=s; head=(struct node *)malloc (sizeof (struct node); /*建立新的总链表头结点*/ head-next=NULL; for (i=0

19、;inext = queuei.link;first=0;p=head;while (p-next!=NULL) p=p-next; /*p指向最后结点*/ else /*不是链入总链表的第一个链表*/ p-next=queuei.link; p=queuei.link; while (p-next!=NULL) p=p-next; printf(n显示所有元素:n); if (head-next!=NULL) /*p指向总链表的首结点*/ p=head-next;while (p!=NULL)printf(%d ,p-data);p=p-next;3. 算法设计如下：/*只有一个指针rear

20、的链式队的基本操作*/#include typedef char elemtype;struct node /*定义链队列结点*/elemtype data;struct node *next;typedef struct queue /*定义链队列数据类型*/struct node *rear; LinkQueue;void initqueue(LinkQueue *Q)/*初始化队列*/ Q=(struct queue *)malloc(sizeof(struct queue); Q-rear=NULL; void enqueue(LinkQueue *Q,elemtype x) /*入队

21、算法*/ struct node *s,*p; s=(struct node *)malloc(sizeof(struct node); s-data=x; if (Q-rear=NULL) /*原为空队时*/ Q-rear=s;s-next=s; else /*原队不为空时*/ p=Q-rear-next; /*p指向第一个结点*/Q-rear-next=s; /*将s链接到队尾*/Q-rear=s; /*Q-rear指向队尾*/s-next=p; void delqueue(LinkQueue *Q) /*出队算法*/ struct node *t; if (Q-rear=NULL) pr

22、intf(队列为空!n);return(0); else if (Q-rear-next=Q-rear) /*只有一个结点时*/ t=Q-rear;Q-rear=NULL; else /*有多个结点时*/ t=Q-rear-next; /*t指向第一个结点*/Q-rear-next=t-next; /*引成循环链*/ free(t); elemtype gethead(LinkQueue *Q) /*取队首元素算法*/ if (Q-rear=NULL) printf(队列为空!n); else return(Q-rear-next-data); int emptyqueue(LinkQueue

23、 *Q) /*判断队列是否为空算法*/ if (Q-rear=NULL) return(1); /*为空,则返回true*/ else return(0); /*不为空,则返回flase*/ void dispqueue(LinkQueue *Q) /*显示队列中元素算法*/ struct node *p=Q-rear-next; printf(队列元素:); while (p!=Q-rear) printf(%c ,p-data);p=p-next; printf(%cn,p-data);4. “回文”判定算法设计如下：int isPalindrome()/*回文判定算法*/InitStac

24、k(S);InitQueue(Q);While(c=read()!=#)push(S,c); /*读入字符分别保存在栈和队列中*/EnQueue(Q,c);While( !QmptyStack( S ) & ! EmptyQueue( Q ) )if (pop(S) != DelQueue(Q) /*正序和逆序字符的比较*/return (FALSE);if ( !EmptyStack(S) | ! EmptyQueue( Q )return (FALSE);return( TRUE );/*isPalindrome*/5. 表达式中括号是否正确配对的算法。#include stdio.h#i

25、nclude stdlib.h#define FALSE 0#define TRUE 1#define LEN sizeof( struct node )struct nodechar data;struct node *next;typedef struct node *stack;void push_stack(stack *, char );int pop_stack(stack *);void main()stack s;int valid=TRUE;char ch,symble;symble=getchar();s=NULL;push_stack(&s, #);while (symb

26、le != # ) & (valid =TRUE) )if ( symble !=( & symble !=) & symble != & symble != & symble != & symble != )symble=getchar();else if (symble=( | symble= | symble= )push_stack(&s, symble );symble=getchar();else if ( s=NULL )valid=FALSE;elsech=pop_stack(&s);if ( (ch=( & symble=) | (ch= & symble=) | ch=(

27、& symble=) )valid=TRUE;symble=getchar();elsevalid=FALSE;if ( valid = TRUE )printf( The string is valid. n);elseprintf(The string is valid. n);void push_stack( stack *topptr, char ch )stack newptr;newptr=(struct node * ) malloc( LEN );newptr-data=ch;newptr-next=*topptr;*topptr=newptr;int pop_stack( s

28、tack topptr )stack tempptr;char popvalue;if (topptr!=NULL )tempptr=topptr;popvalue=topptr-data;topptr=topptr-next;free( tempptr );return popvalue;else return 0;6. 背包问题求解算法如下：#include stdio.h#define NUMBER 20 /*定义物品个数*/#define TRUE 1#define FALSE 0int stackNUMBER; int top;void main()int knapproblem(

29、int, int, int);int weightNUMBER; /*存放物品质量的数组*/int n, i;int maxweight; /*包所能承受的最大重量*/printf(Please input maxweight :n);scanf(%d,&maxweight);printf( NUMBER :n);scanf(%d, &n);printf( Please input every objects weight :n );for (i=1; i0;top- )printf(weigh%d=%4d, stacktop,weightstacktop);/*pop stack and p

30、rint every weight*/printf(n);elseprintf(FAIL!n); /*main*/int knapproblem( int n, int maxweight, int weight ) /*背包问题处理函数*/*func kanpstack*/int i=1;top=0;while (maxweight0)&(i0 )& (i0) /*继续试探*/i=stacktop;top=top-1;maxweight = maxweight+weighti;i+; /*while*/return( FALSE ); /*knapproblem*/7. 划分子集问题可以抽象

31、成数学模型进行求解。模型为：已知集合A=a1, a2, ， an 和定义在集合上的关系R= (ai, aj ) | ai, aj A, 1in, 1jn, ij , 其中( ai, aj )表示ai 和 aj之间存在“冲突关系”，现要求将A划分成K个互不相交的子集A1，A2，Ak (kn)使得任何一个子集中的元素无冲突关系。同时，对于给定的集合A和关系R，希望划分的子集个数尽可能的少。划分子集问题的求解算法如下：#include stdio.h#define MAX 10 /*元素数目*/int rMAXMAX; /*存放关系矩阵*/int n;int resultMAX; /*存放分组结果*

32、/void main()void division( int MAXMAX ); /*声明划分子集函数*/int i, j;printf(Please input the number :n);scanf(%d, &n);printf(rashed matrix,1 rash, 0 no rash:n); /*输入冲突矩阵,1冲突,0不冲突*/for ( i=1; i=n; i+ )for( j=1; j=n; j+ )scanf(%d,&rij);division(r); /*调用子集划分函数*/for( i=1; i=n; i+ ) /*输出分组结果*/printf(No.%d divis

33、ied into %d group. n, i, resulti);void division ( int rMAXMAX)/*子集划分函数*/int newrMAX; /*记录所有以入组的元素发生冲突的元素信息*/int cqMAX; /*循环队列*/int i, k;int front, rear; /*循环队列头尾指针*/int group, pre;for (k=0; k=n-1; k+ ) /*n个元素依此入队列*/cqk=k+1;for ( k=0; k=n; k+)/*初始状态,均不冲突*/newrk=0;group=1;pre=0;while ( rear != front )

34、 | (rear != 0 )front=(front+1)%n;i=cqfront;if (ipre)group=group+1;resulti=group; /*记录组号*/for (k=1; k=n; k+ )newrk=rik;else if (newri != 0) /*发生冲突,重新入队列*/rear=(rear+1)%n;cqrear=i;else /*可以分在当前组*/resulti=group;for (k=1; k%cn,from,to);/*输出移动过程*/*move*/void hanoi( n,x,y,z )/*递归执行过程*/char x,y,z;int n;if

35、( n=1 )move( x,z );elsehanoi( n-1,x,z,y );move( x,z );hanoi( n-1,y,x,z );/*hanoi*/main()int n;printf(Please input the nmmber of diskes:n);scanf(%d,&n);printf(Begin to move %d diskes:n);hanoi( n,A,B,C );/*汉诺塔问题的非递归算法*/#include stdio.hstruct nodechar x;char y;char z;int id;stack30;main()int i=1;int n;

36、char s;printf(Input the number of diskes:n);scanf(%d,&n);printf(Begin to move %d diskes:n,n);if( n=1 )printf(A-Cn);elsestack1.id=n;stack1.x=A;stack1.y=B;stack1.z=C;dowhile( n1 )n-;i+;stacki.id=n;stacki.x=stacki-1.x;stacki.y=stacki-1.z;stacki.z=stacki-1.y;printf(%c,stacki.x);printf();printf(d,stacki.

37、id);printf()-);printf(%cn, stacki.z);i-;doif( i=1 )printf(%c, stacki.x);printf();printf(d, stacki.id);printf()-);printf(%cn, stacki.z);stacki.id = stacki.id-1;n=stacki.id;if( n=1 )s=stacki.x;stacki.x = stacki.y;stacki.y=s;if( n=1 )printf(%c, stacki.x);printf();printf(d, stacki.id);printf()-);printf(

38、%cn, stacki.z);i-;while( (n0) )while( i0 )getch();第4章一、选择题1. B2. C3. C4. B二、填空题1. 有限序列、串名、串值2. 长度3. 空串、零4. 空格串、空格的个数5. 子串、子串6. 位置7. 值相等、长度相等、相等8. ASCII码、ASCII码、较大者9. 顺序存储结构10. 紧缩式存储方式11. 非紧缩存储方式、一个字符、一个字符12. 串所占用的存储单元的个数13. 一个字符、单字节存储方式、串长、不包含14. 数据、指针、数据、指针15. 模式匹配三、判断题1. 错误：子串是主串中连续字符构成的有限序列。2. 正确

39、。3. 正确：注意字符可以是字母、数字或计算机能表达的其他符号。4. 错误：可以是数字或其他字符。5. 正确。6. 正确。7. 错误：串可以是空串、长度可以为零。8. 正确。9. 正确。四、综合题1. 串的置换题的算法如下：void replace (stringtype s1, int i, int j, stringtype s2)stringtype s100;int h,k;if ( i=h & is1.len & js1.len )for (h=1; h=i; h+ )s.chh=s1.chh;/*把s1的前i个字符赋值给s*/s.len=i;h=1;while(hs2.len)/*

40、连接串s2*/s.chs.len+h=s2.chh;h+;s.len=s.len+s2.len;for ( k=s.len+1; h=j; h=s1.len; h+,k+ )s.chk=s1.chh; /*将s1串中从第j个字符开始到结束的字符连接到s串*/s.len=k;s.chs.len=0;return(s);2. 测试是否回文的算法编写如下：int invert(stringtype *s)/*判断是否回文*/int i, j;j=length(s)%2;for ( i=0; ij; i+ )if ( SubStr(s,i,1) != SubStr(s, s.len-i+1,1)ret

41、urn ( 0 ); /*返回False*/return(1) /*返回True*/*invert*/3. void reverse ( stringtype *s )char c;int i;i=1;printf(Please char, # is the end.n);doscanf(%c,&c);Reverse(s);s.chi=c;i+;while(c!=#&idata=x)/*删除第一个结点*/s=p-next;free(p);p=s;elseq=p;p=p-next;w=0;else /*处理其他结点*/if ( p-data=x) /*删除值为x的结点*/q-next=p-nex

42、t;free (p);p=q-next;elseq=p;p=p-next; /*sjt4*/第5章一、选择题1. D2. B3. B4. B5. A6. C7. A8. C9. C10. A11. B12. B二、填空题1. 相同类型数据、地址连续2. 数组元素、数组元素、维数3. 以行序为主、以列序为主4. 特殊矩阵、稀疏矩阵、特殊矩阵、稀疏矩阵5. 对称矩阵6. 三元组顺序表、三元组7. 矩阵转置8. 名称、长度、空表9. 原子、子表10. 表头、表尾11. 最大的层数、括号的重数、最大深度加1三、判断题1. 正确：十字链表是链接存储结构。2. 正确：具有存取任一元素的时间相等这一特点的存

43、储结构称为随机存取结构，三元组表存储矩阵的时候，要访问第i行j列元素必须扫描三元组表，显然查找三元组表前面的元素与后面元素所耗费的时间不同，因此三元组表不是一个随机存取结构。3. 正确：随机存取结构是指存取任一元素的时间相等这一特点的存储结构，对稀疏矩阵压缩存储所用的存储结构是十字链表和三元组，而这两种存储结构都不是随机存取结构。4. 错误：如广义表L=(),(A, B)为非空，而表头为空表。5. 错误：广义表是线性表的推广，是一类非线性数据结构。6. 正确：表尾的定义是除表头元素以外其余元素（可以为空）构成的表，所以必定是广义表。7. 错误：应该在互换行列后再按照行优先重新存储。8. 正确。

44、9. 正确。10. 正确。11. 错误：广义表中元素个数为广义表的长度。12. 错误：广义表最大子表的深度加1为广义表的深度。13. 正确。14. 正确。15. 错误：广义表是一种非线性结构。16. 正确。17. 正确。18. 正确：注意单链表结构不一定是线性的。四、综合题1. 打印“魔方阵”算法如下所示：void MagicMatrix( )int a1616,i,j,k,p,m,n;p=1;while(p=1)/*输入115的奇数*/printf(Please input n(n=115)n);scanf(%d,&n);if (n!=0) & (n=15) &(n%2 !=0)p=0;/*

45、Initialization*/for ( i=1;i=n;i+)for( j=1;j=n;j+)aij=0;/*建立魔方阵*/j=n/2+1;a1j=1;for (k=2; k=n*n;k+)i=i-1;j=j+1;if (in)i=i+2;j=j-1;elseif (in)j=1;if (aij=0)aij=k;elsei=i+2;j=j-1;aij=k;/*输出魔方阵*/for (i=1; i=n; i+ ) for(j=1;j=n;j+)printf(%4d,aij);printf(n);/*MagicMatrix*/2. 打印一个二维数组中的鞍点的算法如下所示：#define N 1

46、0#define M 10void Andian( )int i,j,m,n,flag1,flag2,aNM, max, maxi, maxj;printf(Please input the row number :n);scanf(%d,&n);printf(Please input the column number :n);scanf(%d,&m);for (i=0; in; i+ )printf(NO. %d row n,i)for (j=0; jm; j+ )scanf(%d,&aij);printf(n);flag2=0;for (i=0; in; i+ )max=ai0;for( j=0;jmax )max=aij;maxj=j;for (k=0, flag1=1; kakmaxj )flag1=0;if (flag1)printf( Row %d ,Column %d ,the number is:%d n,i, maxj,max);flag2=1;if (!flag2)printf(There is no this