數(shù)據(jù)結(jié)構(gòu)考試試題

1、數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題一數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題一一、簡(jiǎn)答問題：、簡(jiǎn)答問題：1四類數(shù)據(jù)結(jié)構(gòu)四類數(shù)據(jù)結(jié)構(gòu)2線性結(jié)構(gòu)與非線性結(jié)構(gòu)有何差別？線性結(jié)構(gòu)與非線性結(jié)構(gòu)有何差別？3簡(jiǎn)述算法的定義與特性。簡(jiǎn)述算法的定義與特性。4設(shè)有設(shè)有1000個(gè)無序元素，僅要求找出前個(gè)無序元素，僅要求找出前10個(gè)最小元素，在下列排序方法中（歸并排序、個(gè)最小元素，在下列排序方法中（歸并排序、基數(shù)排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？基數(shù)排序、快速排序、堆排序、插入

2、排序）哪一種方法最好，為什么？二、判斷正誤：（每小題二、判斷正誤：（每小題1分，共分，共5分）正確在（分）正確在（）內(nèi)打√，否則打）內(nèi)打√，否則打?。1（）二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：）二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點(diǎn)的值大于其左孩子的值，若它的左子樹非空，則根結(jié)點(diǎn)的值大于其左孩子的值，若它的右子樹非空，則根結(jié)點(diǎn)的值大于其右孩子的值。若它的右子樹非空，則根結(jié)點(diǎn)的值大于其右

3、孩子的值。2（）索引順序表的特點(diǎn)是塊內(nèi)可無序，塊間要有序。）索引順序表的特點(diǎn)是塊內(nèi)可無序，塊間要有序。3（）子串是主串中任意個(gè)連續(xù)字符組成的序列。）子串是主串中任意個(gè)連續(xù)字符組成的序列。4（）線性結(jié)構(gòu)只能用順序結(jié)構(gòu)存放，非線性結(jié)構(gòu)只能用鏈表存放。）線性結(jié)構(gòu)只能用順序結(jié)構(gòu)存放，非線性結(jié)構(gòu)只能用鏈表存放。5（）快速排序的樞軸元素可以任意選定。）快速排序的樞軸元素可以任意選定。三、單項(xiàng)選擇題：三、單項(xiàng)選擇題：(每小題每小題1分，共分，共4分)

4、1棧棧S最多能容納最多能容納4個(gè)元素?，F(xiàn)有個(gè)元素?，F(xiàn)有6個(gè)元素按個(gè)元素按A、B、C、D、E、F的順序進(jìn)棧的順序進(jìn)棧問下列問下列哪一個(gè)序列是可能的出棧序列哪一個(gè)序列是可能的出棧序列A)E、D、C、B、A、FB)B、C、E、F、A、DC)C、B、E、D、A、FD)A、D、F、E、B、C2將一棵有將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根

5、結(jié)點(diǎn)編號(hào)為號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)為，則編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為：的結(jié)點(diǎn)的左孩子的編號(hào)為：A、98B、99C、50D、483.對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是：對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是：A）21、25、5、17、9、23、30B）25、23、30、17、21、5、9B）21、9、17、30、25、23、5D）5、9、17、21、23、25、304.設(shè)森林設(shè)森林F中有三棵樹

6、，第一、第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3。與森。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是：對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是：A）M1B）M1M2C）M3D）M2M3四、填空題：四、填空題：(每小題每小題2分共2020分)1設(shè)一哈希表表長(zhǎng)設(shè)一哈希表表長(zhǎng)M為100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=KMODP（Pnext=和pne

7、xt=的操作的操作.8廣義表廣義表((ab)cd)的表頭是的表頭是表尾是表尾是9循環(huán)單鏈表循環(huán)單鏈表LA中，指針中，指針P所指結(jié)點(diǎn)為表尾結(jié)點(diǎn)的條件是所指結(jié)點(diǎn)為表尾結(jié)點(diǎn)的條件是10在一個(gè)待排序的序列中，只有很少量元素不在自己最終的正確位置上，但離他們的正在一個(gè)待排序的序列中，只有很少量元素不在自己最終的正確位置上，但離他們的正確位置都不遠(yuǎn)，則使用確位置都不遠(yuǎn)，則使用排序方法最好。排序方法最好。五、構(gòu)造題：（每小題五、構(gòu)造題：（每小題5分，

8、共分，共2525分）分）1已知一棵二叉樹，其中序序列已知一棵二叉樹，其中序序列DBCAFGE，后序序列，后序序列DCBGFEA，構(gòu)造該二叉樹。，構(gòu)造該二叉樹。2設(shè)哈希表長(zhǎng)度為設(shè)哈希表長(zhǎng)度為11，哈希函數(shù)，哈希函數(shù)H（K）=（K的第一字母在字母表中的序號(hào)）的第一字母在字母表中的序號(hào)）MOD11，若輸入順序?yàn)椋ǎ糨斎腠樞驗(yàn)椋―，BA，TN，M，CI，I，K，X，TA），處理沖突方法為線，處理沖突方法為線性探測(cè)再散列或鏈地址法，要求構(gòu)造哈希

9、表，并求出等概率情況下查找成功平均查找長(zhǎng)性探測(cè)再散列或鏈地址法，要求構(gòu)造哈希表，并求出等概率情況下查找成功平均查找長(zhǎng)《數(shù)據(jù)結(jié)構(gòu)》試卷參考答案《數(shù)據(jù)結(jié)構(gòu)》試卷參考答案一、簡(jiǎn)答問題：（每小題、簡(jiǎn)答問題：（每小題4分，共分，共16分）分）1集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)2線性結(jié)構(gòu)的前驅(qū)與后繼之間為一對(duì)一關(guān)系，非線性結(jié)構(gòu)的前驅(qū)與后繼之間通常線性結(jié)構(gòu)的前驅(qū)與后繼之間為一對(duì)一關(guān)系，非線性結(jié)構(gòu)的前驅(qū)與后繼

10、之間通常為一對(duì)多或多對(duì)多關(guān)系。為一對(duì)多或多對(duì)多關(guān)系。3解決特定問題的有限指令序列。有限性、確定性、可行性、有解決特定問題的有限指令序列。有限性、確定性、可行性、有0個(gè)或多個(gè)輸入個(gè)或多個(gè)輸入數(shù)據(jù)、有數(shù)據(jù)、有1個(gè)或多個(gè)輸出結(jié)果。個(gè)或多個(gè)輸出結(jié)果。4堆排序。因?yàn)橐惶硕雅判蚺哦ㄒ粋€(gè)元素，只需進(jìn)行前堆排序。因?yàn)橐惶硕雅判蚺哦ㄒ粋€(gè)元素，只需進(jìn)行前10趟堆排序就可以了。趟堆排序就可以了。其它排序方法均需進(jìn)行完全排序。其它排序方法均需進(jìn)行完全排序。二、

11、判斷正誤：（每小題二、判斷正誤：（每小題1分，共分，共5分）分）正確在（正確在（）內(nèi)打√，否則打）內(nèi)打√，否則打?。1.（?）2.（√）（√）3.（√）（√）4.（?）5.（√）（√）三、單項(xiàng)選擇題：三、單項(xiàng)選擇題：(每小題每小題1分，共分，共4分)1C)2A)3.A)4.D)四、填空題：四、填空題：(每小題每小題2分共20分)1972.n13.鏈域數(shù)目不同鏈域數(shù)目不同4.哈希查找法哈希查找法5.26–16.11687.pnext、s8