數(shù)據(jù)結(jié)構(gòu)(C語言版)(第4版)習(xí)題

習(xí)題1選擇題。(1)計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象統(tǒng)稱為。A．?dāng)?shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型(2)數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的及它們之間的聯(lián)系。A．存儲(chǔ)和邏輯結(jié)構(gòu)B.存儲(chǔ)和抽象C.理想和抽象D.理想和邏輯(3)下列不是數(shù)據(jù)的邏輯結(jié)構(gòu)的是。A．散列結(jié)構(gòu)B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖狀結(jié)構(gòu)(4)數(shù)據(jù)結(jié)構(gòu)被形式地定義<D,R>，其中D是的有限集，R是___的有限集。A．算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)(5)組成數(shù)據(jù)的基本單位是。A．?dāng)?shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量(6)設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D,R),其中，D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},則數(shù)據(jù)結(jié)構(gòu)A是。A．線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.圖狀結(jié)構(gòu)D.集合(7)數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中表示時(shí)，若物理地址與邏輯地址相同并且是連續(xù)的，則稱為。A．存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C．順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(8)在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分。A．內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B.靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)B．線性結(jié)構(gòu)與非線性結(jié)構(gòu)D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)(9)對(duì)于一個(gè)算法的評(píng)價(jià)，不包括以下方面的內(nèi)容。A.健壯性和可讀性B.并行性C.正確性D.時(shí)間空間復(fù)雜度(10)算法分析的兩個(gè)方面是。A．空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡明性C．可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性1.2填空題(1)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的以及它們之間的和運(yùn)算等的學(xué)科。(2)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的結(jié)構(gòu)和結(jié)構(gòu)。(3)數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為3種基本類型，即、和。(4)數(shù)據(jù)的物理結(jié)構(gòu)被分為、、和種類型。(5)一種抽象數(shù)據(jù)結(jié)構(gòu)類型包括和兩個(gè)部分。(6)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指(7)數(shù)據(jù)結(jié)構(gòu)是指指數(shù)數(shù)據(jù)及其相互之間的當(dāng)結(jié)點(diǎn)之間存在M對(duì)N(M:N)的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為當(dāng)結(jié)點(diǎn)之間存在1對(duì)N(1：N)的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為(8)對(duì)算法從時(shí)間和空間兩個(gè)方面進(jìn)行衡量，分別稱為分析。(9)算法的效率可以分為效率和效率。(10)for(i=1,t=1,s=0;i<=n;i++){t=t*i;s=s+t;}的時(shí)間復(fù)雜度為1.3簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的物理結(jié)構(gòu)、數(shù)據(jù)類型和算法。1.4分析下面語句段執(zhí)行的時(shí)間復(fù)雜度。(1)for(i=1;i<=n;i++)for(j=1;j<=n;j++)s++;(2)for(i=1;i<=n;i++)for(j=i;j<=n;j++)s++;(3)for(i=1;i<=n;i++)for(j=1;j<=i;j++)s++;(4)i=1;k=0;While(i<=n-1){k+=10*i;i++;}(5)for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;1.5試寫一個(gè)算法，自大至小依次輸出順序讀入的3個(gè)整數(shù)X、Y和Z。1.6編寫算法，求一元多項(xiàng)式Pn(x)=a0+a1x+習(xí)題22.1選擇題(1)線性表是具有n個(gè)的有限序列(n≠0)。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)(2)順序表的存儲(chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索取存取D.Hash存取(3)在一個(gè)長度為n的順序表中向第i個(gè)元素(1≤i≤n+1)之間插入一個(gè)新元素時(shí)需要向后移動(dòng)個(gè)元素。A.n-iB.n-i+1C.n-i-1D.i(4)鏈表是一種采用存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。A．順序B.鏈?zhǔn)紺.星型D.網(wǎng)狀(5)下面關(guān)于線性表的敘述錯(cuò)誤的是A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D．線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)(6)設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單向鏈表B.單向循環(huán)鏈表C.雙向鏈表D.雙向循環(huán)鏈表(7)設(shè)指針q指向單鏈表中的結(jié)點(diǎn)A，指針p指向單鏈表中的結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A和結(jié)點(diǎn)B之間插入結(jié)點(diǎn)X的操作序列為A.s->next=p->next;p->next=-s;B.q->next=s;s->next=p;C.p->next=s->next;s->next=p;D.p->next=s;s->next=q;(8)設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為A.p->next=p->next->nextB.p=p->nextC.p=->next->nextD.p->next=p(9)在一個(gè)以h為頭的單循環(huán)鏈表中，p指針指向鏈尾的條件是。A.p->next=hB.p->next=NULLC.p->next->next=hD.p->date=-1(10)對(duì)于只有首、尾兩端進(jìn)行操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為。A.順序表B.用頭指針表示的單循環(huán)鏈表C.單鏈表D.用尾指針表示的單循環(huán)鏈表2.2填空題(1)線性表是n個(gè)元素的________________。(2)線性表的存儲(chǔ)結(jié)構(gòu)有________________。(3)設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為。(4)設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則在第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中的個(gè)數(shù)據(jù)元素，刪除第i個(gè)位置上數(shù)據(jù)元素需要移動(dòng)表中的個(gè)元素。(5)若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，則該線性表應(yīng)采用存儲(chǔ)結(jié)構(gòu)。(6)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含域和域。(7)在雙向鏈?zhǔn)奖碇忻總€(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向另一個(gè)指向(8)對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為在表尾插入元素的時(shí)間復(fù)雜度為(9)設(shè)指針變量p指向單鏈?zhǔn)奖碇械慕Y(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)B，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列為________。(10)設(shè)指針變量p指向單鏈?zhǔn)奖碇械慕Y(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)（假設(shè)存在）的語句序列為“s=p->next;p->next=;free(s);”2.3將一順序表A中的元素逆置。例如原來順序表A中的元素是100,90,80,70,60,50,40，逆置以后為40,50,60,70,80,90,100。要求算法所用的輔助空間盡可能地少，用非形式算法描述，并編寫C語言程序。2.4寫一算法輸出已知順序表A中元素的最大值和最小值，并編寫C語言程序。2.5設(shè)一順序表中的元素值遞增有序，寫一算法，將元素x插入到表中的適當(dāng)位置，并保持順序表的有序性。2.6設(shè)有兩個(gè)按元素遞增有序的順序表A和B（單鏈?zhǔn)奖鞟和B），編一程序?qū)表和B表歸并成一個(gè)新的遞增有序的順序表C（單鏈?zhǔn)奖鞢），值相同的元素均保留在C表中。2.7設(shè)有兩個(gè)線性表A和B都是單鏈表存儲(chǔ)結(jié)構(gòu)。同一個(gè)表中的元素各不相同，且遞增有序，寫一算法，構(gòu)成一個(gè)新的線性表C，使C為A和B的交集，且C中的元素也遞增有序。習(xí)題33.1選擇題(1)下列說法正確的是_____。A.堆棧是在兩端操作、先進(jìn)后出的線性表B.堆棧是在一端操作、先進(jìn)先出的線性表C.隊(duì)列是在一端操作、先進(jìn)先出的線性表D.隊(duì)列是在兩端操作、先進(jìn)先出的線性表(2)棧和隊(duì)列的共同點(diǎn)是_____。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)(3)以下數(shù)據(jù)結(jié)構(gòu)中是非線性結(jié)構(gòu)的是_____。A.隊(duì)列B.棧C.線性表D.二叉樹(4)已知一個(gè)棧的入棧序列是1,2,3，…,n，輸出序列是p1，p2，p3?A.iB.n-iC.n-i+1D.不確定(5)當(dāng)利用大小為N的一堆數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則向這個(gè)棧插入一個(gè)元素時(shí)首先應(yīng)執(zhí)行_____語句修改top指針。A.top++B.top--C.top=0D.top(6)4個(gè)元素進(jìn)S棧的順序是A→B→C→D，經(jīng)POP(S)運(yùn)算后棧頂元素是_____。A.AB.BC.CD.D(7)一個(gè)棧的輸入序列是a,b,c,d,e,則棧不可能的輸出序列是____。A.e,d,c,b,aB.d,e,c,b,aC.d,c,e,a,bD.a,b,c,d,e(8)設(shè)輸入序列是1,2,3，…，n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出的元素是_____。A.n-iB.n-i-1C.n+1-iD.不能確定(9)字符A,B,C,D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，最多可以組成_____個(gè)不同的字符串。A.15B.14C.16D.21(10)遞歸函數(shù)f(n-1)=f(n-1)+n(n≥1)的遞歸出口是_____。A.f1=0B.f1=1C.(11)設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作為_____。A.top=top+1;B.top=top-1;C.top->next=top;D.top=top->next;(12)中綴表達(dá)式A-(B+C/D)*E的后綴形式是_____。A.ABC+D/*E-B.ABCD/+E*-C.AB-C+D/E*D.ABC-+D/E*(13)用front和rear分別表示順序循環(huán)隊(duì)列的隊(duì)首和隊(duì)尾指針，判斷隊(duì)空的條件為_____。A.front+==reearB.(rear+1)%maxSize==frontC.front==0D.front==rear(14)判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件為_____。A.QU->front==QU->rearB.QU->front!=QU->rearC.QU->front==(QU->rear+1)%mD.QU->front!=(QU->rear+1)%m(15)設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，A.6B.4C.3D.2(16)用連接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)_____。A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改(17)若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素再加入兩個(gè)元素后，rear和front的值分別為_____。A.1和5B.2和4C.4和2D.5和1(18)設(shè)順序循環(huán)隊(duì)列Q[0：M=1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一個(gè)位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為_____。A.R-FB.F-RC.(R-F=M)%MD.(F-R+M)%M(19)設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作為_____。A.front->next=s;front=s;B.s->next=front;rear=s;C.rear->next=s;rear=s;D.s->next=front;front=s;(20)當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長度為_____。A.n-2B.n-1C.nD.n+13.2填空題（1）棧的插入和刪除只能在棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為_____表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為下劃表。（2）后綴算式923+-102/-的值為_____，中綴算式(3+4X)-2Y/3對(duì)應(yīng)的后綴算式為_____。（3）下面程序段的功能是實(shí)現(xiàn)數(shù)據(jù)x的進(jìn)棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==n-1)printf(“overfow”);else{__________；__________；}（4）設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為_____；_____；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。（5）設(shè)一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)M-1個(gè)隊(duì)列元素，當(dāng)前實(shí)際存儲(chǔ)_____個(gè)隊(duì)列元素（設(shè)頭指針F指向F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針指向當(dāng)前隊(duì)尾元素的位置）。（6）設(shè)有一個(gè)順序共享?xiàng)[0:n-1],其中，第一個(gè)棧頂指針top1的處置為-1，第二個(gè)棧頂指著top2的初值為n，則判斷共享?xiàng)M的條件是（7）設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為__________。（8）順序循環(huán)隊(duì)列判空的條件是（使用front、rear、n表示）__________。（9）順序循環(huán)隊(duì)列判滿的條件是（使用front、rear、n表示）__________。（10）順序循環(huán)隊(duì)列MAXSIZE=N,最多可以存儲(chǔ)_____個(gè)元素。3.3簡述棧和線性表的區(qū)別。3.4簡述棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)。3.5如果進(jìn)棧的元素序列為A,B,C,D,可能得到的出棧序列有多少種？寫出全部的可能序列。3.6如果進(jìn)棧的元素序列為1,2,3,4,5,6，能否得到4,3,5,6,1,2和1,3,5,4,2,6的出棧序列？說明為什么不能得到或如何得到。3.7寫出下列程序段的運(yùn)行結(jié)果（棧中的元素類型是char）:main(){SeqStacks,*p;charx,y;p=&s;Init_Queue(p);x=’c’;y=’k’;push(p,x);push(p,’a’);push(p,y);x=pop(p);push(p,’t’);push(p,x);x=pop(p);push(p,’s’);while(!Empty_SeqStack(p)){y=pop(p);printf(“%c”,y);}printf(“%c\n”,x);}3.8將一個(gè)非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)，用非遞歸算法和遞歸算法來實(shí)現(xiàn)。3.9寫一算法將一順序棧中的元素依次取出，并打印元素值。3.10寫出下列程序段的運(yùn)行結(jié)果（隊(duì)列中的元素類型是char）:main(){SeqStacka,*q;charx,y;q=&a;x=’e’;y=’c’;Init_Queue(q);In_Quene(q,’h’);In_Quene(q,’r’);In_Quene(q,y);x=Out_Quene(q);Init_Queue(q,x);x=Out_Quene(q);Init_Queue(q,’a’);while(!Empty_SeqStack(q)){y=Out_Quene(q);printf(“%c”,y);}printf(“%c\n”,x);}3.11寫一算法將一鏈隊(duì)列中的元素依次取出，并打印這些元素值。習(xí)題44.1選擇題(1)下列敘述正確的是_____。A．串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串(2)下列關(guān)于串的敘述正確的是_____。A.串長度是指串中不同字符的個(gè)數(shù)B.串是n個(gè)字母的有限序列C.如果兩個(gè)串含有相同的字符，則它們相等D.只有當(dāng)兩個(gè)串的長度相等并且各個(gè)對(duì)應(yīng)位置的字符都相符時(shí)才相等(3)字符串的長度是指_____。A.串中不同字符的個(gè)數(shù)B.串中不同字母的個(gè)數(shù)C.串中所含字符的個(gè)數(shù)D.串中不同數(shù)字的個(gè)數(shù)(4)兩個(gè)字符串相等的充要條件是_____。A.兩個(gè)字符串的長度相等B.兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等C.同時(shí)具備A和B兩個(gè)條件D.以上答案都不對(duì)(5)串是一種特殊的線性表，其特殊性體現(xiàn)在_____。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以連接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符(6)設(shè)有兩個(gè)p和q,求q和p中首次出現(xiàn)的位置的位置的運(yùn)算稱為_____。A.連接B.模式匹配C.求子串D.求串長(7)設(shè)串s1=“ADCDEFG”,s2==“PQRET”，函數(shù)con(x,y)返回x和y串的連接subs(s,i,j)返回串s從序列號(hào)為i的字符開始的j個(gè)字符組成的子串，len(s)返回串s的度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是_____。A.BCDEFB.BCDEFGC.BCPQRETD.BCDEFEF(8)函數(shù)substr(“DATASTRUCTURE”),5,9)的返回值為_____。A.“STRUCTURE”B.“DATA”C.“ASTRUCTUR”D.“DATASTRUCTURE”(9)設(shè)有二維數(shù)組A[50][60],其元素長度為1B，按列優(yōu)先順序存儲(chǔ)，首先素A[0][0]的地址為200，則元素A[10][20]的存儲(chǔ)地址為_____。A.820B.720C.1210D.1410(10)設(shè)串s=“IAMATEACHER!”,其長度是_____。A.16B.11C.14D.154.2填空題（1）兩個(gè)串相等的充要條件是__________。（2）空串是_____，其長度為_____。（3）空格串是_____，其長度是_____。（4）s=“Iamaman”的長度為_____。（5）s1=“hello”,s2=“boy”,s1,s2連接后為_____。（6）s=“thisisthemainstring”，sub=“string”,strindex(s,sub)是_____。（7）inta[10][10],已知a=1000,sizeof(int)=2,a[3][3]的地址為_____。（8）設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為_____。（9）串的長度是指_____。（10）s=“xiaotech”所含子串的個(gè)數(shù)是_____。4.3設(shè)s=“IAMASTUDENT”,t=“GOOD”,q=“WORKER”,求StrLength(s)、StrLength(t)、SubStr(t,2,1)、SteeIndex(s,“A”)、StrIndex(s,t)、StrRep(s,“STUDENT”,q)。4.4已知s=“（XXZ）+*”,t=“（X+Z）*Y”,試?yán)眠B接、求字串和置換等基本運(yùn)算將s轉(zhuǎn)化為t。4.5簡述下列每對(duì)術(shù)語的區(qū)別：空串和空格串；串變量和串常量；主串和字串；串變量的名字和串變量的值。4.6編一算法，在順序串上實(shí)現(xiàn)串的判等操作EQUAL(S,T).4.7設(shè)有二維數(shù)組A(6×8),每個(gè)元素占6B順序存放，A的起地址為1000，做以下計(jì)算：（1）數(shù)組A的體積（即存儲(chǔ)量）；（2）數(shù)組的最后一個(gè)元素A5,（3）按行優(yōu)先存放時(shí)，元素A1,（4）按列優(yōu)先存放時(shí)，元素A4,74.8已知稀疏矩陣如圖4.12所示，畫出它的三元組表的示意圖。A=圖4.12題4.8圖習(xí)題55.1單選題（1）樹最適合用來表示_____。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素間具有層次關(guān)系的數(shù)據(jù)D.元素間無聯(lián)系的數(shù)據(jù)（2）在m叉樹中，度為0的結(jié)點(diǎn)稱為_____。A.兄弟B.樹葉C.樹根D.1（3）如果樹的結(jié)點(diǎn)A有4個(gè)兄弟，而且B為A的雙親，則B的度為_____。（4）根據(jù)二叉樹的定義可知二叉樹共有_____種不同的形態(tài)。A.4B.5C.6D.7（5）由3個(gè)結(jié)點(diǎn)可以構(gòu)造出_____種不同形態(tài)的二叉樹。A.3B.4C.5D.6(6)具有20個(gè)結(jié)點(diǎn)的二叉樹，其深度最多為_____。A.4B.5C.6D.20（7）高度為h的滿二叉樹的結(jié)點(diǎn)數(shù)是_____個(gè)。A.log2hB.2hC.2h-1（8）深度為5的二叉樹最多有_____個(gè)結(jié)點(diǎn)。A.16B.32C.31D.10（9）設(shè)一棵二叉樹共有50個(gè)葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)），則共有_____個(gè)度為2的結(jié)點(diǎn)。A.25B.49C.50D.51（10）一顆完全二叉樹中根結(jié)點(diǎn)的編號(hào)為1，并且23號(hào)結(jié)點(diǎn)有左孩子但沒有右孩子，則完全二叉樹共有_____個(gè)結(jié)點(diǎn)。A.24B.45C.46D.47（11）二叉樹的第3層最少有_____個(gè)結(jié)點(diǎn)。A.4B.1C.2D.3（12）設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m之前的條件是_____。A.n在m右方B.n是m的祖先C.n在m左方D.n是m的子孫（13）某二叉樹的先序序列和后序序列正好相同，該二叉樹可能是_____的二叉樹。A.高度大于1的左單支B.高度大于1的右單支C.最多只有一個(gè)結(jié)點(diǎn)D.既有左孩子又有右孩子（14）某二叉樹的先序序列和后序序列正好相反，該二叉樹一定是_____的二叉樹。A.空或只有一個(gè)結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù)C.任一結(jié)點(diǎn)無左孩子D.任一結(jié)點(diǎn)無右孩子（15）有n個(gè)結(jié)點(diǎn)的二叉樹鏈表共有_____個(gè)空指針域。A.n-1B.2n-1C.2n+1D.2(n-1)（16）一個(gè)有n個(gè)葉結(jié)點(diǎn)的哈夫曼樹具有的結(jié)點(diǎn)數(shù)為_____。A.2nB.2n-1C.2n+1D.2(n-1)5.2填空題（1）一顆深度為5的二叉樹，最少有_____個(gè)葉子結(jié)點(diǎn)。（２）一顆完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)占４個(gè)字節(jié)，設(shè)編號(hào)為５的元素的地址為１０１６，且它有左孩子和右孩子，則該左孩子和右孩子的地址分別為_____和_____。（３）一顆完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，若編號(hào)為ｉ的元素有有左孩子，則該左孩子的編號(hào)為_____。（４）一棵含有ｎ（ｎ＞１）個(gè)結(jié)點(diǎn)的ｋ叉樹，當(dāng)ｋ＝_____時(shí)深度最大，此最大深度為_____；當(dāng)ｋ＝_____時(shí)深度最小，此最小深度為_____。（５）深度為為ｋ的玩群二叉樹最少有_____個(gè)結(jié)點(diǎn)，最多有_____個(gè)結(jié)點(diǎn)。（６）已知一棵二叉樹的線序遍歷序列為ＥＢＡＤＣＦＨＧＩＫＪ，中序遍歷序列為ＡＢＣＤＥＦＧＦＩＪＫ，則該二叉樹的后序遍歷序列為_____。（７）如果指針ｐ指向一棵二叉樹的一個(gè)結(jié)點(diǎn)，則判斷ｐ沒有左孩子的邏輯表達(dá)式為_____。（８）在由ｎ個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)造出的所有二叉樹中，帶權(quán)路徑長度最小的二叉樹稱為_____。（９）在樹的孩子兄弟表示法中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向_____，另一個(gè)指向_____。（１０）樹的先根遍歷結(jié)果與其轉(zhuǎn)換的相應(yīng)二叉樹的_____結(jié)果相同；樹的后跟遍歷與其轉(zhuǎn)換的相應(yīng)二叉樹的_____結(jié)果相同。５.３寫出圖５.２４中樹的葉子結(jié)點(diǎn)、非終端結(jié)點(diǎn)、個(gè)結(jié)點(diǎn)的度和樹深。５．４分別畫出含３個(gè)結(jié)點(diǎn)的無序樹與二叉樹的所有不同形態(tài)。５．５分別畫出含３個(gè)結(jié)點(diǎn)的無序樹與二叉樹的所有不同形態(tài)。５.６分別寫出圖５.２５中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結(jié)點(diǎn)訪問序列。圖５.２４題５.３圖圖５.２５題５.５圖５.７試找出分別滿足下列條件的所有二叉樹：（１）先徐序列和中序序列相同；（２）后徐序列和中序序列相同；（３）先徐序列和后序序列相同。５.８已知一棵二叉樹的中序序列和后序序列分別為ＢＣＤＥＡＦＨＧ和ＤＥＣＢＨＧＦＡ，試畫出這棵二叉樹。５.９分別寫出圖５．２４中所示樹的先根遍歷、后根遍歷和層次遍歷的結(jié)點(diǎn)訪問序列。５.１０如果一棵樹有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)為2的結(jié)點(diǎn)?！?nm個(gè)度為m的結(jié)點(diǎn)，則該樹共有多少個(gè)葉5.12編一算法求二叉樹中的結(jié)點(diǎn)的總數(shù)。5.13編一算法將二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換。5.14編一算法判別給定的二叉樹是否是完全二叉樹。5.15將圖5.26中所示的森林轉(zhuǎn)換為二叉樹。圖5.26題5.15圖5.16分別畫出圖5.27中所示二叉樹對(duì)應(yīng)的森林。5.17在以雙親鏈表表示法存儲(chǔ)結(jié)構(gòu)的樹中，寫出以下算法：（1）求樹中結(jié)點(diǎn)雙親的算法；（2）求樹中結(jié)點(diǎn)孩子的算法。5.18在以孩子鏈表表示法存儲(chǔ)結(jié)構(gòu)的樹中，寫出以下算法：（1）求樹中結(jié)點(diǎn)雙親的算法；（2）求樹中結(jié)點(diǎn)孩子的算法。5.19在以孩子兄弟鏈表結(jié)構(gòu)存儲(chǔ)的樹中，寫出求樹中結(jié)點(diǎn)孩子的算法。5.20（1）給定權(quán)值（4,3,16,9,22,10,5），構(gòu)造相應(yīng)的哈夫曼樹。（2）設(shè)上述權(quán)值分別代表7個(gè)字母出現(xiàn)的頻率，試為這7個(gè)字母設(shè)計(jì)哈夫曼編碼。習(xí)題66.1選擇題（1）一個(gè)有8個(gè)頂點(diǎn)的有向圖，所有頂點(diǎn)的入度之和與所有頂點(diǎn)的出度之和的差是_____。A.16B.4C.0D.2（2）一個(gè)有n個(gè)頂點(diǎn)的連通無向圖最少有_____條邊。A.n-1B.nC.n+1D.n+2（3）具有n個(gè)頂點(diǎn)的完全有向圖的弧數(shù)為_____。A.n(n-1)/2B.n(n-1)C.n2D.（4）一個(gè)n條邊的連通無向圖，其頂點(diǎn)的個(gè)數(shù)最多為_____。A.n-1B.nC.n+1D.nlogn（5）設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有_____條邊。A.n-1B.n(n-1)/2C.n(n+1)/2D.0（6）任何一個(gè)無向連通圖的最小生成樹_____A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在（7）在下列算法中，_____算法用來求圖中某頂點(diǎn)到其他所有頂點(diǎn)之間的最短路徑。A.DijkstraB.FloyedC.PrimD.Kruskal（8）在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_____倍。A.2B.3C.1D.1.5（9）下面關(guān)于圖的存儲(chǔ)的敘述中正確的是_____。A.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中的邊數(shù)有關(guān)，而與頂點(diǎn)個(gè)數(shù)無關(guān)。B.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中的邊數(shù)和頂點(diǎn)個(gè)數(shù)都有關(guān)。C.用鄰接矩陣表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中的邊數(shù)和頂點(diǎn)個(gè)數(shù)都有關(guān)。D.用鄰接矩陣表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中的邊數(shù)有關(guān)，而與頂點(diǎn)個(gè)數(shù)無關(guān)。（10）設(shè)有向無環(huán)圖G中的有向邊集合E={<1，2>,<2，3>,<3，4>,<1，4>},則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖莀____。A.1，2，3，4B.2，3，4，1C.1，4，2，3D.1，2，4，3(11)設(shè)無向圖G中的邊的集合E={(a,b),(a,e),(a,c)(b,e),(e,d),(d,f),(f,c)},則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為_____。A.aedfcbB.acfebdC.aebcfdD.aedfbc（12）連通圖G中有n個(gè)頂點(diǎn)，G的生成樹是_____連通子圖。A.包含G的所有頂點(diǎn)B.包含G的所有邊C.不必包含G的所有頂點(diǎn)D.包含G的所有頂點(diǎn)和所有邊（13）設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有_____中個(gè)表頭結(jié)點(diǎn)。A.n-1B.nC.n+1D.2n-1（14）設(shè)無向圖G中有n個(gè)頂點(diǎn)、e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和邊表結(jié)點(diǎn)的個(gè)數(shù)分別為_____。A.n,eB.e,nC.2n,eD.n,2e（15）用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為_____。A.第i行非0元素的個(gè)數(shù)之和B.第i列非0元素的個(gè)數(shù)之和C.第i行0元素的個(gè)數(shù)之和D.第i列0元素的個(gè)數(shù)之和（16）用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的出度為_____。A.第i行非0元素的個(gè)數(shù)之和B.第i列非0元素的個(gè)數(shù)之和C.第i行0元素的個(gè)數(shù)之和D.第i列0元素的個(gè)數(shù)之和（17）可以判斷一個(gè)有向圖中是否含有回路的方法為_____。A.廣度優(yōu)先遍歷B.深度優(yōu)先遍歷C.拓?fù)渑判駾.求最短路徑6.2填空題（1）一個(gè)連通無向圖有5個(gè)頂點(diǎn)、8條條邊，則其生成樹將要去掉_____條邊。（2）在樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著_____和_____的聯(lián)系。（3）有n個(gè)頂點(diǎn)的連通圖至少有_____條邊，有n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有_____條邊。（4）一個(gè)具有n個(gè)頂點(diǎn)的有向圖至少有_____條弧。（5）如果不知道一個(gè)圖是有向圖還是無向圖，但是知道它的鄰接矩陣是非對(duì)稱的，那么這個(gè)圖必定是_____。（6）在無向圖G的鄰接矩陣A中，若A[I][J]=1，則A[J][I]為_____。（7）無向圖用鄰接矩陣存儲(chǔ)，其所有元素之和表示無向圖的邊數(shù)的_____。（8）無向圖用鄰接表存儲(chǔ)，其所有邊表結(jié)點(diǎn)之和表示無向圖的邊數(shù)的_____。（9）無向圖用鄰接表存儲(chǔ)，頂點(diǎn)vi的度為_____（10）有向圖用鄰接表存儲(chǔ)，頂點(diǎn)vi的度為_____（11）圖的遍歷方式一般有_____和_____兩種。（12）Prim算法的時(shí)間復(fù)雜度為_____，與邊數(shù)無關(guān)，因此適用于求邊稠密的網(wǎng)的最小生成樹。（13）如果某有向圖的所有頂點(diǎn)可以構(gòu)成一個(gè)拓?fù)渑判蛐蛄?，則說明該有向圖_____。6.3畫出無向圖6.23的鄰接矩陣和鄰接鏈表示意圖，并寫出每個(gè)頂點(diǎn)的度。6.4畫出有向圖6.24的鄰接矩陣、鄰接鏈表和逆鄰接鏈表示意圖，并寫出每個(gè)頂點(diǎn)的入度、出度。圖6.23題6.3圖圖6.24題6.4圖6.5對(duì)應(yīng)圖6.25，寫出從v1出發(fā)的深度優(yōu)先查找遍歷結(jié)果和廣度優(yōu)先查找遍歷結(jié)果各3個(gè)。6.6求圖6.26的連通分量。6.7分別用Prim算法按列表方式求出圖6,27的最小生成樹，并畫出最小生成樹的示意圖。圖6.25題6.5圖圖6.26題6.6圖圖6.27題6.7圖6.8寫出圖6.28的拓?fù)渑判颉?.9試寫出下列算法：（1）建立無向圖鄰接矩陣算法；（2）建立無向網(wǎng)鄰接矩陣算法；（3）建立有向圖鄰接矩陣算法。6.10試寫出下列算法：（1）建立無向圖鄰接鏈表結(jié)構(gòu)算法；（2）建立無向網(wǎng)鄰接鏈表結(jié)構(gòu)算法。6.11編寫算法，在無向圖的鄰接鏈表結(jié)構(gòu)上生成無向圖的鄰接矩陣結(jié)構(gòu)。6.12編寫算法，在無向圖的鄰接矩陣結(jié)構(gòu)上生成無向圖的鄰接鏈表結(jié)構(gòu)。6.13已知有m個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣結(jié)構(gòu)存儲(chǔ)，問：（1）圖中有多少條邊？（2）任意兩個(gè)頂點(diǎn)i和j之間是否有邊相連？（3）任意一個(gè)頂點(diǎn)的度是多少？6.14已知一個(gè)無向圖，采用鄰接鏈表結(jié)構(gòu)存儲(chǔ)，問：（1）圖中有多少條邊？（2）任意兩個(gè)頂點(diǎn)i和j之間是否有邊相連？（3）任意一個(gè)頂點(diǎn)的度是多少？6.15以圖6.29所示的無向圖連通圖為例，按照深度優(yōu)先查找遍歷的算法編寫程序上機(jī)運(yùn)行，并獲得正確的結(jié)果。圖6.28題6.8圖圖6.29題6.15圖習(xí)題77.1選擇題（1）對(duì)長度為n的無序線性表進(jìn)行順序查找，查找成功、不成功時(shí)的平均數(shù)據(jù)比較次數(shù)分別為_____。A.n2、nB.n+12、n-1（2）指出順序表{2、5、7、10、14、15、18、23、35、41、52}中用二分法查找關(guān)鍵碼12需做_____次關(guān)鍵碼比較。A.2B.3C.4D.5（3）對(duì)線性表進(jìn)行折半查找時(shí)，必須要求線性表_____。A.以順序方式存儲(chǔ)B.以鏈?zhǔn)椒绞酱鎯?chǔ)C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D.以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列（4）設(shè)二叉樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均查找長度為_____。A.O(1)B.O(log2n)C.O(n)D.O(（5）在依次插入序列（50,72,43,85,75,20,35,45,65,30）后建立的二叉搜索樹中，查找元素35要進(jìn)行_____元素間的比較。A.4次B.5次C.7次D.10次（6）在一棵高度為5的理想平衡樹中，最少含有16個(gè)結(jié)點(diǎn)，最多含有_____個(gè)結(jié)點(diǎn)。A.31B.32C.30D.33(7)對(duì)包含N個(gè)元素的散列表進(jìn)行查找，平均查找長度_____。A.為O(log2N)C.不直接依賴于ND.上述三者都不是（8）設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H（key）=key%p,則p最好選擇_____。A.小于等于m的最大奇數(shù)B.小于等于m的最大素?cái)?shù)C.小于等于m的最大偶數(shù)D.小于等于m的最大合數(shù)（9）_____是Hash查找的沖突處理方法。A.求余法B.平方取中法C.二分法D.開放地址法（10）當(dāng)α的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有_____的查找速度。A.較慢B.較快C.相同D.不確定（11）對(duì)線性表進(jìn)行折半查找最方面結(jié)構(gòu)是_____。A.順序表B.有序的順序表C.鏈表D.有序的鏈表（12）對(duì)一個(gè)排好序的線性表用二分法檢索表中的元素，被檢索的表應(yīng)當(dāng)采用_____。A.順序存儲(chǔ)B.鏈接存儲(chǔ)C.散列法存儲(chǔ)D.存儲(chǔ)表示不受限制（13）若在線性表中采用折半查找法查找元素，該線性應(yīng)該_____。A.元素按值有序B.采用順序存儲(chǔ)結(jié)構(gòu)C.元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D.元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（14）用二分法查找一個(gè)長度為10的、排好序的線性表，查找不成功是，最多需要比較_____次。A.5B.2C.4D.1（15）采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的塊，每塊分_____個(gè)結(jié)點(diǎn)最佳。A.10B.25C.6D.625（16）如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用_____查找方法。A.分塊B.順序C.二分D.散列（17）散列函數(shù)有一個(gè)共同性質(zhì)，即函數(shù)值應(yīng)按_____取其值域的每一個(gè)值。A.最大概率B.最小概率C.同等概率D.平均概率（18）某順序存儲(chǔ)的表格中有90000個(gè)元素，以按關(guān)鍵字值額定升序排列，假定對(duì)每個(gè)元素進(jìn)行查找的概率相同，且每個(gè)元素的關(guān)鍵字的值都不相同，在用順序查找法查找時(shí)，平均比較次數(shù)約為_____，最大比較次數(shù)為_____。A.25000B.30000C.45000D.90000（19）如果m階B_樹中具有n個(gè)關(guān)鍵字，則葉子結(jié)點(diǎn)（即查找不成功的結(jié)點(diǎn)）為_____。A.n-1B.n+1C.nD.n/2（20）m階B_樹中的所有非終端（除根之外）結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須大于或等于_____。A.m/2B.m/2-1C.m/2+1D.m7.2填空題（1）對(duì)于長度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為_____；若采用折半法查找，則時(shí)間復(fù)雜度為_____。（2）假設(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ù)為_____，平均查找長度為_____。（3）在一棵二叉樹搜索樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定_____該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定_____該結(jié)點(diǎn)的值。（4）在對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)_____。（5）在一棵m階B_樹上，每個(gè)非樹根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為_____個(gè)，最多為_____。（6）對(duì)于線性表（70,34,55,23,65,41,20）進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%7作為散列函數(shù)，則散列地址為0的元素有_____個(gè)，散列地址為6的元素有_____個(gè)。（7）在線性表的散列存儲(chǔ)中，裝填因子α又稱為裝填系數(shù)，若用m表示散列表的長度，用n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則α等于_____。（8）在散列表中解決沖突的兩種方法是_____和_____。（9）在散列存儲(chǔ)中，裝填因子α的值越大，_____；α的值越小，_____。（10）散列法存儲(chǔ)的基本思想是由_____決定數(shù)據(jù)的存儲(chǔ)地址。（11）最優(yōu)二叉樹（哈夫曼樹）、最優(yōu)查樹均為查找路徑長度i=1nwihi最小的樹，其中對(duì)于最優(yōu)二叉樹，n表示_____，對(duì)于最優(yōu)查找樹，n表示_____（12）在分塊檢索中，對(duì)于256個(gè)元素的線性表最好分成_____塊，每塊的最佳長度是_____；若每塊的長度為_____，其平均檢索長度為_____。（13）構(gòu)造哈希函數(shù)的方法有_____。（14）哈希表處理沖突的方法有_____。（15）負(fù)載因子（裝填因子）是散列表的一個(gè)重要參數(shù)，它反映散列表的_____。（16）在分塊查找中首先查找_____，然后查找相應(yīng)的_____。（17）散列表的查找效率主要取決與散列表造表時(shí)選擇的_____和_____。（18）當(dāng)所有結(jié)點(diǎn)的權(quán)值都相等時(shí)，用這些結(jié)點(diǎn)構(gòu)造的二叉排序樹，_____遍歷它們得到的序列的順序是一樣的。（19）對(duì)兩棵具有相同關(guān)鍵字集合但形狀不同的二叉排序樹，_____遍歷它們得到的序列的順序是一樣的。（20）m階B_樹每一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)最多_____m。7.3何謂二叉排序樹？7.4簡述用二次探測法解決沖突的基本思路。7.5順序查找時(shí)間為O(n),二分查找時(shí)間為O(log2n)，散列查找時(shí)間為7.6簡述用多重散列法解決沖突的基本思路。7.7簡述用公共溢出區(qū)法解決沖突的基本思路。7.8在結(jié)點(diǎn)個(gè)數(shù)n(n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？7.9設(shè)單鏈表的結(jié)點(diǎn)是按關(guān)鍵字從小到大排列的，試寫出對(duì)詞鏈表的查找算法，并說明是否可以采用折半查找（二分查找）。7.10試寫一個(gè)判別給定二叉樹是否為二叉排序數(shù)的算法，設(shè)此二叉樹以二叉鏈表做存儲(chǔ)結(jié)構(gòu)。7.11通過散列函數(shù)hashf(x)=xmod11把一個(gè)整數(shù)數(shù)值轉(zhuǎn)換成散列表下標(biāo)，現(xiàn)要把數(shù)據(jù)1、13、12、34、38、33、27、22插入到散列表中。（1）使用線性探查再散列法來構(gòu)造散列表。（2）使用鏈地址法來構(gòu)造散列表。（3）針對(duì)這種情況，確定其裝填因子，查找成功所需的平均查找次數(shù)以及查找不成功所需的平均探查次數(shù)。7.12試寫出二分查找的遞歸算法。7.13假設(shè)線性表中的結(jié)點(diǎn)是按鍵值遞增的順序存放的，試寫一順序查找法，將崗哨設(shè)在高下標(biāo)端，然后分別求出等概率情況下查找成功和不成功時(shí)的平均查找長度。7.14已知紀(jì)錄關(guān)鍵字集合為（53,17,19,61,98,75,79,63,46,49），要求散列到地址區(qū)間（100,101,102,103,104,105,106,107,108,109）內(nèi)，若產(chǎn)生沖突則開型尋址法的線性探測法解決，要求寫出選用的散列函數(shù)、形成的散列表、計(jì)算出查找成功時(shí)的平均查找長度和查找不成功時(shí)的平均查找長度。習(xí)題88.1選擇題。（1）下述排序算法中，穩(wěn)定的是_____。A.直接選擇排序B.直接插入排序C.快速排序D.堆排法（2）下列排序算法中，_____需要的輔助存儲(chǔ)空間最大。A.快速排序B.插入排序C.希爾排序D.基數(shù)排序（3）下列排序算法中，平均時(shí)間復(fù)雜度為O(n2)是_____A.快速排序B.堆排法C.歸并排序D.冒泡排序（4）在基于關(guān)鍵碼比較的排序算法中，_____算法在最壞情況下關(guān)鍵的比較次數(shù)不高于O(logA.冒泡排序B.直接插入排序C.二路歸并排序D.快速排序（5）一組紀(jì)錄為{46,79,56,38,84,40}，則采用冒泡排序法按升序排列時(shí)第一趟的排序結(jié)果是_____。A.46，79，56，38，40，84B.46，56，38，79，40，84C.38，40，46，56，84，79D.38，46，79，56，40，84（6）每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法稱為_____排序。A.插入B.堆C.快速D.歸并（7）每次從無序表中挑選出一個(gè)最小或最大的元素，把它交換到有序表的一端，此種排序方法稱為_____排序。A.插入B.堆C.快速D.歸并（8）設(shè)有一組初始紀(jì)錄關(guān)鍵字序列（5,2,6,3,8），以第一個(gè)紀(jì)錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為_____。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8（9）設(shè)有n個(gè)待排序的紀(jì)錄關(guān)鍵字，則在堆排序中需要_____個(gè)輔助紀(jì)錄單元。A.1B.nC.nlog2n（10）對(duì)于關(guān)鍵字序列（12,13,11,18,60,15,7,18,25,100），用篩選法建堆，必須從關(guān)鍵字值為_____的結(jié)點(diǎn)開始。A.100B.12C.60D.15（11）在下列排序方法中，比較次數(shù)與紀(jì)錄的初始排列狀態(tài)無關(guān)的方法是_____。A.直接插入排序B.冒泡排序C.快速排序D.直接選擇排序（12）設(shè)有關(guān)鍵碼初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X},新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用_____方法對(duì)初始序列進(jìn)行第一趟掃描的結(jié)果。A.直接插入排序B.二路歸并排序C.以第一個(gè)元素為分界元素的快速排序D.基數(shù)排序（13）在待排序文件已基本有序的前提下，下述排序方法中效率最高的是_____。A.直接插入排序B.直接選擇排序C.快速排序D.歸并排序（14）排序的算法很多，若按排序的穩(wěn)定性和不穩(wěn)定性分類，則_____是不穩(wěn)定排序。A.冒泡排序B.歸并排序C.直接插入排序D.希爾（15）若需在On(log2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序A.快速排序B.堆排序C.歸并排序D.直接插入排序（16）將兩者各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是_____。A.nB.2n-1C.2nD.n-1（17）下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)的影響，恒為O(log2n)A.堆排序B.冒泡排序C.直接插入排序D.快速排序（18）下列排序算法中，_____算法可能會(huì)出現(xiàn)下面的情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。A.堆排序B.冒泡排序C.快速排序D.Shell排序（19）數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用_____算法最節(jié)省時(shí)間。A.堆排序B.希爾排序C.快速排序D.直接插入排序（20）如果只想得到1024個(gè)元素組成的序列中第5個(gè)最小袁術(shù)之前的部分排列的序，用_____方法最快。A.冒泡排序B.快速排序C.簡單選擇排序D.堆排序8.2填空題（1）當(dāng)待排序的紀(jì)錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不做要求時(shí)，宜采用_____排序；當(dāng)待排序的紀(jì)錄數(shù)較大，存儲(chǔ)空間允許且要求排序穩(wěn)定時(shí)，宜采用____