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

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

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

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

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

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

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