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

1、 數(shù)據(jù)結(jié)構(gòu)第04章在線測試 數(shù)據(jù)結(jié)構(gòu)第04章在線測試剩余時間：43:12窗體頂端 答題須知：1、本卷滿分20分。           2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。           3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題（每題1分，5道題共5分） 1、若串S"

2、abcdef"，則其非空子串?dāng)?shù)目為。A、6B、12C、21D、22 2、字符串是一種特殊的線性表，其特殊性在于它的數(shù)據(jù)元素只能是。A、字符B、字符串C、數(shù)字D、字母 3、設(shè)有三個串，s1"How", s2" are", s3" you",則這三個串連接后得到的結(jié)果串是。A、"Howareyou"B、"How are you"C、"How are you."D、" How are you" 4、串是一種特殊的線性表，其

3、特殊性體現(xiàn)在。A、可以順序存儲B、數(shù)據(jù)元素是一個字符C、可以鏈接存儲D、數(shù)據(jù)元素可以是多個字符 5、空格串的長度為。A、0B、1C、串中空格的個數(shù)D、第二題、多項選擇題（每題2分，5道題共10分） 1、在定長順序存儲表示中，對串長的表示方法有。A、用域變量表示B、用下標(biāo)為0的數(shù)組分量表示C、在串值后加結(jié)束標(biāo)記字符D、無法明確表示 2、以下關(guān)于串的存儲方式的說法中正確的是。A、定長順序表示和堆分配表示都是串的順序存儲表示B、定長順序表示的串的存儲空間是編譯時預(yù)先分配的一個比較大的連續(xù)空間C、堆分配表示的串的存儲空間是在程序執(zhí)行過程中動態(tài)分配的D、堆分配存儲表示時的空

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

5、確錯誤 3、串是n個字母的有限序列（n0）。正確錯誤 4、串是元素類型受限制的線性表。正確錯誤 5、在C語言中，用動態(tài)分配函數(shù)進行管理的自由存儲區(qū)稱為“堆”。正確錯誤   窗體底端 數(shù)據(jù)結(jié)構(gòu)第05章在線測試剩余時間：35:15窗體頂端 答題須知：1、本卷滿分20分。           2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。    

6、0;      3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題（每題1分，5道題共5分） 1、按照二叉樹的定義，具有3個結(jié)點的二叉樹有種形態(tài)。A、3B、4C、5D、6 2、樹最適合表示。A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無聯(lián)系的數(shù)據(jù) 3、的同種順序的遍歷仍需要棧的支持。A、先序線索樹B、中序線索樹C、后序線索樹D、 4、已知二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的先序遍歷序列是。A、acbedB、deca

7、bC、deabcD、cedba 5、對于表達式(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、下列關(guān)于完全二叉樹的敘述中，正確的有。A、完全二叉樹一定是滿二叉樹B、滿二叉樹一定是完全二叉樹C、完全二叉樹中要么沒有結(jié)點的度為1，要么只可能有一個結(jié)點的度為1D、只有一個結(jié)點的度為1的二叉樹一定是完全二叉樹 2、下列關(guān)于樹和二叉樹的敘述中，正確的有。A、森林和二叉樹之間可以相互轉(zhuǎn)換B、樹和二叉樹之間可以相互轉(zhuǎn)換C、

8、二叉樹的子樹有左右之分，而樹的子樹沒有左右之分D、二叉樹結(jié)點的最大度數(shù)為2，而樹的結(jié)點的最大度數(shù)沒有限制 3、森林的遍歷方式有A、先序遍歷B、中序遍歷C、后序遍歷D、層序遍歷 4、先序序列和中序序列相同的二叉樹有。A、空二叉樹B、左單支樹C、右單支樹D、根樹 5、將一個有50個結(jié)點的完全二叉樹按層序編號（根編號為1），則編號為 25的結(jié)點。A、有左孩子B、有右孩子C、無左孩子D、無右孩子第三題、判斷題（每題1分，5道題共5分） 1、n個葉子的Huffman樹共有2n-1個結(jié)點。正確錯誤 2、二叉樹的先、中、后序遍歷序列中，葉子結(jié)點的相對順序不會

9、發(fā)生改變。正確錯誤 3、將一棵樹轉(zhuǎn)換成相應(yīng)的二叉樹后，二叉樹的根結(jié)點肯定沒有左子樹。正確錯誤 4、二叉樹的先序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。正確錯誤 5、給定二叉樹的先序和后序遍歷序列，可以唯一的確定這棵二叉樹。正確錯誤窗體底端數(shù)據(jù)結(jié)構(gòu)第06章在線測試剩余時間：47:27窗體頂端 答題須知：1、本卷滿分20分。           2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。  

10、0;        3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題（每題1分，5道題共5分） 1、一個有n個頂點的無向圖若是連通圖，則至少有條邊。A、n-1B、nC、n+1D、(n+1)/2 2、4個頂點的無向完全圖有條邊。錯A、6B、12C、16D、20 3、一個無向連通圖的生成樹是含有該連通圖所有頂點的。A、極大連通子圖B、極大子圖C、極小連通子圖D、極小子圖 4、對，用克魯斯卡爾算法求最小生成樹較為合適。A、非連通圖B、連通圖C、稀疏圖D、稠密圖&

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

12、頂點的無向連通圖的邊數(shù)為n(n-1)B、圖的廣度優(yōu)先遍歷過程是一個遞歸過程C、n個頂點的有向完全圖的弧數(shù)為n(n-1)D、有向圖的強連通分量是有向圖的極大強連通子圖 4、下列關(guān)于最短路徑的說法中，正確的有。A、Dijkstra算法是按路徑長度遞增的順序依次產(chǎn)生從某一固定源點到其他各頂點之間的最短路徑。B、若僅求單一源點到某一特定頂點之間的最短路徑，則其算法的時間復(fù)雜度可以達到O(n)。C、求圖中每一對頂點間最短路徑的Floyd算法的時間復(fù)雜度為O(n3)。D、求圖中每一對頂點間的最短路徑也可用Dijkstra算法實現(xiàn)。 5、有向圖中頂點之間關(guān)系的特征是：每個頂點可以有。A、

13、一個前驅(qū)B、一個后繼C、多個前驅(qū)D、多個后繼第三題、判斷題（每題1分，5道題共5分） 1、連通網(wǎng)的最小生成樹是唯一的。正確錯誤 2、Dijkstra算法是按路徑長度遞增的順序依次產(chǎn)生從某一固定源點到其他各頂點之間的最短路徑。正確錯誤 3、圖的深度優(yōu)先遍歷算法類似于二叉樹的先序遍歷正確錯誤 4、對稀疏圖，用Prim算法求最小生成樹較為合適正確錯誤 5、若從無向圖的一個頂點出發(fā)進行深度優(yōu)先遍歷可訪問到圖中的所有頂點，則 該圖一定是連通圖。正確錯誤窗體底端數(shù)據(jù)結(jié)構(gòu)第07章在線測試 數(shù)據(jù)結(jié)構(gòu)第07章在線測試剩余時間：42:32窗體頂端

14、0;答題須知：1、本卷滿分20分。           2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。           3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題（每題1分，5道題共5分） 1、對線性表進行折半查找時，要求線性表必須。A、以順序方式存儲B、以鏈?zhǔn)椒绞酱鎯、以順序方式存儲且表中元素按關(guān)鍵字有序排列D、以

15、鏈?zhǔn)椒绞酱鎯η冶碇性匕搓P(guān)鍵字有序排列 2、用折半查找對長度為12的有序表進行查找，則等概率下查找成功時的平均查找長度為。A、35/12B、37/12C、39/12D、43/12 3、用鏈地址法處理沖突構(gòu)造的散列表中，每個地址單元所鏈接的同義詞表的相同。A、關(guān)鍵字B、元素值C、散列地址D、含義 4、如果要求一個線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，可以采用查找方法。A、折半B、順序C、分塊D、散列 5、哈希函數(shù)有一個性質(zhì)：函數(shù)值應(yīng)按取其值域的每一個值。A、最小概率B、最大概率C、平均概率D、同等概率第二題、多項選擇題（每題2分，5道題共10分）&

16、#160;1、構(gòu)造散列函數(shù)時通常考慮的因素有。A、計算函數(shù)的工作量B、關(guān)鍵字的長度C、散列表長D、關(guān)鍵字的分布情況 2、下列關(guān)于n個結(jié)點的m階B樹的說法中，正確的是。A、樹中每個結(jié)點最多有m個關(guān)鍵字B、樹中葉子結(jié)點的個數(shù)為n+1C、在B樹上進行查找的過程是順指針找結(jié)點和在結(jié)點內(nèi)找關(guān)鍵字交叉進行的過程。D、樹中所有葉子結(jié)點都在同一層，并且不帶任何信息E、樹中每個結(jié)點最多有m-1個關(guān)鍵字F、樹中每個結(jié)點最多有m+1個關(guān)鍵字 3、影響散列表的平均查找長度的因素有。A、散列函數(shù)B、散列表長C、裝填因子D、處理沖突的方法 4、在順序表的順序查找算法中，監(jiān)視哨的位置。A、只能

17、在表頭B、只能在表尾C、可以在表頭D、可以在表尾 5、對序列50，72，43，85，75，20，35，45，30按順序建二叉排序樹，則在樹中須比較3次方可查找成功的元素有。A、50B、43C、85D、75E、20F、35G、45H、30第三題、判斷題（每題1分，5道題共5分） 1、散列表的裝填因子越小，發(fā)生沖突的可能性越大。正確錯誤 2、折半查找和二叉排序樹查找的時間性能相同。正確錯誤 3、給出不同的輸入序列構(gòu)造二叉排序樹，一定得到不同的二叉排序樹。正確錯誤 4、9階B樹中，除根以外的任意非終端結(jié)點中的關(guān)鍵字個數(shù)不少于4。正確錯誤 5

18、、在分塊查找中，對索引表的查找既可用順序查找法，也可用折半查找法。正確錯誤窗體底端 數(shù)據(jù)結(jié)構(gòu)第08章在線測試剩余時間：37:27窗體頂端 答題須知：1、本卷滿分20分。           2、答完題后，請一定要單擊下面的“交卷”按鈕交卷，否則無法記錄本試卷的成績。           3、在交卷之前，不要刷新本網(wǎng)頁，否則你的答題結(jié)果將會被清空。第一題、單項選擇題（每題1分，5

19、道題共5分） 1、下列方法中，是穩(wěn)定的排序方法。A、折半插入排序B、希爾排序C、快速排序D、堆排序 2、一組記錄的關(guān)鍵字序列為46，79，56，38，40，84，則利用快速排序方法，以第一個記錄為樞軸得到的一次劃分結(jié)果是。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79 3、在下列排序方法中，平均情況下占用內(nèi)存量最大的是方法。A、快速排序B、插入排序C、冒泡排序D、堆排序 4、在下列排序方法中，在待排序的數(shù)據(jù)有序時, 花費時間反而最多的是。A、堆排序B、起泡排序C、快速排序D、插