第一篇：數(shù)據(jù)結構練習題及答案
數(shù)據(jù)結構練習題及答案 第1章 緒論 一、判斷題 1.數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的內(nèi)容和形式無關。
（√）2.一個數(shù)據(jù)結構是由一個邏輯結構和這個邏輯結構上的一個基本運算集構成的整體。
（√）3.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。
（×）4.數(shù)據(jù)的邏輯結構和數(shù)據(jù)的存儲結構是相同的。
（×）5.程序和算法原則上沒有區(qū)別，所以在討論數(shù)據(jù)結構時可以通用。
（×）6.從邏輯關系上講，數(shù)據(jù)結構主要分為線性結構和非線性結構兩類。
（√）7.數(shù)據(jù)的存儲結構是數(shù)據(jù)的邏輯結構的存儲映象。
（√）8.數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式。
（√）9.數(shù)據(jù)的邏輯結構是依賴于計算機的。
（×）10.算法是對解題方法和步驟的描述。
（√）二、填空題 1.數(shù)據(jù)有邏輯結構和 存儲結構 兩種結構。
2.數(shù)據(jù)邏輯結構除了集合以外，還包括線性結構、樹形結構和圖形結構 。
3.數(shù)據(jù)結構按邏輯結構可分為兩大類，它們是線性結構和非線性結構 。
4.樹形結構 和圖形結構 合稱為非線性結構。
5.在樹形結構中，除了樹根結點以外，其余每個結點只有1個前驅(qū)結點。
6.在圖形結構中，每個結點的前驅(qū)結點數(shù)和后繼結點數(shù)可以任意多個 。
7.數(shù)據(jù)的存儲結構又叫物理結構 。
8.數(shù)據(jù)的存儲結構形式包括順序存儲、鏈式存儲、索引存儲和散列存儲 。
9.線性結構中的元素之間存在一對一 的關系。
10.樹形結構中的元素之間存在一對多 的關系。
11.圖形結構的元素之間存在多對多 的關系。
12.數(shù)據(jù)結構主要研究數(shù)據(jù)的邏輯結構、存儲結構和算法（或運算） 3個方面的內(nèi)容。
13.數(shù)據(jù)結構被定義為（D，R），其中D是數(shù)據(jù)的有限集合，R是D上的關系 有限集合。
14.算法是一個有窮指令 的集合。
15.算法效率的度量可以分為事先估算法和事后統(tǒng)計法 。
16.一個算法的時間復雜度是算法 輸入規(guī)模 的函數(shù)。
17.算法的空間復雜度是指該算法所耗費的存儲空間 ，它是該算法求解問題規(guī)模的n的函數(shù)。
18.若一個算法中的語句頻度之和為T(n)=6n+3nlog2n,則算法的時間復雜度為O（nlog2n）。
19.若一個算法的語句頻度之和為T(n)=3n+nlog2+n2,則算法的時間復雜度為O（n2）。
20.數(shù)據(jù)結構是一門研究非數(shù)值計算的程序問題中計算機的操作對象，以及它們之間的關系和運算的學科。
三、選擇題 1.數(shù)據(jù)結構通常是研究數(shù)據(jù)的（A）及它們之間的相互關系。
A．存儲結構和邏輯結構 B．存儲和抽象 C．聯(lián)系和抽象 D．聯(lián)系與邏輯 2.在邏輯上可以把數(shù)據(jù)結構分成（C）。
A．動態(tài)結構和靜態(tài)結構 B．緊湊結構和非緊湊結構 C．線性結構和非線性結構 D．內(nèi)部結構和外部結構。
3.數(shù)據(jù)在計算機存儲內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（C）。
A．存儲結構 B．邏輯結構 C．順序存儲結構 D．鏈式存儲結構 4.非線性結構中的每個結點（D）。
A．無直接前驅(qū)結點． B．無直接后繼結點． C．只有一個直接前驅(qū)結點和一個直接后繼結點D．可能有多個直接前驅(qū)結點和多個直接后繼結點 5.鏈式存儲結構所占存儲空間（A）。
A．分兩部分，一部分存放結點的值，另一個部分存放表示結點間關系的指針。
B．只有一部分，存放結點的值。
C．只有一部分，存儲表示結點間關系的指針。
D．分兩部分，一部分存放結點的值，另一部分存放結點所占單元素 6.算法的計算量大小稱為算法的（C）。
A．現(xiàn)實性 B．難度 C．時間復雜性 D．效率 7.數(shù)據(jù)的基本單位（B）。
A．數(shù)據(jù)結構 B．數(shù)據(jù)元素 C．數(shù)據(jù)項 D．文件 8.每個結點只含有一個數(shù)據(jù)元素，所有存儲結點相繼存放在一個連續(xù)的存儲空間里，這種存儲結構稱為（A）結構。
A．順序結構 B．鏈式結構 C．索引結構 D．散列結構 9.每一個存儲結點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（B）。
A．順序 B．鏈式 C．索引 D．散列 10.以下任何兩個結點之間都沒有邏輯關系的是（D）。
A．圖形結構 B．線性結構 C．樹形結構 D．集合 11.在數(shù)據(jù)結構中，與所使用的計算機無關的是（C）。
A．物理結構 B．存儲結構 C．邏輯結構 D．邏輯和存儲結構 12.下列4種基本邏輯結構中，數(shù)據(jù)元素之間關系最弱的是（A）。
A．集合 B．線性結構 C．樹形結構 D．圖形結構 13.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的（A）。
A．邏輯結構 B．存儲結構 C．邏輯實現(xiàn) D．存儲實現(xiàn) 14.每一個存儲結點只含有一個數(shù)據(jù)元素，存儲結點存放在連續(xù)的存儲空間，另外有一組指明結點存儲位置的表，該存儲方式是（C）存儲方式。
A．順序 B．鏈式 C．索引 D．散列 15.算法能正確的實現(xiàn)預定功能的特性稱為算法的（A）。
A．正確性 B．易讀性 C．健壯性 D．高效性 16.算法在發(fā)生非法操作時可以作出相應處理的特性稱為算法的（C）。
A．正確性 B．易讀性 C．健壯性 D．高效性 17.下列時間復雜度中最壞的是（D）。
A．O（1）B.O（n）C.O(log2n)D.O(n2)18.下列算法的時間復雜度是（D）。
for(i=0;i A.空間復雜性和時間復雜性 B.正確性和簡明性 C.可讀性和文檔性 D.數(shù)據(jù)復雜性和程序復雜性 20.計算機算法必須具備輸入、輸出和（C）。 A.計算方法 B.排序方法 C.解決問題的有限運算步驟D.程序設計方法 第2章 線性表 一、判斷題 1.線性表的鏈式存儲結構優(yōu)于順序存儲。 （×）2.鏈表的每個結點都恰好包含一個指針域。 （×）3.在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。 （√）4.順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。 （×）5.線性鏈表的刪除算法簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。 （×）6.順序表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。 （×）7.線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。 （√）8.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 （√）9.順序表結構適宜進行順序存取，而鏈表適宜進行隨機存取。 （×）10.插入和刪除操作是數(shù)據(jù)結構中是最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。（×）二、填空題 1.順序表中邏輯上相鄰的元素在物理位置上必須相鄰。 2.線性表中結點的集合是有限的，結點間的關系是一對一關系。 3.順序表相對于鏈表的優(yōu)點是節(jié)省存儲和隨機存取。 4.鏈表相對于順序表的優(yōu)點是插入、刪除方便。 5.當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快速度存取線性表中的元素時，應采用 順序 存儲結構。 6.順序表中訪問任意一個結點的時間復雜度均為O（1）。 7.鏈表相對于順序表的優(yōu)點是插入、刪除方便； 缺點是存儲密度小。 8.在雙向鏈表中要刪除已知結點*P，其時間復雜度為O（1）。 9.在單向鏈表中要在已知結點*P之前插入一個新結點，需找到*P的直接前驅(qū)結點的地址，其查找的時間復雜度為O(n)。 10.在單向鏈表中需知道頭指針才能遍歷整個鏈表。 11.線性表中第一個結點沒有直接前驅(qū)，稱為開始結點。 12.在一個長度為n的順序表中刪除第i個元素，要移動 n-i 個元素。 13.在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移 n-i+1 個元素。 14.在無頭結點的單向鏈表中，第一個結點的地址存放在頭指針中，而其他結點的存儲地址存放在 前趨 結點的指針域中。 15.線性表的元素總數(shù)不確定，且經(jīng)常需要進行插入和刪除操作，應采用 鏈子 存儲結構。 16.在線性表中的鏈式存儲中，元素之間的邏輯關系是通過 指針 決定。 17.在雙向鏈表中，每個結點都有兩個指針域，它們一個指向其 前趨 結點，另一個指向其后繼結點。 18.對一個需要經(jīng)常進行插入和刪除操作的線性表，采用 鏈式 存儲結構為宜。 19.雙向鏈表中，設P是指向其中待刪除的結點，則需要執(zhí)行的操作為p->prior->next=p->next； p->next->prior=p->prior 20.在如圖所示的鏈表中，若在指針P所在的結點之后插入數(shù)據(jù)域值為a和b的兩個結點，則可用語句S->next->next=p->next和P-> next=S； 來實現(xiàn)該操作。 p ∧ a b s 三、選擇題 1.在具有n個結點的單向鏈表中，實現(xiàn)（A）的操作，其算法的時間復雜度都是O(n).A.遍歷鏈表或求鏈表的第i個結點 B.在地址為P的結點之后插入一個結點 C.刪除開始結點 D.刪除地址為P的結點的后繼結點 2.設a、b、c為3個結點，p、10、20分別代表它們的地址，則如下的存儲結構稱為（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.已知一個順序存儲的線性表，設每個結點占m個存儲單元，若第一個結點的地址為B，則第i個結點的地址為（A）。 A.B+(i-1)×m B.B+i×m C.B-i×m D.B+(i+1)×m 5.在有n個結點的順序表上做插入、刪除結點運算的時間復雜度為（B）。 A．O（1）B.O（n）C.O(n2)D.O(log2n)6.設front、rear分別為循環(huá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)點是（C）。 A．便于隨機存取 B．花費的存儲空間比順序表少 C．便于插入和刪除 D．數(shù)據(jù)元素的物理順序與邏輯順序相同 9.在單鏈表中，增加頭結點的目的是（C）。 A．使單鏈表至少有一個結點 B．標志表中首結點的位置 C．方便運算的實現(xiàn) D．說明該單鏈表是線性表的鏈式存儲結構 10.下面關于線性表的敘述中，錯誤的是（D）關系。 A．順序表必須占一片地址連續(xù)的存儲單元B．順序表可以隨機存取任一元素 C．鏈表不必占用一片地址連續(xù)的存儲單元D．鏈表可以隨機存取任一元素 11.L是線性表，已知LengthList(L)的值是5，經(jīng)DelList(L，2)運算后，LengthList(L)的值是（C）。 A．2 B．3 C．4 D．5 12.單向鏈表的示意圖如下： L A B C D ∧ P Q R 指向鏈表Q結點的前驅(qū)的指針是（B）。 A．L B．P C．Q D．R 13.設p為指向單循環(huán)鏈表上某結點的指針，則*p的直接前驅(qū)（C）。 A．找不到 B．查找時間復雜度為O（1）C．查找時間復雜度為O（n）D．查找結點的次數(shù)約為n 14.等概率情況下，在有n個結點的順序表上做插入結點運算，需平均移動結點的數(shù)目為（8）。 A．n B.(n-1)/2 C.n/2 D.(n+1)/2 15.在下列鏈表中不能從當前結點出發(fā)訪問到其余各結點的是（C）。 A.雙向鏈表 B.單循環(huán)鏈表 C.單向鏈表 D.雙向循環(huán)鏈表 16.在順序表中，只要知道（D），就可以求出任一結點的存儲地址。 A.基地址 B.結點大小 C.向量大小 D.基地址和結點大小 17.在雙向鏈表中做插入運算的時間復雜度為（A）。 A．O（1）B.O（n）C.O(n2)D.O(log2n)18.鏈表不具備的特點是（A）。 A．隨機訪問 B.不必事先估計存儲空間C.插入刪除時不需要移動元素 D.所需空間與線性表成正比 19.以下關于線性表的論述，不正確的為（C）。 A.線性表中的元素可以是數(shù)字、字符、記錄等不同類型B.線性順序表中包含的元素個數(shù)不是任意的 C.線性表中的每個結點都有且僅有一個直接前驅(qū)和一個直接后繼 D.存在這樣的線性表，即表中沒有任何結點 20.在（B）的運算中，使用順序表比鏈表好。 A.插入 B.根據(jù)序號查找 C.刪除 D.根據(jù)元素查找 第3章 棧 一、判斷題 1.棧是運算受限制的線性表。 （√）2.在棧空的情況下，不能作出棧操作，否則產(chǎn)生下溢。 （√）3.棧一定是順序存儲的線性結構。 （×）4.棧的特點是“后進先出”。 （√）5.空棧就是所有元素都為0的棧。 （×）6.在C（或C++）語言中設順序棧的長度為MAXLEN，則top=MAXLEN時表示棧滿。 （×）7.鏈棧與順序棧相比，其特點之一是通常不會出現(xiàn)棧滿的情況。 （√）8.一個棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。 （×）9.遞歸定義就是循環(huán)定義。 （×）10.將十進制數(shù)轉換為二進制數(shù)是棧的典型應用之一。 （√）二、填空題 1.在棧結構中，允許插入、刪除的一端稱為 棧頂。 2.在順序棧中，當棧頂指針top=-1時，表示 棧空。 3.在有n個元素的棧中，進棧操作時間復雜度為 O（1）。 4.在棧中，出棧操作時間復雜度為 O（1）。 5.已知表達式，求它的后綴表達式是 棧 的典型應用。 6.在一個鏈棧中，若棧頂指針等于NULL，則表示 棧空。 7.向一個棧頂指針為top的鏈棧插入一個新結點*p時，應執(zhí)行p->next=top;top=p； 操作。 8.順序棧S存儲在數(shù)組S->data[0…MAXLEN-1]中，進棧操作時要執(zhí)行的語句有：S->top++。(或S->top+1)S->data[S->top]=x 9.鏈棧LS，指向棧頂元素的指針是LS->next。 10.從一個棧刪除元素時，首先取出 棧頂元素，然后再移動棧頂指針。 11.由于鏈棧的操作只在鏈表的頭部進行，所以沒有必要設置 頭 結點。 12.已知順序棧S，在對S進棧操作之前首先要判斷 棧是否滿。 13.已知順序棧S，在對S出棧操作之前首先要判斷 棧是否空。 14.若內(nèi)在空間充足， 鏈 棧可以不定義棧滿運算。 15.鏈棧LS為空的條件是 LS->next=NULL。 16.鏈棧LS的棧頂元素是鏈表的 首 元素。 17.同一棧的各元素的類型 相同。 18.若進棧的次序是A、B、C、D、E，執(zhí)行3次出棧操作以后，棧頂元素為 B。 19.A+B/C-D*E的后綴表達式是 ABC/+DE*-。 20.4個元素A、B、C、D順序進S棧，執(zhí)行兩次Pop(S,x)運算后，x的值是 C。 三、選擇題 1.插入和刪除操作只能在一端進行的線性表，稱為（C）。 A．隊列 B．循環(huán)隊列 C．棧 D．循環(huán)棧 2.設有編號為1，2。3，4的4輛列車，順序進入一個棧結構的站臺，下列不可能的出站順序為（D）。 A．1234 B．1243 C．1324 D．1423 3.如果以鏈表作為棧的存儲結構，則出棧操作時（B）。 A．必須判別棧是否滿 B．必須判別棧是否為空 C．必須判別棧元素類型 D．棧可不做任何判別 4.元素A、B、C、D依次進棧以后，棧頂元素是（D）A．A B．B C．C D．D 5.順序棧存儲空間的實現(xiàn)使用（B）存儲元素。 A．鏈表 B．數(shù)組 C．循環(huán)鏈表 D．變量 6.在C（或C++）語言中，一個順序棧一旦被聲明，其占用空間的大小（A）。 A．已固定 B．不固定 C．可以改變 D．動態(tài)變化 7.帶頭結點的鏈棧LS的示意圖如下，棧頂元素是（A）。 LS H A B C D ∧ A．A B．B C．C D．D 8.鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是（B）。 A.插入操作更加方便 B.通常不會出現(xiàn)棧滿的情況 C.不會出現(xiàn)棧空的情況 D.刪除操作更加方便 9.從一個棧頂指針為top的鏈棧中刪除一個結點時，用x保存被刪除的結點，應執(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指針所指的結點入棧，應執(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順序進S棧，執(zhí)行兩次Pop(S，x)運算后，棧頂元素的值是（B）。 A．A B．B C．C D．D 12.元素A、B、C、D依次進棧以后，棧底元素是（A）。 A．A B．B C．C D．D 13.經(jīng)過下列棧的運算后，再執(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)過下列棧的運算后，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)過下列棧的運算后，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)過下列棧的運算后,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．誰先誰后無關緊要 D．同時進行 18.初始化一個空間大小為5的順序棧S后，S->top的值是（B）。 A．0 B．-1 C．不再改變 D．動態(tài)變化 19.設有一個入棧的次序A、B、C、D、E，則棧不可能的輸出序列是（C）。 A．EDCBA B．DECBA C．DCEAB D．ABCDE 20.設有一個順序棧S，元素A、B、C、D、E、F依次進棧，如果6個元素出棧的順序是B、D、C、F、E、A，則棧的容量至少應是（A）。 A．3 B．4 C．5 D．6 第4章 隊列 一、判斷題 1.隊列是限制在兩端進行操作的線性表。 （√）2.判斷順序隊列為空的標準是頭指針和尾指針都指向同一個結點。 （√）3.在鏈隊列上做出隊操作時，會改變front指針的值。 （×）4.在循環(huán)隊列中，若尾指針rear大于頭指針front，其元素個數(shù)為rear-front。 （√）5.在單向循環(huán)鏈表中，若頭指針為h，那么p所指結點為尾結點的條件是p=h。 （×）6.鏈隊列在一定范圍內(nèi)不會出現(xiàn)隊滿的情況。 （√）7.在循環(huán)鏈隊列中無溢出現(xiàn)象。 （×）8.棧和隊列都是順序存儲的線性結構。 （×）9.在隊列中允許刪除的一端稱為隊尾。 （×）10.順序隊和循環(huán)隊關于隊滿和隊空的判斷條件是一樣的。 （×）二、填空題 1.在隊列中存取數(shù)據(jù)應遵循的原則是 先進先出。 2.隊列 是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算線性表。 3.在隊列中，允許插入的一端稱為 隊尾。 4.在隊列中，允許刪除的一端稱為 隊首（或隊頭）。 5.隊列在進行出隊操作時，首先要判斷隊列是否為 空。 6.順序隊列在進行入隊操作時，首先在判斷隊列是否為 滿。 7.順序隊列初始化后，初始化后，front=rear= -1。 8.解決順序隊列“假溢出”的方法是采用 循環(huán)隊列。 9.循環(huán)隊列的隊指針為front，隊尾指針為rear，則隊空的條件為 front= =rear。 10.鏈隊列LQ為空時，LQ->front->next= NULL。 11.設長度為n的鏈隊列用單循環(huán)表表示，若只設頭指針，則入隊操作的時間復雜度為 O(n)。 12.設長度為n的鏈隊列用單循環(huán)表表示，若只設尾指針，則入隊操作的時間復雜度為 O(1)。 13.在一個鏈隊列中，若隊首指針與隊尾指針的值相同，則表示該隊列為 空。 14.設循環(huán)隊列的頭指針front指向隊首元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，則隊滿標志為 front= =(rear+1)%MAXLEN。 15.在一個鏈隊列中，若隊首指針為front，隊尾指針為rear，則判斷隊列只有一個結點的條件為front= =rear或front!。 16.向一個循環(huán)隊列中插入元素時，首先要判斷 隊尾指針，然后再向指針所指的位置寫入新的數(shù)據(jù)。 17.讀隊首元素的操作 不改變或不影響隊列元素的個數(shù)。 18.設循環(huán)隊列的容量為40（序號0～39），現(xiàn)經(jīng)過一系列的入隊和出隊的運算后，front=11，rear=19，則循環(huán)隊列中還有 8 個元素。 19.隊列Q，經(jīng)過下列運算：InitQueue(Q)(初始化隊列)； InQueue(Q,a)； InQueue(Q,b)； OutQueue(Q,x)； ReadFront(Q,x)； QEmpty(Q)； 后的值是 8。 20.隊列Q經(jīng)過InitQueue(Q)(初始化隊列)； InQueue(Q,a)； InQueue(Q,b)； ReadFront(Q,x)后，x的值是 a。 三、選擇題 1.隊列是限定在（D）進行操作的線性表。 A．中間者 B.隊首 C.隊尾 D.端點 2.隊列中的元素個數(shù)是（B）。 A．不變的 B.可變的 C.任意的 D.0 3.同一隊列內(nèi)的各元素的類型（A）。 A.必須一致 B.不能一致 C.可以不一致 D.不限制 4.隊列是一個（C）線性表結構。 A.不加限制的 B.推廣了的 C.加了限制的 D.非 5.當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最后一個元素的下標為（B）。 A.n-2 B.n-1 C.n D.n+1 6.一個循環(huán)隊列一旦說明，其占用空間的大小（A）。 A.已固定 B.可以變動 C.不能固定 D.動態(tài)變化 7.循環(huán)隊列占用的空間（A）。 A.必須連續(xù) B.不必連續(xù) C.不能連續(xù) D.可以不連續(xù) 8.存放循環(huán)隊列元素的數(shù)組data有10個元素，則data數(shù)組的下標范圍是（B）。 A.0～10 B.0～9 C.1～9 D.1～10 9.若進隊的序列為A、B、C、D，則出隊的序列是（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ù)進隊Q，則隊尾元素是（D）A．A B．B C．C D．D 11.4個元素按A、B、C、D順序連續(xù)進隊Q，執(zhí)行一次QutQueue(Q)操作后，隊頭元素是（B）。 A.A B.B C.C D.D 12.4個元素按A、B、C、D順序連續(xù)進隊Q，執(zhí)行4次QutQueue(Q)操作后，再執(zhí)行QEmpty(Q)； 后的值是（B）。 A.0 B.1 C.2 D.3 13.隊列Q，經(jīng)過下列運算后，x的值是（B）。InitQueue(Q)(初始化隊列)； InQueue(Q,a)； InQueue(Q,b)； OutQueue(Q,x)； ReadFront(Q,x)； A.a B.b C.0 D.1 14.循環(huán)隊列SQ隊滿的條件是（B）。 A.SQ->rear= =SQ->front B.(SQ->rear+1)%MAXLEN= =SQ->front C.SQ->rear= =0 D.SQ->front= =0 15.設鏈棧中結點的結構：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針，若想在鏈棧的棧頂插入一個由指針s所指的結點，則應執(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.帶頭結點的鏈隊LQ示意圖如下，鏈隊列的隊頭元素是（A）。 LQ->front H A B C D ∧ LQ->rear A．A B．B C．C D．D 17.帶頭結點的鏈隊列LQ示意圖如下，指向鏈隊列的隊頭指針是（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.帶頭結點的鏈隊列LQ示意圖如下,在進行進隊的運算時指針LQ->frnot(A).LQ->front H A B C D ∧ LQ->rear A.始終不改變 B.有時改變 C.進隊時改變 D.出隊時改變 19.隊列Q，經(jīng)過下列運算后，再執(zhí)行QEmpty(Q)的值是（C）。 InitQueue(Q)(初始化隊列)； InQueue(Q,a)； InQueue(Q,b)； OutQueue(Q,x)； ReadQueue(Q,x)； A.a B.b C.0 D.1 20.若用一個大小為6數(shù)組來實現(xiàn)循環(huán)隊列，且當前front和rear的值分別為3和0，當從隊列中刪除一個元素，再加入兩個元素后，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)存儲結構。 （√）7.“DT”是“DATA”的子串。 （×）8.串中任意個字符組成的子序列稱為該串的子串。 （×）9.子串的定位運算稱為模式匹配。 （√）10.在鏈串中為了提高存儲密度，應該增大結點的大小。 （√）二、填空題 1.由零個或多個字符組成的有限序列稱為 字符串（或串）。 2.字符串按存儲方式可以分為順序存儲、鏈接存儲和 堆分配存儲。 3.串的順序存儲結構簡稱為 順序串。 4.串順序存儲非緊湊格式的缺點是 空間利用率低。 5.串順序存儲緊湊格式的缺點是對串的字符處理 效率低。 6.串鏈接存儲的優(yōu)點是插入、刪除方便，缺點是 空間利用率。 7.在C或C++語言中，以字符 ＼0 表示串值的終結。 8.空格串的長度等于 空格的個數(shù)。 9.在空串和空格串中，長度不為0的是 空格串。 10.兩個串相等是指兩個串長度相等，且對應位置的 字符都相同。 11.設“S=My Music”，則LenStr(s)= 8。 12.兩個字符串分別為； S1=”Today is”、S2=”30 July，2005”，ConcatStr(S1，S2)的結果是 Today is 30 July,2005。 13.求子串函數(shù)SubStr(“Today is 30 July，2005”，13，4)的結果是 July。 14.在串的運算中，EqualStr(aaa,aab)的返回值 <0。 15.在串的運算中，EqualStr(aaa,aaa)的返回值 0。 16.在子串的定位運算中，被匹配的主串稱為目標串，子串稱為 模式。 17.模式匹配成功的起始位置稱為 有效位移。 18.設S=”abccdcdccbaa”，T=”cdcc”，則第 6 次匹配成功。 19.設S=”c:/mydocument/text1.doc”，T=”mydont”，則字符定位的位置為 0。 20.若n為主串長度，m為子串長度，n>>m，則模式匹配算法最壞情況下的時間復雜度為(n-m+1)*m。 三、選擇題 1.串是和種特殊的線性表，其特殊體現(xiàn)在（B）。 A．可能順序存儲 B．數(shù)據(jù)元素是一個字符C．可以鏈接存儲 D．數(shù)據(jù)元素可以是多個字符 2.某串的長度小于一常數(shù)，則采用（B）存儲方式最節(jié)省空間。 A．鏈式 B．順序 C．堆結構 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.設有兩個串S1和S2，則EqualStr（S1，S2）運算稱作（D）。 A．串連接 B．模式匹配 C．求子串 D．串比較 7.串的模式匹配是指（D）。 A．判斷兩個串是否相等 B．對兩個串比較大小 C．找某字符在主串中第一次出現(xiàn)的位置D．找某子串在主串中第一次出現(xiàn)的第一個字符位置 8.若字符串”ABCDEFG”采用鏈式存儲，假設每個字符占用1個字節(jié)，每個指針占用2個字節(jié)。則該字符串的存儲密度為（D）。 A．20% B．40% C．50% D．33.3% 9.若字符串”ABCDEFG”采用鏈式存儲，假設每個指針占用2個字節(jié)，若希望存儲密度為50%，則每個結點應存儲（A）個字符。 A.2 B.3 C.4 D.5 10.設串S1=”IAM”，S2=”A SDUDENT”，則ConcatStr(S1，S2)=（B）。 A．”I AM” B.”I AM A SDUDENT” C.”IAMASDUDENT” D.”A SDUDENT” 11.設S=””，則LenStr(S)=（A）。 A.0 B.1 C.2 D.3 12.設目標串T=”AABBCCDDE”，模式P=”ABCDE”，則該模式匹配的有效位移為（A）。 A.0 B.1 C.2 D.3 13.設目標串T=”AABBCCDDEEFF”，模式P=”CCD”，則該模式匹配的有效位移為（D）。 A.2 B.3 C.4 D.5 14.設目標串T=”aabaababaabaa”，模式P=”abab”，模式匹配算法的外層循環(huán)進行了（D）次。 A.1 B.9 C.4 D.5 15.模式匹配算法在最壞情況下的時間復雜是（D）。 A.O(m)B.O(n)C.O(m+n)D.O(m×n)16.S=”morning”,執(zhí)行求子串函數(shù)SubSur(S,2,2)后結果為（B）。 A.”mo” B.”or” C.”in” D.”ng” 17.S1=”good”，S2”morning”，執(zhí)行串連接函數(shù)ConcatStr(S1，S2)后結果為（A）。 A.”goodmorning” B.”good morning” C.”GOODMORNING” D.”GOODMORNING” 18.S1=”good”, S2=”morning”執(zhí)行函數(shù)SubSur(S2,4,LenStr(S1))后的結果為（B）。 A.”good” B.”ning” C.”go” D.”morn” 19.設串S1=”ABCDEFG”，S2=”PQRST”，則ConcatStr（SubStr(S1，2，LenStr（S2）），SubStr(S1，LenStr（S2），2））的結果串為（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ù)組元素組成的線性結構。 （√）2.稀疏矩陣中非零元素的個數(shù)遠小于矩陣元素的總數(shù)。 （√）3.上三角矩陣主對角線以上（不包括主對角線的元素），均為常數(shù)C。 （×）4.數(shù)組元素可以由若干數(shù)據(jù)項組成。 （√）5.數(shù)組的三元組表存儲是對稀疏矩陣的壓縮存儲。 （√）6.任何矩陣都可以進行壓縮存儲。 （×）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ù)元素的存放地址可以直接通過地址計算公式算出，所以多維數(shù)組是一 種 隨機 存取結構。 3.在n維數(shù)組中的每一個元素最多可以有 n 個直接前驅(qū)。 4.輸出二維數(shù)組A[n][m]中所有元素值的時間復雜度為 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]的實際地址是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 項。 10.稀疏疏矩陣的壓縮存儲方法通常有三元組表和 十字鏈表 兩種。 11.任何一個非空廣義表的表尾必定是廣義表（或子表）。 12.tail(head((a，b)(c，d)= b。 13.設廣義表（（a，b，c））則將c分離出來的運算是 head(tail(tail(head(L))))。 14.廣義表現(xiàn)出（（a，b）c，d），表尾是 (c,d)。 15.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.開始結點 B.總終端結點 C.邊界結點 D.內(nèi)部結點 2.對下述矩陣進行壓縮存儲后，失去隨機存取功能的是（D）。 A.對稱矩陣 B.三角矩陣 C.三對角矩陣 D.稀疏矩陣 3.在按行優(yōu)先順序存儲的三元組表中，下述陳述錯誤的是（D）。 A.同一行的非零元素，是按列號遞增次序存儲的B.同一列的非零元素，是按行號遞增次序存儲的 C.三元組表中三元組行號是遞增的 D.三元組表中三元組列號是遞增的 4.對稀疏矩陣進行壓縮存儲是為了（B）。 A.降低運算時間B.節(jié)約存儲空間C.便于矩陣運算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．肥否使用原子項 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)),則運算head(head(tail(A)))為（A）。 A． x B．(a,b)C．(x,(a,b))D．A 13.tail(head((a,b),c,(c,d)))的結果是（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）線性表結構。 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.設廣義表D=(a,b,c,d),其深度為（D）。 A.2 B.3 C.4 D.∞ 第7章 樹和二叉樹 一、判斷題 1.樹結構中每個結點最多只有一個直接前驅(qū)。 （√）2.完全二叉樹一定是滿二叉樹。 （×）3.在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。 （×）4.一棵二叉樹中序遍歷序列的最后一個結點，必定是該二叉樹前序遍歷的最后一個結點。（√）5.二叉樹的前序遍歷中，任意一個結點均處于其子女結點的前面。 （√）6.由二叉樹的前序遍歷序列和中序遍歷序列，可以推導出后序遍歷的序列。 （√）7.在完全二叉樹中，若一個結點沒有左孩子，則它必然是葉子結點。 （√）8.在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率相同，其編碼也相同，對于這種情況應該做特殊處理。（×）9.含多于兩棵樹的森林轉換的二叉樹，其根結點一定無右孩子。 （×）10.具有n個葉子結點的哈夫曼樹共有2n-1個結點。 （√）二、填空題 1.在樹中，一個結點所擁有的子樹數(shù)稱為該結點的 度。 2.度為零的結點稱為 葉（或葉子，或終端）結點。 3.樹中結點的最大層次稱為樹的 深度（或高度）。 4.對于二叉樹來說，第i層上至多有 2i-1 個結點。 5.深度為h的二叉樹至多有 2h-1 個結點。 6.由一棵二叉樹的前序序列和 中序 序列可唯一確定這棵二叉樹。 7.有20個結點的完全二叉樹，編號為10的結點的父結點的編號是 5。 8.哈夫曼樹是帶權路徑長度的 最小 的二叉樹。 9.由二叉樹的后序和 中序 遍歷序列，可以唯一確定一棵二叉樹。 10.某二叉樹的中序遍歷序列為：DEBAC，后序遍歷序列為：EBCAD。則前序遍歷序列為 DABEC。 11.設一棵二叉樹結點的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG，則二叉樹中葉結點是： E、F、H。 12.已知完全二叉樹的第8層有8個結點，則其葉結點數(shù)是 68。 13.由樹轉換二叉樹時，其根結點無 右子樹。 14.采用二叉鏈表存儲的n個結點的二叉樹，一共有 2n 個指針域。 15.采用二叉鏈表存儲的n個結點的二叉樹，共有空指針 n+1 個。 16.前序為A，B，C且后序C，B，A的二叉樹共有 4 種。 17.三個結點可以組成 2 種不同形態(tài)的樹。 18.將一棵完全二叉樹按層次編號，對于任意一個編號為i的結點，其左孩子結點的編號為： 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.元素之間有分支的層次關系 2.前序為A，B，C的二叉樹共有（D）種。 A.2 B.3 C.4 D.5 3.根據(jù)二叉樹的定義，具有3個結點的二叉樹有（C）種樹型。 A.3 B.4 C.5 D.6 4.在一棵具有五層的滿二叉樹中，結點的點數(shù)為（B）。 A.16 B.31 C.32 D.33 5.具有64個結點的完全二叉樹的深度為（C）。 A.5 B.6 C.7 D.8 6.任何一棵二叉樹的葉結點在前序、中序、后序遍歷序列中的相對次序（A）。 A.不發(fā)生改變 B.發(fā)生改變 C.不能確定 D.以上都不對 7.A，B為一棵二叉樹上的兩個結點，在中序遍歷時，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)個結點的完全二叉樹中，結點i(2i>n)的左孩子結點是（D）。 A.2i B.2i+1 C.2i-1 D.不存在 13.把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是（A）。 A.唯一的 B.有多種 C.有多種，但根結點都沒有左孩子 D.有多種，但根結點都沒有右孩子 14.將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點編號，根結點的編號為1，則編號為45的結點的左孩子編號為（B）。 A.46 B.47 C.90 D.91 15.將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點編號，根結點的編號為1，則編號為49的結點的右孩子編號為（B）。 A.98 B.99 C.50 D.100 16.二叉樹按某種順序線索化后，任一結點均有指向其前驅(qū)和后繼的線索，這種說法（B）。 A.正確 B.錯誤 C.不確定 D.都有可能 17.下列陳述正確的是（D）。 A.二叉樹是度為為2的有序樹 B.二叉樹中結點只有一個孩子時無左右之分 C.二叉樹必有度為2的結點 D.二叉樹中最多只有兩棵子樹，且有左右子樹之分 18.用5個權值{3，2，4，5，1}構造的哈夫曼樹的帶權路徑長度是（B）。 A.32 B.33 C.34 D.15 19.在樹結構中，若結點B有4個兄弟，A是B的父親結點，則A的度為（C）。 A.3 B.4 C.5 D.6 20.二叉樹的葉結點個數(shù)比度為2的結點的個數(shù)（C）。 A.無關 B.相等 C.多一個 D.少一個 第8章 圖 一、判斷題 1.圖可以沒有邊，但不能沒有頂點。 （√）2.在無向圖中，(v1，v2)與（v2，v1）是兩條不同的邊。 （×）3.鄰接表只能用于有向圖的存儲。 （×）4.一個圖的鄰接矩陣表示是唯一的。 （√）5.用鄰接矩陣法存儲一個圖時，所占用的存儲空間大小與圖中頂點個數(shù)無關，而只與圖的邊數(shù)有關。（×）6.有向圖不能進行廣度優(yōu)先遍歷。 （×）7.若一個無向圖以頂點v1為起點進行深度優(yōu)先遍歷，所得的遍歷序列唯一，則可以唯一確定該圖。 （√）8.存儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的上三角（或下三角）部分就可以了。 （√）9.用鄰接表法存儲圖時，占用的存儲空間大小只與圖中的邊數(shù)有關，而與結點的個數(shù)無關。 （×）10.若從一個無向圖中任一頂占出發(fā)，進行了一次深度優(yōu)先遍歷，就可以訪問圖中所有的頂點，則該圖一定是連通的。 （√）二、填空題 1.圖常用的存儲方式有鄰接矩陣和 鄰接表 等。 2.圖的遍歷有： 深度優(yōu)先搜 和廣度優(yōu)先搜等方法。 3.有n條邊的無向圖鄰接矩陣中，1的個數(shù)是 2n。 4.有向圖的邊也稱為 弧。 5.圖的鄰接矩陣表示法是表示 頂點 之間相鄰關系的矩陣。 6.有向圖G用鄰接矩陣存儲，其第i行的所有元素之和等于頂點i的 出度。 7.n個頂占e條邊的圖若采用鄰接矩陣存儲，則空間復雜度為： On2。 8.n個頂占e條邊的圖若采用鄰接表存儲，則空間復雜度為： O(n+e)。 9.設有一稀疏圖G，則G采用 鄰接表 存儲比較節(jié)省空間。 10.設有一稠密圖G，則G采用 鄰接矩陣 存儲比較節(jié)省空間。 11.圖的逆鄰接表存儲結構只適用于 有向 圖。 12.n個頂點的完全無向圖有 n(n-1)/2 條邊。 13.有向圖的鄰接矩陣表表示適于求頂點的 出度。 14.有向圖的鄰接矩陣表示中，第i列上非0元素的個數(shù)為頂點vi的 入度。 15.對于具有n個頂點的圖，其生成樹有且僅有 n-1 條邊。 16.對有n個頂點，e條弧的有向圖，其鄰接表表示中，需要 n+e 個結點。 17.從圖中某一頂點出發(fā)，訪遍歷圖中其余頂點，且使每一頂點僅被訪問一次，稱這一過程為圖的 遍歷。 18.無向圖的鄰接矩陣一定是 對稱 矩陣。 19.一個連通網(wǎng)的最小生成樹是該圖所有生成樹中 權 最小的生成樹。 20.若要求一個稠密圖G的最小生成樹，最好用 Prim 算法來求解。 三、選擇題 1.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（C）倍。 A.1/2 B.1 C.2 D.4 2.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（B）倍。 A.1/2 B.1 C.2 D.4 3.對于一個具有n個頂點的有向圖的邊數(shù)最多有（B）。 A.n B.n(n-1)C.n(n-1)/2 D.2n 4.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（C）條邊。 A.n B.n+1 C.n-1 D.n/2 5.有8個結點的有向完全圖有（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.無向圖頂點v的度是關聯(lián)于該頂點B）的數(shù)目。 A.頂點 B.邊 C.序號 D.下標 10.有n個頂點的無向圖的鄰接矩陣是用（B）數(shù)組存儲。 A.一維 B.n行n列 C.任意行n列 D.n行任意列 11.對于一個具有n個頂點和e條邊的無向圖，采用鄰接表表示，則表頭向量大小為（C）。 A.n-1 B.n+1 C.n D.n+e 12.在圖的表示法中，表示形式唯一的是（A）。 A.鄰接矩陣表示法 B.鄰接表表示法 C.逆鄰接表表示法 D.鄰接表和逆鄰接表表示法 13.在一個具有n個頂點e條邊的圖中，所有頂點的度數(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的結點 圖8-24（15）題 圖8-25從頂點a出發(fā) 圖8-26優(yōu)先遍歷 14.圖8-23中，度為3的結點是（B）。 A.V1 B.V2 C.V3 D.V4 15.圖8-24是（A）。 A.連通圖 B.強連通圖 C.生成樹 D.無環(huán)圖 16.如圖8-25所示，從頂點a出發(fā)，按深度優(yōu)先進行遍歷，則可能得到的一種頂點序列為（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所示，從頂點a出發(fā)，按廣度優(yōu)先進行遍歷，則可能得到的一種頂點序列為（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.最小生成樹的構造可使用（A）算法。 A.Prim算法 B.卡爾算法 C.哈夫曼算法 D.迪杰斯特拉算法 19.下面關于圖的存儲結構的敘述中正確的是（A）。 A.用鄰接矩陣存儲圖，占用空間大小只與圖中頂點數(shù)有關，而與邊數(shù)無關 B.用鄰接矩陣存儲圖，占用空間大小只與圖中邊數(shù)有關，而與頂點數(shù)無關 C.用鄰接存儲圖，占用空間大小只與圖中頂點數(shù)有關，而與邊數(shù)無關 D.用鄰接存儲圖，占用空間大小只與圖中邊數(shù)有關，而與頂點數(shù)無關 20.連通分量是（C）的極大連通子圖。 A.樹 B.圖 C.無向圖 D.有向圖 第9章 查找 一、判斷題 1.二分查找法要求待查表的關鍵字值必須有序。 （√）2.對有序表而言采用二分查找總比采用順序查找法速度快。 （×）3.在二叉排序樹中，根結點的值都小于孩子的結點的值。 （×）4.散列存儲法的基本思想是由關鍵字的值的決定數(shù)據(jù)的存儲地址。 （√）5.哈希表是一種將關鍵字轉換為存儲地址的存儲方法。 （√）6.選擇好的哈希函數(shù)就可以避免沖突的發(fā)生。 （×）7.在有序的順序表和有序的鏈表上，均可以采用二分查找來提高查找速度。 （×）8.采用分塊查找，既有實現(xiàn)線性表所希望的查找速度，又能適應動態(tài)變化的需要。 （√）9.哈希查找的效率主要取決于哈希表構造時選取的哈希函數(shù)和處理沖突的方法。 （√）10.在二叉排序樹上刪除一個結點時，不必移動其他結點，只要將該結點的父結點的相應指針域置空即可。 （×）二、填空題 1.順序查找法，表中元素可以 任意 存放。 2.在分塊查找方法中，首先查找 索引，然后再查找相應的塊。 3.順序查找、二分查找、分塊查找都屬于 靜態(tài) 查找。 4.靜態(tài) 查找表所含元素個數(shù)在查找階段是固定不變的。 5.對于長度為n的線性表，若進行順序查找，則時間復雜度為 O(n)。 6.對于長度為n的線性表，若采用二分查找，則時間復雜度為 O(log2n)。 7.理想情況下，在散列表中查找一個元素的時間復雜度為： O(1)。 8.在關鍵字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找關鍵字92，要比較 4 次才找到。 9.設有100個元素，用二分查找法查找時，最大的比較次數(shù)是 7 次。 10.對二叉排序樹進行查找的方法是用待查的值與根結點的鍵值進行比較，若比根結點值小，則繼續(xù)在 左 子樹中查找。 11.二叉排序樹是一種 動態(tài) 查找表。 12.哈希表是按 散列 存儲方式構造的存儲結構。 13.哈希法既是一種存儲方法，又是一種 查找 方法。 14.散列表的查找效率主要取決于散列表造表時選取的散列函數(shù)和處理 沖突 的方法。 15.設散列函數(shù)H和鍵值k1，k2，若k1≠k2 ，而H（k2）H（k2），則稱這種現(xiàn)象為 沖突。 16.處理沖突的兩類主要方法是開放定地址法和 拉鏈法（或鏈地址法）。 17.散列表（或散列） 查找法的平均查找長度與元素個數(shù)n無關。 18.在哈希函數(shù)H（key）= key%P中，P一般應取 質(zhì)數(shù)。 19.在查找過程中有插入元素或刪除元素操作的，稱為 動態(tài) 查找。 20.各結點左、右子樹深度之差的絕對值至多為 1 的二叉樹稱為平衡二叉樹。 三、選擇題 1.查找表以（A）為查找結構。 A.集合 B.圖 C.樹 D.文件 2.順序查找法適合于存儲結構為（B）的線性表。 A.散列存儲 B.順序存儲或鏈接存儲C.壓縮存儲 D.索引存儲 3.在表長為n的鏈表中進行線性查找，它的平均查找長度為（B）。 A.ASL=n B.ASL=(n+1)/2 C.ASL=+1 D.ASL≈log2n 4.對線性表進行二分查找時，要求線性表必須（D）。 A.以順序方式存儲 B.以鏈接方式存儲，且結點按關鍵字有序排序 C.以鏈接方式存儲 D.以順序方式存儲，且結點按關鍵字有序排序 5.衡量查找算法效率的主要標準是（B）。 A.元素個數(shù) B.平均查找長度 C.所需的存儲量 D.算法難易難度 6.如果要求一個線性表既能較快地查找，又能適應動態(tài)變化的要求，可以采用（A）查找方法。 A.分塊 B.順序 C.二分 D.散列 7.鏈表適用于（A）查找。 A.順序 B.二分 C.隨機 D.順序或二分 8.一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當二分查找值為82的結點時，（C）次比較后查找成功。 A.2 B.3 C.4 D.5 9.二分查找有序表{4，6，10，12，20，30，50，70，88，100}，若查找表中元素58，則它將依次與表中（B）比較大小，查找結果是失敗。 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的有序表，按二分查找法對其進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（B）。 A.35/12 B.37/12 C.39/12 D.43/12 12.采用分塊查找時，若線性表共有625個元素，查找生個元素等概率相等，假設采用順序查找來確定結點所在的塊時，每塊分（C）個結點最佳。 A．6 B．10 C．25 D．625 13.下列（C）不是利用查找表中數(shù)據(jù)元素的關系進行查找的方法。 A．平衡二叉樹 B．有序表的查找 C．散列查找 D．二叉排序樹的查找 14.設哈希表長m=14，哈希函數(shù)H(key)=key%11。表中已有4個結點：addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7其余地址為空。如用二次探測再散列處理沖突，關鍵字為49的結點的地址是（D）。 A．8 B．3 C．5 D．9 15.對包含n個元素的散列表進行查找。平均查找長度為（D）。 A．O(n2)B．O(log2n)C．O(n)D．不直接依賴于n 16.沖突指的是（C）。 A．兩個元素具有相同序號 B．兩個元素的鍵值不同 C．不同鍵值對應相同的存儲地址 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}，按照依次插入結點的方法生成一棵二叉排序樹，最后兩層上結點的總數(shù)為（B）。 A．1 B．2 C．3 D．4 19.不可能生成圖9-17所示的二叉排序樹的關鍵字的序列是（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)定，則該排序方法就沒有實用價值。 （×）2.希爾排序是不穩(wěn)定的排序。 （√）3.冒泡排序是不穩(wěn)定的排序。 （×）4.對n個記錄的進行快速排序，所需要的平均時間是O（nlog2n）。 （√）5.堆排序所需的時間與待排序的記錄個數(shù)無關。 （×）6.當待排序的元素個數(shù)很多時，為了交換元素的位置占用較多的時間，這是影響時間復雜度的主要因素。 （√）7.快速排序在任何情況下都比其他排序方法速度快。 （×）8.對快速排序來說，初始序列為正序或反序都是最壞情況。 （√）9.采用歸并排序可以實現(xiàn)外排序。 （√）10.采用希爾排序時，若原始關鍵字的排列雜亂無序，則效率最高。 （√）二、填空題 1.大多數(shù)排序算法都有兩個基本的操作： 比較 和移動。 2.評價排序算法優(yōu)劣的主要標準是 時間復雜度 和算法所需的附加空間。 3.根據(jù)被處理的數(shù)據(jù)在計算機中使用不同的存儲設備，排序可分為 內(nèi)排序 和外排序。 4.外排序是指在排序過程中，數(shù)據(jù)的主要部分存在計算機的 外存 中。 5.對n個關鍵字進行冒泡排序，其可能的最小比較次數(shù)為 n-1 次。 6.在最壞情況下，在第i趟直接插入排序中，要進行 i-1 次關鍵字的比較。 7.對n個關鍵字進行冒泡排序，時間復雜度為 O（n2）。 8.快速排序在最壞情況下的時間復雜度是 O（n2）。 9.對于n個記錄的集合進行歸并排序，所需要的平均時間為 O（nlog2n）。 10.對于n個記錄的集合進行歸并排序，所需要的附加空間為 O(n)。 11.若原始數(shù)據(jù)接近無序，則選用 快速排序 最好。 12.在排序前，關鍵字值相等的不同記錄，排序后相對位置保持 不變 的排序方法，稱為穩(wěn)定排序方法。 13.在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 插入排序較好。 14.當增量為1時，該趟希爾排序與 直接插入 排序基本一致。 15.第一趟排序后，序列中鍵值最大的記錄交換到最后的排序算法是 冒泡 排序。 16.依次將后面文件每個記錄插入到一個前面有序的子文件中的排序方法稱為直接插入 排序。 17.在插入排序、選擇排序和歸并排序中，不穩(wěn)定的排序為： 選擇 排序。 18.在對一組記錄（54，38，96，23，15，72，60，45，93）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較 3 次。 19.兩個序列分別為：L1={25，57，48，37，92，86，12,33} L2 ={25，37，33，12，48，57，86，92} 用冒泡排序法對L1和 L2進行排序，交換次數(shù)較少的是序列： L2。 20.對一組記錄（54，35，96，21，12，72，60，44，80）進行直接選擇排序時，第4次選擇和交換后，未排序記錄是 54，72，60，96，80。 三、選擇題 1.排序是根據(jù)（A）的大小重新安排各元素的順序。 A.關鍵字 B.數(shù)組 C.元素件 D.結點 2.評價排序算法好壞的標準主要是（D）。 A.執(zhí)行時間 B.輔助空間 C.算法本身的復雜度 D.執(zhí)行時間和所需的輔助空間 3.直接插入排序的方法是（B）的排序方法。 A.不穩(wěn)定 B.穩(wěn)定 C.外部 D.選擇 4.直接插入排序的方法要求被排序的數(shù)據(jù)（B）存儲。 A.必須鏈表 B.必須順序 C.順序或鏈表 D.可以任意 5.排序方法中，從無序序列中選擇關鍵字最小的記錄，將其與無序區(qū)（初始為空）的第一個記錄交換的排序方法，稱為（D）。 A.希爾排序 B.歸并排序 C.插入排序 D.選擇排序 6.每次把待排序的數(shù)據(jù)劃分為左、右兩個區(qū)間，其中左區(qū)間中元素的值不大于基準元素的值，右區(qū)間中元素的值不小于基準元素的值，此種排序方法稱為（C）。 A.冒泡排序 B.堆排序 C.快速排序 D.歸并排序 7.快速排序在（C）情況下最易發(fā)揮其長處。 A.待排序的數(shù)據(jù)中含有多個相同的關鍵字B.待排序的數(shù)據(jù)已基本有序 C.待排序的數(shù)據(jù)完全無序 D.待排序的數(shù)據(jù)中最大值與最小值相差懸殊。 8.下述幾種排序方法中，要求內(nèi)存量最大的是（D）。 A.插入排序 B.選擇排序 C.快速排序 D.歸并排序 9.直接插入排序的方法是從第（B）個元素開始，插入前邊適當位置的排序方法。 A.1 B.2 C.3 D.n 10.堆的形狀是一棵（C）。 A.二叉排序樹 B.滿二叉樹 C.完全二叉樹 D.平衡二叉樹 11.內(nèi)排序是指在排序的整個過程中，全部數(shù)據(jù)都在計算機的（A）中完成的排序。 A.內(nèi)存 B.外存 C.內(nèi)存和外存 D.寄存器 12.快速排序的方法是（A）的排序方法。 A.不穩(wěn)定 B.穩(wěn)定 C.外部 D.選擇 13.下列排序方法中，關鍵字比較次數(shù)與記錄的初始排列次序無關的是（A）。 A.選擇排序 B.希爾排序 C.插入排序 D.冒泡排序 14.下述幾種排序方法中，平均時間復雜度最小的是（A）。 A.希爾排序 B.插入排序 C.冒泡排序 D.選擇排序 15.對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是（B）。 A.O(n)B.O(n2)C.O(nlog2n)D.O(n3)16.冒泡排序的方法對n個數(shù)據(jù)進行排序，第一趟排序共需要比較（C）次。 A.1 B.2 C.n-1 D.n 17.對n個不同的排序碼進行冒泡（遞增）排序，在下列（B）情況比較的次數(shù)最多。 A.從小到大排列好的 B.從大到小排列好的C.元素無序 D.元素基本有序 18.用直接插入排序法對下面的4個序列進行由小到大的排序，元素比較次數(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的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為（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ù)序列的關鍵字為（46，79，56，38，40，84），采用快速排序，并以第一個數(shù)為基準得到第一次劃分的結果為（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ì)相同的記錄的集合。放在外存 主關鍵字項：能唯一標識記錄的數(shù)據(jù)項或數(shù)據(jù)項的組合（如學號）文件的操作：檢索和維護 文件的存貯結構：順序、索引、散列、鏈 文件的組織方式：順序文件、索引文件、散列文件、多關鍵字文件 2．順序文件：記錄進入文件的先后順序存放其邏輯順序與物理順序一致的文件。 順序文件的更新方法： 優(yōu)點： 3．索引文件：在主文件之外另外建立一張表：邏輯記錄與物理記錄的對應關系表各主文件一起構成的文件叫索引文件。 4．索引順序文件：索引表按主關鍵字有序，主文件按關鍵字可有序 索引非順序文件索引表按主關鍵字有序，主文件按關鍵字無序 ISAM文件：專為磁盤存取設計的文件組織方式，靜態(tài)索引結構，由多級主索引、柱面索引、磁道索引和主文件組成。 VSAM文件：虛擬存貯存取方法，用B+樹用為動態(tài)索引結構，文件由三部分組成：索引集、順序集、數(shù)據(jù)集 5．散列文件：用散列存貯方式組織的文件，直接存取文件 桶： 6．多關鍵字文件：包含有多個次關鍵字索引的文件 多重表文件：索引方法與鏈接方法相結合的一種組織方式 倒排文件：與多重表不同的是次關鍵字索引的結構不同 三、應用題(本大題共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)寫出從頂點A出發(fā),對該圖進行廣度優(yōu)先搜索遍歷的頂點序列：ABDCE(2)畫出該有向圖的逆鄰接表。 29.依次讀入給定的整數(shù)序列{7，16，4，8，20，9，6，18，5}，完成下列操作： 1)構造一棵二叉排序樹,計算在等概率情況下該二叉排序樹的平均查找長度ASL;2)若變更序列中元素的排列,可構造出平均查找長度達到最小的二叉排序樹。寫出滿足上述要求的序列中的第一個元素。 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.由森林轉換得到的對應二叉樹如圖所示，寫出原森林中第三棵樹 的前序序列和后序序列。 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;為便于刪除和插入圖的頂點的操作，可將鄰接表的表頭向量定義為鏈式結構，兩種定義的存儲表示實例如下圖所示，請寫出重新定義的類型說明。 題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。運用基數(shù)排序?qū)ο铝形锲肪幪栃蛄羞M行按字典序的排序，寫出每一趟（分配和收集）后的結果。 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的有序順序表進行二分查找的判定樹； 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）已知關鍵字序列為（12，14，16，21，24，28，35，43，52，67，71，84，99），寫出在該序列中二分查找37時所需進行的比較次數(shù)。5 29．在棧的輸入端元素的輸入順序為1，2，3，4，5，6，進棧過程中可以退棧，則退棧時能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，寫出進棧、退棧過程，若不能，簡述理由。（用push（x）表示x進棧，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)整方法： 根結點不平衡：根左子樹高>右子樹高+1：根的中序序列8，11，13，14，15，20中根的前一點14上移為根 14 11 15 8 13 20 根左子樹高<右子樹高+1：根的中序序列中根的后一點上移為根 33．用冒泡排序法（快速排序）對數(shù)據(jù)序列（49，38，65，97，76，134，27，49）進行排序，寫出排序過程。并說明冒泡排序是否為穩(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)畫出將關鍵字6插入之后的B-樹； (2)畫出在(1)所得樹中插入關鍵字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）寫出三種以頂點A為起點的深度優(yōu)先搜索頂點序列。 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.假設通信電文使用的字符集為 {a，b，c，d，e，f，g，h} 各字符在電文中出現(xiàn)的頻度分別為：7，26，2，28，13，10，3，11，試為這8個字符設計哈夫曼編碼。要求： (1)畫出你所構造的哈夫曼樹(要求樹中左孩子結點的權值不大于右孩子結點的權值)； (2)按左分支為0和右分支為1的規(guī)則，分別寫出與每個字符對應的編碼。 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.假設以帶頭結點的單鏈表表示線性表,閱讀下列算法f30,并回答問題:(1)設線性表為(a1, a2 , a3, a4 , a 5, a6, a7), 寫出執(zhí)行算法f30后的線性表； (2)簡述算法f30的功能。 void f30(LinkList L){ //L為帶頭結點單鏈表的頭指針 LinkList p,q;P =L;while(p &&p–>next){q = p–>next;//q指向第一個點 p–>next =q–>next;//p的下一個指向第二個點,刪除了第一個點 p =q–>next;//p指向第二個點 free(q);//回收q } }(1)(a2 , a3, a4 , a 5, a6, a7),(2)刪除了鏈表第一個點(不是頭結點)31.算法f31的功能是借助棧結構實現(xiàn)整數(shù)從10進制到8進制的轉換，閱讀算法并回答問題： (1)畫出n為十進制的1348時算法執(zhí)行過程中棧的動態(tài)變化情況;(2)說明算法中while循環(huán)完成的操作。 void f31(int n)//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)當棧不空時出棧輸出n化為8進制數(shù)的序列2504 32.已知以二叉鏈表作二叉樹的存儲結構，閱讀算法f32，并回答問題： (1)設二叉樹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.設有向圖鄰接表定義如下； typedef struct{ VertexNode adjlist[Max VertexNum];int n,e;//圖的當前頂點數(shù)和弧數(shù) } ALGraph;//鄰接表類型 vertex firstedge 其中頂點表結點VertexNode結構為： adjvex next 邊表結點EdegNode結構為： 閱讀下列算法f33，并回答問題： (1)已知有向圖G的鄰接表如圖所示, 寫出算法f33的輸出結果;(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.假設以二叉鏈表表示二叉樹，其類型定義如下： 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.設有向圖鄰接表定義如下： typedef struct { VertexNode adjlist[ MaxVertexNum ];int n，e； ／／圖的當前頂點數(shù)和弧數(shù) }ALGraph； ／／鄰接表類型 其中頂點表結點VertexNode 邊表結點EdgeNode結構為： 閱讀下列算法，并回答問題： (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的功能是對記錄序列進行雙向冒泡排序。算法的基本思想為，先從前往后通過交換將關鍵字最大的記錄移動至后端，然后從后往前通過交換將關鍵字最小的記錄移動至前端，如此反復進行，直至整個序列按關鍵字遞增有序為止。請在空缺處填入合適的內(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ù)結構試卷 （二）一、選擇題(24分)1．下面關于線性表的敘述錯誤的是（）。 (A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間 (B)線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C)線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn) 2．設哈夫曼樹中的葉子結點總數(shù)為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（）個空指針域。 (A)2m-1(B)2m(C)2m+1(D)4m 3．設順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為（）。 (A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。 (A)BADC(B)BCDA(C)CDAB(D)CBDA 5．設某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。 (A)n(n-1)/2(B)n(n-1)(C)n 2(D)n2-1 6．設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（）。 (A)9(B)10(C)11(D)12 7．設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（）個表頭結點。 (A)n-1(B)n(C)n+1(D)2n-1 8．設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進行一趟快速排序的結果為（）。 (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.為了能有效地應用HASH查找技術，必須解決的兩個問題是____________________和__________________________。 2.2.下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。 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.快速排序的最壞時間復雜度為___________，平均時間復雜度為__________。5.5.設某棵二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為N1，則該二叉樹中度數(shù)為2的結點數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有_______個空指針域。 6.6.設某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_______。 7.7.設一組初始記錄關鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。 v1??3??2??4v2??1??3v3??1??4??28.8.設某無向圖G的鄰接表為v4??1??3，則從頂點V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。 三、應用題(36分)1． 1． 設一組初始記錄關鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結果。 2． 2． 設指針變量p指向雙向鏈表中結點A，指針變量q指向被插入結點B，要求給出在結點A的后面插入結點B的操作序列（設雙向鏈表中結點的兩個指針域分別為llink和rlink）。 3． 3． 設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。 4． 4． 設一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。5． 5． 設有無向圖G（如右圖所示），要求給出用普里姆算法構造最小生成樹所走過的邊的集合。 6． 6． 設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹并給出構造過程。 數(shù)據(jù)結構試卷 （二）參考答案 一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二、填空題 1.1.構造一個好的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) 三、應用題 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.樹的鏈式存儲結構略，二叉樹略 5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略 數(shù)據(jù)結構試卷 （三）一、選擇題(30分)1．設某數(shù)據(jù)結構的二元組形式表示為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ù)結構A是（）。 (A)線性結構(B)樹型結構(C)物理結構(D)圖型結構 2．下面程序的時間復雜為（） 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．設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點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．設有n個待排序的記錄關鍵字，則在堆排序中需要（）個輔助記錄單元。 (A)1(B)n(C)nlog2n(D)n2 5．設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結束后的結果為()。(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．設二叉排序樹中有n個結點，則在二叉排序樹的平均平均查找長度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數(shù)分別為（）。 (A)n，e(B)e，n(C)2n，e(D)n，2e 8.設某強連通圖中有n個頂點，則該強連通圖中至少有（）條邊。 (A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（）方法可以達到此目的。 (A)快速排序(B)堆排序(C)歸并排序(D)插入排序 10.下列四種排序中（）的空間復雜度最大。 (A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序 二、填空殖(48分，其中最后兩小題各6分)1.1.數(shù)據(jù)的物理結構主要包括_____________和______________兩種情況。 2.2.設一棵完全二叉樹中有500個結點，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有___________個空指針域。 3.3.設輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。 4.4.設有向圖G用鄰接矩陣A[n][n]作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點i的________。 5.5.設哈夫曼樹中共有n個結點，則該哈夫曼樹中有________個度數(shù)為1的結點。6.6.設有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關系為_________。 7.7.__________遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列（填先序、中序或后序）。 8.8.設查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。 9.9.不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為____________。 10.10.設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為____________，右孩子結點的編號為___________。11.11.設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為___________________________。 12.12.設有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為____________________。 13.13.下列算法實現(xiàn)在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。 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.下列算法實現(xiàn)在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。 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ù)結構試卷 （三）參考答案 一、選擇題 1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值復制到結點A中，最后刪除結點B。 第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。 二、填空題 1.1.順序存儲結構、鏈式存儲結構 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小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。 } 數(shù)據(jù)結構試卷 （四）一、選擇題(30分)1．設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設一棵二叉樹的深度為k，則該二叉樹中最多有（）個結點。 (A)2k-1(B)2k(C)2k-1(D)2k-1 3．設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。 (A)n(B)e(C)2n(D)2e 4．在二叉排序樹中插入一個結點的時間復雜度為（）。 (A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（）條有向邊。 (A)n(B)n-1(C)m(D)m-1 6．設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（）趟的分配和回收才能使得初始關鍵字序列變成有序序列。 (A)3(B)4(C)5(D)8 7．設用鏈表作為棧的存儲結構則退棧操作（）。 (A)必須判別棧是否為滿(B)必須判別棧是否為空 (C)判別棧元素的類型(D)對棧不作任何判別 8．下列四種排序中（）的空間復雜度最大。 (A)快速排序(B)冒泡排序(C)希爾排序(D)堆 9．設某二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，度數(shù)為2的結點數(shù)為N2，則下列等式成立的是（）。 (A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。 (A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1) 二、填空題(42分)1． 1． 設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為________，快速排序的平均時間復雜度為_________。 2． 2． 設指針變量p指向雙向循環(huán)鏈表中的結點X，則刪除結點X需要執(zhí)行的語句序列為_________________________________________________________（設結點中的兩個指針域分別為llink和rlink）。3． 3． 根據(jù)初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4． 4． 深度為k的完全二叉樹中最少有____________個結點。5． 5． 設初始記錄關鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。 6． 6． 設哈夫曼樹中共有99個結點，則該樹中有_________個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有_____個空指針域。 7． 7． 設有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。 8． 8． 設順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_______個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_______個元素。9． 9． 設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結果為______________________________。 10．10．設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關鍵字序列建成的初始堆為________________________。 11．11．設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是______________________。 12．12．設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_________第i列上非0元素的個數(shù)（填等于，大于或小于）。 13．13．設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。 14．14．設散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志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ù)結構試卷 （四）參考答案 一、選擇題 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ù)結構試卷 （五）一、選擇題(30分) 1．數(shù)據(jù)的最小單位是（）。 (A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量 2．設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（）。 (A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（）。 (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．設一個有序的單鏈表中有n個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（）。 (A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設一棵m叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，……，度數(shù)為m的結點數(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．設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。 (A)25(B)10(C)7(D)1 8．設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（）。 (A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。 (A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（）。 (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.設有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。 2.2.在圖的鄰接表中用順序存儲結構存儲表頭結點的優(yōu)點是____________________。 3.3.設有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_______個數(shù)據(jù)元素。 4.4.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。 5.5.設一棵完全二叉樹的順序存儲結構中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。 6.6.設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為________，有__________個葉子結點。 7.7.設有向圖G的存儲結構用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的________，第i列中所有非零元素個數(shù)之和等于頂點i的__________。 8.8.設一組初始記錄關鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。 9.9.下面程序段的功能是實現(xià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.下面程序段的功能是實現(xià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);} 三、應用題(24分) 1.1.設某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2.2.設無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權值之和。 3.3.設一組初始記錄關鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。 4.4.設散列表的長度為8，散列函數(shù)H(k)=k mod 7，初始記錄關鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。 數(shù)據(jù)結構試卷 （五）參考答案 一、選擇題 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.可以隨機訪問到任一個頂點的簡單鏈表 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 三、應用題 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ù)結構試卷 （六）一、選擇題(30分)1． 設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為（）。 (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．設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。 (A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序 5．設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。 (A)空或只有一個結點(B)高度等于其結點數(shù) (C)任一結點無左孩子(D)任一結點無右孩子 6．一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（）。 (A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序 7．設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（）。 (A)3(B)4(C)5(D)6 8．順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（）。 21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時間復雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結點。 (A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向?qū)⒁腙犃械慕Y點X，則入隊列的操作序列為（）。 (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.設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。 (A)99(B)100(C)101(D)102 14.設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（）。 (A)第i行非0元素的個數(shù)之和(B)第i列非0元素的個數(shù)之和 (C)第i行0元素的個數(shù)之和(D)第i列0元素的個數(shù)之和 二、判斷題(20分)1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（） 2．分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（）3．冒泡排序在初始關鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（） 5．設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個有序的序列。（） 7．設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結構比鏈式存儲結構更好。（） 9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（） 三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復雜度為_________。 2．設指針變量p指向單鏈表中結點A，指針變量s指向被插入的新結點X，則進行插入操作的語句序列為__________________________（設結點的指針域為next）。3．設有向圖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>}，則給出該圖的一種拓撲排序序列__________。4．設無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_________。5．設二叉樹中度數(shù)為0的結點數(shù)為50，度數(shù)為1的結點數(shù)為30，則該二叉樹中總共有_______個結點數(shù)。 6．設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。 7．設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是_____________________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復雜度為___________。 9．快速排序算法的空間復雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。 數(shù)據(jù)結構試卷 （六）參考答案 一、選擇題 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ù)結構試卷 （七）一、選擇題(30分)1．設某無向圖有n個頂點，則該無向圖的鄰接表中有（）個表頭結點。 (A)2n(B)n(C)n/2(D)n(n-1)2．設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。 (A)n(B)n-1(C)2n(D)2n-1 3．設一組初始記錄關鍵字序列為(60，80，55，40，42，85)，則以第一個關鍵字45為基準而得到的一趟快速排序結果是（）。 (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．設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（）。 (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)；的時間復雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設帶有頭結點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。 (A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（）。 (A)20(B)256(C)512(D)1024 9．設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數(shù)為（）。 (A)1(B)2(C)3(D)4 10.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。 (A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next; 三、填空題(30分)1.1.設指針變量p指向雙向鏈表中的結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設結點中的兩個指針域分別為left和right）。2.2.設完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。 3.3.設關鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進行篩選。 4.4.解決散列表沖突的兩種方法是________________和__________________。 5.5.設一棵三叉樹中有50個度數(shù)為0的結點，21個度數(shù)為2的結點，則該二叉樹中度數(shù)為3的結點數(shù)有______個。 6.6.高度為h的完全二叉樹中最少有________個結點，最多有________個結點。7.7.設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結束后的結果的是__________________________________。 8.8.設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結束后的結果的是__________________________________。 9.9.設一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。 10.10.下面程序段的功能是實現(xià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ù)結構試卷 （七）一、選擇題 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ù)結構試卷 （八）一、選擇題(30分)1.1.字符串的長度是指（）。 (A)串中不同字符的個數(shù)(B)串中不同字母的個數(shù) (C)串中所含字符的個數(shù)(D)串中不同數(shù)字的個數(shù) 2.2.建立一個長度為n的有序單鏈表的時間復雜度為（） (A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個字符串相等的充要條件是（）。 (A)兩個字符串的長度相等(B)兩個字符串中對應位置上的字符相等 (C)同時具備(A)和(B)兩個條件(D)以上答案都不對 4.4.設某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（）。 (A)99(B)97(C)91(D)93 5.5.在二叉排序樹中插入一個關鍵字值的平均時間復雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.設一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。 (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.設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（）。 (A)8(B)7(C)6(D)5 8.8.設一棵三叉樹中有2個度數(shù)為1的結點，2個度數(shù)為2的結點，2個度數(shù)為3的結點，則該三叉鏈權中有（）個度數(shù)為0的結點。 (A)5(B)6(C)7(D)8 9.9.設無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為（）。 (A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.隊列是一種（）的線性表。 (A)先進先出(B)先進后出(C)只能插入(D)只能刪除 三、填空題(30分)1． 1． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結束后的結果為_____________________________。 2． 2． 下面程序段的功能是實現(xià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． 設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X需要執(zhí)行的語句序列：s->next=p->next;_________________。4． 4． 設指針變量head指向雙向鏈表中的頭結點，指針變量p指向雙向鏈表中的第一個結點，則指針變量p和指針變量head之間的關系是p=_________和head=__________（設結點中的兩個指針域分別為llink和rlink）。 5． 5． 設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。 6． 6． 完全二叉樹中第5層上最少有__________個結點，最多有_________個結點。7． 7． 設有向圖中不存在有向邊 8． 8． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結束后的結果為_____________________________。 9． 9． 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有___________條邊。10． 10． 設有一組初始記錄關鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。 數(shù)據(jù)結構試卷 （八）參考答案 一、選擇題 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.填空題 ⑴ 設無向圖G中頂點數(shù)為n，則圖G至少有（）條邊，至多有（）條邊；若G為有向圖，則至少有（）條邊，至多有（）條邊。【解答】0，n(n-1)/2，0，n(n-1)【分析】圖的頂點集合是有窮非空的，而邊集可以是空集；邊數(shù)達到最多的圖稱為完全圖，在完全圖中，任意兩個頂點之間都存在邊。 ⑵ 任何連通圖的連通分量只有一個，即是（）。【解答】其自身 ⑶ 圖的存儲結構主要有兩種，分別是（）和（）。【解答】鄰接矩陣，鄰接表 【分析】這是最常用的兩種存儲結構，此外，還有十字鏈表、鄰接多重表、邊集數(shù)組等。⑷ 已知無向圖G的頂點數(shù)為n，邊數(shù)為e，其鄰接表表示的空間復雜度為（）。【解答】Ｏ(n+e)【分析】在無向圖的鄰接表中，頂點表有n個結點，邊表有2e個結點，共有n+2e個結點，其空間復雜度為Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一個有向圖的鄰接矩陣表示，計算第j個頂點的入度的方法是（）。【解答】求第j列的所有元素之和 ⑹ 有向圖G用鄰接矩陣A[n][n]存儲，其第i行的所有元素之和等于頂點i的（）。【解答】出度 ⑺ 圖的深度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結構是（）；圖的廣度優(yōu)先遍歷類似于樹的（）遍歷，它所用到的數(shù)據(jù)結構是（）。【解答】前序，棧，層序，隊列 ⑻ 對于含有n個頂點e條邊的連通圖，利用Prim算法求最小生成樹的時間復雜度為（），利用Kruskal算法求最小生成樹的時間復雜度為（）。【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用鄰接矩陣做存儲結構，適合于求稠密圖的最小生成樹；Kruskal算法采用邊集數(shù)組做存儲結構，適合于求稀疏圖的最小生成樹。 ⑼ 如果一個有向圖不存在（），則該圖的全部頂點可以排列成一個拓撲序列。【解答】回路 ⑽ 在一個有向圖中，若存在弧、、，則在其拓撲序列中，頂點vi, vj, vk的相對次序為（）。【解答】vi, vj, vk 【分析】對由頂點vi, vj, vk組成的圖進行拓撲排序。 2.選擇題 ⑴ 在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。A 1/2 B 1 C 2 D 4 【解答】C 【分析】設無向圖中含有n個頂點e條邊，則。 ⑵ n個頂點的強連通圖至少有（）條邊，其形狀是（）。A n B n+1 C n-1 D n×(n-1)E 無回路 F 有回路 G 環(huán)狀 H 樹狀 【解答】A，G ⑶ 含n 個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（）。A 1 B n/2 C n-1 D n 【解答】C 【分析】若超過n-1，則路徑中必存在重復的頂點。 ⑷ 對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是（）。A n B(n-1)2 C n-1 D n2 【解答】D ⑸ 圖的生成樹（），n個頂點的生成樹有（）條邊。A 唯一 B 不唯一 C 唯一性不能確定 D n E n +1 F n-1 【解答】C，F(xiàn) ⑹ 設無向圖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）。 【分析】連通分量是無向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點的所有邊都加上，所以，連通分量中可能存在回路。 ⑺ G是一個非連通無向圖，共有28條邊，則該圖至少有（）個頂點。A 6 B 7 C 8 D 9 【解答】D 【分析】n個頂點的無向圖中，邊數(shù)e≤n(n-1)/2，將e=28代入，有n≥8，現(xiàn)已知無向圖非連通，則n=9。 ⑻ 最小生成樹指的是（）。A 由連通網(wǎng)所得到的邊數(shù)最少的生成樹 B 由連通網(wǎng)所得到的頂點數(shù)相對較少的生成樹 C 連通網(wǎng)中所有生成樹中權值之和為最小的生成樹 D 連通網(wǎng)的極小連通子圖 【解答】C ⑼ 判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以用（）。A 求關鍵路徑的方法 B 求最短路徑的方法 C 廣度優(yōu)先遍歷算法 D 深度優(yōu)先遍歷算法 【解答】D 【分析】當有向圖中無回路時，從某頂點出發(fā)進行深度優(yōu)先遍歷時，出棧的順序（退出DFSTraverse算法）即為逆向的拓撲序列。 ⑽ 下面關于工程計劃的AOE網(wǎng)的敘述中，不正確的是（）?br /> A 關鍵活動不按期完成就會影響整個工程的完成時間 B 任何一個關鍵活動提前完成，那么整個工程將會提前完成 C 所有的關鍵活動都提前完成，那么整個工程將會提前完成 D 某些關鍵活動若提前完成，那么整個工程將會提前完 【解答】B 【分析】AOE網(wǎng)中的關鍵路徑可能不止一條，如果某一個關鍵活動提前完成，還不能提前整個工程，而必須同時提高在幾條關鍵路徑上的關鍵活動。 3.判斷題 ⑴ 一個有向圖的鄰接表和逆鄰接表中的結點個數(shù)一定相等。 【解答】對。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結點個數(shù)都等于有向圖中邊的個數(shù)。 ⑵ 用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數(shù)有關，而與圖的邊數(shù)無關。【解答】對。鄰接矩陣的空間復雜度為Ｏ(n2)，與邊的個數(shù)無關。 ⑶ 圖G的生成樹是該圖的一個極小連通子圖 【解答】錯。必須包含全部頂點。 ⑷ 無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的 【解答】錯。有向圖的鄰接矩陣不一定對稱，例如有向完全圖的鄰接矩陣就是對稱的。 ⑸ 對任意一個圖，從某頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問圖的所有頂點。【解答】錯。只有連通圖從某頂點出發(fā)進行一次遍歷，可訪問圖的所有頂點。 ⑹ 在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧。【解答】錯。只能說明從頂點a到頂點b有一條路徑。 ⑺ 若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲序列必定存在。【解答】對。參見第11題的證明。 ⑻ 在AOE網(wǎng)中一定只有一條關鍵路徑?br />【解答】錯。AOE網(wǎng)中可能有不止一條關鍵路徑，他們的路徑長度相同 4．n個頂點的無向圖，采用鄰接表存儲，回答下列問題?br />⑴ 圖中有多少條邊？ ⑵ 任意兩個頂點i和j是否有邊相連？ ⑶ 任意一個頂點的度是多少?br /> 【解答】 ⑴ 邊表中的結點個數(shù)之和除以2。⑵ 第i個邊表中是否含有結點j。⑶ 該頂點所對應的邊表中所含結點個數(shù)。 5．n個頂點的無向圖，采用鄰接矩陣存儲，回答下列問題： ⑴ 圖中有多少條邊？ ⑵ 任意兩個頂點i和j是否有邊相連？ ⑶ 任意一個頂點的度是多少？ 【解答】 ⑴ 鄰接矩陣中非零元素個數(shù)的總和除以2。 ⑵ 當鄰接矩陣A中A[i][j]=1（或A[j][i]=1）時，表示兩頂點之間有邊相連。⑶ 計算鄰接矩陣上該頂點對應的行上非零元素的個數(shù)。 6．證明：生成樹中最長路徑的起點和終點的度均為１。【解答】用反證法證明。 設v1, v2, …, vk是生成樹的一條最長路徑，其中，v1為起點，vk為終點。若vk的度為2，取vk的另一個鄰接點v，由于生成樹中無回路，所以，v在最長路徑上，顯然 v1, v2, …, vk , v的路徑最長，與假設矛盾。所以生成樹中最長路徑的終點的度為1。同理可證起點v1的度不能大于1，只能為1。 7．已知一個連通圖如圖6-6所示，試給出圖的鄰接矩陣和鄰接表存儲示意圖，若從頂點v1出發(fā)對該圖進行遍歷，分別給出一個按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列。 【解答】鄰接矩陣表示如下： 深度優(yōu)先遍歷序列為：v1 v2 v3 v5 v4 v6 廣度優(yōu)先遍歷序列為：v1 v2 v4 v6 v3 v5 鄰接表表示如下： 8．圖6-7所示是一個無向帶權圖，請分別按Prim算法和Kruskal算法求最小生成樹。 【解答】按Prim算法求最小生成樹的過程如下： 按Kruskal算法求最小生成樹的過程如下： 9．對于圖6-8所示的帶權有向圖，求從源點v1到其他各頂點的最短路徑。 【解答】從源點v1到其他各頂點的最短路徑如下表所示。 源點 終點 最短路徑 最短路徑長度 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算法求從頂點v1到其他各頂點的最短路徑。 【解答】從源點v1到其他各頂點的最短路徑如下表所示。 源點 終點 最短路徑 最短路徑長度 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．證明：只要適當?shù)嘏帕许旤c的次序，就能使有向無環(huán)圖的鄰接矩陣中主對角線以下的元素全部為0。【解答】任意n個結點的有向無環(huán)圖都可以得到一個拓撲序列。設拓撲序列為v0v1v2…vn-1，我們來證明此時的鄰接矩陣A為上三角矩陣。證明采用反證法。 假設此時的鄰接矩陣不是上三角矩陣，那么，存在下標i和j（i>j），使得A[i][j]不等于零，即圖中存在從 vi到vj的一條有向邊。由拓撲序 列的定義可知，在任意拓撲序列中，vi的位置一定在vj之前，而在上述拓撲序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，導 致矛盾。因此命題正確。 12.算法設計 ⑴ 設計算法，將一個無向圖的鄰接矩陣轉換為鄰接表。 【解答】先設置一個空的鄰接表，然后在鄰接矩陣上查找值不為零的元素，找到后在鄰接表的對應單鏈表中插入相應的邊表結點。 鄰接矩陣存儲結構定義如下： const int MaxSize=10;template struct AdjMatrix { T vertex[MaxSize];//存放圖中頂點的數(shù)組 int arc[MaxSize][MaxSize];//存放圖中邊的數(shù)組 int vertexNum, arcNum;//圖的頂點數(shù)和邊數(shù) };鄰接表存儲結構定義如下： const int MaxSize=10;struct ArcNode //定義邊表結點 { int adjvex;//鄰接點域 ArcNode *next;};template struct VertexNode //定義頂點表結點 { T vertex;ArcNode *firstedge;};struct AdjList { VertexNode adjlist[MaxSize];int vertexNum, arcNum;//圖的頂點數(shù)和邊數(shù) };具體算法如下： ⑵ 設計算法，將一個無向圖的鄰接表轉換成鄰接矩陣。 【解答】在鄰接表上順序地取每個邊表中的結點，將鄰接矩陣中對應單元的值置為1。鄰接矩陣和鄰接表的存儲結構定義與上題相同。具體算法如下： ⑶ 設計算法，計算圖中出度為零的頂點個數(shù)。 【解答】在有向圖的鄰接矩陣中，一行對應一個頂點，每行的非零元素的個數(shù)等于對應頂點的出度。因此，當某行非零元素的個數(shù)為零時，則對應頂點的出度為零。據(jù)此，從第一行開始，查找每行的非零元素個數(shù)是否為零，若是則計數(shù)器加1。具體算法如下： ⑷ 以鄰接表作存儲結構，設計按深度優(yōu)先遍歷圖的非遞歸算法。【解答】參見6.2.1。 ⑸ 已知一個有向圖的鄰接表，編寫算法建立其逆鄰接表。 【解答】在有向圖中，若鄰接表中頂點vi有鄰接點vj，在逆鄰接表中vj一定有鄰接點vi，由此得到本題算法思路：首先將逆鄰接表的表頭結點firstedge域置空，然后逐行將表頭結點的鄰接點進行轉化。 ⑹ 分別基于深度優(yōu)先搜索和廣度優(yōu)先搜索編寫算法，判斷以鄰接表存儲的有向圖中是否存在由頂點vi到頂點vj的路徑（i≠j）。 【解答】⑴ 基于深度優(yōu)先遍歷： ⑵ 基于廣度優(yōu)先遍歷： 學習自測及答案 1．某無向圖的鄰接矩陣A=，可以看出，該圖共有（A 3 B 6 C 9 D 以上答案均不正確 【解答】A 2．無向圖的鄰接矩陣是一個（），有向圖的鄰接矩陣是一個（）A 上三角矩陣 B 下三角矩陣 C 對稱矩陣 D 無規(guī)律 【解答】C，D 3．下列命題正確的是（）。 A 一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一）個頂點。 B 一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一 C 一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一 D 一個圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一 【解答】B 4．十字鏈表適合存儲（），鄰接多重表適合存儲（）。【解答】有向圖，無向圖 5.在一個具有n 個頂點的有向完全圖中包含有（）條邊： A n(n-1)/2 B n(n-1)C n(n+1)/2 D n2 【解答】B 6．n個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有（）個非零元素。【解答】2(n-1)7．表示一個有100個頂點，1000條邊的有向圖的鄰接矩陣有（）個非零矩陣元素。【解答】1000 8．一個具有n個頂點k條邊的無向圖是一個森林（n>k），則該森林中必有（）棵樹。 A k B n C n-k D 1 【解答】C 9．用深度優(yōu)先遍歷方法遍歷一個有向無環(huán)圖，并在深度優(yōu)先遍歷算法中按退棧次序打印出相應的頂點，則輸出的頂點序列是（）。 A 逆拓撲有序 B 拓撲有序 C 無序 D 深度優(yōu)先遍歷序列 【解答】A 10.關鍵路徑是AOE網(wǎng)中（）。 A 從源點到終點的最長路徑 B從源點到終點的最長路徑 C 最長的回路 D 最短的回路 【解答】A 11.已知無向圖G的鄰接表如圖6-10所示，分別寫出從頂點1出發(fā)的深度遍歷和廣度遍歷序列，并畫出相應的生成樹。 【解答】深度優(yōu)先遍歷序列為：1，2，3，4，5，6 對應的生成樹為： 廣度優(yōu)先遍歷序列為：1，2，4，3，5，6 對應的生成樹為： 12.已知已個AOV網(wǎng)如圖6-11所示，寫出所有拓撲序列。 【解答】拓撲序列為：v0 v1 v5 v2 v3 v6 v4、v0 v1 v5 v2 v6 v3 v4、v0 v1 v5 v6 v2 v3 v4。 《數(shù)據(jù)結構》 2n10．散列函數(shù)越復雜越好，因為這樣隨機性好，沖突概率小.× 11．Hash表的平均查找長度與處理沖突的方法無關。× 12．負載因子(裝填因子)是散列表的一個重要參數(shù)，它反映散列表的裝滿程度。√ 13.若散列表的負載因子α<1，則可避免碰撞的產(chǎn)生。× 三、填空題 1.順序查找n個元素的順序表，若查找成功，則比較關鍵字的次數(shù)最多為__（1）n __次。2.在有序表A[1..20]中，按二分查找方法進行查找，查找長度為5的元素個數(shù)是__（2）5 __。 3.在有序表A[1?20]中，按二分查找方法進行查找，查找長度為4的元素的下標從小到大依次是____（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個記錄的有序順序表中進行折半查找，最大比較次數(shù)是___（6）log2n+1__。（取下界） 6.平衡因子的定義是___（7）結點的左子樹的高度減去結點的右子樹的高度___ 7.高度為8的平衡二叉樹的結點數(shù)至少有___（8）54__個。（參照教材P238：N0=0,N1=1,N2=2,公式Nh=Nh-1+Nh-2+1） 8.動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有___（9）插入 _和__（10）_刪除__運算，而后者不包含這兩種運算。 四、應用題 1.假定對有序表：(3,4,5,7,24,30,42,54,63,72,87,95)進行折半查找，試回答下列問題： (1).畫出描述折半查找過程的判定樹； (2).若查找元素54，需依次與那些元素比較?(3).若查找元素90，需依次與那些元素比較?(4).假定每個元素的查找概率相等，求查找成功時的平均查找長度。 2.一棵二叉排序樹結構如下,各結點的值從小到大依次為1-9，請標出各結點的值。 3.依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序樹【華中理工大學 2000 五（10分）】 (1)試畫出生成之后的二叉排序樹;(2)對該二叉排序樹作中序遍歷，試寫出遍歷序列;(3)假定每個元素的查找概率相等，試計算該二叉排序樹的平均查找長度。 4.設哈希函數(shù)H（k）=3 K mod 11，散列地址空間為0～10，對關鍵字序列（32,13,49,24,38,21,4,12）按下述兩種解決沖突的方法構造哈希表（1）線性探測再散列（2）鏈地址法，并分別求出等概率下查找成功時的平均查找長度； 、數(shù)據(jù)結構復習題及答案 中南大學現(xiàn)代遠程教育課程考試（專科）復習題及參考答案 數(shù)據(jù)結構 一、判斷題： 1． 數(shù)組是一種復雜的數(shù)據(jù)結構，數(shù)組元素之間的關系既不是線性的也不是樹形的。（）2． 鏈式存儲在插人和刪除時需要保持物理存儲空間的順序分配，不需要保持數(shù)據(jù)元素之間的邏輯順序。 （） 3． 在只有度為0和度為k的結點的k叉樹中，設度為0的結點有n0個，度為k的結點有nk個，則有n0=nk+1。（）4． 折半搜索只適用于有序表，包括有序的順序表和有序的鏈表。（）5． 如果兩個串含有相同的字符，則這兩個串相等。 （） 6． 數(shù)組可以看成線性結構的一種推廣，因此可以對它進行插入、刪除等運算。（）7． 在用循環(huán)單鏈表表示的鏈式隊列中，可以不設隊頭指針，僅在鏈尾設置隊尾指針。（）8． 通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高。 （）9． 一個廣義表的表尾總是一個廣義表。 （）10． 當從一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。 （） 11． 對于一棵具有n個結點，其高度為h的二叉樹，進行任一種次序遍歷的時間復雜度為O（h）。 （） 12． 存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關，而且與圖的邊數(shù)也有關。 （） 13． 直接選擇排序是一種穩(wěn)定的排序方法。 （）14． 閉散列法通常比開散列法時間效率更高。 （）15． 有n個結點的不同的二叉樹有n!棵。（）16． 直接選擇排序是一種不穩(wěn)定的排序方法。（）17． 在2048個互不相同的關鍵碼中選擇最小的5個關鍵碼，用堆排序比用錦標賽排序更快。（）18． 當3階B_樹中有255個關鍵碼時,其最大高度(包括失敗結點層)不超過8。（）19． 一棵3階B_樹是平衡的3路搜索樹,反之,一棵平衡的3路搜索樹是3階非B_樹。（）20． 在用散列表存儲關鍵碼集合時，可以用雙散列法尋找下一個空桶。在設計再散列函數(shù)時，要求計算出的值與表的大小m互質(zhì)。（）21． 在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關，而且與每一塊中元素個數(shù)有關。（） 22． 在順序表中取出第i個元素所花費的時間與i成正比。 （）23． 在棧滿情況下不能作進棧運算，否則產(chǎn)生“上溢”。 ()24． 二路歸并排序的核心操作是將兩個有序序列歸并為一個有序序列。（）25． 對任意一個圖，從它的某個頂點出 發(fā)，進行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點.（）26． 二叉排序樹或者是一棵空二叉樹，或者不是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結點的值大于其左孩子的值;若它的右子樹非空，則根結點的值小于其右孩子的值。（）27． 在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（） 28． 一個有向圖的鄰接表和逆鄰接表中表結點的個數(shù)一定相等。（） 二、選擇題： 1． 在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為（）。A.O(n) B.O(n／2) C.O(1) D.O(n2)2． 帶頭結點的單鏈表first為空的判定條件是：（）A.first==NULL B.first一>1ink＝＝NULL C.first一>link==first D.first!＝NUlL 3． 當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（）。 A.n-2 B.n-l C.n D.n+1 4． 在系統(tǒng)實現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存實際參數(shù)的值。在傳值參數(shù)情形，需為對應形式參數(shù)分配空間，以存放實際參數(shù)的副本；在引用參數(shù)情形，需保存實際參數(shù)的（），在被調(diào)用程序中可直接操縱實際參數(shù)。 A.空間 B.副本 C.返回地址 D.地址 5． 在一棵樹中，（）沒有前驅(qū)結點。A.分支結點 D.葉結點 C.樹根結點 D.空結點 6． 在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（）。 A.2 B.1 C.0 D.-1 7． 對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（）的值除以9。A.20 B.18 C.25 D.22 8． 在有向圖中每個頂點的度等于該頂點的（）。A.入度 B.出度 C.入度與出度之和 D.入度與出度之差 9． 在基于排序碼比較的排序算法中，（）算法的最壞情況下的時間復雜度不高于O(n10g2n)。A.起泡排序 B.希爾排序 C.歸并排序 D.快速排序 10． 當α的值較小時，散列存儲通常比其他存儲方式具有（）的查找速度。A.較慢 B.較快 C.相同 D.不清楚 11． 設有一個含200個表項的散列表，用線性探查法解決沖突，按關鍵碼查詢時找到一個表項的平均探查次數(shù)不超過1.5，則散列表項應能夠至少容納（）個表項。(設搜索成功的平均搜索長度為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ù)結構形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上() A.操作的有限集合B.映象的有限集合 C.類型的有限集合D.關系的有限集合 14． 在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為() A.n-i+1 B.i C.i+1 D.n-i 15． 若不帶頭結點的單鏈表的頭指針為head，則該鏈表為空的判定條件是() A.head==NULL B.head->next==NULL C.head!=NULL D.head->next==head 16． 引起循環(huán)隊列隊頭位置發(fā)生變化的操作是() A.出隊 B.入隊 C.取隊頭元素 D.取隊尾元素 17． 若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現(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.索引存儲和鏈式存儲 C.順序存儲和鏈式存儲 D.散列存儲和順序存儲 19． 設主串長為n，模式串長為m(m≤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))的結果是() A.(e,f) B.((e,f)) C.(f) D.()22． 下列圖示的順序存儲結構表示的二叉樹是() 23． n個頂點的強連通圖中至少含有()A.n-1條有向邊 B.n條有向邊 C.n(n-1)/2條有向邊 D.n(n-1)條有向邊 24． 對關鍵字序列(56，23，78，92，88，67，19，34)進行增量為3的一趟希爾排序的結果為() 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-樹中插入關鍵字引起結點分裂，則該結點在插入前含有的關鍵字個數(shù)為() A.4 B.5 C.8 D.9 26． 由同一關鍵字集合構造的各棵二叉排序樹() A.其形態(tài)不一定相同，但平均查找長度相同 B.其形態(tài)不一定相同，平均查找長度也不一定相同 C.其形態(tài)均相同，但平均查找長度不一定相同 D.其形態(tài)均相同，平均查找長度也都相同 27． ISAM文件和VSAM文件的區(qū)別之一是() A.前者是索引順序文件，后者是索引非順序文件 B.前者只能進行順序存取，后者只能進行隨機存取 C.前者建立靜態(tài)索引結構，后者建立動態(tài)索引結構 D.前者的存儲介質(zhì)是磁盤，后者的存儲介質(zhì)不是磁盤 28． 下列描述中正確的是（） A． 線性表的邏輯順序與存儲順序總是一致的 B． 每種數(shù)據(jù)結構都具備三個基本運算：插入、刪除和查找 C． 數(shù)據(jù)結構實質(zhì)上包括邏輯結構和存儲結構兩方面的內(nèi)容 D． 選擇合適的數(shù)據(jù)結構是解決應用問題的關鍵步驟 29． 下面程序段的時間復雜度是（） i=s=0 while(s {i++; s+=i; } A．O(1)B.O(n)C.O(log2n)D.O(n2)30． 對于順序表來說，訪問任一節(jié)點的時間復雜度是（） A．O(1)B.O(n)C.O(log2n)D.O(n2)31． 在具有n個節(jié)點的雙鏈表中做插入、刪除運算，平均時間復雜度為（） A．O(1)B.O(n)C.O(log2n)D.O(n2)32． 經(jīng)過下列運算后，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)隊列是空隊列的條件是（） A．Q->rear==Q->front B.(Q->rear+1)%maxsize==Q->front C.Q->rear==0 D.Q->front==0 35． 設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é)點（） 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é)點數(shù)稱為（） A．根 B.葉 C.祖先 D.子孫 41． 已知一個圖如下所示，若從頂點a出發(fā)按寬度搜索法進行遍歷，則可能得到的一種頂 點序列為（） 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． 散列查找是由鍵值______確定散列表中的位置，進行存儲或查找（） A．散列函數(shù)值 B.本身 C.平方 D.相反數(shù) 46． 順序文件的缺點是（） A．不利于修改 B.讀取速度慢 C.只能寫不能讀 D.寫文件慢 47． 索引文件的檢索方式是直接存取或按_____存取（） A．隨機存取 B.關鍵字 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) 三、計算與算法應用題（本大題每小題9分） 1.給定表（119，14，22，1，66，21，83，27，56，13，10） 請按表中元素的順序構造一棵平衡二叉樹，并求其在等概率情況下查找成功的平均長度。（9分）2.已知一個有向圖的頂點集V和邊集G分別為： V={a,b,c,d,e,f,g,h} E={ 3.設散列表的長度為13，散列函數(shù)為H（h）= k%13，給定的關鍵碼序列為19，14，23，01，68，20，84，27。試畫出用線性探查法解決沖突時所構成的散列表。（8分） 0 4.對7個關鍵字進行快速排序，在最好的情況下僅需進行10次關鍵字的比較。 (1)假設關鍵字集合為{1,2,3,4,5,6,7}，試舉出能達到上述結果的初始關鍵字序列； (2)對所舉序列進行快速排序，寫出排序過程。（９分）5.如圖所示二叉樹，回答下列問題。（9分） 6.畫出在一個初始為空的AVL樹中依次插入3,1,4,6,9,8,5,7時每一插入后AVL樹的形態(tài)。若做了某種旋轉，說明旋轉的類型。然后，給出在這棵插入后得到的AVL樹中刪去根結點后的結果。7.已知一組記錄的排序碼為（46，79，56，38，40，80，95，24），寫出對其進行快速排序的每一次劃分結果。 8.一個線性表為 B=（12，23，45，57，20，03，78，31，15，36），設散列表為 HT[0..12]，散列函數(shù)為 H（key）= key % 13 并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。 9.已知一棵二叉樹的前序遍歷的結果序列是 ABECKFGHIJ，中序遍歷的結果是 EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結果。 10.假定對線性表(38，25，74，52，48，65，36)進行散列存儲，采用H(K)=K％9作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對應的平均查找長度分別為 和 。11．假定一組記錄的排序碼 為(46，79，56，38，40，80，25，34，57，21)，則對其進行快速排序的第一次劃分后又對左、右兩個子區(qū)間分別進行一次劃分，得到的結果為：。 12.下圖是帶權的有向圖G的鄰接表表示法。從結點V1出發(fā)，深度遍歷圖G所得結點序列為（A），廣度遍歷圖G所得結點序列為（B）；G的一個拓撲序列是（C）；從結點V1到結點V8的最短路徑為（D）；從結點V1到結點V8的關鍵路徑為（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的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均查找長度。14.已知如圖所示的有向網(wǎng)，試利用Dijkstra算法求頂點1到其余頂點的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。 15.假定用于通信的電文由８個字母a,b,c,d,e,f,g,h組成，各字母在電文中出現(xiàn)的頻率分別為５，２５，３，６，１０，１１，３６，４。試為這８個字母設計不等長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.假設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設計哈夫曼編碼。使用0～7的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。 四、算法設計題 1.已知深度為h的二叉樹以一維數(shù)組BT(1:2h-1)作為其存儲結構。請寫一算法，求該二叉樹中葉結點的個數(shù)。 2.編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結點的非遞歸算法，若查找item帶回整個結點的值并返回ture，否則返回false。bool Find（BtreeNode*BST，ElemType&item） 3.編寫算法，將一個結點類型為 Lnode 的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為 a 1，......a n-1，a n，則逆序鏈接后變?yōu)?, a n，a n-1，......a 1。 4.根據(jù)下面函數(shù)原型，編寫一個遞歸算法，統(tǒng)計并返回以BT為樹根指針的二叉樹中所有 葉子結點的個數(shù)。int Count(BTreeNode * BT)； 5.設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的結點，刪去以它為根的子樹，并釋放相應的空間。 8.編寫算法判別T是否為二叉排序樹.9.試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑（i<>j）。注意：算法中涉及的圖的基本操作必須在存儲結構上實現(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.√ 二、單項選擇題 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 三 計算與算法應用題 １．［解答］ 平均長度為4.2、解：畫圖（略） 深度優(yōu)先搜索序列：a，b，f，h，c，d，g，e 廣度優(yōu)先搜索序列：a，b，c，f，d，e，h，g 3、解：計算機關鍵碼得到的散列地址 關鍵碼 19 14 23 01 68 20 84 27 散列地址 6 10．× 26.B 1 3 7 6 1 在散列表中散列結果 0 01 68 27 19 20 84 23 4.對n個關鍵自序列進行一趟快速排序，要進行n-1次比較，也就是基準和其他n-1個關鍵字比較。 這里要求10次，而71)= 10，這就要求2趟快速排序后，算法結束。所以，列舉出來的序列，要求在做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樹中刪除根結點時有兩種方案: 【方案1】在根的左子樹中沿右鏈走到底,用5遞補根結點中原來的6,再刪除5所在的結點.【方案2】在根的右子樹中沿左鏈走到底,用7遞補根結點中原來的6,再刪除7所在的結點.7.劃分次序 劃分結果第二篇：數(shù)據(jù)結構試題及答案
第三篇：數(shù)據(jù)結構 第六章 圖 練習題及答案詳細解析(精華版)
第四篇：數(shù)據(jù)結構第四教學單元測驗練習題(答案)
第五篇：數(shù)據(jù)結構復習題及答案
點擊咨詢 