李春葆數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析(修訂版)

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