1、習題1 1解釋以下概念：邏輯結構，存儲結構，操作，數據結構，數據結構的表示，數據結構的實現，抽象數據類型，算法，算法的時間代價，算法的空間代價，大O表示法。 2理解以下關系：算法與數據結構的關系；數據結構與抽象數據類型的關系；算法和數據結構與問題求解的關系。 3. 寫出下列程序段的平均情況下的時間代價O表示式。(1) a=b+c; d=a+e(2) sum=0; for (i=0;i<3;i+) for (j=0;j<n;j+) sum+;(3) x=n; y=0; while (x>=(y+1)*(y+1) y+;(4) s=0; if(even(n) for (i=0;i

2、<n;i+) sum+; else s=s+n;(5) x=66;n=200; while (n>0) if(x>lO0) x=x-10; n=n-1; else x=x+1; 4對于給定的n個元素，可以構造出的邏輯結構有 ， ， ， 四種。 5.按增長率由小到大的順序排列下列各函數：2100, ()n, ()n, ()n, nn, n, n!, n, log2n, n/log2n習題22.1已知L是無頭結點的單鏈表，且p結點既不是第一個結點，也不是最后一個結點，試從下列提供的語句中選出合適的語句序列：(1)在p結點之后插入s結點：(2)在p結點之前插入s結點：(3)在單鏈表

3、L首插入s結點：(4)在單鏈表L后插入s結點：提供的語句：p->nexts； p->nextp->next->next；p->next=s->next； s->next=p->next；s->nextL； s->next=p；s->next=NULL； qp；while(p->next!=q)p=p->next； while(p->next!=NULL)p=p->next；p=q； p=L；Ls； Lp；2.2已知p結點是某雙向鏈表的中間結點，試從下列提供的語句中選出合適的語句序列。(1)在p結點之后插入

4、s結點：(2)在p結點之前插入s結點：(3)刪除p結點的直接后繼結點：(4)刪除p結點的直接前驅結點：提供的語句：p->nextp->next->next； p->prior=p->prior->prior；p->next=s； p->prior=s；s->next=p； s->priorp；s->next=p->next； s->prior=p->prior；p->prior->next=p->next； p->prior->nextp；p->next->priorp

5、； p->next->priors；p->prior->next=s； p->next->prior=p->prior；q=p->next； q=p->prior；free(p)； free(q)；2.3試編寫一個計算頭結點指針為L的單鏈表長度的算法。2.4試編寫一個將單循環鏈表逆置的算法。2.5已知一順序表A，其元素值非遞減有序排列，編寫一個算法，刪除順序表中多余的值相同的元素。習題3 3.1 簡述棧和線性表的區別。簡述棧和隊列的相同點和不同點。 3.2 如果進棧的數據元素序列為1、2、3、4、5、6，能否得到4、3、5、6、1、2和1、

6、3、5、4、2、6的出棧序列?并說明為什么得不到或如何得到。 3.3 利用兩個棧模擬一個隊列的入隊、出隊和判斷隊列空的運算。 3.4 寫一算法，將一個順序棧中的元素依次取出，并打印元素值。 3.5 寫一算法，將一個非負十進制整數轉換成二進制。 3.6 寫一算法，將一個鏈式隊列中的元素依次取出，并打印元素值。 3.7 設有編號為1、2、3、4的4輛車，順序進入一個棧式結構的站臺，試寫出這4輛車開出站臺的所有可能的順序。 3.8 寫一個算法，借助于棧將一個單鏈表逆置。習題44.1 空串和空格串有什么區別?4.2 兩個字符串相等的充要條件是什么?4.3 串的三種機內表示方法是什么?4.4 設S

7、9;I am a student'，T'good'，Q'worker'。求： (1)StrLength(S) (2)SubString(&Sub，S，8，7) (3)SubString(&Sub，T，2，1) (4)Index(S，'a'，1) (5)Index(S，T，1) (6)Replace(&S，'Student'，Q) (7)Concat(&N，SubString(&V，S，6，2)，Concat(&P，T，SubString(&W,S,7,8)4.5 設A

8、'This'，F'a sample'，C'good'，D'ne'，B' '，G'is'。求： (1)Coneat(&S，A，Concat(&Z，SubString(&Y，F，2，7)，Concat(&X，B，SubString(A，3，2) (2)Concat(&U，SubString(&X，C，3，1)，D) (3) Replace(&F，SubString(&X，F，3，6)，C) (4)StrLength(S) (5)Index(

9、V，G，1) (6)Index(U，G，1) (7) Concat(&V，S，Concat(&Z，B，Concat(&Y，F，Concat(&X，B，U)4.6 利用C的庫函數strlen、strcpy(或strcat)寫一個算法voidStrDelete(char *S,int i,int m)，刪除串S中從位置i開始連續的m個字符。若istrlen(S)，則沒有字符被刪除；若i+mstrlen(S)，則S中從位置i開始直至末尾的字符均被刪去.。 4.7 采用順序結構存儲串，編寫一個函數，求串s和串t的一個最長的公共子串。 提示: 需要采用三重循環來實現。習題

10、51. 假設按行優先存儲整數數組A9358時，第一個元素的字節地址是100，每個整數占4個字節。問下列元素的存儲地址是什么?(1) a0000 (2) a1111 (3) a3125 (4) a82472. 假設一個準對角矩陣按以下方式存儲于一維數組B4m中：寫出由一對下標 (i,j) 求k的轉換公式。3. 現有如下的稀疏矩陣A，要求畫出三元組表示法。習題610. 假設用于通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別為7，19，2，6，32，3，21，10。試為這8個字母設計赫夫曼編碼。使用07的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優缺點。11一棵度為2的樹與

11、一棵二叉樹有何區別?樹與二叉樹之間有何區別?12對于如圖所示的樹，試給出： (1)雙親數組表示法示意圖； (2)孩子鏈表表示法示意圖；(3)孩子兄弟鏈表表示法示意圖。13畫出下圖所示的森林經轉換后所對應的二叉樹，并指出在二叉鏈表中某結點所對應的森林中結點為葉子結點的條件。14將如圖所示的二叉樹轉換成相應的森林。15在具有n(n>1)個結點的各棵樹中，其中深度最小的那棵樹的深度是多少?它共有多少葉子和非葉子結點?其中深度最大的那棵樹的深度是多少?它共有多少葉子和非葉子結點?16畫出和下列已知序列對應的樹T：樹的先根訪問序列為：GFKDAIEBCHJ；樹的后根訪問序列為：DIAEKFCJHB

12、G。17畫出和下列已知序列對應的森林F：森林的先序訪問序列為：ABCDEFGHIJKL；森林的中序訪問序列為：CBEFDGAJIKLH。18對以孩子兄弟鏈表表示的樹編寫計算樹的深度的算法。習題71 對于右圖所示的有向圖，試給出： (1)每個頂點的入度和出度。 (2)鄰接矩陣。 (3)鄰接表。 (4)逆鄰接表。 (5)強連通分量。2 設無向圖G如右圖所示，試給出： (1)該圖的鄰接矩陣。 (2)該圖的鄰接表。 (3)該圖的多重鄰接表。 (4)從v0出發的“深度優先”遍歷序列。 (5)從v0出發的“廣度優先”遍歷序列。3請對下邊的無向帶權圖， (1)寫出它的鄰接矩陣，并按普里姆算法求其最小生成樹； (2)寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹。4 對下圖所示的帶權有向圖G，試回答以下問題：(1)求出G中從結點v1出發按深度優先搜索遍歷G所得到結點序列；(2)求出G中從結點v1出發按廣度優先搜索遍歷G所得的結