數(shù)據(jù)結(jié)構(gòu)2011年1月答案

1、本套試題共分10頁(yè)，當(dāng)前頁(yè)是第1頁(yè)全國(guó)全國(guó)20112011年1月高等教育自學(xué)考試月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題數(shù)據(jù)結(jié)構(gòu)試題課程代碼：課程代碼：0233102331一、單項(xiàng)選擇題（本大題共一、單項(xiàng)選擇題（本大題共15小題，每小題小題，每小題2分，共分，共30分）分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)

2、。錯(cuò)選、多選或未選均無(wú)分。選均無(wú)分。1.下列選項(xiàng)中與數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（）A.順序表B.鏈表C.鏈隊(duì)列D.棧2.將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，最少的比較次數(shù)是（）A.n1B.nC.2n1D.2n3.已知循環(huán)隊(duì)列的存儲(chǔ)空間大小為m，隊(duì)頭指針front指向隊(duì)頭元素，隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置，則向隊(duì)列中插入新元素時(shí)，修改指針的操作是（）A.rear=(rear1)%mB.front=(front1)%mC.

3、front=(front1)%mD.rear=(rear1)%m4.遞歸實(shí)現(xiàn)或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，應(yīng)采用的數(shù)據(jù)結(jié)構(gòu)是（）？？？？A.堆棧B.多維數(shù)組多維數(shù)組C.隊(duì)列D.線(xiàn)性表5.設(shè)有兩個(gè)串p和q，其中q是p的子串，則求q在p中首次出現(xiàn)位置的算法稱(chēng)為（）p55A.求子串B.串聯(lián)接C.串匹配串匹配D.求串長(zhǎng)6.對(duì)于廣義表A，若head(A)等于tail(A)，則表A為（）p66A.()B.(())C.(()())D.(()()(

4、))7.若一棵具有n(n0)個(gè)結(jié)點(diǎn)的二叉樹(shù)的先序序列與后序序列正好相反，則該二叉樹(shù)一定是（）A.結(jié)點(diǎn)均無(wú)左孩子的二叉樹(shù)B.結(jié)點(diǎn)均無(wú)右孩子的二叉樹(shù)C.高度為高度為n的二叉樹(shù)的二叉樹(shù)D.存在度為2的結(jié)點(diǎn)的二叉樹(shù)8.若一棵二叉樹(shù)中度為l的結(jié)點(diǎn)個(gè)數(shù)是3，度為2的結(jié)點(diǎn)個(gè)數(shù)是4，則該二叉樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)是（）p73A.4B.5C.7D.89.下列敘述中錯(cuò)誤的是（）108A.圖的遍歷是從給定的源點(diǎn)出發(fā)對(duì)每一個(gè)頂點(diǎn)訪(fǎng)問(wèn)且僅訪(fǎng)問(wèn)一次107B.圖的遍歷可以

5、采用深度優(yōu)先遍歷和廣度優(yōu)先遍歷108C.圖的廣度優(yōu)先遍歷只適用于無(wú)向圖圖的廣度優(yōu)先遍歷只適用于無(wú)向圖D.圖的深度優(yōu)先遍歷是一個(gè)遞歸過(guò)程108本套試題共分10頁(yè)，當(dāng)前頁(yè)是第3頁(yè)23.當(dāng)待排關(guān)鍵字序列基本有序時(shí)，快速排序、簡(jiǎn)單選擇排序和直接插入排序三種排序方法中，運(yùn)行效率最高的是________________。直接插入排序24.在一棵深度為h的具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中，查找任一結(jié)點(diǎn)的最多比較次數(shù)是______________。h25.不

6、定長(zhǎng)文件指的是文件的____________大小不固定。記錄的信息p207三、解答題（本大題共三、解答題（本大題共4小題，每小題小題，每小題5分，共分，共20分）分）26.已知一棵二叉排序樹(shù)（結(jié)點(diǎn)值大小按字母順序）的前序遍歷序列為EBACDFHG，請(qǐng)回答下列問(wèn)題：(1)畫(huà)出此二叉排序樹(shù)；前序遍歷序列:EBACDFHG中序遍歷序列:ABCDEFGHEBHACDFG(2)若將此二叉排序樹(shù)看作森林的二叉鏈表存儲(chǔ)，請(qǐng)畫(huà)出對(duì)應(yīng)的森林。?抹線(xiàn)：將二