數(shù)據(jù)結(jié)構(gòu)智慧樹知到課后章節(jié)答案2023年下上海海洋大學(xué)

數(shù)據(jù)結(jié)構(gòu)智慧樹知到課后章節(jié)答案2023年下上海海洋大學(xué)上海海洋大學(xué)

第一章測試

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

A:數(shù)據(jù)結(jié)構(gòu)B:物理結(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ù)項

答案:數(shù)據(jù)元素

下面程序段的時間復(fù)雜度為：（）

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

答案:O（n）

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

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

答案:O（n2）

關(guān)于算法的說法錯誤的是（）

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

答案:算法就是程序

第二章測試

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

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

答案:n

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

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

答案:p->Link=p->Link->Link;

在等概率情況下，順序表的插入操作要移動（）表項。

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

答案:一半

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

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

答案:p->next=HL->next;HL->next=p;

對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）

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

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

第三章測試

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

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

答案:312

棧和隊列的共同特點是（）。

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

答案:只允許在端點處插入和刪除元素

設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。

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

答案:必須判別棧是否為空

向一個棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€s結(jié)點時，應(yīng)執(zhí)行（）。

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

答案:s->link=top;top=s;

在一個鏈?zhǔn)疥犃兄?，假定front和rear分別為隊頭和隊尾指針，則刪除一個結(jié)點的操作為（）。

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

答案:front=front->next

第四章測試

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

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進制表示。

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

答案:692

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

A:(x,(a,B))B:(a,B)C:AD:x

答案:x

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

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

答案:子串的第一個字符在主串中首次出現(xiàn)的位置

兩個字符串相等的充要條件是（）。

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

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

第五章測試

樹最適合用來表示（）。

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

答案:元素之間具有分支層次關(guān)系的數(shù)據(jù)

設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點的左子樹的結(jié)點數(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:229B:129C:189D:219

答案:229

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

A:2nB:2n+lC:2n-1D:n+l

答案:2n-1

線索二叉樹中，結(jié)點p沒有左子樹的充要條件是（）。

A:其余選項都不對B:p->ltag=1且p->LeftChild=NULLC:p->LeftChild=NULLD:p->ltag=1

答案:p->ltag=1

第六章測試

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

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

答案:5

對于無向圖G=(V,E),下列選項中，正確的是：（）

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

答案:當(dāng)∣V∣>∣E∣+1時，G一定是不連通的

若使用AOE網(wǎng)估算工程進度，則下列敘述中正確的是：（）

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

答案:關(guān)鍵路徑是從源點到匯點路徑長度最長的路徑

已知無向圖G如下所示，使用克魯斯卡爾（Kruskal）算法求圖G的最小生成樹，加入到最小生成樹中的邊依次是：（）

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

答案:(b,f),(b,d),(a,e),(c,e),(b,e)

對下圖從頂點C出發(fā)進行深度優(yōu)先搜索，哪個是錯誤的搜索序列？（）

A:CBADEFGHB:CDABEHFGC:CBAEFGHDD:CDAEHGFB

答案:CDABEHFG

給定有向圖如下。下列哪個選項不是對應(yīng)的拓撲序列？（）

A:aedfbcB:aedbfcC:abedfcD:abdfce

答案:abdfce

下圖所示的AOE網(wǎng)表示一項包含8個活動的工程。活動d的最早開始時間和最遲開始時間分別是：（）

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

答案:12和14

第七章測試

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

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

答案:4

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

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

答案:1.36

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

A:(d+1)/mB:d+1C:(d+1)%mD:d

答案:(d+1)%m

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

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

答案:7

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

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

答案:線性探查法、雙散列法、開散列法。

在一棵平衡二叉搜索樹中，每個結(jié)點的左子樹高度與右子樹高度之差的絕對值不超過（）。

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

答案:1

第八章測試

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

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

答案:歸并排序

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

A:將M劃分為n個部分，每個部分中僅含有一個元素B:將兩個有序表合并為一個新的有序表C:將M劃分為兩部分，一部分元素的值均小于另一部分元素的值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:301，892C:236，301D:485，301

答案:301，892

將序列{