數(shù)據(jù)結構知到智慧樹章節(jié)測試課后答案2024年秋廣州大學

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

與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的（）。

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

答案:邏輯結構說法正確的是（）。

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

答案:一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構在這些數(shù)據(jù)結構中，（）是非線性數(shù)據(jù)結構

A:樹B:隊列C:棧D:字符串

答案:樹在數(shù)據(jù)結構中，數(shù)據(jù)的基本單位是（）。

A:數(shù)據(jù)項B:數(shù)據(jù)元素C:數(shù)據(jù)變量D:數(shù)據(jù)類型

答案:數(shù)據(jù)元素計算算法的時間復雜度是屬于一種（）。

A:事前分析估算的方法B:事后統(tǒng)計的方法C:事前統(tǒng)計的方法D:事后分析估算的方法

答案:事前分析估算的方法數(shù)據(jù)元素之間的關系稱為（）

A:結構B:數(shù)據(jù)對象C:操作D:數(shù)據(jù)集合

答案:結構在下列算法中，“x=x*2”的執(zhí)行次數(shù)是（）

intsuanfal(intn){

inti,j,x=1;for(i=0;i<n;i++)for(j=i;j<n;j++)x=x*2;

returnx;}

A:n(n-1)/2B:nlog2nC:n2D:n(n+1)/2

答案:n(n+1)/2求整數(shù)n（n≥0）階乘的算法如下，其時間復雜度是（）

intfact(intn){

if(n<=1)return1;return

n×fact(n-1);}

A:O(nlog2n)B:O(n2)C:O(n)D:O(log2n)

答案:O(n)數(shù)據(jù)元素可以由類型互不相同的數(shù)據(jù)項構成。（）

A:錯B:對

答案:對在順序存儲結構中，有時也存儲數(shù)據(jù)結構中元素之間的關系。（）

A:對B:錯

答案:錯算法可以沒有輸人，但是必須有輸出。（）

A:對B:錯

答案:對

第二章單元測試

線性表是一個（）

A:有限序列，可以為空B:無限序列，可以為空C:無限序列，不能為空D:有限序列，不能為空

答案:有限序列，可以為空能在O(1)時間內(nèi)訪問線性表的第i個元素的結構是（）。

A:單鏈表B:順序表C:雙向鏈表D:單向循環(huán)鏈表

答案:順序表線性表是具有n（n>0）個（）的有限序列。

A:字符B:數(shù)據(jù)元素C:表元素D:數(shù)據(jù)項

答案:數(shù)據(jù)元素若某線性表最常用的操作是存取任一指定序號的元素并在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。

A:單循環(huán)鏈表B:順序表C:帶頭結點的雙循環(huán)鏈表D:雙鏈表

答案:順序表線性表（a1，a2，…，an）以鏈接方式存儲時，訪問第i個位置元素的時間復雜性為（）。

A:O(i)B:О(1)C:O(i-1)D:O(n)

答案:O(n)將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（）

A:O(m+n)B:О(m)C:O(n)D:O(1)

答案:О(m)鏈表具有的特點是（）。

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

答案:不必事先估計存儲空間；插入、刪除不需要移動元素；所需空間與線性長度成正比已知L是有頭結點的非空單鏈表，則要在P結點前插入S結點的語句序列是（）

A:while(Q->next!=P)Q=Q->next;B:Q->next=S;C:Q=L;D:Q=P;E:deleteQ;F:S->next=Q->next;G:P->next=Q->next;H:P=Q;I:P->next=S->next;

答案:while(Q->next!=P)Q=Q->next;；Q->next=S;；Q=L;；S->next=Q->next;下面代碼是實現(xiàn)尾插法創(chuàng)建單鏈表L的過程，請選擇合適的語句，將代碼補充完整。（）

voidCreatList_R(LinkList&L,intn){

L=newLNode;

L->next=NULL;

①

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

LNode*p=newLNode;

cin>>p->data;

②

r=p;

}}

A:LNode*p=NULL;B:p->next=NULL;r->next=p;C:LNode*r=L;D:LNode*r=L->next;E:r->next=NULL;p->next=r;

答案:p->next=NULL;r->next=p;；LNode*r=L;線性表的邏輯順序與物理順序總是一致的。（）

A:錯B:對

答案:錯線性表的插入和刪除操作總是伴隨著大量數(shù)據(jù)的移動。（）

A:對B:錯

答案:錯在順序表中取出第i個元素所花費的時間與i成正比。（）

A:對B:錯

答案:錯線性表采用鏈式存儲表示時，所有結點之間的存儲單元地址可連續(xù)可不連續(xù)。（）

A:錯B:對

答案:對在單鏈表中，要訪問某個結點，只要知道該結點的指針即可，因此，單鏈表是一種隨機存取結構。（）

A:對B:錯

答案:錯在具有頭結點的鏈式存儲結構中，頭指針指向鏈表中的第一個數(shù)據(jù)結點。（）

A:對B:錯

答案:錯在一個具有頭指針和尾指針的單鏈表中，執(zhí)行刪除該單鏈表中最后一個元素的操作與鏈表的長度無關。（）

A:對B:錯

答案:錯

第三章單元測試

數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素個數(shù)的公式為（）。

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

答案:（n+r-f)%n為解決計算機主機與打印機間速度不匹配問題，通常設一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結構應該是（）。

A:有序表B:線性表C:棧D:隊列

答案:隊列用鏈接方式存儲的隊列，在進行刪除運算時（）。

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

答案:頭、尾指針可能都要修改同一組不重復輸入序列，執(zhí)行不同的入、出站組合操作，所得結果也可能相同。（）

A:對B:錯

答案:對若某堆棧初始為空，push與pop分別表示對棧進行一次進棧與出棧操作，那么，對于輸入序列A、B、C、D、E經(jīng)過pushpushpoppushpoppushpush以后，輸出序列中有元素（）。

A:DB:BC:AD:CE:E

答案:B；C下面代碼實現(xiàn)的是一個順序棧S的出棧操作，請選擇合適的語句將代碼補充完整。（）

boolPop(SqStack&S,ElemType&e){

if(

①

)return0;

②

return1;}

A:S.top==NULL;B:e=*S.top;S.top--;C:S.base==NULL;D:S.top==S.base;E:

S.top--;e=*S.top;

答案:S.top==S.base;；

S.top--;e=*S.top;下面代碼實現(xiàn)的是一個循環(huán)隊列Q的出隊操作，請選擇合適的語句將代碼補充完整。（）boolDeQueue(SqQueue&Q,ElemType&e){

if(

①

)return0;

e=Q.base[②];

③

return

1;}

A:Q.front==Q.rear;B:Q.front+1;C:Q.front=(Q.front+1)%MAXSIZE;D:Q.rear=(Q.rear+1)%MAXSIZE;E:Q.front;

答案:Q.front==Q.rear;；Q.front=(Q.front+1)%MAXSIZE;；Q.front;

第四章單元測試

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

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

答案:5一個具有1025個結點的二叉樹的高h為（）。

A:10B:11至1025之間C:10至1024之間D:11

答案:11至1025之間利用二叉鏈表存儲樹，則根結點的右指針是（）。

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

答案:空n（n≥2）個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是（）。

A:樹中任一非葉結點的權值一定不小于下一層任一結點的權值B:該樹一定是一棵完全二叉樹C:樹中兩個權值最小的結點一定是兄弟結點D:樹中一定沒有度為1的結點

答案:該樹一定是一棵完全二叉樹下列判斷中，（）是正確的。

A:深度為k的二叉樹最多有2k-1個結點（k≥1），最少有k個結點B:二叉樹中不存在度大于2的結點C:構造線索二叉樹是為能方便找到每個結點的雙親D:對二叉樹遍歷是指先序、中序或后序遍歷中的一種

答案:深度為k的二叉樹最多有2k-1個結點（k≥1），最少有k個結點；二叉樹中不存在度大于2的結點根據(jù)（）可以唯一地確定一棵二叉樹。

A:先序遍歷和中序次遍歷B:中序遍歷和后序遍歷C:先序遍歷和后序遍歷D:中序遍歷

答案:先序遍歷和中序次遍歷；中序遍歷和后序遍歷下面代碼是中序遍歷二叉樹的非遞歸算法，請選擇合適的語句將代碼補充完整。（）

A:p=q->rchild;B:p=p->lchild;C:q=q->lchild;D:p=p->rchild;

答案:p=q->rchild;；p=p->lchild;二叉樹只能采用二叉鏈表來存儲。（）

A:對B:錯

答案:錯二叉樹是度為2的有序樹。（）

A:對B:錯

答案:錯對一棵有n個結點的二叉樹，從上到下、從左到右用自然數(shù)依次給予編號，則編號為i的結點的左兒子的編號為2i（2i<n），右兒子是2i+1（2i+1<n）。（）

A:錯B:對

答案:錯用二叉樹的前序遍歷序列和中序遍歷序列可以求出二叉樹的后序序列序列。（）

A:對B:錯

答案:對哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根結點較近。（）

A:錯B:對

答案:對

第五章單元測試

在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（）倍。

A:4B:1C:1/2D:2

答案:2下面（）算法適合構造一個稠密圖G的最小生成樹。

A:Kruskal算法B:Dijkstra算法C:Prim算法D:Floyd算法

答案:Prim算法廣度優(yōu)先遍歷類似于二叉樹的（）。

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

答案:層次遍歷已知圖的鄰接矩陣如圖所示，則從頂點v0出發(fā)按深度優(yōu)先遍歷的結果是（）。

A:0361542B:0134256C:0243156D:0136542

答案:0134256下面（）方法不可以判斷出一個有向圖是否有環(huán)。

A:深度優(yōu)先遍歷B:拓撲排序C:求關鍵路徑D:求最短路徑

答案:拓撲排序n個結點的無向圖，若不允許結點到自身的邊，也不允許結點到結點的多重邊，且邊的總數(shù)為n（n-1）/2，則該無向圖一定是連通圖。（）

A:錯B:對

答案:對n個結點的有向圖，若它有n（n-1)條邊，則它一定是強連通的。（）

A:錯B:對

答案:對無向圖中任何一個邊數(shù)最少且連通所有頂點的子圖都是該無向圖的生成樹。（）

A:錯B:對

答案:對圖g的頂點v的入度等于其鄰接矩陣中第v列中的1的個數(shù)。（）

A:對B:錯

答案:對用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結點個數(shù)有關，而與圖的邊數(shù)無關。（）

A:對B:錯

答案:對有e條邊的無向圖在鄰接表中有e個結點。（）

A:對B:錯

答案:錯任何無向圖都存在生成樹。（）

A:對B:錯

答案:錯不同的求最小生成樹的方法最后得到的生成樹是相同的。（）

A:錯B:對

答案:錯一個帶權的無向連通圖的最小生成樹的權值之和是唯一的。（）

A:對B:錯

答案:對連通圖上各邊權值均不相同，則該圖的最小生成樹是唯一的。（）

A:對B:錯

答案:對對于任意一個圖，從它的某個頂點進行一次先深或先廣搜索可以訪問到該圖的每個頂點。（）

A:錯B:對

答案:錯采用深度優(yōu)先搜索或拓撲排序算法可以判斷出一個有向圖中是否有環(huán)。（）

A:錯B:對

答案:對如果有向圖的拓撲排序序列是唯一的，則圖中必定只有一個頂點的入度為0，一個頂點的出度為0。（）

A:錯B:對

答案:對具有n個頂點和e條邊的無向圖，若用鄰接矩陣作為存儲結構，則求任意頂點的度數(shù)的時間復雜度為O(e)。（）

A:對B:錯

答案:錯廣度優(yōu)先搜索遍歷圖的時間復雜度和深度優(yōu)先搜索遍歷的相同。（）

A:對B:錯

答案:對在拓撲序列中，任意兩個相繼結點Vi和Vj都存在從Vi到Vj的路徑。（）

A:錯B:對

答案:錯有向圖如下圖所示，該圖的深度優(yōu)先遍歷序列是（）。

A:12543B:13254C:15432D:12345

答案:12543；13254；15432下列關于最小生成樹的敘述中，不正確的是（）。

A:使用Prim算法從不同頂點開始得到的最小生成樹一定相同B:最小生成樹的代價唯一C:使用Prim算法和Kruskas算法得到的最小生成樹總不相同。D:所有權值最小的邊一定會出現(xiàn)在最小生成樹中

答案:使用Prim算法從不同頂點開始得到的最小生成樹一定相同；使用Prim算法和Kruskas算法得到的最小生成樹總不相同。；所有權值最小的邊一定會出現(xiàn)在最小生成樹中無向圖如下圖所示，在求該圖的最小生成樹時，可能是Kruskal算法第二次選中的邊，也可能是Prim算法，從4號頂點開始，第二次選中的邊是（）。

A:(2,3)B:(1,4)C:(3,4)D:(1,3)

答案:(3,4)；(1,3)下面哪些方法可以用來判斷一個有向圖中是否有環(huán)存在。（）

A:廣度優(yōu)先遍歷B:深度優(yōu)先遍歷C:求最短路徑算法D:拓撲排序

答案:深度優(yōu)先遍歷；拓撲排序

第六章單元測試

衡量查找算法效率的主要標準是（）。

A:算法難易程度B:平均查找長度C:元素個數(shù)D:所需的存儲量

答案:平均查找長度對n個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為（）。

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

答案:(n+1)/2已知8個元素為{34,76,45,18,26,54,92,65}，按照依次有序插入結點的方法生成一棵二叉排序樹，最后兩層上結點的總數(shù)為（）。

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

答案:2順序查找法，表中元素可以任意存放。（）

A:錯B:對

答案:對折半查找法要求待查表的關鍵字值必須有序。（）

A:對B:錯

答案:對在有序的順序表和有序的鏈表上，均可以采用折半查找法來提高查找速度。（）

A:錯B:對

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

A:對B:錯

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

A:錯B:對

答案:錯在二叉排序樹中，根結點的值都小于孩子結點的值。（）

A:錯B:對

答案:錯利用二叉排序樹進行查找時，若關鍵字的值比根結點的值小，則繼續(xù)在左子樹中查找。（）

A:對B:錯

答案:對在二叉排序樹上刪除一個結點時，不必移動其他結點，只要將該結點的父結點的相應指針域置空即可。（）

A:對B:錯

答案:錯對于一個堆，按照二叉樹的層次遍歷，可以得到一個有序序列。（）

A:錯B:對

答案:錯下面針對折半查找算法，說法正確的是（）

A:折半查找不適用于數(shù)據(jù)元素經(jīng)常變動的線性表。B:當給定的關鍵字與mid位置處的關鍵字不相等時，說明查找失敗。C:在折半查找算法對應的二叉判定樹中，結點的值是查找表中數(shù)據(jù)元素的關鍵字。D:當給定的關鍵字與mid位置處的關鍵字相等時，說明查找成功。

答案:折半查找不適用于數(shù)據(jù)元素經(jīng)常變動的線性表。；當給定的關鍵字與mid位置處的關鍵字相等時，說明查找成功。下列選項中，能構成折半查找中關鍵字比較序列的是（）。

A:180,500,200,450B:180,200,500,450C:500,450,200.180D:500,200,450,180

答案:180,500,200,450；180,200,500,450；500,450,200.180對于下列關鍵字序列，可能構成某二叉排序樹中一條查找路徑的序列是（）。

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

答案:12,25,71,68,33,34；92,20,91,34,88,35；21,89,77,29,36,38

下面代碼是折半查找的遞歸算法，請為①②位置處選擇合適的語句。（）

A:midB:highC:lowD:r[mid].key＞kE:r[mid].key<k

答案:mid；r[mid].key<k

第七章單元測試

評價排序算法好壞的標準主要是（）。

A:執(zhí)行時間B:輔助空間C:算法本身的復雜度D:執(zhí)行時間和所需的輔助空間

答案:執(zhí)行時間和所需的輔助空間內(nèi)排序是指在排序的整個過程中，全部數(shù)據(jù)都在計算機的（）中完成的排序。

A:內(nèi)存和外存B:寄存器C:內(nèi)存D:外存

答案:內(nèi)存直接插入排序的方法是從第（）個元素開始，插入到前邊適當位置的排序方法。

A:nB:1C:3D:2

答案:2按排序策略分類，冒泡排序?qū)儆冢ǎ?/p>

A:交換排序B:插入排序C:分配排序D:選擇排序

答案:交換排序用直接插入排序法對下面的4個序列進行由小到大的排序，元素比較次數(shù)最少的是（）。

A:21，32，46，40，80，69，90，94B:94，32，40，90，80，46，21，69C:32，40，21，46，69，94，90，80D:90，69，80，46，21，32，94，40

答案:21，32，46，40，80，69，90，94從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱為（）。

A:插入排序B:快速排序C:冒泡排序D:選擇排序

答案:插入排序從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（）。

A:冒泡排序B:插入排序C:選擇排序D:快速排序

答案:選擇排序?qū)個不同的關鍵字由小到大進行冒泡排序，在下列（）情況下比較的次數(shù)最多。

A:元素基本有序B:元素無序C:從小到大排列好的D:從大到小排列好的

答案:從大到小排列好的對n個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)最多為（）。

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

答案:n(n-1)/2快速排序在下列（）情況下最不易發(fā)揮其長處。

A:被排序的數(shù)據(jù)完全無序B:被排序的數(shù)據(jù)中含有多個相同排序碼C:被排序的數(shù)據(jù)中的最大值和最小值相差懸殊D:被排序的數(shù)據(jù)已基本有序

答案:被排序的數(shù)據(jù)已基本有序?qū)個關鍵字作快速排序，在最壞情況下，算法的時間復雜度是（）。

A:O(n3)B:O(n2)C:O(nlog2n)D:O(n)

答案:O(n2)若一組記錄的排序碼為{46,79，56，38，40，84}，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（）。

A:40，38，46，84，56，79B:40，38，46，79，56，84C:40，38，46，56，79，84D:38，40，46，56，79，84

答案:40，38，46，56，79，84下列關鍵字序列中，（）是堆。

A:16，53，23，94，31，72B:16，72，31，23，94，53C:94，23，31，72，16，53D:16，23，53，31，94，72

答案:16，23，53，31，94，72堆是一種（）排序。

A:插入B:選擇C:歸并D:交換

答案:選擇堆的形狀是一棵（）。

A:二叉排序樹B:滿二叉樹C:完全二叉樹D:平衡二叉樹

答案:完全二叉樹若一組記錄的排序碼為{46，79，56，38，40，84}，則利用堆排序的方法建立的初始堆為（）。

A:84，79，56，38，40，46B:79，46，56，38，40，84C:84，79，56，46，40，38D:84，56，79，40，46，38

答案:84，79，56，38，40，46下述幾種排序方法中，（）是穩(wěn)定的排序方法。

A:冒泡排序B:堆排序C:簡單選擇排序D:快速排序

答案:冒泡排序數(shù)據(jù)表中有10000個元素，如果僅要求求出其中最大的10個元素，則采用（）算法最節(jié)省時間。

A:簡單選擇排序B:冒泡排序C:快速排序D:堆排