[鍵入文字]PAGEPAGE11復習題集一判斷題（）1.在決定選取何種存儲結構時，一般不考慮各結點的值如何。（）2.抽象數據類型與計算機內部表示和實現無關。（）3.線性表采用鏈式存儲結構時，結點和結點內部的存儲空間可以是不連續的。（）4.鏈表的每個結點中都恰好包含一個指針。（）5.鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續的各個單元向前移動。（）6.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。（）7.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（）8.線性表在物理存儲空間中也一定是連續的。（）9.順序存儲方式只能用于存儲線性結構。（）10.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。（）11.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。（）12.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。（）13.兩個棧共享一片連續內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。（）14.二叉樹的度為2。（）15.若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n—1個非空指針域。（）16.二叉樹中每個結點的兩棵子樹的高度差等于1。（）17.用二叉鏈表法存儲包含n個結點的二叉樹，結點的2n個指針區域中有n+1個為空指針。（）18.具有12個結點的完全二叉樹有5個度為2的結點。（）19.二叉樹的前序遍歷序列中，任意一個結點均處在其孩子結點的前面。（）20.在冒泡法排序中，關鍵值較小的元素總是向前移動，關鍵值較大的元素總是向后移動。（）21.計算機處理的對象可以分為數據和非數據兩大類。（）22.數據的邏輯結構與各數據元素在計算機中如何存儲有關。（）23.算法必須用程序語言來書寫。（）24.判斷某個算法是否容易閱讀是算法分析的任務之一。（）25.順序表是一種有序的線性表。（）26.分配給順序表的內存單元地址必須是連續的。（）27.棧和隊列具有相同的邏輯特性。（）28.樹形結構中每個結點至多有一個前驅。（）29.在樹形結構中，處于同一層上的各結點之間都存在兄弟關系。（）30.如果表示圖的鄰接矩陣是對稱矩陣，則該圖一定是無向圖。（）31.如果表示圖的鄰接矩陣是對稱矩陣，則該圖一定是有向圖。（）32.順序查找方法只能在順序存儲結構上進行。（）33.折半查找可以在有序的雙向鏈表上進行。（）34.滿二叉樹中不存在度為1的結點。（）35.完全二叉樹中的每個結點或者沒有孩子或者有兩個孩子。（）36.對n個元素執行快速排序，在進行第一次分組時，排序碼的比較次數總是n-1次。（）37.在有向圖中，各頂點的入度之和等于各頂點的出度之和。一、選擇題（）1.在n個結點的順序表中，算法的時間復雜度是O(1)的操作是：A)訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）C)刪除第i個結點（1≤i≤n）B)在第i個結點后插入一個新結點（1≤i≤n）D)將n個結點從小到大排序（）2.算法分析的目的是：A)找出數據結構的合理性B)研究算法中的輸入和輸出的關系C)分析算法的效率以求改進D)分析算法的易懂性和文檔性（）3.算法分析的兩個主要方面是：A)空間復雜性和時間復雜性B)正確性和簡明性C)可讀性和文檔性D)數據復雜性和程序復雜性（）4.計算機算法指的是：A)計算方法B)排序方法C)解決問題的有限運算序列D)調度方法（）5.計算機算法必須具備輸入、輸出和等5個特性。A)可行性、可移植性和可擴充性B)可行性、確定性和有窮性C)確定性、有窮性和穩定性D)易讀性、穩定性和安全性（）6.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是:（A）110（B）108（C）100（D）120（）下列選項中與數據存儲結構無關的術語是：A.順序表B.鏈表C.鏈隊列D.棧（）7.鏈接存儲的存儲結構所占存儲空間：（A）分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針（B）只有一部分，存放結點值（C）只有一部分，存儲表示結點間關系的指針（D）分兩部分，一部分存放結點值，另一部分存放結點所占單元數（）8.帶頭結點的單鏈表head，鏈表為空的判定條件是(A)head==NULL(B)head->next==NULL(C)head->next==head(D)head!=NULL（）9.一個棧的輸入序列為1，2，3，…，n，若輸出序列的第一個元素是n，輸出第i（1≤i≤n）個元素是。A)不確定B)n－i＋1C)iD)n（）10.最大容量為n的循環隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。A)(rear＋1)%n==frontB)rear===frontC)rear＋1==frontD)(rear－l)%n==front（）11.循環隊列A[0..m－1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數是:(A)(rear－front＋m)%m(B)rear－front＋1(C)rear－front－1(D)rear－front（）12.若用一個大小為6的數值來實現循環隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為:(A)1和5(B)2和4(C)4和2(D)5和1（）13.按照二叉樹的定義，具有3個結點的二叉樹有（）種。A)3B)4C)5D)6[（）14.若一棵二叉樹中度為l的結點個數是3，度為2的結點個數是4，則該二叉樹葉子結點的個數是:(A)4(B)5(C)7(D)8（）15.具有n(n>0)個結點的完全二叉樹的深度為:(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+1（）16.對一個滿二叉樹，m個葉子，n個結點，深度為h，則:(A)n=h+m(B)h+m=2n(C)m=h-1(D)n=2h-1（）17．在高度為h的完全二叉樹中，表述正確的是（）A.度為0的結點都在第h層上B.第i(1≤i<h)層上的結點都是度為2的結點C.第i(1≤i<h)層上有2i-1個結點D.不存在度為1的結點（）18.深度為5的二叉樹至多有（）個結點。A)32B)31C)16（）19.用鄰接表表示圖進行深度優先遍歷時，通常采用()結構來時實現算法。A)棧B)隊列C)樹D)圖（）20.對N個記錄作順序查找時，當查找成功時，平均查找長度是（）。A)N2B)N2/2C)ND)（N﹢1)/2（）21.當一個有n個頂點的圖用鄰接矩陣A表示時，頂點Vi的度是（）。(A)B)C)D)+（）22．某算法的時間復雜度為O(2n)，表明該算法的（）A.問題規模是2nB.執行時間等于2nC.執行時間近似與2n成正比D.問題的規模近似與2n成正比（）23．“二叉樹為空”意味著二叉樹（）A.由一些沒有賦值的空結點構成B.根結點沒有子樹C.不存在D.沒有結點（）24．數據結構的研究內容不涉及（）A.數據如何組織B.數據如何存儲C.數據的運算如何實現D.算法用什么語言描述（）25．在存儲數據時，通常不僅要存儲各數據元素的值，而且還要存儲A.數據的處理方法B.數據元素的類型C.數據元素之間的關系D.數據的存儲方法（）26．數據采用順序存儲，要求（）A.存儲的是屬于線性結構的數據B.根據結點值的大小，有序存放各結點C.按存儲單元地址由低到高的順序存放各結點D.各結點存放方法有規律，能隱含表示結點間的邏輯關系（）27．一個順序表所占存儲空間大的大小與（）無關A.順序表長度B.結點類型C.結點中各字段的類型D.結點存放順序（）28．數據采用鏈接存儲，要求（）A.每個結點占用一片連續的存儲區域B.所有結點占用一片連續的存儲區域C.結點的最后一個字段是指針型的字段C.每個結點有多少個后繼，就設多少個指針字段（）29．算法的時間復雜度與（）有關A.問題規模B.計算機硬件性能C.編譯程序質量D.程序設計語言（）30．在程序中，為了設置一個空的順序表，必須（）A.給各數組元素賦空值B.給各順序表元素賦空值C.給表示順序表長度的變量賦初始值D.給數組變量名賦初始值（）31．若變量H是某個帶表頭結點循環單向鏈表的表頭指針，則在該鏈表最后的一個結點的后繼指針域中存放的是（）A.H的地址B.H的值C.表頭結點的值D.首元結點的地址（）32．棧和隊列的共同點在于（）A.邏輯特性B.存儲結構C.運算方法D.元素類型（）33．棧和隊列的共同點在于（）A.都對存儲方法作了限制B.都是只能進行插入、刪除運算C.都對插入、刪除的位置作了限制D.都對插入、刪除兩中操作的先后順序作了限制（）34．若5個元素的進棧序列是1,2,3,4,5，則不可能得到出棧序列（）A.1，2，3，4，5B.3，4，2，5，1C.4，2，1，3，5D.5，4，3，2，1（）35．順序循環隊列中是否可以插入下一個元素，（）A.與隊首指針和隊尾指針的值有關B.只與隊尾指針的值有關，與隊首指針的值無關C.只與數組大小有關，與隊首指針和隊尾指針的值無關D.與曾經進行過多少次插入操作有關（）36．在順序隊列中，元素的排列順序（）A.由元素插入隊列的先后順序決定B.與元素值的大小有關C.與隊首指針和隊尾指針的取值有關D.與數組大小有關（）37．在高度為h的完全二叉樹中，（）A.度為0的結點都在第h層上B.第i(1≤i<h)層上的結點都是度為2的結點C.第i(1≤i<h)層上有2i-1個結點D.不存在度為1的結點（）38．一顆二叉樹如圖所示，其中序遍歷的序列為：ACEACEBFGDHB.DGBAECHFC.GDBEHFCAD.ABCDEFGH（）39．采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷（）40．采用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷（）41.已知關鍵字序列為(51，22，83，46，75，18，68，30)，對其進行快速排序，第一趟劃分完成后的關鍵字序列是A.(18,22,30,46,51,68,75,83) B.(30,18,22,46,51,75,83,68)C.(46,30,22,18,51,75,68,83) D.(30,22,18,46,51,75,68,83)二、填空題1．數據結構包括數據的、數據的和數據的這三個方面的內容。2．下面程序段的時間復雜度是。i＝0；while（i<=n）i=i*3；3．在順序表中插入或刪除一個元素，需要平均移動元素，具體移動的元素個數與有關。4．當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應采用存儲結構。5．在n個結點的單鏈表中要刪除已知結點*p，需找到它的的地址，其時間復雜度為。6．已知L是帶表頭結點的非空單鏈表，且P結點既不是首元結點，也不是尾結點，試從下列提供的答案中選擇合適的語句序列。刪除P結點的直接后繼結點的語句序列是。刪除P結點的語句序列是。(1)P=P->next;(2)P->next=P;(3)P->next=P->next->next(4)P->next=P->next->next;(5)while(P!=NULL)P=P->next;(6)while(Q->next!=NULL){P=Q;Q=Q->next;}(7)while(P->next!=Q)P=P->next;(8)while(P->next->next!=Q)P=P->next;(9)while(P->next->next!=NULL)P=P->next;(10)Q=P;(11)Q=P->next;(12)P=L;(13)L=L->next;(14)free(Q);7．棧是一種特殊的線性表，允許插入和刪除運算的一端稱為。不允許插入和刪除運算的一端稱為。8．設棧S的初始狀態為空，若元素a、b、c、d、e、f依次進棧，得到的出棧序列是b、d、c、f、e、a，則棧S的容量至少是。9．用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的S和X的操作串為。10．數據的邏輯結構可以分為和兩大類。11．數據的運算用表示。12．邏輯上相鄰的結點在存儲器中也相鄰，這是存儲結構的特點。13．在長度為n的順序表上實現定位操作，其算法的時間復雜度為。14．為了實現隨機訪問，線性結構應該采用存儲。15．在長度為n的順序表中插入一個元素，最多要移動個元素。16．棧的存儲結構主要有和兩種。17．在編寫程序的時候，如果棧的最大長度難以預先估計，則最好使用棧。18．在樹形結構中，如果某結點，則稱該結點為根結點；如果某結點，則稱該結點為葉子。19．在樹形結構中，每個結點最多只有一個。20．由3個結點所構成的二叉樹有種形態。21．二叉樹的前序遍歷按如下三個步驟進行：；；。22．二叉樹的中序遍歷按如下三個步驟進行：；；。23．在n個頂點的無向圖中，至少有條邊，至多有條邊。24．在n個頂點的有向圖中，至少有條邊，至多有條邊。25．如果排序不改變之間的相對次序，則稱該排序方法是穩定的。26．如果排序改變了之間的相對次序，則稱該排序方法是不穩定的。27．當待排關鍵字序列基本有序時，快速排序、簡單選擇排序和直接插入排序三種排序方法中，運行效率最高的是。28．在一個圖中，所有頂點的度數之和是所有邊數的倍。29．無向圖中邊的數目等于鄰接矩陣中非零元素個數的倍。30．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素比較大小。31．在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第二次被比較的元素是。32．在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第三次被比較的元素是。三、簡答題1．對鏈表設置頭結點的作用是什么？（至少說出兩條好處）2.寫出下列程序段的輸出結果（隊列中的元素類型QElemType為char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}3.簡述以下算法的功能（棧和隊列的元素類型均為int）。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}4.描述以下三個概念的區別：頭指針、頭結點、首元結點（第一個元素結點）。在單鏈表中設置頭結點的作用是什么？5.25738^L對以下單鏈表25738^LT=L;while(T->next!=NULL){T->data=2*T->data;T=T->next;}6.請畫出下圖的鄰接矩陣和鄰接表7．假設二叉樹采用順序存儲結構，如圖所示。（1）畫出二叉樹表示；（2）寫出先序遍歷、中序遍歷和后序遍歷的結果；（3）寫出結點值c的雙親結點，其左、右孩子；1234567891011121314151617181920eafdgcjhib8.樹和二叉樹之間有什么樣的區別與聯系？9.一棵二叉樹中的結點的度或為0或為2，則二叉樹的枝數為2(n0-1)，其中n0是度為0的結點的個數。10.一個深度為L的滿K叉樹有以下性質：第L層上的結點都是葉子結點，其余各層上每個結點都有K棵非空子樹，如果按層次順序從1開始對全部結點進行編號，求：（1）各層的結點的數目是多少？（2）編號為n的結點的雙親結點（若存在）的編號是多少？（3）編號為n的結點的第i個孩子結點（若存在）的編號是多少？（4）編號為n的結點有右兄弟的條件是什么？如果有，其右兄弟的編號是多少？請給出計算和推導過程。11.如果用一個循環數組q[0..m-1]表示隊列時，該隊列只有一個隊列頭指針front，不設隊列尾指針rear，而改置計數器count用以記錄隊列中結點的個數。（1）編寫實現隊列的三個基本運算：判空、入隊、出隊（2）隊列中能容納元素的最多個數是多少？【此題超出教學范圍，不作解答。】ABCDEF12.已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDFABCDEF13．假設以二叉鏈表表示二叉樹，其類型定義如下：typedefstructnode{chardata;structnode*lchild,*rchild;∥左右孩子指針}*BinTree；閱讀下列程序。voidf13(BinTreeT){InitStack(S);∥初始化一個堆棧Swhile(T||!StackEmpty(S)){while(T){Push(S,T);T=T->lchild;}if(!StackEmpty(S)){T=Pop(S);printf(“%c”,T->data);T=T->rchild;}}}回答下列問題：(1)已知以T為根指針的二叉樹如圖所示，請寫出執行f13(T)的輸出結果：(2)簡述算法f13的功能。14．設如下圖所示的二叉樹B的存儲結構為二叉鏈表，root為根指針，結點結構為：（lchild,data,rchild）。其中lchild，rchild分別為指向左右孩子的指針，data為字符型，root為根指針，試回答下列問題：（1）對下列二叉樹B，執行下列算法traversal(root)，試指出其輸出結果；（2）假定二叉樹B共有n個結點，試分析算法traversal(root)的時間復雜度。二叉樹BAABDCFGEC的結點類型定義如下：C的結點類型定義如下：structnode{chardata;structnode*lchild,rchild;};C算法如下：voidtraversal(structnode*root){if(root){printf(“%c”,root->data);traversal(root->lchild);printf(“%c”,root->data);traversal(root->rchild);}}15.已知有向圖的鄰接表如圖所示，請回答下面問題：(1)給