“數(shù)據(jù)結(jié)構(gòu)”復(fù)習(xí)題

1、選擇題： A. 便于隨機(jī)存取 B. 便于元素的插入和刪除操作C. 存儲(chǔ)的密度較高 D. 元素的物理順序與邏輯順序一致，（ 3、在長度為n 的順序表中，向第k 個(gè)元素（1kn+1）之前插入一個(gè)新元素時(shí)，需向后移 A. 入棧操作更加方便 B. 出棧操作更加方便C. 通常不會(huì)出現(xiàn)棧滿 D. 通常不會(huì)出現(xiàn)?？?8、在一個(gè)單鏈表中，若要?jiǎng)h除指針p 所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則需執(zhí)行（ A ）中的語句。 ，（ 表示隊(duì)尾元素的所在位置，則計(jì)算隊(duì)列中元素個(gè)數(shù)的表達(dá)式為（ D ）。A. r-f B. (m-f-r) %m 15、設(shè)二叉樹中任一結(jié)點(diǎn)的值大于其左子樹中每個(gè)結(jié)點(diǎn)的值，而小于其右子樹中每個(gè)結(jié)點(diǎn)的 值，即它是

2、一個(gè)二叉排序樹。則中序遍歷該二叉樹時(shí)，訪問結(jié)點(diǎn)的序列是一個(gè)值（B ）的序 A. 遞減 B. 遞增C. 先遞減后遞增 D. 先遞增后遞減16、以順序存儲(chǔ)方式將完全二叉樹中的所有結(jié)點(diǎn)逐層存放于數(shù)組A 中，結(jié)點(diǎn)Ai若有左孩子， A. A2*i B. A2*i+1 C.A2*i+2 D. Ai/2 ，（ A. 雙親表示法 B. 孩子鏈表表示法C. 孩子兄弟表示法 D. 順序存儲(chǔ)表示法19、某二叉樹如圖所示，對該二叉樹進(jìn)行中序遍歷，結(jié)點(diǎn)的訪問序列為 。 20、某二叉樹如圖所示，對該二叉樹進(jìn)行 先序遍歷的結(jié)點(diǎn)序列為 。 knkn22、對于一個(gè)具有n 個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣中元素的個(gè)數(shù)為 。

3、A.n 23、對圖所示的無向圖G，從頂點(diǎn)開始，廣度優(yōu)先遍歷，可能的頂點(diǎn)訪問順序?yàn)?。 24、對上一題的圖G，從頂點(diǎn)開始，深度優(yōu)先遍歷，則可能的頂點(diǎn)訪問順序?yàn)?。 A. AiiA. Aiii0 i0 26、采用順序檢索的方法檢索長度為 n 的順序表，檢索每個(gè)元素的平均比較次數(shù)（即平均檢 28、哈希檢索的基本思想是依據(jù)關(guān)鍵字值的簡單換算來決定 。A. 記錄的存儲(chǔ)地址 B. 記錄的序號 2222 31、用直接插入排序法對下面 4 個(gè)序列進(jìn)行遞增（由小到大）排序，元素比較次數(shù)和移動(dòng)次 分割之后序列的次序是 。 33、以下排序算法中，時(shí)間復(fù)雜度最高的是 。A. 希爾排序 B. 歸并排序 C. 快速排序

4、D. 堆排序34、以下排序算法中，需要附加的內(nèi)存空間最大的是 。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序 6對n 個(gè)記錄的集合進(jìn)行快速排序，所需的平均時(shí)間是O(nlog n)。 2 （） 14當(dāng)待排序的數(shù)據(jù)元素個(gè)數(shù)很大時(shí)，為交換元素的位置，移動(dòng)元素將耗用較多的時(shí)間，這 可能相等 （） 1在一個(gè)單鏈表中，在指針p 所指結(jié)點(diǎn)之后插入指針s 所指結(jié)點(diǎn)，應(yīng)執(zhí)行 4對于n 個(gè)頂點(diǎn)e 條邊的無向圖，其鄰接表中有 n 個(gè)頂點(diǎn)。5n 個(gè)結(jié)點(diǎn)的循環(huán)隊(duì)列的頭指針front 指示隊(duì)頭的下標(biāo)，尾指針rear 指向隊(duì)尾之后的下標(biāo)，則 孩子兄弟鏈表表示法 。 12設(shè)有二維數(shù)組A919，其每個(gè)元素占用

5、一個(gè)內(nèi)存單元，數(shù)組以列為主序存儲(chǔ)，第一個(gè)元 根序 。16遍歷圖的鄰接矩陣第i 行可以統(tǒng)計(jì)第i 個(gè)頂點(diǎn)的 出 度，遍歷第i 列可以統(tǒng)計(jì)第i 個(gè)頂 17 散列表 檢索方法的平均檢索長度與記錄的個(gè)數(shù)n 無關(guān)。18棧中的最后一個(gè)數(shù)據(jù)元素稱為 棧頂 ，隊(duì)列中的第一個(gè)數(shù)據(jù)元素稱為 隊(duì) 19將鍵值較大的記錄向序列的尾部移動(dòng)，鍵值較小的記錄向序列的前部移動(dòng)的排序方法稱 1試分別畫出下面二叉樹的二叉鏈表和靜態(tài)二叉鏈表。2有向圖G 如圖所示，頂點(diǎn)的次序依次為A,B, C,D,E，試寫出該圖的鄰接矩陣和鄰接表。 其在表中的次序依次插入到一棵初始為空的二叉排序樹中，畫出插入完成后的二叉排序樹， 并計(jì)算在等概率的情形下

6、，在該二叉排序樹上成功檢索的平均檢索長度。 4已知一棵二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDAHGF，試畫出該 010101 從頂點(diǎn)a 出發(fā)，采用深度優(yōu)先搜索，畫出所得該圖 從頂點(diǎn)a 出發(fā)，采用廣度深度優(yōu)先搜索，畫出該圖的廣度優(yōu)先生成樹； 采用Prim 算法，畫出其求解最小生成樹的每一步驟； 采用Kruscal算法，畫出其求解最小生成樹的每一步驟。 1有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，已知指向頭結(jié)點(diǎn)的指針hp，試寫出在元素值為a 的結(jié)點(diǎn)（假設(shè) 該結(jié)點(diǎn)存在）之后插入元素值為b 的結(jié)點(diǎn)（該結(jié)點(diǎn)未建立）的算法過程。結(jié)點(diǎn)類型node 已經(jīng) 定義，含有存放元素的data 域（elemtp類型）和指向后繼結(jié)點(diǎn)的指針域next。 2以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫出求二叉樹中葉子結(jié)點(diǎn)數(shù)的算法的遞歸函數(shù)。 結(jié)點(diǎn)，并返回新結(jié)點(diǎn)的地址）算法的函數(shù)。設(shè)同義詞單鏈表結(jié)點(diǎn)的數(shù)據(jù)類型定義如下： 5有一個(gè)不帶頭結(jié)點(diǎn)的單鏈表，指向第一元素結(jié)點(diǎn)的指針為hp，試編寫計(jì)算單鏈表長度（結(jié) 點(diǎn)個(gè)數(shù)）算法函數(shù)。假