鄭州大學遠程教育數(shù)據結構考試

1、數(shù)據結構第04章在線測試數(shù)據結構第04章在線測試剩余時間：43:12窗體頂端答題須知：1、本卷滿分20分。 2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。 3、在交卷之前，不要刷新本網頁，否則你的答題結果將會被清空。第一題、單項選擇題（每題1分，5道題共5分）1、若串Sabcdef，則其非空子串數(shù)目為。A、6B、12C、21D、222、字符串是一種特殊的線性表，其特殊性在于它的數(shù)據元素只能是。A、字符B、字符串C、數(shù)字D、字母3、設有三個串，s1How, s2 are, s3 you,則這三個串連接后得到的結果串是。A、HowareyouB、How are you

2、C、How are you.D、 How are you4、串是一種特殊的線性表，其特殊性體現(xiàn)在。A、可以順序存儲B、數(shù)據元素是一個字符C、可以鏈接存儲D、數(shù)據元素可以是多個字符5、空格串的長度為。A、0B、1C、串中空格的個數(shù)D、第二題、多項選擇題（每題2分，5道題共10分）1、在定長順序存儲表示中，對串長的表示方法有。A、用域變量表示B、用下標為0的數(shù)組分量表示C、在串值后加結束標記字符D、無法明確表示2、以下關于串的存儲方式的說法中正確的是。A、定長順序表示和堆分配表示都是串的順序存儲表示B、定長順序表示的串的存儲空間是編譯時預先分配的一個比較大的連續(xù)空間C、堆分配表示的串的存儲空間是在

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

4、是n個字母的有限序列（n0）。正確錯誤4、串是元素類型受限制的線性表。正確錯誤5、在C語言中，用動態(tài)分配函數(shù)進行管理的自由存儲區(qū)稱為“堆”。正確錯誤窗體底端數(shù)據結構第05章在線測試剩余時間：35:15窗體頂端答題須知：1、本卷滿分20分。 2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。 3、在交卷之前，不要刷新本網頁，否則你的答題結果將會被清空。第一題、單項選擇題（每題1分，5道題共5分）1、按照二叉樹的定義，具有3個結點的二叉樹有種形態(tài)。A、3B、4C、5D、62、樹最適合表示。A、有序數(shù)據元素B、無序數(shù)據元素C、元素之間具有分支層次關系的數(shù)據D、元素之間無聯(lián)系

5、的數(shù)據3、的同種順序的遍歷仍需要棧的支持。A、先序線索樹B、中序線索樹C、后序線索樹D、4、已知二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的先序遍歷序列是。A、acbedB、decabC、deabcD、cedba5、對于表達式(a-b+c)*d/(e+f),其前綴表達式為。錯A、/*+-abcd+efB、a-b+c*d/e+fC、/*-a+bcd+efD、ab-c+d*ef+/第二題、多項選擇題（每題2分，5道題共10分）1、下列關于完全二叉樹的敘述中，正確的有。A、完全二叉樹一定是滿二叉樹B、滿二叉樹一定是完全二叉樹C、完全二叉樹中要么沒有結點的度為1，要么只可能有一個

6、結點的度為1D、只有一個結點的度為1的二叉樹一定是完全二叉樹2、下列關于樹和二叉樹的敘述中，正確的有。A、森林和二叉樹之間可以相互轉換B、樹和二叉樹之間可以相互轉換C、二叉樹的子樹有左右之分，而樹的子樹沒有左右之分D、二叉樹結點的最大度數(shù)為2，而樹的結點的最大度數(shù)沒有限制3、森林的遍歷方式有A、先序遍歷B、中序遍歷C、后序遍歷D、層序遍歷4、先序序列和中序序列相同的二叉樹有。A、空二叉樹B、左單支樹C、右單支樹D、根樹5、將一個有50個結點的完全二叉樹按層序編號（根編號為1），則編號為 25的結點。A、有左孩子B、有右孩子C、無左孩子D、無右孩子第三題、判斷題（每題1分，5道題共5分）1、n個

7、葉子的Huffman樹共有2n-1個結點。正確錯誤2、二叉樹的先、中、后序遍歷序列中，葉子結點的相對順序不會發(fā)生改變。正確錯誤3、將一棵樹轉換成相應的二叉樹后，二叉樹的根結點肯定沒有左子樹。正確錯誤4、二叉樹的先序遍歷序列中，任意一個結點均處在其孩子結點的前面。正確錯誤5、給定二叉樹的先序和后序遍歷序列，可以唯一的確定這棵二叉樹。正確錯誤窗體底端數(shù)據結構第06章在線測試剩余時間：47:27窗體頂端答題須知：1、本卷滿分20分。 2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。 3、在交卷之前，不要刷新本網頁，否則你的答題結果將會被清空。第一題、單項選擇題（每題1分，

8、5道題共5分）1、一個有n個頂點的無向圖若是連通圖，則至少有條邊。A、n-1B、nC、n+1D、(n+1)/22、4個頂點的無向完全圖有條邊。錯A、6B、12C、16D、203、一個無向連通圖的生成樹是含有該連通圖所有頂點的。A、極大連通子圖B、極大子圖C、極小連通子圖D、極小子圖4、對，用克魯斯卡爾算法求最小生成樹較為合適。A、非連通圖B、連通圖C、稀疏圖D、稠密圖5、對，用Prim算法求最小生成樹較為合適。A、非連通圖B、連通圖C、稀疏圖D、稠密圖第二題、多項選擇題（每題2分，5道題共10分）1、如果對無向圖G必須進行二次廣度優(yōu)先遍歷才能訪問到圖中所有頂點，則下列說法中正確的是。A、G肯定

9、不是完全圖B、G肯定不是連通圖C、G中一定有回路D、G有兩個連通分量2、下列說法中正確的是。A、無向圖中的極大連通子圖稱為連通分量。B、圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點。C、圖的深度優(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算法是按路徑長度遞增的順序依次產生從某一固定源點到其

10、他各頂點之間的最短路徑。B、若僅求單一源點到某一特定頂點之間的最短路徑，則其算法的時間復雜度可以達到O(n)。C、求圖中每一對頂點間最短路徑的Floyd算法的時間復雜度為O(n3)。D、求圖中每一對頂點間的最短路徑也可用Dijkstra算法實現(xiàn)。5、有向圖中頂點之間關系的特征是：每個頂點可以有。A、一個前驅B、一個后繼C、多個前驅D、多個后繼第三題、判斷題（每題1分，5道題共5分）1、連通網的最小生成樹是唯一的。正確錯誤2、Dijkstra算法是按路徑長度遞增的順序依次產生從某一固定源點到其他各頂點之間的最短路徑。正確錯誤3、圖的深度優(yōu)先遍歷算法類似于二叉樹的先序遍歷正確錯誤4、對稀疏圖，用P

11、rim算法求最小生成樹較為合適正確錯誤5、若從無向圖的一個頂點出發(fā)進行深度優(yōu)先遍歷可訪問到圖中的所有頂點，則 該圖一定是連通圖。正確錯誤窗體底端數(shù)據結構第07章在線測試數(shù)據結構第07章在線測試剩余時間：42:32窗體頂端答題須知：1、本卷滿分20分。 2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。 3、在交卷之前，不要刷新本網頁，否則你的答題結果將會被清空。第一題、單項選擇題（每題1分，5道題共5分）1、對線性表進行折半查找時，要求線性表必須。A、以順序方式存儲B、以鏈式方式存儲C、以順序方式存儲且表中元素按關鍵字有序排列D、以鏈式方式存儲且表中元素按關鍵字有序排

12、列2、用折半查找對長度為12的有序表進行查找，則等概率下查找成功時的平均查找長度為。A、35/12B、37/12C、39/12D、43/123、用鏈地址法處理沖突構造的散列表中，每個地址單元所鏈接的同義詞表的相同。A、關鍵字B、元素值C、散列地址D、含義4、如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，可以采用查找方法。A、折半B、順序C、分塊D、散列5、哈希函數(shù)有一個性質：函數(shù)值應按取其值域的每一個值。A、最小概率B、最大概率C、平均概率D、同等概率第二題、多項選擇題（每題2分，5道題共10分）1、構造散列函數(shù)時通?？紤]的因素有。A、計算函數(shù)的工作量B、關鍵字的長度C、散列表長D

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

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

15、”按鈕交卷，否則無法記錄本試卷的成績。 3、在交卷之前，不要刷新本網頁，否則你的答題結果將會被清空。第一題、單項選擇題（每題1分，5道題共5分）1、下列方法中，是穩(wěn)定的排序方法。A、折半插入排序B、希爾排序C、快速排序D、堆排序2、一組記錄的關鍵字序列為46，79，56，38，40，84，則利用快速排序方法，以第一個記錄為樞軸得到的一次劃分結果是。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，793、在下列排序方法中，平均情況下占用內存量最大的是方法。A、快速排序B、插入排序C、冒泡排序D、堆

16、排序4、在下列排序方法中，在待排序的數(shù)據有序時, 花費時間反而最多的是。A、堆排序B、起泡排序C、快速排序D、插入排序5、對n個記錄的序列進行堆排序，最壞情況下的時間復雜度為。A、O(logn)B、O(nlogn)C、O(n)D、O(n2)第二題、多項選擇題（每題2分，5道題共10分）1、下列排序方法中，是穩(wěn)定的排序方法。A、簡單選擇排序B、起泡排序C、快速排序D、直接插入排序E、折半插入排序2、在下列排序方法中，每一趟排序結束后都能選出一個元素放在其最終位置上的是。A、簡單選擇排序B、起泡排序C、快速排序D、直接插入排序E、堆排序3、下列排序方法中，空間復雜度為O(1)的排序方法有。A、堆排序B、快速排序C、直接插入排序D、冒泡排序4、下列排序方法中，在最壞情況下算法的時間復雜度為O(n2)的有。A、堆排序B、快速排序C、希