數(shù)據(jù)結(jié)構(gòu)導(dǎo)論摹擬試題一、考試題型及分值分布：、單項(xiàng)選擇題本大題共小題，每小題分，共分、填空題本大題共小題，每小題分，共分、應(yīng)用題本大題共小題，每小題分，共分、算法設(shè)計(jì)題本大題共小題，每小題分，共分二、單項(xiàng)選擇題和填空題樣題參考（一）單項(xiàng)選擇題在二維數(shù)組中，每一個(gè)數(shù)組元素同時(shí)處于（）個(gè)向量中。它們分別由表頭指針?biāo)赶颍魧⒁阎獑捂湵黹L(zhǎng)度為，單鏈表長(zhǎng)度為，整體連接到的末尾，其時(shí)間復(fù)雜度應(yīng)為（）o它們分別由表頭指針?biāo)赶?，若將假定一個(gè)鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為和，則判斷隊(duì)空的條件為假定一個(gè)鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為和，則判斷隊(duì)空的條件為若讓元素 挨次進(jìn)棧，則出棧次序不可能浮現(xiàn)種情況。圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的（）遍歷。先根 中根 后根 層次下面程序段的時(shí)間復(fù)雜度為 。設(shè)有兩個(gè)串和，求在中首次浮現(xiàn)的位置的運(yùn)算叫做（）o求子串 模式匹配 串替換 串聯(lián)接利用雙向鏈表作線性表的存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是（）o便于單向進(jìn)行插入和刪除的操作節(jié)省空間設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（ ）,便于單向進(jìn)行插入和刪除的操作節(jié)省空間設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（ ）,的棧頂插入一個(gè)由指針?biāo)傅慕Y(jié)點(diǎn)，則應(yīng)執(zhí)行便于雙向進(jìn)行插入和刪除的操作便于銷(xiāo)毀結(jié)構(gòu)釋放空間且 是指向棧頂?shù)闹羔?。若想在鏈?zhǔn)綏２僮?。一棵具有個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)的高度為O一棵具有個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)的高度為O假定空樹(shù)的高度為。一個(gè)有個(gè)頂點(diǎn)和條邊的無(wú)向圖一定是 的。.連通.不連通.無(wú)回路.有回路在一個(gè)長(zhǎng)度為的順序表的任一位置插入一個(gè)新元素的時(shí)間復(fù)雜度為（）。已知廣義表為,從中取出原子的運(yùn)算是（已知廣義表為,從中取出原子的運(yùn)算是（）o在一棵樹(shù)的靜態(tài)雙親表示中，每一個(gè)存儲(chǔ)結(jié)點(diǎn)包含 個(gè)域。有向圖中的一個(gè)頂點(diǎn)的度數(shù)等于該頂點(diǎn)的 。?入度 ?出度.入度與出度之和 .入度出度2與鄰接矩陣相比，鄰接表更適合于存儲(chǔ) 。?無(wú)向圖.連通圖?稀疏圖.稠密圖較快的數(shù)據(jù)搜索方法是（）搜索方法。順序 折半 單鏈散列在閉散列表中，散列到同一個(gè)地址而引起的“堆積”問(wèn)題是由于（）引起的。同義詞之間發(fā)生沖突 非同義詞之間發(fā)生沖突同義詞之偶爾非同義詞之間發(fā)生沖突 散列表“溢出”根據(jù)個(gè)元素建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度為（）o假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為 和，則判斷隊(duì)空的條件為 。假定一棵二叉樹(shù)的第層上有個(gè)結(jié)點(diǎn)，則第 層上最多有 個(gè)結(jié)點(diǎn)。對(duì)于具有條邊的無(wú)向圖，它的鄰接表中共有 個(gè)邊結(jié)點(diǎn)。????圖的深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的（）次序遍歷。先根 中根 后根 層次.棧最多能容納個(gè)元素?，F(xiàn)有個(gè)元素按的順序進(jìn)棧問(wèn)下列哪一個(gè)序列是可能的出棧序列.將一棵有 個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)從根這一層開(kāi)始，每一層從左到右挨次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為，則編號(hào)為的結(jié)點(diǎn)的左孩子的編號(hào)為：對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是：.對(duì)于只在表的首、尾進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為順序表 用頭指針表示的單循環(huán)鏈表用尾指針表示的單循環(huán)鏈表 單鏈表.假設(shè)以第一個(gè)元素為分界元素，對(duì)字符序列（）進(jìn)行快速排序，則第一次劃分的結(jié)果是：.下面是三個(gè)關(guān)于有向圖運(yùn)算的敘述:（）求有向圖結(jié)點(diǎn)的拓?fù)湫蛄校浣Y(jié)果必然是惟一的（）求兩個(gè)指向結(jié)點(diǎn)間的最短路徑，其結(jié)果必然是惟一的（）求 網(wǎng)的關(guān)鍵路徑，其結(jié)果必然是惟一的其中哪個(gè)（些）是正確的？惟獨(dú)（） （）和（） 都正確 都不正確.若進(jìn)棧序列為 ，則通過(guò)入出棧操作可能得到的 的不同羅列個(gè)數(shù)為以下關(guān)于廣義表的敘述中正確的是：廣義表是由個(gè)或者多個(gè)單元素或者子表構(gòu)成的有限序列廣義表至少有一個(gè)元素是子表廣義表不能遞歸定義廣義表不能為空表排序時(shí)掃描待排序記錄序列，按次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交換位置這是哪種排序方法的基本思想？堆排序 直接插入排序這是哪種排序方法的基本思想？堆排序 直接插入排序?已知一個(gè)有向圖的鄰接矩陣表示，

將鄰接矩陣的第行刪除

將鄰接矩陣的第列刪除.有一個(gè)含頭結(jié)點(diǎn)的雙向循環(huán)鏈表,快速排序 冒泡排序要?jiǎng)h除所有從第個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)該:將鄰接矩陣的第行元素全部置為將鄰接矩陣的第列元素全部置為頭指針為 則其為空的條件是：在順序表 中，用折半法查找關(guān)鍵碼值，所需的關(guān)鍵碼比較次數(shù)為：以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？從隊(duì)尾插入一個(gè)新元素 從隊(duì)列中刪除第個(gè)元素判斷一個(gè)隊(duì)列是否為空 讀取隊(duì)頭元素的值.對(duì)包含個(gè)元素的哈希表進(jìn)行查找，平均查找長(zhǎng)度為：不直接依賴(lài)于.將一棵有個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)從根這一層開(kāi)始，每一層從左到右挨次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為，則編號(hào)最大的非葉結(jié)點(diǎn)的編號(hào)為：.某二叉樹(shù)結(jié)點(diǎn)的中序序列為、、、、、、，后序序列為、、、、、、,則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：?下面是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)。存儲(chǔ)密度大 插入運(yùn)算方便查找方便 適合各種邏輯結(jié)構(gòu)的存儲(chǔ)表示.下面關(guān)于串的敘述中，是不正確的。串是字符的有限序列 空串是由空格構(gòu)成的串模式匹配是串的一種重要運(yùn)算 串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ).的鄰接矩陣是對(duì)稱(chēng)矩陣。有向圖 無(wú)向圖 網(wǎng) 網(wǎng).用鏈?zhǔn)椒绞酱鎯?chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)，O僅修改頭指針 僅修改尾指針頭、尾指針都要修改 頭、尾指針可能都要修改.二叉樹(shù)的先序遍歷和中序遍歷如下，則該二叉樹(shù)右子樹(shù)的樹(shù)根是O先序序列： 中序序列：?下面方法可以判斷出一個(gè)有向圖中是否有環(huán)。深度優(yōu)先遍歷 拓樸排序 求最短路徑 求關(guān)鍵路徑.從未排序序列中挨次取出一個(gè)元素與已排序序列中的元素挨次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱(chēng)為 排序法。插入 選擇 冒泡都不是.一個(gè)棧的入棧序列是 ，則棧的不可能的輸出序列是O個(gè)節(jié)點(diǎn)的徹底二叉樹(shù)，編號(hào)為的節(jié)點(diǎn)是葉子結(jié)點(diǎn)的條件是O.向一個(gè)有 個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要挪移個(gè)元素。,在一個(gè)單鏈表中，若要在指針?biāo)附Y(jié)點(diǎn)的后面插入一個(gè)由指針?biāo)赶虻慕Y(jié)點(diǎn)，則執(zhí)行。.對(duì)一個(gè)滿二叉樹(shù)， 個(gè)樹(shù)葉，個(gè)結(jié)點(diǎn)，深度為，則有O.在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始羅列次序無(wú)關(guān)的是O選擇排序冒泡排序 插入排序 希爾排序用鏈?zhǔn)椒绞酱鎯?chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)，O僅修改頭指針 僅修改尾指針頭、尾指針都要修改 頭、尾指針可能都要修改.在一個(gè)長(zhǎng)度為的順序存儲(chǔ)的線性表中，向第個(gè)元素（WW）插入一個(gè)新元素時(shí)，需要從后向前挨次后移個(gè)元素。.一個(gè)棧的入棧序列是 ，則棧的不可能的輸出序列是O個(gè)頂點(diǎn)的有向圖最多有條弧。.假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針?lè)謩e為和，則判斷隊(duì)空的條件為O.若某線性表中最常用的操作是提取第個(gè)元素及找第個(gè)元素的前驅(qū)元素，則采用（ ）存儲(chǔ)方式最省時(shí)間。單鏈表 雙鏈表 單向循環(huán)鏈表 順序表.將含有 個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)從根開(kāi)始自上向下，每層從左到右挨次編號(hào)，且設(shè)根結(jié)點(diǎn)的編號(hào)為，則編號(hào)的結(jié)點(diǎn)的雙親的編號(hào)為（）o無(wú)法確定單循環(huán)鏈表的主要優(yōu)點(diǎn)是（）o再也不需要頭指針了已知某結(jié)點(diǎn)的位置后，很容易找到其前驅(qū)在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開(kāi)從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表一個(gè)棧的入棧順序是、、、、，則此棧不可能的輸出順序?yàn)椋?）o串是一種特殊的線性表，其特殊性表現(xiàn)在（ ）o可以順序存儲(chǔ) 數(shù)據(jù)元素是一個(gè)字符可以鏈?zhǔn)酱鎯?chǔ) 數(shù)據(jù)元素是多個(gè)字符個(gè)頂點(diǎn)的無(wú)向圖中最多有（）條邊。個(gè)頂點(diǎn)的無(wú)向圖中，至少有（）條邊才干保證是一個(gè)連通圖。.若某線性表中最常用的操作是刪除第個(gè)元素，則不宜采用（ ）存儲(chǔ)方式。單鏈表 雙鏈表 單向循環(huán)鏈表順序表.在一棵徹底二叉樹(shù)的順序存儲(chǔ)方式中，若編號(hào)的結(jié)點(diǎn)有右孩子，則其右孩子的編號(hào)為（）o按照二叉樹(shù)的定義，具有個(gè)結(jié)點(diǎn)的二叉樹(shù)有（ ）種不同形態(tài)。在長(zhǎng)為的順序表中，刪除第個(gè)元素wW 需要向前挪移（ ）個(gè)元素。TOC\o"1-5"\h\z一個(gè)隊(duì)的入隊(duì)順序是、、、、，則此隊(duì)的出隊(duì)順序?yàn)椋?）。棧是一種特殊的線性表，其特殊性表現(xiàn)在（ ）?？梢皂樞虼鎯?chǔ) 只能從端點(diǎn)進(jìn)行插入和刪除可以鏈?zhǔn)酱鎯?chǔ) 可以在任何位置進(jìn)行插入和刪除一棵二叉樹(shù)中，第層上最多有（ ）個(gè)結(jié)點(diǎn)。一棵有個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度最小為（ ）層。有向圖中，所有頂點(diǎn)入度和是所有頂點(diǎn)出度和的（ ）倍。（-）填空題數(shù)據(jù)元素之間存在的相互關(guān)系稱(chēng)為O數(shù)據(jù)結(jié)構(gòu)從邏輯上分為結(jié)構(gòu)和結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)為O所有插入在表的一端進(jìn)行，而所有刪除在表的另一端進(jìn)行的線性表稱(chēng)為深度為的二叉樹(shù)至少有個(gè)結(jié)點(diǎn)。折半查找要求待查表為表。個(gè)記錄按其關(guān)鍵字大小遞增或者遞減的次序羅列起來(lái)的過(guò)程稱(chēng)為存儲(chǔ)數(shù)據(jù)時(shí)不僅要存儲(chǔ)數(shù)據(jù)元素的還要存儲(chǔ)元素之間的相互..將一棵有 個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)按層編號(hào)，則編號(hào)為的結(jié)點(diǎn)，其雙親（）的編號(hào)為O、一個(gè)字符串相等的充要條件是和O、在有向圖的鄰接表和逆鄰接表表示中，每一個(gè)頂點(diǎn)的邊鏈表中分別鏈接著該頂點(diǎn)的所右和 結(jié)點(diǎn)。、在一個(gè)長(zhǎng)度為的順序表中向第 個(gè)元素（W）之前插入一個(gè)新元素時(shí)，需要向后挪移個(gè)元素。、是只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。、設(shè)主串=" ”模式串=" ”則第次匹配成功。、在一棵二叉樹(shù)中，第層上的結(jié)點(diǎn)數(shù)最多為 O（根的層次為）、假設(shè)一個(gè)階的上三角矩陣按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組中，其中［］存儲(chǔ)矩陣中第個(gè)元素,則 中存放的元素是O、有個(gè)結(jié)點(diǎn)的二叉鏈表中，其中空的指針域?yàn)椋赶蚝⒆拥闹羔槀€(gè)數(shù)為O、二叉樹(shù)后序遍歷的順序是 ，則該二叉樹(shù)的根結(jié)點(diǎn)是O、對(duì)于一個(gè)具有個(gè)頂點(diǎn)和條邊的無(wú)向圖，若采用鄰接表表示，則整個(gè)鄰接表中的結(jié)點(diǎn)總數(shù)是.O、在單鏈表上難以實(shí)現(xiàn)的排序方法有和O.查找法的平均查找長(zhǎng)度與元素個(gè)數(shù)無(wú)關(guān)。、在有個(gè)元素的順序表的任意位置插入一個(gè)元素所需挪移結(jié)點(diǎn)的平均次數(shù)為、是插入和刪除元素都在表的同一端進(jìn)行的線性表。、廣義表=（ ）則其長(zhǎng)度為O、在樹(shù)中，除跟結(jié)點(diǎn)外，其他結(jié)點(diǎn)都有且惟獨(dú)一個(gè)結(jié)點(diǎn)。、在串“ ”中，以為首字符的子串有個(gè)。、廣度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的按 遍歷的過(guò)程。、已知一棵徹底二叉樹(shù)中共有 個(gè)結(jié)點(diǎn)為，則該樹(shù)中共有個(gè)葉子結(jié)點(diǎn)。、在有序表（ ）中二分查找關(guān)鍵字時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)^。、兩個(gè)長(zhǎng)度分別和（）的排好序的表歸并成一個(gè)排好序的表，至少要進(jìn)行次鍵值比較。通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量： 、、和 。、 一個(gè)算法的時(shí)間復(fù)雜度為 ，其數(shù)量級(jí)表示為 。、 若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)，每一個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，個(gè)結(jié)點(diǎn)的二叉樹(shù)共有 個(gè)指針域，其中有個(gè)指針域是存放了地址，有 個(gè)指針是空指針。、 對(duì)于一個(gè)具有個(gè)頂點(diǎn)和條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有個(gè)和個(gè)。、 在一個(gè)具有個(gè)頂點(diǎn)的無(wú)向徹底圖中，包含有條邊，在一個(gè)具有個(gè)頂點(diǎn)的有向徹底圖中，包含有條邊。在快速排序、堆排序、歸并排序中， 排序是穩(wěn)定的。37.中序遍歷二叉排序樹(shù)所得到的序列是序列?？焖倥判虻淖顗臅r(shí)間復(fù)雜度為 ，平均時(shí)間復(fù)雜度為 。設(shè)一組初始記錄關(guān)鍵字序列為，，，，，，， ，則利用篩選法建立的初始堆為 。.數(shù)據(jù)的物理結(jié)構(gòu)主要包括 和 兩種情況。設(shè)一棵徹底二叉樹(shù)中有 個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的深度為 ；若用二叉鏈表作為該徹底二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則共有 個(gè)空指針域。、設(shè)輸入序列為、、，則經(jīng)過(guò)棧的作用后可以得到 種不同的輸出序列。、設(shè)有向圖用鄰接矩陣 作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第行上所有元素之和等于頂點(diǎn)的，第列上所有元素之和等于頂點(diǎn)的。設(shè)哈夫曼樹(shù)中共有個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有 個(gè)度數(shù)為的結(jié)點(diǎn)。設(shè)有向圖中有個(gè)頂點(diǎn)條有向邊，所有的頂點(diǎn)入度數(shù)之和為，則和的關(guān)系為遍歷二叉排序樹(shù)中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列（填先序、中序或者后序）。設(shè)查找表中有個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素，則最多需要比較次就可以斷定數(shù)據(jù)元素是否在查找表中。不管是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為T(mén)OC\o"1-5"\h\z設(shè)有個(gè)結(jié)點(diǎn)的徹底二叉樹(shù)，如果按照從自上到下、從左到右從開(kāi)始順序編號(hào)，則第個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為 ，右孩子結(jié)點(diǎn)的編號(hào)為 。設(shè)一組初始記錄關(guān)鍵字為，，，，，，，則以記錄關(guān)鍵字為基準(zhǔn)的一趟快速排序結(jié)果為 。設(shè)有向圖中有向邊的集合 ，，，，，，，，， ，則該圖的一種拓?fù)湫蛄袨?。下列算法實(shí)現(xiàn)在順序散列表中查找值為的關(guān)鍵字，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。下列算法實(shí)現(xiàn)在二叉排序樹(shù)上查找關(guān)鍵值，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。設(shè)有個(gè)無(wú)序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為 ，快速排序的平均時(shí)間復(fù)雜度為設(shè)指針變量指向雙向循環(huán)鏈表中的結(jié)點(diǎn)，則刪除結(jié)點(diǎn)需要執(zhí)行的語(yǔ)句序列為（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為和）分別為和）O根據(jù)初始關(guān)鍵字序列高度為 。深度為的徹底二叉樹(shù)中至少有設(shè)初始記錄關(guān)鍵字序列為，，…，素開(kāi)始進(jìn)行篩選。、設(shè)哈夫曼樹(shù)中共有個(gè)結(jié)點(diǎn)，則該樹(shù)中有存儲(chǔ)結(jié)構(gòu)，則該樹(shù)中有 個(gè)空指針域。、設(shè)有一個(gè)順序循環(huán)隊(duì)列中有個(gè)存儲(chǔ)單元，,,,, 建立的二叉排序樹(shù)的個(gè)結(jié)點(diǎn)。,則用篩選法思想建堆必須從第 個(gè)元個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為則該循環(huán)隊(duì)列中最多能夠存