1、數據結構（本）形成性考核作業答案作業1（本部分作業覆蓋教材第1-2章的內容）一、單項選擇題1C 2D 3B 4C 5D 6C 7B 8C 9A 10B11C 12D 13C 14A 15B 16C 17C 18B 19B 20D二、填空題 1n-i+12n-i 3集合 線性結構 樹形結構 圖狀結構 4物理結構 存儲結構 5線性結構 非線性結構6有窮性 確定性 可形性 有零個或多個輸入 有零個或多個輸出 7圖狀結構 8樹形結構 9線性結構 10 n-1 O(n)11s->next=p->next; 12head 13q->next=p->next; 14p->nex

2、t=head; 15單鏈表16順序存儲 鏈式存儲17存儲結構18兩個 直接后繼 直接前驅 尾結點 頭結點19頭結點的指針 指向第一個結點的指針20鏈式 鏈表三、問答題1簡述數據的邏輯結構和存儲結構的區別與聯系，它們如何影響算法的設計與實現？答：若用結點表示某個數據元素，則結點與結點之間的邏輯關系就稱為數據的邏輯結構。數據在計算機中的存儲表示稱為數據的存儲結構。可見，數據的邏輯結構是反映數據之間的固有關系，而數據的存儲結構是數據在計算機中的存儲表示。盡管因采用的存儲結構不同，邏輯上相鄰的結點，其物理地址未必相同，但可通過結點的內部信息，找到其相鄰的結點，從而保留了邏輯結構的特點。采用的存儲結構不

3、同，對數據的操作在靈活性，算法復雜度等方面差別較大。2解釋順序存儲結構和鏈式存儲結構的特點，并比較順序存儲結構和鏈式存儲結構的優缺點。答：順序結構存儲時，相鄰數據元素的存放地址也相鄰，即邏輯結構和存儲結構是統一的，要求內存中存儲單元的地址必須是連續的。優點：一般情況下，存儲密度大，存儲空間利用率高。缺點：（1）在做插入和刪除操作時，需移動大量元素；（2）由于難以估計，必須預先分配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。鏈式結構存儲時，相鄰數據元素可隨意存放，所占空間分為兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。優點：插入和刪除元素時很方便，使用靈活

4、。缺點：存儲密度小，存儲空間利用率低。3什么情況下用順序表比鏈表好？答：順序表適于做查找這樣的靜態操作，鏈表適于做插入和刪除這樣的動態操作。如果線性表的變化長度變化不大，且其主要操作是查找，則采用順序表；如果線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。4解釋頭結點、第一個結點（或稱首元結點）、頭指針這三個概念的區別？答：頭結點是在鏈表的開始結點之前附加的一個結點；第一個結點（或稱首元結點）是鏈表中存儲第一個數據元素的結點；頭指針是指向鏈表中第一個結點（或為頭結點或為首元結點）的指針。5解釋帶頭結點的單鏈表和不帶頭結點的單鏈表的區別。 答：帶頭結點的單鏈表和不帶頭結點的單鏈表

5、的區別主要體現在其結構上和算法操作上。在結構上，帶頭結點的單鏈表，不管鏈表是否為空，均含有一個頭結點，不帶頭結點的單鏈表不含頭結點。在操作上，帶頭結點的單鏈表的初始化為申請一個頭結點。無論插入或刪除的位置是地第一個結點還是其他結點，算法步驟都相同。不帶頭結點的單鏈表，其算法步驟要分別考慮插入或刪除的位置是第一個結點還是其他結點。因為兩種情況的算法步驟不同。四、程序填空題1（1）p->data=i（2）p->next=NULL（3）q->next=p（4）q=p2（1）head=p（2）q=p（3）p->next=NULL（4）p->next=q->next（

6、5）q->next=p3（1）p=q->next（2）q->next=p->next五、完成：實驗1線性表根據實驗要求（見教材P201-202）認真完成本實驗，并提交實驗報告。作業2答案（本部分作業覆蓋教材第3-5章的內容）一、單項選擇題1C 2B 3A 4C 5B 6A 7B 8C 9A 10C 11B 12C 13B 14B 15A 16C 17B 18A 19C 20D 21B 22D 23C 24B 25D 26A 27C 28D 29D 30C 31A 32D 二、填空題 1后進先出2下一個3增1 增14假上溢5 棧是否滿 s->top=MAXSIZE-

7、1 棧頂指針 棧頂對應的數組元素 棧是否空 s->top=-1 棧頂元素 修改棧頂指針6bceda7終止條件 遞歸部分8LU->front=LU->rear9運算符 操作數 ab+c/fde/-10s->next=h; 11h=h->next; 12r->next=s; 13f=f->next; 14字符 15順序存儲方式 鏈式存儲方式 160 空格字符的個數 17特殊 稀疏 18（） （） 2 19（d,e,f） 20串長度相等且對應位置的字符相等 21i(i-1)/2+j 22行下標、列下標、非零元素值 三、問答題1簡述棧和一般線性表的區別。答：棧

8、是一種先進后出的線性表，棧的插入和刪除操作都只能在棧頂進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。2簡述隊列和一般線性表的區別。隊列是一種先進先出的線性表，隊列的插入只能在隊尾進行，隊列的刪除只能在隊頭進行，而一般的線性表可以在線性表的任何位置進行插入和刪除操作。3鏈棧中為何不設頭結點？答：因為鏈棧只在鏈頭插入和刪除結點，不可能在鏈表中間插入和刪除結點，算法實現很簡單，所以一般不設置頭結點。4利用一個棧，則：（1）如果輸入序列由A，B，C組成，試給出全部可能的輸出序列和不可能的輸出序列。（2）如果輸入序列由A，B，C，D組成，試給出全部可能的輸出序列和不可能的輸出序列。答：（

9、1）棧的操作特點是后進先出，因此輸出序列有：A入，A出，B入，B出，C入C出，輸出序列為ABC。A入，A出，B入，C入，C出，B出，輸出序列為ACB。A入，B入，B出，A出，C入，C出，輸出序列為BAC。A入，B入，B出，C入，C出，A出，輸出序列為BCA。A入，B入，C入，C出，B出，A出，輸出序列為CBA。由A，B，C組成的數據項，除上述五個不同的組合外，還有一個C，A，B組合。但不可能先把C出棧，再把A出棧，（A不在棧頂位置），最后把B出棧，所以序列CAB不可能由輸入序列A，B，C 通過棧得到。（2）按照上述方法，可能的輸出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BAC

10、D，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。不可能的輸出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD5用S表示入棧操作，X表示出棧操作，若元素入棧順序為1234，為了得到1342出棧順序，相應的S和X操作串是什么？答：應是SXSSXSXX。各操作結果如下：S 1入棧X 1出棧 輸出序列：1S 2入棧S 3入棧X 3出棧 輸出序列：13S 4入棧 X 4出棧 輸出序列：134X 2出棧 輸出序列：1342 6有5個元素，其入棧次序為：A、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先的

11、次序有哪幾個？答：從題中可知，要使C第一個且D第二個出棧，應是A入棧，B入棧，C入棧，C出棧，D入棧。之后可以有以下幾種情況：（1）B出棧，A出棧，E入棧，E出棧，輸出序列為：CDBAE。（2）B出棧，E入棧，E出棧，A 出棧，輸出序列為CDBEA。（3）E入棧，E出棧，B出棧，A出棧，輸出序列為CDEBA所以可能的次序有：CDBAE，CDBEA，CDEBA7寫出以下運算式的后綴算術運算式 3x2+x-1/x+5 (A+B)*C-D/(E+F)+G答；對應的后綴算術運算式 3x2*x+1x/-5+ AB+C*DEF+/-G+8 簡述廣義表和線性表的區別和聯系。答：廣義表是線性表的的推廣，它也是

12、n(n>0)個元素a1 ,a2ai an的有限序列，其中ai或者是原子或者是一個廣義表。所以，廣義表是一種遞歸數據結構，而線性表沒有這種特性，線性表可以看成廣義表的特殊情況，當ai都是原子時，廣義表退化成線性表。 四、程序填空題1（1）q->front->next=p->next;（2）free(p);（3）q->rear=q->front五、綜合題1答：出隊序列是e2,e4,e3,e6,e5,e1的過程： e1入棧（棧底到棧頂元素是e1） e2入棧（棧底到棧頂元素是e1,e2） e2出棧（棧底到棧頂元素是e1） e3入棧（棧底到棧頂元素是e1,e3） e4

13、入棧（棧底到棧頂元素是e1,e3,e4） e4出棧（棧底到棧頂元素是e1,e3） e3出棧（棧底到棧頂元素是e1） e5入棧（棧底到棧頂元素是e1,e5） e6入棧（棧底到棧頂元素是e1,e5,e6） e6出棧（棧底到棧頂元素是e1,e5） e5出棧（棧底到棧頂元素是e1） e1出棧（棧底到棧頂元素是空）棧中最多時有3個元素，所以棧S的容量至少是3。2算法設計如下：/*只有一個指針rear的鏈式隊的基本操作*/#include <stdio.h>typedef char elemtype;struct node /*定義鏈隊列結點*/elemtype data;struct nod

14、e *next;typedef struct queue /*定義鏈隊列數據類型*/struct node *rear; LinkQueue;void initqueue(LinkQueue *Q)/*初始化隊列*/ Q=(struct queue *)malloc(sizeof(struct queue); Q->rear=NULL; void enqueue(LinkQueue *Q,elemtype x) /*入隊算法*/ struct node *s,*p; s=(struct node *)malloc(sizeof(struct node); s->data=x; if

15、 (Q->rear=NULL) /*原為空隊時*/ Q->rear=s;s->next=s; else /*原隊不為空時*/ p=Q->rear->next; /*p指向第一個結點*/Q->rear->next=s; /*將s鏈接到隊尾*/Q->rear=s; /*Q->rear指向隊尾*/s->next=p; void delqueue(LinkQueue *Q) /*出隊算法*/ struct node *t; if (Q->rear=NULL) printf("隊列為空!n");return(0); e

16、lse if (Q->rear->next=Q->rear) /*只有一個結點時*/ t=Q->rear;Q->rear=NULL; else /*有多個結點時*/ t=Q->rear->next; /*t指向第一個結點*/Q->rear->next=t->next; /*引成循環鏈*/ free(t); elemtype gethead(LinkQueue *Q) /*取隊首元素算法*/ if (Q->rear=NULL) printf("隊列為空!n"); else return(Q->rear-&

17、gt;next->data); int emptyqueue(LinkQueue *Q) /*判斷隊列是否為空算法*/ if (Q->rear=NULL) return(1); /*為空,則返回true*/ else return(0); /*不為空,則返回flase*/ void dispqueue(LinkQueue *Q) /*顯示隊列中元素算法*/ struct node *p=Q->rear->next; printf("隊列元素:"); while (p!=Q->rear) printf("%c ",p->

18、data);p=p->next; printf("%cn",p->data);六、完成：實驗2棧、隊列、遞歸程序設計根據實驗要求（見教材P203）認真完成本實驗，并提交實驗報告。作業3答案（本部分作業覆蓋教材第6-7章的內容）一、單項選擇題1B 2B 3D 4C 5B 6A 7A 8C 9A 10. D11. A 12C 13C 14B 15B 16C 17B 18C 19A 20B21D 22B 23. B 24. B 25. C 26. A 27A 28C二、填空題 1子樹樹木或后繼結點數2樹中所有結點的度的最大值3分支結點 非終端結點4葉子結點 終端結點5

19、子樹的根 后繼結點 孩子結點6祖先7樹中結點的最大層數8 9根結點 左子樹 右子樹10左子樹 根結點 右子樹11左子樹 右子樹 根結點12權13帶權路徑長度之和14最優二叉樹 最小的二叉樹1569 162m-1 17多對多18所有頂點 一次19先序 20按層次21n222鄰接矩陣 鄰接表232(n-1)24n-125棧三、綜合題1寫出如下圖所示的二叉樹的先序、中序和后序遍歷序列。答：二叉樹的定義是遞歸的，所以，一棵二叉樹可看作由根結點，左子樹和右子樹這三個基本部分組成，即依次遍歷整個二叉樹，又左子樹或者右子樹又可看作一棵二叉樹并繼續分為根結點、左子樹和右子樹三個部分.，這樣劃分一直進行到樹葉結

20、點。(1)先序為“根左右”，先序序列為：fdbacegihl(2)中序為“左根右”，中序序列為：abcdefghij(3)后序為“左右根”，后序序列為：acbedhjigf2已知某二叉樹的先序遍歷結果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍歷結果是：G，D，B，A，L，H，E，K，I，M，C，F和J，請畫出這棵二叉樹，并寫出該該二叉樹后續遍歷的結果。 （1）二叉樹圖形表示如下： （2）該二叉樹后序遍歷的結果是：G、D、B、L、H、K、M、I、E、J、F、C和A。 3答 已知深度為k的二叉樹最多有2k-1個結點(K1)， 29-1<892< 210-1，故樹

21、的高度為10 對于完全二叉樹來說，度為1的結點只能是0或1因為n=n0+n1+n2和n0=n2+1得：設n1=0，892=n0+0+n2=2n2+1得n2不為整數出錯設n1=1，892=n0+1+n2=2n2+2得n2 =445 n0=n2+1=446葉子結點數為446。 由得單支結點數為1 對于n個結點的完全二叉樹，最后一個樹葉結點，即序號為n的葉結點其雙親結點 即為最后一個非終端結點，序號為892/2=446。4（1）先序序列和中序序列相同的二叉樹為空樹或任一結點均無左孩子的非空二叉樹（2）中序和后序序列相同的二叉樹為空樹或任一結點均無右孩子的非空二叉樹（3）先序和后序序列相同的二叉樹為空

22、樹或僅有一個結點5（1）哈夫曼樹如圖B-4所示。圖B-4（2）其帶權路徑長度WPL值為270。（3）每個字符的哈夫曼編碼為：A:100, B:11, C:1010, D:000, E:0010, F:10110, G:10111, H:0011, I:01 6答（1）深度優先遍歷：v1,v2,v3,v8,v5,v7,v4,v6 廣度優先遍歷：v1,v2,v4,v6,v3,v5,v7,v8(2) G的拓撲序列為：v1,v2,v4,v6,v5,v5,v3,v5,v7,v8(3)最短路徑為：v1,v2,v5,v7,v87 g1的圖示和圖g1的鄰接表如下圖所示。 圖G 圖G的鄰接矩陣如下圖所示： 0

23、1 0 1 01 0 0 1 10 0 0 1 11 1 1 0 00 1 1 0 0 圖G的鄰接矩陣 圖G的鄰接表V1、V2、V3、V4、V5的度分別為：2，3，2，3，2 四、程序分析題1. (1) return c1+1 (2) NodeLevel(BT->right,X) (3) (c2>=1) return c2+12(1)for(j=0; j<n; j+) (2) dfstree(GA,j,n); 五、算法設計題1寫一個將一棵二叉樹復制給另一棵二叉樹的算法。define NULL 0typedef struct btnodeelemtype data;struct

24、 btnode *lchild, *rchild;bitnode, *bitree;bitree *CopyTree( bitnode *p )/*復制一棵二叉樹*/bitnode *t;if ( p!=NULL )t=(bitnode *)malloc (sizeof (bitnode);t->data=p->data;t->lchild=CopyTree(p->lchild);t->rchild=CopyTree(p->rchild);return(t);elsereturn(NULL);/*CopyTree*/2. int BTreeLeafCount

25、(struct BTreeNode* BT) if(BT=NULL) return 0; else if(BT->left=NULL && BT->right=NULL) return 1; else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right); 六、完成：實驗3棧、隊列、遞歸程序設計 實驗4圖的存儲方式和應用根據實驗要求（見教材P203）認真完成本實驗，并提交實驗報告。作業4答案（本部分作業覆蓋教材第8-9章的內容）一、單項選擇題1D 2C 3B 4C 5D 6 7C 8D 9B

26、10D 11C 12C13A 14C 15D16B 17B 18D 19D20A21D22D23A 24A 25C 26C 27B 28A 29B 30C二、填空題 1哈希表查找法2數據項的值 記錄3主關鍵字4數學期望值5順序6二分查找 升序或降序排列 7順序存儲結構 8索引順序查找 順序查找9均小于根結點的值 均大于根結點的值 二叉排序樹10自變量 函數值119， 14， 16 ，17 12內部排序 外部排序 13交換排序 143154 816堆排序 快速排序17主關鍵字 18關鍵字相等的記錄19n-1,n-j20堆尾 堆頂 向下 三、綜合題1已知序列（70，83，100，65，10，32，

27、7，9），請寫出對此序列采用插入排序法進行升序排序時各趟的結果。答：原始序列：（70），83，100，65，10，32，7，9第1趟： （70，83），100，65，10，32，7，9第2趟：（70，83，100），65，10，32，7，9第3趟：（65，70，83，100），10，32，7，9第4趟：（10，65，70，83，100），32，7，9第5趟：（10，32，65，70，83，100），7，9第6趟：（7，10，32，65，70，83，100），9第7趟：（7，9，10，32，65，70，83，100）2已知序列（10，18，4，3，6，12，1，9，15，8），請寫出對此序列采用

28、歸并排序法進行升序排序時各趟的結果。答：原始序列：10，18，4，3，6，12，1，9，15，8第1趟： 10，18 3，46，121，9 8，15第2趟： 3，4，10，18， 1，6，9，12 8，15第3趟： 3，4，10，18， 1，6，8，9，12，15第4趟： 1，3，4，6，8，9，10，12，15，183已知序列（17，18，60，40，7，32，73，65，85）采用冒泡排序法排序的各趟的結果如下：原始初始：17，18，60，40，7，32，73，65，85第1趟：17，18，40，7，32，60，65，73，85第2趟：17，18，7，32，40，60，65，73，85第3

29、趟：17，7，18，32，40，60，65，73，85第4趟：7，17，18，32，40，60，65，73，85第5趟：7，17，18，32，40，60，65，73，85 4已知序列（503，87，512，61，908，170，897，275，653，462）請給出采用快速排序法對該序列作升序排列時的每一趟結果。原始序列：503，87，512，61，908，170，897，275，653，462第1趟： 462，87，275，61，170503897，908，653，512 第2趟： 170，87，275，61 462，503897，908，653，512 第3趟： 87，61170275 4

30、62，503897，908，653，512 第4趟： 61 87170275 462，503897，908，653，512第5趟： 61 ，87，170，275 462，503897，908，653，512第6趟： 61 ，87，170，275，462，503897，908，653，512第7趟： 61 ，87，170，275，462，503512，653897908第8趟： 61 ，87，170，275，462，503，512，653 897908第9趟： 61 ，87，170，275，462，503，653，897908第10趟： 61 ，87，170，275，462，503，653，897，9085設一組記錄的關鍵字序列為（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并畫出中間過程）（1）以二叉樹描述6個元素的初始堆（2）以二叉樹描述逐次取走堆頂元素后，經調整得到的5個元素、4個元素的堆答：（1）4959834143478347414359494983414743598359494143478349594159474149