1、數(shù)據(jù)結構復習題第一章概論一. 選擇題1、研究數(shù)據(jù)結構就是研究（D ）。B.數(shù)據(jù)的存儲結構D.數(shù)據(jù)的邏輯結構、存儲結構及其基本操作B.正確性和簡單性D.數(shù)據(jù)復雜性和程序復雜性A. 數(shù)據(jù)的邏紺結構C.數(shù)據(jù)的邏輯結構和存儲結構2、算法分析的兩個主要方面是（AA. 空間復雜度和時間復雜度C 可讀性和文檔性3、計算機中的算法指的是解決某一個問題的有限運算序列，它必須貝備輸入、輸出、（B ） 等5個特性。A町行性.可移植性利町擴充性B.可行性.有窮性和確定性D.易讀性、穩(wěn)定性和確定性C確定性.有窮性和穩(wěn)定性4、卜面程序段的時間復雜度是（C ）« for （i=0;i<m;i+）for（j=

2、0;j<n;j+）ai jl=i*j；A. 0(m2)B. 0(n2)C. O(m*n)D. 0(m+n)5. 算法是（D ）oA.計算機程序B.解決問題的計算方法C.排序算法D.解決問題的方法和步驟，是規(guī)則的冇窮集介6. 某算法的語句執(zhí)行頻度為（3n+n丄ogm+n'+S），其時間復朵度表示（C ）。A. 0（n）B. O（nlog2n）C 0（n二）D. O（log2n）7、卞而程序段的時間復雜度為（C ）owhile （i<=n）i=i*3;A. 0（n）B. 0（3n） C. O（log3n） D. 0（n3）8、數(shù)據(jù)結構是一類數(shù)據(jù)的表示及其相關操作，它一般包括三個

3、方面的內容：數(shù)據(jù)的邏輯結 構、（D ）和數(shù)據(jù)的運算。A. 數(shù)據(jù)的操作B.數(shù)據(jù)的算法C.數(shù)據(jù)的連接D.數(shù)據(jù)的存儲結構9、捕象數(shù)據(jù)類型的三個組成部分分別為（A ）oA. 數(shù)據(jù)對彖、數(shù)據(jù)關系和基本操作B.數(shù)崔元素、邏輯結構和存儲結構C.數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型D.數(shù)據(jù)元索、數(shù)據(jù)結構和數(shù)據(jù)類型1U、卜列程序段的時間復雜度為（B）。 x=n;y=0;while (x>=(y+1)*(y+1) y=y+l;A. 0(n)B. O(/njc. 0(1)D. 0(n=)二、填空題1、程序段丄e(ivn) i=i*2; ”的時間復雜度為log： 。2、數(shù)據(jù)結構的四種基本類型中，樹形結構的元素是一對多關系

4、。3、數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的運算這三個方面的內容。4、數(shù)據(jù)結構按邏紺結構叮分為四類，它們分別是集合、線性結構、樹狀結構和圖狀結構。5、線性結構中元素之間存在一對-關系，樹形結構中元索Z間存在一對多關系，圖形結構 中元素之間存在多對多關系。6、在線性結構中，第一個結點沒有前驅結點,其余每個結點有且只有二個前驅結點：最后 一個結點沒有后繼結點,其余每個結點有且只有1個后繼結點。7、在樹形結構中，樹根結點沒右前驅結點，其余每個結點有且只有二個前驅結點：葉子結 點沒有后續(xù)結點,其余每個結點的后續(xù)結點數(shù)可以任意多個。8、在圖形結構中，每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以任意多

5、個。9、數(shù)據(jù)的存儲結構町用四種基本的存儲方法表示，它們分別是順丿宇、鏈式、索引、散列。10、一個算法的效率可分為時間效率和空間效率。三、簡答題1、簡述線性結構與非線性結構的不同點。答：線性結構反映結點間的邏輯關系是一對一的，非線fl：結構反映結點仙的邏輯關系是多對 多的。第二章線性表一、選擇題1、卞述哪一條是順序存儲結構的優(yōu)點？( A )A存儲密度犬B.插入運算方便C.刪除運算方便D.可方便地用于各種邏輯結 構的存儲表示2. 卜面關于線性表的敘述中，錯誤的是哪-個？( B )A. 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B. 線性表采用順序存儲.便于進行插入和刪除操作tC. 線性表釆用

6、鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3、若長度為n的線性表采用順序存儲結構，在其第i個位蜀插入一個新元素算法的時間復雜度(C )o 衣若一個線性表屮繪常用的操作是取第i個元素和找第i個元素的前趨元素，則釆用（） 存儲方式敲節(jié)省時間。（A ）oA Odogm】)B.O(l)C. 0(n)D.O(n2)A.順序表B.單鏈表C.雙鏈表D.單循環(huán)鏈表5、具有線性結構的數(shù)據(jù)結構是（D ）oA.圖B.樹C.廣義表D.棧6、在一個長度為n的順序表中，在第i個元素之前（元素從1開始計數(shù)）插入一個新元 素時，需向后移動（）個元素。（B ）A. n-iB. n-i+1C

7、. n-i-1D. i7、非空的循壞單鏈表head的尾結點p滿足（AA p->next=headC. p=NULL8、鏈表不具有的特點是（A ）。 A町隨機訪問任一元素 C.不必事先估計存儲空間B p->next=NULLD p=headB. 插入刪除不需要移動元素D. 所需空間與線性表長度成正比9、線性表采用鏈式存儲時，結點的存儲地址（）cA.必須是連續(xù)的B. 必須是不連續(xù)的C.連續(xù)與否均叮D.和頭結點的儲地址相連續(xù)10. 在-個長度為n的順序表中刪除第i個元素，需要向前移動（A ）個元素。A. n-iB. n-i+1C. n-i-1D. i+111>從表中任一結點出發(fā)，都

8、能掃描整個表的是（C ）。A.單鏈表B.順序表C.循環(huán)鏈表D.靜態(tài)鏈表12. 在貝有n個結點的單鏈表上查找值為x的元素時，其時間復雜度為（A ）.A. O（n）B. 0（1）C. O（n:）D. O（n-l）13. 線性表L=（al,a2,，an）,下列說法正確的是（D ）。A. 每個元素都有一個直接前驅和一個直接后繼B. 線性表中至少要有一個元素C. 表中諸元素的排列順序必須是由小到大或由大到小D. 除第一個和故后一個元索外，其余每個元素都由一個且僅有一個直接前驅和直接后 繼14. 在線性表的卜冽存儲結構中，讀取元素花費的時間最少的是（D ）。A.單鏈表B.雙鏈表C.循環(huán)鏈表D.順序表15.

9、 在一個單鏈表中，若刪除p所指向結點的后續(xù)結點，則執(zhí)行（A ）。A. p->next=p->next->next;B. p=p->next;p->next=p->next->next;C. p =p->next;D. p=p->next->next;16. 循環(huán)鏈表的主要優(yōu)點是（D ）oA.不再需要頭指針B.己知某結點位置后能容易找到其直接前馳C. 在進行插入、刪除運算時能保證鏈表不斷開D. 在表中任一結點出發(fā)都能掃描整個鏈表17. 在下列對順序表進行的操作中，算法時間復雜度為0（1）的是（A ）«A.訪問第i個元素的前驅（

10、Kin ） B.在第i個元素之后插入一個新元素 （1 <i <n）C. 刪除第i個元素（lGSn）D.對顧序表中元素進行排序18、已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針s指向另一個 單鏈表中某個結點，則在s所指結點之后插入上述鏈表應執(zhí)行的語句為（A ）0A. q->next=s->next： s->next=p：B. s->next=p； q->next=s->next；C p->next=s->next： s->next=q；D s->next=q： p->next=s->next

11、：19、在以下的敘述中，正確的是（C ）oA.線性表的順序存儲結構優(yōu)于鏈表存儲結構B .線性表的順序存儲結構適用丁頻繁插入/刪除數(shù)據(jù)元索的情況C. 線性表的鏈表存儲結構適用于頻繁插入/刪除數(shù)據(jù)元素的情況D. 線性表的鏈表存儲結構優(yōu)于順序存儲結構20、在表長為n的順序表中，當在任何位置刪除一個元素的概率相同時，刪除一個元素所需 移動的平均個數(shù)為（A ）oA. （n-l）/2B. n/2 C. （n+1） /2 D. n21、在單鏈表中，指針p指向元素為x的結點，實現(xiàn)刪除x的后繼的語句是（B ）。A. p=p->next;B. p->next=p->next->next;C

12、. p->next=p;D. p=p->next->next;二、填空題設單鏈表的結點結構為（data,next）o己知指針p指向單鏈表中的結點，q指向新結點, 欲將q插入到p結點之后，則需要執(zhí)行的語句：: 。答案：q>next =p->nextp->next=q2、線性表的邏輯結構是,其所含元素的個數(shù)稱為線性表的。答案：線性結構長度3、帶頭結點的單鏈表head為空的條件是o答案：head->next=NULL4、在一個單鏈表中刪除p所指結點的后繼結點時，應執(zhí)行以卜操作：q = p->next;p->next=;答案:q->next三

13、、判斷題丄、單鏈表不是一種隨機存儲結構。/2、在具有頭結點的單鏈表中，頭指針指向鏈表的第一個數(shù)據(jù)結點。x3、在線性表的順序存儲結構中，邏輯上相鄰的兩個元素但是在物理位晝上不一定是相鄰的。x4、順序存儲結構的主要缺點是不利于插入或刪除操作。（/）5、線性表采用鏈衷存儲時，結點和結點內部的存儲空間町以足不連續(xù)的。（/）6、顧序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。0）7、線性表的特點是每個元素都有一個前馳和一個后繼。（x）8、取線性表的第I個尤素的時間同1的人小有關（戈）9、線性表只能用順序存儲結構實現(xiàn)。(*)10、順序存儲方式的優(yōu)點是存儲密度人，且插入、刪除運算效率高。(X )

14、11、鏈表是采用鏈式存儲結構的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結 構中效率高。(/ )四、程序分析填空題1、函數(shù)實現(xiàn)單鏈表的插入算法，請在空格處將算法補充完整。int Listinsert (LinkList Lr int i,ElemType e)LNode *pr *s;int j;p=L;j=0;while(p!二NULL)&&(j<i-l) p=p->next;j+;if(p=NULL|j>i-l) return ERROR;s=(LNode *)malloc(sizeof(LNode);s->data=e;return OK;

15、/*ListInsert*/答案：(丄)s->next=p->next (2)p->next=s2、函數(shù)ListDelete_sq實現(xiàn)順序表刪除算法，請在空格處將算法補充完整。int ListDelete_sq(Sqlist L,int i)int k;if (i<l|i>L->length) return ERROR;for (k=i-l;k<L->length-1;k+)L->slistk-(1);<2>；return OK;答案：(1) L->slistk+1(2) ->Length3、慚數(shù)實現(xiàn)單鏈表的刪除算法

16、，請在空格處將算法補充完整。int ListDelete (LinkList Lrint ir ElemType *s)LNode *pz *q;int j;p=L;j=0;v/hile ( (1) && (j) p=p->next;j+;if(p->next=NULL|j>i-l) return ERROR;q=p->next;As=q->data; free (q);(2) ;return OK;/*listDelete*/答案：(1) p->next !=NULL (2) p->next=q->next五、編程題1、有兩個循

17、環(huán)鏈表，銃頭指針分別為L1和L三，要求寫出算法將L2鏈表鏈到L1鏈表之 后，且連接后仍保持循環(huán)鏈表形式。答案：void mei*ge(Lnode *L1, Lnode *L2)Lnode *p,*q;while(p->nexti=Ll)p=p->next,while(q->next l=L2)q=q->next,q->next=Ll; p->next =L2t2、設一個帶頭結點的單向鏈表的頭指針為head,設計算法，將鏈農的記錄，按照data域的 值遞增排序。答案：void assenduig(Lnode *head)Lnode *p,*q , *i; *s

18、;pMiead->next, q=p->next, p->next=NULL,while(q)r=q, q=q->next,if(r->data<=p ->data)r->next=p, head->next=i p=r, elsewhile(ip && r->data>p->data)s=p, p=p->next, r->next=p, s->next=i; pMiead->next, 六、應用題1、線性表有兩種存儲結構：一是順序表，二是鏈表。試問：(1) <111果有n個線

19、性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表 的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結構？為什么？(2) 若：線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線 性表中的元素，那么應采用哪種存儲結構？為什么？(1) 選鏈式存儲結構。它可動態(tài)申請內存空間，不受表長度(即表中元素個數(shù))的影響， 插入、刪除時間復雜度為0 (1)。(2) 選噸序存儲結構。順序表町以隨機存取，時間復雜度為0 (1)2、若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜釆用何種存儲結構？為什 么？采用鏈式存儲結構，它根據(jù)實際需要申諸內存空間，而當不需要時又可將不用結點空間返還

20、給系統(tǒng)。在鏈式存儲結構中插入和刪除操作不需要移動元素第三章棧、隊列和串一.選擇題1、對于棧操作數(shù)據(jù)的原則是（B ）。A.先進先出B.后進先出C.后進后出D.不分順序2、棧在（D ）中應用。A.遞歸調用B.子程序調用C.表達式求值D. A, B, C3、一個棧的輸入序列為1 2 3 4 5,則卞列序列中不可能是校的輸出序列的是（B ）oA. 2 3 4 1 5B. 5 4 13 2C. 2 3 14 524、一個遞歸算法必須包括（B ）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分部分5、用鏈接方式存儲的隊列，在進行刪除運算時（D ）。幾僅修改頭指針 B.僅修改尾指針C.頭、尾指針都要修改D

21、1 5 4 3D.終止條件和迭代D.頭、尾指針可能都要修改6、用不帶頭結點的單鏈表存儲隊列時，其隊頭指針指向隊頭結點，其隊尾指針指向隊尾結點, 則在進行刪除操作時（D ）oA.僅修改隊頭指針B. 僅修改隊尾指針C.隊頭、隊尾指針都要修改D.隊頭，隊尾指針都町能要修改7、遞歸過程或函數(shù)調用時，處理參數(shù)及返回地址，要用一種稱為（CA.隊列B.多維數(shù)組C.棧D.8、棧和隊列都是（C ）A.順序存儲的線性結構C.限制存取點的線性結構9、一個棧的輸入序列為：a.A. a, b, c, d, eC. d, c, e, a, bb.B.鏈式存儲的非線性結構D.限制存取點的非線性結構c, d, e,則棧的不可

22、能輸出的序列是（B d, e, c, b, aD e, d, c, b, a10>設計一個判別表達式中扌舌號是否配對的算法，A.順序表B.鏈表11.帶頭結點的單鏈表head為空的判定條件是（A. head=NULL采用（D ） C.隊列 B ）。B. head->next=NULL）的數(shù)據(jù)結構。線性表C ）o數(shù)據(jù)結構最佳。D.棧C. head->next!=NULLD head!=NULL12>帶頭結點的單鏈表head為空的判定條件是（B ）。A. head=NULLB. head->next=NULLC. head->next!=NULLD. head!=

23、NULL13.隊列的插入操作是在（A ）«>A 隊尾B隊頭C.隊列任意位置D.隊頭元索后丄4、循環(huán)隊列的隊頭和隊尾指針分別為front和匸ear,則判斷循壞隊列為空的條件是A. front=rearB. front=0C. reaE=OD. front=rear+l15.棧的插入和刪除操作在（B ）oA.棧底B.棧頂C.任意位置D.指定位置16.五節(jié)車廂以編號1, 2, 3, 4,5順序進入鐵路調度站（棧人可以得到（C）的編組。A. 3, 4, 5, 1, 2B. 2, 4, 1, 3, 5C. 3, 5, 4,D. 1, 3, 5, 2, 417. 依次在初始為空的隊列中插入

24、元素a.b.c.d以后，緊接著做了兩次刪除操作，此時的 隊頭元素是（c ）。A. aB. bC. cD. d18. 正常情況卜，刪除非空的順序存儲結構的堆棧的棧頂元素，棧頂指針top的變化是 （D ）。A. top不變B. top=0 C. top=top+lD. top=top-l19. 設有兩個串SI和S2,求串S2在S1中首次出現(xiàn)位置的運算稱作（C ）oA.連接 B.求子串C.模式匹配 D.判斷子串20. 串與普通的線性表相比較，它的特殊性體現(xiàn)在（C ）。A.順序的存儲結構B.鏈式存儲結構C. 數(shù)據(jù)元素是一個字符D.數(shù)據(jù)元素任意21、空串和空格串（B ）。A.相同B .不相同C . 口：

25、能相同D .無法確定22. 設SUBSTR（Sri,k）是求S中從第i個字符開始的連續(xù)k個字符組成的子串的操作, 則對于 S=' Beijing&Nanjing* SUBSTR （S, 4,5） = （ B ）。A. 'ij ing* B. ' j ing&'C. 'ingNa'D. 'ing&N二、填空題1、一個循環(huán)隊列Q的存儲空間大小為M,其隊頭和隊尾指針分別為front和匸ea則循環(huán)隊列中元素的個數(shù)為：°答案：（r e ar -fr ont +M） %I2、在具有n個元素的循環(huán)隊列中，隊滿時具有個元

26、素。答案：n-13、設循環(huán)隊列的容最為70,現(xiàn)經過一系列的入隊和出隊操作后，front為20, gar為11,則隊列中元素的個數(shù)為o答案：614、求子串在主串中首次出現(xiàn)的位置的運算稱為模式匹配。5、兩個串相等的充分必要條件是兩個串的長度相等且對應位置字符相同。三、判斷題1、枝和隊列都是受限的線性結構。（/）2、在單鏈表中，要訪問某個結點，只要知道該結點的地址即可；因此，單鏈表是一種隨機 存取結構。（*）3、以鏈表作為棧的存儲結構，出棧操作必須判別棧空的情況。（/）4、消除遞歸不一定需要使用棧，此說法（/）5、棧與隊列是一種持殊操作的線性表。（/）6、棧和隊列都是限制存取點的線性結構。（/）7、

27、隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。(*)四、程序分析填空題丄、己知棧的基本操作函數(shù)：int InitStack (SqStack *S) ; /構造空枝int StackEmpty (SqStack *S) ; /判斷棧空int Push (SqStack *Sr ElemType e);/入棧int Pop (SqStack *Sr ElemType 9);/出棧函數(shù)conversion實現(xiàn)十進制數(shù)轉換為八進制數(shù)，請將兩數(shù)補充完整。void conversion ()(InitStack (S);scant (壯d" 9 &N);wh

28、ile(N)(1) ;N=N/8；while (2) Pop(Sz &e);printf C%dre);/convei?sion答案：(1) Push(S,N%8)(2) IStackEnpty(S)2、閱讀算法f2,并回答下列問題：(1) 設隊列Q=(1，3, 5, 2, 4, 6)«寫出執(zhí)行算法后的隊列Q;(2) 簡述算法f2的功能。void f2 (Queue *Q) DataType e;if (IQueueEmpty(Q)e=DeQueue(Q);f2 (Q)；EnQueue(Q,e);答案：(1) 6,4,2,5,3,1(2)將隊列倒It五、綜合題1、假設以帶頭結

29、點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針， 請寫出相應的入隊列算法(用函數(shù)實現(xiàn))。答 案：void EnQueue(Lnode *reai; ElemTyp e e) Lnode *new,New=QLnode *)malloc(sizeof(Lnode),If(!new) return ERROR,nev/>data=e, new->next=i-ear->next, rear->next=new, rear=new,已知Q是一個非空隊列，S是一個空棧。編寫算法，僅用隊列和棧的ADT因數(shù)和少最工 作變量，將隊列Q的所有元素逆置。棧的ADT函數(shù)有

30、：void makeEmpty (SqStack s);胃空棧void push (SqStack s r ElemType e); 元素 e 入棧ElemType pop (SqStack s); 出棧，返回棧頂元素int isEmpty (SqStack s);判斷棧空隊列的ADT函數(shù)有：void enQueue (Queue qf ElemType e);元素 e 入隊ElemType deQueue (Queue q);出隊，返回隊頭元素int isEmpty (Queue q); 判斷隊空答案：void QueueInvent(Queue q) ElemType x,makeEmpt

31、y(S qStack s),while(i isEnpty(Queue q)x=deQueue(Queue q), push(SqStack s, ElemTypex), while(! isEnpty(SqStack s)x=pop(SqStack s), enQueue(Queue q, ElemType x),3、函數(shù)實現(xiàn)串的模式匹配算法，請在空格處將算法補充完整。int index_bf(sqstring*s/sqstring *tz int start)int i=start-lr j=0;v/hile (i<s->len&&j<t->len)

32、if (s->datai=t->dataj)i+;j+;elsei=i_j+l; j = 0;if(j>=t->len)return i-t->len+l;elsereturn -1; /*listDelete*/4、寫出下面算法的功能。int function (SqString *slz SqString *s2) int i;foe (i=0;i<sl->length&&i<sl->lengrh;i+)if (s->datai!=s2->datai)return sl->datai-s2->da

33、ta i;return s1->length-s2->length;答案：串比較算法5、寫出算法的功能。int fun (sqstring *s z sqstring *tr int start) int i=start-lr j=0;v/hile (i<s->len&&j<t->len)if(s->datai=t->dataj)i+;j+;elsei=i-j+l;j=0;if (j>=t->len)匸eturn i-t->len+l;elsereturn -1;答案：串的模式匹配算法第五章多維數(shù)組和廣義表一、選

34、擇題1、將_個AE1.100, 1.100的三對角矩陣,按行優(yōu)先存入一維數(shù)組Bl298中,A中 元素A6665 (即該元素下標i=66, j二65),在B數(shù)組中的位置K為(B )。A. 198B. 195C. 197D. 1982、二維數(shù)組A的元素都是6個字符組成的串，行卜標i的范用從0到8,列卜標j的范圈從1到io。從供選擇的答案屮選出應填入卜列關于數(shù)組存儲敘述中()內的正確答案。(1) 存放A至少需要(E )個字節(jié)：(2) A的第8列和第5行共占(A )個字節(jié)；(3) 若A按行存放，元素A8, 5的起始地址與A按列存放時的元素(B )的起始地址 一致。供選擇的答案：(1) A. 90B18

35、0C.240D.270E. 540(2) A. 108B.114c.54D.60E. 150(3) A. A8, 5B.A3, 10c.A5, 8D.A0, 93、設A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維 數(shù)組Bl. n(n+l)/2中，對上述任一元素aij (lWi, jWn,且iW j)在B中的位置為(B )。A. i(i-l)/2+j B. j(j-l)/2+iC. j(jT)/2+iT D. i(i-l)/2+j-l4、AN, N是對稱矩陣,將下面三角(包扌舌對角線)以行序存儲到一維數(shù)組TN (N+1) /2 中，則對任一上三角元素aij對應Tk的

36、下標k是(B ).A. i (i-1) /2+j K. j (j-1) /2+i C. i (ji) /2+1 D. j (i-1) /2+15、設二維數(shù)組Al. m, 1. n(即m行n列)按行存儲在數(shù)組Bl. m*n中，則二維數(shù) 組元素Ai, j在一維數(shù)組B中的下標為(A )oA. (i_l) *n+j B. (i_l) *n+j_lC. i* (jT)D. j*m+i-l6、有一個100*90的稀疏矩陣，非0元素有10個，設每個整型數(shù)占2字節(jié)，則用三元組表 示該矩陣時，所需的字節(jié)數(shù)是(B )oA. 60B. 66C. 180C0D. 337、數(shù)組A0. 4, -1. -3, 5. 7中含

37、有元素的個數(shù)(B )。A. 55B. 45C. 36D. 168、廣義表A二(a,b, (c,d), (e, (f,g),則下面式子的值為(D )。Head(Tail(Head(Tail(Tail (A)A. (g)B. (d)C. cD. d9、己知廣義表:A=(a,b), B=(A,A), C=(a, (b,A),B),求下列運算的結果: ta訂 Giead(ta訂(C) =( F ) «A. (a)B. AC aD. (b)EbF. (A)10、廣義表運算式Tail (a, b),(c,d)的操作結果是(C )oA. (c, d)B. c, dC. (c, d)Dd11、廣義表

38、L二(a, (b, c),進行Tail (L)操作后的結果為(DA. cB. b» cC. (b, c)D. (b. c)12、廣義表(a, b, c,d)的表頭是(C ),表尾是(B )oA. aB. ( )C. (a, b, c, d) D. (b, c, d)13、設廣義表L=(a, b, O),則L的長度和深度分別為(C )。A. 1和 1B.1 和3C. 1 和2D. 2和314、廣義表(a) , a)的表尾是(B )。A. aB.(a)C. ()D. ( (a)15、稀疏矩陣的常見壓縮存儲方法有(C )兩種。A.二維數(shù)組和三維數(shù)組B.三元組和散列表C.三元組和十字鏈表D.

39、散列表和十字鏈表一個非空廣義表的表頭(D )oA.不可能是子表 B.只能是子表 C.只能是原子D.可以是子表或原子17. 廣義表 G=(a,B(c,d/ (e,f),g)的長度是(A )。A. 3B. 4C. 7D. 818. 釆用稀疏矩陣的三元組表形式進行壓縮存儲，若要完成對三元組表進行轉置，只要將 行和列對換，這種說法(B )。A.正確 B.錯誤 C.無法確定D.以上均不對19. 廣義表(a,b,c)的表尾是(B )A. b,cB. (b,c)C. cD. (c)20、對-些特殊矩陣采用壓縮存儲的目的主要是為了( D )。A.表達變得簡單C.去掉矩陣中的多余元素21. 廣義表A=(a) ,

40、a)的表頭是(BA. aB. (a)B. 對矩陣元素的存取變得簡單D. 減少不必要的存儲空間的開銷)oC. bD. (a)C.不能遞歸定義D.不能為空表22. 以下有關廣義表的表述中，正確的足(A )oA.由0個或多個原子或子表構成的有限序列B.至少有一個元素是子表C.不能遞歸定義D.不能為空表二、判斷題1、數(shù)組不適合作為任何二叉樹的存儲結構。(X )2、從邏輯結構上看，n維數(shù)組的每個元素均屬于n個向量。(J )3、廣義表中原子個數(shù)即為廣義表的長度。(X )4、數(shù)組町看成線性結構的一種推廣，因此與線性表-樣，可以對它進行插入，刪除等操作。 (X )5、一個稀疏矩陣九采用三元組形式表示，若把三元

41、組中有關行下標與列卜標的值互換， 并把m和n的值互換，則就完成了也的轉置運算。(X )6、二維以上的數(shù)組其實是一種特殊的廣義表。(V )7、廣義表的取表尾運算，其結果通常是個表，但有時也可是個單元素值。(X )8、若一個廣義表的表頭為空表，則此廣義表亦為空表。(X )9、廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表。(X )10、所謂取廣義表的表尾就是返回廣義表中最后一個元素。(X )11、對長度為無窮大的廣義表，由于存儲空間的限制，不能在計算機中實現(xiàn)。(V )12、廣義表是一種多層次的數(shù)據(jù)結構，其元素可以是單原子也可以是子表。(丁) 三、填空題1、已知二維數(shù)組Amn采用行序

42、為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC(A00),則的地址是 Loc(A0 0)+(i*N+j)*k。2、廣義表運算式HEAD(TAIL( (afb,c) , (x,y,z)的結果是：(x,y, z)。3、設廣義表 L=(), 0),則 head(L)是()_： tail(L)是(2)()_)_: L 的長度是(3) 2_ _：深度是 (4)_2 一。4、已知廣義表A二(9, 7,( 8, 10, (99), 12),試用求表頭和表尾的操作Head()和Tail() 將原子元素99從A中取出來。head (head (tail (tail (head (tail

43、 (tail (A)5、廣義表的深度是_表展開后所金括號的層數(shù)=°6、廣義表(a, (a,b),d,e, (G, j),k)的長度是(1)5 ,深度是(2)37、已知廣義表LS二(a, (b, c, d), e),運用head和tail函數(shù)取出LS屮原子b的運算是_head (head (tail (LS)_。8、廣義表A=(a,b), (c,d, e),取出A中的原子e的操作是： _head(tail (tail (head(tail (head(A)_。四、綜合題1、現(xiàn)有一個稀疏矩陣，請給出它的三元組表。0 310_10 0 00 2 100 0-20答案:1JV13131115

44、S3143-2第五章樹形結構D. -+A*BC/DEA.C.D.一、選擇題1. 已知一算術表達式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/其前綴形式為 (D )A. -A+B*C/DEB. -A+B*CD/E C. -+*ABC/DE2、算術表達式a+b* （c+d/e）轉為后綴表達式后為（BA. ab+cde/* B. abcde/+*+C. abcde/*+3、i殳有一表示算術表達式的二叉樹（見下圖），它所表示的算術表達式是（c ）A. A*B+C/（D*E） + （F） B（A*B+C） / （D*E） + （F）C（A*B+C）/（D*E+ （F-G） ） D A*B+

45、C/D*E+F-C 4、設樹T的度為4,其中度為1, 2, 3和4的結點個數(shù)分別為4, 2, b 1則T中的葉子 數(shù)為（D ）D. 8A 5B 6C. 75、在下述結論中，正確的是（D ）只冇一個結點的二叉樹的度為0;二叉樹的度為2： 二叉樹的左右子樹可任意 交換；深度為K的完全二叉樹的結點個數(shù)小于或等于深度柑同的滿二叉樹。6、設森林F對應的二叉樹為B,它有m個結點，B的根為p,p的右子樹結點個數(shù)為m森林F 中第一棵樹的結點個數(shù)是（A ）A. mFB. hifTC. n+1D.條件不足，無法確定7、若一棵二叉樹貝冇10個度為2的結點,5個度為1的結點，則度為0的結點個數(shù)是（B ）A. 9B.

46、11C. 15D.不確定8、在一棵三元樹中度為3的結點數(shù)為2個，度為2的結點數(shù)為1個，度為1的結點數(shù)為2 個，則度為0的結點數(shù)為（C ）個A. 4B. 5C. 6 D. 79、設森林F中有三棵樹，第一，第二，第三棵樹的結點個數(shù)分別為Ml, M2和M3。與森林F 對應的二叉樹根結點的右子樹上的結點個數(shù)是（D ）oA. MlB. M1+M2C. M3D. M2+M310、具有10個葉結點的二叉樹中冇（B ）個度為2的結點，B. 9C. 10D. 1111、一棵完全二叉樹上有1001個結點，其中葉子結點的個數(shù)是（E ）A. 250 B. 500 C. 254 D. 505 E.以上答案都不對12、設

47、給定權值總數(shù)有n個，其哈夫曼樹的結點總數(shù)為（D ）A.不確定B. 2nC. 2n+lD 2nl13、有n個葉子的哈夫曼樹的結點總數(shù)為（D ）。A.不確定B. 2nC. 2n+lD. 2nT14、若度為m的哈夫曼樹中,其葉結點個數(shù)為m則非葉結點的個數(shù)為（C ）oA. n"lB. Ln/mJ"lE. （n+1）/ （m+l）T"l15、有關二叉樹卜列說法正確的是（BA.二叉樹的度為2C. 二叉樹中至少冇一個結點的度為2C (nT) / (m-l)lD n/ (m-l)TlB. 棵二叉樹的度可以小于2D. 二叉樹中任何一個結點的度都為216、二叉樹的第I層上最多含有結點

48、數(shù)為（C ）A. 2X17、一個具有1025個結點的二叉樹的高h為（C ）A. 11B. 10C. 11 至 1025 之間D. 10至1024之間18、一棵二叉樹高度為h,所有結點的度或為0.或為2則這棵二叉樹最少有（B ）結點A. 2h B 2hTC. 2h+lD h+119、對于有n個結點的二叉樹，其高度為（D ）A. nlogm B. logmC. Llog：nJ|lD.不確定20、一棵具有n個結點的完全二叉樹的樹高度（深度）是（A ）A. L logtfi J+lB logi +1C. L logji D. logdi -121、深度為h的滿m叉樹的第k層有（A ）個結點。（l=&l

49、t;k=<h）A. m1"1B m1"!C. m"1 D. mF 22、在一棵高度為k的滿二叉樹中結點總數(shù)為（C ）A. 2円B. 2kC. 2k-l23、高度為K的二叉樹最衣的結點數(shù)為（A. 2"B. 2='C. 2124、一棵樹高為K的完全二叉樹至少有（A 21 - 1B. 2戸-1D. Llog2、J+l)oC-1D. 2W-1C ）個結點C. 2戸D. 2 25、將冇關二叉樹的概念推廣到三叉樹，則一棵有244個結點的完全三叉樹的高度（C）A. 4B. 5C. 6D. 726、對二叉樹的結點從1開始進行連續(xù)編號，要求每個結點的編號人于

50、其左、右孩子的編號， 同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，町采用（C ）次序的遍歷 實現(xiàn)編號。A.先序B.中序C.后序BD.從根開始按層次遍歷27、樹的后根遍歷序列等同于該樹對應的二叉樹的（B ）.A.先序序列B.中序序列C.后序序列28、若二叉樹采用二叉鏈表存儲結構，要交換其所有分支結點左、右子樹的位疊，利用（C ） 遍歷方法最合適。A.前序 B.中序 C.后序 D.按層次29、在下列存儲形式中，哪一個不是樹的存儲形式？（ D ）A.雙親表示法B.孩子鏈表表示法C.孩子兄弟表示法D.順序存儲表示法30、一棵叉樹的前序遍歷序列為ABCDEG它的中序遍歷序列可能足（B ）A.

51、 CABDEFGB ABCDEFGC. DACEFBGD. ADCFEG31、已知一棵叉樹的前序遍歷結果為ABCDEF,中序遍歷結果為CBAEDF,則后序遍歷的結果 為（A ）。A. CBEFDAB. FEDCBAC. CBEDFAD.不定32、己知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac ,它的前序遍歷是 （D ）。A. acbedB. decab C. deabcD. cedba33、某二叉樹中序序列為A, B, C, D, E, F, G,后序序列為B, D, C, A, F, G, E則前序序列是:（B ）A. E, G, F, A. C, D, B B. A. C

52、, B, D, G, F C. E, A, G, C, F, B, D D.上面的 都不對34、上題的二叉樹對應的森林包括多少棵樹（B ）A. 1B. 2C. 3D.概念上是錯誤的35、二叉樹的先序遍歷和中序遍歷如卜：先序遍歷：EFHIGJK：中序遍歷:HFIEJKG。該二 叉樹根的右子樹的根是：（C ）A、EB、FC、GD、H36、將一棵樹t轉換為孩子一兄弟鏈表表示的二叉樹h,則t的后根序遍歷是h的（B ）A.前序遍歷B.中序遍歷 C.后序遍歷 D.層次遍歷37、某二叉樹T有n個結點，設按某種順序對T中的每個結點進行編號，編號為1,2,，n,且有如下性質：T中任一結點V,其編號等于左子樹上的

53、最小編號減1,而V的右子樹的 結點中，其最小編號等于V左子樹上結點的最大編號加1。這時是按（B ）編號的。A中序遍歷序列B.前序遍歷序列C.后序遍歷序列D.層次顧序38、下面的說法中正確的是（B ）.（1）任何一棵二叉樹的葉子結點在三種遍歷中的相對次序不變：（2）按二叉樹定義，具有三個結點的二叉樹共有6種。A. （1）（2） B. （1） C. （2） D.、都錯39、對于前序遍歷與中序遍歷結果相同的二叉樹為（l）o F對于前序遍歷和后序遍歷結果相同的二叉樹為（2）o BA. 一般二叉樹 B.只有根結點的二叉樹C.根結點無左孩子的二叉樹D. 根結點無右孩子的二叉樹E.所有結點只有左子數(shù)的二叉樹

54、F.所有結點只有右子 樹的二叉樹40、在二叉樹結點的先序序列，中序序列和后序序列中，所有葉子結點的先后順序（B ）A.都不相同 B.完全相同 C.先序和中序相同，而與后序不同D. 中序和后序相同，而與先序不同41、某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（C）的二叉樹。A.空或只有一個結點B.任一結點無左子樹C.高度等于其結點數(shù)D.任一結點無右子樹42、在完全二叉樹中，若一個結點是葉結點，則它沒（C ）«A.左子結點B.右子結點C.左子結點和右子結點D.左子結點，右子結點和兄弟結點43、用順序存儲的方法，將完全二叉樹中所有結點按層逐個從左到右的順序存放在一維數(shù)組 R1.N中，若結點Ri有右孩子，則其右孩子是（B ）。A. R2i-1 B. R2i+1C. R2iD. R2/i44、設a, b為一棵二叉樹上的兩個結點，在中序遍歷時，a在b前而的條件足（B ）。A. a在b的右方B. a在b的左方C. a足b的祖先 D. a是b的子孫45、在一棵具有5層的滿二叉樹中結點總數(shù)為（A）。A. 31B. 32 C. 33D. 164