武漢理工大學(xué)數(shù)據(jù)結(jié)構(gòu)2014復(fù)習(xí)題

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