鄭州大學遠程教育數(shù)據(jù)結(jié)構(gòu)考試

1、數(shù)據(jù)結(jié)構(gòu)第04章在線測試答題須知：1、本卷滿分20分。2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題（每題1分，5道題共5分）1、若串S = abcdef”，則其非空子串數(shù)目為OrA、6B、12rC、21rD、222、字符串是一種特殊的線性表，其特殊性在于它的數(shù)據(jù)元素只能是OrA、字符B、字符串rC、數(shù)字rD、字母3、設有三個串，s1=How”, s2 = are”, s3 = you”,則這三個串連接后得到的結(jié)果串是OrA、 HowareyouB、How are your ,C、How

2、 are you.rD、How are you4、串是一種特殊的線性表，其特殊性體現(xiàn)在OrA、可以順序存儲B、數(shù)據(jù)元素是一個字符rC、可以鏈接存儲rD、數(shù)據(jù)元素可以是多個字符5、空格串的長度為orA、0rB、1rC、串中空格的個數(shù)D、第二題、多項選擇題（每題2分，5道題共10分）1、在定長順序存儲表示中，對串長的表示方法有Or一A、用域變量表示B、用下標為0的數(shù)組分量表示C、在串值后加結(jié)束標記字符rD、無法明確表示2、以下關于串的存儲方式的說法中正確的是O數(shù)據(jù)結(jié)構(gòu)第04章在線測試剩余時間：43:12AA、定長順序表示和堆分配表示都是串的順序存儲表示B、定長順序表示的串的存儲空間是編譯時預先分配

3、的一個比較大的連續(xù)空間C、堆分配表示的串的存儲空間是在程序執(zhí)行過程中動態(tài)分配的D、堆分配存儲表示時的空串不占用連續(xù)的存儲區(qū)3、兩個串相等的充分必要條件是。A、串長相等且各對應位置字符相等匚B、所含字符集合相同匚C、所含字符個數(shù)相同D、串值相等 TOC o 1-5 h z 4、串的機內(nèi)表示方法有。A、定長順序存儲表示B、堆分配存儲表示C、塊鏈存儲表示匚一D、散列表示5、以下關于塊鏈結(jié)構(gòu)的說法正確的是。A、結(jié)點大小小，則存儲密度小匚B、結(jié)點大小小，則存儲密度大C、結(jié)點大小小，則占用存儲空間多匚D、結(jié)點大小小，則占用存儲空間少第三題、判斷題（每題1分，5道題共5分）1、如果一個串中的所有字符均在另一

4、串中出現(xiàn)，則前者是后者的子串。r際正確錯誤2、串也有兩種存儲結(jié)構(gòu)：順序結(jié)構(gòu)和鏈式結(jié)構(gòu)。汗r正確錯誤3、串是n個字母的有限序列（nNO）。正確錯誤4、串是元素類型受限制的線性表。&r正確錯誤5、在C語言中，用動態(tài)分配函數(shù)進行管理的自由存儲區(qū)稱為“堆”。苻r(nóng)正確錯誤交卷數(shù)據(jù)結(jié)構(gòu)第05章在線測試剩余時間：35:15答題須知：1、本卷滿分20分。2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題(每題1分，5道題共5分)1、按照二叉樹的定義，具有3個結(jié)點的二叉樹有種形態(tài)。rA、3rB、4C、5rD、

5、62、樹最適合表示。rA、有序數(shù)據(jù)元素rB、無序數(shù)據(jù)元素C、元素之間具有分支層次關系的數(shù)據(jù)rD、元素之間無聯(lián)系的數(shù)據(jù)3、的同種順序的遍歷仍需要棧的支持。rA、先序線索樹rB、中序線索樹C、后序線索樹rD、4、巳知二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的先序遍歷序列是。rA、 acbedrB、 decabrC、 deabcD、 cedba5、對于表達式(a-b+c)*d/(e+f),其前綴表達式為。錯rA、 /*+-abcd+efrB、 a-b+c*d/e+fC、 /*-a+bcd+efrD、 ab-c+d*ef+/第二題、多項選擇題（每題2分，5道題共10分）1、下列

6、關于完全二叉樹的敘述中，正確的有。A、完全二叉樹一定是滿二叉樹B、滿二叉樹一定是完全二叉樹C、完全二叉樹中要么沒有結(jié)點的度為1，要么只可能有一個結(jié)點的度為1D、只有一個結(jié)點的度為1的二叉樹一定是完全二叉樹2、下列關于樹和二叉樹的敘述中，正確的有。EA、森林和二叉樹之間可以相互轉(zhuǎn)換B、樹和二叉樹之間可以相互轉(zhuǎn)換c、二叉樹的子樹有左右之分，而樹的子樹沒有左右之分ED、二叉樹結(jié)點的最大度數(shù)為2,而樹的結(jié)點的最大度數(shù)沒有限制3、森林的遍歷方式有A、先序遍歷B、中序遍歷C、后序遍歷口D、層序遍歷4、先序序列和中序序列相同的二叉樹有。A、空二叉樹B、左單支樹C、右單支樹D、根樹5、將一個有50個結(jié)點的完全

7、二叉樹按層序編號（根編號為1），則編號為25的結(jié)點A、有左孩子rB、有右孩子rC、無左孩子17D、無右孩子第三題、判斷題（每題1分，5道題共5分）1、n個葉子的Huffman樹共有2n-1個結(jié)點。r正確錯誤2、二叉樹的先、中、后序遍歷序列中，葉子結(jié)點的相對順序不會發(fā)生改變。苻r(nóng)正確錯誤3、將一棵樹轉(zhuǎn)換成相應的二叉樹后，二叉樹的根結(jié)點肯定沒有左子樹。r河正確錯誤4、二叉樹的先序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。苻r(nóng)正確錯誤5、給定二叉樹的先序和后序遍歷序列，可以唯一的確定這棵二叉樹。r河正確錯誤數(shù)據(jù)結(jié)構(gòu)第06章在線測試剩余時間：47:27答題須知：1、本卷滿分20分。2、答完題后，

8、請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題（每題1分，5道題共5分）1、一個有n個頂點的無向圖若是連通圖，則至少有條邊。&A、n-1rB、nrC、n+1rD、(n+1)/22、4個頂點的無向完全圖有條邊。錯rA、6B、12rC、16rD、203、一個無向連通圖的生成樹是含有該連通圖所有頂點的。rA、極大連通子圖rB、極大子圖&C、極小連通子圖rD、極小子圖4、對，用克魯斯卡爾算法求最小生成樹較為合適。A、非連通圖B、連通圖 TOC o 1-5 h z #rC、稀疏圖D、稠密圖5、對，用Prim算法

9、求最小生成樹較為合適。 HYPERLINK l bookmark179 o Current Document rrA、非連通圖B、連通圖 HYPERLINK l bookmark183 o Current Document r河C、稀疏圖D、稠密圖第二題、多項選擇題(每題2分，5道題共10分)1、如果對無向圖G必須進行二次廣度優(yōu)先遍歷才能訪問到圖中所有頂點，則下列說法中正確的是,匚A、G肯定不是完全圖匚B、G肯定不是連通圖匚C、G中一定有回路匚D、G有兩個連通分量2、下列說法中正確的是。匚A、無向圖中的極大連通子圖稱為連通分量。匚B、圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點。匚C、

10、圖的深度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點。匚D、有向圖的遍歷不能采用廣度優(yōu)先搜索方法。3、下列說法中不正確的有。A、n個頂點的無向連通圖的邊數(shù)為n(n-1)B、圖的廣度優(yōu)先遍歷過程是一個遞歸過程匚C、n個頂點的有向完全圖的弧數(shù)為n(n-1)匚D、有向圖的強連通分量是有向圖的極大強連通子圖4、下列關于最短路徑的說法中，正確的有。匚A、Dijkstra算法是按路徑長度遞增的順序依次產(chǎn)生從某一固定源點到其他各頂點之間的最短路徑。匚B、若僅求單一源點到某一特定頂點之間的最短路徑，則其算法的時間復雜度可以達到O(n)。C、求圖中每一對頂點間最短路徑的Floyd算法的時間復雜度為O（n”3）。

11、D、求圖中每一對頂點間的最短路徑也可用Dijkstra算法實現(xiàn)。5、有向圖中頂點之間關系的特征是：每個頂點可以有。A、一個前驅(qū)B、一個后繼17C、多個前驅(qū)17D、多個后繼第三題、判斷題（每題1分，5道題共5分）1、連通網(wǎng)的最小生成樹是唯一的。 TOC o 1-5 h z r際正確錯誤2、Dijkstra算法是按路徑長度遞增的順序依次產(chǎn)生從某一固定源點到其他各頂點之間的最短路徑。rr正確錯誤3、圖的深度優(yōu)先遍歷算法類似于二叉樹的先序遍歷年r正確錯誤4、對稀疏圖，用Prim算法求最小生成樹較為合適r河正確錯誤5、若從無向圖的一個頂點出發(fā)進行深度優(yōu)先遍歷可訪問到圖中的所有頂點，則 該圖一定是連通圖。

12、rr正確錯誤數(shù)據(jù)結(jié)構(gòu)第07章在線測試數(shù)據(jù)結(jié)構(gòu)第07章在線測試剩余時間：42:32答題須知：1、本卷滿分20分。2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題（每題1分，5道題共5分） TOC o 1-5 h z 1、對線性表進行折半查找時，要求線性表必須。rrA、以順序方式存儲B、以鏈式方式存儲汗rC、以順序方式存儲且表中元素按關鍵字有序排列D、以鏈式方式存儲且表中元素按關鍵字有序排列2、用折半查找對長度為12的有序表進行查找，則等概率下查找成功時的平均查找長度為。A、35/12B、 3

13、7/12 TOC o 1-5 h z rrC、 39/12D、 43/123、用鏈地址法處理沖突構(gòu)造的散列表中，每個地址單元所鏈接的同義詞表的相同。rrA、關鍵字B、元素值汗rC、散列地址D、含義4、如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，可以采用查找方法。rrA、折半B、順序#rC、分塊D、散列5、哈希函數(shù)有一個性質(zhì)：函數(shù)值應按取其值域的每一個值。rrA、最小概率B、最大概率r河C、平均概率D、同等概率第二題、多項選擇題（每題2分，5道題共10分）1、構(gòu)造散列函數(shù)時通常考慮的因素有。匠A、計算函數(shù)的工作量B、關鍵字的長度C、散列表長D、關鍵字的分布情況2、下列關于n個結(jié)點的

14、m階B樹的說法中，正確的是。A、樹中每個結(jié)點最多有m個關鍵字B、樹中葉子結(jié)點的個數(shù)為n+1C、在B樹上進行查找的過程是順指針找結(jié)點和在結(jié)點內(nèi)找關鍵字交叉進行的過程。D、樹中所有葉子結(jié)點都在同一層，并且不帶任何信息E、樹中每個結(jié)點最多有m-1個關鍵字F、樹中每個結(jié)點最多有m+1個關鍵字3、影響散列表的平均查找長度的因素有。A、散列函數(shù)B、散列表長C、裝填因子D、處理沖突的方法4、在順序表的順序查找算法中，監(jiān)視哨的位置A、只能在表頭B、只能在表尾7C、可以在表頭7D、可以在表尾5、對序列50，72, 43, 85，75，20，35, 45，30按順序建二叉排序樹，則在樹中須比較3次方可查找成功的元

15、素有.A、50B、43C、85D、75E、20F、35G、45H、30第三題、判斷題（每題1分，5道題共5分）1、散列表的裝填因子越小，發(fā)生沖突的可能性越大。錯誤錯誤r錯誤錯誤正確2、折半查找和二叉排序樹查找的時間性能相同。r正確3、給出不同的輸入序列構(gòu)造二叉排序樹，一定得到不同的二叉排序樹。正確錯誤正確4、9階B樹中，除根以外的任意非終端結(jié)點中的關鍵字個數(shù)不少于4。&r正確錯誤5、在分塊查找中，對索引表的查找既可用順序查找法，也可用折半查找法。苻r(nóng)正確錯誤剩余時間：37:27數(shù)據(jù)結(jié)構(gòu)第08章在線測試 答題須知：1、本卷滿分20分。剩余時間：37:272、答完題后，請一定要單擊下面的“交卷”按

16、鈕交卷，否則無法記錄本試卷的成績。3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題(每題1分，5道題共5分)1、下列方法中，是穩(wěn)定的排序方法。 TOC o 1-5 h z a-rA、折半插入排序B、希爾排序rrC、快速排序D、堆排序2、一組記錄的關鍵字序列為46, 79, 56, 38, 40，84，則利用快速排序方法，以第一個記錄為樞軸得到的一次劃分結(jié)果是.底rA、 38， 40， 46， 56， 79， 84B、 40， 38， 46， 79， 56， 84C、 40， 38， 46， 56， 79， 84D、 40， 38， 46， 84， 56， 793、

17、在下列排序方法中，平均情況下占用內(nèi)存量最大的是 方法。r汗A、快速排序B、插入排序C、冒泡排序D、堆排序4、在下列排序方法中，在待排序的數(shù)據(jù)有序時，花費時間反而最多的是rrA、堆排序B、起泡排序底rC、快速排序。、插入排序5、對n個記錄的序列進行堆排序，最壞情況下的時間復雜度為。oA、O(logn)B、O(nlogn)rrC、O(n)D、O(n2)第二題、多項選擇題(每題2分，5道題共10分)1、下列排序方法中，是穩(wěn)定的排序方法。A、簡單選擇排序1B、起泡排序C、快速排序D、直接插入排序17E、折半插入排序2、在下列排序方法中，每一趟排序結(jié)束后都能選出一個元素放在其最終位置上的是A、簡單選擇排序17B、起泡排序17C、快速排序D、直接插入排序17E、堆排序3、下列排序方法中，空間復雜度為0(1)的排序方法有。A、堆排序B、快速排序C、直接插入排序D、冒泡排序4、下列排序方法中，在最壞情況下算法的時間復雜度為0(n”2)的有。A、堆排序17B、快速排序17C、希爾排序17D、