數(shù)據(jù)結(jié)構(gòu)知到智慧樹章節(jié)測試課后答案2024年秋上海海洋大學(xué)第一章單元測試

數(shù)據(jù)的（）是面向計算機(jī)的。

A:線性結(jié)構(gòu)B:數(shù)據(jù)結(jié)構(gòu)C:邏輯結(jié)構(gòu)D:物理結(jié)構(gòu)

答案:物理結(jié)構(gòu)（）是組成數(shù)據(jù)的基本單位。

A:數(shù)據(jù)類型B:數(shù)據(jù)元素C:抽象數(shù)據(jù)類型D:數(shù)據(jù)項(xiàng)

答案:數(shù)據(jù)元素下面程序段的時間復(fù)雜度為：（）

A:O（n!）B:O（n2）C:O（1）D:O（n）

答案:O（n）一個算法的時間復(fù)雜度為（5n3+2nlog2n+4n+11）/（5n），其數(shù)量級表示為：（）

A:O（n2）B:O（log2n）C:O（n）D:O（nlog2n）

答案:O（n2）關(guān)于算法的說法錯誤的是（）

A:算法就是程序B:算法分析的主要目的是評價算法的效率C:算法必須在有限次數(shù)內(nèi)完成D:算法應(yīng)該具有確定性

答案:算法就是程序

第二章單元測試

從一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時，在查找不成功的情況下，需比較（）個元素結(jié)點(diǎn)。

A:nB:（n-1）/2C:n/2D:（n+1）/2

答案:n設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link），若要刪除單鏈表中指針p指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)（若存在），則需修改指針的操作為（）。

A:p=p->Link->Link;B:p=p->Link;C:p->Link=p->Link->Link;D:p->Link=p;

答案:p->Link=p->Link->Link;在等概率情況下，順序表的插入操作要移動（）表項(xiàng)。

A:全部B:一半C:三分之一D:四分之一

答案:一半在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。

A:p->next=HL;p=HL;B:HL=p;p->next=HL;C:p->next=HL;HL=p;D:p->next=HL->next;HL->next=p;

答案:p->next=HL->next;HL->next=p;對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）

A:表中元素的個數(shù)不變B:經(jīng)常需要隨機(jī)地存取元素C:經(jīng)常需要進(jìn)行插入和刪除操作D:表中元素需要占據(jù)一片連續(xù)的存儲空間

答案:經(jīng)常需要進(jìn)行插入和刪除操作

第三章單元測試

一個棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是（）

A:123B:321C:312D:231

答案:312棧和隊(duì)列的共同特點(diǎn)是（）。

A:都是先進(jìn)后出B:沒有共同點(diǎn)C:只允許在端點(diǎn)處插入和刪除元素D:都是先進(jìn)先出

答案:只允許在端點(diǎn)處插入和刪除元素設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。

A:對棧不作任何判別B:必須判別棧是否為空C:判別棧元素的類型D:必須判別棧是否為滿

答案:必須判別棧是否為空向一個棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€s結(jié)點(diǎn)時，應(yīng)執(zhí)行（）。

A:s->link=top->link;top->link=s;B:s->link=top;top=top->link;C:s->link=top;top=s;D:top->link=s;

答案:s->link=top;top=s;在一個鏈?zhǔn)疥?duì)列中，假定front和rear分別為隊(duì)頭和隊(duì)尾指針，則刪除一個結(jié)點(diǎn)的操作為（）。

A:front=rear->nextB:rear=rear->nextC:front=front->nextD:rear=front->next

答案:front=front->next

第四章單元測試

在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點(diǎn)都具有相同的（）。

A:列號B:行號C:元素值D:非零元素個數(shù)

答案:列號設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？（）腳注(10)表示用10進(jìn)制表示。

A:696B:688C:692D:678

答案:692廣義表A=((x,(a,B)),(x,(a,B),y))，則運(yùn)算head(head(tail(A)))的結(jié)果為（）。

A:(x,(a,B))B:AC:xD:(a,B)

答案:x一個子串在包含它的主串中的位置是指（）。

A:子串的第一個字符在主串中的位置B:子串的最后那個字符在主串中首次出現(xiàn)的位置C:子串的第一個字符在主串中首次出現(xiàn)的位置D:子串的最后那個字符在主串中的位置

答案:子串的第一個字符在主串中首次出現(xiàn)的位置兩個字符串相等的充要條件是（）。

A:同時具備(A)和(B)兩個條件B:其余選項(xiàng)答案都不對C:兩個字符串中對應(yīng)位置上的字符相等D:兩個字符串的長度相等

答案:同時具備(A)和(B)兩個條件

第五章單元測試

樹最適合用來表示（）。

A:有序數(shù)據(jù)元素B:元素之間無聯(lián)系的數(shù)據(jù)C:元素之間具有分支層次關(guān)系的數(shù)據(jù)D:無序數(shù)據(jù)元素

答案:元素之間具有分支層次關(guān)系的數(shù)據(jù)設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為（）。

A:N2-1B:N1-1C:N1+N3D:N2+N3

答案:N1-1設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（）。

A:129B:229C:219D:189

答案:22910.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（）個結(jié)點(diǎn)。

A:2n-1B:2n+lC:n+lD:2n

答案:2n-1線索二叉樹中，結(jié)點(diǎn)p沒有左子樹的充要條件是（）。

A:p->LeftChild=NULLB:其余選項(xiàng)都不對C:p->ltag=1且p->LeftChild=NULLD:p->ltag=1

答案:p->ltag=1

第六章單元測試

設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（）條邊才能確保是一個連通圖。

A:8B:5C:7D:6

答案:5對于無向圖G=(V,E),下列選項(xiàng)中，正確的是：（）

A:當(dāng)∣V∣>∣E∣時，G一定是連通的B:當(dāng)∣V∣=∣E∣?1時，G一定是不連通的C:當(dāng)∣V∣>∣E∣+1時，G一定是不連通的D:當(dāng)∣V∣<∣E∣時，G一定是連通的

答案:當(dāng)∣V∣>∣E∣+1時，G一定是不連通的若使用AOE網(wǎng)估算工程進(jìn)度，則下列敘述中正確的是：（）

A:縮短任一關(guān)鍵活動的時間將會縮短工程的工期B:關(guān)鍵路徑是從源點(diǎn)到匯點(diǎn)路徑長度最長的路徑C:關(guān)鍵路徑是從源點(diǎn)到匯點(diǎn)邊數(shù)最多的一條路徑D:增加任一關(guān)鍵活動的時間不會延長工程的工期

答案:關(guān)鍵路徑是從源點(diǎn)到匯點(diǎn)路徑長度最長的路徑已知無向圖G如下所示，使用克魯斯卡爾（Kruskal）算法求圖G的最小生成樹，加入到最小生成樹中的邊依次是：（）

A:(a,e),(b,e),(c,e),(b,d),(b,f)B:(a,e),(c,e),(b,e),(b,f),(b,d)C:(b,f),(b,d),(a,e),(c,e),(b,e)D:(b,f),(b,d),(b,e),(a,e),(c,e)

答案:(b,f),(b,d),(a,e),(c,e),(b,e)對下圖從頂點(diǎn)C出發(fā)進(jìn)行深度優(yōu)先搜索，哪個是錯誤的搜索序列？（）

A:CBADEFGHB:CDABEHFGC:CBAEFGHDD:CDAEHGFB

答案:CDABEHFG給定有向圖如下。下列哪個選項(xiàng)不是對應(yīng)的拓?fù)湫蛄校浚ǎ?/p>

A:abedfcB:abdfceC:aedbfcD:aedfbc

答案:abdfce下圖所示的AOE網(wǎng)表示一項(xiàng)包含8個活動的工程?；顒觗的最早開始時間和最遲開始時間分別是：（）

A:12和12B:12和14C:3和7D:15和15

答案:12和14

第七章單元測試

對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個，

A:3B:1C:4D:2

答案:4已知線性表的關(guān)鍵字集合{21，11，13，25，48，6，39，83，30，96，108}，散列函數(shù)為h(key)=key%11，采用分離鏈接法解決沖突。則成功查找的平均查找長度為（）

A:1.36B:2.36C:1.27D:1.18

答案:1.36若根據(jù)關(guān)鍵碼建立長度為m的散列表，采用線性探測法處理沖突，假定對一個元素第一次計算的散列地址為d，則下一次的哈希地址為（）。

A:(d+1)%mB:dC:d+1D:(d+1)/m

答案:(d+1)%m用二分查找從100個有序整數(shù)中查找某數(shù)，最壞情況下需要比較的次數(shù)是：（）

A:7B:50C:99D:10

答案:7解決散列法中出現(xiàn)的沖突問題常采用的方法是（）。

A:數(shù)字分析法、除留余數(shù)法、線性探查法。B:數(shù)字分析法、線性探查法、雙散列法。C:線性探查法、雙散列法、開散列法。D:數(shù)字分析法、除留余數(shù)法、平方取中法。

答案:線性探查法、雙散列法、開散列法。在一棵平衡二叉搜索樹中，每個結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對值不超過（）。

A:2B:0C:3D:1

答案:1

第八章單元測試

平均時間復(fù)雜度為O(nlogn)且穩(wěn)定的排序算法是（）。

A:桶排序B:歸并排序C:快速排序D:選擇排序

答案:歸并排序使用二路歸并排序?qū)琻個元素的數(shù)組M進(jìn)行排序時，二路歸并操作的功能是：（）

A:將M劃分為n個部分，每個部分中僅含有一個元素B:將M劃分為兩部分，一部分元素的值均小于另一部分元素的值C:將兩個有序表合并為一個新的有序表D:將M劃分為兩部分，兩部分的元素個數(shù)大致相等

答案:將兩個有序表合并為一個新的有序表設(shè)數(shù)組S[]={93,946,372,9,146,151,301,485,236,327,43,892}，采用最低位優(yōu)先（LSD）基數(shù)排序?qū)排列成升序序列。第1趟分配、收集后，元素372之前、之后緊鄰的元素分別是：（）

A:43，892B:485，301C:301，892D:236，301

答案:301，892將序列{