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

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

數(shù)據(jù)的（）是面向計(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ù)元素下面程序段的時(shí)間復(fù)雜度為：（）

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

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

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

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

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

答案:算法就是程序

第二章單元測(cè)試

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

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

答案:n設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link），若要?jiǎng)h除單鏈表中指針p指向結(jié)點(diǎn)的后一個(gè)結(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;在等概率情況下，順序表的插入操作要移動(dòng)（）表項(xiàng)。

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

答案:一半在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針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;對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）

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

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

第三章單元測(cè)試

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

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

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

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

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

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

答案:必須判別棧是否為空向一個(gè)棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)s結(jié)點(diǎn)時(shí)，應(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;在一個(gè)鏈?zhǔn)疥?duì)列中，假定front和rear分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為（）。

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

答案:front=front->next

第四章單元測(cè)試

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

A:列號(hào)B:行號(hào)C:元素值D:非零元素個(gè)數(shù)

答案:列號(hào)設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn)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一個(gè)子串在包含它的主串中的位置是指（）。

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

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

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

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

第五章單元測(cè)試

樹(shù)最適合用來(lái)表示（）。

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

答案:元素之間具有分支層次關(guān)系的數(shù)據(jù)設(shè)F是由T1、T2和T3三棵樹(shù)組成的森林，與F對(duì)應(yīng)的二叉樹(shù)為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹(shù)B的根結(jié)點(diǎn)的左子樹(shù)的結(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)造一棵哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為（）。

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

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

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

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

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

答案:p->ltag=1

第六章單元測(cè)試

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

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

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

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

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

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

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

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)對(duì)下圖從頂點(diǎn)C出發(fā)進(jìn)行深度優(yōu)先搜索，哪個(gè)是錯(cuò)誤的搜索序列？（）

A:CBADEFGHB:CDABEHFGC:CBAEFGHDD:CDAEHGFB

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

A:abedfcB:abdfceC:aedbfcD:aedfbc

答案:abdfce下圖所示的AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程。活動(dòng)d的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間分別是：（）

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

答案:12和14

第七章單元測(cè)試

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

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

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

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

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

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

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

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

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

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

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

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

答案:1

第八章單元測(cè)試

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

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

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

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

答案:將兩個(gè)有序表合并為一個(gè)新的有序表設(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將序列{