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

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

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

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