第一篇：數(shù)據(jù)結(jié)構(gòu)練習(xí)題及答案
數(shù)據(jù)結(jié)構(gòu)練習(xí)題及答案 第1章 緒論 一、判斷題 1.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。
（√）2.一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的一個基本運(yùn)算集構(gòu)成的整體。
（√）3.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。
（×）4.數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是相同的。
（×）5.程序和算法原則上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時可以通用。
（×）6.從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。
（√）7.數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象。
（√）8.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲形式。
（√）9.數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。
（×）10.算法是對解題方法和步驟的描述。
（√）二、填空題 1.數(shù)據(jù)有邏輯結(jié)構(gòu)和 存儲結(jié)構(gòu) 兩種結(jié)構(gòu)。
2.數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu) 。
3.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu) 。
4.樹形結(jié)構(gòu) 和圖形結(jié)構(gòu) 合稱為非線性結(jié)構(gòu)。
5.在樹形結(jié)構(gòu)中，除了樹根結(jié)點(diǎn)以外，其余每個結(jié)點(diǎn)只有1個前驅(qū)結(jié)點(diǎn)。
6.在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以任意多個 。
7.數(shù)據(jù)的存儲結(jié)構(gòu)又叫物理結(jié)構(gòu) 。
8.數(shù)據(jù)的存儲結(jié)構(gòu)形式包括順序存儲、鏈?zhǔn)酱鎯?、索引存儲和散列存?。
9.線性結(jié)構(gòu)中的元素之間存在一對一 的關(guān)系。
10.樹形結(jié)構(gòu)中的元素之間存在一對多 的關(guān)系。
11.圖形結(jié)構(gòu)的元素之間存在多對多 的關(guān)系。
12.數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法（或運(yùn)算） 3個方面的內(nèi)容。
13.數(shù)據(jù)結(jié)構(gòu)被定義為（D，R），其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系 有限集合。
14.算法是一個有窮指令 的集合。
15.算法效率的度量可以分為事先估算法和事后統(tǒng)計(jì)法 。
16.一個算法的時間復(fù)雜度是算法 輸入規(guī)模 的函數(shù)。
17.算法的空間復(fù)雜度是指該算法所耗費(fèi)的存儲空間 ，它是該算法求解問題規(guī)模的n的函數(shù)。
18.若一個算法中的語句頻度之和為T(n)=6n+3nlog2n,則算法的時間復(fù)雜度為O（nlog2n）。
19.若一個算法的語句頻度之和為T(n)=3n+nlog2+n2,則算法的時間復(fù)雜度為O（n2）。
20.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序問題中計(jì)算機(jī)的操作對象，以及它們之間的關(guān)系和運(yùn)算的學(xué)科。
三、選擇題 1.數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A）及它們之間的相互關(guān)系。
A．存儲結(jié)構(gòu)和邏輯結(jié)構(gòu) B．存儲和抽象 C．聯(lián)系和抽象 D．聯(lián)系與邏輯 2.在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（C）。
A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C．線性結(jié)構(gòu)和非線性結(jié)構(gòu) D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)。
3.數(shù)據(jù)在計(jì)算機(jī)存儲內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（C）。
A．存儲結(jié)構(gòu) B．邏輯結(jié)構(gòu) C．順序存儲結(jié)構(gòu) D．鏈?zhǔn)酱鎯Y(jié)構(gòu) 4.非線性結(jié)構(gòu)中的每個結(jié)點(diǎn)（D）。
A．無直接前驅(qū)結(jié)點(diǎn)． B．無直接后繼結(jié)點(diǎn)． C．只有一個直接前驅(qū)結(jié)點(diǎn)和一個直接后繼結(jié)點(diǎn)D．可能有多個直接前驅(qū)結(jié)點(diǎn)和多個直接后繼結(jié)點(diǎn) 5.鏈?zhǔn)酱鎯Y(jié)構(gòu)所占存儲空間（A）。
A．分兩部分，一部分存放結(jié)點(diǎn)的值，另一個部分存放表示結(jié)點(diǎn)間關(guān)系的指針。
B．只有一部分，存放結(jié)點(diǎn)的值。
C．只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針。
D．分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放結(jié)點(diǎn)所占單元素 6.算法的計(jì)算量大小稱為算法的（C）。
A．現(xiàn)實(shí)性 B．難度 C．時間復(fù)雜性 D．效率 7.數(shù)據(jù)的基本單位（B）。
A．?dāng)?shù)據(jù)結(jié)構(gòu) B．?dāng)?shù)據(jù)元素 C．?dāng)?shù)據(jù)項(xiàng) D．文件 8.每個結(jié)點(diǎn)只含有一個數(shù)據(jù)元素，所有存儲結(jié)點(diǎn)相繼存放在一個連續(xù)的存儲空間里，這種存儲結(jié)構(gòu)稱為（A）結(jié)構(gòu)。
A．順序結(jié)構(gòu) B．鏈?zhǔn)浇Y(jié)構(gòu) C．索引結(jié)構(gòu) D．散列結(jié)構(gòu) 9.每一個存儲結(jié)點(diǎn)不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（B）。
A．順序 B．鏈?zhǔn)? C．索引 D．散列 10.以下任何兩個結(jié)點(diǎn)之間都沒有邏輯關(guān)系的是（D）。
A．圖形結(jié)構(gòu) B．線性結(jié)構(gòu) C．樹形結(jié)構(gòu) D．集合 11.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是（C）。
A．物理結(jié)構(gòu) B．存儲結(jié)構(gòu) C．邏輯結(jié)構(gòu) D．邏輯和存儲結(jié)構(gòu) 12.下列4種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（A）。
A．集合 B．線性結(jié)構(gòu) C．樹形結(jié)構(gòu) D．圖形結(jié)構(gòu) 13.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（A）。
A．邏輯結(jié)構(gòu) B．存儲結(jié)構(gòu) C．邏輯實(shí)現(xiàn) D．存儲實(shí)現(xiàn) 14.每一個存儲結(jié)點(diǎn)只含有一個數(shù)據(jù)元素，存儲結(jié)點(diǎn)存放在連續(xù)的存儲空間，另外有一組指明結(jié)點(diǎn)存儲位置的表，該存儲方式是（C）存儲方式。
A．順序 B．鏈?zhǔn)? C．索引 D．散列 15.算法能正確的實(shí)現(xiàn)預(yù)定功能的特性稱為算法的（A）。
A．正確性 B．易讀性 C．健壯性 D．高效性 16.算法在發(fā)生非法操作時可以作出相應(yīng)處理的特性稱為算法的（C）。
A．正確性 B．易讀性 C．健壯性 D．高效性 17.下列時間復(fù)雜度中最壞的是（D）。
A．O（1）B.O（n）C.O(log2n)D.O(n2)18.下列算法的時間復(fù)雜度是（D）。
for(i=0;i A.空間復(fù)雜性和時間復(fù)雜性 B.正確性和簡明性 C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 20.計(jì)算機(jī)算法必須具備輸入、輸出和（C）。 A.計(jì)算方法 B.排序方法 C.解決問題的有限運(yùn)算步驟D.程序設(shè)計(jì)方法 第2章 線性表 一、判斷題 1.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲。 （×）2.鏈表的每個結(jié)點(diǎn)都恰好包含一個指針域。 （×）3.在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。 （√）4.順序存儲方式的優(yōu)點(diǎn)是存儲密度大，插入、刪除效率高。 （×）5.線性鏈表的刪除算法簡單，因?yàn)楫?dāng)刪除鏈中某個結(jié)點(diǎn)后，計(jì)算機(jī)會自動地將后續(xù)的各個單元向前移動。 （×）6.順序表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個結(jié)點(diǎn)可以是一個復(fù)雜類型。 （×）7.線性表鏈?zhǔn)酱鎯Φ奶攸c(diǎn)是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。 （√）8.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 （√）9.順序表結(jié)構(gòu)適宜進(jìn)行順序存取，而鏈表適宜進(jìn)行隨機(jī)存取。 （×）10.插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中是最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。（×）二、填空題 1.順序表中邏輯上相鄰的元素在物理位置上必須相鄰。 2.線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對一關(guān)系。 3.順序表相對于鏈表的優(yōu)點(diǎn)是節(jié)省存儲和隨機(jī)存取。 4.鏈表相對于順序表的優(yōu)點(diǎn)是插入、刪除方便。 5.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快速度存取線性表中的元素時，應(yīng)采用 順序 存儲結(jié)構(gòu)。 6.順序表中訪問任意一個結(jié)點(diǎn)的時間復(fù)雜度均為O（1）。 7.鏈表相對于順序表的優(yōu)點(diǎn)是插入、刪除方便； 缺點(diǎn)是存儲密度小。 8.在雙向鏈表中要刪除已知結(jié)點(diǎn)*P，其時間復(fù)雜度為O（1）。 9.在單向鏈表中要在已知結(jié)點(diǎn)*P之前插入一個新結(jié)點(diǎn)，需找到*P的直接前驅(qū)結(jié)點(diǎn)的地址，其查找的時間復(fù)雜度為O(n)。 10.在單向鏈表中需知道頭指針才能遍歷整個鏈表。 11.線性表中第一個結(jié)點(diǎn)沒有直接前驅(qū)，稱為開始結(jié)點(diǎn)。 12.在一個長度為n的順序表中刪除第i個元素，要移動 n-i 個元素。 13.在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移 n-i+1 個元素。 14.在無頭結(jié)點(diǎn)的單向鏈表中，第一個結(jié)點(diǎn)的地址存放在頭指針中，而其他結(jié)點(diǎn)的存儲地址存放在 前趨 結(jié)點(diǎn)的指針域中。 15.線性表的元素總數(shù)不確定，且經(jīng)常需要進(jìn)行插入和刪除操作，應(yīng)采用 鏈子 存儲結(jié)構(gòu)。 16.在線性表中的鏈?zhǔn)酱鎯χ?，元素之間的邏輯關(guān)系是通過 指針 決定。 17.在雙向鏈表中，每個結(jié)點(diǎn)都有兩個指針域，它們一個指向其 前趨 結(jié)點(diǎn)，另一個指向其后繼結(jié)點(diǎn)。 18.對一個需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用 鏈?zhǔn)? 存儲結(jié)構(gòu)為宜。 19.雙向鏈表中，設(shè)P是指向其中待刪除的結(jié)點(diǎn)，則需要執(zhí)行的操作為p->prior->next=p->next； p->next->prior=p->prior 20.在如圖所示的鏈表中，若在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩個結(jié)點(diǎn)，則可用語句S->next->next=p->next和P-> next=S； 來實(shí)現(xiàn)該操作。 p ∧ a b s 三、選擇題 1.在具有n個結(jié)點(diǎn)的單向鏈表中，實(shí)現(xiàn)（A）的操作，其算法的時間復(fù)雜度都是O(n).A.遍歷鏈表或求鏈表的第i個結(jié)點(diǎn) B.在地址為P的結(jié)點(diǎn)之后插入一個結(jié)點(diǎn) C.刪除開始結(jié)點(diǎn) D.刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn) 2.設(shè)a、b、c為3個結(jié)點(diǎn)，p、10、20分別代表它們的地址，則如下的存儲結(jié)構(gòu)稱為（B）。 p a 10 b 20 c ∧ A．循環(huán)鏈表 B．單向鏈表 C．雙向循環(huán)鏈表 D．雙向鏈表 3.單向鏈表的存儲密度（C）。 A.大于1 B.等于1 C.小于1 D.不能確定 4.已知一個順序存儲的線性表，設(shè)每個結(jié)點(diǎn)占m個存儲單元，若第一個結(jié)點(diǎn)的地址為B，則第i個結(jié)點(diǎn)的地址為（A）。 A.B+(i-1)×m B.B+i×m C.B-i×m D.B+(i+1)×m 5.在有n個結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時間復(fù)雜度為（B）。 A．O（1）B.O（n）C.O(n2)D.O(log2n)6.設(shè)front、rear分別為循環(huán)雙向鏈表結(jié)點(diǎn)的左指針和右指針，則指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是（D）。 A.P= =L B.P->front= =L C.P= =NULL D.P->rear= =L 7.兩個指針P和Q，分別指向單向鏈表的兩個元素，P所指元素是Q所指元素前驅(qū)的條件是（B）A．P->next= =Q->next B.P->next= =Q C.Q->next= =P D.P==Q 8.用鏈表存儲的線性表，其優(yōu)點(diǎn)是（C）。 A．便于隨機(jī)存取 B．花費(fèi)的存儲空間比順序表少 C．便于插入和刪除 D．?dāng)?shù)據(jù)元素的物理順序與邏輯順序相同 9.在單鏈表中，增加頭結(jié)點(diǎn)的目的是（C）。 A．使單鏈表至少有一個結(jié)點(diǎn) B．標(biāo)志表中首結(jié)點(diǎn)的位置 C．方便運(yùn)算的實(shí)現(xiàn) D．說明該單鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 10.下面關(guān)于線性表的敘述中，錯誤的是（D）關(guān)系。 A．順序表必須占一片地址連續(xù)的存儲單元B．順序表可以隨機(jī)存取任一元素 C．鏈表不必占用一片地址連續(xù)的存儲單元D．鏈表可以隨機(jī)存取任一元素 11.L是線性表，已知LengthList(L)的值是5，經(jīng)DelList(L，2)運(yùn)算后，LengthList(L)的值是（C）。 A．2 B．3 C．4 D．5 12.單向鏈表的示意圖如下： L A B C D ∧ P Q R 指向鏈表Q結(jié)點(diǎn)的前驅(qū)的指針是（B）。 A．L B．P C．Q D．R 13.設(shè)p為指向單循環(huán)鏈表上某結(jié)點(diǎn)的指針，則*p的直接前驅(qū)（C）。 A．找不到 B．查找時間復(fù)雜度為O（1）C．查找時間復(fù)雜度為O（n）D．查找結(jié)點(diǎn)的次數(shù)約為n 14.等概率情況下，在有n個結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動結(jié)點(diǎn)的數(shù)目為（8）。 A．n B.(n-1)/2 C.n/2 D.(n+1)/2 15.在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到其余各結(jié)點(diǎn)的是（C）。 A.雙向鏈表 B.單循環(huán)鏈表 C.單向鏈表 D.雙向循環(huán)鏈表 16.在順序表中，只要知道（D），就可以求出任一結(jié)點(diǎn)的存儲地址。 A.基地址 B.結(jié)點(diǎn)大小 C.向量大小 D.基地址和結(jié)點(diǎn)大小 17.在雙向鏈表中做插入運(yùn)算的時間復(fù)雜度為（A）。 A．O（1）B.O（n）C.O(n2)D.O(log2n)18.鏈表不具備的特點(diǎn)是（A）。 A．隨機(jī)訪問 B.不必事先估計(jì)存儲空間C.插入刪除時不需要移動元素 D.所需空間與線性表成正比 19.以下關(guān)于線性表的論述，不正確的為（C）。 A.線性表中的元素可以是數(shù)字、字符、記錄等不同類型B.線性順序表中包含的元素個數(shù)不是任意的 C.線性表中的每個結(jié)點(diǎn)都有且僅有一個直接前驅(qū)和一個直接后繼 D.存在這樣的線性表，即表中沒有任何結(jié)點(diǎn) 20.在（B）的運(yùn)算中，使用順序表比鏈表好。 A.插入 B.根據(jù)序號查找 C.刪除 D.根據(jù)元素查找 第3章 棧 一、判斷題 1.棧是運(yùn)算受限制的線性表。 （√）2.在棧空的情況下，不能作出棧操作，否則產(chǎn)生下溢。 （√）3.棧一定是順序存儲的線性結(jié)構(gòu)。 （×）4.棧的特點(diǎn)是“后進(jìn)先出”。 （√）5.空棧就是所有元素都為0的棧。 （×）6.在C（或C++）語言中設(shè)順序棧的長度為MAXLEN，則top=MAXLEN時表示棧滿。 （×）7.鏈棧與順序棧相比，其特點(diǎn)之一是通常不會出現(xiàn)棧滿的情況。 （√）8.一個棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。 （×）9.遞歸定義就是循環(huán)定義。 （×）10.將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。 （√）二、填空題 1.在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為 棧頂。 2.在順序棧中，當(dāng)棧頂指針top=-1時，表示 ?？?。 3.在有n個元素的棧中，進(jìn)棧操作時間復(fù)雜度為 O（1）。 4.在棧中，出棧操作時間復(fù)雜度為 O（1）。 5.已知表達(dá)式，求它的后綴表達(dá)式是 棧 的典型應(yīng)用。 6.在一個鏈棧中，若棧頂指針等于NULL，則表示 ?？?。 7.向一個棧頂指針為top的鏈棧插入一個新結(jié)點(diǎn)*p時，應(yīng)執(zhí)行p->next=top;top=p； 操作。 8.順序棧S存儲在數(shù)組S->data[0…MAXLEN-1]中，進(jìn)棧操作時要執(zhí)行的語句有：S->top++。(或S->top+1)S->data[S->top]=x 9.鏈棧LS，指向棧頂元素的指針是LS->next。 10.從一個棧刪除元素時，首先取出 棧頂元素，然后再移動棧頂指針。 11.由于鏈棧的操作只在鏈表的頭部進(jìn)行，所以沒有必要設(shè)置 頭 結(jié)點(diǎn)。 12.已知順序棧S，在對S進(jìn)棧操作之前首先要判斷 棧是否滿。 13.已知順序棧S，在對S出棧操作之前首先要判斷 棧是否空。 14.若內(nèi)在空間充足， 鏈 ?？梢圆欢x棧滿運(yùn)算。 15.鏈棧LS為空的條件是 LS->next=NULL。 16.鏈棧LS的棧頂元素是鏈表的 首 元素。 17.同一棧的各元素的類型 相同。 18.若進(jìn)棧的次序是A、B、C、D、E，執(zhí)行3次出棧操作以后，棧頂元素為 B。 19.A+B/C-D*E的后綴表達(dá)式是 ABC/+DE*-。 C。 三、選擇題 1.插入和刪除操作只能在一端進(jìn)行的線性表，稱為（C）。 A．隊(duì)列 B．循環(huán)隊(duì)列 C．棧 D．循環(huán)棧 2.設(shè)有編號為1，2。3，4的4輛列車，順序進(jìn)入一個棧結(jié)構(gòu)的站臺，下列不可能的出站順序?yàn)椋―）。 A．1234 B．1243 C．1324 D．1423 3.如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（B）。 A．必須判別棧是否滿 B．必須判別棧是否為空 C．必須判別棧元素類型 D．?？刹蛔鋈魏闻袆e 4.元素A、B、C、D依次進(jìn)棧以后，棧頂元素是（D）A．A B．B C．C D．D 5.順序棧存儲空間的實(shí)現(xiàn)使用（B）存儲元素。 A．鏈表 B．?dāng)?shù)組 C．循環(huán)鏈表 D．變量 6.在C（或C++）語言中，一個順序棧一旦被聲明，其占用空間的大?。ˋ）。 A．已固定 B．不固定 C．可以改變 D．動態(tài)變化 7.帶頭結(jié)點(diǎn)的鏈棧LS的示意圖如下，棧頂元素是（A）。 LS H A B C D ∧ A．A B．B C．C D．D 8.鏈棧與順序棧相比，有一個比較明顯的優(yōu)點(diǎn)是（B）。 A.插入操作更加方便 B.通常不會出現(xiàn)棧滿的情況 C.不會出現(xiàn)棧空的情況 D.刪除操作更加方便 9.從一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列（d）命令。 A．x=top;top->next;B.top=top->next;x=top->data C.x=top->data;D.x=top->data;top=top->next 10.在一個棧頂指針為HS的鏈棧中，將一個S指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行下列（B）命令。 A.HS->next=S B.S->next=HS->next;HS->next=S;C.S->next=HS->next;HS=S;D.S->next=HS=HS->next 11.4元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop(S，x)運(yùn)算后，棧頂元素的值是（B）。 A．A B．B C．C D．D 12.元素A、B、C、D依次進(jìn)棧以后，棧底元素是（A）。 A．A B．B C．C D．D 13.經(jīng)過下列棧的運(yùn)算后，再執(zhí)行ReadTop(s)的值是（A）。 InitStack(s);Push(s，a);Push(s，b);Pob(s);A.a B.b C.1 D.0 14.經(jīng)過下列棧的運(yùn)算后，x的值是（B）。 InitStack(s)（初始化棧）;Push(s，a);Push(s，b);ReadTop(s)； Pob(s，x);A.a B.b C.1 D.0 15.經(jīng)過下列棧的運(yùn)算后，x的值是（B）。 InitStack(s)（初始化棧）;Push(s,a);Pob(s，x);Push(s,b);Pob(s，x);A.a B.b C.1 D.0 16.經(jīng)過下列棧的運(yùn)算后,SEmpty(s)的值是（C）。 InitStack(s)（初始化棧）;Push(s,a);Push(s,b);Pob(s，x);Pob(s，x);A.a B.b C.1 D.0 17.向順序棧中輸入元素時（B）。 A．先存入元素，后移動棧頂指針 B．先移動棧頂指針，后存入元素 C．誰先誰后無關(guān)緊要 D．同時進(jìn)行 18.初始化一個空間大小為5的順序棧S后，S->top的值是（B）。 A．0 B．-1 C．不再改變 D．動態(tài)變化 19.設(shè)有一個入棧的次序A、B、C、D、E，則棧不可能的輸出序列是（C）。 A．EDCBA B．DECBA C．DCEAB D．ABCDE 20.設(shè)有一個順序棧S，元素A、B、C、D、E、F依次進(jìn)棧，如果6個元素出棧的順序是B、D、C、F、E、A，則棧的容量至少應(yīng)是（A）。 A．3 B．4 C．5 D．6 第4章 隊(duì)列 一、判斷題 1.隊(duì)列是限制在兩端進(jìn)行操作的線性表。 （√）2.判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個結(jié)點(diǎn)。 （√）3.在鏈隊(duì)列上做出隊(duì)操作時，會改變front指針的值。 （×）4.在循環(huán)隊(duì)列中，若尾指針rear大于頭指針front，其元素個數(shù)為rear-front。 （√）5.在單向循環(huán)鏈表中，若頭指針為h，那么p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是p=h。 （×）6.鏈隊(duì)列在一定范圍內(nèi)不會出現(xiàn)隊(duì)滿的情況。 （√）7.在循環(huán)鏈隊(duì)列中無溢出現(xiàn)象。 （×）8.棧和隊(duì)列都是順序存儲的線性結(jié)構(gòu)。 （×）9.在隊(duì)列中允許刪除的一端稱為隊(duì)尾。 （×）10.順序隊(duì)和循環(huán)隊(duì)關(guān)于隊(duì)滿和隊(duì)空的判斷條件是一樣的。 （×）二、填空題 1.在隊(duì)列中存取數(shù)據(jù)應(yīng)遵循的原則是 先進(jìn)先出。 2.隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算線性表。 3.在隊(duì)列中，允許插入的一端稱為 隊(duì)尾。 4.在隊(duì)列中，允許刪除的一端稱為 隊(duì)首（或隊(duì)頭）。 5.隊(duì)列在進(jìn)行出隊(duì)操作時，首先要判斷隊(duì)列是否為 空。 6.順序隊(duì)列在進(jìn)行入隊(duì)操作時，首先在判斷隊(duì)列是否為 滿。 7.順序隊(duì)列初始化后，初始化后，front=rear= -1。 8.解決順序隊(duì)列“假溢出”的方法是采用 循環(huán)隊(duì)列。 9.循環(huán)隊(duì)列的隊(duì)指針為front，隊(duì)尾指針為rear，則隊(duì)空的條件為 front= =rear。 10.鏈隊(duì)列LQ為空時，LQ->front->next= NULL。 11.設(shè)長度為n的鏈隊(duì)列用單循環(huán)表表示，若只設(shè)頭指針，則入隊(duì)操作的時間復(fù)雜度為 O(n)。 12.設(shè)長度為n的鏈隊(duì)列用單循環(huán)表表示，若只設(shè)尾指針，則入隊(duì)操作的時間復(fù)雜度為 O(1)。 13.在一個鏈隊(duì)列中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為 空。 14.設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)首元素，尾指針rear指向隊(duì)尾元素后的一個空閑元素，隊(duì)列的最大空間為MAXLEN，則隊(duì)滿標(biāo)志為 front= =(rear+1)%MAXLEN。 15.在一個鏈隊(duì)列中，若隊(duì)首指針為front，隊(duì)尾指針為rear，則判斷隊(duì)列只有一個結(jié)點(diǎn)的條件為front= =rear或front!。 16.向一個循環(huán)隊(duì)列中插入元素時，首先要判斷 隊(duì)尾指針，然后再向指針?biāo)傅奈恢脤懭胄碌臄?shù)據(jù)。 17.讀隊(duì)首元素的操作 不改變或不影響隊(duì)列元素的個數(shù)。 18.設(shè)循環(huán)隊(duì)列的容量為40（序號0～39），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)的運(yùn)算后，front=11，rear=19，則循環(huán)隊(duì)列中還有 8 個元素。 19.隊(duì)列Q，經(jīng)過下列運(yùn)算：InitQueue(Q)(初始化隊(duì)列)； InQueue(Q,a)； InQueue(Q,b)； OutQueue(Q,x)； ReadFront(Q,x)； QEmpty(Q)； 后的值是 8。 20.隊(duì)列Q經(jīng)過InitQueue(Q)(初始化隊(duì)列)； InQueue(Q,a)； InQueue(Q,b)； ReadFront(Q,x)后，x的值是 a。 三、選擇題 1.隊(duì)列是限定在（D）進(jìn)行操作的線性表。 A．中間者 B.隊(duì)首 C.隊(duì)尾 D.端點(diǎn) 2.隊(duì)列中的元素個數(shù)是（B）。 A．不變的 B.可變的 C.任意的 D.0 3.同一隊(duì)列內(nèi)的各元素的類型（A）。 A.必須一致 B.不能一致 C.可以不一致 D.不限制 4.隊(duì)列是一個（C）線性表結(jié)構(gòu)。 A.不加限制的 B.推廣了的 C.加了限制的 D.非 5.當(dāng)利用大小為n的數(shù)組順序存儲一個隊(duì)列時，該隊(duì)列的最后一個元素的下標(biāo)為（B）。 A.n-2 B.n-1 C.n D.n+1 6.一個循環(huán)隊(duì)列一旦說明，其占用空間的大?。ˋ）。 A.已固定 B.可以變動 C.不能固定 D.動態(tài)變化 7.循環(huán)隊(duì)列占用的空間（A）。 A.必須連續(xù) B.不必連續(xù) C.不能連續(xù) D.可以不連續(xù) 8.存放循環(huán)隊(duì)列元素的數(shù)組data有10個元素，則data數(shù)組的下標(biāo)范圍是（B）。 A.0～10 B.0～9 C.1～9 D.1～10 9.若進(jìn)隊(duì)的序列為A、B、C、D，則出隊(duì)的序列是（C）。 A.B、C、D、A B.A、C、B、D C.A、B、C、D D.C、B、D、A 10.4個元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，則隊(duì)尾元素是（D）A．A B．B C．C D．D 11.4個元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行一次QutQueue(Q)操作后，隊(duì)頭元素是（B）。 A.A B.B C.C D.D 12.4個元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行4次QutQueue(Q)操作后，再執(zhí)行QEmpty(Q)； 后的值是（B）。 A.0 B.1 C.2 D.3 13.隊(duì)列Q，經(jīng)過下列運(yùn)算后，x的值是（B）。InitQueue(Q)(初始化隊(duì)列)； InQueue(Q,a)； InQueue(Q,b)； OutQueue(Q,x)； ReadFront(Q,x)； A.a B.b C.0 D.1 14.循環(huán)隊(duì)列SQ隊(duì)滿的條件是（B）。 A.SQ->rear= =SQ->front B.(SQ->rear+1)%MAXLEN= =SQ->front C.SQ->rear= =0 D.SQ->front= =0 15.設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針，若想在鏈棧的棧頂插入一個由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行下列（A）操作。 A.s->next=top->next;top->next=s;B.top->next=s;C.s->next=top;top->next;D.s->next=top;top=s;16.帶頭結(jié)點(diǎn)的鏈隊(duì)LQ示意圖如下，鏈隊(duì)列的隊(duì)頭元素是（A）。 LQ->front H A B C D ∧ LQ->rear A．A B．B C．C D．D 17.帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下，指向鏈隊(duì)列的隊(duì)頭指針是（C）。 LQ->front H A B C D ∧ LQ->rear A.LQ->front B.LQ->rear C.LQ->front->next D.LQ->rear->next 18.帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下,在進(jìn)行進(jìn)隊(duì)的運(yùn)算時指針LQ->frnot(A).LQ->front H A B C D ∧ LQ->rear A.始終不改變 B.有時改變 C.進(jìn)隊(duì)時改變 D.出隊(duì)時改變 19.隊(duì)列Q，經(jīng)過下列運(yùn)算后，再執(zhí)行QEmpty(Q)的值是（C）。 InitQueue(Q)(初始化隊(duì)列)； InQueue(Q,a)； InQueue(Q,b)； OutQueue(Q,x)； ReadQueue(Q,x)； A.a B.b C.0 D.1 20.若用一個大小為6數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊(duì)列中刪除一個元素，再加入兩個元素后，front和rear的值分別為（B）。 A.5和1 B.4和2 C.2和4 D.1和5 第5章 串 一、判斷題 1.串是n個字母的有限序列。 （×）2.串的數(shù)據(jù)元素是一個字符。 （√）3.串的長度是指串中不同字符的個數(shù)。 （×）4.如果兩個串含有相同的字符，則說明它們相等。 （×）5.如果一個串中所有的字母均在另一個串中出現(xiàn)，則說明前者是后者的子串。 （×）6.串的堆分配存儲是一種動態(tài)存儲結(jié)構(gòu)。 （√）7.“DT”是“DATA”的子串。 （×）8.串中任意個字符組成的子序列稱為該串的子串。 （×）9.子串的定位運(yùn)算稱為模式匹配。 （√）10.在鏈串中為了提高存儲密度，應(yīng)該增大結(jié)點(diǎn)的大小。 （√）二、填空題 1.由零個或多個字符組成的有限序列稱為 字符串（或串）。 2.字符串按存儲方式可以分為順序存儲、鏈接存儲和 堆分配存儲。 3.串的順序存儲結(jié)構(gòu)簡稱為 順序串。 4.串順序存儲非緊湊格式的缺點(diǎn)是 空間利用率低。 5.串順序存儲緊湊格式的缺點(diǎn)是對串的字符處理 效率低。 6.串鏈接存儲的優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)是 空間利用率。 7.在C或C++語言中，以字符 ＼0 表示串值的終結(jié)。 8.空格串的長度等于 空格的個數(shù)。 9.在空串和空格串中，長度不為0的是 空格串。 10.兩個串相等是指兩個串長度相等，且對應(yīng)位置的 字符都相同。 11.設(shè)“S=My Music”，則LenStr(s)= 8。 12.兩個字符串分別為； S1=”Today is”、S2=”30 July，2005”，ConcatStr(S1，S2)的結(jié)果是 Today is 30 July,2005。 13.求子串函數(shù)SubStr(“Today is 30 July，2005”，13，4)的結(jié)果是 July。 14.在串的運(yùn)算中，EqualStr(aaa,aab)的返回值 <0。 15.在串的運(yùn)算中，EqualStr(aaa,aaa)的返回值 0。 16.在子串的定位運(yùn)算中，被匹配的主串稱為目標(biāo)串，子串稱為 模式。 17.模式匹配成功的起始位置稱為 有效位移。 18.設(shè)S=”abccdcdccbaa”，T=”cdcc”，則第 6 次匹配成功。 19.設(shè)S=”c:/mydocument/text1.doc”，T=”mydont”，則字符定位的位置為 0。 20.若n為主串長度，m為子串長度，n>>m，則模式匹配算法最壞情況下的時間復(fù)雜度為(n-m+1)*m。 三、選擇題 1.串是和種特殊的線性表，其特殊體現(xiàn)在（B）。 A．可能順序存儲 B．?dāng)?shù)據(jù)元素是一個字符C．可以鏈接存儲 D．?dāng)?shù)據(jù)元素可以是多個字符 2.某串的長度小于一常數(shù)，則采用（B）存儲方式最節(jié)省空間。 A．鏈?zhǔn)? B．順序 C．堆結(jié)構(gòu) D．無法確定 3.以下論述正確的是（C）。 A．空串與空格串是相同的B．”tel”是”Teleptone”的子串 C．空串是零個字符的串 D．空串的長度等于1 4.以下論述正確的是（B）。 A．空串與空格串是相同的B．”ton”是”Teleptone”的子串 C．空格串是有空格的串 D．空串的長度等于1 5.以下論斷正確的是（A）。 A．全部由空格組成的串是空格串 B．”BEUIJING”是”BEI JING”的子串 C．”something”<”Something” D．”BIT”=”BITE” 6.設(shè)有兩個串S1和S2，則EqualStr（S1，S2）運(yùn)算稱作（D）。 A．串連接 B．模式匹配 C．求子串 D．串比較 7.串的模式匹配是指（D）。 A．判斷兩個串是否相等 B．對兩個串比較大小 C．找某字符在主串中第一次出現(xiàn)的位置D．找某子串在主串中第一次出現(xiàn)的第一個字符位置 8.若字符串”ABCDEFG”采用鏈?zhǔn)酱鎯?，假設(shè)每個字符占用1個字節(jié)，每個指針占用2個字節(jié)。則該字符串的存儲密度為（D）。 A．20% B．40% C．50% D．33.3% 9.若字符串”ABCDEFG”采用鏈?zhǔn)酱鎯?，假設(shè)每個指針占用2個字節(jié)，若希望存儲密度為50%，則每個結(jié)點(diǎn)應(yīng)存儲（A）個字符。 A.2 B.3 C.4 D.5 10.設(shè)串S1=”IAM”，S2=”A SDUDENT”，則ConcatStr(S1，S2)=（B）。 A．”I AM” B.”I AM A SDUDENT” C.”IAMASDUDENT” D.”A SDUDENT” 11.設(shè)S=””，則LenStr(S)=（A）。 A.0 B.1 C.2 D.3 12.設(shè)目標(biāo)串T=”AABBCCDDE”，模式P=”ABCDE”，則該模式匹配的有效位移為（A）。 A.0 B.1 C.2 D.3 13.設(shè)目標(biāo)串T=”AABBCCDDEEFF”，模式P=”CCD”，則該模式匹配的有效位移為（D）。 A.2 B.3 C.4 D.5 14.設(shè)目標(biāo)串T=”aabaababaabaa”，模式P=”abab”，模式匹配算法的外層循環(huán)進(jìn)行了（D）次。 A.1 B.9 C.4 D.5 15.模式匹配算法在最壞情況下的時間復(fù)雜是（D）。 A.O(m)B.O(n)C.O(m+n)D.O(m×n)16.S=”morning”,執(zhí)行求子串函數(shù)SubSur(S,2,2)后結(jié)果為（B）。 A.”mo” B.”or” C.”in” D.”ng” 17.S1=”good”，S2”morning”，執(zhí)行串連接函數(shù)ConcatStr(S1，S2)后結(jié)果為（A）。 A.”goodmorning” B.”good morning” C.”GOODMORNING” D.”GOODMORNING” 18.S1=”good”, S2=”morning”執(zhí)行函數(shù)SubSur(S2,4,LenStr(S1))后的結(jié)果為（B）。 A.”good” B.”ning” C.”go” D.”morn” 19.設(shè)串S1=”ABCDEFG”，S2=”PQRST”，則ConcatStr（SubStr(S1，2，LenStr（S2）），SubStr(S1，LenStr（S2），2））的結(jié)果串為（D）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 20.若串S=”SOFTWARE”，其子串的數(shù)目最多是（C）。 A．35 B.36 C.37 D.38 第6章 多維數(shù)組和廣義表 一、判斷題 1.n維多維數(shù)可以視為n-1維數(shù)組元素組成的線性結(jié)構(gòu)。 （√）2.稀疏矩陣中非零元素的個數(shù)遠(yuǎn)小于矩陣元素的總數(shù)。 （√）3.上三角矩陣主對角線以上（不包括主對角線的元素），均為常數(shù)C。 （×）4.數(shù)組元素可以由若干數(shù)據(jù)項(xiàng)組成。 （√）5.數(shù)組的三元組表存儲是對稀疏矩陣的壓縮存儲。 （√）6.任何矩陣都可以進(jìn)行壓縮存儲。 （×）7.廣義表是線性表的推廣，所以廣義表也是線性表。 （×）8.廣義表LS=（a0，a1，……an-1），則an-1是其表尾。 （×）9.廣義表（（a，b）a，b）的表頭和表尾是相等的。 （√）10.一個廣義表的表尾總是一個廣義表。 （√）二、填空題 1.多維數(shù)組的順序存儲方式有按行優(yōu)先順序存儲和 按優(yōu)先順序存儲 兩種。 2.在多維數(shù)組中，數(shù)據(jù)元素的存放地址可以直接通過地址計(jì)算公式算出，所以多維數(shù)組是一 種 隨機(jī) 存取結(jié)構(gòu)。 3.在n維數(shù)組中的每一個元素最多可以有 n 個直接前驅(qū)。 4.輸出二維數(shù)組A[n][m]中所有元素值的時間復(fù)雜度為 n(n*m)。0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 3 0 0 7 0 0 5 0 0 0 0 0 0 0 0 9 0 圖6-19 稀疏矩陣A 5.數(shù)組元素a[0…2][0…3]的實(shí)際地址是2000，元素長度是4，則LOC[1，2]= 2024。 6.稀疏矩陣的三元組有 3 列。 7.稀疏矩陣的三元組中第1列存儲的是數(shù)組中非零元素所在的 行數(shù)。 8.n階對稱矩，如果只存儲下三角元素，只需要 n(n-1)/2 個存儲單元。 9.稀疏矩陣A如圖6-19所示，其非零元素存三元組表中，三元組（4，1，5）按列優(yōu)先順序存儲在三元組表的第 4 項(xiàng)。 10.稀疏疏矩陣的壓縮存儲方法通常有三元組表和 十字鏈表 兩種。 11.任何一個非空廣義表的表尾必定是廣義表（或子表）。 12.tail(head((a，b)(c，d)= b。 13.設(shè)廣義表（（a，b，c））則將c分離出來的運(yùn)算是 head(tail(tail(head(L))))。 14.廣義表現(xiàn)出（（a，b）c，d），表尾是 (c,d)。 15.n階下三角矩陣，因?yàn)閷蔷€的上方是同一個常數(shù)，需要 n(n-1)/2+1 個存儲單元。 16.稀疏矩陣中有n個非零元素，則三元組有 n 行。 17.廣義表LS=（a,（b）,（（c,（d））））的長度是 3。 18.廣義表LS=（a,（b）,（（c,（d））））的深度是 4。 19.廣義表LS=（（），L）,則L的深度是 ∞。 20.廣義表LS=（a,（b）,（（c,（d））））的表尾是 ((b),((c,(d))))。 三、選擇題 1.在一個m維數(shù)組中，（D）恰好有m個直接前驅(qū)和m個直接界后繼。 A.開始結(jié)點(diǎn) B.總終端結(jié)點(diǎn) C.邊界結(jié)點(diǎn) D.內(nèi)部結(jié)點(diǎn) 2.對下述矩陣進(jìn)行壓縮存儲后，失去隨機(jī)存取功能的是（D）。 A.對稱矩陣 B.三角矩陣 C.三對角矩陣 D.稀疏矩陣 3.在按行優(yōu)先順序存儲的三元組表中，下述陳述錯誤的是（D）。 A.同一行的非零元素，是按列號遞增次序存儲的B.同一列的非零元素，是按行號遞增次序存儲的 C.三元組表中三元組行號是遞增的 D.三元組表中三元組列號是遞增的 4.對稀疏矩陣進(jìn)行壓縮存儲是為了（B）。 A.降低運(yùn)算時間B.節(jié)約存儲空間C.便于矩陣運(yùn)算D.便于輸入和輸出 5.若數(shù)組A[0‥m] [0‥n]按列優(yōu)先順序存儲，則aij的地址為（A）。 A.LOC(a00)+[j×m+i] B.LOC(a00)+[j×n+i] C.LOC(a00)+[(j-1)×n+i-1] D.LOC(a00)+[(j-1)×m+i-1] 6.下列矩陣是一個（B）。 A． 對稱矩陣 B．三角矩陣 C．稀疏矩陣 D．帶狀矩陣 1 0 0 0 2 3 0 0 4 5 6 0 7 8 9 10 7.在稀疏矩陣的三元組表示法中，每個三元組表示（D）。 A．矩陣非零元素的值 B．矩陣中數(shù)據(jù)元素的行號和列號 C．矩陣中數(shù)據(jù)元素的行號、列號和值 D．矩陣中非零數(shù)據(jù)元素的行號、列號和值 8.已知二維數(shù)組A[6][10]，每個數(shù)組元素占4個存儲單元，若按行優(yōu)先順序存儲存放數(shù)組元素a[3][5]的存儲地址是1000，則a[0][0]的存儲地址是（B）。 A．872 B．860 C．868 D．864 9.廣義表是線性表的推廣，它們之間的區(qū)別于（A）。 A．能否使用子表 B．肥否使用原子項(xiàng) C．是否能為空 D．表的長度 10.下列廣義表屬于線性表的是（B）。 A.E=(a,E)B.E=(a,b,c)C.E=(a,(b,c))D.E=(a,L);L=()11.廣義表（（a,b）,c,d）的表尾是（D）。 A．a(chǎn) B．d C．(a,b)D．(c,d)12.廣義表A=((x,(a,b)),(x,(a,b),y)),則運(yùn)算head(head(tail(A)))為（A）。 A． x B．(a,b)C．(x,(a,b))D．A 13.tail(head((a,b),c,(c,d)))的結(jié)果是（B）。 A． b B．(b)C．(a,b)D．(d)14.若廣義表滿足head(L)=tail(L),則L的形式是（B）。 A．空表 B．若L=（a1,…,an）,則a1=(a2,…,an)C．若L=（a1,…,an）,則(a1=a2,=…an)D．((a1)(a1))15.數(shù)組是一個（B）線性表結(jié)構(gòu)。 A.非 B.推廣了的 C.加了限制的 D.不加限制的 16.數(shù)組A[0：1，0：1，0：1]共有（D）元素。 A.4 B.5 C.6 D.8 17.廣義表（（a,b）,c,d）的表頭是（C）。 A.a B.d C.(a,b)D.(c,d)18.廣義表A=(a),則表尾為（C）。 A.a B.(())C.空表 D.(a)19.以下（C）是稀疏矩陣的壓縮存儲方法。 A.一維數(shù)組 B.二維數(shù)組 C.三元數(shù)組 D.廣義表 20.設(shè)廣義表D=(a,b,c,d),其深度為（D）。 A.2 B.3 C.4 D.∞ 第7章 樹和二叉樹 一、判斷題 1.樹結(jié)構(gòu)中每個結(jié)點(diǎn)最多只有一個直接前驅(qū)。 （√）2.完全二叉樹一定是滿二叉樹。 （×）3.在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。 （×）4.一棵二叉樹中序遍歷序列的最后一個結(jié)點(diǎn)，必定是該二叉樹前序遍歷的最后一個結(jié)點(diǎn)。（√）5.二叉樹的前序遍歷中，任意一個結(jié)點(diǎn)均處于其子女結(jié)點(diǎn)的前面。 （√）6.由二叉樹的前序遍歷序列和中序遍歷序列，可以推導(dǎo)出后序遍歷的序列。 （√）7.在完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必然是葉子結(jié)點(diǎn)。 （√）8.在哈夫曼編碼中，當(dāng)兩個字符出現(xiàn)的頻率相同，其編碼也相同，對于這種情況應(yīng)該做特殊處理。（×）9.含多于兩棵樹的森林轉(zhuǎn)換的二叉樹，其根結(jié)點(diǎn)一定無右孩子。 （×）10.具有n個葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1個結(jié)點(diǎn)。 （√）二、填空題 1.在樹中，一個結(jié)點(diǎn)所擁有的子樹數(shù)稱為該結(jié)點(diǎn)的 度。 2.度為零的結(jié)點(diǎn)稱為 葉（或葉子，或終端）結(jié)點(diǎn)。 3.樹中結(jié)點(diǎn)的最大層次稱為樹的 深度（或高度）。 4.對于二叉樹來說，第i層上至多有 2i-1 個結(jié)點(diǎn)。 5.深度為h的二叉樹至多有 2h-1 個結(jié)點(diǎn)。 6.由一棵二叉樹的前序序列和 中序 序列可唯一確定這棵二叉樹。 7.有20個結(jié)點(diǎn)的完全二叉樹，編號為10的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號是 5。 8.哈夫曼樹是帶權(quán)路徑長度的 最小 的二叉樹。 9.由二叉樹的后序和 中序 遍歷序列，可以唯一確定一棵二叉樹。 10.某二叉樹的中序遍歷序列為：DEBAC，后序遍歷序列為：EBCAD。則前序遍歷序列為 DABEC。 11.設(shè)一棵二叉樹結(jié)點(diǎn)的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG，則二叉樹中葉結(jié)點(diǎn)是： E、F、H。 12.已知完全二叉樹的第8層有8個結(jié)點(diǎn)，則其葉結(jié)點(diǎn)數(shù)是 68。 13.由樹轉(zhuǎn)換二叉樹時，其根結(jié)點(diǎn)無 右子樹。 14.采用二叉鏈表存儲的n個結(jié)點(diǎn)的二叉樹，一共有 2n 個指針域。 15.采用二叉鏈表存儲的n個結(jié)點(diǎn)的二叉樹，共有空指針 n+1 個。 16.前序?yàn)锳，B，C且后序C，B，A的二叉樹共有 4 種。 17.三個結(jié)點(diǎn)可以組成 2 種不同形態(tài)的樹。 18.將一棵完全二叉樹按層次編號，對于任意一個編號為i的結(jié)點(diǎn)，其左孩子結(jié)點(diǎn)的編號為： 2*i。 19.給定如圖7-36所示的二叉樹，其前序遍歷序列為： ABEFHCG。 20.給定如圖7-37所示的二叉樹，其層次遍歷序列為： ABCEFGH。 A A B C B C E F G 圖7-36 二叉樹1 E F G 圖7-37 二叉樹2 HD HD 三、選擇題 1.樹最適合用來表示（D）。 A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間無聯(lián)系的數(shù)據(jù) D.元素之間有分支的層次關(guān)系 2.前序?yàn)锳，B，C的二叉樹共有（D）種。 A.2 B.3 C.4 D.5 3.根據(jù)二叉樹的定義，具有3個結(jié)點(diǎn)的二叉樹有（C）種樹型。 A.3 B.4 C.5 D.6 4.在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)的點(diǎn)數(shù)為（B）。 A.16 B.31 C.32 D.33 5.具有64個結(jié)點(diǎn)的完全二叉樹的深度為（C）。 A.5 B.6 C.7 D.8 6.任何一棵二叉樹的葉結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對次序（A）。 A.不發(fā)生改變 B.發(fā)生改變 C.不能確定 D.以上都不對 7.A，B為一棵二叉樹上的兩個結(jié)點(diǎn)，在中序遍歷時，A在B前的條件是（C）。 A.A和B右方 B.A是B祖先 C.A和B左方 D.A是B子孫 8.下列4棵樹中，（B）不是完全二叉樹。 A． A B.A C.A D.A B C B C B C B C D E HD G D E F D E D 9.如圖7-38所示的二叉樹，后序遍歷的序列是（D）。 A.ABCDEFGHI A B.ABDHIECFG 圖7-38二叉樹3 C.HDIBEAFCG B C D.HIDEBFGCA D E F G H I 10.對于圖7-39所示的二叉樹，其中序序序列為（A）。 A． DBEHAFCG B.DBHEAFCG C.ABDEHCFG D.ABCDEFGH A B C D E F G 圖7-39二叉樹4 H 11.某二叉樹的后序遍歷序列為：DABEC，中序遍歷序列為：DEBAC，則前序遍歷序列為（D）。 A.ACBED B.DECAB C.DEABC D.CEDBA 12.具有n(n>1)個結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn)i(2i>n)的左孩子結(jié)點(diǎn)是（D）。 A.2i B.2i+1 C.2i-1 D.不存在 13.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（A）。 A.唯一的 B.有多種 C.有多種，但根結(jié)點(diǎn)都沒有左孩子 D.有多種，但根結(jié)點(diǎn)都沒有右孩子 14.將一棵有100個結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1，則編號為45的結(jié)點(diǎn)的左孩子編號為（B）。 A.46 B.47 C.90 D.91 15.將一棵有100個結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對結(jié)點(diǎn)編號，根結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的右孩子編號為（B）。 A.98 B.99 C.50 D.100 16.二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索，這種說法（B）。 A.正確 B.錯誤 C.不確定 D.都有可能 17.下列陳述正確的是（D）。 A.二叉樹是度為為2的有序樹 B.二叉樹中結(jié)點(diǎn)只有一個孩子時無左右之分 C.二叉樹必有度為2的結(jié)點(diǎn) D.二叉樹中最多只有兩棵子樹，且有左右子樹之分 18.用5個權(quán)值{3，2，4，5，1}構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是（B）。 A.32 B.33 C.34 D.15 19.在樹結(jié)構(gòu)中，若結(jié)點(diǎn)B有4個兄弟，A是B的父親結(jié)點(diǎn)，則A的度為（C）。 A.3 B.4 C.5 D.6 20.二叉樹的葉結(jié)點(diǎn)個數(shù)比度為2的結(jié)點(diǎn)的個數(shù)（C）。 A.無關(guān) B.相等 C.多一個 D.少一個 第8章 圖 一、判斷題 1.圖可以沒有邊，但不能沒有頂點(diǎn)。 （√）2.在無向圖中，(v1，v2)與（v2，v1）是兩條不同的邊。 （×）3.鄰接表只能用于有向圖的存儲。 （×）4.一個圖的鄰接矩陣表示是唯一的。 （√）5.用鄰接矩陣法存儲一個圖時，所占用的存儲空間大小與圖中頂點(diǎn)個數(shù)無關(guān)，而只與圖的邊數(shù)有關(guān)。（×）6.有向圖不能進(jìn)行廣度優(yōu)先遍歷。 （×）7.若一個無向圖以頂點(diǎn)v1為起點(diǎn)進(jìn)行深度優(yōu)先遍歷，所得的遍歷序列唯一，則可以唯一確定該圖。 （√）8.存儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的上三角（或下三角）部分就可以了。 （√）9.用鄰接表法存儲圖時，占用的存儲空間大小只與圖中的邊數(shù)有關(guān)，而與結(jié)點(diǎn)的個數(shù)無關(guān)。 （×）10.若從一個無向圖中任一頂占出發(fā)，進(jìn)行了一次深度優(yōu)先遍歷，就可以訪問圖中所有的頂點(diǎn)，則該圖一定是連通的。 （√）二、填空題 1.圖常用的存儲方式有鄰接矩陣和 鄰接表 等。 2.圖的遍歷有： 深度優(yōu)先搜 和廣度優(yōu)先搜等方法。 3.有n條邊的無向圖鄰接矩陣中，1的個數(shù)是 2n。 4.有向圖的邊也稱為 弧。 5.圖的鄰接矩陣表示法是表示 頂點(diǎn) 之間相鄰關(guān)系的矩陣。 6.有向圖G用鄰接矩陣存儲，其第i行的所有元素之和等于頂點(diǎn)i的 出度。 7.n個頂占e條邊的圖若采用鄰接矩陣存儲，則空間復(fù)雜度為： On2。 8.n個頂占e條邊的圖若采用鄰接表存儲，則空間復(fù)雜度為： O(n+e)。 9.設(shè)有一稀疏圖G，則G采用 鄰接表 存儲比較節(jié)省空間。 10.設(shè)有一稠密圖G，則G采用 鄰接矩陣 存儲比較節(jié)省空間。 11.圖的逆鄰接表存儲結(jié)構(gòu)只適用于 有向 圖。 12.n個頂點(diǎn)的完全無向圖有 n(n-1)/2 條邊。 13.有向圖的鄰接矩陣表表示適于求頂點(diǎn)的 出度。 14.有向圖的鄰接矩陣表示中，第i列上非0元素的個數(shù)為頂點(diǎn)vi的 入度。 15.對于具有n個頂點(diǎn)的圖，其生成樹有且僅有 n-1 條邊。 16.對有n個頂點(diǎn)，e條弧的有向圖，其鄰接表表示中，需要 n+e 個結(jié)點(diǎn)。 17.從圖中某一頂點(diǎn)出發(fā)，訪遍歷圖中其余頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次，稱這一過程為圖的 遍歷。 18.無向圖的鄰接矩陣一定是 對稱 矩陣。 19.一個連通網(wǎng)的最小生成樹是該圖所有生成樹中 權(quán) 最小的生成樹。 20.若要求一個稠密圖G的最小生成樹，最好用 Prim 算法來求解。 三、選擇題 1.在一個圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的（C）倍。 A.1/2 B.1 C.2 D.4 2.在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（B）倍。 A.1/2 B.1 C.2 D.4 3.對于一個具有n個頂點(diǎn)的有向圖的邊數(shù)最多有（B）。 A.n B.n(n-1)C.n(n-1)/2 D.2n 4.在一個具有n個頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要（C）條邊。 A.n B.n+1 C.n-1 D.n/2 5.有8個結(jié)點(diǎn)的有向完全圖有（C）條邊。 A.14 B.28 C.56 D.112 6.深度優(yōu)先遍歷類似于二叉樹的（A）。 A.先序遍歷 B.中序遍歷 C.后序遍歷 D.層次遍歷 7.廣度優(yōu)先遍歷類似于二叉樹的（D）。 A.先序遍歷 B.中序遍歷 C.后序遍歷 D.層次遍歷 8.任何一個無向連通圖的最小生成樹（A）。 A.只有一棵 B.一棵或多棵 C.一定有多棵 D.可以不存在 9.無向圖頂點(diǎn)v的度是關(guān)聯(lián)于該頂點(diǎn)B）的數(shù)目。 A.頂點(diǎn) B.邊 C.序號 D.下標(biāo) 10.有n個頂點(diǎn)的無向圖的鄰接矩陣是用（B）數(shù)組存儲。 A.一維 B.n行n列 C.任意行n列 D.n行任意列 11.對于一個具有n個頂點(diǎn)和e條邊的無向圖，采用鄰接表表示，則表頭向量大小為（C）。 A.n-1 B.n+1 C.n D.n+e 12.在圖的表示法中，表示形式唯一的是（A）。 A.鄰接矩陣表示法 B.鄰接表表示法 C.逆鄰接表表示法 D.鄰接表和逆鄰接表表示法 13.在一個具有n個頂點(diǎn)e條邊的圖中，所有頂點(diǎn)的度數(shù)之和等于（C）。 A.n B.e C.2n D.2e v1 1 a a v2 v3 2 3 b c b c e e v4 v5 4 5 d f d f 圖8-23度為3的結(jié)點(diǎn) 圖8-24（15）題 圖8-25從頂點(diǎn)a出發(fā) 圖8-26優(yōu)先遍歷 14.圖8-23中，度為3的結(jié)點(diǎn)是（B）。 A.V1 B.V2 C.V3 D.V4 15.圖8-24是（A）。 A.連通圖 B.強(qiáng)連通圖 C.生成樹 D.無環(huán)圖 16.如圖8-25所示，從頂點(diǎn)a出發(fā)，按深度優(yōu)先進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（D）。 A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b 17.如圖8-26所示，從頂點(diǎn)a出發(fā)，按廣度優(yōu)先進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（A）。 A.a,b,e,c,d,f B.a,b,e,c,f,d C.a,e,b,c,f,d D.a,e,d,f,c,b 18.最小生成樹的構(gòu)造可使用（A）算法。 A.Prim算法 B.卡爾算法 C.哈夫曼算法 D.迪杰斯特拉算法 19.下面關(guān)于圖的存儲結(jié)構(gòu)的敘述中正確的是（A）。 A.用鄰接矩陣存儲圖，占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān) B.用鄰接矩陣存儲圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無關(guān) C.用鄰接存儲圖，占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān) D.用鄰接存儲圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無關(guān) 20.連通分量是（C）的極大連通子圖。 A.樹 B.圖 C.無向圖 D.有向圖 第9章 查找 一、判斷題 1.二分查找法要求待查表的關(guān)鍵字值必須有序。 （√）2.對有序表而言采用二分查找總比采用順序查找法速度快。 （×）3.在二叉排序樹中，根結(jié)點(diǎn)的值都小于孩子的結(jié)點(diǎn)的值。 （×）4.散列存儲法的基本思想是由關(guān)鍵字的值的決定數(shù)據(jù)的存儲地址。 （√）5.哈希表是一種將關(guān)鍵字轉(zhuǎn)換為存儲地址的存儲方法。 （√）6.選擇好的哈希函數(shù)就可以避免沖突的發(fā)生。 （×）7.在有序的順序表和有序的鏈表上，均可以采用二分查找來提高查找速度。 （×）8.采用分塊查找，既有實(shí)現(xiàn)線性表所希望的查找速度，又能適應(yīng)動態(tài)變化的需要。 （√）9.哈希查找的效率主要取決于哈希表構(gòu)造時選取的哈希函數(shù)和處理沖突的方法。 （√）10.在二叉排序樹上刪除一個結(jié)點(diǎn)時，不必移動其他結(jié)點(diǎn)，只要將該結(jié)點(diǎn)的父結(jié)點(diǎn)的相應(yīng)指針域置空即可。 （×）二、填空題 1.順序查找法，表中元素可以 任意 存放。 2.在分塊查找方法中，首先查找 索引，然后再查找相應(yīng)的塊。 3.順序查找、二分查找、分塊查找都屬于 靜態(tài) 查找。 4.靜態(tài) 查找表所含元素個數(shù)在查找階段是固定不變的。 5.對于長度為n的線性表，若進(jìn)行順序查找，則時間復(fù)雜度為 O(n)。 6.對于長度為n的線性表，若采用二分查找，則時間復(fù)雜度為 O(log2n)。 7.理想情況下，在散列表中查找一個元素的時間復(fù)雜度為： O(1)。 8.在關(guān)鍵字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找關(guān)鍵字92，要比較 4 次才找到。 9.設(shè)有100個元素，用二分查找法查找時，最大的比較次數(shù)是 7 次。 10.對二叉排序樹進(jìn)行查找的方法是用待查的值與根結(jié)點(diǎn)的鍵值進(jìn)行比較，若比根結(jié)點(diǎn)值小，則繼續(xù)在 左 子樹中查找。 11.二叉排序樹是一種 動態(tài) 查找表。 12.哈希表是按 散列 存儲方式構(gòu)造的存儲結(jié)構(gòu)。 13.哈希法既是一種存儲方法，又是一種 查找 方法。 14.散列表的查找效率主要取決于散列表造表時選取的散列函數(shù)和處理 沖突 的方法。 15.設(shè)散列函數(shù)H和鍵值k1，k2，若k1≠k2 ，而H（k2）H（k2），則稱這種現(xiàn)象為 沖突。 16.處理沖突的兩類主要方法是開放定地址法和 拉鏈法（或鏈地址法）。 17.散列表（或散列） 查找法的平均查找長度與元素個數(shù)n無關(guān)。 18.在哈希函數(shù)H（key）= key%P中，P一般應(yīng)取 質(zhì)數(shù)。 19.在查找過程中有插入元素或刪除元素操作的，稱為 動態(tài) 查找。 20.各結(jié)點(diǎn)左、右子樹深度之差的絕對值至多為 1 的二叉樹稱為平衡二叉樹。 三、選擇題 1.查找表以（A）為查找結(jié)構(gòu)。 A.集合 B.圖 C.樹 D.文件 2.順序查找法適合于存儲結(jié)構(gòu)為（B）的線性表。 A.散列存儲 B.順序存儲或鏈接存儲C.壓縮存儲 D.索引存儲 3.在表長為n的鏈表中進(jìn)行線性查找，它的平均查找長度為（B）。 A.ASL=n B.ASL=(n+1)/2 C.ASL=+1 D.ASL≈log2n 4.對線性表進(jìn)行二分查找時，要求線性表必須（D）。 A.以順序方式存儲 B.以鏈接方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排序 C.以鏈接方式存儲 D.以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排序 5.衡量查找算法效率的主要標(biāo)準(zhǔn)是（B）。 A.元素個數(shù) B.平均查找長度 C.所需的存儲量 D.算法難易難度 6.如果要求一個線性表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，可以采用（A）查找方法。 A.分塊 B.順序 C.二分 D.散列 7.鏈表適用于（A）查找。 A.順序 B.二分 C.隨機(jī) D.順序或二分 8.一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值為82的結(jié)點(diǎn)時，（C）次比較后查找成功。 A.2 B.3 C.4 D.5 9.二分查找有序表{4，6，10，12，20，30，50，70，88，100}，若查找表中元素58，則它將依次與表中（B）比較大小，查找結(jié)果是失敗。 A.30，88，70，50 B.20，70，30，50 C.20，50 D.30，88，50 10.對有14個元素的有序A[1‥14]作二分查找，查找元素A[4]時的被比較元素依次為（C）A.A[1]，A[2]，A[3]，A[4] B.A[1]，A[14]，A[7]，A[4] C.A[7]，A[3]，A[5]，A[4] D.A[7]，A[5]，A[3]，A[4] 11.有一個長度為12的有序表，按二分查找法對其進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（B）。 A.35/12 B.37/12 C.39/12 D.43/12 12.采用分塊查找時，若線性表共有625個元素，查找生個元素等概率相等，假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的塊時，每塊分（C）個結(jié)點(diǎn)最佳。 A．6 B．10 C．25 D．625 13.下列（C）不是利用查找表中數(shù)據(jù)元素的關(guān)系進(jìn)行查找的方法。 A．平衡二叉樹 B．有序表的查找 C．散列查找 D．二叉排序樹的查找 14.設(shè)哈希表長m=14，哈希函數(shù)H(key)=key%11。表中已有4個結(jié)點(diǎn)：addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7其余地址為空。如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是（D）。 A．8 B．3 C．5 D．9 15.對包含n個元素的散列表進(jìn)行查找。平均查找長度為（D）。 A．O(n2)B．O(log2n)C．O(n)D．不直接依賴于n 16.沖突指的是（C）。 A．兩個元素具有相同序號 B．兩個元素的鍵值不同 C．不同鍵值對應(yīng)相同的存儲地址 D．兩個元素的鍵值相同 17.在查找過程中，不做增加、刪除或修改的查找稱為（A）。 A．靜態(tài)查找 B．內(nèi)創(chuàng)造 C．動態(tài)查找 D．處查找 18.已知8個元素為{34，76，45，18，26，54，92，65}，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，最后兩層上結(jié)點(diǎn)的總數(shù)為（B）。 A．1 B．2 C．3 D．4 19.不可能生成圖9-17所示的二叉排序樹的關(guān)鍵字的序列是（A）。 A．4 5 3 1 2 B．4 2 5 3 1 C．4 5 2 1 3 D．4 2 3 1 5 4 2 5 1 3 圖9-17二叉樹 20.動態(tài)查找包括（B）查找。 A.順序表 B.二叉排序樹 C.有序表 D.索引順序表 第10章 排序 一、判斷題 1.如果某種排序算法不穩(wěn)定，則該排序方法就沒有實(shí)用價值。 （×）2.希爾排序是不穩(wěn)定的排序。 （√）3.冒泡排序是不穩(wěn)定的排序。 （×）4.對n個記錄的進(jìn)行快速排序，所需要的平均時間是O（nlog2n）。 （√）5.堆排序所需的時間與待排序的記錄個數(shù)無關(guān)。 （×）6.當(dāng)待排序的元素個數(shù)很多時，為了交換元素的位置占用較多的時間，這是影響時間復(fù)雜度的主要因素。 （√）7.快速排序在任何情況下都比其他排序方法速度快。 （×）8.對快速排序來說，初始序列為正序或反序都是最壞情況。 （√）9.采用歸并排序可以實(shí)現(xiàn)外排序。 （√）10.采用希爾排序時，若原始關(guān)鍵字的排列雜亂無序，則效率最高。 （√）二、填空題 1.大多數(shù)排序算法都有兩個基本的操作： 比較 和移動。 2.評價排序算法優(yōu)劣的主要標(biāo)準(zhǔn)是 時間復(fù)雜度 和算法所需的附加空間。 3.根據(jù)被處理的數(shù)據(jù)在計(jì)算機(jī)中使用不同的存儲設(shè)備，排序可分為 內(nèi)排序 和外排序。 4.外排序是指在排序過程中，數(shù)據(jù)的主要部分存在計(jì)算機(jī)的 外存 中。 5.對n個關(guān)鍵字進(jìn)行冒泡排序，其可能的最小比較次數(shù)為 n-1 次。 6.在最壞情況下，在第i趟直接插入排序中，要進(jìn)行 i-1 次關(guān)鍵字的比較。 7.對n個關(guān)鍵字進(jìn)行冒泡排序，時間復(fù)雜度為 O（n2）。 8.快速排序在最壞情況下的時間復(fù)雜度是 O（n2）。 9.對于n個記錄的集合進(jìn)行歸并排序，所需要的平均時間為 O（nlog2n）。 10.對于n個記錄的集合進(jìn)行歸并排序，所需要的附加空間為 O(n)。 11.若原始數(shù)據(jù)接近無序，則選用 快速排序 最好。 12.在排序前，關(guān)鍵字值相等的不同記錄，排序后相對位置保持 不變 的排序方法，稱為穩(wěn)定排序方法。 13.在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 插入排序較好。 14.當(dāng)增量為1時，該趟希爾排序與 直接插入 排序基本一致。 15.第一趟排序后，序列中鍵值最大的記錄交換到最后的排序算法是 冒泡 排序。 16.依次將后面文件每個記錄插入到一個前面有序的子文件中的排序方法稱為直接插入 排序。 17.在插入排序、選擇排序和歸并排序中，不穩(wěn)定的排序?yàn)椋? 選擇 排序。 18.在對一組記錄（54，38，96，23，15，72，60，45，93）進(jìn)行直接插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置需比較 3 次。 19.兩個序列分別為：L1={25，57，48，37，92，86，12,33} L2 ={25，37，33，12，48，57，86，92} 用冒泡排序法對L1和 L2進(jìn)行排序，交換次數(shù)較少的是序列： L2。 20.對一組記錄（54，35，96，21，12，72，60，44，80）進(jìn)行直接選擇排序時，第4次選擇和交換后，未排序記錄是 54，72，60，96，80。 三、選擇題 1.排序是根據(jù)（A）的大小重新安排各元素的順序。 A.關(guān)鍵字 B.數(shù)組 C.元素件 D.結(jié)點(diǎn) 2.評價排序算法好壞的標(biāo)準(zhǔn)主要是（D）。 A.執(zhí)行時間 B.輔助空間 C.算法本身的復(fù)雜度 D.執(zhí)行時間和所需的輔助空間 3.直接插入排序的方法是（B）的排序方法。 A.不穩(wěn)定 B.穩(wěn)定 C.外部 D.選擇 4.直接插入排序的方法要求被排序的數(shù)據(jù)（B）存儲。 A.必須鏈表 B.必須順序 C.順序或鏈表 D.可以任意 5.排序方法中，從無序序列中選擇關(guān)鍵字最小的記錄，將其與無序區(qū)（初始為空）的第一個記錄交換的排序方法，稱為（D）。 A.希爾排序 B.歸并排序 C.插入排序 D.選擇排序 6.每次把待排序的數(shù)據(jù)劃分為左、右兩個區(qū)間，其中左區(qū)間中元素的值不大于基準(zhǔn)元素的值，右區(qū)間中元素的值不小于基準(zhǔn)元素的值，此種排序方法稱為（C）。 A.冒泡排序 B.堆排序 C.快速排序 D.歸并排序 7.快速排序在（C）情況下最易發(fā)揮其長處。 A.待排序的數(shù)據(jù)中含有多個相同的關(guān)鍵字B.待排序的數(shù)據(jù)已基本有序 C.待排序的數(shù)據(jù)完全無序 D.待排序的數(shù)據(jù)中最大值與最小值相差懸殊。 8.下述幾種排序方法中，要求內(nèi)存量最大的是（D）。 A.插入排序 B.選擇排序 C.快速排序 D.歸并排序 9.直接插入排序的方法是從第（B）個元素開始，插入前邊適當(dāng)位置的排序方法。 A.1 B.2 C.3 D.n 10.堆的形狀是一棵（C）。 A.二叉排序樹 B.滿二叉樹 C.完全二叉樹 D.平衡二叉樹 11.內(nèi)排序是指在排序的整個過程中，全部數(shù)據(jù)都在計(jì)算機(jī)的（A）中完成的排序。 A.內(nèi)存 B.外存 C.內(nèi)存和外存 D.寄存器 12.快速排序的方法是（A）的排序方法。 A.不穩(wěn)定 B.穩(wěn)定 C.外部 D.選擇 13.下列排序方法中，關(guān)鍵字比較次數(shù)與記錄的初始排列次序無關(guān)的是（A）。 A.選擇排序 B.希爾排序 C.插入排序 D.冒泡排序 14.下述幾種排序方法中，平均時間復(fù)雜度最小的是（A）。 A.希爾排序 B.插入排序 C.冒泡排序 D.選擇排序 15.對有n個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是（B）。 A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)16.冒泡排序的方法對n個數(shù)據(jù)進(jìn)行排序，第一趟排序共需要比較（C）次。 A.1 B.2 C.n-1 D.n 17.對n個不同的排序碼進(jìn)行冒泡（遞增）排序，在下列（B）情況比較的次數(shù)最多。 A.從小到大排列好的 B.從大到小排列好的C.元素?zé)o序 D.元素基本有序 18.用直接插入排序法對下面的4個序列進(jìn)行由小到大的排序，元素比較次數(shù)最少的是（B）。 A.94，32，40，90，80，46，21，69 B.21，32，46，40，80，69，90，94 C.32，40，21，46，69，94，90，80 D.90，69，80，46，21，32，94，40 19.一組記錄的排序碼為（25，48，16，35，79，82，23，40），其中含有4個長度為2的有序表，按歸并排序的方法對該序列進(jìn)行一趟歸并后的結(jié)果為（A）。 A.16 25 35 48 23 40 79 82 B.16 25 35 48 79 82 23 40 C.16 25 48 35 79 82 23 40 D.16 25 35 48 79 23 40 82 20.一個數(shù)據(jù)序列的關(guān)鍵字為（46，79，56，38，40，84），采用快速排序，并以第一個數(shù)為基準(zhǔn)得到第一次劃分的結(jié)果為（C）。 A.（38，40，46，56，79，84）B.（40，38，46，79，56，84）C.（40，38，46，56，79，84）D.（40，38，46，79，56，84）第十章文件 1．文件：性質(zhì)相同的記錄的集合。放在外存 主關(guān)鍵字項(xiàng)：能唯一標(biāo)識記錄的數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)的組合（如學(xué)號）文件的操作：檢索和維護(hù) 文件的存貯結(jié)構(gòu)：順序、索引、散列、鏈 文件的組織方式：順序文件、索引文件、散列文件、多關(guān)鍵字文件 2．順序文件：記錄進(jìn)入文件的先后順序存放其邏輯順序與物理順序一致的文件。 順序文件的更新方法： 優(yōu)點(diǎn)： 3．索引文件：在主文件之外另外建立一張表：邏輯記錄與物理記錄的對應(yīng)關(guān)系表各主文件一起構(gòu)成的文件叫索引文件。 4．索引順序文件：索引表按主關(guān)鍵字有序，主文件按關(guān)鍵字可有序 索引非順序文件索引表按主關(guān)鍵字有序，主文件按關(guān)鍵字無序 ISAM文件：專為磁盤存取設(shè)計(jì)的文件組織方式，靜態(tài)索引結(jié)構(gòu)，由多級主索引、柱面索引、磁道索引和主文件組成。 VSAM文件：虛擬存貯存取方法，用B+樹用為動態(tài)索引結(jié)構(gòu)，文件由三部分組成：索引集、順序集、數(shù)據(jù)集 5．散列文件：用散列存貯方式組織的文件，直接存取文件 桶： 6．多關(guān)鍵字文件：包含有多個次關(guān)鍵字索引的文件 多重表文件：索引方法與鏈接方法相結(jié)合的一種組織方式 倒排文件：與多重表不同的是次關(guān)鍵字索引的結(jié)構(gòu)不同 三、應(yīng)用題(本大題共5小題，每小題6分，共30分)26.已知廣義表的圖形表示如圖所示,(1)寫出該廣義表L;(2)分別寫出該廣義表的深度和長度。 L=((e),(),(a,(b,c,d)),(b,c,d))深度3 長度4 27.已知二叉樹的先序序列和中序序列分別為ABDEHCFI和DBHEACIF，(1)畫出該二叉樹的二叉鏈表存儲表示;(2)寫出該二叉樹的后序序列。DHEBIFCA A B C D E F H I 28.已知有向圖的鄰接表如圖所示,(1)寫出從頂點(diǎn)A出發(fā),對該圖進(jìn)行廣度優(yōu)先搜索遍歷的頂點(diǎn)序列：ABDCE(2)畫出該有向圖的逆鄰接表。 29.依次讀入給定的整數(shù)序列{7，16，4，8，20，9，6，18，5}，完成下列操作： 1)構(gòu)造一棵二叉排序樹,計(jì)算在等概率情況下該二叉排序樹的平均查找長度ASL;2)若變更序列中元素的排列,可構(gòu)造出平均查找長度達(dá)到最小的二叉排序樹。寫出滿足上述要求的序列中的第一個元素。 4 16 6 8 20 5 9 18 ASL=1/9*（1+2*2+3*3+3*4）=26/9 {9，7，5，4，8，18，6，16，20} 9 7 18 5 8 16 20 4 6 ASL=1/9*（1+2*2+4*3+2*4）=25/9 26.由森林轉(zhuǎn)換得到的對應(yīng)二叉樹如圖所示，寫出原森林中第三棵樹 的前序序列和后序序列。 G H I J 前序序列：GHI J 后序序列：HJIG 27.圖的鄰接表的類型定義如下所示： #define MaxVertexNum 50 typedef struct node { int adjvex;struct node *next;}EdgeNode;typedef struct { VertexType vertex;EdgeNode *firstedge;}VertexNode;typedef VertexNode AdjList[MaxVertexNum];typedef struct { AdjList adjlist;int n, e;}ALGraph;為便于刪除和插入圖的頂點(diǎn)的操作，可將鄰接表的表頭向量定義為鏈?zhǔn)浇Y(jié)構(gòu)，兩種定義的存儲表示實(shí)例如下圖所示，請寫出重新定義的類型說明。 題27圖 typedef struct link { VertexType vertex;EdgeNode *firstedge;link *down;};typedef struct node { struct node *next;struct link *next1;}EdgeNode;struct Link * ALGraph;28.某類物品的編號由一個大寫英文字母及2位數(shù)字（0..9）組成，形如E32。運(yùn)用基數(shù)排序?qū)ο铝形锲肪幪栃蛄羞M(jìn)行按字典序的排序，寫出每一趟（分配和收集）后的結(jié)果。 E13，A37，F(xiàn)43，B32，B47，E12，F(xiàn)37，B12 第一趟：B32,E12,B12,E13,F43,A37,B37,F37 第二趟：E12,B12,E13,B32,A37,F37,F43,B47 第三趟：A37,B12,B32,B47,E12,E13,F37,F43 29.（1）畫出對表長為13的有序順序表進(jìn)行二分查找的判定樹； A[6]=28 A[3]= 16 A[10]= 67 A[1]= 12 A[4]= 21 A[8]=43 A[12]=84 A[2]= 14 A[5]= 24 A[7]= 35 A[9]= 52 A[11]= 71 A[13]= 99（2）已知關(guān)鍵字序列為（12，14，16，21，24，28，35，43，52，67，71，84，99），寫出在該序列中二分查找37時所需進(jìn)行的比較次數(shù)。5 29．在棧的輸入端元素的輸入順序?yàn)?，2，3，4，5，6，進(jìn)棧過程中可以退棧，則退棧時能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，寫出進(jìn)棧、退棧過程，若不能，簡述理由。（用push（x）表示x進(jìn)棧，pop(x)表示x退棧）push（1）push（2）push（3）pop(3)pop(2)push（4）push（5）POP（5）push（6）pop(6)pop(4)pop(1)30．已知一棵二叉樹的中根遍歷序列為CBEDFAGH，后根遍歷序列為CEFDBHGA，畫出該二叉樹。 A B G C D H E F 31．給定表（15，11，8，20，14，13），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹，并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它調(diào)整為平衡二叉排序樹。 11 20 8 14 13 調(diào)整方法： 根結(jié)點(diǎn)不平衡：根左子樹高>右子樹高+1：根的中序序列8，11，13，14，15，20中根的前一點(diǎn)14上移為根 14 11 15 8 13 20 根左子樹高<右子樹高+1：根的中序序列中根的后一點(diǎn)上移為根 33．用冒泡排序法（快速排序）對數(shù)據(jù)序列（49，38，65，97，76，134，27，49）進(jìn)行排序，寫出排序過程。并說明冒泡排序是否為穩(wěn)定排序。 冒泡排序法穩(wěn)定 49，38，65，97，76，134，27，49 49，65，97，76，134，38，49，27 65，97，76，134，49，49，38，27 97，76，134，65，49，49，38，27 97，134，76，65，49，49，38，27 134，97，76，65，49，49，38，27 快速排序不穩(wěn)定 49，38，65，97，76，134，27，49 49，38，27，49，76，134，97，65，27，38，49，49，65，76，97，134 27，38，49，49，65，76，97，134 29.已知3階B-樹如圖所示，(1)畫出將關(guān)鍵字6插入之后的B-樹； (2)畫出在(1)所得樹中插入關(guān)鍵字2之后的B-樹。5 6 2 1 3 2 8 9 2 3 6 2 1 2 1 5 2 8 9 32．如題32圖所示無向圖，（1）寫出其鄰接矩陣； （2）寫出三種以頂點(diǎn)A為起點(diǎn)的深度優(yōu)先搜索頂點(diǎn)序列。 a0 1 1 0 0 0 0 1 b1 0 0 1 1 00 0 c0 0 0 0 0 1 0 0 d0 1 0 1 0 0 0 0 e0 1 0 0 0 1 0 0 f 0 0 1 0 0 0 0 0 g0 0 0 1 1 0 0 0 h10 0 0 0 0 0 0 圖6-19 稀疏矩陣A ACFBEGDH ABDGEHCF AHBEGDCF 28.假設(shè)通信電文使用的字符集為 {a，b，c，d，e，f，g，h} 各字符在電文中出現(xiàn)的頻度分別為：7，26，2，28，13，10，3，11，試為這8個字符設(shè)計(jì)哈夫曼編碼。要求： (1)畫出你所構(gòu)造的哈夫曼樹(要求樹中左孩子結(jié)點(diǎn)的權(quán)值不大于右孩子結(jié)點(diǎn)的權(quán)值)； (2)按左分支為0和右分支為1的規(guī)則，分別寫出與每個字符對應(yīng)的編碼。 46 54 21 25 26b 28d 10f 11h 12 13e 5 7a 2c 3g A:0101 b:10 c:01000 d:00 e:011 f:000 g:01001 h:001 四、算法閱讀題(本大題共4小題，每小題5分，共20分)四、算法閱讀題（本大題共4小題，每小題5分，共20分）30.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表,閱讀下列算法f30,并回答問題:(1)設(shè)線性表為(a1, a2 , a3, a4 , a 5, a6, a7), 寫出執(zhí)行算法f30后的線性表； (2)簡述算法f30的功能。 void f30(LinkList L){ //L為帶頭結(jié)點(diǎn)單鏈表的頭指針 LinkList p,q;P =L;while(p &&p–>next){q = p–>next;//q指向第一個點(diǎn) p–>next =q–>next;//p的下一個指向第二個點(diǎn),刪除了第一個點(diǎn) p =q–>next;//p指向第二個點(diǎn) free(q);//回收q } }(1)(a2 , a3, a4 , a 5, a6, a7),(2)刪除了鏈表第一個點(diǎn)(不是頭結(jié)點(diǎn))31.算法f31的功能是借助棧結(jié)構(gòu)實(shí)現(xiàn)整數(shù)從10進(jìn)制到8進(jìn)制的轉(zhuǎn)換，閱讀算法并回答問題： (1)畫出n為十進(jìn)制的1348時算法執(zhí)行過程中棧的動態(tài)變化情況;(2)說明算法中while循環(huán)完成的操作。 void f31(int n)//n為非負(fù)的十進(jìn)制整數(shù) { int e;SeqStack S;InitStack(& S);do{ Push(& S,n%8);n =n/8;}while(n);while(!StackEmpty(& S)){e =Pop(& S);printf(〞%ld〞,e);} }(1)4，0，5 2(2)當(dāng)棧不空時出棧輸出n化為8進(jìn)制數(shù)的序列2504 32.已知以二叉鏈表作二叉樹的存儲結(jié)構(gòu)，閱讀算法f32，并回答問題： (1)設(shè)二叉樹T如圖所示,寫出執(zhí)行f32(T)的返回值;(2)簡述算法f32的功能。 int f32(BinTree T){ int m, n;if(!T)return 0;else { m= f32(T–>lchild);n = f 32(T–>rchild);if(m>n)return m +1;else return n+1;} }(1)(2)33.設(shè)有向圖鄰接表定義如下； typedef struct{ VertexNode adjlist[Max VertexNum];int n,e;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) } ALGraph;//鄰接表類型 vertex firstedge 其中頂點(diǎn)表結(jié)點(diǎn)VertexNode結(jié)構(gòu)為： adjvex next 邊表結(jié)點(diǎn)EdegNode結(jié)構(gòu)為： 閱讀下列算法f33，并回答問題： (1)已知有向圖G的鄰接表如圖所示, 寫出算法f33的輸出結(jié)果;(2)簡述算法f33的功能。 void dfs(ALGraph *G,int v){ EdgeNode * p;visited[v]=TRUE;printf(〞%c〞,G–>adjlist[v]·vertex);for(p =G–>adjlist[v])·firstedge;p;p=p–>next)if(!visited[p–>adjvex])dfs(G, p–>adjvex);} void f33(ALGraph *G){ int v,w;for(v=0;v typedef int DataType;typedef struct node { DataType data;struct node * next;} LinkNode, * LinkList;閱讀下列算法，并回答問題： (1)已知初始鏈表如圖所示，畫出執(zhí)行f30(head)之后的鏈表； 題30圖(2)簡述算法f30的功能。 void f30(LinkList head){ LinkList p,r, s;if(head-> next){ r = head-> next;p = r->next;r-> next = NULL;while(p){ s =p;p = p->next;if(s-> data% 2 = = 0){ s-> next = head-> next;head-> next = s;} else { s-> next = r-> next;r->next = s;r =s;} } } }(1)2 8 5 7(2)將原鏈中偶數(shù)置前，奇數(shù)置后 31.假設(shè)以二叉鏈表表示二叉樹，其類型定義如下： typedef struct node { DataType data;struct node * lchild, * rchild;//左右孩子指針 } * BinTree;閱讀下列算法，并回答問題： (1)已知以T為根指針的二叉樹如圖所示，寫出執(zhí)行f31(T)之后的返回值； (2)簡述算法f31的功能。 int f31(BinTree T){ int d;if(!T)return 0;d = f31(T-> lchild)+ f31(T-> rchild);if(T-> lchild && T-> rchild)return d + 1;else return d;(1)(2)32.設(shè)有向圖鄰接表定義如下： typedef struct { VertexNode adjlist[ MaxVertexNum ];int n，e； ／／圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) }ALGraph； ／／鄰接表類型 其中頂點(diǎn)表結(jié)點(diǎn)VertexNode 邊表結(jié)點(diǎn)EdgeNode結(jié)構(gòu)為： 閱讀下列算法，并回答問題： (1)已知某有向圖存儲在如圖所示的鄰接 表G中，寫出執(zhí)行f32(＆G)的輸出； (2)簡述算法f32的功能。 int visited[ MaxNum ];void DFS(ALGraph * G, int i){ EdgeNode * p;visited [ i ] = TRUE;if(G-> adjlist[ i].firstedge = = NULL)printf(“% c “, G-> adjlist[ i].vertex)； else { p = G-> adjlist[ i].firstedge;while(p!= NULL){ if(!visited[p-> adjvex])DFS(G, p-> adjvex);p = p->next;} } } void f32(ALGraph * G){ int i;for(i = 0;i < G->n;i ++)visited [ i ] = FALSE;for(i = 0;i < G->n;i++)if(!visited[i])DFS(G, i);}(1)(2)33.下列算法f33的功能是對記錄序列進(jìn)行雙向冒泡排序。算法的基本思想為，先從前往后通過交換將關(guān)鍵字最大的記錄移動至后端，然后從后往前通過交換將關(guān)鍵字最小的記錄移動至前端，如此反復(fù)進(jìn)行，直至整個序列按關(guān)鍵字遞增有序?yàn)橹?。請?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為完整的算法。 #define MAXLEN 100 typedef int KeyType;typedef struct { KeyType key;InfoType otherinfo;} NodeType;typedef NodeType SqList[ MAXLEN ];void f33(SqList R, int n){ int i,j,k;NodeType t;i =0;j =n-l;while(i < j){ for(k=i;k 數(shù)據(jù)結(jié)構(gòu)試卷 （二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯誤的是（）。 (A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間 (B)線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C)線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn) 2．設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。 (A)2m-1(B)2m(C)2m+1(D)4m 3．設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個數(shù)為（）。 (A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。 (A)BADC(B)BCDA(C)CDAB(D)CBDA 5．設(shè)某完全無向圖中有n個頂點(diǎn)，則該完全無向圖中有（）條邊。 (A)n(n-1)/2(B)n(n-1)(C)n 2(D)n2-1 6．設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為（）。 (A)9(B)10(C)11(D)12 7．設(shè)某有向圖中有n個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（）個表頭結(jié)點(diǎn)。 (A)n-1(B)n(C)n+1(D)2n-1 8．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。 (A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8 二、填空題(24分)1.1.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是____________________和__________________________。 2.2.下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。 typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”); else {____________________;_________________;} } 3.3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.4.快速排序的最壞時間復(fù)雜度為___________，平均時間復(fù)雜度為__________。5.5.設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_______個空指針域。 6.6.設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=_______。 7.7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。 v1??3??2??4v2??1??3v3??1??4??28.8.設(shè)某無向圖G的鄰接表為v4??1??3，則從頂點(diǎn)V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。 三、應(yīng)用題(36分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。 2． 2． 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink和rlink）。 3． 3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時的比較次數(shù)并計(jì)算出查找成功時的平均查找長度。 4． 4． 設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5． 5． 設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。 6． 6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。 數(shù)據(jù)結(jié)構(gòu)試卷 （二）參考答案 一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二、填空題 1.1.構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序 4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4) 三、應(yīng)用題 1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略 5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略 數(shù)據(jù)結(jié)構(gòu)試卷 （三）一、選擇題(30分)1．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。 (A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu) 2．下面程序的時間復(fù)雜為（） for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（）。 (A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； (C)q=p->next；p->next=q->next；free(q)； (D)q=p->next；p->data=q->data；free(q)； 4．設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（）個輔助記錄單元。 (A)1(B)n(C)nlog2n(D)n2 5．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21 6．設(shè)二叉排序樹中有n個結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設(shè)無向圖G中有n個頂點(diǎn)e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為（）。 (A)n，e(B)e，n(C)2n，e(D)n，2e 8.設(shè)某強(qiáng)連通圖中有n個頂點(diǎn)，則該強(qiáng)連通圖中至少有（）條邊。 (A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。 (A)快速排序(B)堆排序(C)歸并排序(D)插入排序 10.下列四種排序中（）的空間復(fù)雜度最大。 (A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序 二、填空殖(48分，其中最后兩小題各6分)1.1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。 2.2.設(shè)一棵完全二叉樹中有500個結(jié)點(diǎn)，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有___________個空指針域。 3.3.設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。 4.4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的________，第i列上所有元素之和等于頂點(diǎn)i的________。 5.5.設(shè)哈夫曼樹中共有n個結(jié)點(diǎn)，則該哈夫曼樹中有________個度數(shù)為1的結(jié)點(diǎn)。6.6.設(shè)有向圖G中有n個頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為_________。 7.7.__________遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。 8.8.設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。 9.9.不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為____________。 10.10.設(shè)有n個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為____________，右孩子結(jié)點(diǎn)的編號為___________。11.11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為___________________________。 12.12.設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓?fù)湫蛄袨開___________________。 13.13.下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請?jiān)谙聞澗€處填上正確的語句。 struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);} if(_______________________)return(j);else return(-1);} 14.14.下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請?jiān)谙聞澗€處填上正確的語句。 typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){ if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;} 數(shù)據(jù)結(jié)構(gòu)試卷 （三）參考答案 一、選擇題 1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，然后將結(jié)點(diǎn)B的值復(fù)制到結(jié)點(diǎn)A中，最后刪除結(jié)點(diǎn)B。 第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時間復(fù)雜度為O(log2n)。 二、填空題 1.1.順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu) 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。 } 數(shù)據(jù)結(jié)構(gòu)試卷 （四）一、選擇題(30分)1．設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（）個結(jié)點(diǎn)。 (A)2k-1(B)2k(C)2k-1(D)2k-1 3．設(shè)某無向圖中有n個頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為（）。 (A)n(B)e(C)2n(D)2e 4．在二叉排序樹中插入一個結(jié)點(diǎn)的時間復(fù)雜度為（）。 (A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設(shè)某有向圖的鄰接表中有n個表頭結(jié)點(diǎn)和m個表結(jié)點(diǎn)，則該圖中有（）條有向邊。 (A)n(B)n-1(C)m(D)m-1 6．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 (A)3(B)4(C)5(D)8 7．設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。 (A)必須判別棧是否為滿(B)必須判別棧是否為空 (C)判別棧元素的類型(D)對棧不作任何判別 8．下列四種排序中（）的空間復(fù)雜度最大。 (A)快速排序(B)冒泡排序(C)希爾排序(D)堆 9．設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（）。 (A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。 (A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1) 二、填空題(42分)1． 1． 設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為________，快速排序的平均時間復(fù)雜度為_________。 2． 2． 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為_________________________________________________________（設(shè)結(jié)點(diǎn)中的兩個指針域分別為llink和rlink）。3． 3． 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4． 4． 深度為k的完全二叉樹中最少有____________個結(jié)點(diǎn)。5． 5． 設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進(jìn)行篩選。 6． 6． 設(shè)哈夫曼樹中共有99個結(jié)點(diǎn)，則該樹中有_________個葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_____個空指針域。 7． 7． 設(shè)有一個順序循環(huán)隊(duì)列中有M個存儲單元，則該循環(huán)隊(duì)列中最多能夠存儲________個隊(duì)列元素；當(dāng)前實(shí)際存儲________________個隊(duì)列元素（設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個位置，尾指針指向當(dāng)前隊(duì)尾元素的位置）。 8． 8． 設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_______個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_______個元素。9． 9． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為______________________________。 10．10．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為________________________。 11．11．設(shè)某無向圖G中有n個頂點(diǎn)，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是______________________。 12．12．設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_________第i列上非0元素的個數(shù)（填等于，大于或小于）。 13．13．設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。 14．14．設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時返回指向關(guān)鍵字的指針，不成功時返回標(biāo)志0。 typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;i 數(shù)據(jù)結(jié)構(gòu)試卷 （四）參考答案 一、選擇題 1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A 二、填空題 1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s 數(shù)據(jù)結(jié)構(gòu)試卷 （五）一、選擇題(30分) 1．?dāng)?shù)據(jù)的最小單位是（）。 (A)數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量 2．設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（）。 (A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（）。 (A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（）。 (A)“STRUCTURE”(B)“DATA” (C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．設(shè)一個有序的單鏈表中有n個結(jié)點(diǎn)，現(xiàn)要求插入一個新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（）。 (A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（）。 (A)Nl+N2+……+Nm (B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm 7．設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。 (A)25(B)10(C)7(D)1 8．設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。 (A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設(shè)輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。 (A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（）。 (A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80 二、填空題(共30分)1.1.設(shè)有一個順序共享?xiàng)[0：n-1]，其中第一個棧項(xiàng)指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享?xiàng)M的條件是____________________。 2.2.在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是____________________。 3.3.設(shè)有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_______個數(shù)據(jù)元素。 4.4.棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為__________表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為_________表。 5.5.設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。 6.6.設(shè)一棵完全二叉樹有128個結(jié)點(diǎn)，則該完全二叉樹的深度為________，有__________個葉子結(jié)點(diǎn)。 7.7.設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點(diǎn)i的________，第i列中所有非零元素個數(shù)之和等于頂點(diǎn)i的__________。 8.8.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。 9.9.下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請?jiān)谙聞澗€處填上正確的語句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++) if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是實(shí)現(xiàn)二分查找算法，請?jiān)谙聞澗€處填上正確的語句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){ int low=0,mid,high=n-1; while(low<=high){ ________________________________; if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1; } return(0);} 三、應(yīng)用題(24分) 1.1.設(shè)某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2.2.設(shè)無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。 3.3.設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時的平均查找長度。 4.4.設(shè)散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計(jì)算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。 數(shù)據(jù)結(jié)構(gòu)試卷 （五）參考答案 一、選擇題 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C 二、填空題 1.1.top1+1=top2 2.2.可以隨機(jī)訪問到任一個頂點(diǎn)的簡單鏈表 3.3.i(i+1)/2+j-1 4.4.FILO，F(xiàn)IFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度 8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k 三、應(yīng)用題 1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3 數(shù)據(jù)結(jié)構(gòu)試卷 （六）一、選擇題(30分)1． 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（）。 (A)20(B)30(C)40(D)45 2．執(zhí)行一趟快速排序能夠得到的序列是（）。 (A)[41，12，34，45，27] 55 [72，63](B)[45，34，12，41] 55 [72，63，27](C)[63，12，34，45，27] 55 [41，72](D)[12，27，45，41] 55 [34，63，72] 3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。 (A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序 5．設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。 (A)空或只有一個結(jié)點(diǎn)(B)高度等于其結(jié)點(diǎn)數(shù) (C)任一結(jié)點(diǎn)無左孩子(D)任一結(jié)點(diǎn)無右孩子 6．一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是（）。 (A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序 7．設(shè)某棵三叉樹中有40個結(jié)點(diǎn)，則該三叉樹的最小高度為（）。 (A)3(B)4(C)5(D)6 8．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（）。 21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結(jié)點(diǎn)。 (A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（）。 (A)front->next=s；front=s；(B)s->next=rear；rear=s； (C)rear->next=s；rear=s；(D)s->next=front；front=s； 12.設(shè)某無向圖中有n個頂點(diǎn)e條邊，則建立該圖鄰接表的時間復(fù)雜度為（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.設(shè)某哈夫曼樹中有199個結(jié)點(diǎn)，則該哈夫曼樹中有（）個葉子結(jié)點(diǎn)。 (A)99(B)100(C)101(D)102 14.設(shè)二叉排序樹上有n個結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（）。 (A)第i行非0元素的個數(shù)之和(B)第i列非0元素的個數(shù)之和 (C)第i行0元素的個數(shù)之和(D)第i列0元素的個數(shù)之和 二、判斷題(20分)1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。（） 2．分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（）3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（） 5．設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個有序的序列。（） 7．設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。（） 9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（） 三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復(fù)雜度為_________。 2．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的新結(jié)點(diǎn)X，則進(jìn)行插入操作的語句序列為__________________________（設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext）。3．設(shè)有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓?fù)渑判蛐蛄衉_________。4．設(shè)無向圖G中有n個頂點(diǎn)，則該無向圖中每個頂點(diǎn)的度數(shù)最多是_________。5．設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有_______個結(jié)點(diǎn)數(shù)。 6．設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為_____________________。 7．設(shè)二叉樹中結(jié)點(diǎn)的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_____________________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為___________。 9．快速排序算法的空間復(fù)雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。 數(shù)據(jù)結(jié)構(gòu)試卷 （六）參考答案 一、選擇題 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B 二、判斷題 1．錯 2．對 3．對 4．對 5．錯 6．錯 7．對 8．錯 9．對 10．對 三、填空題 1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.開放定址法，鏈地址法 數(shù)據(jù)結(jié)構(gòu)試卷 （七）一、選擇題(30分)1．設(shè)某無向圖有n個頂點(diǎn)，則該無向圖的鄰接表中有（）個表頭結(jié)點(diǎn)。 (A)2n(B)n(C)n/2(D)n(n-1)2．設(shè)無向圖G中有n個頂點(diǎn)，則該無向圖的最小生成樹上有（）條邊。 (A)n(B)n-1(C)2n(D)2n-1 3．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。 (A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序樹可以得到一個從小到大的有序序列。 (A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷 5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為（）。 (A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的時間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。 (A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有（）。 (A)20(B)256(C)512(D)1024 9．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（）。 (A)1(B)2(C)3(D)4 10.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（）。 (A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next; 三、填空題(30分)1.1.設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設(shè)結(jié)點(diǎn)中的兩個指針域分別為left和right）。2.2.設(shè)完全有向圖中有n個頂點(diǎn)，則該完全有向圖中共有________條有向條；設(shè)完全無向圖中有n個頂點(diǎn)，則該完全無向圖中共有________條無向邊。 3.3.設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進(jìn)行篩選。 4.4.解決散列表沖突的兩種方法是________________和__________________。 5.5.設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點(diǎn)，21個度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有______個。 6.6.高度為h的完全二叉樹中最少有________個結(jié)點(diǎn)，最多有________個結(jié)點(diǎn)。7.7.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。 8.8.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是__________________________________。 9.9.設(shè)一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。 10.10.下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請?jiān)谙聞澗€處填上正確的語句。 struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){ int j=t;struct record x=r[s];i=s; while(i while(i while(____________________)i=i+1;if(i } _________________;} 數(shù)據(jù)結(jié)構(gòu)試卷 （七）一、選擇題 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B 三、填空題 1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.開放定址法，鏈地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i 5．B 10．D 數(shù)據(jù)結(jié)構(gòu)試卷 （八）一、選擇題(30分)1.1.字符串的長度是指（）。 (A)串中不同字符的個數(shù)(B)串中不同字母的個數(shù) (C)串中所含字符的個數(shù)(D)串中不同數(shù)字的個數(shù) 2.2.建立一個長度為n的有序單鏈表的時間復(fù)雜度為（） (A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個字符串相等的充要條件是（）。 (A)兩個字符串的長度相等(B)兩個字符串中對應(yīng)位置上的字符相等 (C)同時具備(A)和(B)兩個條件(D)以上答案都不對 4.4.設(shè)某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（）。 (A)99(B)97(C)91(D)93 5.5.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.設(shè)一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序?yàn)?)。 (A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.7.設(shè)一棵完全二叉樹中有65個結(jié)點(diǎn)，則該完全二叉樹的深度為（）。 (A)8(B)7(C)6(D)5 8.8.設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點(diǎn)，2個度數(shù)為2的結(jié)點(diǎn)，2個度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（）個度數(shù)為0的結(jié)點(diǎn)。 (A)5(B)6(C)7(D)8 9.9.設(shè)無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（）。 (A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.隊(duì)列是一種（）的線性表。 (A)先進(jìn)先出(B)先進(jìn)后出(C)只能插入(D)只能刪除 三、填空題(30分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_____________________________。 2． 2． 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹中插入一個新結(jié)點(diǎn)，請?jiān)谙聞澗€處填上正確的內(nèi)容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語句序列：s->next=p->next;_________________。4． 4． 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點(diǎn)中的兩個指針域分別為llink和rlink）。 5． 5． 設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。 6． 6． 完全二叉樹中第5層上最少有__________個結(jié)點(diǎn)，最多有_________個結(jié)點(diǎn)。7． 7． 設(shè)有向圖中不存在有向邊 8． 8． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_____________________________。 9． 9． 設(shè)連通圖G中有n個頂點(diǎn)e條邊，則對應(yīng)的最小生成樹上有___________條邊。10． 10． 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。 數(shù)據(jù)結(jié)構(gòu)試卷 （八）參考答案 一、選擇題 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A 三、填空題 1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50 圖 1.填空題 ⑴ 設(shè)無向圖G中頂點(diǎn)數(shù)為n，則圖G至少有（）條邊，至多有（）條邊；若G為有向圖，則至少有（）條邊，至多有（）條邊?！窘獯稹?，n(n-1)/2，0，n(n-1)【分析】圖的頂點(diǎn)集合是有窮非空的，而邊集可以是空集；邊數(shù)達(dá)到最多的圖稱為完全圖，在完全圖中，任意兩個頂點(diǎn)之間都存在邊。 ⑵ 任何連通圖的連通分量只有一個，即是（）?！窘獯稹科渥陨?/p> ⑶ 圖的存儲結(jié)構(gòu)主要有兩種，分別是（）和（）?！窘獯稹苦徑泳仃嚕徑颖?/p> 【分析】這是最常用的兩種存儲結(jié)構(gòu)，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組等。⑷ 已知無向圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e，其鄰接表表示的空間復(fù)雜度為（）?！窘獯稹浚?n+e)【分析】在無向圖的鄰接表中，頂點(diǎn)表有n個結(jié)點(diǎn)，邊表有2e個結(jié)點(diǎn)，共有n+2e個結(jié)點(diǎn)，其空間復(fù)雜度為Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一個有向圖的鄰接矩陣表示，計(jì)算第j個頂點(diǎn)的入度的方法是（）?！窘獯稹壳蟮趈列的所有元素之和 ⑹ 有向圖G用鄰接矩陣A[n][n]存儲，其第i行的所有元素之和等于頂點(diǎn)i的（）。【解答】出度 ⑺ 圖的深度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）；圖的廣度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是（）?！窘獯稹壳靶?，棧，層序，隊(duì)列 ⑻ 對于含有n個頂點(diǎn)e條邊的連通圖，利用Prim算法求最小生成樹的時間復(fù)雜度為（），利用Kruskal算法求最小生成樹的時間復(fù)雜度為（）?！窘獯稹浚?n2)，Ｏ(elog2e)【分析】Prim算法采用鄰接矩陣做存儲結(jié)構(gòu)，適合于求稠密圖的最小生成樹；Kruskal算法采用邊集數(shù)組做存儲結(jié)構(gòu)，適合于求稀疏圖的最小生成樹。 ⑼ 如果一個有向圖不存在（），則該圖的全部頂點(diǎn)可以排列成一個拓?fù)湫蛄?。【解答】回?/p> ⑽ 在一個有向圖中，若存在弧、、，則在其拓?fù)湫蛄兄?，頂點(diǎn)vi, vj, vk的相對次序?yàn)椋ǎ！窘獯稹縱i, vj, vk 【分析】對由頂點(diǎn)vi, vj, vk組成的圖進(jìn)行拓?fù)渑判颉?/p> 2.選擇題 ⑴ 在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。A 1/2 B 1 C 2 D 4 【解答】C 【分析】設(shè)無向圖中含有n個頂點(diǎn)e條邊，則。 ⑵ n個頂點(diǎn)的強(qiáng)連通圖至少有（）條邊，其形狀是（）。A n B n+1 C n-1 D n×(n-1)E 無回路 F 有回路 G 環(huán)狀 H 樹狀 【解答】A，G ⑶ 含n 個頂點(diǎn)的連通圖中的任意一條簡單路徑，其長度不可能超過（）。A 1 B n/2 C n-1 D n 【解答】C 【分析】若超過n-1，則路徑中必存在重復(fù)的頂點(diǎn)。 ⑷ 對于一個具有n個頂點(diǎn)的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是（）。A n B(n-1)2 C n-1 D n2 【解答】D ⑸ 圖的生成樹（），n個頂點(diǎn)的生成樹有（）條邊。A 唯一 B 不唯一 C 唯一性不能確定 D n E n +1 F n-1 【解答】C，F(xiàn) ⑹ 設(shè)無向圖G=(V, E)和G' =(V', E')，如果G' 是G的生成樹，則下面的說法中錯誤的是（A G' 為 G的子圖 B G' 為 G的連通分量 C G' 為G的極小連通子圖且V = V' D G' 是G的一個無環(huán)子圖 【解答】B）。 【分析】連通分量是無向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點(diǎn)的所有邊都加上，所以，連通分量中可能存在回路。 ⑺ G是一個非連通無向圖，共有28條邊，則該圖至少有（）個頂點(diǎn)。A 6 B 7 C 8 D 9 【解答】D 【分析】n個頂點(diǎn)的無向圖中，邊數(shù)e≤n(n-1)/2，將e=28代入，有n≥8，現(xiàn)已知無向圖非連通，則n=9。 ⑻ 最小生成樹指的是（）。A 由連通網(wǎng)所得到的邊數(shù)最少的生成樹 B 由連通網(wǎng)所得到的頂點(diǎn)數(shù)相對較少的生成樹 C 連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹 D 連通網(wǎng)的極小連通子圖 【解答】C ⑼ 判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以用（）。A 求關(guān)鍵路徑的方法 B 求最短路徑的方法 C 廣度優(yōu)先遍歷算法 D 深度優(yōu)先遍歷算法 【解答】D 【分析】當(dāng)有向圖中無回路時，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時，出棧的順序（退出DFSTraverse算法）即為逆向的拓?fù)湫蛄小?/p> ⑽ 下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是（）?br /> A 關(guān)鍵活動不按期完成就會影響整個工程的完成時間 B 任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成 C 所有的關(guān)鍵活動都提前完成，那么整個工程將會提前完成 D 某些關(guān)鍵活動若提前完成，那么整個工程將會提前完 【解答】B 【分析】AOE網(wǎng)中的關(guān)鍵路徑可能不止一條，如果某一個關(guān)鍵活動提前完成，還不能提前整個工程，而必須同時提高在幾條關(guān)鍵路徑上的關(guān)鍵活動。 3.判斷題 ⑴ 一個有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)個數(shù)一定相等。 【解答】對。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結(jié)點(diǎn)個數(shù)都等于有向圖中邊的個數(shù)。 ⑵ 用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點(diǎn)個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。【解答】對。鄰接矩陣的空間復(fù)雜度為Ｏ(n2)，與邊的個數(shù)無關(guān)。 ⑶ 圖G的生成樹是該圖的一個極小連通子圖 【解答】錯。必須包含全部頂點(diǎn)。 ⑷ 無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的 【解答】錯。有向圖的鄰接矩陣不一定對稱，例如有向完全圖的鄰接矩陣就是對稱的。 ⑸ 對任意一個圖，從某頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問圖的所有頂點(diǎn)。【解答】錯。只有連通圖從某頂點(diǎn)出發(fā)進(jìn)行一次遍歷，可訪問圖的所有頂點(diǎn)。 ⑹ 在一個有向圖的拓?fù)湫蛄兄校繇旤c(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧。【解答】錯。只能說明從頂點(diǎn)a到頂點(diǎn)b有一條路徑。 ⑺ 若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓?fù)湫蛄斜囟ù嬖??！窘獯稹繉?。參見?1題的證明。 ⑻ 在AOE網(wǎng)中一定只有一條關(guān)鍵路徑?br />【解答】錯。AOE網(wǎng)中可能有不止一條關(guān)鍵路徑，他們的路徑長度相同 4．n個頂點(diǎn)的無向圖，采用鄰接表存儲，回答下列問題?br />⑴ 圖中有多少條邊？ ⑵ 任意兩個頂點(diǎn)i和j是否有邊相連？ ⑶ 任意一個頂點(diǎn)的度是多少?br /> 【解答】 ⑴ 邊表中的結(jié)點(diǎn)個數(shù)之和除以2。⑵ 第i個邊表中是否含有結(jié)點(diǎn)j。⑶ 該頂點(diǎn)所對應(yīng)的邊表中所含結(jié)點(diǎn)個數(shù)。 5．n個頂點(diǎn)的無向圖，采用鄰接矩陣存儲，回答下列問題： ⑴ 圖中有多少條邊？ ⑵ 任意兩個頂點(diǎn)i和j是否有邊相連？ ⑶ 任意一個頂點(diǎn)的度是多少？ 【解答】 ⑴ 鄰接矩陣中非零元素個數(shù)的總和除以2。 ⑵ 當(dāng)鄰接矩陣A中A[i][j]=1（或A[j][i]=1）時，表示兩頂點(diǎn)之間有邊相連。⑶ 計(jì)算鄰接矩陣上該頂點(diǎn)對應(yīng)的行上非零元素的個數(shù)。 6．證明：生成樹中最長路徑的起點(diǎn)和終點(diǎn)的度均為１。【解答】用反證法證明。 設(shè)v1, v2, …, vk是生成樹的一條最長路徑，其中，v1為起點(diǎn)，vk為終點(diǎn)。若vk的度為2，取vk的另一個鄰接點(diǎn)v，由于生成樹中無回路，所以，v在最長路徑上，顯然 v1, v2, …, vk , v的路徑最長，與假設(shè)矛盾。所以生成樹中最長路徑的終點(diǎn)的度為1。同理可證起點(diǎn)v1的度不能大于1，只能為1。 7．已知一個連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰接表存儲示意圖，若從頂點(diǎn)v1出發(fā)對該圖進(jìn)行遍歷，分別給出一個按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列。 【解答】鄰接矩陣表示如下： 深度優(yōu)先遍歷序列為：v1 v2 v3 v5 v4 v6 廣度優(yōu)先遍歷序列為：v1 v2 v4 v6 v3 v5 鄰接表表示如下： 8．圖6-7所示是一個無向帶權(quán)圖，請分別按Prim算法和Kruskal算法求最小生成樹。 【解答】按Prim算法求最小生成樹的過程如下： 按Kruskal算法求最小生成樹的過程如下： 9．對于圖6-8所示的帶權(quán)有向圖，求從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑。 【解答】從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑如下表所示。 源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長度 v1 v7 v1 v7 7 v1 v5 v1 v5 11 v1 v4 v1 v7 v4 13 v1 v6 v1 v7 v4 v6 16 v1 v2 v1 v7 v2 22 v1 v3 v1 v7 v4 v6 v3 25 10．如圖6-9所示的有向網(wǎng)圖，利用Dijkstra算法求從頂點(diǎn)v1到其他各頂點(diǎn)的最短路徑。 【解答】從源點(diǎn)v1到其他各頂點(diǎn)的最短路徑如下表所示。 源點(diǎn) 終點(diǎn) 最短路徑 最短路徑長度 v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45 11．證明：只要適當(dāng)?shù)嘏帕许旤c(diǎn)的次序，就能使有向無環(huán)圖的鄰接矩陣中主對角線以下的元素全部為0?！窘獯稹咳我鈔個結(jié)點(diǎn)的有向無環(huán)圖都可以得到一個拓?fù)湫蛄小ＴO(shè)拓?fù)湫蛄袨関0v1v2…vn-1，我們來證明此時的鄰接矩陣A為上三角矩陣。證明采用反證法。 假設(shè)此時的鄰接矩陣不是上三角矩陣，那么，存在下標(biāo)i和j（i>j），使得A[i][j]不等于零，即圖中存在從 vi到vj的一條有向邊。由拓?fù)湫?列的定義可知，在任意拓?fù)湫蛄兄?，vi的位置一定在vj之前，而在上述拓?fù)湫蛄衯0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，導(dǎo) 致矛盾。因此命題正確。 12.算法設(shè)計(jì) ⑴ 設(shè)計(jì)算法，將一個無向圖的鄰接矩陣轉(zhuǎn)換為鄰接表。 【解答】先設(shè)置一個空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對應(yīng)單鏈表中插入相應(yīng)的邊表結(jié)點(diǎn)。 鄰接矩陣存儲結(jié)構(gòu)定義如下： const int MaxSize=10;template struct AdjMatrix { T vertex[MaxSize];//存放圖中頂點(diǎn)的數(shù)組 int arc[MaxSize][MaxSize];//存放圖中邊的數(shù)組 int vertexNum, arcNum;//圖的頂點(diǎn)數(shù)和邊數(shù) };鄰接表存儲結(jié)構(gòu)定義如下： const int MaxSize=10;struct ArcNode //定義邊表結(jié)點(diǎn) { int adjvex;//鄰接點(diǎn)域 ArcNode *next;};template struct VertexNode //定義頂點(diǎn)表結(jié)點(diǎn) { T vertex;ArcNode *firstedge;};struct AdjList { VertexNode adjlist[MaxSize];int vertexNum, arcNum;//圖的頂點(diǎn)數(shù)和邊數(shù) };具體算法如下： ⑵ 設(shè)計(jì)算法，將一個無向圖的鄰接表轉(zhuǎn)換成鄰接矩陣。 【解答】在鄰接表上順序地取每個邊表中的結(jié)點(diǎn)，將鄰接矩陣中對應(yīng)單元的值置為1。鄰接矩陣和鄰接表的存儲結(jié)構(gòu)定義與上題相同。具體算法如下： ⑶ 設(shè)計(jì)算法，計(jì)算圖中出度為零的頂點(diǎn)個數(shù)。 【解答】在有向圖的鄰接矩陣中，一行對應(yīng)一個頂點(diǎn)，每行的非零元素的個數(shù)等于對應(yīng)頂點(diǎn)的出度。因此，當(dāng)某行非零元素的個數(shù)為零時，則對應(yīng)頂點(diǎn)的出度為零。據(jù)此，從第一行開始，查找每行的非零元素個數(shù)是否為零，若是則計(jì)數(shù)器加1。具體算法如下： ⑷ 以鄰接表作存儲結(jié)構(gòu)，設(shè)計(jì)按深度優(yōu)先遍歷圖的非遞歸算法?！窘獯稹繀⒁?.2.1。 ⑸ 已知一個有向圖的鄰接表，編寫算法建立其逆鄰接表。 【解答】在有向圖中，若鄰接表中頂點(diǎn)vi有鄰接點(diǎn)vj，在逆鄰接表中vj一定有鄰接點(diǎn)vi，由此得到本題算法思路：首先將逆鄰接表的表頭結(jié)點(diǎn)firstedge域置空，然后逐行將表頭結(jié)點(diǎn)的鄰接點(diǎn)進(jìn)行轉(zhuǎn)化。 ⑹ 分別基于深度優(yōu)先搜索和廣度優(yōu)先搜索編寫算法，判斷以鄰接表存儲的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑（i≠j）。 【解答】⑴ 基于深度優(yōu)先遍歷： ⑵ 基于廣度優(yōu)先遍歷： 學(xué)習(xí)自測及答案 1．某無向圖的鄰接矩陣A=，可以看出，該圖共有（A 3 B 6 C 9 D 以上答案均不正確 【解答】A 2．無向圖的鄰接矩陣是一個（），有向圖的鄰接矩陣是一個（）A 上三角矩陣 B 下三角矩陣 C 對稱矩陣 D 無規(guī)律 【解答】C，D 3．下列命題正確的是（）。 A 一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一）個頂點(diǎn)。 B 一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一 C 一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一 D 一個圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一 【解答】B 4．十字鏈表適合存儲（），鄰接多重表適合存儲（）?！窘獯稹坑邢驁D，無向圖 5.在一個具有n 個頂點(diǎn)的有向完全圖中包含有（）條邊： A n(n-1)/2 B n(n-1)C n(n+1)/2 D n2 【解答】B 6．n個頂點(diǎn)的連通圖用鄰接矩陣表示時，該矩陣至少有（）個非零元素?！窘獯稹?(n-1)7．表示一個有100個頂點(diǎn)，1000條邊的有向圖的鄰接矩陣有（）個非零矩陣元素。【解答】1000 8．一個具有n個頂點(diǎn)k條邊的無向圖是一個森林（n>k），則該森林中必有（）棵樹。 A k B n C n-k D 1 【解答】C 9．用深度優(yōu)先遍歷方法遍歷一個有向無環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧次序打印出相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是（）。 A 逆拓?fù)溆行?B 拓?fù)溆行?C 無序 D 深度優(yōu)先遍歷序列 【解答】A 10.關(guān)鍵路徑是AOE網(wǎng)中（）。 A 從源點(diǎn)到終點(diǎn)的最長路徑 B從源點(diǎn)到終點(diǎn)的最長路徑 C 最長的回路 D 最短的回路 【解答】A 11.已知無向圖G的鄰接表如圖6-10所示，分別寫出從頂點(diǎn)1出發(fā)的深度遍歷和廣度遍歷序列，并畫出相應(yīng)的生成樹。 【解答】深度優(yōu)先遍歷序列為：1，2，3，4，5，6 對應(yīng)的生成樹為： 廣度優(yōu)先遍歷序列為：1，2，4，3，5，6 對應(yīng)的生成樹為： 12.已知已個AOV網(wǎng)如圖6-11所示，寫出所有拓?fù)湫蛄小?/p> 【解答】拓?fù)湫蛄袨椋簐0 v1 v5 v2 v3 v6 v4、v0 v1 v5 v2 v6 v3 v4、v0 v1 v5 v6 v2 v3 v4。 《數(shù)據(jù)結(jié)構(gòu)》 2n10．散列函數(shù)越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突概率小.× 11．Hash表的平均查找長度與處理沖突的方法無關(guān)?！?/p> 12．負(fù)載因子(裝填因子)是散列表的一個重要參數(shù)，它反映散列表的裝滿程度?！?13.若散列表的負(fù)載因子α<1，則可避免碰撞的產(chǎn)生?！?/p> 三、填空題 1.順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為__（1）n __次。2.在有序表A[1..20]中，按二分查找方法進(jìn)行查找，查找長度為5的元素個數(shù)是__（2）5 __。 3.在有序表A[1?20]中，按二分查找方法進(jìn)行查找，查找長度為4的元素的下標(biāo)從小到大依次是____（3）1,3,6,8,11,13,16,19__。4.有序表(12,18,24,35,47,50,62,83,90,115，134)使用二分法查找90時，需___（4）2_次查找成功，查100時，需___（5）4_次才能確定不成功。 5.在n個記錄的有序順序表中進(jìn)行折半查找，最大比較次數(shù)是___（6）log2n+1__。（取下界） 6.平衡因子的定義是___（7）結(jié)點(diǎn)的左子樹的高度減去結(jié)點(diǎn)的右子樹的高度___ 7.高度為8的平衡二叉樹的結(jié)點(diǎn)數(shù)至少有___（8）54__個。（參照教材P238：N0=0,N1=1,N2=2,公式Nh=Nh-1+Nh-2+1） 8.動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有___（9）插入 _和__（10）_刪除__運(yùn)算，而后者不包含這兩種運(yùn)算。 四、應(yīng)用題 1.假定對有序表：(3,4,5,7,24,30,42,54,63,72,87,95)進(jìn)行折半查找，試回答下列問題： (1).畫出描述折半查找過程的判定樹； (2).若查找元素54，需依次與那些元素比較?(3).若查找元素90，需依次與那些元素比較?(4).假定每個元素的查找概率相等，求查找成功時的平均查找長度。 2.一棵二叉排序樹結(jié)構(gòu)如下,各結(jié)點(diǎn)的值從小到大依次為1-9，請標(biāo)出各結(jié)點(diǎn)的值。 3.依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序樹【華中理工大學(xué) 2000 五（10分）】 (1)試畫出生成之后的二叉排序樹;(2)對該二叉排序樹作中序遍歷，試寫出遍歷序列;(3)假定每個元素的查找概率相等，試計(jì)算該二叉排序樹的平均查找長度。 4.設(shè)哈希函數(shù)H（k）=3 K mod 11，散列地址空間為0～10，對關(guān)鍵字序列（32,13,49,24,38,21,4,12）按下述兩種解決沖突的方法構(gòu)造哈希表（1）線性探測再散列（2）鏈地址法，并分別求出等概率下查找成功時的平均查找長度； 、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案 中南大學(xué)現(xiàn)代遠(yuǎn)程教育課程考試（?？疲?fù)習(xí)題及參考答案 數(shù)據(jù)結(jié)構(gòu) 一、判斷題： 1． 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。（）2． 鏈?zhǔn)酱鎯υ诓迦撕蛣h除時需要保持物理存儲空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序。 （） 3． 在只有度為0和度為k的結(jié)點(diǎn)的k叉樹中，設(shè)度為0的結(jié)點(diǎn)有n0個，度為k的結(jié)點(diǎn)有nk個，則有n0=nk+1。（）4． 折半搜索只適用于有序表，包括有序的順序表和有序的鏈表。（）5． 如果兩個串含有相同的字符，則這兩個串相等。 （） 6． 數(shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以對它進(jìn)行插入、刪除等運(yùn)算。（）7． 在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針。（）8． 通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高。 （）9． 一個廣義表的表尾總是一個廣義表。 （）10． 當(dāng)從一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。 （） 11． 對于一棵具有n個結(jié)點(diǎn)，其高度為h的二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度為O（h）。 （） 12． 存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。 （） 13． 直接選擇排序是一種穩(wěn)定的排序方法。 （）14． 閉散列法通常比開散列法時間效率更高。 （）15． 有n個結(jié)點(diǎn)的不同的二叉樹有n!棵。（）16． 直接選擇排序是一種不穩(wěn)定的排序方法。（）17． 在2048個互不相同的關(guān)鍵碼中選擇最小的5個關(guān)鍵碼，用堆排序比用錦標(biāo)賽排序更快。（）18． 當(dāng)3階B_樹中有255個關(guān)鍵碼時,其最大高度(包括失敗結(jié)點(diǎn)層)不超過8。（）19． 一棵3階B_樹是平衡的3路搜索樹,反之,一棵平衡的3路搜索樹是3階非B_樹。（）20． 在用散列表存儲關(guān)鍵碼集合時，可以用雙散列法尋找下一個空桶。在設(shè)計(jì)再散列函數(shù)時，要求計(jì)算出的值與表的大小m互質(zhì)。（）21． 在索引順序表上實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關(guān)，而且與每一塊中元素個數(shù)有關(guān)。（） 22． 在順序表中取出第i個元素所花費(fèi)的時間與i成正比。 （）23． 在棧滿情況下不能作進(jìn)棧運(yùn)算，否則產(chǎn)生“上溢”。 ()24． 二路歸并排序的核心操作是將兩個有序序列歸并為一個有序序列。（）25． 對任意一個圖，從它的某個頂點(diǎn)出 發(fā)，進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點(diǎn).（）26． 二叉排序樹或者是一棵空二叉樹，或者不是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點(diǎn)的值大于其左孩子的值;若它的右子樹非空，則根結(jié)點(diǎn)的值小于其右孩子的值。（）27． 在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（） 28． 一個有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個數(shù)一定相等。（） 二、選擇題： 1． 在一個長度為n的順序表的任一位置插入一個新元素的漸進(jìn)時間復(fù)雜度為（）。A.O(n) B.O(n／2) C.O(1) D.O(n2)2． 帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是：（）A.first==NULL B.first一>1ink＝＝NULL C.first一>link==first D.first!＝NUlL 3． 當(dāng)利用大小為n的數(shù)組順序存儲一個隊(duì)列時，該隊(duì)列的最大長度為（）。 A.n-2 B.n-l C.n D.n+1 4． 在系統(tǒng)實(shí)現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存實(shí)際參數(shù)的值。在傳值參數(shù)情形，需為對應(yīng)形式參數(shù)分配空間，以存放實(shí)際參數(shù)的副本；在引用參數(shù)情形，需保存實(shí)際參數(shù)的（），在被調(diào)用程序中可直接操縱實(shí)際參數(shù)。 A.空間 B.副本 C.返回地址 D.地址 5． 在一棵樹中，（）沒有前驅(qū)結(jié)點(diǎn)。A.分支結(jié)點(diǎn) D.葉結(jié)點(diǎn) C.樹根結(jié)點(diǎn) D.空結(jié)點(diǎn) 6． 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（）。 A.2 B.1 C.0 D.-1 7． 對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（）的值除以9。A.20 B.18 C.25 D.22 8． 在有向圖中每個頂點(diǎn)的度等于該頂點(diǎn)的（）。A.入度 B.出度 C.入度與出度之和 D.入度與出度之差 9． 在基于排序碼比較的排序算法中，（）算法的最壞情況下的時間復(fù)雜度不高于O(n10g2n)。A.起泡排序 B.希爾排序 C.歸并排序 D.快速排序 10． 當(dāng)α的值較小時，散列存儲通常比其他存儲方式具有（）的查找速度。A.較慢 B.較快 C.相同 D.不清楚 11． 設(shè)有一個含200個表項(xiàng)的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時找到一個表項(xiàng)的平均探查次數(shù)不超過1.5，則散列表項(xiàng)應(yīng)能夠至少容納（）個表項(xiàng)。(設(shè)搜索成功的平均搜索長度為Snl＝{1+l／(1一α)}／2，其中α為裝填因子) A.400 B.526 C.624 D.676 12． 堆是一個鍵值序列{k1,k2,.....kn},對I=1,2,....|_n/2_|,滿足（）A.ki≤k2i≤k2i+1 B.ki 1(2i+1≤n) 13． 若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上() A.操作的有限集合B.映象的有限集合 C.類型的有限集合D.關(guān)系的有限集合 14． 在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為() A.n-i+1 B.i C.i+1 D.n-i 15． 若不帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則該鏈表為空的判定條件是() A.head==NULL B.head->next==NULL C.head!=NULL D.head->next==head 16． 引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是() A.出隊(duì) B.入隊(duì) C.取隊(duì)頭元素 D.取隊(duì)尾元素 17． 若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)的出棧序列是() A.2，4，3，1，5，6 B.3，2，4，1，6，5 C.4，3，2，1，5，6 D.2，3，5，1，6，4 18． 字符串通常采用的兩種存儲方式是() A.散列存儲和索引存儲 B.索引存儲和鏈?zhǔn)酱鎯?/p> C.順序存儲和鏈?zhǔn)酱鎯?/p> D.散列存儲和順序存儲 19． 設(shè)主串長為n，模式串長為m(m≤n)，則在匹配失敗情況下，樸素匹配算法進(jìn)行的無效位移次數(shù)為() A.m B.n-m C.n-m+D.n 20． 二維數(shù)組A［12］［18］采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且第1個元素的地址為150，則元素A［9］［7］的地址為() A.429 B.432 C.435 D.438 21． 對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結(jié)果是() A.(e,f) B.((e,f)) C.(f) D.()22． 下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是() 23． n個頂點(diǎn)的強(qiáng)連通圖中至少含有()A.n-1條有向邊 B.n條有向邊 C.n(n-1)/2條有向邊 D.n(n-1)條有向邊 24． 對關(guān)鍵字序列(56，23，78，92，88，67，19，34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為() A.(19，23，56，34，78，67，88，92)B.23，56，78，66，88，92，19，34) C.(19，23，34，56，67，78，88，92) D.(19，23，67，56，34，78，92，88)25． 若在9階B-樹中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，則該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個數(shù)為() A.4 B.5 C.8 D.9 26． 由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹() A.其形態(tài)不一定相同，但平均查找長度相同 B.其形態(tài)不一定相同，平均查找長度也不一定相同 C.其形態(tài)均相同，但平均查找長度不一定相同 D.其形態(tài)均相同，平均查找長度也都相同 27． ISAM文件和VSAM文件的區(qū)別之一是() A.前者是索引順序文件，后者是索引非順序文件 B.前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取 C.前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動態(tài)索引結(jié)構(gòu) D.前者的存儲介質(zhì)是磁盤，后者的存儲介質(zhì)不是磁盤 28． 下列描述中正確的是（） A． 線性表的邏輯順序與存儲順序總是一致的 B． 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運(yùn)算：插入、刪除和查找 C． 數(shù)據(jù)結(jié)構(gòu)實(shí)質(zhì)上包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的內(nèi)容 D． 選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問題的關(guān)鍵步驟 29． 下面程序段的時間復(fù)雜度是（） i=s=0 while(s {i++; s+=i; } A．O(1)B.O(n)C.O(log2n)D.O(n2)30． 對于順序表來說，訪問任一節(jié)點(diǎn)的時間復(fù)雜度是（） A．O(1)B.O(n)C.O(log2n)D.O(n2)31． 在具有n個節(jié)點(diǎn)的雙鏈表中做插入、刪除運(yùn)算，平均時間復(fù)雜度為（） A．O(1)B.O(n)C.O(log2n)D.O(n2)32． 經(jīng)過下列運(yùn)算后，QueueFront(Q)的值是（） InitQueue(Q);EnQueue(Q,a);EnQueue(Q,a);DeQueue(Q,x); A.a B.b C.1 D.2 33． 一個棧的入棧序列是a,b,c，則棧的不可能輸出序列是（） A.acb B.abc C.bca D.cab 34． 循環(huán)隊(duì)列是空隊(duì)列的條件是（） A．Q->rear==Q->front B.(Q->rear+1)%maxsize==Q->front C.Q->rear==0 D.Q->front==0 35． 設(shè)s3=“I AM”,s4=“A TERCHER”.則strcmp(s3,s4)=() A.0 B.小于0 C.大于0 D.不確定 36． 一維數(shù)組的元素起始地址loc[6]=1000，元素長度為4，則loc[8]為（） A．1000 B.1004 C.1008 D.8 37． 廣義表（（a,b）,c,d）的表尾是（） A．a(chǎn) B.b C.(a,b)D.(c,d)38． 對于二叉樹來說，第I層上至多有____個節(jié)點(diǎn)（） A．2i B.2i-1 C.2i-1 D.2i-1-1 39． 某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF，則后序遍歷序列為（） A．BDGCEFHA B.GDBECFHA C.BDGAECHF D.GDBEHFCA 40． M叉樹中，度為0的節(jié)點(diǎn)數(shù)稱為（） A．根 B.葉 C.祖先 D.子孫 41． 已知一個圖如下所示，若從頂點(diǎn)a出發(fā)按寬度搜索法進(jìn)行遍歷，則可能得到的一種頂 點(diǎn)序列為（） 42． 堆的形狀是一棵（） A．二叉排序樹 B.滿二叉樹 C.完全二義樹 D.平衡二叉樹 43． 排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（） A．希爾排序 B.歸并排序 C.插入排序 D.選擇排序 44． 采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（） A．n B.n/2 C.(n+1)/2 D.（n-1)/2 45． 散列查找是由鍵值______確定散列表中的位置，進(jìn)行存儲或查找（） A．散列函數(shù)值 B.本身 C.平方 D.相反數(shù) 46． 順序文件的缺點(diǎn)是（） A．不利于修改 B.讀取速度慢 C.只能寫不能讀 D.寫文件慢 47． 索引文件的檢索方式是直接存取或按_____存取（） A．隨機(jī)存取 B.關(guān)鍵字 C.間接 D.散列 48． 堆是一個鍵值序列{k1,k2,.....kn},對i=1,2,....|_n/2_|,滿足（） A.ki≤k2i≤k2i+1 B.ki C.ki≤k2i且ki≤k2i+1(2i+1≤n)D.ki≤k2i 或ki≤k2i+1(2i+1≤n) 三、計(jì)算與算法應(yīng)用題（本大題每小題9分） 1.給定表（119，14，22，1，66，21，83，27，56，13，10） 請按表中元素的順序構(gòu)造一棵平衡二叉樹，并求其在等概率情況下查找成功的平均長度。（9分）2.已知一個有向圖的頂點(diǎn)集V和邊集G分別為： V={a,b,c,d,e,f,g,h} E={ 3.設(shè)散列表的長度為13，散列函數(shù)為H（h）= k%13，給定的關(guān)鍵碼序列為19，14，23，01，68，20，84，27。試畫出用線性探查法解決沖突時所構(gòu)成的散列表。（8分） 0 4.對7個關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。 (1)假設(shè)關(guān)鍵字集合為{1,2,3,4,5,6,7}，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列； (2)對所舉序列進(jìn)行快速排序，寫出排序過程。（９分）5.如圖所示二叉樹，回答下列問題。（9分） 6.畫出在一個初始為空的AVL樹中依次插入3,1,4,6,9,8,5,7時每一插入后AVL樹的形態(tài)。若做了某種旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。然后，給出在這棵插入后得到的AVL樹中刪去根結(jié)點(diǎn)后的結(jié)果。7.已知一組記錄的排序碼為（46，79，56，38，40，80，95，24），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。 8.一個線性表為 B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為 HT[0..12]，散列函數(shù)為 H（key）= key % 13 并用線性探查法解決沖突，請畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。 9.已知一棵二叉樹的前序遍歷的結(jié)果序列是 ABECKFGHIJ，中序遍歷的結(jié)果是 EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。 10.假定對線性表(38，25，74，52，48，65，36)進(jìn)行散列存儲，采用H(K)=K％9作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對應(yīng)的平均查找長度分別為 和 。11．假定一組記錄的排序碼 為(46，79，56，38，40，80，25，34，57，21)，則對其進(jìn)行快速排序的第一次劃分后又對左、右兩個子區(qū)間分別進(jìn)行一次劃分，得到的結(jié)果為：。 12.下圖是帶權(quán)的有向圖G的鄰接表表示法。從結(jié)點(diǎn)V1出發(fā)，深度遍歷圖G所得結(jié)點(diǎn)序列為（A），廣度遍歷圖G所得結(jié)點(diǎn)序列為（B）；G的一個拓?fù)湫蛄惺牵–）；從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的最短路徑為（D）；從結(jié)點(diǎn)V1到結(jié)點(diǎn)V8的關(guān)鍵路徑為（E）。其中A、B、C的選擇有： V1,V2,V3,V4,V5,V6,V7,V8 V1,V2,V4,V6,V5,V3,V7,V8 V1,V2,V4,V6,V3,V5,V7,V8 V1,V2,V4,V6,V7,V3,V5,V8 V1,V2,V3,V8,V4,V5,V6,V7 V1,V2,V3,V8,V4,V5,V7,V6 V1,V2,V3,V8,V5,V7,V4,V6 D、E的選擇有： ① V1,V2,V4,V5,V3,V8 ② V1,V6,V5,V3,V8 ③ V1,V6,V7,V8 ④ V1,V2,V5,V7,V8 13.畫出對長度為10的有序表進(jìn)行折半查找的判定樹，并求其等概率時查找成功的平均查找長度。14.已知如圖所示的有向網(wǎng)，試?yán)肈ijkstra算法求頂點(diǎn)1到其余頂點(diǎn)的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。 15.假定用于通信的電文由８個字母a,b,c,d,e,f,g,h組成，各字母在電文中出現(xiàn)的頻率分別為５，２５，３，６，１０，１１，３６，４。試為這８個字母設(shè)計(jì)不等長Huffman編碼，并給出該電文的總碼數(shù)。 16.已知一棵二叉樹的中序和前序序列如下，試畫出該二叉樹并求該二叉樹的后序序列。（9分）中序序列：c，b，d，e，a，g，i，h，j，f 前序序列：a，b，c，d，e，f，g，h，i，j 17.假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設(shè)計(jì)哈夫曼編碼。使用0～7的二進(jìn)制表示形式是另一種編碼方案。對于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。 四、算法設(shè)計(jì)題 1.已知深度為h的二叉樹以一維數(shù)組BT(1:2h-1)作為其存儲結(jié)構(gòu)。請寫一算法，求該二叉樹中葉結(jié)點(diǎn)的個數(shù)。 2.編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找item帶回整個結(jié)點(diǎn)的值并返回ture，否則返回false。bool Find（BtreeNode*BST，ElemType&item） 3.編寫算法，將一個結(jié)點(diǎn)類型為 Lnode 的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序?yàn)?a 1，......a n-1，a n，則逆序鏈接后變?yōu)?, a n，a n-1，......a 1。 4.根據(jù)下面函數(shù)原型，編寫一個遞歸算法，統(tǒng)計(jì)并返回以BT為樹根指針的二叉樹中所有 葉子結(jié)點(diǎn)的個數(shù)。int Count(BTreeNode * BT)； 5.設(shè)A=(a1,...,am)和B=(b1,...,bn)均為順序表，A'和B'分別為A和B中除去最大共同前綴后的子表。若A'=B'=空表，則A=B；若A'=空表，而B' ≠空表，或者兩者均不為空表，且A'的首元小于B'的首元，則A 6.已知單鏈表a和b的元素按值遞增有序排列, 編寫算法歸并a和b得到新的單鏈表c，c的元素按值遞減有序。 7.編寫遞歸算法，對于二叉樹中每一個元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹，并釋放相應(yīng)的空間。 8.編寫算法判別T是否為二叉排序樹.9.試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑（i<>j）。注意：算法中涉及的圖的基本操作必須在存儲結(jié)構(gòu)上實(shí)現(xiàn)。 參考答案 一、判斷題 1．√ 2．× 3．√ 4．× 5．√ 6．√ 7．× 8．× 9．× 11 × 12√ 13 × 14 √ 15 × 16 √ 17 × 18 × 19.× 20.× 21.√ 22.× 23.√ 24.√ 25.× 26.× 27.× 28.√ 二、單項(xiàng)選擇題 1．A 2．B 3．B 4．D 5．C 6．A 7．C 8．C 9．C 10．B 11．A 12 C 13.B 14.D 15.A 16.A 17.D 18.C 19.C 20.A 21.B 22.A 23.B 24.D 25.C C 28.D 29.B 30.A 31.A 32.B 33.D 34.A 35.C 36.C 37.D 38.C 39.D 40.A 41.B 42.C 43.D 44.C 45.A 46.A 47.B 48.C 三 計(jì)算與算法應(yīng)用題 １．［解答］ 平均長度為4.2、解：畫圖（略） 深度優(yōu)先搜索序列：a，b，f，h，c，d，g，e 廣度優(yōu)先搜索序列：a，b，c，f，d，e，h，g 3、解：計(jì)算機(jī)關(guān)鍵碼得到的散列地址 關(guān)鍵碼 19 14 23 01 68 20 84 27 散列地址 6 10．× 26.B 1 3 7 6 1 在散列表中散列結(jié)果 0 01 68 27 19 20 84 23 4.對n個關(guān)鍵自序列進(jìn)行一趟快速排序，要進(jìn)行n-1次比較，也就是基準(zhǔn)和其他n-1個關(guān)鍵字比較。 這里要求10次，而71)= 10，這就要求2趟快速排序后，算法結(jié)束。所以，列舉出來的序列，要求在做partition的時候，正好將序列平分 (1)4 1 3 2 6 5 7 或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7.......(2)按自己序列完成 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov(1)(2)(1)(1)(1)(1)(2)(4)(5)(2)(5)(6) (2)搜索成功的平均搜索長度為 l／12*(1+2+l+l+l+l+2+4+5+2+5+6)：3l／12 5．答案：(1)djbaechif(2)abdjcefhi(3)jdbeihfca 6.在這個AVL樹中刪除根結(jié)點(diǎn)時有兩種方案: 【方案1】在根的左子樹中沿右鏈走到底,用5遞補(bǔ)根結(jié)點(diǎn)中原來的6,再刪除5所在的結(jié)點(diǎn).【方案2】在根的右子樹中沿左鏈走到底,用7遞補(bǔ)根結(jié)點(diǎn)中原來的6,再刪除7所在的結(jié)點(diǎn).7.劃分次序 劃分結(jié)果第二篇：數(shù)據(jù)結(jié)構(gòu)試題及答案
第三篇：數(shù)據(jù)結(jié)構(gòu) 第六章 圖 練習(xí)題及答案詳細(xì)解析(精華版)
第四篇：數(shù)據(jù)結(jié)構(gòu)第四教學(xué)單元測驗(yàn)練習(xí)題(答案)
第五篇：數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案
點(diǎn)擊咨詢 