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

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

下列敘述中正確的是（

）

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

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

）

A:對B:錯

答案:對在數據結構中，從邏輯上可以把數據結構分成（

）

A:內部結構和外部結構B:動態(tài)結構和靜態(tài)結構C:線性結構和非線性結構D:緊湊結構和非緊湊結構

答案:線性結構和非線性結構與數據元素本身的形式、內容、相對位置、個數無關的是數據的（

）

A:運算實現(xiàn)B:邏輯結構C:存儲結構D:存儲實現(xiàn)

答案:邏輯結構以下說法正確的是（

）

A:一些表面上很不相同的數據可以有相同的邏輯結構B:數據項是數據的基本單位C:數據結構是帶有結構的各數據項的集合D:數據元素是數據的最小單位

答案:一些表面上很不相同的數據可以有相同的邏輯結構下面代碼段的時間復雜度是（）。

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

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

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:錯

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

A:對B:錯

答案:錯

第二章單元測試

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

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

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

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

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

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

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

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

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

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的順序表的表尾插入一個新元素的時間復雜度為（）

A:O(

n2

)B:O(

1

)C:O(

logn

)D:O(

n

)

答案:O(

1

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

A:說明單鏈表是線性表的鏈式存儲實現(xiàn)B:標示表結點中首結點的位置C:方便運算的實現(xiàn)D:使單鏈表至少有一個結點

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

A:對B:錯

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

)

A:對B:錯

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

A:對B:錯

答案:錯

第三章單元測試

設有六列火車，編號為1，2，3，4，5，6，順序開進一個棧式結構的站臺，問下列輸出序列中，哪個是不可能出現(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棧和隊列都是運算受限的線性表。（

）

A:錯B:對

答案:對當用長度為N的數組順序存儲一個棧時，假定用top==N表示棧空，則表示棧滿的條件是top==1。（

）

A:對B:錯

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

）。

A:4

B:6C:5

D:3

答案:4

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

）。

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

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

）。

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

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

）。

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

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

）。

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

答案:3循環(huán)隊列放在一維數組A[0…M-1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容納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用鏈接方式存儲的隊列，在進行刪除運算時（

）。

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

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

第四章單元測試

由3個結點可以構造出多少種不同的樹（）

A:4B:2

C:5D:3

答案:2

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

)個結點

A:B:C:D:

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

）

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

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

A:B:C:D:不確定

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

A:LRNB:RLNC:RNLD:NRL

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

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棵二叉樹，進行2N-1次合并后才能剩下最終的哈夫曼樹B:一般在哈夫曼樹中，權值越大的葉子離根結點越近C:若初始森林中共有N棵二叉樹，最終求得的哈夫曼樹中共有2N-1個結點D:哈夫曼樹中沒有度數為1的分支結點

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

A:對B:錯

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

A:錯B:對

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

）

A:對B:錯

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

）

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

答案:空

第五章單元測試

用鄰接矩陣法存儲圖，占用的存儲空間數只與圖中結點個數有關，而與邊數無關。（）

A:對B:錯

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

A:對B:錯

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

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

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

1.所有頂點的度之和為偶數

2.邊數大于頂點個數減1

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

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

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

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

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

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點開始進行廣度優(yōu)先搜索算法可能得到的結果為（）。

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任何一個帶權無向連通圖的最小生成樹（）。

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

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

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到其它各頂點的最短路徑，依次得到的各最短路徑的目標頂點是（）。

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）若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；（2）若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值。（

）

A:對B:錯

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

）

A:對B:錯

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

）

A:錯B:對

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

）

A:對B:錯

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

）

A:錯B:對

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

）。

A:6

B:7C:5

D:4

答案:5

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

）。

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中，刪除某結點v之后形成二叉排序樹T2，再將v插入T2形成二叉排序樹T3。下列關于T1與T3的敘述中，正確的是（

）。

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

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

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

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

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

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

）個

A:1

B:2

C:4D:3

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

)

A:鏈接方式存儲，元素有序B:順序方式存儲，元素有序C:順序方式存儲，元素無序

D:鏈接方式存儲，元素無序

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

A:8B:1

C:4

D:2

答案:4

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

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有數據{53，30，37，12，45，24，96}，從空二叉樹開始逐步插入數據形成二叉排序樹，若希望高度最小，應選擇下列（）的序列輸入。

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下面關于哈希查找的說法，不正確的是（）

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

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

第七章單元測試

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

A:錯B:對

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

A:錯B:對

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

A:對B:錯

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

A:對B:錯

答案:對比較次數與排序