數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋濰坊學(xué)院

數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋濰坊學(xué)院第一章單元測(cè)試

數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面。（）

A:錯(cuò)B:對(duì)

答案:對(duì)數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān)。（）

A:對(duì)B:錯(cuò)

答案:對(duì)算法分析的兩個(gè)主要方面是時(shí)間復(fù)雜度和空間復(fù)雜度的分析。（）

A:對(duì)B:錯(cuò)

答案:對(duì)，

對(duì)應(yīng)的算法時(shí)間復(fù)雜度相同。（）

A:錯(cuò)B:對(duì)

答案:對(duì)算法的時(shí)間復(fù)雜度取決于（）

A:A和BB:待處理數(shù)據(jù)的初態(tài)C:問(wèn)題的規(guī)模

答案:A和B數(shù)據(jù)邏輯結(jié)構(gòu)可以分為（）。

A:集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)B:線性結(jié)構(gòu)和圖結(jié)構(gòu)C:集合結(jié)構(gòu)和非線性結(jié)構(gòu)D:順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)

答案:集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。

A:存儲(chǔ)B:邏輯和存儲(chǔ)C:邏輯D:物理

答案:邏輯在計(jì)算機(jī)中存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)（）。

A:數(shù)據(jù)的處理方法B:數(shù)據(jù)元素之間的關(guān)系C:數(shù)據(jù)元素的類型D:數(shù)據(jù)的存儲(chǔ)方法

答案:數(shù)據(jù)元素之間的關(guān)系數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的（）。

A:邏輯結(jié)構(gòu)B:抽象數(shù)據(jù)類型C:存儲(chǔ)結(jié)構(gòu)D:順序結(jié)構(gòu)

答案:存儲(chǔ)結(jié)構(gòu)

第二章單元測(cè)試

若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用順序表存儲(chǔ)最節(jié)省時(shí)間。（）

A:對(duì)B:錯(cuò)

答案:對(duì)在順序表中，邏輯上相鄰的元素，其物理位置必定相鄰。（）

A:錯(cuò)B:對(duì)

答案:對(duì)線性表的插入、刪除總是伴隨著大量數(shù)據(jù)的移動(dòng)。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)帶頭結(jié)點(diǎn)的循環(huán)單鏈表中，任一結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針域均不空。（）

A:對(duì)B:錯(cuò)

答案:對(duì)線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，各個(gè)數(shù)據(jù)元素的存儲(chǔ)單元地址一定是不連續(xù)的。（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)線性表L=(a1?，a2?，…，an?)，下列說(shuō)法正確的是（）

A:除第一個(gè)和最后一個(gè)元素外，其他元素都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼B:表中至少有一個(gè)元素C:表中元素需有序D:每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

答案:除第一個(gè)和最后一個(gè)元素外，其他元素都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼在n個(gè)數(shù)據(jù)元素的順序表中，算法時(shí)間復(fù)雜度為O(1)的操作是（）

(1)訪問(wèn)第i個(gè)結(jié)點(diǎn)（1≤i≤n）

(2)求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）

(3)求第i個(gè)結(jié)點(diǎn)的直接后繼（1≤i≤n-1）

(4)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）

(5)刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）

(6)排序

A:(6)B:(1)(2)(3)(4)(5)C:(4)(5)D:(1)(2)(3)

答案:(1)(2)(3)假設(shè)某個(gè)帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則判定該表為空表的條件是（）

A:head!=NULLB:head->next==headC:head->next==NULLD:head==NULL

答案:head->next==NULL創(chuàng)建一個(gè)包括n個(gè)結(jié)點(diǎn)的單鏈表的時(shí)間復(fù)雜度是（）

A:O(n2)B:O(n)C:O(1)D:O(log2?n)

答案:O(n)在單鏈表中，指針域?yàn)閚ext，要將q所指結(jié)點(diǎn)鏈接到p所指結(jié)點(diǎn)之后，其語(yǔ)句序列應(yīng)為（）

A:q->next=p->next;p->next=q;B:q->next=p+1;p->next=q;C:p->next=q;q->next=p;D:p->next=q;q->next=p->next;

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

第三章單元測(cè)試

棧頂元素和棧底元素有可能是冋一個(gè)元素。（）

A:錯(cuò)B:對(duì)

答案:對(duì)鏈棧和順序棧相比，比較明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿的情況。（）

A:錯(cuò)B:對(duì)

答案:對(duì)在用數(shù)組表示的循環(huán)隊(duì)列中，front值一定小于等于rear值。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)棧是插入和刪除只能在一端進(jìn)行的線性表；隊(duì)列是插入在一端進(jìn)行，刪除在另一端進(jìn)行的線性表。（）

A:對(duì)B:錯(cuò)

答案:對(duì)為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）？

A:圖B:棧C:隊(duì)列D:樹(shù)

答案:隊(duì)列棧在（）中有所應(yīng)用。

A:遞歸調(diào)用B:前三個(gè)選項(xiàng)都有C:函數(shù)調(diào)用D:表達(dá)式求值

答案:前三個(gè)選項(xiàng)都有循環(huán)隊(duì)列的引入，目的是為了克服（）。

A:真溢出問(wèn)題B:假溢出問(wèn)題C:操作不方便D:空間不夠用

答案:假溢出問(wèn)題若用一個(gè)大小為6的數(shù)值來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（）。

A:1和5B:2和4C:5和1D:4和2

答案:2和4若元素1、2、3、4、5依次入棧，則出棧次序不可能為（）。

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

答案:1,5,3,4,2

第四章單元測(cè)試

廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)，其元素可以是單原子也可以是子表。（）

A:錯(cuò)B:對(duì)

答案:對(duì)已知二維數(shù)組A[0..5][0..7]（行下標(biāo)為0到5，列下標(biāo)為0到7），每個(gè)元素占用2個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，若A[0][0]的地址為2000，則按行優(yōu)先存儲(chǔ)時(shí)元素A[3][4]的地址是2056。（）

A:對(duì)B:錯(cuò)

答案:對(duì)廣義表A=（（a），a）的表頭是（）。

A:(a)B:((a))C:()D:a

答案:(a)對(duì)廣義表，通常采用的存儲(chǔ)結(jié)構(gòu)是（）。

A:鏈表B:數(shù)組C:三元組D:Hash表

答案:鏈表已知二維數(shù)組A[0..4][0..5]，則A按行優(yōu)先存儲(chǔ)時(shí)元素A[3][5]的地址與A按列優(yōu)先存儲(chǔ)時(shí)元素（）的地址相同。

A:A[3][5]B:A[2][4]C:A[3][4]D:A[4][3]

答案:A[3][4]已知二維數(shù)組A[0..7][0..9]（行下標(biāo)為0到7，列下標(biāo)為0到9），數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，數(shù)據(jù)元素A[0][0]的內(nèi)存首地址為100，當(dāng)采用列主序存放時(shí)，元素A[4][7]的存儲(chǔ)首地址為（）

A:241B:322C:325D:280

答案:280在一個(gè)二維數(shù)組A中，假設(shè)每個(gè)數(shù)組元素的長(zhǎng)度為3個(gè)存儲(chǔ)單元，行下標(biāo)為0~8,列下標(biāo)為0~9，從首地址SA開(kāi)始連續(xù)存放。則按行優(yōu)先存儲(chǔ)時(shí)，元素A[8][5]的起始地址為（）

A:SA+141B:SA+222C:SA+144D:SA+255

答案:SA+255廣義表((a,b),c,d,e)的表頭和表尾分別是

A:(a,b)和eB:

(a,b)和(c,d,e)C:a和eD:a和(c,d,e)

答案:

(a,b)和(c,d,e)

第五章單元測(cè)試

在含有n個(gè)結(jié)點(diǎn)的樹(shù)中，分支數(shù)只能是n-1條。（）

A:對(duì)B:錯(cuò)

答案:對(duì)一棵有124個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其葉結(jié)點(diǎn)個(gè)數(shù)是確定的。（）

A:對(duì)B:錯(cuò)

答案:對(duì)在任意一棵二叉樹(shù)中，分支結(jié)點(diǎn)的數(shù)目一定少于葉結(jié)點(diǎn)的數(shù)目。（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)哈夫曼樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)。（）

A:錯(cuò)B:對(duì)

答案:對(duì)一棵非空二叉樹(shù)，若先序遍歷與后序遍歷的序列相反，則該二叉樹(shù)（）。

A:為任意二叉樹(shù)B:只有一個(gè)葉子結(jié)點(diǎn)C:所有結(jié)點(diǎn)均無(wú)左孩子D:所有結(jié)點(diǎn)均無(wú)右孩子

答案:只有一個(gè)葉子結(jié)點(diǎn)樹(shù)最適合用來(lái)表示（）。

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

答案:元素之間具有分支層次關(guān)系的數(shù)據(jù)深度為5的二叉樹(shù)至多有（）個(gè)節(jié)點(diǎn)。

A:31B:32C:16D:10

答案:31設(shè)某棵二叉樹(shù)的中序遍歷序列為DBEAC，先序遍歷序列為ABDEC，則該二叉樹(shù)的后序遍歷序列是（）。

A:CFDBAB:DBFACC:DBEACD:DEBCA

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

A:30B:60C:90D:69

答案:69

第六章單元測(cè)試

有n個(gè)頂點(diǎn)的無(wú)向圖,采用鄰接矩陣表示,圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。（）

A:錯(cuò)B:對(duì)

答案:對(duì)無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣，有向圖的鄰接矩陣一定是非對(duì)稱矩陣。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)鄰接表法只能用于有向圖的存儲(chǔ)，鄰接矩陣法對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用。（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)連通分量是無(wú)向圖中的極小連通子圖。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)對(duì)下圖進(jìn)行廣度優(yōu)先遍歷，得到的序列不可能為（）。

A:AFEBCDB:CDFBAEC:DCEFBAD:BCFADE

答案:CDFBAE使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點(diǎn)1到其他各頂點(diǎn)的最短路徑，依次得到的各最短路徑的目標(biāo)頂點(diǎn)是：（）

A:5,2,6,3,4,7B:2,3,4,5,6,7C:2,4,3,6,5,7D:2,5,3,4,6,7

答案:2,4,3,6,5,7已知無(wú)向圖G如下所示，使用克魯斯卡爾（Kruskal）算法求圖G的最小生成樹(shù)，加入到最小生成樹(shù)中的邊依次是：（）

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

答案:(b,f),(b,d),(a,e),(c,e),(b,e)在下圖中，自a點(diǎn)開(kāi)始進(jìn)行深度優(yōu)先遍歷算法可能得到的結(jié)果為

A:a,e,d,f,c,bB:a,c,f,e,b,d

C:a,e,b,c,f,dD:a,b,e,c,d,f

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

第七章單元測(cè)試

當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度（）。

A:取決于表遞增還是遞減B:不一定C:必定快D:在大部分情況下要快

答案:在大部分情況下要快在有N個(gè)結(jié)點(diǎn)且為完全二叉樹(shù)的二叉排序樹(shù)中查找一個(gè)鍵值，其平均比較次數(shù)的數(shù)量級(jí)為：（）

A:O(Nlog2N)B:O(N)C:O(N2)D:O(log2N)

答案:O(log2N)若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為（）。

A:n/2B:(n+1)/2C:(n-1)/2D:n

答案:(n+1)/2適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（）。

A:順序方式存儲(chǔ)，元素有序B:順序方式存儲(chǔ)，元素?zé)o序C:鏈接方式存儲(chǔ)，元素?zé)o序D:鏈接方式存儲(chǔ)，元素有序

答案:順序方式存儲(chǔ)，元素有序?qū)3,8,9,1,2,6}依次插入初始為空的二叉排序樹(shù)。則該樹(shù)的后序遍歷結(jié)果是：（）

A:1,2,8,6,9,3B:2,1,6,9,8,3C:1,2,3,6,9,8D:2,1,3,6,9,8

答案:2,1,6,9,8,3設(shè)散列表的地址區(qū)間為[0,16]，散列函數(shù)為H(Key)=Key%17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列{26，25，72，38，8，18，59}依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址是：（）

A:9B:11C:8D:10

答案:11設(shè)有一組關(guān)鍵字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函數(shù)為H(key)=key%17，采用線性探測(cè)方法解決沖突。試在0到18的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造散列表，則成功查找的平均查找長(zhǎng)度為（）。

A:1.17B:1.25C:1.33D:0.33

答案:1.33設(shè)有一組關(guān)鍵字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函數(shù)為H(key)=key%17，采用二次探測(cè)方法解決沖突。試在0到18的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造散列表，則成功查找的平均查找長(zhǎng)度為（）。

A:0.33B:1.25C:1.33D:1.17

答案:1.25

第八章單元測(cè)試

插入排序算法在每一趟都能選取出一個(gè)元素放在其最終的位置上。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)對(duì)N個(gè)記錄進(jìn)行簡(jiǎn)單選擇排序，比較次數(shù)和移動(dòng)次數(shù)分別為O(N2)和O(N)。（）

A:對(duì)B:錯(cuò)

答案:對(duì)要從50個(gè)鍵值中找出最大的3個(gè)值，簡(jiǎn)單選擇排序比堆排序快。（）

A:對(duì)B:錯(cuò)

答案:對(duì)對(duì)N個(gè)記錄進(jìn)行快速排序，在最壞的情況下，其時(shí)間復(fù)雜度是O(Nlog2N)。（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)基數(shù)排序只適用于以數(shù)字為關(guān)鍵字的情況，不適用于以字符串為關(guān)鍵字的情況。（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)希爾排序的組內(nèi)排序采用的是（）。

A:快速排序B:直接插入排序C:折半插入排序D:歸并排序

答案:直接插入排序下述幾種排序方法中，（）是穩(wěn)定的排序方法。

A:希爾排序B:堆排序C:快速排序D:歸并排序

答案:歸并排序用某種排序