李春葆數(shù)據(jù)結構習題與解析(修訂版)

李春葆編著：數(shù)據(jù)結構〔C語言篇〕――習題與解析〔修訂版〕清華大學出版社一、緒論選擇題1.數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的1以及它們之間的2和運算等的學科。1A.數(shù)據(jù)元素B.計算方法C.邏輯存儲D.數(shù)據(jù)映像2A.結構B.關系C.運算D.算法2.數(shù)據(jù)結構被形式地定義為(K,R)，其中K是1的有限集，R是K上的2有限集。1A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結構2A.操作B.映像C.存儲D.關系3.在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成。A.動態(tài)結構和靜態(tài)結構B.緊湊結構和非緊湊結構C.線性結構和非線性結構D.內部結構和外部結構4.線性結構的順序存儲結構是一種1的存儲結構，線性表的鏈式存儲結構是一種2的存儲結構。A.隨機存取B.順序存取C.索引存取D.散列存取5.算法分析的目的是1，算法分析的兩個主要方面是2。1A.找出數(shù)據(jù)結構的合理性B.研究算法中的輸入和輸出的關系C.分析算法的效率以求改良D.分析算法的易懂性和文檔性2A.空間復雜度和時間復雜度B.正確性和簡單性C.可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性6.計算機算法指的是1，它必須具備輸入、輸出和2等5個特性。1A.計算方法B.排序方法C.解決問題的有限運算序列D.調度方法2A.可執(zhí)行性、可移植性和可擴充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和平安性7.線性表的邏輯順序與存儲順序總是一致的，這種說法。A.正確B.不正確8線性表假設采用鏈式存儲結構時，要求內存中可用存儲單元的地址。A.必須連續(xù)的B.局部地址必須連續(xù)的C.一定是不續(xù)的D連續(xù)不連續(xù)都可以9.以下的表達中，正確的選項是。A.線性表的存儲結構優(yōu)于鏈式存儲結構B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進先出D.隊列的操作方式是先進后出10.每種數(shù)據(jù)結構都具備三個根本運算：插入、刪除和查找，這種說法。A.正確B.不正確填空題1.數(shù)據(jù)邏輯結構包括三種類型、和，樹形結構和圖形結構合稱為。2.在線性結構中，第一個結點前驅結點，其余每個結點有且只有個前驅結點；最后一個結點后續(xù)結點，其余每個結點有且只有個后續(xù)結點。3.在樹形結構中，樹根結點沒有結點，其余每個結點有且只有個前驅結點；葉子結點沒有結點，其余每個結點的后續(xù)可以。4.在圖形結構中，每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以。5.線性結構中元素之間存在關系，樹形結構中元素之間存在關系，圖形結構中元素之間存在關系。6.算法的五個重要特性是、、、、。7.下面程序段的時間復雜度是。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;8.下面程序段的時間復雜度是。i=s=0;while(s<n){i++;/*i=i+1*/s+=i;/*s=s+i*/}9.下面程序段的時間復雜度是。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;10.下面程序段的時間復雜度是。i=1;while(i<=n)i=i*3;二、線性表單項選擇題1.一個向量第一個元素的存儲地址是100，每個元素的長度為2，那么第5個元素的地址是。A.110B.108C.100D.1202.一個棧的入棧序列是a、b、c、d、e，那么棧的不可能輸出序列是。A.edcbaB.decbaC.dceabD.abcde3.假設一個棧的入棧序列是1、2、3、…、n，其輸出序列為p1、p2、p3、…、pn，假設p1=n，那么pi為。A.iB.n=iC.n-i+1D.不確定4.棧結構通常采用的兩種存儲結構是。A.線性存儲結構和鏈表存儲結構B.散列方式和索引方式C.鏈表存儲結構和數(shù)組D.線性存儲結構和非線性存儲結構5.判斷一個棧ST(最多元素為m)為空的條件是。A.ST->top!=0B.ST->top==0C.ST->top!=mD.ST6.判斷一個棧ST(最多元素為m)為滿棧的條件是。A.ST->top!=0B.ST->top==0C.ST7.棧的特點是1，隊列的特點是2。A.先進先出B.先進后出8.一個隊列的入隊序列是1、2、3、4，那么隊列輸出序列是。A.4、3、2、1B.1、2、3、4C.1、4、3、2D.3、2、4、19.判斷一個隊列QU(最多元素為m)為空的條件是。A.QU->rear－QU->front==mB.QU->rear－QU->front－1==mC.QU->front==QU->rearD.QU->front－QU->rear+110.判斷一個隊列QU(最多元素為m)為滿隊列的條件是。A.QU->rear－QU->front==mB.QU->rear－QU->front－1==mC.QU->front==QU->rearD.QU->front－QU->rear+111.判斷一個循環(huán)隊列QU(最多元素為m)為空的條件是。A.QU->front==QU->rearB.QU->front!=QU->rearC.QU->front==(QU->rear+1)%mD.QU->front!=(QU->rear+1)%m12.判斷一個循環(huán)隊列QU(最多元素為m)為滿隊列的條件是。A.QU->front==QU->rearB.QU->front!=QU->rearC.QU->front==(QU->rear+1)%mD.QU->front!=(QU->rear+1)%m13循環(huán)隊列用數(shù)組A[0,m-1]存放其元素值，其頭尾指針分別是front和rear，那么當前隊列中的元素個數(shù)是。A.(rear－front+m)%mB.rear－front+1C.rear－front－1D.rear－front14.棧和隊列的共同點是。A.都是先進后出B.都是先進先出C.只允許在端點處插入、刪除元素D.沒有共同點填空題1.向量、棧和隊列都是結構，可以在向量的位置插入和刪除元素；對于棧只能在插入和刪除元素；對于隊列只能在插入元素和刪除元素。2.在一個長度為n的向量中的第i個元素(1≤i≤n)之前插入一個元素時，需向后移動個元素。3.在一個長度為n的向量中的刪除第i個元素(1≤i≤n)時，需要向前移動個元素。4.向棧中壓入元素的操作是。5.對棧進行退棧時的操作是。6.在一個循環(huán)隊列中，隊首指針指向隊首元素的。7.從循環(huán)隊列中刪除一個元素時，其操作是。8.在具有n個單元的循環(huán)隊列中，隊滿時共有個元素的。9.一個棧的輸入序列是12345，那么棧的輸出序列43512是。10.一個棧的輸入序列是12345，那么棧的輸出序列12345是。三、鏈表單項選擇題1.不帶頭結點的單鏈表head為空的判定條件是。A.head==NULLB.head->nxt==NULLC.head->next==headD.head!=NULL2.帶頭結點的單鏈表head為空的判定條件是。A.head==NULLB.head->nxt==NULLC.head->next==headD.head!=NULL3.非空的循環(huán)單鏈表head的尾結點〔由p所指向〕滿足。A.p->next==NULLB.p==NULLC.p->next==headD.p==head4.在循環(huán)雙鏈表的p所指結點之后插入s所指結點的操作是。A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;5.在一個單鏈表中，q所指結點是p所指結點的前驅結點，假設在q和p之間插入s結點，那么執(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;6.在一個單鏈表中，p所指結點不是最后結點，在p之后插入s所指結點，那么執(zhí)行。A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;C.s->next=p->next;p=s;D.p->next=s;s->next=p;7.在一個單鏈表中，假設刪除p所指結點的后續(xù)結點，那么執(zhí)行。A.p->next=p->next->next;B.p=p->next;p->next=p->next->next;C.p->next=p->next;D.p=p->next->next;9.從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比擬個結點。A.nB.n/2C.(n-1)/2D.(n+1)/210.在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)11.給定有n個元素的向量，建立一個有序單鏈表的時間復雜度是。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)12.向一個棧頂指針為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;13.從一個棧頂指針為HS的鏈棧中刪除一個結點，用x保存被刪除結點的值，那么執(zhí)行。A.x=HS;HS=HS->next;B.x=HS->data;C.HS=HS->next;x=HS->data;D.x=HS->data;HS=HS->next;14.在一個鏈隊中，假設f和r分別為隊首和隊尾指針，插入s所指結點，那么執(zhí)行。A.f->next=s;f=s;B.r->next=s;r=s;C.s->next=r;r=s;D.s->next=f;f=s;15.在一個鏈隊中，假設f和r分別為隊首和隊尾指針，刪除一個結點，那么執(zhí)行。A.r=f->next;B.r=r->next;C.f=f->next;D.f=r->next;填空題1.單鏈表是的鏈接存儲表示。2.可以使用表示樹形結構。3.在雙鏈表中，每個結點有兩個指針域，一個指向，另一個指向。4.在一個單鏈表中，p所指結點之前插入s所指向結點，可執(zhí)行如下操作：〔1〕s->next=；〔2〕p->next=s；〔3〕t=p->data；〔4〕p->data=；〔5〕s->data=；5.在一單鏈表中，刪除p所指結點時，應執(zhí)行以下操作：〔1〕q=p->next；〔2〕p->data=p->next->data；〔3〕p->next=；〔4〕free(q)；6.帶頭結點的單鏈表head為空的條件是。7.在一個單鏈表中，p所指結點之后插入s所指向結點，應執(zhí)行s->next=和p->next=的操作。8.非空的循環(huán)單鏈表head的尾結點〔由p所指向〕，滿足。9.在棧頂指針為HS的鏈棧中，判定棧空的條件是。10.在棧頂指針為HS的鏈棧中，計算該鏈棧中結點個數(shù)的函數(shù)是。11.在HQ的鏈隊中，判定只有一個結點的條件是。12.在HQ的鏈隊中，計算該棧鏈中結點個數(shù)的函數(shù)是。四、串單項選擇題1.空串與空格串是相同的，這種說法。A.正確B.不正確2.串是一種特殊的線性表，其特殊性表達在。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符3.設兩個字符串p和q，求q在p中首次出現(xiàn)的位置的運算稱作。A.連接B.模式匹配C.求子串D.求串長4.設串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x與y串的連接串，函數(shù)subs(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，函數(shù)len(s)返回串s的長度，那么con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結果串是。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF填空題1.串的兩種最根本的存儲方式是。2.兩個串相等的充分必要條件是。3.空串是，其長度等于。4.空格串是，其長度等于。5.設s=‘IAMATEACHER’，其長度是。6.設s1=‘GOOD’，s2=‘’，s3=‘BYE!’，那么s1、s2和s3連接后的結果是。五、數(shù)組與稀疏矩陣單項選擇題1.常對數(shù)組進行的兩種根本操作是。A.建立與刪除B.索引和修改C.查找和修改D.查找與索引2.二維數(shù)組M的成員是6個字符〔每個字符占一個存儲單元〕組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，那么存放M至少需要1個字節(jié)；M的第8列和第5行共占2個字節(jié)；假設M按行優(yōu)先方式存儲，元素M[8][5]的起始地址與當M按列優(yōu)先方式存儲時的3元素的起始地址一致。1A.90B.180C.240D.5402A.108B.114C.54D.603A.M[8][5]B.M[3][10]C.M[5][8]D.M[0][9]3.二維數(shù)組M的成員是4個字符〔每個字符占一個存儲單元〕組成的串，行下標i的范圍從0到4，列下標j的范圍從0到5，M按行存儲時元素M[3][5]的起始地址與M按列存儲時元素的元素的起始地址一致。A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][4]4.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內，存放該數(shù)組至少需要的單元素是。A.80B.120C.240D.2705.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內，該數(shù)組按行存放時，元素A[8][5]的起始地址為。A.SA+141B.SA+144C.SA+222D.SA+2256.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內，該數(shù)組按列存放時，元素A[5][8]的起始地址為。A.SA+141B.SA+180C.SA+222D.SA+2257.稀疏矩陣一般的壓縮存儲方法有兩種，即。A.二維數(shù)組和三維數(shù)組B.三元組與散列C.三元組與十字鏈表D.散列和十字鏈表8.假設用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置運算，這種觀點。A.正確B.不正確9.設矩陣A是一個對稱矩陣，為節(jié)省存儲，將其下三角局部按行序存放在一信數(shù)組B[1,n(n-1)/2]中，對下三角局部中任一元素aij(i≥j)，在一組數(shù)組B的下標位置k的值是。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j填空題1.二維數(shù)組A[m][n]采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC(A[0][0])，那么A[i][j]的地址是。2.二維數(shù)組A[10][20]采用列序為主方式存儲，每個元素占一個存儲單元，并且A[0][0]的存儲地址是200，那么A[6][10]的地址是。3.二維數(shù)組A[10..20][5..20]采用行序為主方式存儲，每個元素占4個存儲單元，并且A[10][5]的存儲地址是1000，那么A[18][9]的地址是。4.有一個10階對稱矩陣A，采用壓縮存儲方式〔以行為主存儲，且LOC(A[0][0])=1〕，那么A[8][5]的地址是。5.設n行n列的下三角矩陣A已壓縮到一維數(shù)組S[1..n*(n+1)/2]中，假設按行序為主存儲，那么A[i][j]對應的S中的存儲位置是。6.一個稀疏矩陣如下圖，那么對應的三元數(shù)組表示為。八、樹形結構單項選擇題1.如下圖的4棵二叉樹中，不是完全二叉樹。3.在線索化二叉樹中，t所指結點沒有左子樹的充要條件是。A.t->left==NULLB.t->ltag==1C.t->ltag==1且t->left==NULLD.以上都不對4.二叉樹按某種順序線索化后，任一結點均有指向其前趨和后繼的線索，這種說法。A.正確B.錯誤5.二叉樹的前序遍歷序列中，任意一個結點均處在其子女結點的前面，這種說法。A.正確B.錯誤6.由于二叉樹中每個結點的度最大為2，所以二叉樹是一種特殊的樹，這種說法。A.正確B.錯誤7.設高度為h的二叉樹上只有度為0和度為2的結點，那么此類二叉樹中所包含的結點數(shù)至少為。A.2hB.2h-1C.2h+1D.h+18.如下圖二叉樹的中序遍歷序列是。A.abcdgefB.dfebagcC.dbaefcgD.defbagc9.某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列是。A.acbedB.decabC.deabcD.cedba10.如果T2是由有序樹T轉換而來的二叉樹，那么T中結點的前序就是T2中結點的。A.前序B.中序C.后序D.層次序11.如果T2是由有序樹T轉換而來的二叉樹，那么T中結點的后序就是T2中結點的。A.前序B.中序C.后序D.層次序12某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷結點訪問順序是dgbaechf，那么其后序遍歷結點訪問順序是。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca13.二叉樹為二叉排序樹的充分必要條件是任一結點的值均大于其左孩子的值、小于其右孩子的值，這種說法。A.正確B.錯誤14.按照二叉樹的定義，具有3個結點的二叉樹有種。A.3B.4C.5D.615.如下圖二叉樹的中序遍歷序列是。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh16.樹的根本遍歷策略可分為先根遍歷和后根遍歷；二叉樹根本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這時，我們把由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。結論是正確的。A.樹的先根遍歷序列與二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與二叉樹的后序遍歷序列相同C.樹的先根遍歷序列與二叉樹的中序遍歷序列相同D.以上都不對17.深度為5的二叉樹至多有個結點。A.16B.32C.31D.1018.在一非空二叉樹的中序遍歷序列中，根結點的右邊。A.只有右子樹上的所有結點B.只有右子樹上的局部結點C.只有左子樹上的所有結點D.只有左子樹上的局部結點19.樹最適合用來表示。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)20任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對21.實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結構，最正確方案是二叉樹采用存儲結構。A.二叉鏈表B.廣義表存儲結構C.三叉鏈表D.順序存儲結構22.對于一個滿二叉樹，m個樹葉，n個結點，深度為h，那么。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-123.如果某二叉樹的前序為stuwv，中序為uwtvs，那么該二叉樹的后序。A.uwvtsB.vwutsC.wuvtsD.wutsv25.如下圖的T2是由有序樹T1轉換而來的二叉樹，那么樹T1有個葉結點。A.4B.5C.6D.726.設n、m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是。A.n在m右方B.n是m祖先C.n在m左方D.n是m子孫27.線索二叉樹是一種結構。A.邏輯B.邏輯和存儲C.物理D.線性填空題1.有一棵樹如下圖，答復下面問題：〔1〕這棵樹的根結點是；〔2〕這棵樹的葉子結點是；〔3〕結點c的度是；〔4〕這棵樹的度是；〔5〕這棵樹的深度是；〔6〕結點c的子女是；〔7〕結點c的父母結點是。2.指出樹和二叉樹的三個主要差異、、。3.從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結構，將樹轉化為二叉樹的根本目的是。4.一棵二叉樹的結點數(shù)據(jù)采用順序存儲結構，存儲于數(shù)組T中，如下圖，那么該二叉樹的鏈接表示形式為。123456789101112131415161718192021eafdgcjihb5.深度為k的完全二叉樹至少有個結點，至多有個結點，假設按自上而下、從左到右次序給結點編號〔從1開始〕，那么編最小的葉子結點的編號是。6.在一棵二叉樹中，度為零的結點的個數(shù)為n0，度為2的結點的個數(shù)為n2，那么有n0=。7.一棵二叉樹的第k層最多有個結點；一棵有n個結點的滿二叉樹共有個葉子和個非終端結點。8.結點最少的樹為，結點最少的二叉樹為。9.現(xiàn)有按中序遍歷二叉樹的結果是abc，問有種不同形態(tài)的二叉樹可以得到這一遍歷結果，這些二叉樹分別是。10.根據(jù)二叉樹的定義，具有三個結點的二叉樹有種不同的形態(tài)，它們分別是。11.由如下圖的二叉樹，答復以下問題：〔1〕其中序遍歷序列；〔2〕其前序遍歷序列；〔3〕其后序遍歷序列；〔4〕該二叉樹的中序線索二叉樹為；〔5〕該二叉樹的后序線索二叉樹為；〔6〕該二叉樹對應的森林是。12.一棵樹如下圖，其孩子兄弟表示為。13.以數(shù)據(jù)集｛4，5，6，7，10，12，18｝為結點權值所構造的哈夫曼樹為，其帶權路徑長度為。九、圖1.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的倍。A.1/2B.1C.2D.42.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度這和倍。A.1/2B.1C.2D.43.一個有n個頂點的無向圖最多有條邊。A.nB.n(n-1)C.n(n-1)/2D.2n4.具有4個頂點的無向完全圖有條邊。A.6B.12C.16D.205.具有6個頂點的無向圖至少應有條邊才能確保是一個連通圖。A.5B.6C.7D.86.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要條邊。A.nB.n+1C.n-1D.n/27.對于一個具有n個頂點的無向圖，假設采用鄰接矩陣表示，那么該矩陣的大小是。A.nB.(n-1)2C.n-1D.n8.對于一個具有n個頂點和e條邊的無向圖，假設采用鄰接矩陣表示，那么表頭向量的大小是1；所有鄰接矩陣中的結點總數(shù)是2。1A.nB.n+1C.n-1D.n+e2A.e/2B.eC.2eD.n+e9.一個圖如下圖，假設從頂點a出發(fā)按深度搜索法進行遍歷，那么可得到頂點序列為1；按寬度搜索法進行遍歷，那么可得到頂點序列為2。1A.abecdfB.acfebdC.aebcfdD.aedfcb2A.abcedfB.abcefdC.aebcfdD.acfdeb10.一有向圖的鄰接表存儲結構如下圖〔1〕根據(jù)有向圖的深度優(yōu)先遍歷算法，從v1頂點出發(fā)，所得到的頂點序列是1?！?〕根據(jù)有向圖的寬度優(yōu)先遍歷算法，從v1頂點出發(fā)，所得到的頂點序列是2。1A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v22A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v211.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的。A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷12.采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的。A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷13.判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用。A.求關鍵路徑方法B.求最短路徑的Dijkstra方法C.寬度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法填空題1.n個頂點的連通圖至少條邊。2.在無權圖G的鄰接矩陣中，假設(vi,vj)或<vi,vj>屬于圖G的邊集，那么對應元素A[i][j]等于，否那么等于。3.在無權圖G的鄰接矩陣中，假設A[i][j]等于1，那么等于A[j][i]=。4.圖G的鄰接表如下圖，其從v1頂點出發(fā)的深度優(yōu)先搜索序列為，其從v1頂點出發(fā)的寬度優(yōu)先搜索序列為。5.一圖的鄰接矩陣表示，計算第i個結點的入度的方法是。6.一圖的鄰接矩陣表示，刪除所有從第i個結點出發(fā)的邊的方法是。十、查找單項選擇題1.順序查找法適合于存儲結構為的線性表。A.散列存儲B.順序存儲或鏈接存儲C.壓縮存儲D.索引存儲2.對線性表進行二分查找時，要求線性表必須。A.以順序方式存儲B.以順序方式存儲，且結點按關鍵字有序排列C.以鏈接方式存儲D.以鏈接方式存儲，且結點按關鍵字有序排列3.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為。A.nB.n/2C.(n+1)/2D.(n-1)/24.采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為。A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)5.二分查找和二叉排序樹的時間性能。A.相同B.不相同6.有一個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當二分查找值為82的結點時，次比擬后查找成功。A.1B.2C.4D.87.設哈希表長m=14，哈希函數(shù)H(key)=key%11。表中有4個結點：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空如用二次探測再散列處理沖突，關鍵字為49的結點的地址是。A.8B.3C.5D.98.有一個長度為12的有序表，按二分查找法對該表進行查找，在表內各元素等概率情況下查找成功所需的平均比擬次數(shù)為。A.35/12B.37/12C.39/12D.43/129.采用分塊查找時，假設線性表中共有625個元素，查找每個元素的概率相同，假設采用順序查找來確定結點所在的塊時，每塊應分個結點最正確地。A.10B.25C.6D.62510.如果要求一個線性表既能較快地查找，又能適應動態(tài)變化的要求，可以采用查找方法。A.分塊B.順序C.二分D.散列填空題1.順序查找法的平均查找長度為；二分查找法的平均查找長度為；分塊查找法〔以順序查找確定塊〕的平均查找長度為；分塊查找法〔以二分查找確定塊〕的平均查找長度為；哈希表查找法采用鏈接法處理沖突時的平均查找長度為。2.在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是。3.二分查找的存儲結構僅限于，且是。4.在分塊查找方法中，首先查找，然后再查找相應的。5.長度為255的表，采用分塊查找法，每塊的最正確長度是。6.在散列函數(shù)H(key)=key%p中，p應取。7.假設在有序線性表A[1..20]上進行二分查找，那么比擬一次查找成功的結點數(shù)為，那么比擬二次查找成功的結點數(shù)為，那么比擬三次查找成功的結點數(shù)為，那么比擬四次查找成功的結點數(shù)為，那么比擬五次查找成功的結點數(shù)為，平均查找長度為。8.對于長度為n的線性表，假設進行順序查找，那么時間復雜度為；假設采用二分法查找，那么時間復雜度為；假設采用分塊查找〔假設總塊數(shù)和每塊長度均接近n1/2〕，那么時間復雜度為。9.在散列存儲中，裝填因子α的值越大，那么；α的值越小，那么。十一、內排序1.在所有排序方法中，關鍵字比擬的次數(shù)與記錄的初始排列次序無關的是。A.希爾排序B.起泡排序C.插入排序D.選擇排序2.設有1000個無序的元素，希望有最快的速度挑選出其中前10個最大的元素，最好采用排序法。A.起泡排序B.快速排序C.堆排序D.基數(shù)排序3.在待排序的元素序列根本有序的前提下，效率最高的排序方法是。A.插入排序B.選擇排序C.快速排序D.歸并排序4.一組記錄的排序碼為〔46，79，56，38，40，84〕，那么利用堆排序方法建立的初始堆為。A.79，46，56，38，40，80B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，385.一組記錄的排序碼為〔46，79，56，38，40，84〕，那么利用快速排序方法，以第一個記錄為基準得到的一次劃分結果為。A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，796.一組記錄的排序碼為〔25，48，16，35，79，82，23，40，36，72〕，其中含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為。A.16253548234079823672B.16253548798223364072C.16254835798223364072D.162535487923364072827.排序方法中，從未排序序列中依次取出元素與已排序序列〔初始時為空〕中的元素進行比擬，將其放入已排序序列的正確位置上的方法，稱為。A.希爾排序B.起泡排序C.插入排序D.選擇排序8.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列〔初始時為空〕的一端的方法，稱為。A.希爾排序B.歸并排序C.插入排序D.選擇排序9.用某種排序方法對線性表〔25，84，21，47，15，27，68，35，20〕進行排序時，元素序列的變化情況如下：〔1〕25，84，21，47，15，27，68，35，20〔2〕20，15，21，25，47，27，68，35，84〔3〕15，20，21，25，35，27，47，68，84〔4〕15，20，21，25，27，35，47，68，84那么采用的排序方法是。A.選擇排序B.希爾排序C.歸并排序D.快速排序10.以下幾種排序方法中，平均查找長度最小的是。A.插入排序B.選擇排序C.快速排序D.歸并排序11.以下幾種排序方法中，要求內存量最大的是。A.插入排序B.選擇排序C.快速排序D.歸并排序12.快速排序方法在情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個值C.要排序的數(shù)據(jù)已根本有序D.要排序的數(shù)據(jù)個數(shù)為奇數(shù)填空題1.在對一組記錄〔54，38，96，23，15，72，60，45，83〕進行直接插入排序時，當把第七個記錄60插入到有序表時，為尋找插入位置需比擬次。2.在利用快速排序方法對〔54，38，96，23，15，72，60，45，83〕進行快速排序時，遞歸調用而使用的棧的所能到達的最大深度為，共需遞歸調用的次數(shù)為，其中第二次遞歸調用是對一組記錄進行快速排序。3.在堆排序、快速排序和歸并排序中，假設只從存儲空間考慮，那么應首先選取方法，其次選取方法，最后選取方法；假設只從排序結果的穩(wěn)定性考慮，那么應選取方法；假設只從平均情況下排序最快考慮，那么應選取方法；假設從最壞情況下排序最快并且要節(jié)省內存考慮，那么應選取方法。4.在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有。5.在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比擬次數(shù)最少的排序是，需要內存量最多的是。6.在堆排序和快速排序中，假設原始記錄接近正序或反序，那么選用，假設原始記錄無序，那么選用。7.在插入排序和選擇排序中，假設初始數(shù)據(jù)根本正序，那么選用，假設初始數(shù)據(jù)根本反序，那么選用，8.對n個元素的序列進行起泡排序時，最少的比擬次數(shù)是。答案緒論選擇題：1.A.B。2.B.D。3.C。4.A.B。5.C.A+B。6.C.B。7.B。8.D。9.B。10.B。填空題：1.線性結構，樹形結構，圖形結構，非線性結構。2.沒有，1，沒有，1。前驅，1，后續(xù)，任意多個。4.任意多個。5.一對一，一對多，多對多。6.有窮性，確定性，可行性，輸入，輸出。7.O〔m*n〕。8.O〔n〕。9.O〔n2〕。10.O〔log3n〕。二、線性表選擇題：1.B。2.C。3.C。4.A。5.B。6.D。7.B，A。8.B。9.C。10.A。11.A。12.C。13.A。14.C。填空題：1.線性，任何，棧頂，隊尾，隊首。2.n-i+1。3.n-i。4.先棧頂指針，后存入元素。5.先取出元素，后移動棧頂指針。6.前一個位置。7.先移動隊首元素，后取出元素。8.n-1。9.不可能的。10.可能的。三、鏈表選擇題：1.A。2.B。3.C。4.D。5.C。6.B。7.A。9.D。10.B。11.C。12.C。13.D。14.B。15.C。填空題：1.線性表。2.雙鏈表。3.前驅結點，后續(xù)結點。4.p->next，s->data，t。5.p->next->next。6.head->next==NULL。7.p->next，s。8.h