《数据结构(含上机实训)课后题答案》由会员分享，可在线阅读，更多相关《数据结构(含上机实训)课后题答案（43页珍藏版）》请在金锄头文库上搜索。
1、第1章 数据结构导论一、填空题1 集合结构，线性结构，树形结构，图状结构2 .顺序存储结构，链式存储结构3 有限性，确定性，可行性，输入，输出4 时间复杂度，空间复杂度二、分析下面程序段的时间复杂度。1. 0(m*n)22. 0(n)三、上机操作题1 解答：#i nclude void mai n ()float a10;int i, n;float s = 0;printf (输入数组中元素的个数n： ”)；sca nf (%d, &n);for (i = 0; i n; i +)printf (a%d: , i);scanf (%f, &ai);s = s + ai;printf (数组中
2、所有元素之和为：%fn, s);2 解答：#i nclude void mai n ()int x, y,乙 t;printf (请依次输入 x、y和z的值：n);sca nf (%d %d %d, &x, &y, &z);if (x y)t = x;x = y;y = t；if (x z)t = x;x = z;z = t;if (y z)t = y;y = z;z = t;printf (按从大到小的顺序输出：n ”);printf (%d %d %dn, x, y, z);第2章线性表一、填空题1 数组2 数据元素的物理位置，指针3 单链表，循环链表，双向链表4 数据，数据元素本身数据信
3、息，指针，直接后继元素地址信息5 顺序，链式二、选择题1 B2 D3 C4 C6B7C8B9C10B三、上机操作题1解答：void Reverse (ElemType A, int n) ElemType temp;int i;for (i = 0; i next;r = *list;while (p != NULL)if (p - data q - data) q = p;s = r;r = p;p = p - next;if (q = *list) 结点*list = (*list) - next;else/ 交换元素 Ai 与 An-i-1 的位置/q 为链表中第一个结点/p 为链表中第
4、二个结点/ 保存当前最大值结点/ 保存当前最大值结点的前驱/ 保存 p 所指结点位置/p 指向下一结点/ 链表中第一个结点为最大值/ 删除第一个结点/ 最大值结点不是链表的第一个结占八、s - n ext = q - n ext;free (q);3 解答：void Deleteltem (DLinkList *list, ElemType item) DNode *q;q = (*list) - n ext;while (q != *list)if (q - data = item)q - prior - n ext = q - n ext;q - n ext - prior = q - p
5、rior; free (q);q = q - n ext;4 解答：void In sertItem (DL in kList q, ElemType item)DLin kList p;p = (DL in kList) malloc (sizeof (DNode);p - data = item;p - prior = q;之后p - n ext = q - n ext;q - n ext = p;p - n ext - prior = p;/删除q所指结点/释放q所指结点的空间q指向头结点的后继q所指结点的值为item/删除q所指结点/释放q所指结点的空间q指向下一结点/生成新结点/新结
6、点的数据域赋值/将新结点插入到q所指结点/修改p所指结点的指针域/修改q所指结点的后继/修改p的后继结点的前驱第3章栈和队列、填空题1 .线性2 栈顶，队尾，队头3 .后进先出，先进先出4 数组，指示栈顶元素的位置5.将栈顶指针后移一个位置，将被插入元素放在修改后的栈顶指针所指出的位置6 .链式、选择题1.C2.D3.C4.C5.B6.A7.B8.D9.C10.D三、上机操作题1.解答：表3-1算术表达式求值的过程步骤OPTR栈OPN栈当前读入字符步骤OPTR栈OPN栈当前读入字符1#358# - /35 5022#359# - /35 50 2+3# -35510# -35 254# -35
7、 5*11#10+5# - *35 51012# +1056# - *35 5 10/13# +10 5#7# -35 50/14#15#2 .解答:char op7 = +,char cmp77-,*, /, (, ), #;=, , , , , ,/算符数组 , 5J 5 I5555, ,5J 5 I5555, ,155555,=;/算符优先关系数组/输入字符是否属于运算符集合，如果是，返回它在数组中的位置；否则，返回-1int Isoperator (char ch)int i;for (i = 0; i = 0 & str1i = 9) 则复制到 str2 中str2k + = str
8、1i +;elseif (Isoperator (str1i) = -1) / 如果读入字符不是操作 符，则出错return ERROR;switch (Compare (GetTop (OPTR), stri) / 比较操作符优先级高低 case :优先级/ 栈顶元素出栈/ 出栈元素复制到 str2 中Pop (&OPTR, &theta); str2k + = theta; break;return OK;3解答：int IsHuiwen (char *S) SeqStack T;int i , len;char t;InitStack (&T);len = StrLength (S);f
9、or ( i = 0; i l / 2; i +)Push(&T, Si); while( !EmptyStack (&T) / 求字符串长度/ 将一半字符入栈/ 比较前一半字符和后一半字符是否相等，每弹出一个字符与相应字符比较 Pop (&T, &t);if( t != Sl - i) return 0 ;/ 不等则返回 0 return 1 ;/ 比较完毕均相等则返回 14解答：void LineEdit ()SeqStack S, T;char str1000;int strlen = 0;char e;char ch;InitStack (&S);InitStack (&T);ch = getchar ();while (ch != EOFILE)while (ch != EOFILE & ch != n)swi
