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

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

下列敘述中正確的是（

）

A:程序可以作為算法的一種描述方法B:算法設(shè)計只需考慮得到計算結(jié)果C:算法設(shè)計可以忽略算法的運(yùn)算時間D:所謂算法就是計算方法

答案:程序可以作為算法的一種描述方法數(shù)據(jù)的最小單位是數(shù)據(jù)項（

）

A:對B:錯

答案:對在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（

）

A:內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B:動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C:線性結(jié)構(gòu)和非線性結(jié)構(gòu)D:緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

答案:線性結(jié)構(gòu)和非線性結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（

）

A:運(yùn)算實現(xiàn)B:邏輯結(jié)構(gòu)C:存儲結(jié)構(gòu)D:存儲實現(xiàn)

答案:邏輯結(jié)構(gòu)以下說法正確的是（

）

A:一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)B:數(shù)據(jù)項是數(shù)據(jù)的基本單位C:數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D:數(shù)據(jù)元素是數(shù)據(jù)的最小單位

答案:一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)下面代碼段的時間復(fù)雜度是（）。

s=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

s+=B[i][j];

sum=s;

A:O(n)B:O(logn)C:O(1)D:O(

n2

)

答案:O(

n2

)下面代碼段的時間復(fù)雜度是（）。

x=0;

for(i=1;i<n;i++)

for(j=1;j<=n-i;j++)

x++;

A:O(n)B:O(n3)

C:O(logn)D:O(n2)

答案:O(n2)

NlogN2和NlogN具有相同的增長速度。（

）

A:對B:錯

答案:對N2logN2和NlogN2具有相同的增長速度。（

）

A:對B:錯

答案:錯斐波那契數(shù)列FN的定義為：F0=0，F(xiàn)1=1，F(xiàn)N=FN?1+FN?2，N=2,3,...。用遞歸函數(shù)計算FN的時間復(fù)雜度是O(N!)。

A:對B:錯

答案:錯

第二章單元測試

下面關(guān)于線性表的敘述中，錯誤的是哪一個（）

A:線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B:線性表采用順序存儲，便于進(jìn)行插入和刪除操作C:線性表采用鏈接存儲，便于插入和刪除操作D:線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元

答案:線性表采用順序存儲，便于進(jìn)行插入和刪除操作在具有n個結(jié)點的單鏈表中，實現(xiàn)下列哪個操作，其算法的時間復(fù)雜度是O(n)？

A:刪除開始結(jié)點B:在地址為p的結(jié)點之后插入一個結(jié)點C:刪除地址為p的結(jié)點的后繼結(jié)點D:遍歷鏈表和求鏈表的第i個結(jié)點

答案:遍歷鏈表和求鏈表的第i個結(jié)點鏈表不具有的特點是（）

A:不必事先估計存儲空間B:所需空間與線性表長度成正比C:插入刪除不需要移動元素D:可隨機(jī)訪問任一個元素

答案:可隨機(jī)訪問任一個元素帶頭結(jié)點的單鏈表L為空的條件是（）

A:L->next->next==NULL;B:L->next==NULL;C:L->next==L;D:L==NULL;

答案:L->next==NULL;在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是（）

A:p->next=s->next;

p->next=s;B:p->next=s;

s->next=p->next;C:p->next=s;

p->next=s->next;D:s->next=p->next;

p->next=s;

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

p->next=s;在長度為n的順序表的表尾插入一個新元素的時間復(fù)雜度為（）

A:O(

n2

)B:O(

1

)C:O(

logn

)D:O(

n

)

答案:O(

1

)單鏈表中，增加頭結(jié)點的目的是為了()

A:說明單鏈表是線性表的鏈?zhǔn)酱鎯崿F(xiàn)B:標(biāo)示表結(jié)點中首結(jié)點的位置C:方便運(yùn)算的實現(xiàn)D:使單鏈表至少有一個結(jié)點

答案:方便運(yùn)算的實現(xiàn)線性表的邏輯順序與物理順序總是一致的（）

A:對B:錯

答案:錯取線性表的第i個元素的時間同i的大小有關(guān)(

)

A:對B:錯

答案:錯線性表的長度是線性表所占用的存儲空間的大?。ǎ?/p>

A:對B:錯

答案:錯

第三章單元測試

設(shè)有六列火車，編號為1，2，3，4，5，6，順序開進(jìn)一個棧式結(jié)構(gòu)的站臺，問下列輸出序列中，哪個是不可能出現(xiàn)的（

）。

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

答案:3,1,2,6,5,4棧和隊列都是運(yùn)算受限的線性表。（

）

A:錯B:對

答案:對當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？眨瑒t表示棧滿的條件是top==1。（

）

A:對B:錯

答案:錯元素a,b,c,d,e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數(shù)是（

）。

A:4

B:6C:5

D:3

答案:4

已知循環(huán)隊列存儲在一維數(shù)組A[0..n-1]中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第1個進(jìn)入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是（

）。

A:n-1,n-1B:n-1,0C:0,n-1D:0,0

答案:0,n-1數(shù)組Q[n]用來表示一個循環(huán)隊列，f為當(dāng)前隊列頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數(shù)小于n，計算隊列中元素個數(shù)的公式為（

）。

A:(n+f-r)%nB:r-fC:(n+r-f)%nD:n+r-f

答案:(n+r-f)%n若一個棧以向量V[1..n]存儲，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確操作是（

）。

A:V[top]=x;top++;B:top++;V[top]=x;C:top--;V[top]=x;D:V[top]=x;top--;

答案:top--;V[top]=x;設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個元素出棧后即進(jìn)入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（

）。

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

答案:3循環(huán)隊列放在一維數(shù)組A[0…M-1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設(shè)隊列兩端均可進(jìn)行入隊和出隊操作，隊列中最多能容納M-1個元素。初始時為空，下列判斷隊空和隊滿的條件中，正確的是（

）。

A:隊空：end1==end2；隊滿：end2==(end1+1)mod(M-1)B:隊空：end1==(end2+1)；隊滿：end2==(end1+1)mod(M-1)C:隊空：end2==(end1+1)modM；隊滿：end1==(end2+1)modMD:隊空：end1==end2；隊滿：end1==(end2+1)modM

答案:隊空：end1==end2；隊滿：end1==(end2+1)modM用鏈接方式存儲的隊列，在進(jìn)行刪除運(yùn)算時（

）。

A:頭、尾指針可能都要修改B:僅修改尾指針C:頭、尾指針都要修改D:僅修改頭指針

答案:頭、尾指針可能都要修改

第四章單元測試

由3個結(jié)點可以構(gòu)造出多少種不同的樹（）

A:4B:2

C:5D:3

答案:2

一棵樹高為K的完全二叉樹至少有(

)個結(jié)點

A:B:C:D:

答案:將含有83個結(jié)點的完全二叉樹從根結(jié)點開始編號，根為1號，按從上到下、從左到右順序結(jié)點編號，那么編號為41的雙親結(jié)點編號為（

）

A:20B:40C:42D:21

答案:20對于有n個結(jié)點的二叉樹,其高度為（）

A:B:C:D:不確定

答案:不確定給定二叉樹如下圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3、1、7、5、6、2、4，則其遍歷方式是（）

A:LRNB:RLNC:RNLD:NRL

答案:RNL如果T2是由有序樹T轉(zhuǎn)化而來的二叉樹，那么T中結(jié)點的先序就是T2中結(jié)點的（）

A:后序B:先序C:層次D:中序

答案:先序下面幾個符號串編碼集合中，不是前綴編碼的是（）

A:{0,10,110,1111}B:{11,10,001,101,0001}C:{00,010,0110,1000}

D:{b,c,aa,ac,aba,abb,abc}

答案:{11,10,001,101,0001}二叉樹先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是（）

A:FB:HC:GD:E

答案:G以下說法錯誤的是（）

A:若初始森林中共有N棵二叉樹，進(jìn)行2N-1次合并后才能剩下最終的哈夫曼樹B:一般在哈夫曼樹中，權(quán)值越大的葉子離根結(jié)點越近C:若初始森林中共有N棵二叉樹，最終求得的哈夫曼樹中共有2N-1個結(jié)點D:哈夫曼樹中沒有度數(shù)為1的分支結(jié)點

答案:若初始森林中共有N棵二叉樹，進(jìn)行2N-1次合并后才能剩下最終的哈夫曼樹若一棵二叉樹的任一非葉子結(jié)點的度為2，則該二叉樹為滿二叉樹（）

A:對B:錯

答案:錯若某二叉樹的葉子結(jié)點數(shù)為1，則其先序序列和后序序列一定相反（）

A:錯B:對

答案:對完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。（

）

A:對B:錯

答案:對利用二叉鏈表存儲樹，則根結(jié)點的右指針是（

）

A:指向最左孩子B:指向最右孩子C:空D:非空

答案:空

第五章單元測試

用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)。（）

A:對B:錯

答案:對有向圖的鄰接矩陣是對稱的。（）

A:對B:錯

答案:錯設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（）條邊。

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

答案:n(n-1)/2下列關(guān)于無向連通圖特征的敘述中，正確的是：（）

1.所有頂點的度之和為偶數(shù)

2.邊數(shù)大于頂點個數(shù)減1

3.至少有一個頂點的度為1

A:只有2B:只有1C:1和3D:1和2

答案:只有1對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，所有頂點鄰接表的邊結(jié)點總數(shù)為（）。

A:2eB:e/2C:n+eD:e

答案:2e給定一有向圖的鄰接表如下。從頂點V1出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則得到的頂點序列為()。

A:V1,V5,V4,V7,V6,V2,V3B:V1,V5,V4,V7,V6,V3,V2C:V1,V2,V3,V4,V7,V6,V5D:V1,V5,V6,V4,V7,V2,V3

答案:V1,V5,V4,V7,V6,V3,V2在圖中自a點開始進(jìn)行廣度優(yōu)先搜索算法可能得到的結(jié)果為（）。

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

答案:a,b,e,c,d,f任何一個帶權(quán)無向連通圖的最小生成樹（）。

A:是唯一的B:是不唯一的C:有可能不唯一D:有可能不存在

答案:有可能不唯一對于下列的網(wǎng)，使用克魯斯卡爾算法求最小生成樹，依次得到的邊集是（）。

A:{（A，D），（B，C），（E，A），（C，E）}B:{（A，D），（A，B），（A，E），（E，C）}C:{（A，D），（D，E），（B，C），（C，E）}D:{（A，D），（D，E），（E，C），（C，B）}

答案:{（A，D），（D，E），（B，C），（C，E）}使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點1到其它各頂點的最短路徑，依次得到的各最短路徑的目標(biāo)頂點是（）。

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

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

第六章單元測試

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（1）若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；（2）若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值。（

）

A:對B:錯

答案:錯查找相同結(jié)點的效率折半查找總比順序查找高。（

）

A:對B:錯

答案:錯在查找樹（二叉排序樹）中插入一個新結(jié)點，總是插入到葉結(jié)點下面。（

）

A:錯B:對

答案:錯采用線性探測法處理散列時的沖突，當(dāng)從哈希表刪除一個記錄時，不應(yīng)將這個記錄的所在位置置空，因為這會影響以后的查找。（

）

A:對B:錯

答案:對對一棵二叉排序樹按先序方法遍歷得出的結(jié)點序列是從小到大的序列。（

）

A:錯B:對

答案:錯已知一個長度為16的順序表L,其元素按關(guān)鍵字有序排列,若采用折半查找法查找一個不存在的元素,則比較次數(shù)最多的是（

）。

A:6

B:7C:5

D:4

答案:5

對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是(

）。

A:92,20,91,34,88,35B:12,25,71,68,33,34C:95,22,91,24,94,71D:21,89,77,29,36,38

答案:95,22,91,24,94,71在任意一棵非空二叉排序樹T1中，刪除某結(jié)點v之后形成二叉排序樹T2，再將v插入T2形成二叉排序樹T3。下列關(guān)于T1與T3的敘述中，正確的是（

）。

I.若v是T1的葉結(jié)點，則T1與T3不同

II.若v是T1的葉結(jié)點，則T1與T3相同

III.若v不是T1的葉結(jié)點，則T1與T3不同

IV.若v不是T1的葉結(jié)點，則T1與T3相同

A:僅II、IVB:僅I、IVC:僅II、IIID:僅I、III

答案:僅II、III對于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲時，若選用H（K）=K%7作為散列函數(shù)，則哈希地址為0的元素有（

）個

A:1

B:2

C:4D:3

答案:4適用于折半查找的查找表存儲方式及元素排列要求為(

)

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

D:鏈接方式存儲，元素?zé)o序

答案:順序方式存儲，元素有序有一個有序表為｛1,3,9,12,32,41,45,62,75,77,82,95,100｝，當(dāng)用折半查找方法查找值82的結(jié)點時，（）次比較后查找成功。

A:8B:1

C:4

D:2

答案:4

將{5,2,7,3,4,1,6}依次插入初始為空的二叉排序樹。則該樹的后序遍歷結(jié)果是:（）

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

答案:1,4,3,2,6,7,5有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開始逐步插入數(shù)據(jù)形成二叉排序樹，若希望高度最小，應(yīng)選擇下列（）的序列輸入。

A:30，24，12，37，45，96，53B:37，24，12，30，53，45，96C:45，24，53，12，37，96，30D:12，24，30，37，45，53，96

答案:37，24，12，30，53，45，96下面關(guān)于哈希查找的說法，不正確的是（）

A:用鏈地址法處理沖突，適合表長不確定的情況B:用鏈地址法處理沖突，不會引起二次聚集現(xiàn)象C:采用鏈地址法處理沖突時，若插入規(guī)定總是在鏈?zhǔn)?，則插入任一個元素的時間是相同的D:采用鏈地址法處理沖突時，查找每個元素的時間是相同的

答案:采用鏈地址法處理沖突時，查找每個元素的時間是相同的

第七章單元測試

快速排序的速度在所有排序方法中為最快,而且所需附加空間也最少。

A:錯B:對

答案:錯堆排序是穩(wěn)定的排序方法。

A:錯B:對

答案:錯在初始數(shù)據(jù)表已經(jīng)有序時，快速排序算法的時間復(fù)雜度為O(nlog2n)。

A:對B:錯

答案:錯在用堆排序算法排序時，如果要進(jìn)行增序排序，則需要采用“大根堆”。

A:對B:錯

答案:對比較次數(shù)與排序