緒論判斷題數據的邏輯結構與數據元素本身的內容和形式無關。(√）一個數據結構是由一個邏輯結構和這個邏輯結構上的一個基本運算集構成的整體。（√）數據元素是數據的最小單位。(×）數據的邏輯結構和數據的存儲結構是相同的。（×）程序和算法原則上沒有區別，所以在討論數據結構時可以通用。（×)從邏輯關系上講，數據結構主要分為線性結構和非線性結構兩類。（√）數據的存儲結構是數據的邏輯結構的存儲映象.(√）數據的物理結構是指數據在計算機內實際的存儲形式.（√）數據的邏輯結構是依賴于計算機的。（×）算法是對解題方法和步驟的描述.(√)二、填空題數據有邏輯結構和存儲結構兩種結構。數據邏輯結構除了集合以外,還包括線性結構、樹形結構和圖形結構。數據結構按邏輯結構可分為兩大類，它們是線性結構和非線性結構。樹形結構和圖形結構合稱為非線性結構。在樹形結構中,除了樹根結點以外，其余每個結點只有1個前驅結點。在圖形結構中,每個結點的前驅結點數和后繼結點數可以任意多個。數據的存儲結構又叫物理結構.數據的存儲結構形式包括順序存儲、鏈式存儲、索引存儲和散列存儲。線性結構中的元素之間存在一對一的關系。樹形結構中的元素之間存在一對多的關系。圖形結構的元素之間存在多對多的關系。數據結構主要研究數據的邏輯結構、存儲結構和算法（或運算）3個方面的內容。數據結構被定義為（D，R），其中D是數據的有限集合，R是D上的關系有限集合。算法是一個有窮指令的集合。算法效率的度量可以分為事先估算法和事后統計法。一個算法的時間復雜度是算法輸入規模的函數。算法的空間復雜度是指該算法所耗費的存儲空間，它是該算法求解問題規模的n的函數。若一個算法中的語句頻度之和為T（n）=6n+3nlog2n,則算法的時間復雜度為O（nlog2n）.若一個算法的語句頻度之和為T（n)=3n+nlog2+n2,則算法的時間復雜度為O(n2）.數據結構是一門研究非數值計算的程序問題中計算機的操作對象，以及它們之間的關系和運算的學科。三、選擇題數據結構通常是研究數據的（A)及它們之間的相互關系.A．存儲結構和邏輯結構B．存儲和抽象C．聯系和抽象D．聯系與邏輯在邏輯上可以把數據結構分成（C)。A．動態結構和靜態結構B．緊湊結構和非緊湊結構C．線性結構和非線性結構D．內部結構和外部結構.數據在計算機存儲內表示時，物理地址和邏輯地址相同并且是連續的，稱之為（C).A．存儲結構B．邏輯結構C．順序存儲結構D．鏈式存儲結構非線性結構中的每個結點（D）。A．無直接前驅結點．B．無直接后繼結點．C．只有一個直接前驅結點和一個直接后繼結點D．可能有多個直接前驅結點和多個直接后繼結點鏈式存儲結構所占存儲空間（A）。A．分兩部分，一部分存放結點的值，另一個部分存放表示結點間關系的指針。B．只有一部分,存放結點的值。C．只有一部分，存儲表示結點間關系的指針.D．分兩部分，一部分存放結點的值，另一部分存放結點所占單元素算法的計算量大小稱為算法的（C）。A．現實性B．難度C．時間復雜性D．效率數據的基本單位（B）.A．數據結構B．數據元素C．數據項D．文件每個結點只含有一個數據元素，所有存儲結點相繼存放在一個連續的存儲空間里，這種存儲結構稱為（A）結構。A．順序結構B．鏈式結構C．索引結構D．散列結構每一個存儲結點不僅含有一個數據元素,還包含一組指針，該存儲方式是（B）。A．順序B．鏈式C．索引D．散列以下任何兩個結點之間都沒有邏輯關系的是(D）.A．圖形結構B．線性結構C．樹形結構D．集合在數據結構中,與所使用的計算機無關的是（C).A．物理結構B．存儲結構C．邏輯結構D．邏輯和存儲結構下列4種基本邏輯結構中,數據元素之間關系最弱的是（A）。A．集合B．線性結構C．樹形結構D．圖形結構與數據元素本身的形式、內容、相對位置、個數無關的是數據的（A）。A．邏輯結構B．存儲結構C．邏輯實現D．存儲實現每一個存儲結點只含有一個數據元素，存儲結點存放在連續的存儲空間，另外有一組指明結點存儲位置的表,該存儲方式是（C)存儲方式。A．順序B．鏈式C．索引D．散列算法能正確的實現預定功能的特性稱為算法的（A）。A．正確性B．易讀性C．健壯性D．高效性算法在發生非法操作時可以作出相應處理的特性稱為算法的(C）。A．正確性B．易讀性C．健壯性D．高效性下列時間復雜度中最壞的是（D）。A．O（1)B。O（n）C.O（log2n)D.O(n2)下列算法的時間復雜度是（D）。for(i=0；i<n；i++)for(j=o；i〈n；j++)c[i][j］=i+j;A．O（1)B。O（n)C。(log2n）D。O(n2）算法分析的兩個主要方面是（A）。A。空間復雜性和時間復雜性B.正確性和簡明性C。可讀性和文檔性D.數據復雜性和程序復雜性計算機算法必須具備輸入、輸出和（C）。A。計算方法B.排序方法C.解決問題的有限運算步驟D。程序設計方法

第2章線性表一、判斷題線性表的鏈式存儲結構優于順序存儲。（×）鏈表的每個結點都恰好包含一個指針域。（×）在線性表的鏈式存儲結構中,邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。（√）順序存儲方式的優點是存儲密度大，插入、刪除效率高。（×)線性鏈表的刪除算法簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續的各個單元向前移動。（×)順序表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型.（×）線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數據元素.(√）線性表采用順序存儲，必須占用一片連續的存儲單元。（√）順序表結構適宜進行順序存取，而鏈表適宜進行隨機存取。（×）插入和刪除操作是數據結構中是最基本的兩種操作,所以這兩種操作在數組中也經常使用.（×）二、填空題順序表中邏輯上相鄰的元素在物理位置上必須相鄰.線性表中結點的集合是有限的,結點間的關系是一對一關系。順序表相對于鏈表的優點是節省存儲和隨機存取。鏈表相對于順序表的優點是插入、刪除方便.當線性表的元素總數基本穩定，且很少進行插入和刪除操作,但要求以最快速度存取線性表中的元素時，應采用順序存儲結構。順序表中訪問任意一個結點的時間復雜度均為O（1）。鏈表相對于順序表的優點是插入、刪除方便；缺點是存儲密度小。在雙向鏈表中要刪除已知結點＊P，其時間復雜度為O(1)。在單向鏈表中要在已知結點＊P之前插入一個新結點，需找到*P的直接前驅結點的地址，其查找的時間復雜度為O（n）。在單向鏈表中需知道頭指針才能遍歷整個鏈表。線性表中第一個結點沒有直接前驅,稱為開始結點。在一個長度為n的順序表中刪除第i個元素，要移動n—i個元素.在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移n—i+1個元素.在無頭結點的單向鏈表中，第一個結點的地址存放在頭指針中,而其他結點的存儲地址存放在前趨結點的指針域中。線性表的元素總數不確定,且經常需要進行插入和刪除操作，應采用鏈子存儲結構。在線性表中的鏈式存儲中,元素之間的邏輯關系是通過指針決定。在雙向鏈表中,每個結點都有兩個指針域，它們一個指向其前趨結點，另一個指向其后繼結點。對一個需要經常進行插入和刪除操作的線性表，采用鏈式存儲結構為宜。雙向鏈表中，設P是指向其中待刪除的結點，則需要執行的操作為p-〉prior—〉next=p—〉next；p-〉next—〉prior=p-〉prior在如圖所示的鏈表中，若在指針P所在的結點之后插入數據域值為a和b的兩個結點，則可用語句S—>next->next=p—〉next和P—>next=S；來實現該操作。p ∧abs選擇題在具有n個結點的單向鏈表中，實現（A）的操作，其算法的時間復雜度都是O（n）.A。遍歷鏈表或求鏈表的第i個結點B.在地址為P的結點之后插入一個結點C.刪除開始結點D.刪除地址為P的結點的后繼結點設a、b、c為3個結點，p、10、20分別代表它們的地址,則如下的存儲結構稱為(B）。pa10b20c∧A．循環鏈表B．單向鏈表C．雙向循環鏈表D．雙向鏈表單向鏈表的存儲密度（C)。A.大于1B.等于1C.小于1D。不能確定已知一個順序存儲的線性表，設每個結點占m個存儲單元，若第一個結點的地址為B，則第i個結點的地址為（A）.A。B+（i-1）×mB.B+i×mC。B-i×mD。B+（i+1)×m在有n個結點的順序表上做插入、刪除結點運算的時間復雜度為(B）.A．O（1）B.O(n）C.O(n2）D.O（log2n）設front、rear分別為循環雙向鏈表結點的左指針和右指針，則指針P所指的元素是雙循環鏈表L的尾元素的條件是（D）.A。P==LB。P—>front==LC.P==NULLD.P—>rear==L兩個指針P和Q，分別指向單向鏈表的兩個元素，P所指元素是Q所指元素前驅的條件是（B）A．P—〉next==Q-〉nextB.P-〉next==QC。Q->next==PD。P==Q用鏈表存儲的線性表,其優點是(C)。A．便于隨機存取B．花費的存儲空間比順序表少C．便于插入和刪除D．數據元素的物理順序與邏輯順序相同在單鏈表中,增加頭結點的目的是(C）。A．使單鏈表至少有一個結點B．標志表中首結點的位置C．方便運算的實現D．說明該單鏈表是線性表的鏈式存儲結構下面關于線性表的敘述中，錯誤的是（D)關系。A．順序表必須占一片地址連續的存儲單元B．順序表可以隨機存取任一元素C．鏈表不必占用一片地址連續的存儲單元D．鏈表可以隨機存取任一元素L是線性表，已知LengthList（L）的值是5,經DelList（L，2）運算后，LengthList（L）的值是（C）。A．2B．3C．4D．5單向鏈表的示意圖如下:LABCD∧PQR指向鏈表Q結點的前驅的指針是（B）。A．LB．PC．QD．R設p為指向單循環鏈表上某結點的指針，則*p的直接前驅（C）。A．找不到B．查找時間復雜度為O（1）C．查找時間復雜度為O（n）D．查找結點的次數約為n等概率情況下，在有n個結點的順序表上做插入結點運算，需平均移動結點的數目為（8）.A．nB。(n-1)/2C.n/2D。（n+1)/2在下列鏈表中不能從當前結點出發訪問到其余各結點的是（C)。A.雙向鏈表B.單循環鏈表C。單向鏈表D。雙向循環鏈表在順序表中，只要知道（D），就可以求出任一結點的存儲地址。A.基地址B。結點大小C。向量大小D.基地址和結點大小在雙向鏈表中做插入運算的時間復雜度為(A）。A．O(1）B.O（n）C。O（n2）D。O(log2n）鏈表不具備的特點是（A）。A．隨機訪問B.不必事先估計存儲空間C.插入刪除時不需要移動元素D.所需空間與線性表成正比以下關于線性表的論述，不正確的為（C）.A。線性表中的元素可以是數字、字符、記錄等不同類型B.線性順序表中包含的元素個數不是任意的C.線性表中的每個結點都有且僅有一個直接前驅和一個直接后繼D。存在這樣的線性表，即表中沒有任何結點在（B)的運算中,使用順序表比鏈表好。A.插入B。根據序號查找C.刪除D。根據元素查找

第3章棧判斷題棧是運算受限制的線性表。（√）在棧空的情況下，不能作出棧操作,否則產生下溢。（√）棧一定是順序存儲的線性結構。（×）棧的特點是“后進先出”。（√)空棧就是所有元素都為0的棧。（×)在C（或C++）語言中設順序棧的長度為MAXLEN，則top=MAXLEN時表示棧滿。（×）鏈棧與順序棧相比，其特點之一是通常不會出現棧滿的情況。（√）一個棧的輸入序列為:A，B,C，D，可以得到輸出序列：C，A,B，D。（×）遞歸定義就是循環定義。（×）將十進制數轉換為二進制數是棧的典型應用之一.（√）二、填空題在棧結構中,允許插入、刪除的一端稱為棧頂.在順序棧中,當棧頂指針top=—1時，表示棧空。在有n個元素的棧中，進棧操作時間復雜度為O(1).在棧中，出棧操作時間復雜度為O（1）.已知表達式，求它的后綴表達式是棧的典型應用。在一個鏈棧中,若棧頂指針等于NULL，則表示棧空.向一個棧頂指針為top的鏈棧插入一個新結點*p時，應執行p-〉next=top;top=p；操作。順序棧S存儲在數組S-〉data[0…MAXLEN-1］中，進棧操作時要執行的語句有：S—>top++。(或S-〉top+1）S->data[S—〉top］=x鏈棧LS，指向棧頂元素的指針是LS—>next。從一個棧刪除元素時,首先取出棧頂元素,然后再移動棧頂指針。由于鏈棧的操作只在鏈表的頭部進行,所以沒有必要設置頭結點.已知順序棧S，在對S進棧操作之前首先要判斷棧是否滿。已知順序棧S，在對S出棧操作之前首先要判斷棧是否空。若內在空間充足，鏈棧可以不定義棧滿運算。鏈棧LS為空的條件是LS-〉next=NULL。鏈棧LS的棧頂元素是鏈表的首元素。同一棧的各元素的類型相同。若進棧的次序是A、B、C、D、E，執行3次出棧操作以后，棧頂元素為B。A+B/C—D*E的后綴表達式是ABC/+DE＊—。4個元素A、B、C、D順序進S棧，執行兩次Pop（S，x)運算后，x的值是C.三、選擇題插入和刪除操作只能在一端進行的線性表,稱為（C）。A．隊列B．循環隊列C．棧D．循環棧設有編號為1，2.3,4的4輛列車，順序進入一個棧結構的站臺，下列不可能的出站順序為（D）。A．1234B．1243C．1324D．1423如果以鏈表作為棧的存儲結構，則出棧操作時(B）.A．必須判別棧是否滿B．必須判別棧是否為空C．必須判別棧元素類型D．棧可不做任何判別元素A、B、C、D依次進棧以后，棧頂元素是（D）A．AB．BC．CD．D順序棧存儲空間的實現使用(B）存儲元素。A．鏈表B．數組C．循環鏈表D．變量在C（或C++)語言中,一個順序棧一旦被聲明，其占用空間的大小（A)。A．已固定B．不固定C．可以改變D．動態變化帶頭結點的鏈棧LS的示意圖如下，棧頂元素是(A）.LSHABCD∧A．AB．BC．CD．D鏈棧與順序棧相比，有一個比較明顯的優點是（B）。插入操作更加方便B。通常不會出現棧滿的情況C.不會出現棧空的情況D。刪除操作更加方便從一個棧頂指針為top的鏈棧中刪除一個結點時，用x保存被刪除的結點，應執行下列（d）命令.A．x=top；top->next;B.top=top-〉next;x=top—〉dataC。x=top->data;D.x=top—>data；top=top—〉next在一個棧頂指針為HS的鏈棧中，將一個S指針所指的結點入棧，應執行下列(B）命令。A.HS—>next=SB.S-〉next=HS—〉next；HS—〉next=S;C。S—〉next=HS->next;HS=S；D.S->next=HS=HS->next4元素按A、B、C、D順序進S棧，執行兩次Pop(S,x）運算后，棧頂元素的值是(B）。A．AB．BC．CD．D元素A、B、C、D依次進棧以后，棧底元素是（A）。A．AB．BC．CD．D經過下列棧的運算后，再執行ReadTop(s)的值是（A）.InitStack(s);Push（s，a）；Push(s，b)；Pob（s）；aB。bC.1D。0經過下列棧的運算后，x的值是（B)。InitStack（s）（初始化棧）；Push（s，a)；Push(s,b)；ReadTop（s）;Pob（s，x）；aB。bC。1D。0經過下列棧的運算后,x的值是（B）。InitStack（s）（初始化棧）;Push(s，a）;Pob（s,x）；Push（s,b）；Pob(s,x)；A.aB.bC.1D.0經過下列棧的運算后,SEmpty(s）的值是（C）。InitStack（s)（初始化棧）；Push（s，a）；Push（s，b）;Pob（s，x)；Pob(s，x);A。aB。bC.1D。0向順序棧中輸入元素時（B）。A．先存入元素，后移動棧頂指針B．先移動棧頂指針，后存入元素C．誰先誰后無關緊要D．同時進行初始化一個空間大小為5的順序棧S后，S-〉top的值是（B)。A．0B．—1C．不再改變D．動態變化設有一個入棧的次序A、B、C、D、E，則棧不可能的輸出序列是（C）.A．EDCBAB．DECBAC．DCEABD．ABCDE設有一個順序棧S，元素A、B、C、D、E、F依次進棧，如果6個元素出棧的順序是B、D、C、F、E、A，則棧的容量至少應是（A）.A．3B．4C．5D．6

第4章隊列一、判斷題隊列是限制在兩端進行操作的線性表。（√）判斷順序隊列為空的標準是頭指針和尾指針都指向同一個結點。（√)在鏈隊列上做出隊操作時，會改變front指針的值。（×)在循環隊列中，若尾指針rear大于頭指針front，其元素個數為rear—front。（√)在單向循環鏈表中,若頭指針為h，那么p所指結點為尾結點的條件是p=h。（×）鏈隊列在一定范圍內不會出現隊滿的情況。（√）在循環鏈隊列中無溢出現象。（×）棧和隊列都是順序存儲的線性結構。（×)在隊列中允許刪除的一端稱為隊尾。（×）順序隊和循環隊關于隊滿和隊空的判斷條件是一樣的。（×）二、填空題在隊列中存取數據應遵循的原則是先進先出。隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算線性表。在隊列中，允許插入的一端稱為隊尾。在隊列中，允許刪除的一端稱為隊首（或隊頭）.隊列在進行出隊操作時，首先要判斷隊列是否為空。順序隊列在進行入隊操作時，首先在判斷隊列是否為滿.順序隊列初始化后,初始化后，front=rear=-1。解決順序隊列“假溢出”的方法是采用循環隊列.循環隊列的隊指針為front，隊尾指針為rear,則隊空的條件為front==rear。鏈隊列LQ為空時,LQ->front-〉next=NULL。設長度為n的鏈隊列用單循環表表示,若只設頭指針，則入隊操作的時間復雜度為O（n）.設長度為n的鏈隊列用單循環表表示，若只設尾指針,則入隊操作的時間復雜度為O(1)。在一個鏈隊列中，若隊首指針與隊尾指針的值相同，則表示該隊列為空。設循環隊列的頭指針front指向隊首元素,尾指針rear指向隊尾元素后的一個空閑元素,隊列的最大空間為MAXLEN,則隊滿標志為front==(rear+1)%MAXLEN.在一個鏈隊列中，若隊首指針為front，隊尾指針為rear，則判斷隊列只有一個結點的條件為front==rear或front！。向一個循環隊列中插入元素時,首先要判斷隊尾指針，然后再向指針所指的位置寫入新的數據。讀隊首元素的操作不改變或不影響隊列元素的個數。設循環隊列的容量為40（序號0～39）,現經過一系列的入隊和出隊的運算后，front=11,rear=19,則循環隊列中還有8個元素。隊列Q,經過下列運算：InitQueue（Q)（初始化隊列）；InQueue（Q,a);InQueue(Q，b)；OutQueue（Q,x);ReadFront（Q,x);QEmpty(Q）；后的值是8.隊列Q經過InitQueue(Q）（初始化隊列）；InQueue（Q,a）；InQueue(Q，b);ReadFront（Q，x）后，x的值是a.三、選擇題隊列是限定在（D)進行操作的線性表.A．中間者B。隊首C.隊尾D.端點隊列中的元素個數是（B)。A．不變的B。可變的C.任意的D。0同一隊列內的各元素的類型(A）。A.必須一致B。不能一致C。可以不一致D。不限制隊列是一個(C)線性表結構。A.不加限制的B。推廣了的C。加了限制的D.非當利用大小為n的數組順序存儲一個隊列時,該隊列的最后一個元素的下標為（B).A。n-2B。n-1C.nD.n+1一個循環隊列一旦說明,其占用空間的大小（A）。A.已固定B.可以變動C.不能固定D。動態變化循環隊列占用的空間（A）。A.必須連續B.不必連續C.不能連續D.可以不連續存放循環隊列元素的數組data有10個元素，則data數組的下標范圍是（B)。A.0～10B。0～9C.1~9D。1～10若進隊的序列為A、B、C、D,則出隊的序列是(C）.A.B、C、D、AB.A、C、B、DC.A、B、C、DD.C、B、D、A4個元素按A、B、C、D順序連續進隊Q，則隊尾元素是(D）A．AB．BC．CD．D4個元素按A、B、C、D順序連續進隊Q,執行一次QutQueue(Q）操作后，隊頭元素是（B）.A.AB。BC。CD.D4個元素按A、B、C、D順序連續進隊Q,執行4次QutQueue（Q)操作后，再執行QEmpty（Q)；后的值是(B)。A.0B。1C.2D。3隊列Q,經過下列運算后，x的值是（B）。InitQueue（Q)（初始化隊列);InQueue(Q，a）；InQueue（Q，b)；OutQueue(Q,x）;ReadFront(Q，x）；A.aB。bC。0D.1循環隊列SQ隊滿的條件是（B）。A.SQ—>rear==SQ->frontB.（SQ—>rear+1）%MAXLEN==SQ—>frontC。SQ->rear==0D.SQ->front==0設鏈棧中結點的結構：data為數據域，next為指針域，且top是棧頂指針,若想在鏈棧的棧頂插入一個由指針s所指的結點,則應執行下列（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;帶頭結點的鏈隊LQ示意圖如下，鏈隊列的隊頭元素是(A）。LQ—〉front HABCD∧LQ—>rearA．AB．BC．CD．D帶頭結點的鏈隊列LQ示意圖如下,指向鏈隊列的隊頭指針是（C）.LQ-〉frontHABCD∧LQ—>rearA.LQ—〉frontB。LQ—〉rearC。LQ—〉front—>nextD.LQ->rear->next帶頭結點的鏈隊列LQ示意圖如下,在進行進隊的運算時指針LQ—〉frnot（A）。LQ-〉frontHABCD∧LQ—〉rearA.始終不改變B。有時改變C.進隊時改變D。出隊時改變19。隊列Q，經過下列運算后，再執行QEmpty(Q)的值是（C）。InitQueue（Q）(初始化隊列)；InQueue(Q,a）；InQueue(Q,b)；OutQueue（Q，x)；ReadQueue(Q,x);A。aB。bC.0D。120.若用一個大小為6數組來實現循環隊列,且當前front和rear的值分別為3和0,當從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為(B)。A。5和1B.4和2C。2和4D.1和5

第5章串一、判斷題串是n個字母的有限序列.(×)串的數據元素是一個字符。（√）串的長度是指串中不同字符的個數。(×）如果兩個串含有相同的字符，則說明它們相等。（×)如果一個串中所有的字母均在另一個串中出現，則說明前者是后者的子串。（×)串的堆分配存儲是一種動態存儲結構。（√）“DT”是“DATA”的子串。(×）串中任意個字符組成的子序列稱為該串的子串.（×）子串的定位運算稱為模式匹配。（√）在鏈串中為了提高存儲密度，應該增大結點的大小。（√）二、填空題由零個或多個字符組成的有限序列稱為字符串(或串)。字符串按存儲方式可以分為順序存儲、鏈接存儲和堆分配存儲。串的順序存儲結構簡稱為順序串。串順序存儲非緊湊格式的缺點是空間利用率低。串順序存儲緊湊格式的缺點是對串的字符處理效率低。串鏈接存儲的優點是插入、刪除方便,缺點是空間利用率.在C或C++語言中，以字符\0表示串值的終結。空格串的長度等于空格的個數.在空串和空格串中,長度不為0的是空格串。兩個串相等是指兩個串長度相等，且對應位置的字符都相同。設“S=MyMusic"，則LenStr(s)=8。兩個字符串分別為；S1=”Todayis”、S2="30July，2005”，ConcatStr(S1，S2)的結果是Todayis30July，2005。求子串函數SubStr（“Todayis30July,2005"，13，4)的結果是July。在串的運算中,EqualStr（aaa，aab）的返回值〈0。在串的運算中，EqualStr（aaa,aaa)的返回值0.在子串的定位運算中,被匹配的主串稱為目標串,子串稱為模式。模式匹配成功的起始位置稱為有效位移。設S=”abccdcdccbaa”，T=”cdcc”,則第6次匹配成功。設S=”c：/mydocument/text1。doc”,T="mydont”,則字符定位的位置為0。若n為主串長度，m為子串長度，n>〉m，則模式匹配算法最壞情況下的時間復雜度為(n—m+1)＊m。三、選擇題串是和種特殊的線性表，其特殊體現在（B）。A．可能順序存儲B．數據元素是一個字符C．可以鏈接存儲D．數據元素可以是多個字符某串的長度小于一常數，則采用（B）存儲方式最節省空間。A．鏈式B．順序C．堆結構D．無法確定以下論述正確的是（C）。A．空串與空格串是相同的B．”tel”是”Teleptone”的子串C．空串是零個字符的串D．空串的長度等于1以下論述正確的是（B）.A．空串與空格串是相同的B．”ton”是”Teleptone”的子串C．空格串是有空格的串D．空串的長度等于1以下論斷正確的是（A）。A．全部由空格組成的串是空格串B．”BEUIJING”是”BEIJING”的子串C．"something"<”Something”D．”BIT”=”BITE”設有兩個串S1和S2，則EqualStr（S1，S2)運算稱作（D）。A．串連接B．模式匹配C．求子串D．串比較串的模式匹配是指（D)。A．判斷兩個串是否相等B．對兩個串比較大小C．找某字符在主串中第一次出現的位置D．找某子串在主串中第一次出現的第一個字符位置若字符串”ABCDEFG”采用鏈式存儲,假設每個字符占用1個字節，每個指針占用2個字節.則該字符串的存儲密度為（D）。A．20％B．40%C．50%D．33.3％若字符串”ABCDEFG"采用鏈式存儲，假設每個指針占用2個字節，若希望存儲密度為50％,則每個結點應存儲（A）個字符。A.2B.3C.4D.5設串S1="IAM”，S2=”ASDUDENT”，則ConcatStr（S1，S2)=（B）。A．"IAM"B.”IAMASDUDENT"C。”IAMASDUDENT”D.”ASDUDENT”設S="”，則LenStr(S）=（A）.A.0B.1C。2D。3設目標串T=”AABBCCDDE”,模式P=”ABCDE”,則該模式匹配的有效位移為（A）。A.0B.1C.2D.3設目標串T=”AABBCCDDEEFF”,模式P="CCD”,則該模式匹配的有效位移為（D）.A。2B。3C。4D.5設目標串T="aabaababaabaa”，模式P=”abab”，模式匹配算法的外層循環進行了(D）次。A.1B.9C.4D。5模式匹配算法在最壞情況下的時間復雜是（D)。A。O(m）B.O(n)C.O(m+n)D.O(m×n）S=”morning”，執行求子串函數SubSur(S,2,2）后結果為（B）。A。”mo”B。”or”C.”in”D。”ng”S1=”good”，S2"morning”,執行串連接函數ConcatStr(S1，S2)后結果為(A).A。”goodmorning"B。"goodmorning"C。”GOODMORNING”D.”GOODMORNING"S1=”good”,S2=”morning”執行函數SubSur(S2，4,LenStr（S1）)后的結果為（B)。A.”good”B。”ning”C。"go"D.”morn"設串S1=”ABCDEFG”，S2=”PQRST”，則ConcatStr(SubStr（S1，2，LenStr(S2）），SubStr(S1，LenStr（S2），2))的結果串為（D)。BCDEFB。BCDEFGC.BCPQRSTD.BCDEFEF若串S=”SOFTWARE”，其子串的數目最多是（C）。A．35B.36C.37D。38

第6章多維數組和廣義表一、判斷題n維多維數可以視為n—1維數組元素組成的線性結構.（√)稀疏矩陣中非零元素的個數遠小于矩陣元素的總數.（√）上三角矩陣主對角線以上（不包括主對角線的元素），均為常數C。（×）數組元素可以由若干數據項組成。（√）數組的三元組表存儲是對稀疏矩陣的壓縮存儲.（√）任何矩陣都可以進行壓縮存儲.(×）廣義表是線性表的推廣，所以廣義表也是線性表。（×）廣義表LS=(a0,a1，……an—1），則an-1是其表尾。（×）廣義表（（a，b）a，b）的表頭和表尾是相等的.(√)一個廣義表的表尾總是一個廣義表。(√）二、填空題多維數組的順序存儲方式有按行優先順序存儲和按優先順序存儲兩種。在多維數組中，數據元素的存放地址可以直接通過地址計算公式算出，所以多維數組是一種隨機存取結構。在n維數組中的每一個元素最多可以有n個直接前驅。輸出二維數組A[n］[m]中所有元素值的時間復雜度為n（n＊m)。8000000110000000600030070050000000090圖6-19稀疏矩陣A數組元素a[0…2］［08000000110000000600030070050000000090圖6-19稀疏矩陣A稀疏矩陣的三元組有3列。稀疏矩陣的三元組中第1列存儲的是數組中非零元素所在的行數。n階對稱矩，如果只存儲下三角元素，只需要n（n-1)/2個存儲單元。稀疏矩陣A如圖6-19所示,其非零元素存三元組表中，三元組（4，1，5)按列優先順序存儲在三元組表的第4項。稀疏疏矩陣的壓縮存儲方法通常有三元組表和十字鏈表兩種.任何一個非空廣義表的表尾必定是廣義表（或子表)。tail（head（(a，b)(c，d)=b.設廣義表(（a，b，c)）則將c分離出來的運算是head（tail（tail(head（L））））。廣義表現出（（a，b）c，d），表尾是（c，d)。n階下三角矩陣，因為對角線的上方是同一個常數，需要n（n—1）/2+1個存儲單元。稀疏矩陣中有n個非零元素，則三元組有n行。廣義表LS=（a，(b），(（c,（d）））)的長度是3。廣義表LS=（a,（b）,（（c，（d）））)的深度是4。廣義表LS=（(）,L），則L的深度是∞.廣義表LS=（a，（b）,（（c，（d)））)的表尾是((b),((c，（d)）））。三、選擇題在一個m維數組中，（D）恰好有m個直接前驅和m個直接界后繼。A。開始結點B.總終端結點C。邊界結點D.內部結點對下述矩陣進行壓縮存儲后,失去隨機存取功能的是（D）。A。對稱矩陣B。三角矩陣C。三對角矩陣D。稀疏矩陣在按行優先順序存儲的三元組表中,下述陳述錯誤的是（D）。A.同一行的非零元素，是按列號遞增次序存儲的B。同一列的非零元素,是按行號遞增次序存儲的C。三元組表中三元組行號是遞增的D。三元組表中三元組列號是遞增的對稀疏矩陣進行壓縮存儲是為了（B）。A.降低運算時間B.節約存儲空間C。便于矩陣運算D。便于輸入和輸出若數組A［0‥m］［0‥n]按列優先順序存儲，則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］下列矩陣是一個（B).對稱矩陣B．三角矩陣C．稀疏矩陣D．帶狀矩陣10002300456078910在稀疏矩陣的三元組表示法中，每個三元組表示（D）。A．矩陣非零元素的值B．矩陣中數據元素的行號和列號C．矩陣中數據元素的行號、列號和值D．矩陣中非零數據元素的行號、列號和值已知二維數組A［6]［10]，每個數組元素占4個存儲單元，若按行優先順序存儲存放數組元素a［3]［5］的存儲地址是1000,則a[0]［0］的存儲地址是（B)。A．872B．860C．868D．864廣義表是線性表的推廣，它們之間的區別于(A）。A．能否使用子表B．肥否使用原子項C．是否能為空D．表的長度下列廣義表屬于線性表的是(B）。A。E=(a，E）B.E=(a,b，c)C。E=(a，(b,c)）D.E=(a,L);L=()廣義表(（a,b），c，d）的表尾是（D).A．aB．dC．（a,b)D．(c,d)廣義表A=((x，(a,b））,（x,（a，b)，y)),則運算head(head(tail(A）)）為(A）.xB．（a，b）C．（x，（a，b)）D．Atail（head（（a，b）,c，（c，d））)的結果是（B）。bB．（b)C．(a，b)D．(d）若廣義表滿足head（L）=tail(L),則L的形式是（B）。A．空表B．若L=（a1,…,an),則a1=（a2,…，an)C．若L=（a1，…，an），則（a1=a2,=…an）D．(（a1）（a1))數組是一個（B）線性表結構。A。非B.推廣了的C。加了限制的D。不加限制的數組A［0：1，0:1，0:1］共有（D）元素。A.4B。5C.6D。8廣義表（(a,b）,c，d）的表頭是(C）。aB.dC。（a，b）D。(c，d）廣義表A=(a）,則表尾為(C）。aB.（()）C。空表D.(a)以下(C)是稀疏矩陣的壓縮存儲方法。A.一維數組B.二維數組C。三元數組D。廣義表設廣義表D=(a,b,c,d),其深度為（D）。A.2B。3C.4D.∞

第7章樹和二叉樹一、判斷題樹結構中每個結點最多只有一個直接前驅。（√）完全二叉樹一定是滿二叉樹。（×)在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。(×）一棵二叉樹中序遍歷序列的最后一個結點，必定是該二叉樹前序遍歷的最后一個結點。（√）二叉樹的前序遍歷中，任意一個結點均處于其子女結點的前面。（√）由二叉樹的前序遍歷序列和中序遍歷序列,可以推導出后序遍歷的序列。(√)在完全二叉樹中，若一個結點沒有左孩子，則它必然是葉子結點。(√)在哈夫曼編碼中，當兩個字符出現的頻率相同,其編碼也相同，對于這種情況應該做特殊處理。（×）含多于兩棵樹的森林轉換的二叉樹，其根結點一定無右孩子。(×)具有n個葉子結點的哈夫曼樹共有2n-1個結點.（√)二、填空題在樹中，一個結點所擁有的子樹數稱為該結點的度。度為零的結點稱為葉(或葉子,或終端）結點。樹中結點的最大層次稱為樹的深度(或高度）。對于二叉樹來說，第i層上至多有2i-1個結點。深度為h的二叉樹至多有2h—1個結點。由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹.有20個結點的完全二叉樹，編號為10的結點的父結點的編號是5。哈夫曼樹是帶權路徑長度的最小的二叉樹。由二叉樹的后序和中序遍歷序列,可以唯一確定一棵二叉樹。某二叉樹的中序遍歷序列為：DEBAC,后序遍歷序列為：EBCAD。則前序遍歷序列為DABEC.設一棵二叉樹結點的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG,則二叉樹中葉結點是：E、F、H。已知完全二叉樹的第8層有8個結點，則其葉結點數是68.由樹轉換二叉樹時，其根結點無右子樹.采用二叉鏈表存儲的n個結點的二叉樹，一共有2n個指針域。采用二叉鏈表存儲的n個結點的二叉樹,共有空指針n+1個.前序為A，B，C且后序C,B，A的二叉樹共有4種。三個結點可以組成2種不同形態的樹.將一棵完全二叉樹按層次編號，對于任意一個編號為i的結點，其左孩子結點的編號為:2*i。給定如圖7-36所示的二叉樹，其前序遍歷序列為：ABEFHCG。給定如圖7—37所示的二叉樹，其層次遍歷序列為：ABCEFGH.AABCBCEFG圖7-36二叉樹1EFG圖7—37二叉樹2HDHD三、選擇題樹最適合用來表示（D）.A。有序數據元素B。無序數據元素C.元素之間無聯系的數據D.元素之間有分支的層次關系前序為A,B,C的二叉樹共有（D)種.A。2B.3C.4D。5根據二叉樹的定義，具有3個結點的二叉樹有（C）種樹型。A.3B。4C。5D。6在一棵具有五層的滿二叉樹中,結點的點數為（B)。A.16B.31C.32D。33具有64個結點的完全二叉樹的深度為（C）。A.5B.6C.7D.8任何一棵二叉樹的葉結點在前序、中序、后序遍歷序列中的相對次序(A)。A.不發生改變B.發生改變C。不能確定D.以上都不對A，B為一棵二叉樹上的兩個結點,在中序遍歷時,A在B前的條件是（C）。A。A和B右方B.A是B祖先C.A和B左方D.A是B子孫下列4棵樹中，(B)不是完全二叉樹.AB.AC。AD.ABCBCBCBCDEHDGDEFDED如圖7-38所示的二叉樹，后序遍歷的序列是(D)。A。ABCDEFGHIAB.ABDHIECFG圖7—38二叉樹3C。HDIBEAFCGBCD.HIDEBFGCADEFGHI對于圖7—39所示的二叉樹，其中序序序列為(A)。DBEHAFCGB.DBHEAFCGC。ABDEHCFGD.ABCDEFGHABCDEFG圖7-39二叉樹4H某二叉樹的后序遍歷序列為：DABEC,中序遍歷序列為：DEBAC，則前序遍歷序列為（D)。A.ACBEDB.DECABC。DEABCD。CEDBA具有n(n>1)個結點的完全二叉樹中,結點i（2i>n)的左孩子結點是（D).A.2iB。2i+1C.2i—1D.不存在把一棵樹轉換為二叉樹后，這棵二叉樹的形態是（A)。A。唯一的B。有多種C.有多種，但根結點都沒有左孩子D。有多種,但根結點都沒有右孩子將一棵有100個結點的完全二叉樹從上到下,從左到右依次對結點編號，根結點的編號為1，則編號為45的結點的左孩子編號為(B)。A。46B。47C.90D.91將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點編號，根結點的編號為1，則編號為49的結點的右孩子編號為(B）.A.98B。99C.50D.100二叉樹按某種順序線索化后，任一結點均有指向其前驅和后繼的線索，這種說法(B）.A.正確B.錯誤C。不確定D.都有可能下列陳述正確的是（D）.A。二叉樹是度為為2的有序樹B.二叉樹中結點只有一個孩子時無左右之分C.二叉樹必有度為2的結點D。二叉樹中最多只有兩棵子樹，且有左右子樹之分用5個權值{3，2，4，5，1｝構造的哈夫曼樹的帶權路徑長度是（B）.A.32B.33C.34D。15在樹結構中，若結點B有4個兄弟，A是B的父親結點,則A的度為（C)。A.3B.4C.5D.6二叉樹的葉結點個數比度為2的結點的個數（C）。A.無關B.相等C。多一個D.少一個

第8章圖一、判斷題圖可以沒有邊，但不能沒有頂點。（√）在無向圖中，（v1,v2)與（v2，v1)是兩條不同的邊。(×）鄰接表只能用于有向圖的存儲.（×）一個圖的鄰接矩陣表示是唯一的.（√）用鄰接矩陣法存儲一個圖時，所占用的存儲空間大小與圖中頂點個數無關,而只與圖的邊數有關。（×)有向圖不能進行廣度優先遍歷。（×)若一個無向圖以頂點v1為起點進行深度優先遍歷，所得的遍歷序列唯一,則可以唯一確定該圖。（√）存儲無向圖的鄰接矩陣是對稱的,因此只要存儲鄰接矩陣的上三角（或下三角）部分就可以了.(√）用鄰接表法存儲圖時,占用的存儲空間大小只與圖中的邊數有關，而與結點的個數無關。（×）若從一個無向圖中任一頂占出發，進行了一次深度優先遍歷,就可以訪問圖中所有的頂點，則該圖一定是連通的.（√）二、填空題圖常用的存儲方式有鄰接矩陣和鄰接表等。圖的遍歷有：深度優先搜和廣度優先搜等方法。有n條邊的無向圖鄰接矩陣中，1的個數是2n.有向圖的邊也稱為弧。圖的鄰接矩陣表示法是表示頂點之間相鄰關系的矩陣.有向圖G用鄰接矩陣存儲，其第i行的所有元素之和等于頂點i的出度.n個頂占e條邊的圖若采用鄰接矩陣存儲，則空間復雜度為：On2。n個頂占e條邊的圖若采用鄰接表存儲，則空間復雜度為：O(n+e)。設有一稀疏圖G,則G采用鄰接表存儲比較節省空間.設有一稠密圖G,則G采用鄰接矩陣存儲比較節省空間。圖的逆鄰接表存儲結構只適用于有向圖。n個頂點的完全無向圖有n（n—1）/2條邊。有向圖的鄰接矩陣表表示適于求頂