02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論復(fù)習(xí)題

#數(shù)據(jù)結(jié)構(gòu)導(dǎo)論模擬試題一、考試題型及分值分布：1、單項選擇題（本大題共15小題，每小題2分，共30分）2、填空題（本大題共13小題，每小題2分，共26分）3、應(yīng)用題（本大題共5小題，每小題6分，共30分）4、算法設(shè)計題（本大題共2小題，每小題7分，共14分）二、單項選擇題和填空題樣題參考（一）單項選擇題.在二維數(shù)組中，每個數(shù)組元素同時處于（）個向量中。A.0 B.1 C.2 D.n已知單鏈表長度為，單鏈表長度為，它們分別由表頭指針?biāo)赶?，若將整體連接到的末尾，其時間復(fù)雜度應(yīng)為（）。A.O（1） B.O（m） C.O（n）假定一個鏈?zhǔn)疥犃械年狀^和隊尾指針分別為 和，則判斷隊空的條件為若讓元素1,2依,次3進(jìn)棧，則出棧次序不可能出現(xiàn)（種情）況。A.3,2,1 B.2,1,3圖的廣度優(yōu)先搜索類似于樹的（）遍歷。先根 中根 后根 層次下面程序段的時間復(fù)雜度為（。）設(shè)有兩個串和，求在中首次出現(xiàn)的位置的運算叫做（）。求子串 模式匹配 串替換 串連接8利用雙向鏈表作線性表的存儲結(jié)構(gòu)的優(yōu)點是（）。便于單向進(jìn)行插入和刪除的操作 便于雙向進(jìn)行插入和刪除的操作節(jié)省空間 便于銷毀結(jié)構(gòu)釋放空間設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點的結(jié)構(gòu)為（ ）,且 是指向棧頂?shù)闹羔?。若想在鏈?zhǔn)綏５臈ｍ敳迦胍粋€由指針?biāo)傅慕Y(jié)點，則應(yīng)執(zhí)行 操作。.一棵具有35個結(jié)點的完全二叉樹的高度為（。假）定空樹的高度為-1。TOC\o"1-5"\h\zA.5 B.6 C.7一個有個頂點和條邊的無向圖一定是 的。A連通 .不連通.無回路 .有回路在一個長度為的順序表的任一位置插入一個新元素的時間復(fù)雜度為（）。A.O（n） B.O（n/2） 2） C.O（E知廣義表為 ，從中取出原子的運算是（）。.在一棵樹的靜態(tài)雙親表示中，每個存儲結(jié)點包含（個）域。15有.向圖中的一個頂點的度數(shù)等于該頂點的（。）A入度 .出度入度與出度之和 .入度出度2.與鄰接矩陣相比，鄰接表更適合于存儲（。）A無向圖.連通圖 .稀疏圖 .稠密圖.較快的數(shù)據(jù)搜索方法是（）搜索方法。順序 折半 單鏈散列.在閉散列表中，散列到同一個地址而引起的“堆積”問題是由于（）引起的。

同義詞之間發(fā)生沖突 非同義詞之間發(fā)生沖突同義詞之間或非同義詞之間發(fā)生沖突 散列表“溢出”根據(jù)個元素建立一個有序單鏈表的時間復(fù)雜度為（）。A.O（1） B.2O）（n） 2Dn.）CO.（nOl（ong假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為 和，則判斷隊空的條件為（。）假定一棵二叉樹的第層上有個結(jié)點，則第 層上最多有個結(jié)點。A.3i B.6i C.9i D對于具有條邊的無向圖，它的鄰接表中共有 個邊結(jié)點。A．e-1 ．e+1B．2eC．3eD23對圖的深度優(yōu)先搜索遍歷類似于樹的（）次序遍歷。先根 中根 后根 層次.棧最多能容納個元素?，F(xiàn)有個元素按 的順序進(jìn)棧問下列哪一個序列是可能的出棧序列?（ 邊25．將一棵有10個0結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號為：（邊26對對下列關(guān)鍵字序列用快速排序法進(jìn)行排序時，速度最快的情形是：（邊27．對于只在表的首、尾進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為順序表 用頭指針表示的單循環(huán)鏈表用尾指針表示的單循環(huán)鏈表 單鏈表.假設(shè)以第一個元素為分界元素，對字符序列（）進(jìn)行快速排序，則第一次劃分的結(jié)果是：（邊面是三個關(guān)于有向圖運算的敘述：(1)求有向圖結(jié)點的拓?fù)湫蛄?，其結(jié)果必定是唯一的(2)求兩個指向結(jié)點間的最短路徑，其結(jié)果必定是唯一的()求 網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的其中哪個(些)是正確的？只有() ()和() 都正確 都不正確.若進(jìn)棧序列為 ，則通過入出棧操作可能得到的 的不同排列個數(shù)為31.以下關(guān)于廣義表的敘述中,正確的是：( )廣義表是由個或多個單元素或子表構(gòu)成的有限序列廣義表至少有一個元素是子表廣義表不能遞歸定義廣義表不能為空表若2.排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置。這是哪種排序方法的基本思想？( )堆排序直接插入排序 快速排序 冒泡排序.已知一個有向圖的鄰接矩陣表示，要刪除所有從第個結(jié)點發(fā)出的邊，應(yīng)該：將鄰接矩陣的第行刪除 將鄰接矩陣的第行元素全部置為將鄰接矩陣的第列刪除 將鄰接矩陣的第列元素全部置為4有一個含頭結(jié)點的雙向循環(huán)鏈表，頭指針為 則其為空的條件是：TOC\o"1-5"\h\z若5在.順序表(若,6,8,10,12,15中,，用1折6半,法查1找8關(guān),鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為：( )A.2 B.若 C.4若6.以下哪一個不是隊列的基本運算？( )從隊尾插入一個新元素 從隊列中刪除第個元素判斷一個隊列是否為空 讀取隊頭元素的值7對包含個元素的哈希表進(jìn)行查找，平均查找長度為：不直接依賴于TOC\o"1-5"\h\z若8.將一棵有10個0結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點編號為1，則編號最大的非葉結(jié)點的編號為：( )A.48 B.49C.50 D.51.某二叉樹結(jié)點的中序序列為 后序序列為 E則其左子樹中結(jié)點數(shù)目為：A.若 B.2 C.40下面是順序存儲結(jié)構(gòu)的優(yōu)點。存儲密度大 插入運算方便查找方便 適合各種邏輯結(jié)構(gòu)的存儲表示.下面關(guān)于串的敘述中，是不正確的。串是字符的有限序列 空串是由空格構(gòu)成的串模式匹配是串的一種重要運算 串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?的鄰接矩陣是對稱矩陣。有向圖 無向圖 網(wǎng) 網(wǎng).用鏈?zhǔn)椒绞酱鎯Φ年犃?，在進(jìn)行刪除運算時，。僅修改頭指針 僅修改尾指針頭、尾指針都要修改 頭、尾指針可能都要修改.二叉樹的先序遍歷和中序遍歷如下，則該二叉樹右子樹的樹根是。先序序列： 中序序列：A.E B.F C.G D?下面方法可以判斷出一個有向圖中是否有環(huán)。深度優(yōu)先遍歷 拓樸排序 求最短路徑 求關(guān)鍵路徑4?6從未排序序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為排序法。插入 選擇 冒泡都不是7一個棧的入棧序列是 ，則棧的不可能的輸出序列是。A.edcba B.decba C.dceab8個節(jié)點的完全二叉樹，編號為的節(jié)點是葉子結(jié)點的條件是。A.i<nB.2*i<=n C.2*i+1>n49?向一個有12個8元素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元素。O在一個單鏈表中，若要在指針?biāo)附Y(jié)點的后面插入一個由指針?biāo)赶虻慕Y(jié)點，則執(zhí)行。1對一個滿二叉樹，個樹葉，個結(jié)點，深度為，則有。A.n=h+mB.h+m=2n C.m=h-1.在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是。選擇排序 冒泡排序插入排序 希爾排序.用鏈?zhǔn)椒绞酱鎯Φ年犃?，在進(jìn)行插入運算時，。僅修改頭指針 僅修改尾指針頭、尾指針都要修改 頭、尾指針可能都要修改4在一個長度為的順序存儲的線性表中，向第個元素（WW）插入一個新元素時，需要從后向前依次后移個元素。A.n-i 冒.n-i-1 C.n-i+1.一個棧的入棧序列是 3則棧的不可能的輸出序列是。A.23415 冒.54132 C.231456個頂點的有向圖最多有條弧。A.5 冒.20 C.4.假定一個鏈隊的隊首和隊尾指針分別為 和a則判斷隊空的條件為。.若某線性表中最常用的操作是提取第個元素及找第個元素的前驅(qū)元素，則采用（ ）存儲方式最省時間。單鏈表 雙鏈表 單向循環(huán)鏈表 順序表5?9將含有10個0結(jié)點的完全二叉樹從根開始自上向下，每層從左到右依次編號，且設(shè)根結(jié)點的編號為1，則編號69的結(jié)點的雙親的編號為（ ）。無法確定序單循環(huán)鏈表的主要優(yōu)點是（ ）。不再需要頭指針了已知某結(jié)點的位置后，很容易找到其前驅(qū)在進(jìn)行插入、刪除運算時，能更好地保證鏈表不斷開從表中任一結(jié)點出發(fā)都能掃描到整個鏈表.一個棧的入棧順序是1、2、3、4、5，則此棧不可能的輸出順序為（ ）。62.串是一種特殊的線性表，其特殊性表現(xiàn)在（ ）。可以順序存儲 數(shù)據(jù)元素是一個字符可以鏈?zhǔn)酱鎯?數(shù)據(jù)元素是多個字符個頂點的無向圖中最多有（）條邊。A.n（n-1）/2 B.n（n-1） C.n（n64.個頂6點的無向圖中，至少有（）條邊才能保證是一個連通圖。A.5 B.6 C.76．5若某線性表中最常用的操作是刪除第1個元素，則不宜采用（ ）存儲方式。單鏈表 雙鏈表 單向循環(huán)鏈表順序表.在一棵完全二叉樹的順序存儲方式中，若編號的結(jié)點有右孩子，則其右孩子的編號為（）。67序按照二叉樹的定義，具有3個結(jié)點的二叉樹有（ ）種不同形態(tài)。在長為的順序表中，刪除第個元素1W 需要向前移動（ ）個元素。TOC\o"1-5"\h\z69序一個隊的入隊順序是1、2、3、4、5，則此隊的出隊順序為（ ）。70序棧是一種特殊的線性表，其特殊性表現(xiàn)在（ ）?？梢皂樞虼鎯?只能從端點進(jìn)行插入和刪除可以鏈?zhǔn)酱鎯?可以在任何位置進(jìn)行插入和刪除一棵二叉樹中，第層上最多有（ ）個結(jié)點。72序一棵有18個結(jié)點的二叉樹，其高度最小為（ ）層。73有序向圖中，所有頂點入度和是所有頂點出度和的（ ）倍。（二）填空題數(shù)據(jù)元素之間存在的相互關(guān)系稱為。數(shù)據(jù)結(jié)構(gòu)從邏輯上分為結(jié)構(gòu)和 結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)稱為。所有插入在表的一端進(jìn)行，而所有刪除在表的另一端進(jìn)行的線性表稱為深度為的二叉樹最少有 個結(jié)點。折半查找要求待查表為表。個記錄按其關(guān)鍵字大小遞增或遞減的次序排列起來的過程稱為。存儲數(shù)據(jù)時不僅要存儲數(shù)據(jù)元素的還要存儲元素之間的相互。9將一棵有 個結(jié)點的完全二叉樹按層編號，則編號為的結(jié)點X其雙親EN的編號為。0一個字符串相等的充要條件是和。1在有向圖的鄰接表和逆鄰接表表示中，每個頂點的邊鏈表中分別鏈接著該頂點的所有和結(jié)點。1在一個長度為的順序表中向第 個元素（w）之前插入一個新元素時，需要向后移動個元素。2是只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。、設(shè)主串=" "模式串="x則第次匹配成功。4在一棵二叉樹中，第層上的結(jié)點數(shù)最多為。（根的層次為）5假設(shè)一個階的上三角矩陣按列優(yōu)先順序壓縮存儲在一維數(shù)組中，其中［］存儲矩陣中第個元素，則 中存放的元素是。6有個結(jié)點的二叉鏈表中，其中空的指針域為,指向孩子的指針個數(shù)為。、二叉樹后序遍歷的順序是 C則該二叉樹的根結(jié)點是。8對于一個具有個頂點和條邊的無向圖，若采用鄰接表表示，則整個鄰接表中的結(jié)點總數(shù)是。、在單鏈表上難以實現(xiàn)的排序方法有和。0查找法的平均查找長度與元素個數(shù)無關(guān)。1在有個元素的順序表的任意位置插入一個元素所需移動結(jié)點的平均次數(shù)為、是插入和刪除元素都在表的同一端進(jìn)行的線性表。、廣義表=（ ）則其長度為。4在樹中，除跟結(jié)點外，其他結(jié)點都有且只有一個結(jié)點。、在串“ ”中，以為首字符的子串有個。7廣度優(yōu)先搜索遍歷類似于樹的按遍歷的過程。8E知一棵完全二叉樹中共有 個結(jié)點為，則該樹中共有個葉子結(jié)點。、在有序表（ ）中二分查找關(guān)鍵字時所需進(jìn)行的關(guān)鍵字比較次數(shù)為。、兩個長度分別和（）的排好序的表歸并成一個排好序的表，至少要進(jìn)行次鍵值比較。通常從四個方面評價算法的質(zhì)量： 、、和 _1 一個算法的時間復(fù)雜度為 2其數(shù)量級表示為 。、、2 若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，個結(jié)點的二叉樹共有 個指針域，其中有個指針域是存放了地址，有、、、、、、、、個、指、針、是、空、指、針、。、、 對于一個具有個頂點和條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有、、、、個、和、、、、、、個、。、、、4 在一個具有個頂點的無向完全圖中，包含有 條邊，在一個具有個頂點的有向完全圖中，包含有、、、、條、邊、。、、、6在.快速排序、堆排序、歸并排序中，、、、、、排、序、是、穩(wěn)、定的。37.中序遍歷二叉排序樹所得到的序列是 序列。、8快.速排序的最壞時間復(fù)雜度為、、、、、、，、平、均、時、間、復(fù)雜度為、、、、、。、、、、、、、設(shè).一組初始記錄關(guān)鍵字序列為（5，56，、4，4、8，75，8，0、，156，）則利用篩選法建立的初始堆為、、、、、、、、、、、、、、。、、、、、、、、、、、、、40．?dāng)?shù)據(jù)的物理結(jié)構(gòu)主要包括、、、、和、、、、、兩、種、情、況、。41設(shè).一棵完全二叉樹中有50個0結(jié)點，則該二叉樹的深度為 ；_若_用_二_叉_鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有 個_空_指_針_域_。42、設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到 種_不_同_的_輸_出序列。3設(shè)有向圖用鄰接矩陣 作為存儲結(jié)構(gòu)，則該鄰接矩陣中第行上所有元素之和等于頂點的，第列上所有元素之和等于頂點的。設(shè)哈夫曼樹中共有個結(jié)點，則該哈夫曼樹中有 個_度_數(shù)_為_1的結(jié)點。設(shè)有向圖中有個頂點條有向邊，所有的頂點入度數(shù)之和為，則和的關(guān)系為 。 遍_歷_二_叉_排_序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。設(shè)查找表中有 個元素，如果用二分法查找方法查找數(shù)據(jù)元素，則最多需要比較次就可以斷定數(shù)據(jù)元素是否在查找表中。不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為次次次次次次。次次次次次次設(shè)有個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從開始順序編號，則第個結(jié)點的雙親結(jié)點編號為 ，右孩子結(jié)點的編號為 。設(shè)一組初始記錄關(guān)鍵字為（7，27，371，2，394，16，5，）則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為次次次次次次次次次。次次次次次次次次次設(shè)有向圖中有向邊的集合，，，，，，，，， ,則該圖的一種拓?fù)湫蛄袨榇未未未未未未未未未巍４未未未未未未未未未蜗铝兴惴▽崿F(xiàn)在順序散列表中查找值為的關(guān)鍵字，請在下劃線處填上正確的語句。，下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值，請在下劃線處填上正確的語句。，設(shè)有個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為 ，快速排序的平均時間復(fù)雜度為次次次次次。次次次次設(shè)指針變量指向雙向循環(huán)鏈表中的結(jié)點X則刪除結(jié)點需要執(zhí)行的語句序列為次次次次次次次次次次次次次次次次次次次次次次次次次次次次次（次設(shè)次結(jié)次點次中次的次兩次個次指次針次域次分別為和 ）。根據(jù)初始關(guān)鍵字序列12 ,, 建立的二叉排序樹的高度為 3_。 深度為的完全二叉樹中最少有 個結(jié)點。設(shè)初始記錄關(guān)鍵字序列為K，-，）則用篩選法思想建堆必須從第 個元12 n素開始進(jìn)行篩選。59、設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有 個_葉_子_結(jié)_點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有___個_空_指針域。、設(shè)有一個順序循環(huán)隊列中有個存儲單元，則該循環(huán)隊列中最多能夠存儲 個隊列元素；當(dāng)前實際存