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

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

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

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

4、也有兩種存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。正確錯(cuò)誤3、串是 n 個(gè)字母的有限序列（n0）。正確錯(cuò)誤4、串是元素類型受限制的線性表。正確錯(cuò)誤5、在 C 語(yǔ)言中，用動(dòng)態(tài)分配函數(shù)進(jìn)行管理的自由存儲(chǔ)區(qū)稱為“堆”。正確錯(cuò)誤交卷數(shù)據(jù)結(jié)構(gòu)第05 章在線測(cè)試剩余時(shí)間： 35:15答題須知： 1、本卷滿分20 分。2 、答完題后，請(qǐng)一定要單擊下面的“交卷”按鈕交卷，否則無(wú)法記錄本試卷的成績(jī)。3 、在交卷之前，不要刷新本網(wǎng)頁(yè)，否則你的答題結(jié)果將會(huì)被清空。第一題、單項(xiàng)選擇題（每題1 分， 5道題共 5 分）1、按照二叉樹(shù)的定義，具有3 個(gè)結(jié)點(diǎn)的二叉樹(shù)有種形態(tài)。A、 3B、 4C、 5D、 62、樹(shù)最適合表示。A、有序數(shù)

5、據(jù)元素B、無(wú)序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無(wú)聯(lián)系的數(shù)據(jù)3、的同種順序的遍歷仍需要棧的支持。A、先序線索樹(shù)B、中序線索樹(shù)C、后序線索樹(shù)D、4、已知二叉樹(shù)的后序遍歷序列是dabec, 中序遍歷序列是debac, 則它的先序遍歷序列是。A、 acbedB、 decabC、 deabcD、 cedba5、對(duì)于表達(dá)式 (a-b+c)*d/(e+f),其前綴表達(dá)式為。錯(cuò)A、 /*+-abcd+efB、 a-b+c*d/e+fC、 /*-a+bcd+efD、 ab-c+d*ef+/第二題、多項(xiàng)選擇題（每題2 分， 5 道題共 10 分）1、下列關(guān)于完全二叉樹(shù)的敘述中，正確的有。A、

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

7、25 的結(jié)點(diǎn)。A、有左孩子B、有右孩子C、無(wú)左孩子D、無(wú)右孩子第三題、判斷題（每題1 分， 5 道題共 5 分）1、 n 個(gè)葉子的 Huffman 樹(shù)共有 2n-1 個(gè)結(jié)點(diǎn)。正確錯(cuò)誤2、二叉樹(shù)的先、中、后序遍歷序列中，葉子結(jié)點(diǎn)的相對(duì)順序不會(huì)發(fā)生改變。正確錯(cuò)誤3、將一棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)后，二叉樹(shù)的根結(jié)點(diǎn)肯定沒(méi)有左子樹(shù)。正確錯(cuò)誤4、二叉樹(shù)的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。正確錯(cuò)誤5、給定二叉樹(shù)的先序和后序遍歷序列，可以唯一的確定這棵二叉樹(shù)。正確錯(cuò)誤答題須知：數(shù)據(jù)結(jié)構(gòu)第06 章在線測(cè)試1、本卷滿分20 分。剩余時(shí)間：47:272 、答完題后，請(qǐng)一定要單擊下面的“交卷”按鈕交卷

8、，否則無(wú)法記錄本試卷的成績(jī)。3 、在交卷之前，不要刷新本網(wǎng)頁(yè)，否則你的答題結(jié)果將會(huì)被清空。第一題、單項(xiàng)選擇題（每題1 分， 5 道題共 5 分）1、一個(gè)有 n 個(gè)頂點(diǎn)的無(wú)向圖若是連通圖，則至少有條邊。A、 n-1B、 nC、 n+1D、 (n+1)/22、 4 個(gè)頂點(diǎn)的無(wú)向完全圖有條邊。錯(cuò)A、 6B、 12C、 16D、 203、一個(gè)無(wú)向連通圖的生成樹(shù)是含有該連通圖所有頂點(diǎn)的。A、極大連通子圖B、極大子圖C、極小連通子圖D、極小子圖4、對(duì)，用克魯斯卡爾算法求最小生成樹(shù)較為合適。A、非連通圖B、連通圖C、稀疏圖D、稠密圖5、對(duì)，用Prim 算法求最小生成樹(shù)較為合適。A、非連通圖B、連通圖C、稀疏

9、圖D、稠密圖第二題、多項(xiàng)選擇題（每題2 分， 5 道題共 10 分）1、如果對(duì)無(wú)向圖G必須進(jìn)行二次廣度優(yōu)先遍歷才能訪問(wèn)到圖中所有頂點(diǎn)，則下列說(shuō)法中正確的是。A、 G肯定不是完全圖B、 G肯定不是連通圖C、 G中一定有回路D、 G有兩個(gè)連通分量2、下列說(shuō)法中正確的是。A、無(wú)向圖中的極大連通子圖稱為連通分量。B、圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)。C、圖的深度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)。D、有向圖的遍歷不能采用廣度優(yōu)先搜索方法。3、下列說(shuō)法中不正確的有。A、 n 個(gè)頂點(diǎn)的無(wú)向連通圖的邊數(shù)為n(n-1)B、圖的廣度優(yōu)先遍歷過(guò)程是一個(gè)遞歸過(guò)程C、 n 個(gè)頂點(diǎn)的有向完

10、全圖的弧數(shù)為n(n-1)D、有向圖的強(qiáng)連通分量是有向圖的極大強(qiáng)連通子圖4、下列關(guān)于最短路徑的說(shuō)法中，正確的有。A、 Dijkstra算法是按路徑長(zhǎng)度遞增的順序依次產(chǎn)生從某一固定源點(diǎn)到其他各頂點(diǎn)之間的最短路徑。B、若僅求單一源點(diǎn)到某一特定頂點(diǎn)之間的最短路徑，則其算法的時(shí)間復(fù)雜度可以達(dá)到O(n) 。C、求圖中每一對(duì)頂點(diǎn)間最短路徑的Floyd 算法的時(shí)間復(fù)雜度為O(n3) 。D、求圖中每一對(duì)頂點(diǎn)間的最短路徑也可用Dijkstra算法實(shí)現(xiàn)。5、有向圖中頂點(diǎn)之間關(guān)系的特征是：每個(gè)頂點(diǎn)可以有。A、一個(gè)前驅(qū)B、一個(gè)后繼C、多個(gè)前驅(qū)D、多個(gè)后繼第三題、判斷題（每題 1 分， 5 道題共 5分）1、連通網(wǎng)的最小

11、生成樹(shù)是唯一的。正確錯(cuò)誤2、 Dijkstra 算法是按路徑長(zhǎng)度遞增的順序依次產(chǎn)生從某一固定源點(diǎn)到其他各頂點(diǎn)之間的最短路徑。正確錯(cuò)誤3、圖的深度優(yōu)先遍歷算法類似于二叉樹(shù)的先序遍歷正確錯(cuò)誤4、對(duì)稀疏圖，用 Prim 算法求最小生成樹(shù)較為合適正確錯(cuò)誤5、若從無(wú)向圖的一個(gè)頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷可訪問(wèn)到圖中的所有頂點(diǎn)，則該圖一定是連通圖。正確錯(cuò)誤數(shù)據(jù)結(jié)構(gòu)第07 章在線測(cè)試數(shù)據(jù)結(jié)構(gòu)第07 章在線測(cè)試剩余時(shí)間： 42:32答題須知： 1、本卷滿分20 分。2 、答完題后，請(qǐng)一定要單擊下面的“交卷”按鈕交卷，否則無(wú)法記錄本試卷的成績(jī)。3 、在交卷之前，不要刷新本網(wǎng)頁(yè)，否則你的答題結(jié)果將會(huì)被清空。第一題、單

12、項(xiàng)選擇題（每題1 分， 5 道題共5 分）1、對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須。A、以順序方式存儲(chǔ)B、以鏈?zhǔn)椒绞酱鎯?chǔ)C、以順序方式存儲(chǔ)且表中元素按關(guān)鍵字有序排列D、以鏈?zhǔn)椒绞酱鎯?chǔ)且表中元素按關(guān)鍵字有序排列2、用折半查找對(duì)長(zhǎng)度為12 的有序表進(jìn)行查找，則等概率下查找成功時(shí)的平均查找長(zhǎng)度為。A、 35/12B、 37/12C、 39/12D、 43/123、用鏈地址法處理沖突構(gòu)造的散列表中，每個(gè)地址單元所鏈接的同義詞表的相同。A、關(guān)鍵字B、元素值C、散列地址D、含義4、如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用查找方法。A、折半B、順序C、分塊D、散列5、哈希函數(shù)有一

13、個(gè)性質(zhì)：函數(shù)值應(yīng)按取其值域的每一個(gè)值。A、最小概率B、最大概率C、平均概率D、同等概率第二題、多項(xiàng)選擇題（每題2 分， 5道題共 10 分）1、構(gòu)造散列函數(shù)時(shí)通常考慮的因素有。A、計(jì)算函數(shù)的工作量B、關(guān)鍵字的長(zhǎng)度C、散列表長(zhǎng)D、關(guān)鍵字的分布情況2、下列關(guān)于n 個(gè)結(jié)點(diǎn)的m階 B 樹(shù)的說(shuō)法中，正確的是。A、樹(shù)中每個(gè)結(jié)點(diǎn)最多有m個(gè)關(guān)鍵字B、樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)為n+1C、在 B 樹(shù)上進(jìn)行查找的過(guò)程是順指針找結(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)找關(guān)鍵字交叉進(jìn)行的過(guò)程。D、樹(shù)中所有葉子結(jié)點(diǎn)都在同一層，并且不帶任何信息E、樹(shù)中每個(gè)結(jié)點(diǎn)最多有m-1 個(gè)關(guān)鍵字F、樹(shù)中每個(gè)結(jié)點(diǎn)最多有m+1個(gè)關(guān)鍵字3、影響散列表的平均查找長(zhǎng)度的因素有。

14、A、散列函數(shù)B、散列表長(zhǎng)C、裝填因子D、處理沖突的方法4、在順序表的順序查找算法中，監(jiān)視哨的位置。A、只能在表頭B、只能在表尾C、可以在表頭D、可以在表尾5、對(duì)序列 50 ，72，43，85， 75，20，35，45，30 按順序建二叉排序樹(shù)，則在樹(shù)中須比較3 次方可查找成功的元素有。A、 50B、 43C、 85D、 75E、 20F、 35G、 45H、 30第三題、判斷題（每題 1 分， 5道題共 5 分）1、散列表的裝填因子越小，發(fā)生沖突的可能性越大。正確錯(cuò)誤2、折半查找和二叉排序樹(shù)查找的時(shí)間性能相同。正確錯(cuò)誤3、給出不同的輸入序列構(gòu)造二叉排序樹(shù)，一定得到不同的二叉排序樹(shù)。正確錯(cuò)誤4、

15、 9 階 B 樹(shù)中，除根以外的任意非終端結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)不少于4。正確錯(cuò)誤5、在分塊查找中，對(duì)索引表的查找既可用順序查找法，也可用折半查找法。正確錯(cuò)誤數(shù)據(jù)結(jié)構(gòu)第08 章在線測(cè)試剩余時(shí)間：37:27答題須知： 1、本卷滿分20 分。2 、答完題后，請(qǐng)一定要單擊下面的“交卷”按鈕交卷，否則無(wú)法記錄本試卷的成績(jī)。3 、在交卷之前，不要刷新本網(wǎng)頁(yè)，否則你的答題結(jié)果將會(huì)被清空。第一題、單項(xiàng)選擇題（每題1 分， 5 道題共 5 分）1、下列方法中，是穩(wěn)定的排序方法。A、折半插入排序B、希爾排序C、快速排序D、堆排序2、一組記錄的關(guān)鍵字序列為46 ，79，56，38，40，84 ，則利用快速排序方法， 以

16、第一個(gè)記錄為樞軸得到的一次劃分結(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， 793、在下列排序方法中，平均情況下占用內(nèi)存量最大的是方法。A、快速排序B、插入排序C、冒泡排序D、堆排序4、在下列排序方法中，在待排序的數(shù)據(jù)有序時(shí),花費(fèi)時(shí)間反而最多的是。A、堆排序B、起泡排序C、快速排序D、插入排序5、對(duì) n 個(gè)記錄的序列進(jìn)行堆排序，最壞情況下的時(shí)間復(fù)雜度為。A、 O(logn)B、O(nlogn)C、 O(n)D、O(n2)第二題、多項(xiàng)選擇題（每題2 分， 5 道題共 10 分）1、下列排序方法中，是穩(wěn)定的排序方法。A、簡(jiǎn)單選擇排序B、起泡排序C、快速排序D、直接插入排序E、折半插入排序2、在下列排序方法中，每一趟排序結(jié)束后都能選出一個(gè)元素放在其最終位置上的是。A、簡(jiǎn)單選擇排序B、起泡排序C、快速排序D、直接插入排序E、堆排序3、下列排序方法中，空間復(fù)雜度為O(1) 的排序方法有。A、堆排序B、快速排序C、直接插入排序D、冒泡排序4、下列排序方法中，在最壞情況下算法的時(shí)間復(fù)雜度為O(n2) 的有。A、堆排序B、