全國(guó)2014年10月自考全國(guó)數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

1、2014年10月自考全國(guó)數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題全國(guó)2014年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼:02U2請(qǐng)考生按規(guī)定用筆將所有試題的答秦涂、寫(xiě)在答題紙上。選擇題部分注意事項(xiàng)：L答題前苦生務(wù)必將門(mén)己的琴試課程玄稱、姓需、準(zhǔn)萼證號(hào)用黑色字跡的簽字筆或鋼舉 填嗎在答題妖規(guī)定的位置上，2.毎小題選岀答案站JH2B鉛筆把答題紙上對(duì)應(yīng)題目的答案標(biāo)號(hào)涂黑二如需改動(dòng)用橡 度擦干浄后.再選涂苴他答案標(biāo)號(hào)不能答在試題雅上，一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共別分)在每小題列出的四亍備選項(xiàng)中只有一個(gè)是符合題目要求的青將其選出并將“答題紙初的相 應(yīng)代碼涂黑。措涂、多涂或未涂均無(wú)分。1+下列算法的時(shí)間

2、星親度為for i=l jiprior = p；i nexi = pnexi ；pnexi prior= i j:。1&線性表中所含結(jié)點(diǎn)的個(gè)數(shù)稱為。19. 在帶冇頭結(jié)點(diǎn)的循環(huán)鏈表中頭指針為head.判斷p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是20. 鏈棧IE中.15next指向棧頂結(jié)點(diǎn)則新結(jié)點(diǎn)* p入棧的操作為:pnext = I5next ；和21. 為了節(jié)省存儲(chǔ)空間將矩陣中多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間零元素不存儲(chǔ).這種存儲(chǔ)方式通常禰為矩陣的022. 100個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表存儲(chǔ)時(shí)空指針域NU1.冇個(gè)。23. 已知完全二叉樹(shù)的第5層冇5個(gè)結(jié)點(diǎn)則整個(gè)完全二叉樹(shù)冇個(gè)葉結(jié)點(diǎn)。24. 一個(gè)樹(shù)的最少結(jié)

3、點(diǎn)個(gè)數(shù)為。25. 索引順序表由兩部分組成：一個(gè)是順序表另一個(gè)是826. 二叉排序樹(shù)上的平均查找長(zhǎng)度介于和（）（n）之間。27. 二分査找算法的時(shí)間復(fù)雜度是,28. 最好情況下冒泡排序算法的時(shí)間復(fù)雜度為它是一種穩(wěn)定的排序方法。三、應(yīng)用題（本大題共5小題，每小題6分，共3（）分）29. 如題29圖所示在棧的輸入端元素的輸入順序?yàn)锳.5.8.試寫(xiě)出在棧的輸出端町以得到的以數(shù)字開(kāi)頭的聽(tīng)冇輸出序列并寫(xiě)出進(jìn)棧、.!棧的操作過(guò)程（用Push（ x）表示x進(jìn)棧pop （x）表示x出校）。A58站山端輸入端棧題29圖30分別寫(xiě)出題30圖所示二叉樹(shù)的先序遍歷.中序遍歷和后序遍歷的結(jié)點(diǎn)序列。題30圖31. 寫(xiě)出題3

4、1圖所示冇向圖頂點(diǎn)的所冇拓?fù)渑判蛐蛄?。題31圖32. 將題32圖所示的一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)。題32圖33. 判斷序列（28.75,33.6&25,56,47,99,86.36）是否為堆?如果不是則把它調(diào)整為堆（最小堆）.浙0214數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第4頁(yè)（共5頁(yè)）四、算法設(shè)計(jì)題（本大題共2小題，每小題7分，共14分）34. 單鏈表的結(jié)構(gòu)定義如下：typedef struct nodeint data：struct node * next; Node. * LinkList:試編寫(xiě)算法ini CountLinklist （LinkList headint x）實(shí)現(xiàn)在帶頭結(jié)點(diǎn)的單鏈表head中計(jì)算 值為X的結(jié)點(diǎn)數(shù)。35. 假設(shè)線性表中結(jié)點(diǎn)是按鍵值遞增的順序排列試編寫(xiě)一個(gè)順