數(shù)據(jù)結(jié)構(gòu)（山東聯(lián)盟-青島大學）知到智慧樹章節(jié)測試課后答案2024年秋青島大學

數(shù)據(jù)結(jié)構(gòu)（山東聯(lián)盟-青島大學）知到智慧樹章節(jié)測試課后答案2024年秋青島大學第一章單元測試

在Data_Structure=(D，R)中，D是（）的有限集合。

A:數(shù)據(jù)元素B:數(shù)據(jù)操作C:算法D:數(shù)據(jù)對象

答案:數(shù)據(jù)元素計算機所處理的數(shù)據(jù)一般具有某種關(guān)系，這是指（）。

A:元素內(nèi)數(shù)據(jù)項與數(shù)據(jù)項之間存在的某種關(guān)系B:數(shù)據(jù)文件內(nèi)記錄與記錄之間存在的某種關(guān)系C:數(shù)據(jù)與數(shù)據(jù)之間存在的某種關(guān)系D:數(shù)據(jù)元素與數(shù)據(jù)元素之間存在的某種關(guān)系

答案:數(shù)據(jù)元素與數(shù)據(jù)元素之間存在的某種關(guān)系算法的時間復(fù)雜度與（

）有關(guān)。

A:編譯后執(zhí)行程序的質(zhì)量B:問題規(guī)模

C:計算機硬件的運行速度D:源程序的長度

答案:問題規(guī)模

以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法正確的是（

）。

A:數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)獨立于該數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)B:數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)唯一地決定了該數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)C:數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)獨立于其存儲結(jié)構(gòu)D:數(shù)據(jù)結(jié)構(gòu)僅由其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)決定

答案:數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)獨立于其存儲結(jié)構(gòu)某算法的時間復(fù)雜度是O(n2)，表明該算法（）。

A:問題規(guī)模與n^2成正比B:執(zhí)行時間與n^2成正比C:問題規(guī)模是n^2D:執(zhí)行時間等于n^2

答案:執(zhí)行時間與n^2成正比從邏輯上可將數(shù)據(jù)結(jié)構(gòu)分為（）。

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

答案:線性結(jié)構(gòu)和非線性結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。

A:錯B:對

答案:對數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)的實際存儲形式。

A:錯B:對

答案:對每種數(shù)據(jù)結(jié)構(gòu)都具備三種基本運算：插入、刪除和查找。

A:錯B:對

答案:錯算法的時間效率和空間效率往往相互沖突，有時很難兩全其美。

A:對B:錯

答案:對

第二章單元測試

線性表是一個（）。

A:數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素的類型可以不同B:數(shù)據(jù)元素的有限序列，元素不可以是線性表C:數(shù)據(jù)元素的無限序列，元素個數(shù)可以是零個，也可以有多個D:數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素還可以是線性表

答案:數(shù)據(jù)元素的有限序列，元素不可以是線性表以下關(guān)于線性表的說法中正確的是（）。

A:線性表中的元素必須按照從小到大或從大到小的次序排列B:線性表中所有的元素都可以直接（或隨機）存取C:線性表中至少有一個元素D:除第一個元素和最后一個元素外，其他每個元素有且僅有一個直接前趨元素和一個直接后繼元素

答案:除第一個元素和最后一個元素外，其他每個元素有且僅有一個直接前趨元素和一個直接后繼元素以下關(guān)于線性表的說法中正確的是（)。

A:每個元素最多有一個直接前趨和一個直接后繼B:每個元素最少有一個直接前趨和一個直接后繼C:每個元素有且僅有一個直接前趨，有且僅有一個直接后繼D:線性表中的元素還可以是線性表，但數(shù)據(jù)類型必須相同

答案:每個元素最多有一個直接前趨和一個直接后繼如果線性表中的表元素既沒有直接前趨，也沒有直接后繼，則該線性表中應(yīng)有（）個表元素。

A:2B:0

C:1D:n

答案:1在線性表中的每一個表元素都是數(shù)據(jù)對象，它們是不可再分的（）。

A:數(shù)據(jù)記錄B:數(shù)據(jù)元素C:數(shù)據(jù)字段D:數(shù)據(jù)項

答案:數(shù)據(jù)元素順序表是線性表的（）表示。

A:連續(xù)B:順序存取C:有序D:順序存儲

答案:順序存儲以下關(guān)于順序表的說法中正確的是（）。

A:在順序表中每一表元素的數(shù)據(jù)類型還可以是順序表B:順序表利用一維數(shù)組表示，因此順序表與一維數(shù)組在結(jié)構(gòu)上一致，它們可以通用C:在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰D:順序表和一維數(shù)組一樣，都可以按下標隨機（或直接）訪問，順序表還可以從某一指定元素開始，向前或向后逐個元素順序訪問

答案:順序表和一維數(shù)組一樣，都可以按下標隨機（或直接）訪問，順序表還可以從某一指定元素開始，向前或向后逐個元素順序訪問順序表的優(yōu)點是（）。

A:適用于各種邏輯結(jié)構(gòu)的存儲表示B:插入操作的時間效率高C:刪除操作的時間效率高D:存儲密度（存儲利用率）高

答案:存儲密度（存儲利用率）高以下關(guān)于單鏈表的敘述中錯誤的是（）。

A:結(jié)點除自身信息外還包括指針域，因此存儲密度小于順序存儲結(jié)構(gòu)B:可以通過計算直接確定第i個結(jié)點的存儲地址C:插入、刪除運算操作方便，不必移動結(jié)點D:邏輯上相鄰的結(jié)點物理上不必相鄰

答案:可以通過計算直接確定第i個結(jié)點的存儲地址以下關(guān)于單鏈表的敘述中錯誤的是（）。

A:單鏈表中各結(jié)點地址不可能連續(xù)B:結(jié)點的數(shù)據(jù)域用于存儲線性表的一個數(shù)據(jù)元素C:所有數(shù)據(jù)通過指針的鏈接而組織成單鏈表D:結(jié)點的指針域用于存放一個指針，指示本結(jié)點所存儲數(shù)據(jù)元素的直接后繼元素所在結(jié)點的地址

答案:單鏈表中各結(jié)點地址不可能連續(xù)在單鏈表上實施插入和刪除操作（）。

A:既需移動結(jié)點，又需改變結(jié)點指針B:不需移動結(jié)點，只需改變結(jié)點指針C:不需移動結(jié)點，不需改變結(jié)點指針D:只需移動結(jié)點，不需改變結(jié)點指針

答案:不需移動結(jié)點，只需改變結(jié)點指針在單鏈表最終增加頭結(jié)點的目的是（)。

A:方便對鏈表的統(tǒng)一命名B:方便插入、刪除等運算的實現(xiàn)C:使得鏈表遍歷有一個終結(jié)結(jié)點D:標識鏈表首元結(jié)點的位置

答案:方便插入、刪除等運算的實現(xiàn)已知單鏈表中結(jié)點*q是結(jié)點*p的直接前趨，若在*q與*p之間插入結(jié)點*s,則應(yīng)執(zhí)行以下（）操作。

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

答案:q->next=s;s->next=p;已知單鏈表中結(jié)點*p不是鏈尾結(jié)點，若在*p之后插入結(jié)點*s，則應(yīng)執(zhí)行以下（）操作。

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

答案:s->next=p->next;p->next=s;順序表中元素的邏輯順序和物理順序總是一致的。

A:對B:錯

答案:對在單鏈表中插入新元素時，必須先找到要插入位置的前一個結(jié)點。

A:錯B:對

答案:對順序表是靜態(tài)存儲結(jié)構(gòu)，而鏈表是動態(tài)存儲結(jié)構(gòu)。

A:錯B:對

答案:錯循環(huán)單鏈表可以僅在鏈表尾部設(shè)置鏈尾指針。

A:錯B:對

答案:對在為順序表分配連續(xù)的存儲空間時，必須預(yù)估該空間的最大容量。但想估計得準確很不容易，而為鏈表分配存儲空間則不會為此煩惱。

A:對B:錯

答案:對在順序表中插入和刪除時效率太低，因此它不如鏈表好。

A:對B:錯

答案:錯

第三章單元測試

棧的插入和刪除操作在（

）進行。

A:棧頂B:棧底C:指定位置D:任意位置

答案:棧頂對一個初始為空的棧s執(zhí)行操作Push(s,5),Push(s,2),Push(s,4),Pop(s,x),getTop(s,x)后，x的值應(yīng)是（

）。

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

答案:2用S表示進棧操作，用X表示出棧操作，若元素的進棧順序是1234，為了得到1342出棧順序，相應(yīng)的S和X的操作序列為（

）。

A:SSSXXSXXB:SXSSXXSXC:SXSXSSXXD:SXSSXSXX

答案:SXSSXSXX假設(shè)一個棧的輸入序列是1,2,3,4，則不可能得到的輸出序列是（

）。

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

答案:4,1,2,3已知一個棧的進棧序列為1,2,3,…,n，其輸出序列的第一個元素是i，則第j個出棧元素是（

）。

A:不確定B:n-iC:j-i+1D:j-i

答案:不確定已知一個棧的進棧序列為1,2,3,…,n，其輸出序列是p1,p2,p3,…,pn。若p1=n，則pi的值是（

）。

A:iB:不確定C:n-i+1D:n-i

答案:n-i+1已知一個棧的進棧序列為1,2,3,…,n，其輸出序列是p1,p2,p3,…,pn。若p1=3，則p2的值（

）。

A:可能是1B:一定是2C:可能是2D:一定是1

答案:可能是2已知一個棧的進棧序列為p1,p2,p3,…,pn，其輸出序列是1,2,3,…,n。若p3=1，則p1的值（

）。

A:一定是2B:一定是3C:可能是2D:不可能是2

答案:不可能是2設(shè)一個循環(huán)隊列Q[maxSize]的隊頭指針為front，隊尾指針為rear，隊列最大容量為maxSize，除此之外該隊列再沒有其他數(shù)據(jù)成員，則該隊列的隊滿條件是（

）。

A:Q.front==Q.rearB:Q.front==(Q.rear+1)%maxSizeC:Q.front+Q.rear>=maxSizeD:Q.rear==(Q.front+1)%maxSize

答案:Q.front==(Q.rear+1)%maxSize設(shè)循環(huán)隊列的存儲容量為maxSize，隊頭和隊尾指針分別為front和rear。若有一個循環(huán)隊列Q，可應(yīng)用下列語句（

）計算隊列元素個數(shù)？

A:Q.rear-Q.frontB:(Q.rear-Q.front)%maxSize+1C:Q.rear-Q.front+1D:(Q.rear-Q.front+maxSize)%maxSize

答案:(Q.rear-Q.front+maxSize)%maxSize一個隊列的進隊順序是1,2,3,4，則該隊列可能的輸出序列是（

）。

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

答案:1,2,3,4對于鏈式隊列，在執(zhí)行插入操作時（

）。

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

C:僅修改尾指針D:僅修改頭指針

答案:頭、尾指針可能都要修改最適合用作鏈式隊列的鏈表是（

）。

A:只帶隊頭指針的循環(huán)單鏈表B:只帶隊頭指針的非循環(huán)單鏈表C:帶有隊頭指針和隊尾指針的非循環(huán)單鏈表D:帶有隊頭指針和隊尾指針的循環(huán)單鏈表

答案:帶有隊頭指針和隊尾指針的非循環(huán)單鏈表最不適合用作鏈式隊列的鏈表是（

）。

A:帶有隊頭指針的雙向循環(huán)鏈表B:只帶隊尾指針的循環(huán)單鏈表C:只帶隊尾指針的雙向循環(huán)鏈表D:帶有隊頭指針的雙向非循環(huán)鏈表

答案:帶有隊頭指針的雙向非循環(huán)鏈表設(shè)一個鏈式隊列q的隊頭指針和隊尾指針分別為front和rear，則判斷隊列空的條件是（

）。

A:q.front==NULLB:q.front==q.rearC:q.rear==NULLD:q.front!=NULL

答案:q.front==NULL將遞歸算法轉(zhuǎn)換成非遞歸算法時，通常要借助的數(shù)據(jù)結(jié)構(gòu)是（

）。

A:棧B:樹C:線性表D:隊列

答案:棧棧與一般線性表的區(qū)別在于（）。

A:數(shù)據(jù)元素的個數(shù)不同B:運算是否受限制C:邏輯數(shù)據(jù)不同D:數(shù)據(jù)元素的類型不同

答案:運算是否受限制棧和隊列都是順序存取結(jié)構(gòu)。

A:錯B:對

答案:對對循環(huán)隊列初始化時·要求隊頭指針與隊尾指針指向同一個位置，不論隊列存儲中什么位置都可以。

A:錯B:對

答案:對棧是實現(xiàn)過程和函數(shù)等子程序調(diào)用所必需的結(jié)構(gòu)。

A:錯B:對

答案:對

第四章單元測試

字符串可定義為n(n≥0)個字符的有限（

），其中，n是字符串的長度，表明字符串中字符的個數(shù)。

A:數(shù)列B:集合C:聚合D:序列

答案:序列串是一種特殊的線性表，其特殊性體現(xiàn)在（

）。

A:可以順序存儲B:數(shù)據(jù)元素可以是多個字符C:可以鏈接存儲D:數(shù)據(jù)元素是一個字符

答案:數(shù)據(jù)元素是一個字符有n個字符的字符串的非空子串個數(shù)最多有（

）。

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

答案:n(n+1)/2兩個字符串相等的條件是（

）。

A:兩個串的長度相等，并且兩個串包含的字符相同B:兩個串的長度相等C:兩個串的長度相等，并且對應(yīng)位置上的字符相同D:兩個串包含的字符相等

答案:兩個串的長度相等，并且對應(yīng)位置上的字符相同設(shè)有兩個串：T和P，求P在T中首次出現(xiàn)的位置的運算叫做（

）。

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

答案:模式匹配在以下關(guān)于串的說法中正確的是（）。

A:用塊鏈存儲表示實現(xiàn)的串的結(jié)點大小為4,說明每個結(jié)點可存儲4個字符B:空串是由空格組成的串C:子串是從串中抽取出若干字符組成的串D:串長度是指串中不同字符的個數(shù)

答案:用塊鏈存儲表示實現(xiàn)的串的結(jié)點大小為4,說明每個結(jié)點可存儲4個字符設(shè)有兩個串T和P，求P在T中首次出現(xiàn)的位置的運算叫做（）。

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

答案:模式匹配設(shè)T="aaaaaacaaaca”，P=“aaac”，使用BF算法的模式匹配過程需要執(zhí)行的趟數(shù)為（）。

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

答案:4應(yīng)用KMP算法進行模式匹配時，next函數(shù)值序列的產(chǎn)生僅與模式串有關(guān)。

A:對B:錯

答案:對KMP算法的特點是在模式匹配時指示目標串當前比對位置的指針不會回退。

A:對B:錯

答案:對

第五章單元測試

對稀疏矩陣進行壓縮存儲的目的是（

）。

A:便于輸入和輸出B:節(jié)省存儲空間C:降低運算的時間復(fù)雜度D:便于進行矩陣運算

答案:節(jié)省存儲空間一個稀疏矩陣采用壓縮后，和直接采用二維數(shù)組存儲相比會失去（

）特性。

A:其余選項都不對B:順序存儲C:輸入輸出D:隨機存取

答案:隨機存取稀疏矩陣常用的壓縮存儲方法有（

）。

A:三元組和十字鏈表

B:散列表和十字鏈表C:二維數(shù)組

D:三元組和散列表

答案:三元組和十字鏈表

以下關(guān)于一維數(shù)組與順序表不同之處的說法中錯誤的是（）。

A:前者的元素數(shù)據(jù)類型相同，后者的元素數(shù)據(jù)類型可以不相同B:前者的長度不變，后者的長度可變C:前者既可以是邏輯結(jié)構(gòu)也可以是存儲結(jié)構(gòu)，后者是線性表的存儲結(jié)構(gòu)D:前者的元素可以不連續(xù)存放，后者的元素必須相繼存放

答案:前者的元素數(shù)據(jù)類型相同，后者的元素數(shù)據(jù)類型可以不相同將一個n*n的對稱矩陣A的對角線和對角線以上的部分按列優(yōu)先存放于一個一維數(shù)組中，那么A有(

)個矩陣元素未被存于sa中。

A:n(n-1)B:n^2/2

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

答案:n(n-1)/2設(shè)一維數(shù)組A[n]中每個元素占用6個存儲單元，若A[5]的存儲地址從100開始，則該數(shù)組的首地址是（)。

A:64B:76

C:30D:95

答案:64在二維數(shù)組A[9][10]中，每個數(shù)組元素占用3個存儲單元，從首地址SA開始按行優(yōu)先連續(xù)存放。在這種情況下，元素A[8][5]的起始地址為（

）。

A:SA+255B:SA+144C:SA+222D:SA+141

答案:SA+255設(shè)一個稀疏矩陣有1000行850列，其中有1000個非零元素。設(shè)每個整數(shù)占2字節(jié)，數(shù)據(jù)占4字節(jié)。則用三元組表存儲該矩陣時所需字節(jié)數(shù)是（）。

A:8000

B:1000

C:18000D:4000

答案:8000

二維數(shù)組是其數(shù)組元素為線性表的線性表。

A:對B:錯

答案:錯用一維數(shù)組存儲特殊矩陣，可以簡化對矩陣的存取操作。

A:對B:錯

答案:錯

第六章單元測試

樹最合適用來表示（

）。

A:有序數(shù)據(jù)元素B:元素之間具有分支層次關(guān)系的數(shù)據(jù)C:無序數(shù)據(jù)元素D:元素之間無聯(lián)系的數(shù)據(jù)

答案:元素之間具有分支層次關(guān)系的數(shù)據(jù)一棵有n個結(jié)點的樹的所有結(jié)點的度數(shù)之和為（

）。

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

答案:n-1設(shè)樹中某結(jié)點不是根結(jié)點，則離它最近的祖先結(jié)點是（

）。

A:父結(jié)點的父結(jié)點B:根結(jié)點C:父結(jié)點D:該結(jié)點本身

答案:父結(jié)點在二叉樹中某一結(jié)點的深度為3,高度為4,該樹的髙度至少為（

）。

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

答案:6設(shè)一棵高度為h的滿二叉樹有n個結(jié)點，其中有m個葉結(jié)點，則（

）。

A:n=h+mB:h+m=2nC:n=2^h-1D:m=h-1

答案:n=2^h-1具有33個結(jié)點的完全二叉樹，有（

）個度為1的結(jié)點。

A:1B:12C:0D:16

答案:0一顆有124個葉子結(jié)點的完全二叉樹最多有（

）個結(jié)點。

A:249B:247C:250D:248

答案:248一顆有129個葉結(jié)點的完全二叉樹最少有（

）個結(jié)點。

A:255B:257C:254D:258

答案:257如果二叉樹T2是由一棵樹T1轉(zhuǎn)換而來的二叉樹，那么T1中結(jié)點的先根序列對應(yīng)T2的（

）序列。

A:中序遍歷

B:先序遍歷

C:層次遍歷D:后序遍歷

答案:先序遍歷

如果二叉樹T2是由一棵樹T1轉(zhuǎn)換而來的二叉樹，那么T1中結(jié)點的后根序列對應(yīng)T2的（

）序列。

A:層次遍歷B:后序遍歷

C:中序遍歷

D:先序遍歷

答案:中序遍歷

一個深度為k且只有k個結(jié)點的二叉樹，按照完全二叉樹順序存儲的方式存放于一個一維數(shù)組A[n]中，那么n應(yīng)至少是（）。

A:2^kB:2^k-1C:2k+1D:2k

答案:2^k-1二叉樹的葉子結(jié)點在前序、中序和后序遍歷過程中的相對順序（

）。

A:無法確定B:其余選項都不對C:發(fā)生改變D:不發(fā)生改變

答案:不發(fā)生改變設(shè)n、m為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中，n在m前的條件是（）。

A:n在m左方B:n是m的子孫C:n在m右方D:n是m的祖先

答案:n在m左方在一棵二叉樹中有兩個結(jié)點n和m。在該二叉樹的前序遍歷序列中n在m之前，而在其后序遍歷序列中n在m之后，則n和m的關(guān)系是（）。

A:n是m的左兄弟B:n是m的右兄弟C:n是m的子孫D:n是m的祖先

答案:n是m的祖先前序序列與中序序列正好相反的非空二叉樹是（）。

A:滿二叉樹B:右單支樹C:左單支樹D:完全二叉樹

答案:左單支樹在中序線索二叉樹中，指針t所指結(jié)點的左子樹為空的充要條件是（）。

A:t->lchild==NULLB:其余選項都不對C:t->ltag==1且t->lchild==NULLD:t->ltag==1

答案:t->ltag==1且t->lchild==NULL設(shè)森林F對應(yīng)的二叉樹為A，它有m個結(jié)點。A的根為p，p的右子樹中結(jié)點個數(shù)為n，則森林F中第一棵樹的結(jié)點個數(shù)是（）。

A:m-n-1

B:m-nC:無法確定D:n+1

答案:m-n設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非葉結(jié)點，則B中右指針域為空的結(jié)點有（）個。

A:n+1B:nC:n-1

D:n+2

答案:n+1用n個權(quán)重構(gòu)造出來的Huffman樹共有（）個結(jié)點。

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

D:2n

答案:2n-1

設(shè)T是Huffman樹，具有5個葉結(jié)點，樹T的高度最高可以是（）。

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

答案:5

第七章單元測試

在無向圖中定義頂點的度為與它相關(guān)聯(lián)的（

）的數(shù)目。

A:權(quán)B:邊C:頂點D:權(quán)值

答案:邊具有n個頂點且每一對不同的頂點之間都有一條邊的無向圖被稱為（）。

A:無向樹圖B:無向強連通圖C:無向完全圖D:無向連通圖

答案:無向完全圖一個有n個頂點的無向圖最多有（

）邊。

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

C:nD:2n

答案:n(n-1)/2

具有6個頂點的無向圖至少應(yīng)有（

）條邊才能確保是一個連通圖。

A:7

B:6

C:5

D:8

答案:5

圖的簡單路徑是指（

）不重復(fù)的路徑。

A:頂點

B:權(quán)值C:邊與頂點均

D:邊

答案:頂點

在一個具有n個頂點的有向圖中，若所有頂點的出度之和為s，則所有頂點的入度之和為（

）。

A:s+1

B:n

C:s-1

D:s

答案:s

在下列有關(guān)圖的說法中正確的是（）。

A:在圖結(jié)構(gòu)中，頂點可以沒有任何前驅(qū)和后繼B:具有n個頂點的無向圖最多有n(n-1)條邊，最少有n-1條邊C:在有向圖中，各頂點的入度之和等于各頂點的出度之和D:在無向圖中，邊的條數(shù)是結(jié)點度數(shù)之和

答案:在有向圖中，各頂點的入度之和等于各頂點的出度之和對于一個具有n個頂點和e條邊的無向圖，若采用鄰接矩陣表示，則該矩陣中的非零元素個數(shù)是（

）。

A:n^2

B:eC:2eD:e^2

答案:2e無向圖的鄰接矩陣是一個（

）。

A:上三角矩陣B:對角矩陣C:對稱矩陣D:零矩陣

答案:對稱矩陣有n個頂點和e條邊的無向圖采用鄰接矩陣存儲，零元素的個數(shù)為（

）。

A:n^2-2e

B:eC:2eD:n^2-e

答案:n^2-2e

從鄰接矩陣可知，該有向圖共有（

）條有向邊。

A:3

B:9C:4

D:2

答案:4

帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（

）。

A:第i列非∞且非0的元素個數(shù)B:第i行非∞的元素之和C:第i行非∞且非0的元素個數(shù)D:第i列非∞的元素之和

答案:第i列非∞且非0的元素個數(shù)下列說法中正確的是（）。

A:一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一B:一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一C:一個圖的鄰接矩陣表示不唯一，鄰接表表示唯一D:一個圖的鄰接矩陣表示不唯一，鄰接表表示也不唯一

答案:一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一用鄰接表存儲圖所用的空間大?。?/p>

）。

A:只與圖的邊數(shù)有關(guān)系B:只與圖的頂點數(shù)有關(guān)C:與邊數(shù)的平方有關(guān)D:與圖的頂點數(shù)和邊數(shù)都有關(guān)

答案:與圖的頂點數(shù)和邊數(shù)都有關(guān)在下列有關(guān)圖的存儲結(jié)構(gòu)的說法中錯誤的是（

）。

A:鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用B:用鄰接矩陣存儲一個圖時所占用的存儲空間大小與圖中的頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)C:鄰接矩陣只適用于稠密圖（邊數(shù)接近于頂點數(shù)的平方），鄰接表適用于稀疏圖（邊數(shù)遠小于頂點數(shù)的平方）D:對同一個有向圖來說，鄰接表中邊結(jié)點數(shù)與逆鄰接表中邊結(jié)點數(shù)相等

答案:鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用設(shè)圖有n個頂點和e條邊，采用鄰接矩陣時，遍歷圖時的頂點所需時間為（）。

A:O(n)

B:O(ne)C:O(e)D:O(n^2)

答案:O(n^2)

設(shè)圖有n個頂點和e條邊，采用鄰接表時，遍歷圖的頂點所需時間為（）。

A:O(e)B:O(n^2)

C:O(ne)D:O(n+e)

答案:O(n+e)如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是（）。

A:有回路B:強連通圖C:連通圖D:—棵樹

答案:連通圖如果一個連通網(wǎng)絡(luò)G中各邊權(quán)值互不相同，權(quán)值最小的邊一定包含在G的(

)生成樹中。

A:廣度優(yōu)先B:深度優(yōu)先C:任何D:最小

答案:最小任何一個連通圖的最小生成樹（）。

A:一定有多棵B:可能不存在C:有一棵或多棵D:只有一棵

答案:有一棵或多棵Dijkstra算法是（）來求出圖中從某頂點到其余頂點最短路徑的。

A:通過廣度優(yōu)先遍歷求出圖的某頂點到其余頂點的最短路徑B:按長度遞增的順序求出圖的某頂點到其余頂點的最短路徑C:按長度遞減的順序求出圖的某項點到其余頂點的最短路徑D:通過深度優(yōu)先遍歷求出圖的某頂點到其余頂點的所有路徑

答案:按長度遞增的順序求出圖的某頂點到其余頂點的最短路徑已知一個帶權(quán)有向圖如圖所示，依據(jù)Dijkstra算法求從頂點1到其余各頂點的最短路徑的順序應(yīng)是（

）。

A:23546

B:25346

C:54632

D:25463

答案:25346

如果一個有向圖具有拓撲有序序列，并且頂點按拓撲有序序列編號，那么它的鄰接矩陣必定為（）。

A:三對角矩陣B:下三角矩陣C:對稱矩陣D:上三角矩陣

答案:上三角矩陣若一個有向圖中的部分頂點不能通過拓撲排序排到一個拓撲有序序列里，則可斷定該有向圖是一個（）。

A:含有多個入度為0的頂點的圖B:DAG圖C:含有頂點數(shù)大于1的強連通分量D:強連通圖

答案:含有頂點數(shù)大于1的強連通分量在如圖所示的AOE網(wǎng)中，關(guān)鍵路徑長度為（

）。

A:13B:23C:16D:22

答案:23

第八章單元測試

順序查找算法適用于（

）結(jié)構(gòu)。

A:連通圖B:線性表

C:查找網(wǎng)

D:查找樹

答案:線性表

在順序存儲的線性表R[30]上進行順序查找的平均查找長度為（

）。

A:15B:15.5

C:16

D:20

答案:15.5

對長度為10的順序表進行查找，若查找前面5個元素的概率相同，均為1/8，查找后面5個元素的概率相同，均為3/40，則查找到表中任一元素的平均查找長度為（）。

A:19/4

B:39/8

C:5D:5.5

答案:39/8

如果有5個關(guān)鍵字{a,b,c,d,e}放在順序表中，它們的查找概率分別為{0.35,0.25，0.20,0.15,0.05}，按照（

）順序存放可使平均查找長度達到最小。

A:a,b,c,d,eB:d,a,b,c,eC:e,d,c,b,aD:a,c,e,d,b

答案:a,b,c,d,e對長度為n的有序單鏈表，若查找每個元素的概率相等，則順序查找表中任一元素的查找成功的平均查找長度為（

）。

A:(n-1)/2

B:(n+1)/2

C:n/4D:n/2

答案:(n+1)/2

對線性表進行折半查找時，要求線性表必須（

）。

A:以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序B:以鏈接方式存儲C:以順序方式存儲D:以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序

答案:以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序采用折半查找方式查找一個長度為n的有序順序表時，其平均查找長度為（）。

A:O(n^2)B:O(log2n)C:O(nlog2n)D:O(n)

答案:O(log2n)采用折半查找法查找長度為n的有序順序表，查找每個元素的數(shù)據(jù)比較次數(shù)（

）對應(yīng)二叉判定樹的高度（設(shè)高度≥2）。

A:等于B:小于等于

C:小于D:大于

答案:小于等于

折半查找和二叉排序樹的時間性能（

）。

A:有時不相同

B:不定C:相同D:完全不同

答案:有時不相同

在常用的描述二叉排序樹的存儲結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點（

）。

A:左指針一定為空

B:左右指針均不為空C:左右指針均為空

D:右指針一定為空

答案:右指針一定為空m階B-樹是一棵（

）。

A:m叉高度平衡查找樹B:m-1叉高度平衡查找樹C:m+1叉高度平衡查找樹D:m叉查找樹

答案:m叉高度平衡查找樹下列關(guān)于m階B-樹的說法中錯誤的是（

）。

A:根結(jié)點中的數(shù)據(jù)是有序的B:根結(jié)點至多有m棵子樹C:非失敗結(jié)點至少有m/2（m為偶數(shù)）或m/2+1（m為奇數(shù)）棵子樹D:所有葉結(jié)點都在同一層次上

答案:非失敗結(jié)點至少有m/2（m為偶數(shù)）或m/2+1（m為奇數(shù)）棵子樹下面關(guān)于B-樹和B+樹的敘述中錯誤的是（

）。

A:B-樹和B+樹都能有效地支持順序查找B:B-樹和B+樹都能有效地支持隨機查找C:B-樹和B+樹都是平衡的多叉查找樹D:B-樹和B+樹都可用于文件的索引結(jié)構(gòu)

答案:B-樹和B+樹都能有效地支持順序查找散列法存儲的基本思想是根據(jù)（

）來決定元素的存儲地址。

A:關(guān)鍵字值

B:非碼屬性C:元素個數(shù)

D:元素的序號

答案:關(guān)鍵字值

設(shè)一個散列表中有n個元素，用散列法進行查找，理想情況下的平均查找長度是（

）。

A:O(log2n)

B:O(n)

C:O(1)

D:O(n^2)

答案:O(1)

使用散列函數(shù)將元素的關(guān)鍵字值映射為散列地址時，常會產(chǎn)生沖突。此時的沖突是指（

）。

A:兩個元素的關(guān)鍵字值不同，而非關(guān)鍵字值相同B:不同關(guān)鍵字值對應(yīng)到相同的存儲地址C:裝填因子過大，數(shù)據(jù)元素過多D:兩個元素具有相同的序號

答案:不同關(guān)鍵字值對應(yīng)到相同的存儲地址以下關(guān)于散列函數(shù)選擇原則的敘述中，不正確的是（

）。

A:散列函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中B:裝填因子必須限制在0.8以下C:散列函數(shù)應(yīng)是簡單的，能在較短的時間內(nèi)計算出結(jié)果D:散列函數(shù)的定義域應(yīng)包括全部關(guān)鍵字值,值域必須在表范圍之內(nèi)

答案:裝填因子必須限制在0.8以下計算出的地址分布最均勻的散列函數(shù)是（

）。

A:數(shù)字分析法

B:折疊法C:除留余數(shù)法

D:平方取中法

答案:除留余數(shù)法

除留余數(shù)法的基本思路是：設(shè)散列表的地址空間為0～m-1，元素的關(guān)鍵字值為k，用p去除k，將余數(shù)作為元素的散列地址，即h(k)=k%p，為了減少發(fā)生沖突的可能性，一般取p為（

）。

A:大于m的最小素數(shù)B:mC:小于或等于m的最大合數(shù)D:小于或等于m的最大素數(shù)

答案:小于或等于m的最大素數(shù)解決散列法中出現(xiàn)的沖突問題常采用的方法是（

）。

A:線性探測法、二次探測散列法、鏈地址法B:數(shù)字分析法、線性探測法、雙散列法C:數(shù)字分析法、除留余數(shù)法、平方取中法D:數(shù)字分析法、除留余數(shù)法、線性探測法

答案:線性探測法、二次探測散列法、鏈地址法在用開放定址法構(gòu)造出的散列表中，散列到同一個地址而引起的“二次聚集”問題是由于（

）引起的。

A:非同義詞之間發(fā)生沖突B:散列表“溢出”C:同義詞之間或非同義詞之間發(fā)生沖突D:同義詞之間發(fā)生沖突

答案:同義詞之間或非同義詞之間發(fā)生沖突散列表的平均查找長度（

）。

A:與處理沖突方法無關(guān)而與表的長度有關(guān)B:與處理沖突方法有關(guān)且與表的長度有關(guān)C:與處理沖突方法有關(guān)而與表的長度無關(guān)D:與處理沖突方法無關(guān)且與表的長度無關(guān)

答案:與處理沖突方法有關(guān)而與表的長度無關(guān)在由n個元素組成的有序表上進行折半查找時，對任一個元素進行查找的長度都不會大于。

A:錯B:對

答案:對對于兩棵具有相同關(guān)鍵碼集合而形狀不同的二叉查找樹，按中序遍歷它們得到的序列的各元素的順序是一樣的。

A:錯B:對

答案:對在一棵AVL樹中刪除一個結(jié)點后，失去平衡的結(jié)點多于一個。

A:對B:錯

答案:錯

第九章單元測試

每次從未排序的序列中取出一個元素與已排序的序列中的元素依次進行比較，然后把它插入到已排序序列中的適當位置，此種排序方法叫做（

）排序。

A:二路歸并排序B:直接插入排序

C:簡單選擇排序

D:起泡排序

答案:直接插入排序

對5個不同的數(shù)據(jù)元素進行直接插入排序，最多需要進行（

）次比較。

A:25

B:8C:10

D:15

答案:10

有一種排序方法，如果最小的元素位于待排序序列的最后，則在最后一趟排序開始之前，所有元素都不在其最終位置上，這種排序方法是（

）。

A:簡單選擇排序

B:快速排序C:直接插入排序

D:起泡排序

答案:直接插入排序

每次直接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做（）排序。

A:基數(shù)排序B:冒泡排序

C:堆排序

D:選擇排序

答案:冒泡排序

每次從待排序序列中挑選出一個最小或最大元素，把它交換到該序列的最前端，此種排序方法叫做（

）排序。

A:二路歸并排序B:直接插入排序

C:簡單選擇排序

D:起泡排序

答案:簡單選擇排序

在內(nèi)排序的過程中，通常需要對待排序元素序列的關(guān)鍵字做多趟掃描。采用不同的排序方法將產(chǎn)生不同的排序中間結(jié)果，設(shè)要將序列{tang,deng,an,wan,shi,bai,fang,li}中的關(guān)鍵字按升序排列，則（

）是冒泡排序一趟掃描的結(jié)果。

A:deng,tang,an,wan,bai,shi,fang,liB:an,deng,bai,li,shi,tang,fang,wanC:deng,an,tang,shi,bai,fang,li,wanD:deng,tang,an,wan,bai,shi,li,fang

答案:deng,an,tang,shi,bai,fang,li,wan在內(nèi)排序的過程中，通常需要對待排序元素序列的關(guān)鍵字做多趟掃描。采用不同的排序方法將產(chǎn)生不同的排序中間結(jié)果，設(shè)要將集合{tang,deng,an,wan,shi,bai,fang,li}中的關(guān)鍵字按升序排列，則（

）是初始步長為4的希爾排序一趟掃描的結(jié)果。

A:shi,bai,an,li,tang,deng,fang,wanB:li,deng,an,shi,bai,fang,tang,wanC:an,tang,deng,wan,shi,bai,fang,liD:an,bai,deng,fang,li,shi,tang,wan

答案:shi,bai,an,li,tang,deng,fang,wan在內(nèi)排序的過程中，通常需要對待排序元素序列的關(guān)鍵字做多趟掃描。采用不同的排序方法將產(chǎn)生不同的排序中間結(jié)果，設(shè)要將集合{tang,deng,an,wan,shi,bai,fang,li}中的關(guān)鍵字按升序排列，則（

）是以第一個元素為分界元素的快速排序一趟掃描的結(jié)果。

A:shi,bai,an,li,tang,deng,fang,wanB:deng,tang,an,wan,bai,shi,fang,liC:li,deng,an,shi,bai,fang,tang,wanD:deng,an,tang,shi,bai,fang,li,wan

答案:li,deng,an,shi,bai,fang,tang,wan一個元素序列的關(guān)鍵字為{46,79,56,38,40,84}，采用快速排序（以位于最左位置的元素為基準）得到的第一次劃分結(jié)果為（

）。

A:{38,46,56,79,40,84}B:{38,79,56,46,40,84}C:{38,46,79,56,40,84}

D:{40,38,46,79,56,84}

答案:{40,38,46,79,56,84}在快速排序中，要使最壞情況下的空間復(fù)雜度為O(log2n)，要對快速排序做（

）修改。

A:采用鏈表排序B:劃分軸點為三者取中

C:先排小子區(qū)間

D:先排大子區(qū)間

答案:劃分軸點為三者取中

在內(nèi)排序的過程中，通常需要對待排序元素序列的關(guān)鍵字做多趟掃描。采用不同的排序方法將產(chǎn)生不同的排序中間結(jié)果，設(shè)要將集合{tang,deng,an,wan,shi,bai,fang,li}中的關(guān)鍵字按升序排列，則（

）是大根堆排序初始建堆的結(jié)果。

A:deng,tang,an,wan,bai,shi,fang,liB:wan,tang,fang,li,shi,bai,an,dengC:an,ta