南京工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)樣卷09級加答案

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)09一.填空題（26分，每空2分）1.聲明抽象數(shù)據(jù)類型的目的是________________________________________。2.已知結(jié)點(diǎn)類Node有data和next域，下列數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)聲明分別為__________________________________和_____________________________________。3.已知SStrings1(“aababbabac“)s2(“

2、aba“)，執(zhí)行下列語句后，s1字符串是______________。s1.replaceAll(s1.substring(01)s2)s1.removeAll(s2.substring(02))4.中綴表達(dá)式AB(CD(EF)GH)(IJ)K的后綴表達(dá)式為______________________。5.設(shè)一個(gè)順序循環(huán)隊(duì)列容量為60，當(dāng)front=47，rear=23時(shí)，該隊(duì)列有__________個(gè)元素。6.已知二維數(shù)組a[10][

3、8]采用行主序存儲(chǔ)，數(shù)組首地址是1000，每個(gè)元素占用4字節(jié)，則數(shù)組元素a[4][5]的存儲(chǔ)地址是__________________________。7.已知一棵完全二叉樹的根（第0個(gè)）結(jié)點(diǎn)層次為1，則第100個(gè)結(jié)點(diǎn)的層次為_______。8.中根遍歷序列和后根遍歷序列相反的二叉樹是_________________________________。9.由256個(gè)權(quán)值構(gòu)造一棵哈夫曼樹，則該二叉樹共有________________結(jié)點(diǎn)

4、。10.由n個(gè)頂點(diǎn)組成的無向連通圖，最多可以有_____________________條邊。11.10個(gè)元素的排序數(shù)據(jù)序列采用折半查找的平均查找長度是（寫出算式）_____________________________________________________。12.已知關(guān)鍵字序列為674134106924785441，采用快速排序算法按升序排序，以第一個(gè)元素為基準(zhǔn)值，其第一趟排序后的關(guān)鍵字序列為_______________

5、_____________。二.問答題（45分，每小題5分）1.已知目標(biāo)串為“aabcbabcaabcaababc“，模式串為“abcaababc“，寫出模式串改進(jìn)的next數(shù)組；畫出KMP算法的匹配過程，給出字符比較次數(shù)。2.什么是棧和隊(duì)列？兩者有何異同？什么情況下需要使用?；蜿?duì)列？采用順序存儲(chǔ)結(jié)構(gòu)的棧和隊(duì)列，在進(jìn)行插入、刪除操作時(shí)需要移動(dòng)數(shù)據(jù)元素嗎？為什么？什么是隊(duì)列的假溢出？為什么順序存儲(chǔ)結(jié)構(gòu)隊(duì)列會(huì)出現(xiàn)假溢出？怎樣解決隊(duì)列的假溢出

6、問題？鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列會(huì)出現(xiàn)假溢出嗎？順序存儲(chǔ)結(jié)構(gòu)的棧會(huì)出現(xiàn)假溢出嗎？為什么？3.已知一棵二叉樹中根次序遍歷序列為GCBHKAMFDJE，后根次序遍歷序列為CBGHMAJEDFK，畫出這棵二叉樹并進(jìn)行中序線索化。4.設(shè)一段正文由字符集ABCDEFGH組成，其中每個(gè)字符在正文中的出現(xiàn)次數(shù)依次為2351749312918，采用哈夫曼編碼對這段正文進(jìn)行壓縮存儲(chǔ)，畫出所構(gòu)造的哈夫曼樹，并寫出每個(gè)字符的哈夫曼編碼。5.刪除以下帶權(quán)無向圖中的頂點(diǎn)D

7、，畫出刪除D后圖的鄰接矩陣表示和鄰接表表示。2.下列trim()函數(shù)欲刪除當(dāng)前字符串對象中的所有空格字符。voidSString::trim()刪除串對象中的所有空格字符inti=0while(element[i]!=i記住第1個(gè)空格下標(biāo)f(intj=ielement[j]!=0j)if(element[j]!=)element[i]=element[j]非空格字符向前移動(dòng)到空格字符位置len=i①對于以下調(diào)用語句，運(yùn)行結(jié)果是什么？正確

8、的運(yùn)行結(jié)果是什么？SStringstr(“abcdefxyz“)str.trim()coutclassTriNode二叉樹的三叉鏈表結(jié)點(diǎn)類public:Tdata數(shù)據(jù)域，保存元素TriNodeparentleftright指針域，分別指向父母、左、右孩子結(jié)點(diǎn)構(gòu)造結(jié)點(diǎn)，參數(shù)依次分別指定元素、左孩子和右孩子結(jié)點(diǎn)TriNode(TdataTriNodeleft=NULLTriNoderight=NULL)thisdata=datathisle