數(shù)據(jù)結(jié)構(gòu)練習(xí)

數(shù)據(jù)結(jié)構(gòu)習(xí)題Lists、選擇題1.在一個長度為n的順序表中，向第i個元素(1WiWn+1)之前插入一個新元素時，需向后移動個元素。n-1 B.n-i+1需向后移動個元素。n-1 B.n-i+1線性表是 。一個有限序列，可以為空C.一個無限序列，可以為空C.n-i-1 D.I一個有限序列，不能為空D.一個無限序列，不能為空對順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概率的，刪除一個元素時大約要移動表中的個元素。n+1 B.n-1 C.(n-1)/2D.n線性表采用鏈式存儲時，其地 。必須是連續(xù)的 B.部分地址必須是連續(xù)的一定是不連續(xù)的 D.連續(xù)與否均可以設(shè)單鏈表中指針p指著結(jié)點(數(shù)據(jù)域為m)，指針f指著將要插入的新結(jié)點(數(shù)據(jù)域為x)，當(dāng)x插在結(jié)點m之后時，只要先修改 后修改p->link=f即可。f->link=p; B.f->link=p->link;C.p->link=f->link; D.f=nil;在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時需修改指針。((p->rlink)->rlink)->link=p;p->rlink=(p->rlink)->rlink;(p->llink)->rlink=p->rlink;(p->rlink)->llink=p->llink;p->llink=(p->llink)->llink;((p->llink)->llink)->rlink=p;((p->llink)->llink)->rlink=p;p->llink=(p->llink)->llink;在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點的前趨結(jié)點(若存在)時需修改指針。((p->llink)->llink)->rlink=p;p->llink=(p->llink)->llink;((p->rlink)->rlink)->llink=p;p->rlink=(p->rlink)->rlink;(p->llink)->rlink=p->rlink;(p->rlink)->llink=p->llink;p->llink=(p->llink)->llink;((p->llink)->llink)->rlink=p;根據(jù)線性表的鏈式存儲結(jié)構(gòu)，每個結(jié)點所含指針的個數(shù)，鏈表分為單鏈表和—。A.循環(huán)鏈表B.多重鏈表C.普通鏈表 D.無頭結(jié)點鏈表從一個具有n個節(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較個結(jié)點。A.n B.n/2 C.(n-1)/2D.(n+1)/2在一個單鏈表中，已知*q結(jié)點是*p結(jié)點的前驅(qū)結(jié)點，若在*4和*?之間插入*，結(jié)點，則執(zhí)行。A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p;C.q->next=s;s->next=p; D.p->next=s;s->next=q;、填空在線性結(jié)構(gòu)中第一結(jié)點，其余每個結(jié)點有且只有;最后一個結(jié)點TOC\o"1-5"\h\z，其余每個結(jié)點有且只有[ 。對于順序存儲的線性表，當(dāng)隨機插入或刪除一個元素時，約需平均移動表長的元素。對于長度為n的順序表，插入或刪除元素的時間復(fù)雜性為；對于順序?；蜿牬酢?，插入或刪除元素的時間復(fù)雜性為 。從順序表中刪除第i個元素時，首先把第i個元素賦給帶回，接著從開始向后的所有元素均一個位置，最后使線性表的長度 。在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過 決定的。一個單鏈表中刪除*?結(jié)點時，應(yīng)執(zhí)行如下操作：q=p->next;p->data=p->next->data;TOC\o"1-5"\h\zp->next= [1];free(q);若要在一個單鏈表中的*?結(jié)點之前插入一個*，結(jié)點時，可執(zhí)行如下操作：s->next= [1] ;p->next=s;t=p->data;p->data= [2];s->data= [3] ;對于線性表的順序存儲，需要預(yù)先分配好存儲空間，若分配太多則容易造成存儲空間的，若分配太少又容易在算法中造，因此適應(yīng)于數(shù)據(jù)量變化不大的情況；對于線性表的鏈接存儲(假定采用動態(tài)結(jié)點)，不需要分配存儲空間，存儲器中的整個都可供使用，分配和回收結(jié)點都非常方便，能夠有效地利用存儲空間，在算法中不必考慮的發(fā)生，因此適應(yīng)數(shù)據(jù)量變化較大的情況。四、綜合題線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：兩種存儲表示各有哪些主要優(yōu)缺點？如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)?為什么？若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么，應(yīng)采用哪種存儲結(jié)構(gòu)?為什么？用線性表的順序結(jié)構(gòu)來描述一個城市的設(shè)計和規(guī)劃合適嗎?為什么？在單鏈表和雙向表中，能否從當(dāng)前結(jié)點出發(fā)訪問到任一結(jié)點？編寫下列算法向類型有l(wèi)ist的線性表L的第i個元素(OWiWL.len)之后插入一個新元素x。從類型為list的線性表L中刪除其值等于x的所有元素。將兩個有序表A和B合并成一個有序表C，其中A，B，C均為list類型的變參。編寫下列算法，假定單鏈表的表頭指針用HL表示，類型為linklist。將一個單鏈表中的所有結(jié)點按相反次序鏈接。刪除單鏈表中第i個(i31)結(jié)點。刪除單鏈表中由指針p所指向的結(jié)點。從帶有附加表頭結(jié)點的循環(huán)單鏈表中刪除其值等于x的第一個結(jié)點。在單鏈表中指針p所指結(jié)點之前插入一個值為x的新結(jié)點。從循環(huán)單鏈表中查找出最小值。根據(jù)一維數(shù)組A(1:n)中順序存儲的具有n個元素的線性表建立一個帶有附加表頭結(jié)點的單鏈表。請指出下面的過程執(zhí)行p(5)和p(6)時分別輸出的結(jié)果。voidP(intn);{ifn>0{p(n-2);printf("%d”,n);}}假定用一個循環(huán)單鏈表表示隊列(稱此為循環(huán)鏈隊)，該隊列只設(shè)一個隊尾指針，設(shè)隊首指針，試編寫下列算法：向循環(huán)鏈隊插入一個元素為x的結(jié)點；從循環(huán)鏈隊中刪除一個結(jié)點(假定不需要保留被刪除結(jié)點的值和不需要回收結(jié)點)。Stack/Queue一、選擇題在一個具有n個單元的順序棧中，假定以地址低端作為棧底，以top作為棧頂指針，則當(dāng)做退棧處理時，top變化為。A.top不變 B.top=-n C.top=top-1D.top=top+1向順序棧中壓入元素時，。A.先存入元素，后移動棧頂指針 B.先移動棧頂指針，后存入元素在一個順序存儲的循環(huán)隊列中，隊首指針指向隊首元素的。A.前一個位置B.后一個位置C.隊首元素位置 D.隊尾元素位置.若進棧序列為1,2,3,4，進棧過程中可以出棧，則不可能是一個出棧序列。A.3,4,2,1B.2,4,3,1 C.1,4,2,3D.3,2,1,4.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊空的條件是。A.front==rear+1B.front+1==rearC.front==rearD.front==0.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊滿的條件。A.rear%n==frontB.(rear-1)%n==frontC.(rear-1)%n==rearD.(rear+1)%n==front.向一個棧項指針為hs的鏈棧中插入一個*s結(jié)點時，則執(zhí)行 。A.hs->next=s; B.s->next=hs->next;hs->next=s;

C.s->next=hs；hs=s;D.s->next=hs;hs=hs->next;C.s->next=hs；hs=s;在一個鏈隊列中，假定front和rear分別為隊首指針和隊尾指針，則進行插入*，結(jié)點的操作時應(yīng)執(zhí)行。A.front->next=s;front=s;C.front=front->next;A.front->next=s;front=s;C.front=front->next;rear->next=s;rear=s;front=rear->next;二、綜合題1、 試給出鏈式棧的實現(xiàn)代碼？2、 試給出鏈式隊列的實現(xiàn)代碼?Tree一.選擇題（根節(jié)點為第1層）假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15個，單分支結(jié)點數(shù)為32個，則葉子結(jié)點數(shù)為。TOC\o"1-5"\h\zA. 15 B. 16 C.17 D. 47假定一棵二叉樹的結(jié)點數(shù)為18個，則它的最小高度。A. 4 B. 5 C.6 D. 18在一棵二叉樹中第五層（根節(jié)點為第1層）上的結(jié)點數(shù)最多為。A. 8 B. 15 C. 16 D. 32在一棵具有五層（根節(jié)點為第1層）的滿二叉樹中，結(jié)點總數(shù)為。A. 31 B. 32 C. 33 D. 16已知8個數(shù)據(jù)元素為（34、76、45、18、26、54、92、65），按照依次插入結(jié)點的方法生成一棵二叉排序樹后，最后兩層上的結(jié)點總數(shù)為。A.1 B.2 C.3 D.4由分別帶權(quán)為9、2、5、7的四個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度A.23B.37A.23B.37C.44D.46在樹中除根結(jié)點外，其余結(jié)點分成m（m30）個的集合T1,T2,T3...Tm,每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點（1WiWm）。A.C.互不相交A.C.互不相交葉結(jié)點可以相交B.可以相交D.樹枝結(jié)點可以相交下面答案是查找二叉樹（又稱二叉排序樹）。二叉樹中的每個結(jié)點的兩棵子樹的高度差的絕對值不大于1二叉樹中的每個結(jié)點的兩棵子樹的高度差等于1二叉樹中的每個結(jié)點的兩棵子樹是有序的二叉樹中的每個結(jié)點的關(guān)鍵字大于其左子樹（如果存在）所有結(jié)點的關(guān)鍵字值，且小于其右子樹（如果存在）所有結(jié)點的關(guān)鍵字值。如果結(jié)點A有三個兄弟，而且B是入的雙親，則B的出度是 。A.3 B.4 C.5 D.1一個深度為L的滿K叉樹有如下性質(zhì)：第L層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有K棵非空子樹。如果按層次順序從1開始對全部結(jié)點編號，編號為n的有右兄弟的條件是。A.(n-1)%k==0B.(n-1)%k!=0C.n%k==0D.n%k!=0在完全二叉樹中，當(dāng)i為奇數(shù)且不等于1時，結(jié)點i的左兄弟是結(jié)點，否則沒有左兄弟。A.2i-1 B.i+1 C.2i+1 D.i-1某二叉樹T有n個結(jié)點，設(shè)按某種遍歷順序?qū)中的每個結(jié)點進行編號，編號值為1,2,...,n且有如下性質(zhì)：T中任一結(jié)點V，其編號等于左子樹上的最小編號減1，而V的右子樹的結(jié)點中，其最小編號等于V左子樹上結(jié)點的最大編號加1。這時按編號。A.中序遍歷序列 B.前序遍歷序列C.后序遍歷序列D.層次遍歷序列最小代價生成樹。A.是唯一的B.不是唯一的C.唯一性不確定D.唯一性與原因的邊的權(quán)數(shù)有關(guān)二、填空在樹型結(jié)構(gòu)中，樹根結(jié)點沒有結(jié)點，其余每個結(jié)點有且僅有;樹葉結(jié)點沒有，其余每個結(jié)點的結(jié)點數(shù)不受限制。對于一棵具有n個結(jié)點的樹，則該樹中所有結(jié)點的度之和為。在一棵二叉樹中，度為0的結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則：在二叉樹的順序存儲中，對于下標為5的結(jié)點，它的雙親結(jié)點的下標為，若它存在左孩子，則左孩子結(jié)點的下標為，若它存在右孩子，則右孩子結(jié)點的下標為。假定一棵二叉樹的廣義表表示為A(B(，D)，C(E(G)，F(xiàn)))，則該樹的深度為，度為0的結(jié)點數(shù)為—，度為1的結(jié)點數(shù)為—，度為2的結(jié)點數(shù)為—；C結(jié)點是A結(jié)點的，E結(jié)點是C結(jié)點的。在一棵二叉排序樹中，按遍歷得到的結(jié)點序列是一個有序序列。由分別帶權(quán)為3,9,6,2,5的共五個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長—假定在二叉樹的鏈接存儲中，每個結(jié)點的結(jié)構(gòu)為 |left|data|right|，其中data為值域，left和right分別為鏈接左、右孩子結(jié)點的指針域，請在下面中序遍歷算法中畫有橫線的地方填寫合適的語句。voidinorder(bt){if(bt!=NULL){TOC\o"1-5"\h\z;;； }}Gragh一、 選擇題在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和白倍。A.1/2 B.1 C.2 D.4對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為—。A.n B.n+1 C.n-1 D.n+e具有n個頂點的無向完全圖，邊的總數(shù)為條。A.n-1 B.n C.n+1 D.n*(n-1)/2設(shè)圖G有n個頂點和e條邊，當(dāng)G是非孤立頂點的連通圖時有2e>=n,故可推得深度優(yōu)先搜索的時間復(fù)雜度為。A.O(e) B.O(n) C.O(ne) D.O(n+e)在無向圖G的鄰接矩陣A中，若A[i,j]等于1，則A[j,i]等于。A.i+j B.i-j C.1 D.0圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為 。(訪問標志位數(shù)組空間)A.O(n) B.O(e) C.O(n-e) D.O(n+e)二、 填空在圖G的鄰接表表示中，每個頂點鄰接表中所含的結(jié)點數(shù)，對于無向圖來說等于該頂點的，對于有向圖來說等于該頂點的。假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣表示的空間復(fù)雜性為，采用鄰接表表示的空間復(fù)雜性為。已知一個無向圖的鄰接矩陣如下所示，則從頂點A出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列為，按廣度優(yōu)先搜索遍歷得到的頂點序列為ABCDEF廠011010nA11010111B1110100|C10010011D1110001|EL010110JF已知一個圖如下所示，在該圖的最小生成樹中，各邊的權(quán)值之和為四、綜合題證明n個頂點的無向完全圖的邊數(shù)的n(n—1)/2。證明一個有n個頂點，e條邊的無向圖G,必有￡dj=2e其中dj為頂點j的度。證明若無向圖G的頂點度數(shù)的最小值大于或等于2,則G有一條回路。設(shè)無向圖G如下圖：⑴該圖的鄰接矩陣；該圖的鄰接表；從A出發(fā)的“深度優(yōu)先”遍歷序列;從A出發(fā)的“廣度優(yōu)先”遍歷序列。Sorting、選擇題目前以比較為基礎(chǔ)的內(nèi)部排序時間復(fù)雜度T(n)的范圍是;其比較次數(shù)與待排序的記錄的初始排列狀態(tài)無關(guān)的是。①O(log2n)?O(n)③O(nlog2n)①O(log2n)?O(n)③O(nlog2n)?O(n2)①插入排序③快速排序④O(n)?O(n2) ⑤O(n)?O(nlog2n)②先用二分法查找，找到后插入排序④冒泡排序設(shè)關(guān)鍵字序列為：3,7,6,9,8,1,4,5,2。進行排序的最小交換次數(shù)是。6 B.7 C.8 D.20在歸并排序過程中，需歸并的趟數(shù)為—。n B.VnC.log2n向上取整D.log2n向下取整一組記錄排序碼為（46、79、56、38、40、84）,則利用堆排序的方法建立的初始堆為 。A. （79、46、 56、 38、 40、80） B. （84、 79、 56、38、40、46）（84、79、 56、 46、 40、38） D. （84、 56、 79、40、46、38）一組記錄的關(guān)鍵碼為（46、79、56、38、40、84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為 。A. （38、40、 46、 56、 79、84） B. （40、 38、46、79、56、84）（40、38、 46、 56、 79、84） D. （40、 38、46、84、56、79）在平均情況下快速排序的時間復(fù)雜性為—，空間復(fù)雜性為；在最壞情況下（如初始記錄已有序），快速排序的時間復(fù)雜性為— ，空間復(fù)雜性為—。A.O（n）B.O（log2n）C.O（nlog2n）D.O（n2）二、填空在對一組記錄（54,38,96,23,15,72,60,45,83）進行直接選擇排序時，第四次選擇和交換后，未排序記錄（即無序表）為。在對一組記錄（54,38,96,23,15,72,60,45,38）進行冒泡排序時，第一趟需進行相鄰記錄交換的次數(shù)為—，在整個冒泡排序過程中共需進行 趟后才能完成。在歸并排序中，若待排序記錄的個數(shù)為20，則共需要進行趟歸并，在第三趟歸并中，是把長度為的有序表歸并為長度為 的有序表。在直接插入和直接選擇排序中，若初始數(shù)據(jù)基本正序，則選用，若初始數(shù)據(jù)基本反序，則選用。5.在堆排序、快速排序和歸并排序中，若只從節(jié)省空間考慮，則應(yīng)首先選取方法，其次選取方法，最后選取方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取；若只從平均情況下排序最快考慮，則應(yīng)選取方法；若只從最壞情況下排序最 快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取方法。單選：在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的數(shù)據(jù)叫結(jié)構(gòu)。A.存儲 B.物理 C.邏輯 D.物理和存儲TOC\o"1-5"\h\z在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)采用線性鏈表表示一個向量時，要求占用的存儲空間地址（ ）。A.必須是連續(xù)的 B.部分地址必須是連續(xù)的一定是不連續(xù)的 D.可連續(xù)可不連續(xù)在一個單鏈表中，若q結(jié)點是p結(jié)點的前驅(qū)結(jié)點，若在q與p之間插入結(jié)點s，則執(zhí)行（ ）。s—link=pTink;pTink=s;p—link=s;s—link=q;p—link=s—link;s—link=p;q—link=s; s—link=p;線性表的鏈式存儲結(jié)構(gòu)與順序（連續(xù)）存儲結(jié)構(gòu)相比優(yōu)點是（）入.所有的操作/運算算法簡單 B.便于隨機存取C.便于插入和刪除 D.便于查找在線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。單鏈表 B.僅有頭指針的單循環(huán)鏈表。.雙鏈表 D.僅有尾指針的單循環(huán)鏈表鏈表不具有的特點是（ ）A.可隨機訪問任一元素 B.插入、刪除不需要移動元素C.不必事先估計存儲空間 D.所需空間與線性表長度成正比在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依相同次序從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)作為數(shù)據(jù)結(jié)構(gòu)是一個（）結(jié)構(gòu)。A.棧B.隊列C.表（Table）D.線性表一個隊列的入隊序列是1,2,3,4,則隊列的出隊序列為（ ）。A.4,3,2,1 B.1,2,3,4C.1,4,3,2 D.3,2,4,1一個棧的輸入序列為1,2,3,4,5,則下列序列中不可能是棧的輸出序列的是（）A.25341 B.12345C.32145 D.54321將一個A[0..19][0..19]（注：下標均從0開始計）的矩陣，按行序為主序存放，每個元素占4個存儲單元，并且A[1，2]的存儲地址是1088,則A[16,3]的地址是（ ）A.1292B.1296C.2292D.2524將一個A[1..20][1..20]（注：下標均從1開始計）的矩陣，按行序為主存TOC\o"1-5"\h\z放，每個元素占4個存儲單元，并且A［1,2］的存儲地址是1004，則A［20,2］的地址是（ ）。A.1004B.1380C.1520D.2524非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足（ ）。A.p->next=NULLB.p=NULLC.p->next=head D.p=head設(shè)循環(huán)隊列用數(shù)組［0..n-1］存放其元素值，其頭指針front指向隊首元素，rear指向隊尾元素，則隊列的長度為（ ）。A.rear-front B.rear-front+1C.（rear—front+1）%n D.（rear—front+n）%n棧和隊列的共同特點是（ ）。A.都是先進先出B.都是先進后出都是只允許在端點處進行插入和刪除的操作受限的線性表沒有共同點在一棵具有5層的滿二叉樹中結(jié)點數(shù)為（）A31B32C33D16設(shè)有100個數(shù)據(jù)元素，采用折半搜索時，最大比較次數(shù)為（）A6B7C8D10在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。A.3B.2 C.1D.1/2TOC\o"1-5"\h\z樹中所有結(jié)點的度等于所有結(jié)點數(shù)加（ ）A.0 B.1 C.-1 D.2在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于（ ）A.n B.n-1 C.n+1 D.2*n對二叉樹從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用（）次序的遍歷實現(xiàn)編號。A.先序 B.中序C.后序 D.從根開始的層次遍歷若無向圖G有7個頂點，至少需要（ ）條邊，才能保證該圖一定是連通圖（邊可依附任兩頂點，但無重復(fù)邊和自環(huán)）A.43 A.43 B.31 C.25D.6若一棵二叉樹具有10個度為2的結(jié)點，則該二叉樹的度為0的結(jié)點個數(shù)是（ ）。A.9 B.11 C.12 D.不確定在下列樹中，（ ）是完全二叉樹在一棵度為3的樹中，度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1，則度為0的結(jié)點個數(shù)為（ ）A.4B.5 C.6 D.7樹的基本遍歷策略分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。結(jié)論（ ）是正確的樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同樹的后根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同以上都不對在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（ ）A.e B.2e C.n2-eD.n2-2e線性表必須是（ ），才能進行二分查找。用順序存儲的無序表用鏈表存儲的有序表用鏈表存儲的無序表用順序存儲的有序表已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：據(jù)有向圖的廣度優(yōu)先遍歷算法，從頂點V1出發(fā)，所得到的頂點序列是（A.V1V2V3V4V5B.V1V2V3V5V4C.V1V3V2V4V5D.V1V4V3V2V5一個待排序文件的關(guān)鍵字如下：265301751129087863742694076438經(jīng)過（ ）趟直接插入排序后可得到如下序列：129265301751087863742694076438A.1 B.2 C.3 D.4對有18個元素的有序表做折半（二分）查找，則查找A[3]的比較序列的下標依次為（）。A,1-2-3 B.9-5-2-3 C.9-5-3D.9-4-2-3循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別為front和rear，則當(dāng)前元素個數(shù)為（）A.（rear-front+m）modmB.rear-front+1C.rear-front-1rear-frontE.以上答案都不對數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）A.存儲結(jié)構(gòu)B.物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)物理結(jié)構(gòu)和存儲結(jié)構(gòu)E.以上答案都不對在具有n個結(jié)點的單鏈表中，實現(xiàn)（）的操作，其算法的時間復(fù)雜度都是O（n）。A.遍歷鏈表和求鏈表的第i個結(jié)點 B.在地址為p的結(jié)點之后插入一個結(jié)點 C.刪除開始結(jié)點 D.刪除地址為p的結(jié)點的后繼結(jié)點E.以上答案都不對某二叉樹的前序遍歷序列為IJKLMNO，中序遍歷序列為JLKINMO，則后序遍歷序列為（）A.JLKMNOIB.LKNJOMIC.LKJNOMID.LKNOJMIE.以上答案都不對有n個結(jié)點的無向圖的邊數(shù)最多為（）A.n+1B.n（n-1）/2C.n（n+1）D.2n（n+1）E.以上答案都不對某順序存儲的表格中有90000個元素，已按關(guān)鍵字值額定升序排列，假定對每個元素進行查找的概率是相同的，且每個元素的關(guān)鍵字的值皆不相同。用順序查找法查找時，平均比較次數(shù)約為（）A.25000B.30000C.45000D.90000E.以上答案都不對下列排序算法中，第一趟排序完畢后，其最大或最小元素一定在其最終位置的算法是（）A.歸并排序B.直接插入排序C.快速排序冒泡排序E.以上答案都不對關(guān)于樹和二叉樹的有序性，正確的結(jié)論是（）A.樹和二叉樹都是有序的B.樹和二叉樹都可能是有序的C.樹和二叉樹都是無序的 D.二叉樹是有序的，樹可能是有序的，也可能是無序的以上答案都不對在一個圖中，所有頂點的度數(shù)之和與圖的邊數(shù)的比是（）A.1:2 B.1:1C.2:1 D.4:1E.以上答案都不對若一組紀錄的關(guān)鍵碼為（46,79,56,38,40,84），則利用快速排序的方法，以第一個紀錄為基準得到的一次劃分結(jié)果為（）A.38, 40, 46, 56,79,84 B. 40,38,46, 79, 56,84C.40, 38, 46, 56,79,84 D. 40,38,46, 84, 56,79以上答案都不對從理論上講，將數(shù)據(jù)以（）結(jié)構(gòu)存放，則查找一個數(shù)據(jù)所用時間不依賴于數(shù)據(jù)個數(shù)n。A.二叉查找樹 B.鏈表C.二叉樹D.哈希表E.以上答案都不對在非空循環(huán)雙鏈表中q所指的結(jié)點前插入一個由p所指結(jié)點的過程依次為：p->next=q；p->prior=q->prior；q->prior=p；（ ）；A.q->next=p B.q->prior->next=pC.p->prior->next=pp->next->prior=p E.以上答案都不對每個存儲結(jié)點只含有一個數(shù)據(jù)元素，存儲結(jié)點均勻地存放在連續(xù)的存儲空間，使用函數(shù)值對應(yīng)結(jié)點的存儲位置，該存儲方式是（ ）存儲方式A.順序B.鏈接C.索引D.散列E.以上答案都不對對于單鏈表形式的隊列，隊空的條件是（ ）A.F=R=nil B.F=R C.F尹nil且R=nil D.R—F=1以上答案都不對對于序列（49,38,65,97,76,13,27,50）按由小到大進行排序，（ ）是初始步長d=4的希爾排序法第一趟的結(jié)果。49,76,65,13,27,50,97,3813,27,38,49,50,65,76,9797,76,65,50,49,38,27,1349,13,27,50,76,38,65,97以上答案都不對樹中所有結(jié)點的度等于所有結(jié)點數(shù)加（）。A.0B.1 C.—1 D.2 E.以上答案都不對循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別為front和rear，則當(dāng)前元素個數(shù)為（）。A.（rear-front+m）modmB.rear-front+1C.rear-front-1D.rear-front以上答案都不對若線性表最常用的運算是查找第i個元素及其前驅(qū)的值，則采用（ ）存儲方式節(jié)省時間。A.單鏈表B-雙鏈表C.單循環(huán)連表 D.順序表以上答案都不對樹最適合用來表示（ ）A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間無聯(lián)系的數(shù)據(jù)D.元素之間有分支層次關(guān)系 E.以上答案都不對有n個結(jié)點的有向完全圖的邊數(shù)為（ ）A.n*nB.2n C.n（n-1）D.2n（n+1） E.以上答案都不對填空：設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f將依次入棧S,一個元素出棧后即進入隊列。若這6個元素出隊列的順序是b、d、c、f、e、a,則棧S的容量至少應(yīng)該是，上述過程才不會出錯。已知完全二叉樹的第4層（根結(jié)點為第1層）總共只有2個結(jié)點，則其葉子結(jié)點數(shù)是。數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無關(guān)，是獨立于計算機的。TOC\o"1-5"\h\z對n個元素的序列進行冒泡排序時，最少的比較次數(shù)是 。已知某二叉樹的后序遍歷序列是BEDCA,中序遍歷序列是BADEC，那么它的前序遍歷序列是 0在一個N個單元的順序棧中，假定以地址低端（下標為0的單元）作為棧底，以top作為棧頂指針，則向棧中壓入一個元素時，tOp指針的變化是：0在一個單鏈表中，若要刪除P所指結(jié)點的后繼結(jié)點，則執(zhí)行的語句序列 0帶頭結(jié)點的單鏈表head為空的判定條件是：。在長度為n的順序表的第i（1WiWn+1）個位置上插入一個元素，元素的移動次數(shù)為0

在長度為n的順序表的第i（1WiWn）個位置上刪除一個元素，元素的移動次數(shù)已知一棵完全二叉樹中共有768個結(jié)點，則該樹中共有個葉子結(jié)點。在有序表（12,24,36,48,60,72,84）中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為。寫出樹（見右圖）的先序遍歷序列。n個頂點的無向連通圖最少有條邊。有一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100}，當(dāng)二分查找值為9的結(jié)點時，經(jīng)過 次比較后查找成功。已知一棵完全二叉樹中共有768個結(jié)點，則該樹中共有個葉子結(jié)點。寫出右圖所示二叉樹按后序遍歷的結(jié)。寫出右圖所示二叉樹度為1的內(nèi)部結(jié)點的值有向圖G用鄰接矩陣A[1..n,1..n]存儲，其第i行的所有元素之和等于頂點i的（）。已知完全二叉樹的第8層有8個結(jié)點，則其葉子結(jié)點數(shù)是（）有n個頂點的強連通有向圖G至少有（）條弧。3個結(jié)點可構(gòu)成（）棵不同形態(tài)的樹。已知二叉樹中葉子數(shù)為50,僅有一個孩子的結(jié)點數(shù)為30,則總結(jié)點數(shù)是（）在按關(guān)鍵字遞增的數(shù)組A[1..20]中，按折半查找方法進行查找時，查找長度為5的元素個數(shù)是（ 數(shù)組A[1..10,1..10]的每個元素占1個單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[5,6]的地址為。兩個序列如下：L1={25,57,48,37,92,86,12,33}L2={25,37,33,12,48,57,86,92}用冒泡排序方法分別對序列 L1和L2進行排序，交換次數(shù)較少的是序列對于一個具有N個結(jié)點和E條邊的無向圖，若采用鄰接表表示，則頂點表的大小為

TOC\o"1-5"\h\z（ ），所有邊鏈表中邊結(jié)點的總數(shù)為（ ）。鏈表適用于（ ）查找。通常程序在調(diào)用另一個程序時，都需要使用一個（ ）來保存被調(diào)用程度內(nèi)分配的局部變量、形式參數(shù)的存儲空間以及返回地址。前序為abc且后序為cba的二叉樹共有（ ）棵。有n結(jié)點的二叉鏈表中，空指針域有（ ）個。在單鏈表中，申請到新結(jié)點 P，將p指向的結(jié)點后插到s所指結(jié)點的操作，其一是p->next=s->next，其二是（ ）。設(shè)二維數(shù)組A[10..20,5..10]按行優(yōu)先存儲，每個元素占4個單元，A[10,5]的地址為160，則A[15,10]的地址為（）。已知完全二叉樹的高度為8,第7層有10個葉子結(jié)點，則二叉樹的總結(jié)點數(shù)至少是（）。已知二叉樹有50個葉子結(jié)點，且僅有一個孩子的結(jié)點數(shù)為30，則總結(jié)點數(shù)為（）。從一棵二叉樹的前序序列和（ ）可唯一確定這棵二叉樹。設(shè)某二叉樹的后序遍歷為ABKCBPM，則可知該二叉樹的根為（）。設(shè)有一稠密圖G，則G采用（）存儲較省空間。分析:使用二叉鏈表表示法，畫出圖示二叉樹的存儲表示。畫出如圖所示的樹所對應(yīng)的二叉樹。

畫出如圖所示的樹所對應(yīng)的二叉樹。已給無向圖如下：要求：寫出該圖從頂點①開始的深度優(yōu)先和廣度優(yōu)先搜索序列。設(shè)右圖為某樹的二叉樹表示，請畫出該樹。一棵排序二叉樹結(jié)構(gòu)如下，各結(jié)點的值從小到大依次為1?8,請標出各結(jié)點的值。設(shè)右圖為某樹的二叉樹表示，請畫出該樹。已知一個無向圖的頂點集為｛a,b,c,d,e｝，其鄰接矩陣如下所示a01001b10010c00011d01101e10110（1） 根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，