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

1、WORD格式一、編寫算法實現(xiàn)單鏈表的就地逆置，即要求利用原單鏈表的節(jié)點空間，把數(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;二、對于一個堆棧， 15 分（ 1 如果輸入序列有 A， B，C，D 組成，試給出全部可能的輸出序列和不可能的輸出序列。（ 2 設(shè)有 n 個數(shù)據(jù)元素的序列順序進棧，試給出可能的輸出序列個數(shù)。（ 3 設(shè)有 n 個數(shù)據(jù)元素的序列順序進棧，試給出不可能的輸出序列個數(shù)。（ 4 以 n=4 為例，用 2和 3中得出的公式驗證 1的結(jié)論。(1) 隊列有：ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA不可能的輸出隊列有：DABC,ADBC,DACB,DBAC,BDA

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

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

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

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