鄭州大學(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、若串S"

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

3、特殊性體現(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è)比較大的連續(xù)空間C、堆分配表示的串的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配的D、堆分配存儲(chǔ)表示時(shí)的空

4、串不占用連續(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、串也有兩種存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。正

5、確錯(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ī)。    

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

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

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

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

10、0;        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)/2 2、4個(gè)頂點(diǎn)的無(wú)向完全圖有條邊。錯(cuò)A、6B、12C、16D、20 3、一個(gè)無(wú)向連通圖的生成樹是含有該連通圖所有頂點(diǎn)的。A、極大連通子圖B、極大子圖C、極小連通子圖D、極小子圖 4、對(duì)，用克魯斯卡爾算法求最小生成樹較為合適。A、非連通圖B、連通圖C、稀疏圖D、稠密圖&

11、#160;5、對(duì)，用Prim算法求最小生成樹較為合適。A、非連通圖B、連通圖C、稀疏圖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è)

12、頂點(diǎn)的無(wú)向連通圖的邊數(shù)為n(n-1)B、圖的廣度優(yōu)先遍歷過(guò)程是一個(gè)遞歸過(guò)程C、n個(gè)頂點(diǎn)的有向完全圖的弧數(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、

13、一個(gè)前驅(qū)B、一個(gè)后繼C、多個(gè)前驅(qū)D、多個(gè)后繼第三題、判斷題（每題1分，5道題共5分） 1、連通網(wǎng)的最小生成樹是唯一的。正確錯(cuò)誤 2、Dijkstra算法是按路徑長(zhǎng)度遞增的順序依次產(chǎn)生從某一固定源點(diǎn)到其他各頂點(diǎn)之間的最短路徑。正確錯(cuò)誤 3、圖的深度優(yōu)先遍歷算法類似于二叉樹的先序遍歷正確錯(cuò)誤 4、對(duì)稀疏圖，用Prim算法求最小生成樹較為合適正確錯(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窗體頂端

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

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

16、#160;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樹的說(shuō)法中，正確的是。A、樹中每個(gè)結(jié)點(diǎn)最多有m個(gè)關(guān)鍵字B、樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為n+1C、在B樹上進(jìn)行查找的過(guò)程是順指針找結(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)找關(guān)鍵字交叉進(jìn)行的過(guò)程。D、樹中所有葉子結(jié)點(diǎn)都在同一層，并且不帶任何信息E、樹中每個(gè)結(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字F、樹中每個(gè)結(jié)點(diǎn)最多有m+1個(gè)關(guān)鍵字 3、影響散列表的平均查找長(zhǎng)度的因素有。A、散列函數(shù)B、散列表長(zhǎng)C、裝填因子D、處理沖突的方法 4、在順序表的順序查找算法中，監(jiān)視哨的位置。A、只能

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

18、、在分塊查找中，對(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

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