02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2016年份真題及答案

1、2016年10月高等教育自學(xué)考試全國(guó)統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試卷試卷(課程代碼02142)本試卷共本試卷共4頁(yè)，滿分頁(yè)，滿分l00l00分，考試時(shí)間分，考試時(shí)間l50l50分鐘。分鐘?？忌痤}注意事項(xiàng)：考生答題注意事項(xiàng)：1本卷所有試題必須在答題卡上作答。答在試卷上無效，試卷空白處和背面均可作草稿紙。本卷所有試題必須在答題卡上作答。答在試卷上無效，試卷空白處和背面均可作草稿紙。2第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用第一部

2、分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B2B鉛筆將鉛筆將“答題卡答題卡”的相應(yīng)代碼涂黑。的相應(yīng)代碼涂黑。3第二部分為非選擇題。必須注明大、小題號(hào)，使用第二部分為非選擇題。必須注明大、小題號(hào)，使用05毫米黑色字跡簽字筆作答。毫米黑色字跡簽字筆作答。4合理安排答題空間。超出答題區(qū)域無效。合理安排答題空間。超出答題區(qū)域無效。第一部分第一部分選擇題選擇題(共3030分)一、單項(xiàng)選擇題一、單項(xiàng)選擇題(本大題共本大題共1010小題，每小題小題，每小

3、題2分，共分，共3030分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡答題卡”的相應(yīng)代碼涂黑。錯(cuò)涂、的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無分。多涂或未涂均無分。1已知問題規(guī)模為n，則下列程序片段的時(shí)間復(fù)雜度是C2若用計(jì)算機(jī)來模擬銀行客戶排隊(duì)等待辦理業(yè)務(wù)的情形，則所應(yīng)該采用的數(shù)據(jù)結(jié)構(gòu)是A棧B隊(duì)列C樹D圖3若線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則適用的查找方

4、法為A隨機(jī)查找B散列查找C二分查找D順序查找4已知指針P和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)，假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在S所指結(jié)點(diǎn)之后插入上述單鏈表應(yīng)執(zhí)行的語(yǔ)句為Aq→next；s→next；s→next2P；Bs→next=P；q→next=s→next；Cp→next=s→next；s→next=q；Ds→next2q；p→next2s→next；5棧的運(yùn)算特點(diǎn)是先進(jìn)后出，元素a、b、c、d依次入棧，則不能

5、得到的出棧序列是AabedBdcbaCcabdDbcda6在實(shí)現(xiàn)隊(duì)列的鏈表結(jié)構(gòu)中，其時(shí)間復(fù)雜度最優(yōu)的是A僅設(shè)置頭指針的單循環(huán)鏈表B僅設(shè)置尾指針的單循環(huán)鏈表C僅設(shè)置頭指針的雙向鏈表D僅設(shè)置尾指針的雙向鏈表7任意一棵二叉樹的前序和后序遍歷的結(jié)果序列中，各葉子結(jié)點(diǎn)之間的相對(duì)次序關(guān)系是A不一定相同B.都相同C都不相同D互為逆序8若某棵樹的存儲(chǔ)結(jié)構(gòu)采用雙親表示法，如題8圖所示，則該樹的高度是擇題擇題(共7070分)二、填空題二、填空題(本大題共本

6、大題共l3l3小題，每小題小題，每小題2分，共分，共2626分)16從宏觀上看，數(shù)據(jù)、數(shù)據(jù)元素和__數(shù)據(jù)項(xiàng)___反映了數(shù)據(jù)組織的三個(gè)層次。17在表長(zhǎng)為n的順序表中插入或刪除一個(gè)元素，則需移動(dòng)元素的具體個(gè)數(shù)與表長(zhǎng)和_元素位置_有關(guān)。18非空的單循環(huán)鏈表的頭指針為head，尾指針為rear，則rear一next=___head____。19設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列的元素，變量rear和queuelen分別表示循環(huán)隊(duì)列中隊(duì)尾元素的下標(biāo)位置

7、和元素的個(gè)數(shù)。則計(jì)算該隊(duì)列中隊(duì)頭元素下標(biāo)位置的公式是__(rear–queuelenm)%m___。20二維數(shù)組A[8][9]按行優(yōu)先順序存儲(chǔ)，若數(shù)組元素A[2][3]的存儲(chǔ)地址為l087，A[4][7]的存儲(chǔ)地址為ll53，則每個(gè)數(shù)組元素占用的存儲(chǔ)單元的個(gè)數(shù)是___3_____。21設(shè)一個(gè)完全二叉樹共含有196個(gè)結(jié)點(diǎn)，則該完全二叉樹中含有葉結(jié)點(diǎn)的個(gè)數(shù)是___98_____。22假設(shè)高度為h二叉樹中只有度為2和度為0這兩種類型的結(jié)點(diǎn)，則

8、該類二叉樹中結(jié)點(diǎn)個(gè)數(shù)至多為2h1、至少為__3______。23若以數(shù)據(jù)集34，5，12，23，8，18為葉結(jié)點(diǎn)的權(quán)值構(gòu)造一棵哈夫曼(HUffman)樹，那么該Huffman樹的帶權(quán)路徑長(zhǎng)度WPL_238_____。24設(shè)有散列函數(shù)H(k)和鍵值，則這種現(xiàn)象稱為“沖突”，且稱鍵值k1和k2互為__同義詞____。25一個(gè)圖的最小生成樹是滿足一定條件的生成樹，即一個(gè)圖的最小生成樹是指該圖的所有生成樹中__權(quán)值之和最小____的生成樹。26

9、對(duì)長(zhǎng)度為n的有序順序表進(jìn)行二分查找，則查找表中的任意一個(gè)元素時(shí)，無論查找成功與失敗，最多與表中__longN_1___個(gè)元素進(jìn)行比較。27排序方法中，從未排序序列中依次取出元素與已排序序列(初始時(shí)為空)中的元素按序進(jìn)行比較，將其插入已排序序列的正確位置上的方法稱為__直接插入排序____。28一般情況下，時(shí)闖復(fù)雜度是O(nl0g2n)且其空間復(fù)雜度最優(yōu)的排序方法是___堆排序___。三、應(yīng)用題三、應(yīng)用題(本大題共本大題共5小題，每小題小

10、題，每小題6分，共分，共3030分)29借助于隊(duì)列能夠?qū)⒑衝個(gè)數(shù)據(jù)元素的棧逆置，比如棧S中的元素為a，b，C逆置后變成C，b，a。試簡(jiǎn)述你的解決方案。30為便于表示二叉樹的某些基本運(yùn)算，則深度為k的二叉樹的順序存儲(chǔ)結(jié)構(gòu)中的數(shù)組的大小為多少畫出如題30圖所示的二叉樹的順序存儲(chǔ)結(jié)構(gòu)示意圖，并說明對(duì)一般形態(tài)的二叉樹不太適合使用順序存儲(chǔ)結(jié)構(gòu)來表示的原因。31先序遍歷、中序遍歷一個(gè)森林分別等同于先序、中序遍歷該森林所對(duì)應(yīng)的二叉樹?，F(xiàn)已知一個(gè)森林

11、的先序序列和中序序列分別為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ì)算等概率情況下在該二叉排序樹上查找成功的平均查找長(zhǎng)度ASL。33若采用二路歸并排序方法對(duì)關(guān)鍵字序列25，9，78，6，65，15，58，18，45，20進(jìn)行升序排序，寫出其每趟排序結(jié)束后的關(guān)鍵字序列。四、