1、2022學(xué)年9月份考試數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題一、單項(xiàng)選擇題1、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）oA、存儲(chǔ)結(jié)構(gòu)B、物理結(jié)構(gòu)C、邏輯結(jié)構(gòu)D、物理和存儲(chǔ)結(jié)構(gòu)正確答案：C2、在以下排序方法中，關(guān)鍵字比擬的次數(shù)與記錄的初始排列秩序無(wú)關(guān)的是（）oA、希爾排序B、冒泡排序C、插入排序D、選擇排序正確答案：D3、在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直 接后繼，現(xiàn)耍刪除q所指結(jié)點(diǎn)，可用語(yǔ)句（）op=q-nextp-next=qp-next=q-nextq-next=NULL正確答案：C4、一個(gè)有序表為11,22,33,44,55,66,77,88,99,那么順序查找

2、元素55需要比擬（）次。34C、5D、 6正確答案：C5、從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比擬。將其放入已排序序列的正確的位置上，此方法稱為（）A、插入排序B、選擇排序C、交換排序D、歸并排序正確答案：A6、圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。A、先序B、中序C、后序D、層次正確答案：A7、二叉樹第k層上最多有（）個(gè)結(jié)點(diǎn)。2kC、-1D、2正確答案：B8、常對(duì)數(shù)組進(jìn)行的兩種基本操作是（）oA、建立與刪除B、索引和修改C、查找和修改D、查找與索引正確答案：C9、假設(shè)串S= English”，其子串的個(gè)數(shù)是（）o916C、36D、 28正確答案：D10、一個(gè)隊(duì)列的入隊(duì)

3、順序是a,b,c,d,那么離隊(duì)的順序是（）oa,d,c,ba,b,c,dd,c,b,ac,b,dza正確答案：B11、設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為（）on-i+1n-in-i-1i正確答案：B12、順序查找方法適合于存儲(chǔ)結(jié)構(gòu)為（）的線性表。A、散列存儲(chǔ)B、索引存儲(chǔ)C、散列存儲(chǔ)或索引存儲(chǔ)D、順序存儲(chǔ)或鏈接存儲(chǔ)正確答案：D13、利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子的 最長(zhǎng)帶權(quán)路徑長(zhǎng)度為（）o1816C、12D、 30正確答案：A14、設(shè)某一二叉樹先序遍歷為abdec,中序遍歷為dbeac,那么該二叉樹后序遍歷的順序是（）。A、

4、 abdecdebacC、 debcaD、 abedc正確答案：C15、以下有關(guān)二叉樹的說法正確的選項(xiàng)是（）oA、二叉樹中度為0的結(jié)點(diǎn)的個(gè)數(shù)等于度為2的結(jié)點(diǎn)的個(gè)數(shù)加1B、二叉樹中結(jié)點(diǎn)個(gè)數(shù)必大于0C、完全二叉樹中，任何一個(gè)結(jié)點(diǎn)的度，或者為0或者為2D、二叉樹的度是2正確答案：A16、算法的時(shí)間復(fù)雜度與（）有關(guān)。A、所使用的計(jì)算機(jī)B、計(jì)算機(jī)的操作系統(tǒng)C、算法本身D、數(shù)據(jù)結(jié)構(gòu)正確答案：C17、算法分析的目的是（）。A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出的關(guān)系C、分析算法的效率以求改進(jìn)分析算法的易懂性和文檔性D、分析算法的易懂性和文檔性正確答案：C18、鏈表不具有的特點(diǎn)是（ ）oA、可隨機(jī)

5、訪問任一元素B、插入刪除不需要移動(dòng)元素C、不必事先估計(jì)存儲(chǔ)空間D、所需空間與線性表長(zhǎng)度成正比正確答案：A19、在圖的存儲(chǔ)結(jié)構(gòu)表示中，表示形式唯一的是（）oA、nB、n+1C、n-1D、n/2正確答案：C20、對(duì)于順序存儲(chǔ)的有序表5, 12, 20, 26, 37, 42, 46, 50, 64）,假設(shè)采用折半查找，那么查找元素26的比擬次數(shù)是（ ）oA、2B、3C、4D、5正確答案：C21、以下陳述中正確的選項(xiàng)是（）oA、串是一種特殊的線性表B、串的長(zhǎng)度必須大于零C、串中元素只能是字母D、空串就是空白串答案：A22、設(shè)有兩個(gè)串p和q,其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（）。 A

6、、求子串B、連接C、匹配D、求串長(zhǎng)答案：C23串是（）oA、不少于一個(gè)字母的序列B、任意個(gè)字母的序列C、不少于一個(gè)字符的序列D、有限個(gè)字符的序列答案：D解析：24、串的長(zhǎng)度是指（）A、串中所含不同字母的個(gè)數(shù)B、串中所含字符的個(gè)數(shù)C、串中所含不同字符的個(gè)數(shù)D、串中所含非空格字符的個(gè)數(shù)答案：B25、兩個(gè)字符串相等的條件是（）oA、兩串的長(zhǎng)度相等B、兩串包含的字符相同C、兩串的長(zhǎng)度相等，并且兩串包含的字符相同D、兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同答案：D二、填空題1、樹中度大于。的結(jié)點(diǎn)稱作或 。正確答案：第1空：分支結(jié)點(diǎn)第2空：非終端結(jié)點(diǎn)2、哈夫曼樹又稱為正確答案：第1空：最優(yōu)二叉樹3、在一棵

7、樹中，每個(gè)結(jié)點(diǎn)的子樹的根或者說每個(gè)結(jié)點(diǎn)的稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)，簡(jiǎn)稱為孩子。正確答案：第1空：后繼結(jié)點(diǎn)4、樹中度等于。的結(jié)點(diǎn)稱作或 。正確答案：第1空：葉子結(jié)點(diǎn)第2空：終端結(jié)點(diǎn)5、圖常用的兩種存儲(chǔ)結(jié)構(gòu)是和 。正確答案：第1空：鄰接矩陣第2空：鄰接表6、在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針 ，當(dāng)刪除一個(gè)元 素隊(duì)列時(shí)，頭指針 。正確答案：第1空：增1第2空：增17、在對(duì)一組記錄(50, 40, 95, 20, 15, 70, 60, 45, 80)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需要比擬次。正確答案：第1空：38、關(guān)鍵字是記錄某個(gè)，用它可以識(shí)別

8、、確定一個(gè)記錄。正確答案：第1空：數(shù)據(jù)項(xiàng)的值9、具有m個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有結(jié)點(diǎn)。正確答案：第1空：2m-l10、串是一種特殊的線性表，其特殊性表現(xiàn)在組成串的數(shù)據(jù)元素都是。正確答案：第1空：字符11、在一個(gè)單向鏈表中，要?jiǎng)h除p所指結(jié)點(diǎn)，q指向p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。那么可以 用操作o正確答案：第1空：q-next=p-next12、冒泡排序是一種比擬簡(jiǎn)單的方法。正確答案：第1空：交換排序13、單向循環(huán)鏈表是單向鏈表的一種擴(kuò)充，當(dāng)單向鏈表帶有頭結(jié)點(diǎn)時(shí)，把單向鏈表中尾結(jié)點(diǎn) 的指針域由空指針改為 ；當(dāng)單向鏈表不帶頭結(jié)點(diǎn)時(shí)，那么把單向鏈表中尾結(jié)點(diǎn)的指針域由 空指針改為指向 。正確答案：第1空：頭結(jié)點(diǎn)的

9、指針第2空：指向第一個(gè)結(jié)點(diǎn)的指針14、在圖中，任何兩個(gè)數(shù)據(jù)元素之間都可能存在關(guān)系，因此圖的數(shù)據(jù)元素之間是一種 的 關(guān)系正確答案：第1空：多對(duì)多15、數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為結(jié)構(gòu)。正確答案：第1空：圖狀結(jié)構(gòu);圖結(jié)構(gòu)16、分塊查找又稱為，它是一種介于順序查找和折半查找之間的查找方法。正確答案：第一空：索引順序查找17、在有序表A1.18中，采用二分查找算法查找元素值等于A17的元素，所比擬過的元 素的下標(biāo)依次是。正確答案：第一空：9, 14, 16 , 1718、棧是限定在表的一端進(jìn)行插入和刪除操作的線性表，又稱為 。正確答案：第一空：后進(jìn)先出表19、在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入

10、一個(gè)新的隊(duì)列元素時(shí)，尾指針 ，當(dāng)刪除一個(gè)元素 隊(duì)列時(shí)，頭指針 。正確答案：第一空：增1第二空：增120、廣義表 A (a,b,c) ,(d,e,f)的表尾為。正確答案：第一空：(d,e,f)三、簡(jiǎn)答題1、編寫順序查找算法。順序查找算法如下：int search(NODE a,int n, int k)/*在a0an-l中順序查找關(guān)鍵字等于k的記錄。查找成功時(shí)返回該記錄的下標(biāo)，失敗時(shí)返回-1*/)正確答案：順序查找算法如下：int search(NODE a,int n, int k)/*在a0an-l中順序查找關(guān)鍵字等于k的記錄。查找成功時(shí)返回該記錄的下標(biāo)，失敗時(shí) 返回-1*/(int i=0;while(idata=X) return 1; /*根結(jié)點(diǎn)的層號(hào)為 1*/*向子樹中查找X結(jié)點(diǎn)*/else int cl=NodeLevel(BT-left,X);if(cl=l)(1)；int c2=;if ；假設(shè)樹中不存在X結(jié)點(diǎn)那么返回0else return 0;)正確答案：第一空：return cl+1第二空：NodeLevel(BT-right,X)第三空：(c2=l) return c2+l2、閱讀下面算法，在劃線處填入正確的代碼內(nèi)容int write(LinkQueue *q)QueueNode *p;if (q-front=q-rear)/* 隊(duì)空*/pr