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

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

下列敘述中正確的是（

）

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

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

）

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

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

）

A:內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B:動(dòng)態(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)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（

）

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

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

）

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

答案:一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)下面代碼段的時(shí)間復(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

)下面代碼段的時(shí)間復(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具有相同的增長(zhǎng)速度。（

）

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

答案:對(duì)N2logN2和NlogN2具有相同的增長(zhǎng)速度。（

）

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

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

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

答案:錯(cuò)

第二章單元測(cè)試

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

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

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

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

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

A:不必事先估計(jì)存儲(chǔ)空間B:所需空間與線性表長(zhǎng)度成正比C:插入刪除不需要移動(dòng)元素D:可隨機(jī)訪問(wèn)任一個(gè)元素

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

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

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

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;在長(zhǎng)度為n的順序表的表尾插入一個(gè)新元素的時(shí)間復(fù)雜度為（）

A:O(

n2

)B:O(

1

)C:O(

logn

)D:O(

n

)

答案:O(

1

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

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

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

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

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

)

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

答案:錯(cuò)線性表的長(zhǎng)度是線性表所占用的存儲(chǔ)空間的大小（）

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

答案:錯(cuò)

第三章單元測(cè)試

設(shè)有六列火車(chē)，編號(hào)為1，2，3，4，5，6，順序開(kāi)進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺(tái)，問(wèn)下列輸出序列中，哪個(gè)是不可能出現(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棧和隊(duì)列都是運(yùn)算受限的線性表。（

）

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

答案:對(duì)當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示棧空，則表示棧滿的條件是top==1。（

）

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

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

）。

A:4

B:6C:5

D:3

答案:4

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

）。

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

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

）。

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

答案:(n+r-f)%n若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針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和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（

）。

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

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

）。

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

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

）。

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

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

第四章單元測(cè)試

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

A:4B:2

C:5D:3

答案:2

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

)個(gè)結(jié)點(diǎn)

A:B:C:D:

答案:將含有83個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根結(jié)點(diǎn)開(kāi)始編號(hào)，根為1號(hào)，按從上到下、從左到右順序結(jié)點(diǎn)編號(hào)，那么編號(hào)為41的雙親結(jié)點(diǎn)編號(hào)為（

）

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

答案:20對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹(shù),其高度為（）

A:B:C:D:不確定

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

A:LRNB:RLNC:RNLD:NRL

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

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

答案:先序下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（）

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}二叉樹(shù)先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹(shù)根的右子樹(shù)的根是（）

A:FB:HC:GD:E

答案:G以下說(shuō)法錯(cuò)誤的是（）

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

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

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

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

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

答案:對(duì)完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是樹(shù)葉。（

）

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

答案:對(duì)利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（

）

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

答案:空

第五章單元測(cè)試

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

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

答案:對(duì)有向圖的鄰接矩陣是對(duì)稱(chēng)的。（）

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

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

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

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

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

2.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1

3.至少有一個(gè)頂點(diǎn)的度為1

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

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

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

答案:2e給定一有向圖的鄰接表如下。從頂點(diǎn)V1出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則得到的頂點(diǎ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點(diǎn)開(kāi)始進(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任何一個(gè)帶權(quán)無(wú)向連通圖的最小生成樹(shù)（）。

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

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

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）算法求下圖中從頂點(diǎn)1到其它各頂點(diǎn)的最短路徑，依次得到的各最短路徑的目標(biāo)頂點(diǎn)是（）。

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

第六章單元測(cè)試

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

）

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

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

）

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

答案:錯(cuò)在查找樹(shù)（二叉排序樹(shù)）中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。（

）

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

答案:錯(cuò)采用線性探測(cè)法處理散列時(shí)的沖突，當(dāng)從哈希表刪除一個(gè)記錄時(shí)，不應(yīng)將這個(gè)記錄的所在位置置空，因?yàn)檫@會(huì)影響以后的查找。（

）

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

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

）

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

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

）。

A:6

B:7C:5

D:4

答案:5

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

）。

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在任意一棵非空二叉排序樹(shù)T1中，刪除某結(jié)點(diǎn)v之后形成二叉排序樹(shù)T2，再將v插入T2形成二叉排序樹(shù)T3。下列關(guān)于T1與T3的敘述中，正確的是（

）。

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

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

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

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

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

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

）個(gè)

A:1

B:2

C:4D:3

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

)

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

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

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

A:8B:1

C:4

D:2

答案:4

將{5,2,7,3,4,1,6}依次插入初始為空的二叉排序樹(shù)。則該樹(shù)的后序遍歷結(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ù)開(kāi)始逐步插入數(shù)據(jù)形成二叉排序樹(shù)，若希望高度最小，應(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)于哈希查找的說(shuō)法，不正確的是（）

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

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

第七章單元測(cè)試

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

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

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

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

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

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

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

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

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