02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論20xx年10月份真題及答案-資料下載頁
2025-06-28 08:36本頁面
【正文】 其空間復(fù)雜度最優(yōu)的排序方法是___堆排序___。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)29．借助于隊(duì)列能夠?qū)⒑衝個數(shù)據(jù)元素的棧逆置，比如棧S中的元素為{a，b，C}逆置后變成{C，b，a}。試簡述你的解決方案。30．為便于表示二叉樹的某些基本運(yùn)算，則深度為k．的二叉樹的順序存儲結(jié)構(gòu)中的數(shù)組的大小為多少?畫出如題30圖所示的二叉樹的順序存儲結(jié)構(gòu)示意圖，并說明對一般形態(tài)的二叉樹不太適合使用順序存儲結(jié)構(gòu)來表示的原因。31．先序遍歷、中序遍歷一個森林分別等同于先序、中序遍歷該森林所對應(yīng)的二叉樹?，F(xiàn)已知一個森林的先序序列和中序序列分別為ABCDEFIGJH和BDCAIFJGHE，試畫出該森林。32．設(shè)有一組關(guān)鍵字值序列{e，b，d，f，a，g，C}現(xiàn)要求：(1)根據(jù)二叉排序樹的創(chuàng)建方法構(gòu)造出相應(yīng)的二叉排序樹(關(guān)鍵字值的大小按字母表順序計(jì))；(2)計(jì)算等概率情況下在該二叉排序樹上查找成功的平均查找長度ASL。33．若采用二路歸并排序方法對關(guān)鍵字序列{25，9，78，6，65，15，58，18，45，20}進(jìn)行升序排序，寫出其每趟排序結(jié)束后的關(guān)鍵字序列。四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共l4分)34．某電商有關(guān)手機(jī)的庫存信息，按其價格從低到高存儲在一個帶有頭結(jié)點(diǎn)的單循環(huán)鏈表中，鏈表中的結(jié)點(diǎn)由品牌型號(nametype)、價格(price)、數(shù)量(quantity)和指針(next)四個域組成。現(xiàn)新到in臺、價格為c、品牌型號為x的新款手機(jī)需入庫，寫出相應(yīng)的存儲結(jié)構(gòu)和實(shí)現(xiàn)該要求的算法。35．寫出向存儲結(jié)構(gòu)為鄰接矩陣的無向圖G中插入一條邊(x，y)的算法。算法的頭函數(shù)為：void AddEdgetoGraph(Graph*G，VertexType X，VertexType y，無向圖G的存儲結(jié)構(gòu)為：
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1