數(shù)據(jù)結(jié)構(gòu)智慧樹知到期末考試答案章節(jié)答案2024年上海海洋大學(xué)

數(shù)據(jù)結(jié)構(gòu)智慧樹知到期末考試答案+章節(jié)答案2024年上海海洋大學(xué)堆是完全二叉樹，完全二叉樹不一定是堆。（）

答案:對快速排序是排序算法中平均性能最好的一種排序。（）

答案:對如果兩個關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關(guān)鍵字為同義詞。（）

答案:對非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（）

答案:對設(shè)某堆中有n個結(jié)點(diǎn)，則在該堆中插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(log2n)。（）

答案:對設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時間復(fù)雜度為O(nlog2n)。（）

答案:錯已知一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）

答案:錯不論是入隊(duì)列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（）

答案:對設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（）。

答案:q=p->next；p->data=q->data；p->next=q->next；free(q)；對一棵二叉搜索樹進(jìn)行（）遍歷時，得到的結(jié)點(diǎn)序列是一個有序序列。

答案:中序（）是有獨(dú)立含義的最小單位，

答案:數(shù)據(jù)項(xiàng)在一個具有n個單元的順序棧中，假定用top==n表示?？?，則向這個棧插入一個元素時，首先應(yīng)執(zhí)行（）語句修改top指針。

答案:top--假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（）。

答案:5在具有n個單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為（）。

答案:rear==front數(shù)組就是矩陣，矩陣就是數(shù)組，這種說法（）。

答案:錯誤設(shè)散列空間為０到ｍ－１，ｋ為表項(xiàng)的關(guān)鍵碼，散列函數(shù)采用除留余數(shù)法，即Hash（k）=k%p。為了減少發(fā)生沖突的頻率，一般取p為（）。

答案:小于m的最大質(zhì)數(shù)在閉散列表中，散列到同一個地址而引起的“堆積”問題是由于（）引起的。

答案:同義詞或非同義詞之間發(fā)生沖突。在一個具有n個頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量的大小至少為（）。

答案:n我們用一個有向圖來表示航空公司所有航班的航線。下列哪種算法最適合解決找給定兩城市間最經(jīng)濟(jì)的飛行路線問題？（）

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

答案:p->Link=m->Link->Link;下面程序的時間復(fù)雜為（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}

答案:O(n2)假定對長度n=50的有序表進(jìn)行折半查找，則對應(yīng)的樹高度為（）。

答案:6設(shè)某無向圖中有n個頂點(diǎn)e條邊，則建立該圖鄰接表的時間復(fù)雜度為（）。

答案:O(n+e)用順序存儲的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R[1..n]，結(jié)點(diǎn)R[i]若有左孩子，其左孩子的編號為結(jié)點(diǎn)（）。

答案:R[2i]設(shè)用鏈表作為棧的存儲結(jié)構(gòu)，退棧操作（）。

答案:必須判別棧是否為空設(shè)某哈夫曼樹中有199個結(jié)點(diǎn)，則該哈夫曼樹中有（）個葉子結(jié)點(diǎn)。

答案:100數(shù)據(jù)結(jié)構(gòu)形式地定義為（D,S），其中D是數(shù)據(jù)元素的有限集合，S是D上的（）的有限集合。

答案:關(guān)系對一個長度為10的排好序的表用二分法查找，若查找不成功，至少需要比較的次數(shù)是（）。

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

答案:子串的第一個字符在主串中首次出現(xiàn)的位置對于一個具有n個頂點(diǎn)的無向連通圖，它包含的連通分量的個數(shù)為（）。

答案:1從具有n個結(jié)點(diǎn)的二叉搜索樹中查找一個元素時，在最壞情況下的時間復(fù)雜度為（）。

答案:O(n)棧的插入和刪除操作在（）進(jìn)行。

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

答案:將兩個有序表合并為一個新的有序表設(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ù)為（）。

答案:N1-1樹最適合用來表示（）。

答案:元素之間具有分支層次關(guān)系的數(shù)據(jù)一個子串在包含它的主串中的位置是指（）。

答案:子串的第一個字符在主串中首次出現(xiàn)的位置棧和隊(duì)列的共同特點(diǎn)是（）。

答案:只允許在端點(diǎn)處插入和刪除元素在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。

答案:p->next=HL->next;HL->next=p;中序遍歷一棵二叉排序樹可以得到一個有序的序列。（）

答案:對稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（）

答案:對子串“ABC”在主串“AABCABCD”中的位置為2。（）

答案:對層次遍歷初始堆可以得到一個有序的序列。（）

答案:錯圖的深度優(yōu)先遍歷算法中需要設(shè)置一個標(biāo)志數(shù)組，以便區(qū)分圖中的每個頂點(diǎn)是否被訪問過。（）

答案:對線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（）

答案:錯有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個數(shù)不一定相等。（）

答案:錯在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并保持該表有序的時間復(fù)雜度是（）。

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

答案:1采用開散列法解決沖突時，每一個散列地址所鏈接的同義詞表中各個表項(xiàng)的（）相同。

答案:散列地址設(shè)有一個已排序的線性表（長度>=２），分別用順序查找法和二分查找法找一個與K相等的元素，比較的次數(shù)分別是S和B，在查找不成功的情況下，S和B的關(guān)系是（）。

答案:S>=B在一棵高度平衡二叉搜索樹中，每個結(jié)點(diǎn)的平衡因子的取值范圍是（）。

答案:-11（）排序方法能夠每次使無序表中的第一個記錄插入到有序表中。

答案:直接插入設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。

答案:任一結(jié)點(diǎn)無右孩子稀疏矩陣可以采用（）的壓縮存儲方法。

答案:三元組設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（）。

答案:rear->next=s；rear=s；對于順序存儲的線性表，其算法的時間復(fù)雜度為O(1)的運(yùn)算應(yīng)是（）。

答案:查找第i個元素（1≤i≤n）在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個，度為2的結(jié)點(diǎn)數(shù)為1個，度為1的結(jié)點(diǎn)數(shù)為2個，則度為0的結(jié)點(diǎn)數(shù)為（）個。

答案:6非空的循環(huán)單鏈表first的尾結(jié)點(diǎn)（由p所指向）滿足：（）

答案:p->link==first；假定一個順序表的長度為40，并假定查找每個元素的概率都相同，則在查找不成功情況下的平均查找長度（）。

答案:41由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。

答案:53設(shè)二維數(shù)組A[0…m-1][0…n-1]按行優(yōu)先順序存儲在內(nèi)存中，第一個元素的地址為p，每個元素占k個字節(jié)，則元素aij的地址為（）。

答案:p+[i*n+j]*k設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為（）。

答案:10，15，14，18，20，36，40，21設(shè)有廣義表D=(a,b,D)，其深度為（）。

答案:無窮大假定一組記錄為(46,74,53,14,26,38,86,65,27,34)，對其進(jìn)行希爾排序，第一趟間隔為3，得到的排序結(jié)果為（）。

答案:14,26,27,34,65,38,46,74,53,86（）由某一數(shù)據(jù)元素的集合以及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成。

答案:數(shù)據(jù)結(jié)構(gòu)（）中的各個數(shù)據(jù)成員不在一個線性序列中，數(shù)據(jù)元素成員可能與零個或多個其他數(shù)據(jù)成員發(fā)生聯(lián)系。

答案:非線性結(jié)構(gòu)采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（）。

答案:前序遍歷設(shè)一個有序的單鏈表中有n個結(jié)點(diǎn)，現(xiàn)要求插入一個新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（）。

答案:O(n)

答案:(5,6)(4,6)(1,3)(1,2)(3,5)一個算法的時間復(fù)雜度為（3n2+2nlog2n+4n-7）/（5n），其數(shù)量級表示為：（）

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

答案:線性探查法、雙散列法、開散列法。（）排序方法采用的是二分法的思想。

答案:快速

答案:2,4,3,6,5,7下列廣義表用鏈表來表示時，分支結(jié)點(diǎn)最多的是（）。

答案:L=((x,(a,B)),(x,(a,B),y))假定一個初始堆為(1,5,3,9,12,7,15,10)，欲把這組數(shù)從大到小排序，采用最小堆，則進(jìn)行第一趟堆排序后得到的結(jié)果為（）。

答案:A.3,5,7,9,12,10,15,1在（）中的各個數(shù)據(jù)成員依次排列在一個線性序列中。

答案:線性結(jié)構(gòu)設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link），單鏈表中指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，應(yīng)執(zhí)行（）操作。

答案:s->Link=p->Link;p->Link=s；線索二叉樹是一種（）結(jié)構(gòu)。

答案:物理（）排序方法能夠每次從無序表中順序查找出一個最小值。

答案:直接選擇若一棵二叉樹的前序遍歷序列是{4,2,1,3,6,5,7}，中序遍歷序列是{1,2,3,4,5,6,7}，則下列哪句是錯的？（）

答案:6是3的父結(jié)點(diǎn)

答案:O（m*n）一個廣義表的表尾總是一個（）。

答案:廣義表對于長度為9的順序存儲的有序表，若采用折半查找，在等概率情況下的平均查找長度為（）的9分之一。

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

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

答案:歸并排序下列排序算法中，時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(NlogN)的是：（）

答案:堆排序?qū)⑿蛄衶2,12,16,88,5,10,34}排序。若前2趟排序的結(jié)果如下：第1趟排序后：2,12,16,10,5,34,88第2趟排序后：2,5,10,12,16,34,88則可能的排序算法是：（）

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

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

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

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

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

答案:(d+1)%m

答案:12和14若使用AOE網(wǎng)估算工程進(jìn)度，則下列敘述中正確的是：（）

答案:關(guān)鍵路徑是從源點(diǎn)到匯點(diǎn)路徑長度最長的路徑設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有（）條邊才能確保是一個連通圖。

答案:5

答案:abdfce

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

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

答案:當(dāng)∣V∣>∣E∣+1時，G一定是不連通的10.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（）個結(jié)點(diǎn)。

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

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

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

答案:同時具備(A)和(B)兩個條件廣義表A=((x,(a,B)),(x,(a,B),y))，則運(yùn)算head(head(tail(A)))的結(jié)果為（）。

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

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

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

答案:front=front->next設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。

答案:必須判別棧是否為空一個棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是（）

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

答案:s->link=top;top=s;設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link），若要刪除單鏈表中指針p指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)（若存在），