数据结构习题答案汇总.doc

数据结构课后习题参考答案1.1.20（1）T(n) = n-1；渐近时间复杂度为O(n)。（2）T(n) = log2n；渐近时间复杂度为O(log2n)。（3）T(n) = n(n+1)(n+2)/6；渐近时间复杂度为O(n3)（4）T(n) =；渐近时间复杂度为O()2.2.3template bool SeqList:Insert2(int i, T x)if (i n-1)cout Out of bounds endl;return false;if (n = maxLength)T *elem = new T2 * maxLength;maxLength = maxLength * 2;for (int j = 0; j = i; j+)elemj = elementsj;elemi+1 = x;for (j = i+1; j i; j-)elementsj+1 = elementsj;elementsi+1 = x;n+;return true;算法的时间复杂度为O(n)2.4template bool SeqList:Del(T x)if (!n)cout UnderFlow endl;return false;for (int i=0; in; i+)if (elementsi = x)for (int j=i+1; jn; j+)elementsj-1 = elementsj;n-;return true;return false;算法的时间复杂度为O(n)2.6 template void SingleList:Invert() Node *p=first,*q; first=NULL; while (p) q = p-link;p-link = first; first = p; p = q; 算法的时间复杂度为O(n)2.7 template bool SingleList:Del(const T& x) if (!n)cout Under Flow! endl;return false;Node *p=first, *q;if (first-data) = x) first = first-link;delete p;n-;return true;while (p & p-data != x) q = p;p = p-link;if (p)q-link = p-link;delete(p);n-;return true;return false;算法的时间复杂度为O(n)3.3.1答： (2)和(3)不能。对(2)中的E，B，D而言，E最先出栈则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理(3)也不能。 (1)能，操作序列:push(A),pop(),push(B),pop(),push(C),pop(),push(D),pop(),push(E),pop()(4)能，操作序列:push(A),push(B),push(C),push(D),push(E),pop() ,pop(),pop(),pop(),pop() 3.4(1) (a+b)/(c+d) ab+cd+/(2) b2-4*a*c b24a*c*-(3) a*c-b/c2 ac*-bc2/-(4) (a+b)*c+d/(e+f) ab+c*def+/+(5) (a+b)*(c*d+e)-a*c ab+cd*e+*ac*- 3.13t template void SeqStack:Invert(void)SeqQueue sq(maxTop + 1);T temp;while (top != -1)this-Top(temp);this-Pop();sq.EnQueue(temp);while (!sq.IsEmpty()sq.Front(temp);sq.DeQueue();this-Push(temp);4.4.2 设三维数组的维度分别是m, n, l；每个元素占k个存储单元。Loc(Aijk) = Loc(A000) + (i * n * l + j * l) * k4.64.7col01234num10212k011345.5.2（1）无序树：9棵（2）有序树：12棵（3）二叉树：30棵5.4（1）2k-1（2）（3）k(i-1) + m + 1（4） i +15.5(1) 空二叉树和所有结点均无左孩子的二叉树(2) 空二叉树和只有一个根(3) 空二叉树和所有结点均无右孩子5.65.7先：DEHFJGCKAB中：HEJFGKCDAB后：HJKCGFEBAD5.9(1)template void BinaryTree:Del(BTNode *p) /private if (p!=NULL)Del(p-lChild);Del(p-rChild);delete p;template void BTree:Del() /publicDel(root);root = NULL;(2) /*求二叉树中度为1的结点个数*/template int BinaryTree:CountDegree1() int total = 0; CountDegree1(root, total); return total;template void BinaryTree:CountDegree1(BTNode *t, int &num) if (t) if ( ( (t-lChild != NULL) & (t-rChild = NULL) ) | ( (t-lChild = NULL) & (t-rChild != NULL) ) +num; CountDegree1(t-lChild, num); CountDegree1(t-rChild, num); (3)template void BinaryTree:Exch(BTNode *p) /private if (p!=NULL)BTNode *temp;temp=p-lchild; p-lchild=p-rchild; p-rchild=temp;Exch(p-lchild);Exch(p-rchild);template void BTree:Exchange() /publicExch(root); 5.14 5.19（1）（2）WPL = 91（3）各字符的编码A:1010B:1011C:100D:00E:01F:116.6.5template bool SeqList:Search1(T x)constreturn SearchRec(x, 0);template bool SeqList:SearchRec(T x, int i)constif (i = n) return false;if (elementsi = x) return true;else return SearchRec(x, i+1);6.6template bool SingleList:Search1(T x) constNode *p = first;while (p & p-element link;if (p = NULL | p-element x) return false;return true;6.10ASL成功=1/12（1*1+2*2+3*4+4*5）=37/12ASL失败=1/13（3*3+4*10）=49/137.7.17.37.16（1）7.17(1) 删除a删除e删除f删除h8.8.3 8.4012345678910线性探查法5545352570806050二次探查法4535802570605055双散列法55803525706045509.9.1（1）顶点入度出度030122212312423511（2）（3）9.29.4template void LGraph:Degree(int *in)for (int i=0;in;i+)ini=0;ENode *p;for (i=0; iadjvex+;p=p-nextarc;for (i=0;in;i+)couti: ini ; endl;9.6 9.13 9.1710.10.1(1) 简单选择排序初始序列（61 87 12 03 08 70 97 75 53 26第1趟 （03）87 12 61 08 70 97 75 53 26第2趟 （03 08）12 61 87 70 97 75 53 26第3趟 （03 08 12）61 87 70 97 75 53 26第4趟 （03 08 12 26）87 70 97 75 53 61第5趟 （03 08 12 26 53）70 97 75 87 61第6趟 （03 08 12 26 53 61）97 75 87 70第7趟 （03 08 12 26 53 61 70）75 87 97第8趟 （03 08 12 26 53 61 70 75）87 97第9趟 （03 08 12 26 53 61 70 75 87）97(2) 直接插入排序初始序列（61）87 12 03 08 70 97 75 53 26第1趟 （61 87）12 03 08 70 97 75 53 26第2趟 （12 61 87）03 08 70 97 75 53 26第3趟 （03 12 61 87）08 70 97 75 53 26第4趟 （03 08 12 61 87）70 97 75 53 26第5趟 （03 08 12 61 70 87）97 75 53 26第6趟 （03 08 12 61 70 87 97）75 53 26第7趟 （03 08 12 61 70 75 87 97）53 26第8趟 （03 08 12 53 61 70 75 87 97）26第9趟 （03 08 12 26 53 61 70 75 87 97） (3) 冒泡排序（注意冒泡排序只排了7趟）初始序列(61 87 12 03 08 70 97 75 53 26)第1趟 61 12 03 08 70 87 75 53 26 97 第2趟 12 03 08 61 70 75 53 26 87 97第3趟 03 08 12 61 70 53 26 75 87 97第4趟 03 08 12 61 53 26 70 75 87 97第5趟 03 08 12 53 26 61 70 75 87 97第6趟 03 08 12 26 53 61 70 75 87 97第7趟 03 08 12 26 53 61 70 75 87 97(4) 快速排序初始序列61 87 12 03 08 70 97 75 53 26第1趟 (53 26 12 3 8) 61 (97 75 70 87) 第2趟 ( 8 26 12 3) 53 61 (97 75 70 87) 第3趟 3 8 (12 26) 53 61 (97 75 70 87) 第4趟 3 8 12 26 53 (61 97 75 70 87) 第5趟 3 8 12 26 53 61 (87 75 70 97) 第6趟 3 8 12 26 53 61 (70 75) 87 97 第7趟 3 8 12 26 53 61 70 75 87 97 (5) 两路合并排序初始序列（61)(87) (12)(03) (08)(70) (97)(75) (53)(26)第1趟 (61 87) (03 12) ( 08 70) (75 97) (26 53)第2趟 (03 12 61 87) ( 08 70 75 97) (26 53)第3趟 (03 08 12 61 70 75 87 97) (26 53)第4趟 (03 08 12 26 53 61 70 75 87 97) 10.2(1)简单选择排序: 三种情况下的时间复杂度都为O(