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

、緒論選擇題1.數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題計(jì)算機(jī)的—以及它們之間的—和運(yùn)算等的學(xué)科。1A.數(shù)據(jù)元素B.計(jì)算方法2算等的學(xué)科。1A.數(shù)據(jù)元素B.計(jì)算方法2A.結(jié)構(gòu)B.關(guān)系2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K,R）A.算法A.操作B.數(shù)據(jù)元素B.映像C.邏輯存儲(chǔ) D.數(shù)據(jù)映像C.運(yùn)算 D.算法其中K是—的有限集，R是K上的—有限集。C.數(shù)據(jù)操作 D.邏輯結(jié)構(gòu)C.存儲(chǔ) D.關(guān)系.在數(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).線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種—的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種—的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取 B.順序存取 C.索引存取 D.散列存取.算法分析的目的是一，算法分析的兩個(gè)主要方面是一。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性A.找出數(shù)據(jù)結(jié)構(gòu)的合理性C.分析算法的效率以求改進(jìn)A.空間復(fù)雜度和時(shí)間復(fù)雜度C.可讀性和文檔性8.研究算法中的輸入和輸出的關(guān)系D.分析算法的易懂性和文檔性B.正確性和簡(jiǎn)單性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性B.可行性、確定性和有窮性D.B.可行性、確定性和有窮性D.易讀性、穩(wěn)定性和安全性7.線性表的邏輯順序與存儲(chǔ)順序總是A.正確一致的，這種說(shuō)法B.不正確.計(jì)算機(jī)算法指的是一，它必須具備輸入、輸出和一等5個(gè)特性。A.計(jì)算方法 B.排序方法 C.解決問(wèn)題的有限運(yùn)算序列 D.調(diào)度方法A.可執(zhí)行性、可移植性和可擴(kuò)充性C.確定性、有窮性和穩(wěn)定性TOC\o"1-5"\h\z8線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址 。A.必須連續(xù)的B.部分地址必須連續(xù)的C.一定是不續(xù)的D連續(xù)不連續(xù)都可以.以下的敘述中，正確的是 。A.線性表的存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進(jìn)先出 D.隊(duì)列的操作方式是先進(jìn)后出.每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找，這種說(shuō)法 。A.正確 B.不正確填空題.數(shù)據(jù)邏輯結(jié)構(gòu)包括三種類(lèi)型 、和，樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱(chēng)為。.在線性結(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)。.在樹(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ù)可以。.在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 。.線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。.算法的五個(gè)重要特性是.下面程序段的時(shí)間復(fù)雜度是for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;.下面程序段的時(shí)間復(fù)雜度是 =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ù)雜度是=1;while（i<=n）i=i*3;二、線性表單項(xiàng)選擇題.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是一A.110 B.108 C.100 D.120.一個(gè)棧的入棧序列是a、b、c、d、e，則棧的不可能輸出序列是。A.edcbaB.decbaC.dceabD.abcde.若一個(gè)棧的入棧序列是1、2、3、…、n，其輸出序列為p「p2、p3、…、pn，若p1=n，則pi為。A.i B.n=iC.n-i+1 D.不確定TOC\o"1-5"\h\z.棧結(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).判斷一個(gè)棧ST（最多元素為m）為空的條件是 。A.ST->top!=0B.ST->top==0C.ST->top!=mD.ST->top==m.判斷一個(gè)棧ST（最多元素為m）為滿棧的條件是 。A.ST->top!=0B.ST->top==0C.ST->top!=m-1D.ST->top==m-1.棧的特點(diǎn)是，隊(duì)列的特點(diǎn)是」_。A.先進(jìn)先出 B.先進(jìn)后出.一個(gè)隊(duì)列的入隊(duì)序列是1、2、3、4,則隊(duì)列輸出序列是 。A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1.判斷一個(gè)隊(duì)列QU（最多元素為m）為空的條件是 。A.QU->rear－QU->front==m B.QU->rear－QU->front－1==mC.QU->front==QU->rear D.QU->front－QU->rear+1TOC\o"1-5"\h\z.判斷一個(gè)隊(duì)列QU(最多元素為m)為滿隊(duì)列的條件是 。A.QU->rear－QU->front==m B.QU->rear－QU->front－1==mC.QU->front==QU->rear D.QU->front－QU->rear+11L判斷一個(gè)循環(huán)隊(duì)列QU(最多元素為m)為空的條件是 。A.QU->front==QU->rear B.QU->front != QU->rearC.QU->front==(QU->rear+1) %m D.QU->front !=(QU->rear+1) %m12.判斷一個(gè)循環(huán)隊(duì)列QU(最多元素為m)為滿隊(duì)列的條件是 。A.QU->front==QU->rear B.QU->front != QU->rearC.QU->front==(QU->rear+1) %m D.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)%m B.rear－front+1 C.rear－front－1 D.rear－front14.棧和隊(duì)列的共同點(diǎn)是 。A.都是先進(jìn)后出 B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入、刪除元素 D.沒(méi)有共同點(diǎn)填空題.向量、棧和隊(duì)列都是 結(jié)構(gòu)，可以在向量的位置插入和刪除元素；對(duì)于棧只能在 插入和刪除元素;對(duì)于隊(duì)列只能在 插入元素和刪除元素。.在一個(gè)長(zhǎng)度為n的向量中的第i個(gè)元素(1WiWn)之前插入一個(gè)元素時(shí)，需向后移動(dòng)個(gè)元素。.在一個(gè)長(zhǎng)度為n的向量中的刪除第i個(gè)元素(1WiWn)時(shí)，需要向前移動(dòng) 個(gè)元素。TOC\o"1-5"\h\z.向棧中壓入元素的操作是 。.對(duì)棧進(jìn)行退棧時(shí)的操作是 。.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 。.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是 。.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 個(gè)元素的。.一個(gè)棧的輸入序列是12345,則棧的輸出序列43512是 。.一個(gè)棧的輸入序列是12345,則棧的輸出序列12345是 。三、鏈表單項(xiàng)選擇題.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 。A.head==NULL B.head->nxt==NULL C.head->next==head D.head!=NULL.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 。A.head==NULL B.head->nxt==NULL C.head->next==head D.head!=NULL.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足。A.p->next==NULLB.p==NULLC.p->next==headD.p==head.在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是 。p->right=s;s->left=p;p->right->left=s;s->right=p->right;p->right=s;p->right->left=s;s->left=p;s->right=p->right;s->left=p;s->right=p->right;p->right=s;p->right->left=s;s->left=p;s->right=p->right;p->right->left=s;p->right=s;.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行。TOC\o"1-5"\h\zA.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;.在一個(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;.在一個(gè)單鏈表中，若刪除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;.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較個(gè)結(jié)點(diǎn)。A.nB.n/2 C.(n-1)/2D.(n+1)/2.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是 。A.O(1) B.O(n) C.O(n2) D.O(nlog2n).給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是 。A.O(1) B.O(n) C.0(n2) D.O(nlog2n).向一個(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;.從一個(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;.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，插入s所指結(jié)點(diǎn)，則執(zhí)行。TOC\o"1-5"\h\zA.f->next=s;f= s; B.r->next=s;r =s;C.s->next=r;r= s; D.s->next=f;f =s;.在一個(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;填空題.單鏈表是 的鏈接存儲(chǔ)表示。.可以使用表示樹(shù)形結(jié)構(gòu)。.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向，另一個(gè)指向。.在一個(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=；.在一單鏈表中，刪除p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：(1)q=p->next；(2)p->data=p->next->data；(3)p->next=；(4)free(q)；.帶頭結(jié)點(diǎn)的單鏈表head為空的條件是。.在一個(gè)單鏈表中，p所指結(jié)點(diǎn)之后插入s所指向結(jié)點(diǎn)，應(yīng)執(zhí)行s->next=和p->next=的操作。TOC\o"1-5"\h\z.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)，滿足 。.在棧頂指針為HS的鏈棧中，判定?？盏臈l件是 。.在棧頂指針為HS的鏈棧中，計(jì)算該鏈棧中結(jié)點(diǎn)個(gè)數(shù)的函數(shù)是 。.在HQ的鏈隊(duì)中，判定只有一個(gè)結(jié)點(diǎn)的條件是 。.在HQ的鏈隊(duì)中，計(jì)算該棧鏈中結(jié)點(diǎn)個(gè)數(shù)的函數(shù)是 。四、串單項(xiàng)選擇題.空串與空格串是相同的，這種說(shuō)法。A.正確 B.不正確.串是一種特殊的線性表，其特殊性體現(xiàn)在 。A.可以順序存儲(chǔ) B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ) D.數(shù)據(jù)元素可以是多個(gè)字符.設(shè)兩個(gè)字符串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)作。A.連接 B.模式匹配 C.求子串 D.求串長(zhǎng)TOC\o"1-5"\h\z.設(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填空題.串的兩種最基本的存儲(chǔ)方式是 。.兩個(gè)串相等的充分必要條件是 。.空串是 ，其長(zhǎng)度等于 。.空格串是 ，其長(zhǎng)度等于 。.設(shè)s='IAMATEACHER'，其長(zhǎng)度是 。.設(shè)s1=‘GOOD'，s2=' ’，s3=‘BYE!’，則Us1、s2和s3連接后的結(jié)果是 。五、數(shù)組與稀疏矩陣單項(xiàng)選擇題.常對(duì)數(shù)組進(jìn)行的兩種基本操作是 。A.建立與刪除 B.索引和修改 C.查找和修改 D.查找與索引.二維數(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é)；若M按行優(yōu)先方式存儲(chǔ)，元素M[8][5]的起始地址與當(dāng)M按列優(yōu)先方式存儲(chǔ)時(shí)的二_元素的起始地址一致。A.90 B.180 C.240 D.540A.108 B.114 C.54 D.60A.M[8][5] B.M[3][10] C.M[5][8] D.M[0][9].二維數(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].數(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.240 D.270.數(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+222 D,SA+225.數(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+222 D,SA+2257,稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即。A.二維數(shù)組和三維數(shù)組 B,三元組與散列C.三元組與十字鏈表 D.散列和十字鏈表8?若用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)。A.正確 B.不正確9,設(shè)矩陣A是一個(gè)對(duì)稱(chēng)矩陣，為節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一信數(shù)組B[1,n(n-1)/2]中，對(duì)下三角部分中任一元素aij(iNj),在一組數(shù)組B的下標(biāo)位置k的值是 。A.i(i-1)/2+j-1B.i(i-1)/2+jC,i(i+1)/2+j-1 D,i(i+1)/2+j填空題1.已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A[0][0]),貝UA[i]用的地址是。2,二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且A[0][0]的存TOC\o"1-5"\h\z儲(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ì)稱(chēng)矩陣A,采用壓縮存儲(chǔ)方式(以行為主存儲(chǔ)，且LOC(A[0][0])=1),則A[8][5]的地址是 。.設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組S[1..n*(n+1)/2]中，若按行序?yàn)橹鞔鎯?chǔ)，則A[i][j]對(duì)應(yīng)的S中的存儲(chǔ)位置是 。.一個(gè)稀疏矩陣如圖所示，則對(duì)應(yīng)的三元數(shù)組表示為 。0020300000-15_0000八、樹(shù)形結(jié)構(gòu)單項(xiàng)選擇題.在線索化二叉樹(shù)中，t所指結(jié)點(diǎn)沒(méi)有左子樹(shù)的充要條件是 。A.t->left==NULLB.t->ltag==1C.t->ltag==1且t->left==NULLD.以上都不對(duì).二叉樹(shù)按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前趨和后繼的線索，這種說(shuō)法 。A.正確 B.錯(cuò)誤.二叉樹(shù)的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說(shuō)法 。A.正確 B.錯(cuò)誤.由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹(shù)是一種特殊的樹(shù)，這種說(shuō)法 。A.正確 B.錯(cuò)誤.設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為。A.2hB.2h-1C.2h+1 D,h+1.如圖所示二叉樹(shù)的中序遍歷序列是 。A.abcdgefB.dfebagcC.dbaefcg D.defbagcdd.已知某二叉樹(shù)的后序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列是 A.acbedB.decabC.deabc D.cedba.如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的A.前序 B.中序 C.后序 D.層次序.如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的A.前序 B.中序 C.后序 D.層次序TOC\o"1-5"\h\z12某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，則其后序遍歷結(jié)點(diǎn)訪問(wèn)順序是 。A.bdgcefhaB.gdbecfhaC.bdgaechf D.gdbehfca.二叉樹(shù)為二叉排序樹(shù)的充分必要條件是任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值，這種說(shuō)法 。A.正確 B.錯(cuò)誤.按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有種。A.3B.4C.5D.6.如圖所示二叉樹(shù)的中序遍歷序列是 。A.abdgcefhB.dgbaechfC.gdbehfca D.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ì).深度為5的二叉樹(shù)至多有 個(gè)結(jié)點(diǎn)。

A.16B.32C.31 D.10.在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊 。A,只有右子樹(shù)上的所有結(jié)點(diǎn) B.只有右子樹(shù)上的部分結(jié)點(diǎn)C.只有左子樹(shù)上的所有結(jié)點(diǎn) D,只有左子樹(shù)上的部分結(jié)點(diǎn).樹(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ì).實(shí)現(xiàn)任意二叉樹(shù)的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹(shù)采用—存儲(chǔ)結(jié)構(gòu)。A.二叉鏈表 B.廣義表存儲(chǔ)結(jié)構(gòu) C.三叉鏈表 D.順序存儲(chǔ)結(jié)構(gòu).對(duì)于一個(gè)滿二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h，則。A.n=h+mB.h+m=2nC.m=h-1 D.n=2h-1.如果某二叉樹(shù)的前序?yàn)閟tuwv，中序?yàn)閡wtvs，那么該二叉樹(shù)的后序。A.uwvtsB.vwutsC.wuvtsD.wutsv.如圖所示的T2是由有序樹(shù)T1轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么樹(shù)T1有個(gè)葉結(jié)點(diǎn)。A.4 B.5 C.6 D.7C.n在mC.n在m左方 D.n是m子孫C.物理 D.線性、、.設(shè)n、m為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是 A.n在m右方B.n是m祖先.線索二叉樹(shù)是一種結(jié)構(gòu)。A.邏輯 B.邏輯和存儲(chǔ)填空題.有一棵樹(shù)如圖所示，回答下面問(wèn)題：TOC\o"1-5"\h\z（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)是 。.指出樹(shù)和二叉樹(shù)的三個(gè)主要差別.從概念上講，樹(shù)與二叉樹(shù)是二種不同的數(shù)據(jù)結(jié)構(gòu)，將樹(shù)轉(zhuǎn)化為二叉樹(shù)的基本目的是 。.一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組T中，如圖所示，則該二叉樹(shù)的鏈接表示形式為。1 2 3 4 5 67 8 9101112131415161718192021eafdgcjihb5.深度為k的完全二叉樹(shù)至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)，若按自上而下、從左到右次序給結(jié)點(diǎn)編號(hào)（從1開(kāi)始），則編最小的葉子結(jié)點(diǎn)的編號(hào)是 。

.在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2,則有n0=。.一棵二叉樹(shù)的第k層最多有個(gè)結(jié)點(diǎn)；一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)共有個(gè)葉子和個(gè)非終端結(jié)點(diǎn)。.結(jié)點(diǎn)最少的樹(shù)為，結(jié)點(diǎn)最少的二叉樹(shù)為。.現(xiàn)有按中序遍歷二叉樹(shù)的結(jié)果是abc，問(wèn)有種不同形態(tài)的二叉樹(shù)可以得到這一遍T(mén)OC\o"1-5"\h\z歷結(jié)果，這些二叉樹(shù)分別是 。.根據(jù)二叉樹(shù)的定義，具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)有種不同的形態(tài)，它們分別是 。 11L由如圖所示的二叉樹(shù)，回答以下問(wèn)題： bJ：Vc（1）其中序遍歷序列； /（2）其前序遍歷序列 ； 飛（3）其后序遍歷序列 ； 目 a（4）該二叉樹(shù)的中序線索二叉樹(shù)為 ； 1h（5）該二叉樹(shù)的后序線索二叉樹(shù)為 ； /|\d（6）該二叉樹(shù)對(duì)應(yīng)的森林是 。 匕°/\口\.已知一棵樹(shù)如圖所示，其孩子兄弟表示為 。e/ 飛◎\.以數(shù)據(jù)集｛4,5,6,7,10,12,18｝為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹(shù)為，其帶權(quán)路徑長(zhǎng)度為。九、圖.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 倍。A.1/2 B.1 C.2 D.4.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度這和 倍。A.1/2 B.1 C.2 D,4.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有條邊。A.nB.n（n-1）C.n（n-1）/2D.2n.具有4個(gè)頂點(diǎn)的無(wú)向完全圖有條邊。A.6B,12C.16D.20.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.8.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要 條邊。A.nB.n+1C,n-1D.n/2TOC\o"1-5"\h\z.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是 。A.n B.（n-1）2 C.n-1 D.n28,對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接矩陣表示，則表頭向量的大小是一;所有鄰接矩陣中的結(jié)點(diǎn)總數(shù)是 2 。1A.n B,n+1C,n-1D.n+e2A,e/2B.eC.2e D.n+e2A,e/2B.eC.2e D.n+e9.已知一個(gè)圖如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可得到頂點(diǎn)序列為 1 ;按寬度搜索法進(jìn)行遍歷，則可得到頂點(diǎn)序列為 2 。A.abecdf B.acfebd C.aebcfd D.aedfcbA.abcedf B.abcefd C.aebcfd D.acfdeb.已知一有向圖的鄰接表存儲(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)序列是2B.v1,v2,v3,v4,v5D.v1,v4,v3,v5,v2B.v1,v3,v2,v4,v5B.v1,v2,v3,v4,v5D.v1,v4,v3,v5,v2B.v1,v3,v2,v4,v5D.v1,v4,v3,v5,v2C.v1,v3,v4,v5,v22A.v1,v2,v3,v4,v5C.v1,v2,v3,v5,v4.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的 A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷.采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的 。A.先序遍歷 B.中序遍歷C.后序遍歷 D.按層遍歷.判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用 A.求關(guān)鍵路徑方法 B.求最短路徑的Dijkstra方法C.寬度優(yōu)先遍歷算法 D.深度優(yōu)先遍歷算法填空題.n個(gè)頂點(diǎn)的連通圖至少 條邊。.在無(wú)權(quán)圖G的鄰接矩陣中，若(vi,vj)或＜vi,vj＞屬于圖G的邊集，則對(duì)應(yīng)元素A[i][j]等于，否則等于。.在無(wú)權(quán)圖G的鄰接矩陣中，若A[i][j]等于1，則等于A[j][i]=。.已知圖G的鄰接表如圖所示，其從v1頂點(diǎn)出發(fā)的深度優(yōu)先搜索序列為 ，其從v1頂點(diǎn)出發(fā)的寬度優(yōu)先搜索序列為 。.已知一圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 。.已知一圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是 十、查找單項(xiàng)選擇題.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為的線性表。A.散列存儲(chǔ) B.順序存儲(chǔ)或鏈接存儲(chǔ)C.壓縮存儲(chǔ) D.索引存儲(chǔ)TOC\o"1-5"\h\z.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須 。A.以順序方式存儲(chǔ) B.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C.以鏈接方式存儲(chǔ) D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為 。A.nB.n/2C.(n+1)/2D,(n-1)/2.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為 。A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)5,二分查找和二叉排序樹(shù)的時(shí)間性育^ 。A.相同 B.不相同.有一個(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.8.設(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.9.有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為 。A.35/12B.37/12C.39/12D.43/12.采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來(lái)確定結(jié)點(diǎn)所在的塊時(shí)，每塊應(yīng)分 個(gè)結(jié)點(diǎn)最佳地。A.10B.25C.6D.625.如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用 查找方法。A.分塊B.順序C.二分D.散列填空題.順序查找法的平均查找長(zhǎng)度為；二分查找法的平均查找長(zhǎng)度為；分塊查找法(以順序查找確定塊)的平均查找長(zhǎng)度為 ；分塊查找法(以二分查找確定塊)的平均查找長(zhǎng)度為 ；哈希表查找法采用鏈接法處TOC\o"1-5"\h\z理沖突時(shí)的平均查找長(zhǎng)度為 。.在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是 。.二分查找的存儲(chǔ)結(jié)構(gòu)僅限于 ，且是 。.在分塊查找方法中，首先查找，然后再查找相應(yīng)的。.長(zhǎng)度為255的表，采用分塊查找法，每塊的最佳長(zhǎng)度是 。.在散列函數(shù)H(key)=key%p中，p應(yīng)取。.假設(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)度為。.對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為 ；若采用二分法查找，則時(shí)間復(fù)雜度為 ；若采用分塊查找(假設(shè)總塊數(shù)和每塊長(zhǎng)度均接近n1/2)，TOC\o"1-5"\h\z則時(shí)間復(fù)雜度為 。.在散列存儲(chǔ)中，裝填因子a的值越大，則 ；&的值越小，則。十一、內(nèi)排序.在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是 。A.希爾排序 B.起泡排序C.插入排序 D.選擇排序.設(shè)有1000個(gè)無(wú)序的元素，希望有最快的速度挑選出其中前10個(gè)最大的元素，最好采用 排序法。A.起泡排序 B.快速排序 C.堆排序D.基數(shù)排序.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。A.插入排序 B.選擇排序 C.快速排序 D.歸并排序.一組記錄的排序碼為（46,79,56,38,40,84）,則利用堆排序方法建立的初始堆為A.79，46，56，38，40，80 B.84，79，56，38，40，46C.84,79,56,46,40,38 D.84,56,79,40,46,38TOC\o"1-5"\h\z.一組記錄的排序碼為（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)度TOC\o"1-5"\h\z為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為 。A.16253548234079823672 B.16253548798223364072C.16254835798223364072 D.16253548792336407282.排序方法中,從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為 。A.希爾排序B.起泡排序C.插入排序 D.選擇排序.排序方法中,從未排序序列中挑選元素,并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱(chēng)為 。A.希爾排序B.歸并排序C.插入排序 D.選擇排序.用某種排序方法對(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.歸并排序.下列幾種排序方法中，要求內(nèi)存量最大的是 。A.插入排序 B.選擇排序 C.快速排序 D.歸并排序.快速排序方法在情況下最不利于發(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í)，為尋找插入位置需比較次。.在利用快速排序方法對(duì)（54,38,96,23,15,72,60,45,83）進(jìn)行快速排序時(shí)，遞歸調(diào)用而使用的棧的所能達(dá)到的最大深度為 ,共需遞歸調(diào)用的次數(shù)為,其中第二次遞歸調(diào)用是對(duì)一組記錄進(jìn)行快速排序。.在堆排序、快速排序和歸并排序中，若只從存儲(chǔ)空間考慮，則應(yīng)首先選取 方法，其次選取方法，最后選取方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取方法;若只從平均情況下排序最快考慮，則應(yīng)選取方法；若從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取方法。.在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有。.在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是 ，需要內(nèi)存量最多的是 。.在堆排序和快速排序中，若原始記錄接近正序或反序，則選用 ，若原始記錄無(wú)序，則選用。.在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則選用，若初始數(shù)據(jù)基本反序，則選用，.對(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。3.前驅(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。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。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.head->next==p。HS==NULL。 11.HQ->front==HQ->rear。intcount(HS)node*HS{node*p;intn=0;p=HS;while(p!=NULL){n++;p=p->next;}return(n);12.intcount(HQ)strructlinkqueue*HQ{strructlinkqueue