數(shù)據(jù)結(jié)構(gòu)(陳惠南主編第二版)習(xí)題答案1-9章 【全】

1、第一章 緒論1（第18頁，第（5）題） 確定下列各程序段的程序步，確定劃線語句的執(zhí)行次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度。(1) i=1; k=0; do k=k+10*i; i+; while(i<=n-1) 劃線語句的執(zhí)行次數(shù)為 n-1 。(2）i=1; x=0; do x+; i=2*i; while （i<n）; 劃線語句的執(zhí)行次數(shù)為 élog2nù。(3) for(int i=1;i<=n;i+) for(int j=1;j<=i;j+) for (int k=1;k<=j;k+) x+; 劃線語句的執(zhí)行次數(shù)為n(n+1)(n+2)/6 。

2、 (4）x=n;y=0; while(x>=(y+1)*(y+1) y+; 劃線語句的執(zhí)行次數(shù)為ë Ön û。第二章 線性表1第37頁 習(xí)題(2).2 在類LinearList 中增加一個(gè)成員函數(shù)，將順序表逆置，實(shí)現(xiàn)該函數(shù)并分析算法的時(shí)間復(fù)雜度。不利用類SeqList 提供的操作直接實(shí)現(xiàn)。template <class T>void SeqList<T>:Invert()T e;for (int i=1;i<=length/2;i+)e=elementsi-1;elementsi-1=elementslength-i;eleme

3、ntslength-i=e;2第37頁習(xí)題(5) 在類SingleList中增加一個(gè)成員函數(shù)，將單鏈表逆置運(yùn)算，直接實(shí)現(xiàn)該函數(shù)并分析其時(shí)間復(fù)雜度。template <class T>void SingleList<T>:invert() Node<T> *p=first,*q; first=NULL; while (p) q=p->link; p->link=first; first=p; p=q; 3（第37頁，第7題） 單鏈表中結(jié)點(diǎn)按元素值遞增鏈接，在類SingleList中增加一個(gè)成員函數(shù)，直接實(shí)現(xiàn)刪除結(jié)點(diǎn)值在a至b之間的結(jié)點(diǎn)(a£

4、;b)。template <class T>void SingleList<T>:DeleteAb(T a,T b)/第37頁，習(xí)題（7）Node<T> *p=first,*q=first; while (p && p->data<b) if (p->data<=a) q=p;p=p->link; else if (q=first) q=p->link; delete p; p=first=q; else q->link=p->link; delete p; p=q->link; 4.（第

5、37頁，第8題） 在類CircularList中增加一個(gè)成員函數(shù)，在不增加新結(jié)點(diǎn)的情況下，直接實(shí)現(xiàn)兩個(gè)鏈表合并為一個(gè)鏈表的算法，并分析其時(shí)間復(fù)雜度。template<class T>void Merge(CircularList<T> &a, CircularList<T> &b) Node<T> *p=b.first;while (p->link!=b.first) p=p->link;p->link=a.first->link;a.first->link=b.first->link;b.fi

6、rst->link=b.first;b.length=0;template<class T>void Merge1(CircularList<T> &a, CircularList<T> &b) Node<T> *p=b.first->link;b.first->data=b.first->link->data;b.first->link=a.first->link;a.first->link=p->link;p->link=p;b.first=p;第三章 棧與隊(duì)列1 第

7、50頁 習(xí)題(1） 設(shè)A、B、C、D、E五個(gè)元素依次進(jìn)棧(進(jìn)棧后可立即出棧)，問能否得到下列序列。若能得到，則給出相應(yīng)的push和pop序列；若不能，則說明理由。 1）A,B,C,D,E 2) A,C,E,B,D 3) C,A,B,D,E 4) E,D,C,B,A答：2）和3）不能。對(duì)2）中的E，B，D而言，E最先出棧，則表明，此時(shí)B和D均在棧中，由于，B先于D進(jìn)棧，所以應(yīng)有D先出棧。同理3）。2. 第50頁 習(xí)題（9） 利用棧可以檢查表達(dá)式中括號(hào)是否配對(duì)，試編寫算法實(shí)現(xiàn)之。bool match(char a,int n)int top=-1;for (int i=0;i<n;i+) i

8、f (ai='(') top+; else if (ai=')') if (top>-1) top-; else return true; if (top>-1) return true; return false;3. 第50頁 習(xí)題(10) 聲明并實(shí)現(xiàn)鏈?zhǔn)疥?duì)列類LinkedQueue。template <class T>class LinkedStack: public Stack<T> public:LinkedStack();LinkedStack();virtual bool IsEmpty() const;virt

9、ual bool IsFull() const;virtual bool GetTop(T& x);virtual bool Push(const T x);virtual bool Pop();virtual void SetNull();private:Node<T> *top;template <class T>LinkedStack<T>:LinkedStack() top=NULL;template <class T>LinkedStack<T>:LinkedStack() Node<T> *q; whi

10、le (top) q=top->link; delete top; top=q;template <class T>bool LinkedStack<T>:IsEmpty() const return !top;template <class T>bool LinkedStack<T>:IsFull() const return false;template <class T>bool LinkedStack<T>:GetTop(T &x) if (IsEmpty() cout<<"Em

11、pty stack"<<endl; return false; x=top->data; return true;template <class T>bool LinkedStack<T>:Push(const T x) Node <T> *q=new Node<T> q->data=x; q->link=top; top=q; return true;template <class T>bool LinkedStack<T>:Pop() Node<T> *q=top;

12、if (IsEmpty() cout<<"Empty stack"<<endl; return false; top=top->link; delete q; return true;template <class T>void LinkedStack<T>:SetNull() Node<T> *q; while (top) q=top->link; delete top; top=q;第四章 數(shù)組與字符串1. 給出三維數(shù)組元素Aijk的存儲(chǔ)地址loc(Aijk)。答： 設(shè)有三維數(shù)組聲明為An1n2n3

13、，每個(gè)元素占k個(gè)存儲(chǔ)單元，則 loc(Aijk)=loc(A000)+k*(i*n2*n3+j*n3+k)2（第68頁，第5題）給出下列稀疏矩陣的順序三元組的行優(yōu)先和列優(yōu)先表示。答：3（第68頁，第6題） 對(duì)題圖4-5的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時(shí)數(shù)組num和k的值。 答：4 （第69頁，第15題（2） 在順序串類String中增加一個(gè)成員函數(shù)，實(shí)現(xiàn)統(tǒng)計(jì)該串中出現(xiàn)的字符、字符個(gè)數(shù)和每個(gè)字符出現(xiàn)的次數(shù)。void String:count(char ch,int &n, int num) n=0; for (int i=0;i<length;i+) int j=0; while (j<

14、;n && stri!=chj) j+; if (j=n) chj=stri; numj=1; n+; else numj+;第五章 遞歸1設(shè)計(jì)一個(gè)遞歸算法，實(shí)現(xiàn)對(duì)一個(gè)有序表的順序搜索。template<class T>int SeqList<T>:Search4(const T& x) const elementslength=1000; return Sch4(x,0);template<class T>int SeqList<T>:Sch4(const T& x,int i) const if (x<e

15、lementsi) return 0; else if (x=elementsi) return +i; else return Sch4(x,i+1);補(bǔ)充題：（2）求順序搜索有序表失敗時(shí)的平均搜索長度。設(shè)有序表為（a1,a2,an），通?？梢约俣ù樵匚挥赼1之前，a1與a2之間，a2與a3之間,an-1與an之間以及 an之后的共n+1個(gè)位置處的概率是相等的。答：第六章 樹1第107頁，第（2）題對(duì)于三個(gè)結(jié)點(diǎn)A，B和C，可分別組成多少不同的無序樹、有序樹和二叉樹？答：（1）無序樹：9棵 （2）有序樹：12棵 （3）二叉樹：30棵2、（1）k的i1次方（2）（ik2）/k取整（3）（i1

16、）km1（4）（i1）%k不等于02第107頁，第（4）題 設(shè)對(duì)一棵二叉樹進(jìn)行中序遍歷和后序遍歷的結(jié)果分別為： （1）中序遍歷 B D C E A F H G （2）后序遍歷 D E C B H G F A 畫出該二叉樹。答： 3. 第107頁，第（6）題的第6小題設(shè)計(jì)算法，交換一棵二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹。template <class T>void BTree<T>:Exch(BTNode<T> *p)if (p)BTNode<T> *q=p->lchild;p->lchild=p->rchild;p->rchil

17、d=q;Exch(p->lchild); Exch(p->rchild);4. 第107頁，第10題 將圖題6-24中的樹轉(zhuǎn)換成二叉樹，并將圖6-23中的二叉樹轉(zhuǎn)換成森林。 5. 第107頁，第11題 給出對(duì)圖6-24中的樹的先序遍歷和后序遍歷的結(jié)果。 答：先序：A，D，E，F(xiàn)，J，G，M，B，L，H，C，K 后序：J，G，F(xiàn)，E，D，M，H，L，K，C，B，A6. 第107頁，第12題分別以下列數(shù)據(jù)為輸入，構(gòu)造最小堆。(1) 10，20，30，40，50，60，70，80(2) 80，70，60，50，40，30，20，10(3) 80，10，70，20，60，30，50，40（

18、1）（2）（3）7. 第107頁，第13題 分別以上題的數(shù)據(jù)為輸入，從空的優(yōu)先權(quán)隊(duì)列開始，依此插入這些元素，求結(jié)果優(yōu)先權(quán)隊(duì)列的狀態(tài)。 8. 第108頁，第14題第（1）、（2）小題 設(shè)S=A,B,C,D,E,F，W=2,3,5,7,9,12，對(duì)字符集合進(jìn)行哈夫曼編碼，W為各字符的頻率。（1) 畫出哈夫曼樹（2）計(jì)算帶權(quán)路徑長度 第七章 集合與搜索樹1第137頁，第（5）,建立37，45，91，25，14，76，56，65為輸入時(shí)的二叉搜索樹，再從該樹上依此刪除76，45，則樹形分別如何？2 第137頁，第（6）試寫一個(gè)判定任意給定的二叉樹是否二叉搜索樹算法。int k=-¥ bool

19、 fail=false;template <class T>void BTree<T>:IsBiTree(BTNode<T> *p,int &k,bool &fail) if (p&& !fail) IsBiTree(p->lchild,k,fail); if(k< p->element) k=p->element; else fail=true; IsBiTree(p->rchild,k,fail); 3 第137頁，第（8） 以下列序列為輸入，從空樹開始構(gòu)造AVL搜索樹。 （1)A，Z，B，Y

20、，C，X （2)A,V,L,T,R,E,I,S,O,K4 第137頁，第（12）5階B-樹的高度為2時(shí)，樹中元素個(gè)數(shù)最少為多少？答: 55 第137頁，第（13）題 從空樹開始，以關(guān)鍵字序列：a,g,f,b,k,d,h,m,j,e,s,i,r,x ,建立 (1) 4階B-樹; (2) 5階B-樹。(1) 4階B-樹 (2) 5階B-樹6 第137頁，第（14）題 從上題的4階B-樹上依次刪除a,e,f,h。第八章 散列與跳表1 第154頁，第（3）題 設(shè)散列表ht11，散列函數(shù)h(key)=key % 11。采用線性探查法解決沖突，試用關(guān)鍵字值序 列：70，25，80，35，60，45，50，

21、55 建立散列表。 2 第154頁，第（6）題給出用拉鏈方法解決沖突的散列表搜索操作的C+函數(shù)實(shí)現(xiàn)。template<class T>bool LinkedHashTable<T >:Search(const K &k,E&e)const int i=k % M,j; HNode<T>* p=hti;/元素結(jié)點(diǎn)類型Hnode<T> while (p) if(p->element=k)return true; p=p->nextsynonym; return false; 3 第154頁，第（3）題設(shè)散列表ht11，散列

22、函數(shù)h(key)=key % 11。采用二次探查法解決沖突，試用關(guān)鍵字值序列：70，25，80，35，60，45，50，55 建立散列表。4 第154頁，第（4）題對(duì)上題的例子，若采用雙散列法，試以散列函數(shù)h1(key)=key % 11，h2(key)= key % 9+1建立散列表。第九章 圖1 第188頁，第（1）題 對(duì)下面的有向圖求 (1) 每個(gè)頂點(diǎn)的入度和出度； (2) 強(qiáng)連通分量 (3) 鄰接矩陣 2 第188頁，第（2）題當(dāng)以邊1，0，1，3，2，1，2，4，3，2，3，4，4，0，4，1，4，5，5，0的次序從只有6個(gè)頂點(diǎn)沒有邊的圖開始，通過依此插入這些邊，建立鄰接表結(jié)構(gòu)。畫出

23、該鄰接表。 3 第188頁，第（4）題已知有向圖的鄰接表，試寫出計(jì)算各頂點(diǎn)的入度的算法。template<class T>void LinkedGraph<T >:Degree() int *d=new intn;int i; ENode<T>* p; for ( i=0;i<n;i+) di=0; for ( i=0;i<n;i+) p=ai; while (p) dp->adjvex+;p=p->nextarc; for ( i=0;i<n;i+) cout<<"d"<<i<

24、<"="<<di;4 第188頁，第（6）題在題2所建立的鄰接表上進(jìn)行以頂點(diǎn)2為起始頂點(diǎn)的深度優(yōu)先搜索和廣度優(yōu)先搜索。分別畫出遍歷所得到的深度優(yōu)先搜索和廣度優(yōu)先搜索的生成森林（或生成樹）。5 第188頁，第（8）題分別設(shè)計(jì)算法，在鄰接矩陣上實(shí)現(xiàn)有向圖的深度優(yōu)先搜索.template<class T>void MGraph<T >:DFS(int v,bool visited) visitedv=true; cout<<" "<<v; for ( int j=0;j<n;j+) if

25、(avj&&!visitedj) DFS(j,visited);6 第188頁，第（10）題 設(shè)某項(xiàng)工程由圖題9-3所示的工序組成。若各工序以流水方式進(jìn)行（即串行進(jìn)行）。(1) 畫出給工程的AOV網(wǎng)絡(luò)；(2) 給出該工程的全部合理的工程流程。7 第188頁，第（11）題 設(shè)有邊集合：0，1，1，2，4，1，4，5，5，3，2，3(1) 求此圖的所有可能的拓?fù)湫蛄校?2) 若以此順序通過加入邊的方式建立鄰接表，則在該鄰接表上執(zhí)行拓?fù)渑判蛩惴ǎ═opoSort），則得到的拓?fù)湫蛄惺瞧渲心囊环N？ 8. 第188頁，第（13）題 使用普里姆算法以1為源點(diǎn)，畫出圖題9-5的無向圖的最小代

26、價(jià)生成樹。9. 第188頁，第（16）題用迪杰斯特拉算法求圖題9-6的有向圖中以頂點(diǎn)A為源點(diǎn)的單源最短路徑。寫出一維數(shù)組d 和 path在執(zhí)行該算法的過程中各步的狀態(tài)。源點(diǎn)終點(diǎn)最短路徑路徑長度AB(A,B)3C(A,B,C)4D(A,D)4E(A,B,E)4G _S dA pathAdBpathBdCpathCdDpathDdEpathEdGpathGA0,-13,A,-14,A5,A,-1B0,-13,A4,B4,A4,B,-1C0,-13,A4,B4,A4,B,-1D0,-13,A4,B4,A4,B,-1E0,-13,A4,B4,A4,B,-110. 第188頁，第（17）題用弗洛伊德算法

27、求圖題9-6的有向圖的所有頂點(diǎn)之間的最短路徑。寫出二維數(shù)組d和path在執(zhí)行該算法的過程中各步的狀態(tài)。 d path0345011023020320-1A-1AA-1-1-1B-1B-1-1-1-1C-1-1-1D-1-1-1-1-1-1-1E-1-1-1-1-1GG-1 （1）初始狀態(tài) dA pathA0354011023020320-1A-1AA-1-1-1B-1B-1-1-1-1C-1-1-1D-1-1-1-1-1-1-1E-1-1-1-1-1GG-1 dB pathB0344401102340420320-1ABAB-1-1-1B-1B-1-1-1-1C-1-1-1D B-1B-1-1

28、-1-1E-1-1-1-1-1GG-1 dC pathC03444013102340420320-1ABAB-1-1-1BCB-1-1-1-1C-1-1-1D B-1B-1-1-1-1E-1-1-1-1-1GG-1dD pathD03444013150263404562067320-1ABAB-1-1-1BCB-1-1D-1CB-1-1D B-1B-1-1DBE-1-1-1DBGG-1dE dG pathE pathG03444013150263404562067320-1ABAB-1-1-1BCB-1-1D-1CB-1-1DB-1B-1-1DBE-1-1-1DBGG-121. 第200頁，第

29、（1）題元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，給出各趟排序結(jié)果。 (1) 簡單選擇排序； (2) 冒泡排序； (3) 直接插入排序； (4) 快速排序； (5) 兩路合并排序；(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趟 （0

30、3 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 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

31、 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第8趟 03 08 12 26 53 61 70 75 87 97第9趟 03 08 12 26 53 61 70 75 87 97（3）直接插入排序初始序列（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

32、 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）22. 第200頁，第（3）題在帶表頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)簡單選擇排序。template &

33、lt;class T> void SingleList<T>:select_sort() Node<T> *p,*r,*small; p=first->link; if(p) for(; p->link; p=p->link) for(small=p,r=p->link; r; r=r->link) if(small->data>r->data) small=r; if(small!=p) swap(p->data, small->data); ;直接插入排序：template <class T&g

34、t; /用帶表頭節(jié)點(diǎn)的單鏈表存儲(chǔ)void SingleList<T>:DirInsert() Node<T> *head,*q,*p1,*p2; if(first->link) head=first->link->link; /head是待插入元素的鏈表頭 first->link->link=NULL; /first是只有一個(gè)節(jié)點(diǎn)的有序鏈表 while(head) q=head; head=head->link;/從待插入鏈中取下一個(gè)節(jié)點(diǎn) p1=first; p2=first->link; /p1是p2的直接前驅(qū)節(jié)點(diǎn) while

35、(p2&&p2->data<q->data) /從前往后找插入位置 p1=p2; p2=p2->link; if(p2) /q插入在p1和p2之間 q->link=p2; p1->link=q; else /q插入在p2之后，即有序鏈的最后 q->link=NULL; p1->link=q; 104template <class T> void sort(T a,int n) int i,j,k=0,m=-1,s,t; T x; while (k<m) s=k; for (i=k;i<m;i+) /從上向下沉底 if (ai>ai+1) x=ai; ai=ai+1; a