數據結構(含上機實訓)課后題答案(已修改)

　

【正文】 課后習題答案第1章 數據結構導論一、填空題1．集合結構，線性結構，樹形結構，圖狀結構2．順序存儲結構，鏈式存儲結構3．有限性，確定性，可行性，輸入，輸出4．時間復雜度，空間復雜度二、分析下面程序段的時間復雜度。1．O(m*n)2．O(n2)三、上機操作題1．解答：include void main (){ float a[10]。 int i, n。 float s = 0。 printf (輸入數組中元素的個數n：)。 scanf (%d, amp。n)。 for (i = 0。 i n。 i ++) { printf (a[%d]: , i)。 scanf (%f, amp。a[i])。 s = s + a[i]。 } printf (數組中所有元素之和為：%f\n, s)。}2．解答：include void main (){ int x, y, z, t。 printf (請依次輸入x、y和z的值：\n)。 scanf (%d %d %d, amp。x, amp。y, amp。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 %d\n, x, y, z)。}第2章 線性表一、填空題1．數組2．數據元素的物理位置，指針3．單鏈表，循環鏈表，雙向鏈表4．數據，數據元素本身數據信息，指針，直接后繼元素地址信息5．順序，鏈式二、選擇題1．B2．D3．C4．C5．A6．B7．C8．B9．C10．B三、上機操作題1．解答：void Reverse (ElemType A[], int n){ ElemType temp。 int i。 for (i = 0。 i n/2。 i ++) { temp = A[i]。 //交換元素A[i]與A[ni1]的位置 A[i] = A[n – i 1]。 A[n – i 1] = temp。}}2．解答：void DelMax (LinkList *list){ Node *p, *q, *r, *s。 q = *list。 //q為鏈表中第一個結點 p = list next。 //p為鏈表中第二個結點 r = *list。 while (p != NULL) { if (p data q data) { q = p。 //保存當前最大值結點 s = r。 //保存當前最大值結點的前驅}r = p。 //保存p所指結點位置p = p next。 //p指向下一結點}if (q == *list) //鏈表中第一個結點為最大值結點 *list = (*list) next。 //刪除第一個結點else //最大值結點不是鏈表的第一個結點 s next = q next。 //刪除q所指結點free (q)。 //釋放q所指結點的空間}3．解答：void DeleteItem (DLinkList *list, ElemType item){ DNode *q。q = (*list) next。 //q指向頭結點的后繼 while (q != *list) { if (q data == item) //q所指結點的值為item{ q prior next = q next。 //刪除q所指結點 q next prior = q prior。 free (q)。 //釋放q所指結點的空間}q = q next。 //q指向下一結點}}4．解答：void InsertItem (DLinkList q, ElemType item){ DLinkList p。 p = (DLinkList) malloc (sizeof (DNode))。 //生成新結點 p data = item。 //新結點的數據域賦值 p prior = q。 //將新結點插入到q所指結點之后 p next = q next。 //修改p所指結點的指針域 q next = p。 //修改q所指結點的后繼 p next prior = p。 //修改p的后繼結點的前驅}第3章 棧和隊列一、填空題1．線性2．棧頂，隊尾，隊頭3．后進先出，先進先出4．數組，指示棧頂元素的位置5．將棧頂指針后移一個位置，將被插入元素放在修改后的棧頂指針所指出的位置6．鏈式二、選擇題1．C2．D3．C4．C5．B6．A7．B8．D9．C10．D三、上機操作題1．解答：表31 算術表達式求值的過程步驟OPTR棧OPND棧當前讀入字符步驟OPTR棧OPND棧當前讀入字符1358 － /35 502235－9 － /35 50 2＋3 －35510 －35 25＋4 －35 5*1110＋5 － *35 51012 ＋1056 － *35 5 10/13 ＋10 57 －35 50/14 152．解答：char op[7] = {39。+39。, 39。39。, 39。*39。, 39。/39。, 39。(39。, 39。)39。, 39。39。}。 //算符數組char cmp[7][7] = {{39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。39。}, {39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。39。},{39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。39。}, {39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。39。},{39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。=39。, 39。 39。}, {39。39。, 39。39。, 39。39。, 39。39。, 39。 39。, 39。39。, 39。39。}, {39。39。, 39。39。, 39。39。, 39。39。, 39。39。, 39。 39。, 39。=39。}}。 //算符優先關系數組//輸入字符是否屬于運算符集合，如果是，返回它在數組中的位置；否則，返回1int Isoperator (char ch){ int i。 for (i = 0。 i 7。 i ++) { if (ch == op[i]) return i。}return 1。}//比較兩個運算符的優先級char Compare (char ch1, char ch2){ int m, n。 m = Isoperator (ch1)。 n = Isoperator (ch2)。 return cmp[m][n]。}//將中綴表達式轉換為后綴表達式int TransExpression (char *str1, char *str2){ int i = 0, k = 0。 char x, theta。 SeqStack OPTR //定義運算符棧 IniStack (amp。OPTR)。 //初始化運算符棧 Push (amp。OPTR, 39。39。)。 //將39。39。壓入棧底 while (str1[i] != 39。39。 || GetTop (OPTR) != 39。39。) { if (str1[i] = 39。039。 amp。amp。 str1[i] = 39。939。) //如果讀入字符為數則復制到str2中 str2[k ++] = str1[i ++]。 else{ if (Isoperator (str1[i]) == 1) //如果讀入字符不是操作符，則出錯 return ERROR。 switch (Compare (GetTop (OPTR), str[i])) //比較操作符優先級高低{ case 39。39。: //讀入字符優先級高于棧頂字符優先級 Push (amp。OPTR, str[i])。 //操作符進棧 i ++。 break。 case 39。=39。: //讀入字符優先級等于棧頂字符優先級 Pop (amp。OPTR, x)。 //棧頂元素出棧 i ++。 break。 case 39。39。: //讀入字符優先級低于棧頂字符優先級 Pop (amp。OPTR, amp。theta)。 //棧頂元素出棧 str2[k ++] = theta。 //出棧元素復制到str2中 break。}}}return OK。}3．解答：int IsHuiwen (char *S){ SeqStack T。 int i , len。 char t。 InitStack (amp。T)。 len = StrLength (S)。 //求字符串長度 for ( i = 0。 i l / 2。 i ++) //將一半字符入棧 Push(amp。T, S[i])。 while( !EmptySt