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

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

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

A:緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)B:內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)C:動態(tài)結(jié)構(gòu)和靜態(tài)結(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:存儲結(jié)構(gòu)B:存儲實(shí)現(xiàn)C:邏輯結(jié)構(gòu)D:運(yùn)算實(shí)現(xiàn)

答案:邏輯結(jié)構(gòu)通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。

A:不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致B:數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等C:每個數(shù)據(jù)元素都一樣D:數(shù)據(jù)具有同一特點(diǎn)

答案:不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致一下說法正確的是（）。

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

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

A:問題的規(guī)模B:問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)C:待處理數(shù)據(jù)的初態(tài)D:計算機(jī)的配置

答案:問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。

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

答案:樹設(shè)語句x++的時間是單位時間，則以下語句的時間復(fù)雜度為（）。

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

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

x++;

A:O(

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

)

答案:O(

)數(shù)據(jù)在計算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲方式，在存儲空間使用的靈活性上，鏈?zhǔn)酱鎯Ρ软樞虼鎯σǎ?/p>

A:低B:相同C:不好說D:高

答案:高算法分析的目的是（）。

A:分析算法的易懂性和文檔性B:找出數(shù)據(jù)結(jié)構(gòu)的合理性C:研究算法中的輸入和輸出關(guān)系D:分析算法的效率以求改進(jìn)

答案:分析算法的效率以求改進(jìn)計算機(jī)算法指的是（）。

A:排序方法B:解決問題的有限運(yùn)算序列C:調(diào)度方法D:計算方法

答案:解決問題的有限運(yùn)算序列

第二章單元測試

線性結(jié)構(gòu)中的一個結(jié)點(diǎn)代表一個（）

A:數(shù)據(jù)結(jié)構(gòu)B:數(shù)據(jù)元素C:數(shù)據(jù)D:數(shù)據(jù)項

答案:數(shù)據(jù)元素若長度為n的線性表采?順序存儲結(jié)構(gòu)，在其第i個位置插??個新元素算法的時間復(fù)雜度（）。

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

答案:O(n)若?個線性表中最常?的操作是取第i個元素和找第i個元素的前趨元素，則采?（）存儲?式最節(jié)省時間。

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

答案:順序表在?個長度為n的順序表中，在第i個元素之前插??個新元素時，需向后移動（）個元素。

A:n-i-1B:iC:n-iD:n-i+1

答案:n-i+1?空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿?（）。

A:p->next==headB:p==NULLC:p->next==NULLD:p==head

答案:p->next==head鏈表不具有的特點(diǎn)是（）。

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

答案:可隨機(jī)訪問任?元素在?個單鏈表中，若刪除p所指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)?（）。

A:p=p->next;p->next=p->next->next;B:p->next=p->next->next;C:p=p->next;D:p=p->next->next;

答案:p->next=p->next->next;單鏈表不是?種隨機(jī)存儲結(jié)構(gòu)。（）

A:對B:錯

答案:對順序存儲?式只能?于存儲線性結(jié)構(gòu)。（）

A:對B:錯

答案:錯在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素但是在物理位置上不?定是相鄰的。（）

A:對B:錯

答案:錯

第三章單元測試

若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種情況。

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

答案:4，3，1，2，5設(shè)有一個遞歸算法如下：

intfact(intn){//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);}

則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。

A:n+1B:n+2C:nD:n-1

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

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

答案:隊列設(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:4C:6D:3

答案:3最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。

A:(rear+1)%n==frontB:rear+1==frontC:rear==frontD:(rear-l)%n==front

答案:rear==front棧和隊列的共同點(diǎn)是（）。

A:都是先進(jìn)后出B:只允許在端點(diǎn)處插入和刪除元素C:沒有共同點(diǎn)D:都是先進(jìn)先出

答案:只允許在端點(diǎn)處插入和刪除元素棧和隊列都是限制存取端的。（）

A:錯B:對

答案:對對順序棧進(jìn)行進(jìn)棧、出棧操作，不涉及元素的前、后移動問題。（）

A:對B:錯

答案:對若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（）。

A:n-iB:n-i+1C:iD:n-i-1

答案:n-i+1循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（）。

A:rear=(rear+1)%(m+1)B:rear=(rear+1)%(m-1)C:rear=(rear+1)%mD:rear=rear+1

答案:rear=(rear+1)%(m+1)

第四章單元測試

空串與空格串是相同的。（）

A:錯B:對

答案:錯設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作____。（）

A:求子串B:模式匹配C:連接D:求串長

答案:模式匹配設(shè)有一個12×12的對稱矩陣M，將其上三角部分的元素mi,j（1≤i≤j≤12）按行優(yōu)先存人C語言的一維數(shù)組N中，元素m6,6在N中的下標(biāo)是（）。

A:66B:51C:55D:50

答案:55將一個10*10對稱矩陣M的上三角部分的元素mi,j（1≤i≤j≤10）按列優(yōu)先存入C語言的一維數(shù)組N中，元素m7,2在N中的下標(biāo)是____。（）

A:33B:16C:22D:15

答案:22下面關(guān)于串的的敘述中，哪一個是不正確的？（）

A:串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯:模式匹配是串的一種重要運(yùn)算C:空串是由空格構(gòu)成的串D:串是字符的有限序列

答案:空串是由空格構(gòu)成的串串的長度是指（）

A:串中所含不同字符的個數(shù)B:串中所含非空格字符的個數(shù)C:串中所含字符的個數(shù)D:串中所含不同字母的個數(shù)

答案:串中所含字符的個數(shù)若串S=“software”，其子串的個數(shù)是（）。

A:8B:37C:36D:9

答案:36常對數(shù)組進(jìn)行的兩種基本操作是____。（）

A:建立與刪除B:索引和修改C:查找與索引D:查找和修改

答案:查找和修改有一個三維數(shù)組A[-2…2][-4…5][2…6],其元素個數(shù)是____。（）

A:396B:144C:60D:250

答案:250設(shè)二維數(shù)組A[1..5][1..8]，若按行優(yōu)先的順序存放數(shù)組的元素，則A[4][6]元素的前面有____個元素。（）

A:29B:6C:28D:40

答案:29

第五章單元測試

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

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

答案:5一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（）。

A:254B:500C:501D:250

答案:501一個具有1025個結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）。

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

答案:11至1025之間深度為h的滿m叉樹的第k層有（）個結(jié)點(diǎn)。(1=<k=<h)

A:mk-1B:mh-1C:mk-1D:mh-1

答案:mk-1一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）。

A:只有一個葉子結(jié)點(diǎn)B:是任意一棵二叉樹C:所有的結(jié)點(diǎn)均無右孩子D:所有的結(jié)點(diǎn)均無左孩子

答案:只有一個葉子結(jié)點(diǎn)設(shè)哈夫曼樹中有199個結(jié)點(diǎn)，則該哈夫曼樹中有（）個葉子結(jié)點(diǎn)。

A:100B:101C:99D:102

答案:100若X是二叉中序線索樹中一個有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（）。

A:X的右子樹中最左的結(jié)點(diǎn)B:X的雙親C:X的左子樹中最右葉結(jié)點(diǎn)D:X的左子樹中最右結(jié)點(diǎn)

答案:X的左子樹中最右結(jié)點(diǎn)引入二叉線索樹的目的是（）。

A:為了能方便的找到雙親B:使二叉樹的遍歷結(jié)果唯一C:加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度D:為了能在二叉樹中方便的進(jìn)行插入與刪除

答案:加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度n（n≥2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（）。

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

答案:該樹一定是一棵完全二叉樹設(shè)F是一個森林，B是由F變換得到的二叉樹。若F中有n個非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個。

A:nB:n+2C:n?1D:n+1

答案:n+1

第六章單元測試

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

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

答案:2具有n個頂點(diǎn)的有向圖最多有（）條邊

A:n(n+1)B:2nC:nD:n(n-1)

答案:n(n-1)n個頂點(diǎn)的聯(lián)通圖用鄰接矩陣表示時，該矩陣至少有（）個非零元素

A:2(n-1)B:nC:n2D:n/2

答案:2(n-1)若從無向圖的任意一個頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索可以訪問圖中所有的頂點(diǎn)，則該圖一定是（）圖

A:聯(lián)通B:弱連通C:強(qiáng)連通D:非連通

答案:聯(lián)通用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常借助（）來實(shí)現(xiàn)算法

A:樹B:隊列C:圖D:棧

答案:隊列下面（）算法適合構(gòu)造一個稠密圖G的最小生成樹

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

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

A:求關(guān)鍵路徑B:拓?fù)渑判駽:深度優(yōu)先遍歷D:求最短路徑

答案:深度優(yōu)先遍歷使用Dijkstra算法求下圖中從頂點(diǎn)到其他各頂點(diǎn)的最短路徑，依次得到的各最短路徑的目標(biāo)點(diǎn)是（）

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

答案:5,2,3,6,4下圖所示的AOE表示一項包含8個活動的工程，活動d的最早開始時間和最遲開始時間分別是（）

A:15和15B:12和14C:3和7D:12和12

答案:12和14已知無向圖G如下所示，使用Kruskal算法求圖G的最小生成樹，加入到最小生成樹中的邊依次是（）

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

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

第七章單元測試

靜態(tài)查找表和動態(tài)查找表的區(qū)別是？（）

A:所包含的數(shù)據(jù)元素的類型不同B:施加其上的操作不同C:它們的邏輯結(jié)構(gòu)不同D:其他三個選項都不對

答案:施加其上的操作不同采用順序查找方法查找長度為n的順序表時，在等概率時成功查找的平均查找長度為（）。

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

答案:(n+1)/2適合于折半查找的數(shù)據(jù)組織方式是（）。

A:以順序表存儲的線性表B:以順序表存儲的有序線性表C:以鏈表存儲的有序線性表D:以鏈表存儲的線性表

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

A:4B:6C:7D:5

答案:5?對有3600個記錄的索引順序表（分塊表）進(jìn)行分塊查找，最理想的塊長是（）。

A:60B:120C:180D:600

答案:60有一棵含有8個節(jié)點(diǎn)的二叉排序樹，其節(jié)點(diǎn)值為A～H，以下（）是其后序遍歷結(jié)果。

A:ADBCEGFHB:BCAEFDHGC:BDACEFHGD:BCAGEHFD

答案:BCAEFDHG具有5層節(jié)點(diǎn)的AVL樹至少有（）個節(jié)點(diǎn)。

A:12B:17C:10D:15

答案:12?以下關(guān)于m階B-樹的敘述中正確的是（）。

A:當(dāng)插入一個關(guān)鍵字引起B(yǎng)-樹節(jié)點(diǎn)分裂時，樹增高一層B:樹中每個節(jié)點(diǎn)至多有ém/2ù-1個關(guān)鍵字C:所有葉子節(jié)點(diǎn)均在同一層上D:每個節(jié)點(diǎn)至少有兩棵非空子樹

答案:所有葉子節(jié)點(diǎn)均在同一層上?以下關(guān)于哈希查找的敘述中正確的是（）。

A:哈希查找中不需要任何關(guān)鍵字的比較B:采用拉鏈法解決沖突時，查找一個元素的時間是相同的C:哈希表在查找成功時的平均查找長度僅僅與表長有關(guān)D:哈希表的裝填因子等于表中填入的記錄數(shù)除以哈希表的長度

答案:哈希表的裝填因子等于表中填入的記錄數(shù)除以哈希表的長度

第八章單元測試

對n個不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)最多為？（）

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

答案:n(n-1)/2對n個關(guān)鍵字作快速排序，在最壞情況下，算法的時間復(fù)雜度是（）。

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

答案:O(n2)若一組記錄的排序碼為（46,79，56，38，40，84），則利