數(shù)據(jù)結(jié)構(gòu)期末題型歸納測(cè)試

1、WORD格式一、編寫(xiě)算法實(shí)現(xiàn)單鏈表的就地逆置，即要求利用原單鏈表的節(jié)點(diǎn)空間，把數(shù)據(jù)元素序列 (a0，a1, ,an-1) 逆置為 an-1, ,a1,a0。 15 分typedef int DataType;typedef struct NodeDataTypde data;struct Node* next;SLNode;void Converse(SLNode* head)SLNode *p, *q;p = head->next;head->next = NULL;while (p != NULL)q = p;p = p->next;q->next = head-&

2、gt;next;head->next = q;二、對(duì)于一個(gè)堆棧， 15 分（ 1 如果輸入序列有 A， B，C，D 組成，試給出全部可能的輸出序列和不可能的輸出序列。（ 2 設(shè)有 n 個(gè)數(shù)據(jù)元素的序列順序進(jìn)棧，試給出可能的輸出序列個(gè)數(shù)。（ 3 設(shè)有 n 個(gè)數(shù)據(jù)元素的序列順序進(jìn)棧，試給出不可能的輸出序列個(gè)數(shù)。（ 4 以 n=4 為例，用 2和 3中得出的公式驗(yàn)證 1的結(jié)論。(1) 隊(duì)列有：ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA不可能的輸出隊(duì)列有：DABC,ADBC,DACB,DBAC,BDA

3、C,DBCA,DCAB,CDAB,CADB,CABD(2) 可能的輸出序列個(gè)數(shù)為：C n1( 2n)!n*1 (n! ) 23對(duì)有 n 個(gè)數(shù)據(jù)元素的序列，全部可能的排列個(gè)數(shù)Pn n! ，所以，不可能的輸出序列個(gè)數(shù)為： Pn C n4當(dāng) n=4 時(shí)，有C414, P4C 4 24 14 10 ，與1中得出的結(jié)論個(gè)數(shù)相符，說(shuō)明專業(yè)資料整理WORD格式1中得出的結(jié)論是正確的。專業(yè)資料整理WORD格式三、給出采用設(shè)置標(biāo)志位的方法解決隊(duì)列操作和出隊(duì)列操作的算法思想?！凹僖绯?問(wèn)題的順序循環(huán)隊(duì)列的初始化操作、15 分入專業(yè)資料整理WORD格式設(shè) MaxSize 為順序循環(huán)隊(duì)列的數(shù)組最大個(gè)數(shù)，front 為

4、對(duì)頭指針， rear 為隊(duì)尾指針，為標(biāo)志。初始化操作算法思想：置對(duì)頭指針front=0 ，隊(duì)尾指針rear=0，標(biāo)志 tag=0；入隊(duì)列操作算法思想：1判斷是否為滿隊(duì)列，對(duì)滿時(shí)推出，對(duì)滿的條件為rear=front 并且 tag=1tag專業(yè)資料整理WORD格式（ 2 當(dāng)隊(duì)列不滿時(shí)，把要入隊(duì)列的數(shù)據(jù)元素插入到隊(duì)尾（ 3 修改隊(duì)尾指針， rear= rear+1 %MaxSize;（ 4 判斷并標(biāo)記是否對(duì)滿，當(dāng) rear=front 時(shí)置 tag=1。出隊(duì)列操作算法思想：1判斷隊(duì)列是否為空，隊(duì)空時(shí)推出，對(duì)空的條件為rear=front 并且 tag=0（ 2 當(dāng)隊(duì)列不空時(shí)，把當(dāng)前對(duì)頭元素從對(duì)頭刪

5、除；（ 3 修改對(duì)頭指針， front=(front+1)%MaxSize ；（ 4 置標(biāo)記 tag 為非滿狀態(tài)，即置 tag=0。四、對(duì)于如下所示的稀疏矩陣A ： 20 分（ 1 寫(xiě)出該稀疏矩陣的三元組線性表（ 2 畫(huà)出稀疏矩陣 A 的三元組順序表構(gòu)造（ 3 畫(huà)出稀疏矩陣 A 的帶頭節(jié)點(diǎn)單鏈表構(gòu)造（ 4 畫(huà)出稀疏矩陣 A 的行指針數(shù)組鏈表構(gòu)造（ 5 畫(huà)出稀疏矩陣 A 的三元組十字鏈表構(gòu)造。五、給定如下列圖的數(shù)，請(qǐng)完成下述操作：20 分（ 1給出書(shū)的先根遍歷和后根遍歷得到的節(jié)點(diǎn)序列（ 2將該樹(shù)轉(zhuǎn)換為二叉樹(shù)（ 3給出該二叉樹(shù)的先序、后序、中序遍歷結(jié)果。（ 4給出該二叉樹(shù)的前序、中序、后序線索二叉

6、樹(shù)。六、假設(shè)一棵樹(shù)有m1 個(gè)度為 1 的結(jié)點(diǎn)，有m2 個(gè)度為 2 的結(jié)點(diǎn)有 mk 個(gè)度為 k 的結(jié)點(diǎn)，問(wèn)：專業(yè)資料整理WORD格式樹(shù)中共有多少個(gè)葉結(jié)點(diǎn)。15 分假設(shè)初始時(shí)該樹(shù)只存在一個(gè)根節(jié)點(diǎn)，該根節(jié)點(diǎn)的度為0，此時(shí)該樹(shù)的葉節(jié)點(diǎn)個(gè)數(shù)為1.每加一個(gè)度為1 的節(jié)點(diǎn)時(shí)， 均產(chǎn)生一個(gè)新葉節(jié)點(diǎn)，同時(shí)占去原先一個(gè)葉節(jié)點(diǎn)，故葉節(jié)點(diǎn)數(shù)不變，即此時(shí)增加了1-1 *m1=0 個(gè)節(jié)點(diǎn)。每增加一個(gè)度為2 的節(jié)點(diǎn)時(shí)， 均產(chǎn)生兩個(gè)新葉節(jié)點(diǎn)，同時(shí)占去原先一個(gè)葉節(jié)點(diǎn)，故在原先葉節(jié)點(diǎn)數(shù)上加2-1 個(gè)葉節(jié)點(diǎn)；又存在m2 個(gè)度為 2 的節(jié)點(diǎn)，故此時(shí)增加了2-1*m2 個(gè)葉節(jié)點(diǎn)。以此類推， 每增加一個(gè)度為k 的節(jié)點(diǎn)時(shí)， 均產(chǎn)生 k 個(gè)新葉節(jié)點(diǎn)， 同時(shí)占去原先一個(gè)葉節(jié)點(diǎn)，故在原先葉節(jié)點(diǎn)數(shù)上加k-1 個(gè)葉節(jié)點(diǎn)； 又存在 mk 個(gè)度為 k 的節(jié)點(diǎn)， 故此時(shí)增加了