《數(shù)據(jù)結(jié)構(gòu)》習(xí)題集楊先鳳 朱小梅編西南石油大學(xué)計(jì)算機(jī)科學(xué)學(xué)院二零零七年九月目錄TOC\o"1-1"\h\z\u習(xí)題一緒論 1習(xí)題二線性表 5習(xí)題三棧和隊(duì)列 10習(xí)題四串 14習(xí)題五數(shù)組和廣義表 17習(xí)題六樹(shù)和二叉樹(shù) 21習(xí)題七圖 27習(xí)題八查找 32習(xí)題九排序 36習(xí)題十文件 40PAGEPAGE42習(xí)題一緒論一、單項(xiàng)選擇題1．?dāng)?shù)據(jù)結(jié)構(gòu)被形式地定義(K，R)，其中K是（① ）的有限集是K上的（② 有限集。①A．算法 數(shù)據(jù)元素 C．?dāng)?shù)據(jù)操作 D邏輯結(jié)構(gòu)②A．操作 映像 C存儲(chǔ) D關(guān)2．在數(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é)C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)3．?dāng)?shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指（ A．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)元素之間的關(guān)系4．在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)A．邏輯 B．存儲(chǔ) 邏緝和存儲(chǔ) 物理5．算法分析的目的是（① ，算法分析的兩個(gè)主要方面是（② ①A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中的輸入和輸出的關(guān)系C分折算治的效率以求改進(jìn)D分析算法的易讀性和文檔性②A空間復(fù)雜度和時(shí)間復(fù)雜度B正確性和簡(jiǎn)明性C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)（ A數(shù)據(jù)的處理方法 數(shù)據(jù)元素的類(lèi)型C數(shù)據(jù)元素之間的關(guān)系 D數(shù)據(jù)的存儲(chǔ)方法算法的計(jì)算量的大小稱為計(jì)算的（ 。效率 B.復(fù)雜性 C.現(xiàn)實(shí)性 D.難度算法的時(shí)間復(fù)雜度取決于（ ）問(wèn)題的規(guī)模 B.待處理數(shù)據(jù)的初態(tài) C.A和B下面說(shuō)法錯(cuò)誤的是（ ）(1）算法原地工作的含義是指不需要任何額外的輔助空在相同的規(guī)模nO(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越A．(1) B.(1),(2) C.(1),(4) D.(3)在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（ for(i=1;i<=n;i++)for(j=1;j<=n;j++)x:=x+1;O(2n) D．O(logn)2二、判斷題（）線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來(lái)存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來(lái)存放（ ）數(shù)據(jù)元素是數(shù)據(jù)的最小單位( )記錄是數(shù)據(jù)處理的最小單位。( )算法就是程序（ ）數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系6．?dāng)?shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式( 在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系( )順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高( )線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址一定是不連續(xù)的( )數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié).( )三、填空題1.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的__和__，以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的_設(shè)計(jì)出相應(yīng)的 。2.對(duì)于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有_四種。，，，3個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)續(xù)結(jié)點(diǎn)。后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有個(gè)后4．在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以。5．一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中稱為存儲(chǔ)結(jié)構(gòu)。通常存儲(chǔ)結(jié)點(diǎn)之間可以四種關(guān)方式，稱為四種基本存儲(chǔ)方式。抽象數(shù)據(jù)類(lèi)型的定義僅取決于它的一

而_ 無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它_ 不變，都不影響其外部使用8．?dāng)?shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是一個(gè)算法具有5個(gè)特: 、 、 ，有零或多個(gè)輸入、有一個(gè)或多個(gè)輸出。常見(jiàn)時(shí)間復(fù)雜性的量級(jí)有：常數(shù)階O( 、對(duì)數(shù)階O( 、線性O(shè)( 、平方階O( 、和指數(shù)階O( 。通常認(rèn)為，具指數(shù)階量級(jí)的算法，而量級(jí)低于平方階的算法的。計(jì)算機(jī)執(zhí)行下面的語(yǔ)句時(shí)，語(yǔ)句s的執(zhí)行次數(shù)為 for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;m.nn的數(shù)目。例f(5,3)=553+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。以下是該函數(shù)的程序段，請(qǐng)將未完成的部分填入，使之完整intf(m,n)int{if(m==1)return(1) ;if(n==1){return(2) ;}if(m<n){returnf(m,m);}if(m==n){return1+(3) ;}returnf(m.n-1)+f(m-n,(4) );}執(zhí)行程序，f(6,4)= 。程序段“i=1;while(i<=n)i=i*2;”的時(shí)間復(fù)雜度T(n)= 四、應(yīng)用題們分別屬于何種結(jié)構(gòu)。1）A（，R，其中：K={a,b,c,d,e,f,g,h}R={r}r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>}2）B（，R，其中：K={a,b,c,d,e,f,g,h}R={r}r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>},3）C（，RK={1,2,3,4,5,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}這里的圓括號(hào)對(duì)表示兩結(jié)點(diǎn)是雙向的。1004寫(xiě)出這些結(jié)構(gòu)？調(diào)用下列函數(shù)f(n)試指出f(n)值的大小，并寫(xiě)出f(n)假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時(shí)的輸出結(jié)果。Cintf(intn){inti,j，k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--)for(k=1;k<j+1;k++sum++;printf("sum=%d\n",sum)；}return(sum);}設(shè)計(jì)求解下列問(wèn)題的類(lèi)C在數(shù)組A[1..n]中查找值為K的元素,若找到則輸出其位置i(1<=i<=n)0找出數(shù)組A[1..n（準(zhǔn)操作。習(xí)題二線性表一、單項(xiàng)選擇題1．順序表是線性表的（ A．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) B．順序存儲(chǔ)結(jié)構(gòu) C．索引存儲(chǔ)結(jié)構(gòu) D．散列存儲(chǔ)結(jié)構(gòu)對(duì)于順序表，以下說(shuō)法錯(cuò)誤的是（ ）A．順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對(duì)地B．順序表的所有存儲(chǔ)結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列C．順序表的特點(diǎn)邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰D．順序表的特點(diǎn)邏輯上相鄰的元素，存儲(chǔ)在物理位置也相鄰的單元中線性表是具有n個(gè)（ ）的有限序列n>。A．表元素 字符 數(shù)據(jù)元素 數(shù)據(jù)項(xiàng) 信息4.以下說(shuō)法錯(cuò)誤的是()LocateElemO（n）讀表元運(yùn)算在順序表上只需常數(shù)時(shí)間結(jié)構(gòu)在鏈表上實(shí)現(xiàn)讀表元運(yùn)算的平均時(shí)間復(fù)雜度為O（1）D．插入、刪除操作在鏈表上的實(shí)現(xiàn)可在O（1）時(shí)間內(nèi)完成E．插入、刪除操作在順序表上的實(shí)現(xiàn)，平均時(shí)間復(fù)雜度為若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（ 存儲(chǔ)方式最節(jié)省時(shí)間。A．順序表 單鏈表 雙鏈表 單循環(huán)鏈表6．設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選( 最節(jié)省時(shí)間A.單鏈表 B.單循環(huán)鏈表 C.帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表靜態(tài)鏈表中指針表示的是（ ）.內(nèi)存地址 數(shù)組下標(biāo) 下一元素地址 左、右孩子地址鏈表不具有的特點(diǎn)是（ ）A．插入、刪除不需要移動(dòng)元素B．可隨機(jī)訪問(wèn)任一元素C．不必事先估計(jì)存儲(chǔ)空間D．所需空間與線性長(zhǎng)度成正在循環(huán)鏈表中，將頭指針改設(shè)為尾指針rea）后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分是（ ）rear和rear->next->nextB．rear->next和rearC．rear->next->next和rearD．rearrear->next 對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ 。A．O(n)O(n) B.O(n)O(1) C.O(1)O(n) D.O(1)線性（以鏈接方式存儲(chǔ)時(shí)訪問(wèn)第i位置元素的時(shí)間復(fù)雜性（ A．O（i） 在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是（ 。A．p->next=s;s->next=p->next; s->next=p->next;p->next=s;C．p->next=s;p->next=s->next; p->next=s->next;p->next=s;對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ ）head==NULL B．head→next==NULLC．head→next==head 二、判斷題（）1.鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用( )2．線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的( 3．順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好( )所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表( )線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼( )循環(huán)鏈表不是線性.( )線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)( )線性表就是順序存儲(chǔ)的表( )鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性,進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)構(gòu)中效率高。( )三、填空題在順序表中，邏輯上相鄰的元素，其物理位置 相鄰。在單鏈表中，邏輯上鄰的元素，其物理位置 相鄰。在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲(chǔ)位置由 指示，首元素結(jié)點(diǎn)的存儲(chǔ)位置由 指示除首元素結(jié)點(diǎn)外其它任一元素結(jié)點(diǎn)的存儲(chǔ)位由 指示。在單鏈表中若在每個(gè)結(jié)點(diǎn)中增加一個(gè)指針,所含指針指向前驅(qū)結(jié)點(diǎn)，這樣構(gòu)成的鏈中有兩個(gè)方向不同的鏈，稱。對(duì)于順序表的插入算法insert_sqlist來(lái)說(shuō)，若以結(jié)點(diǎn)移動(dòng)為標(biāo)準(zhǔn)操作，則插入算法在最壞情況下的移動(dòng)次數(shù)，時(shí)間復(fù)雜度。在平均情況下的移動(dòng)次數(shù)，時(shí)間復(fù)雜度。線性表的常見(jiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、 和 。單鏈表表示法的基本思想是表示結(jié)點(diǎn)間的邏輯關(guān)系。線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)。設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)指針py指向data為y的新結(jié)點(diǎn),若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后則需要執(zhí)以下語(yǔ): ； ;對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共 個(gè)，單鏈表為 個(gè)。以下為順序表的定位運(yùn)算，分析算法，請(qǐng)?zhí)幪钌险_的語(yǔ)句intlocate_sqlist(sqlistL,datatypeX)/*在順序表L中查找第一值等于X的結(jié)點(diǎn)。若找到回傳該結(jié)點(diǎn)序號(hào)；否則回傳0*/{ ;if( )return(i);else return(0);}對(duì)單鏈表中元素按插入方法排序的C語(yǔ)言描述算法如下，其中L為鏈表頭結(jié)點(diǎn)指針。請(qǐng)?zhí)畛渌惴ㄖ袠?biāo)出的空白處，完成其功能。typedefstructnode{intdata;structnode*next;}linknode,*link;voidInsertsort(link{linkp,q,r,u;p=L->next; (1) ;while((2) ){r=L;q=L->next;while((3) &&q->data<=p->data){r=q;q=q->next;}u=p->next;(4) }}

;(5)

;p=u;下面是一個(gè)求兩個(gè)集合A和B之差C=A-B的程序，即當(dāng)且僅當(dāng)e是AB才是C為空；操作完成后A，B中元素按遞增排列。下面append(last,eelastdifference(A,B)實(shí)現(xiàn)集合運(yùn)算C的鏈表的首結(jié)點(diǎn)的地址。在執(zhí)行A-B頭結(jié)點(diǎn)，以便新結(jié)點(diǎn)的添加，當(dāng)A-B運(yùn)算執(zhí)行完畢，再刪除并釋放表示結(jié)果集合的鏈表的表頭結(jié)點(diǎn)。typedefstructnode{intelement;structnode*link;}NODE;NODE*A，*B，*C;NODE*append(NODE*last,inte){last->link=(NODE*)malloc(sizeof(NODE));last->link->element=e;return(last->link);}NODE*difference(NODE*A,NODE*B){NODE*C,*last;C=last=(NODE*)malloc(sizeof(NODE));while(1)_if(A->element<B->element){last=append(last,A->element);A=A->link;}elseif(2)

{A=A->link;B=B->link;}ELSE(3) ;while(4) {last=append(last,A->element);A=A->link;}(5)}

;last=C; C=C->link;free(last); return(C);/*callform:C=difference(A,B);*/四、應(yīng)用題是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義（也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。參考答案：在單鏈表中不能從當(dāng)前結(jié)點(diǎn)（若當(dāng)前結(jié)點(diǎn)不是第一結(jié)點(diǎn)）出發(fā)訪問(wèn)到任何一個(gè)從當(dāng)前結(jié)點(diǎn)向前到第一結(jié)點(diǎn)，向后到最后結(jié)點(diǎn)，可以訪問(wèn)到任何一個(gè)結(jié)點(diǎn)。（1）說(shuō)明該算法的功能（2）voidunknown(BNODETP*L){ …p=L->next;q=p->next;r=q->next；while(q!=L){while(p!=L)&&(p->data>q->data)p=p->prior；q->prior->next=r；(1)_ q->next=p->next；q->prior=p；(2) (4) }}

；(3) ；

；q=r；p=q->prior；參考答案：1）本算法功能是將雙向循環(huán)鏈表結(jié)點(diǎn)的數(shù)據(jù)域按值自小到大排序，成為非遞減（可能包括數(shù)據(jù)域值相等的結(jié)點(diǎn)）有序雙向循環(huán)鏈表。2）(1)r->prior=q->prior;∥將q(2)p->next->prior=q）將q結(jié)點(diǎn)插入(3)p->next=q;(4)r=r->next;或r=q->next;∥后移指針，再將新結(jié)點(diǎn)插入到適當(dāng)位置。五、算法設(shè)計(jì)題A[1..sizenum各分量中，且遞增有序。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，將x所設(shè)計(jì)算法的時(shí)間復(fù)雜度。附加空間)逆置的算法，在原表的存儲(chǔ)空間內(nèi)將線性表(aa.,a)逆置為1 2 n(a.,a,an 2 1試編寫(xiě)在無(wú)頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表基本運(yùn)算LOCATE(L,X)、INSERT(L,X，iDELETE(L,i)的算法，并和在帶頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)相的算法進(jìn)行比較。4．將線性表A=(a1,a2,……am),B=(b1,b2,……bn)合并成線性表C,C=(a1,b1,……am,bm,bm+1,…….bn) 當(dāng)m<=n時(shí)或C=(a1,b1,……an,bn,an+1,……am)當(dāng)m>n時(shí)線性表C以單鏈表作為存儲(chǔ)結(jié)構(gòu)且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。nA0(n)、空間復(fù)雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素空間為常量。假設(shè)在長(zhǎng)度大于1s*s約瑟夫環(huán)問(wèn)題1,2,…,nnm,從第一個(gè)人開(kāi)始順時(shí)針自1開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m1報(bào)數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計(jì)一個(gè)各人的編號(hào)。例如m的初值為20n=77個(gè)人的密碼依次是：3,1,7,2,4,8,46,1,4,7,2,3,5。習(xí)題三棧和隊(duì)列一單項(xiàng)選擇題在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否(① ),在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否(②)。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為(③)。①,②:A.空B.滿 C.上溢D.下溢③:A.n-1B.n C.n+1D.n/2若已知一個(gè)棧的進(jìn)棧序列是其輸出序列為若p1＝3，則p2( 。A可能是2 B一定是2 C可能是1 D一定是1有六個(gè)元素的順序進(jìn)棧問(wèn)下列哪一個(gè)不是合法的出棧序列A.543612 B.453126 C.346521 D.234156設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧如果6個(gè)元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是 （ ）A.2 B.3 C.5 D.6若棧采用順序存儲(chǔ)方式存儲(chǔ)現(xiàn)兩棧共享空間代表第i個(gè)(i棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（ 。A.|top[2]-top[1]|=0 B.top[1]+1=top[2]C.top[1]+top[2]=m D.top[1]=top[2]執(zhí)行完下列語(yǔ)句段后值為：（ ）int f(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2 B.4 C.8 D.表達(dá)式3*2^(4+2*2-6*3)-5求值過(guò)程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（ ，中^為乘冪。A.3,2,4,1,1；(*^(+*- B.C.3,2,4,2,2；(*^(- D.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（ 。僅修改頭指針 B.僅修改尾指針C.頭、尾指針都要修改 D.頭、尾指針可能都要修改遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)A．隊(duì)列 多維數(shù)組 棧 D.線性表設(shè)C語(yǔ)言數(shù)組Data[m+1]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針則執(zhí)行出隊(duì)操作的語(yǔ)句為 （ front=front+1 B.mC.rear=(rear+1)%(m+1) D.front=(front+1)%(m+1)循環(huán)隊(duì)列的隊(duì)滿條件為()(sq.rear+1)%maxsize==(sq.front+1)%maxsize;(sq.front+1)%maxsize==sq.rear(sq.rear+1)%maxsize==sq.frontD.sq.rear==sq.front棧和隊(duì)列的共同點(diǎn)是（ 。都是先進(jìn)先出 B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素 D.沒(méi)有共同點(diǎn)二、填空題棧的線性表，其運(yùn)算遵的原則。一個(gè)棧的輸入序列是則不可能的棧輸出序列。用S表示入棧操作表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出順序，相應(yīng)的S和X的操作串。循環(huán)隊(duì)列的引入，目的是為了克。隊(duì)列是限制插入只能在表的一端而刪除在表的另一端進(jìn)行的線性表其特點(diǎn)。已知鏈隊(duì)列的頭尾指針?lè)謩e是f和r，則將值x入隊(duì)的操作序列7．表達(dá)式求值應(yīng)用的一個(gè)典型例子。循環(huán)隊(duì)列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針?lè)謩e是front和rear，當(dāng)前隊(duì)列的元素個(gè)數(shù)。以下運(yùn)算實(shí)現(xiàn)在鏈棧上的初始化，請(qǐng)?zhí)幱谜?qǐng)適當(dāng)句子予以填充VoidInitStacl(LstackTp*ls){ ;}`VoidPush（LStackTp*ls,DataType{LstackTp*p;p=malloc(sizeof(LstackTp)); p->next=ls; ;}以下運(yùn)算實(shí)現(xiàn)在鏈棧上的退棧，請(qǐng)?zhí)幱谜?qǐng)適當(dāng)句子予以填充IntPop(LstackTp*ls,DataType*x){LstackTp*p;if(ls!=NULL){p=ls;*x= ls=ls->next; return(1)；}elsereturn(0);}以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的入隊(duì)列，請(qǐng)?zhí)幱眠m當(dāng)句子予以填充VoidEnQueue(QueptrTp*lq,DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp)); p->next=NULL;(lq->rear)->next= ; ;}三、應(yīng)用題1．畫(huà)出對(duì)算術(shù)表達(dá)式A-B*C/D-E↑F將兩個(gè)棧存入數(shù)組V[1..m]應(yīng)如何安排最好？這時(shí)棧空、棧滿的條件是什么？四、算法設(shè)計(jì)題設(shè)表達(dá)式以字符形式已存入數(shù)組E[n中括號(hào)（’和‘）是否配對(duì)的CEXYX(E);假設(shè)以I和OI和O下面所示的序列中哪些是合法的？A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO通過(guò)對(duì)true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中。設(shè)有兩個(gè)棧S,S[O..maxsize-1],為了盡量利1 2S,S1 2和出棧的操作算法。請(qǐng)利用兩個(gè)棧S1S2xSTSTenqueue刪除一個(gè)元素出隊(duì)列；queue_empty（請(qǐng)寫(xiě)明算法的思想及必要的注釋）要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用，設(shè)置一個(gè)標(biāo)志tag,以tag0來(lái)區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿，請(qǐng)編寫(xiě)與此相應(yīng)的入隊(duì)與出隊(duì)算法。已知Q是一個(gè)空棧。僅用隊(duì)列和棧的ADT寫(xiě)一個(gè)算法，將隊(duì)列QADTmakeEmpty(s:stack); 置空棧push(s:stack;value:datatype); 新元素value進(jìn)棧pop(s:stack):datatype; 出棧，返回棧頂isEmpty(s:stack):Boolean; 隊(duì)列的ADTenqueue(q:queue:value:datatype);deQueue(q:queue):datatype;isEmpty(q:queue):boolean;

元素value進(jìn)隊(duì)出隊(duì)列，返回隊(duì)頭值判隊(duì)列空否習(xí)題四串一、單項(xiàng)選擇題1．下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（ A．串是字符的有限序列 空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱娲且环N特殊的線性表，其特殊性體現(xiàn)在（ 。A．可以順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以鏈接存儲(chǔ)D．?dāng)?shù)據(jù)元素可以是多個(gè)字符3．串的長(zhǎng)度是指（）A．串中所含不同字母的個(gè)數(shù) 串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù) 串中所含非空格字符的個(gè)設(shè)有兩個(gè)串p和其中q是p的子串求q在p中首次出現(xiàn)的位置的算法稱（ A．求子串 聯(lián)接 C．匹配 求串長(zhǎng)若串S=“software”,其子串的個(gè)數(shù)是（ ）A．8 二、填空題含零個(gè)字符的串稱串。任何串中所的個(gè)數(shù)稱為該串的長(zhǎng)度?？崭翊?，其長(zhǎng)度等。當(dāng)且僅當(dāng)兩個(gè)串相等并且各個(gè)對(duì)應(yīng)位置上的字符時(shí)，這兩個(gè)串相等一個(gè)串中任意個(gè)連續(xù)字符組成的序列稱為該串串，該串稱為它所有子串串。INDE‘DATASTRUCTUR‘STR）= 。模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列。下列程序判斷字符串s10；如f("abba"f("abab"0；intf((1) ){int i=0,j=0;while(s[j])(2) ;for(j--;i<j&&s[i]==s[j];i++,j--);return((3) )}下列算法實(shí)現(xiàn)求采用順序結(jié)構(gòu)存儲(chǔ)的串s和串tvoidmaxcomstr(orderstring*s,*t;intindex,length){inti,j,k,length1,con;index=0;length=0;i=1;while(i<=s.len){j=1;while(j<=t.len){if(s[i]==t[j]){k=1;length1=1;con=1;while(con)if(1) _{length1=length1+1;k=k+1;}else(2) ;if(length1>length){index=i;length=length1;}(3) ;}else(4) ;}(5)}}三、應(yīng)用題1．設(shè)有A=””:A+BCONCAT（A,B）的簡(jiǎn)寫(xiě),A=""的""含有兩個(gè)空格)。A+BB+AD+C+BSUBSTR(B,3,2)SUBSTR(C,1,0)LENGTH(A)LENGTH(D)INDEX(B,D)INDEX(C,"d")INSERT(D,2,C)INSERT(B,1,A)DELETE(B,2,2)DELETE(B,2,0)設(shè)主串S‘xxyxxxyxxxxyxyT‘xxyxTS給出字符串‘a(chǎn)bacabaaad’在KMPnextnextvals＝（xy）＋＊t＝＋）s轉(zhuǎn)化為t。四、算法設(shè)計(jì)題在順序串上實(shí)現(xiàn)串的判等運(yùn)算EQUAL(S,T)。在鏈串上實(shí)現(xiàn)判等運(yùn)算EQUAL(S,T)。若S和T是用結(jié)點(diǎn)大小為1的單鏈表存儲(chǔ)的兩個(gè)串ST為頭指針ST以順序存儲(chǔ)結(jié)構(gòu)表示串，設(shè)計(jì)算法。求串S中出現(xiàn)的第一個(gè)最長(zhǎng)重復(fù)子串及其位置并分析算法的時(shí)間復(fù)雜度（如果字符串的一個(gè)子串（其長(zhǎng)度大于1）的各個(gè)字符均相同，稱之為等值子串。如果輸入字符串S，以“”作為結(jié)束標(biāo)志。串S中不存在等值子串，則輸出信息“無(wú)等值子串”，否則求出（輸出）一個(gè)長(zhǎng)度最大的等值子串。例如：若 S=“abc123abc123!，則輸出“無(wú)等值子串”；若S=“abceebccadddddaaadd!，則輸出dddd）寫(xiě)一個(gè)遞歸算法來(lái)實(shí)現(xiàn)字符串逆序存儲(chǔ)，要求不另設(shè)串存儲(chǔ)空間。習(xí)題五數(shù)組和廣義表一、單項(xiàng)選擇題1．常對(duì)數(shù)組進(jìn)行的兩種基本操作是（ A.建立與刪除 B.索引與修改 C.查找與修改 D.查找與索引2．對(duì)于C語(yǔ)言的二維數(shù)組DataTypeA[m][n],每個(gè)數(shù)據(jù)元素占K個(gè)存儲(chǔ)單元，二維數(shù)組任意元素a[i,j]的存儲(chǔ)位置可(式確.A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*kB.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*kC.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*kD.Loc[i,j]=[(n+1)*i+j]*k稀疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ) ()非零元素 B.三元祖（i,j,aij） C.aij D.i,j數(shù)組A[0..5,0..6]的每個(gè)元素占五個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為的內(nèi)存單元中，則元素的地址( 。A.1175 B.1180 C.1205 D.1210是對(duì)稱矩陣，將下面三角（包括對(duì)角線）以行序存儲(chǔ)到一維數(shù)中，則對(duì)任一上三角元素a[i][j]對(duì)應(yīng)T[k]的下標(biāo)k是（ 。A.i（i-1）/2+j B.j（j-1）/2+i C.i（j-i）/2+1 D.j（i-1）/2+1用數(shù)組rnextjj沿鏈移動(dòng)的操作為()。A.j=r[j].nextB.j=j+1C.j=j->nextD.j=r[j]->next對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是（ 。A．便于進(jìn)行矩陣運(yùn)算 便于輸入和輸C．節(jié)省存儲(chǔ)空間 降低運(yùn)算的時(shí)間復(fù)雜度已知廣義表LS＝((a,b,c),(d,e,f)),運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算( 。head(tail(LS)) B.tail(head(LS))C.head(tail(head(tail(LS))) D.head(tail(tail(head(LS))))廣義表a,b,c,）的表頭是（ ，表尾是（ 。A.a C.（a,b,c,d） D.（b,c,d）設(shè)廣義表La,b,，則L的長(zhǎng)度和深度分別為（ 。A.1和1 B.1和3 C.1和2 D.2和3下面說(shuō)法不正確的( 。廣義表的表頭總是一個(gè)廣義表 B.廣義表的表尾總是一個(gè)廣義表C.廣義表難以用順序存儲(chǔ)結(jié)構(gòu) D.廣義表可以是一個(gè)多層次的結(jié)構(gòu)二、填空題通常采存儲(chǔ)結(jié)構(gòu)來(lái)存放數(shù)組對(duì)二維數(shù)組可有兩種存儲(chǔ)方法一種是以 為主序的存儲(chǔ)方式，另一種是為主序的存儲(chǔ)方式。用一維數(shù)組B與列優(yōu)先存放帶狀矩陣A中的非零元素A[i,j]中的第8個(gè)元素是A中的_ 行，_ 列的元素。設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組中，若按行為主序儲(chǔ)，則A[i,j]對(duì)應(yīng)的B中存儲(chǔ)位置。所謂稀疏矩陣指的_ 。廣義表簡(jiǎn)稱表，是由零個(gè)或多個(gè)原子或子表組成的有限序列，原子與表的差別僅在于。為了區(qū)分原子和表，一般用

表示表，用 表示原子。一個(gè)表的長(zhǎng)度是指

，而表的深度是 設(shè)廣義表L=((),()),則head(L)是 是 ；L的長(zhǎng)度是 ；深度是 ?；谌M的稀疏矩陣轉(zhuǎn)置的處理方法有兩種以下運(yùn)算按照矩陣A的列序來(lái)進(jìn)行轉(zhuǎn)置請(qǐng)?jiān)?處用適當(dāng)?shù)木渥佑靡蕴畛?。Trans_Sparmat(SpMatrixTpa,SpMatrixTp*b){ (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu;if(a.tu){ q=1;for(col=1; for(p=1;p<=a.tu;p++)if( ==col){(*b).data[q].i=a.data[p].j;(*b).data[q].j=a.data[p].i;(*b).data[q].v=a.data[p].v; ;}}e,）,c（b,。typedefstructglistnode{inttag;structglistnode*next;union{chardata;struct{structglistnode*hp,*tp;}ptr;}val;}*glist,gnode;glistreverse(p)glistp;{glistq,h,t,s;if(p==NULL)else{if(1) {q=(glist)malloc(sizeof(gnode));q->tag=0;q->val.data=p->val.data;}else{(2)if(3){t=reverse(p->val.ptr.tp);s=t;while(s->val.ptr.tp!=NULL) s->val.ptr.tp=(glist)malloc(sizeof(gnode));s=s->val.ptr.tp;s->tag=1;s->val.ptr.tp=NULL;s->val.ptr.hp=h;(4) }else{q=(glist)malloc(sizeof(gnode));q->tag=1;q->val.ptr.tp=NULL;(5) ;}}}return(q);}三、應(yīng)用題數(shù)組A[1..8，-2..6，0..6]以行為主序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是784，試求元素A[4,2,3]的存儲(chǔ)首地址。特殊矩陣和稀疏矩陣哪一種壓縮存儲(chǔ)后失去隨機(jī)存取的功能？為什么？數(shù)組，廣義表與線性表之間有什么樣的關(guān)系？(a)n*nB(1:3n-2)中，使ijB[k]=a，求：ij用i,j表示k用k表示i,j((((a),b)),(((),d),(e,f)))求下列廣義表運(yùn)算的結(jié)果：（1） HEAD[((a,b),(c,d))];（2） TAIL[((a,b),(c,d))];（3） TAIL[HEAD[((a,b),(c,d))]];HEAD[TAIL[HEAD[((a,b),(c,d))]]];TAIL[HEAD[TAIL[((a,b),(c,d))]]];利用廣義表的Head和Ｔail運(yùn)算，把原子d(((((a),b),d),e)；L＝a,(b,((d)),e。四、算法設(shè)計(jì)題給定nxm矩陣A[a..b,c..d],并設(shè)A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i+1,j](a≤i≤b-1,c≤j≤d).設(shè)計(jì)一算法判定X的值是否在A中,要求時(shí)間復(fù)雜度為O(m+n)。設(shè)二維數(shù)組a[1..m,1..n]含有m*n個(gè)整數(shù)。寫(xiě)出算法：判斷a(yes/no)；試分析算法的時(shí)間復(fù)雜度。設(shè)A[1..1001至B[1..100]的內(nèi)容調(diào)整AB[1]=ll的內(nèi)容調(diào)整到A[11]中去。規(guī)定可使用的附加空間為O(1)。n>=0，其中ain=0習(xí)題六樹(shù)和二叉樹(shù)一、單項(xiàng)選擇題以下說(shuō)法錯(cuò)誤的是( )A．樹(shù)形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前B．線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C．樹(shù)形結(jié)構(gòu)可以表(組)更復(fù)雜的數(shù)據(jù)D．樹(shù)(及一切樹(shù)形結(jié)構(gòu))是一種"分支層次"結(jié)構(gòu)E．任何只含一個(gè)結(jié)點(diǎn)的集合是一棵樹(shù)下列說(shuō)法中正確的是( )A．任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為任何一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為2任何一棵二叉樹(shù)中的度肯定等于2任何一棵二叉樹(shù)中的度可以小于23．討論樹(shù)、森林和二叉樹(shù)的關(guān)系，目的是為了（ A．B．將樹(shù)、森林按二叉樹(shù)的存儲(chǔ)方式進(jìn)行存儲(chǔ)C．將樹(shù)、森林轉(zhuǎn)換成二叉樹(shù)D．體現(xiàn)一種技巧，沒(méi)有什么實(shí)際意義樹(shù)最適合用來(lái)表示( )有序數(shù)據(jù)元素 無(wú)序數(shù)據(jù)元素C．元素之間具有分支層次關(guān)系的數(shù)據(jù) 元素之間無(wú)聯(lián)系的數(shù)據(jù)10210（）A．9 設(shè)森林F中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別和M3。與森F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（ 。A．M1 B．M1+M2 一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）A．250 500 C．254 D．505 以上答案都不設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)( )A．不確定 二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為（ ）2I

2I-1-1

-1一棵二叉樹(shù)高度為所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹(shù)最少( 結(jié)A．2h B．2h-1 利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（ 。指向最左孩子 指向最右孩子 空 非空12．已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)為（ 。A．CBEFDA ．FEDCBA ．CBEDFA dabec,中序遍歷序列是debac,它的前序遍歷是（ 。A．a(chǎn)cbed B．decab C．deabc D．cedba在二叉樹(shù)結(jié)點(diǎn)的先序序列中序序列和后序序列中所有葉子結(jié)點(diǎn)的先后順（ A．都不相同 完全相同C．先序和中序相同，而與后序不同 中序和后序相同，而與先序不15．在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)（ 。左子結(jié)點(diǎn) 右子結(jié)點(diǎn)C．左子結(jié)點(diǎn)和右子結(jié)點(diǎn) 左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)在下列情況中，可稱為二叉樹(shù)的是（ A．每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的樹(shù)哈夫曼樹(shù)C．D.每個(gè)結(jié)點(diǎn)只有一棵右子樹(shù)E．以上答案都不對(duì)一棵左右子樹(shù)均不空的二叉樹(shù)在先序線索化后，其中空的鏈域的個(gè)數(shù)是。0 B.1 C.2 D.引入二叉線索樹(shù)的目的是（ ）加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B．為了能在二叉樹(shù)中方便的進(jìn)行插入與刪C．為了能方便的找到雙親 使二叉樹(shù)的遍歷結(jié)果唯一19．n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有的線索數(shù)為（ ）A．2n 20．由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？（ ）A．2 21．下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（ A．{0,10,110,1111} B．{11,10,001,101,0001}C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc}一棵有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，按層次從上到下，同一層從左到右順序存儲(chǔ)在一維數(shù)組A[1..n]中，則二叉樹(shù)中第i1）的右孩子在數(shù)組A位置是（）A．A[2i](2i<=n) B．A[2i+1](2i+1<=n)C．A[i-2] 23、以下說(shuō)法錯(cuò)誤的是()A．哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。B．后序遍歷序列中的第一個(gè)結(jié)點(diǎn)。C．根結(jié)點(diǎn)是哪一個(gè)。D．后。二、判斷題（）1.完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)( )2．對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為。( 二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序( )遍歷是一致的。()用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)( )6．中序遍歷一棵二叉排序樹(shù)的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。( 7．完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是樹(shù)葉( )二叉樹(shù)只能用二叉鏈表表示( )給定一棵樹(shù)，可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)( )用鏈(llink-rlink)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n-1空指針( )樹(shù)形結(jié)構(gòu)中元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系( )將一棵樹(shù)轉(zhuǎn)成二叉樹(shù)，根結(jié)點(diǎn)沒(méi)有左子樹(shù)( )度為二的樹(shù)就是二叉樹(shù)( )二叉樹(shù)中序線索化后，不存在空指針域( )15．霍夫曼樹(shù)的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)( )16．哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近( 三、填空題在二叉樹(shù)中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件。深度為k的完全二叉樹(shù)至少個(gè)結(jié)點(diǎn)，至多個(gè)結(jié)點(diǎn)。高度為8的完全二叉樹(shù)至少個(gè)葉子結(jié)點(diǎn)。具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),一共個(gè)指針,其中只個(gè)用來(lái)指向結(jié)的左右孩子，其余個(gè)指針域?yàn)镹ULL。樹(shù)的主要遍歷方法、 等三種。一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹(shù)按層次（同層次從左到右）用自然數(shù)依此對(duì)結(jié)點(diǎn)編號(hào)則編號(hào)最小的葉子的序號(hào)

_；編號(hào)是i的結(jié)點(diǎn)所在的層次號(hào)是_

（1。如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B是A的雙親，則B的度。二叉樹(shù)的先序序列和中序序列相同的條件。一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。

樹(shù)而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即若一個(gè)二叉樹(shù)的葉子結(jié)點(diǎn)是某子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的 序列中的最后一個(gè)結(jié)點(diǎn)。若作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù)則其帶權(quán)路徑長(zhǎng)度。以下程序段采用先根遍歷方法求二叉樹(shù)的葉子數(shù)，請(qǐng)?jiān)跈M線處填充適當(dāng)?shù)恼Z(yǔ)句。Voidcountleaf(bitreptrt,intt，假定葉子數(shù)count0*/

{if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL)) countleaf(t->lchild,&count);}}類(lèi)型的定義如下：typedefstructnode /*C/{chardata;structnode*lchild,*rchild;}*bitree;voidvst(bitreebt) /*bt*/{bitreep;p=bt;initstack(s); 初始化棧s為空while(p||!empty(s)) 棧s不為*/if(p){push(s,p);(1)

;} /*P*/else{p=pop(s);printf(“%c”,p->data);(2) */}

;棧頂元素出棧二叉樹(shù)存儲(chǔ)結(jié)構(gòu)同上題，以下程序?yàn)榍蠖鏄?shù)深度的遞歸算法，請(qǐng)?zhí)羁胀晟浦甶ntdepth(bitreebt) /*bt為根結(jié)點(diǎn)的指*/{inthl,hr;if(bt==NULL)return((1)_

);hl=depth(bt->lchild);hr=depth(bt->rchild);if((2)_return(hr+1);}

)(3)_ ；15．將二叉樹(shù)bt中每一個(gè)結(jié)點(diǎn)的左右子樹(shù)互換的C語(yǔ)言算法如下，其中中得空白處，完成其功能。typedefstructnode{intdata;structnode*lchild,*rchild;}btnode;voidEXCHANGE(btnode*bt){btnode*p,*q;if(bt){ADDQ(Q,bt);while(!EMPTY(Q))} }//

{p=DELQ(Q);if(p->lchild)(4)_}

;p->rchild=(2)_ ;if(p->rchild)

;(3) ;

_=q;四、應(yīng)用題1．33分別給出下圖所示二叉樹(shù)的先根、中根和后根序列。L的滿KL結(jié)點(diǎn)都有K1各層的結(jié)點(diǎn)的數(shù)目是多少？編號(hào)為n（若存在）的編號(hào)是多少？編號(hào)為ni個(gè)孩子結(jié)點(diǎn)（若存在）的編號(hào)是多少？編號(hào)為n請(qǐng)給出計(jì)算和推導(dǎo)過(guò)程。將下列由三棵樹(shù)組成的森林轉(zhuǎn)換為二叉樹(shù)（只要求給出轉(zhuǎn)換結(jié)果）ABCABCDEFGHIJKGHIJKLM N OP12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000BT6,Lchild,Rchild（l）畫(huà)出二叉樹(shù)BT的邏輯結(jié)構(gòu);畫(huà)出二叉樹(shù)的后序線索樹(shù)。設(shè)有正文AADBAACACCDACACAAD,字符集為A,B,C,D的編碼最短。五、算法設(shè)計(jì)題1．寫(xiě)一個(gè)建立二叉樹(shù)的算法。寫(xiě)一個(gè)判別給定的二叉樹(shù)是否是完全二叉樹(shù)的算法。完全二叉樹(shù)定義為：深度為K，具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)的每個(gè)結(jié)點(diǎn)都與深度為K的滿二1N(LLINK,INFO,RLINK),ROOTp和q分別為指向該二叉樹(shù)中任意兩個(gè)結(jié)點(diǎn)的指針該算法找到pq。有一二叉鏈表，試編寫(xiě)按層次順序遍歷二叉樹(shù)的算法。

ROOp,q,,已知二叉樹(shù)按照二叉鏈表方式存儲(chǔ)試寫(xiě)出復(fù)制一棵二叉樹(shù)的算法。二叉樹(shù)采用標(biāo)準(zhǔn)鏈接結(jié)構(gòu)請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，要求該算法把二叉樹(shù)的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表，表頭指針為head表指針。分析你的算法的時(shí)、空復(fù)雜度。x以它為根的子樹(shù)，并釋放相應(yīng)的空間。T，C為計(jì)數(shù)變量，初值為0BTLT，。T*p繼。在先序線索二叉樹(shù)T*pT*p習(xí)題七圖一、單項(xiàng)選擇題設(shè)有無(wú)向圖和如G’為G的生成樹(shù)，則下面不正確的說(shuō)法是（ ）A．G’為G的子圖 為G的連通分C．G’為G的極小連通子圖且V’=V D．G’是G的無(wú)環(huán)子圖任何一個(gè)帶權(quán)的無(wú)向連通圖的最小生成樹(shù)（ ）A．只有一棵 B．有一棵或多棵 一定有多棵 D．可能不存3．以下說(shuō)法正確的是（ ）A．連通分量是無(wú)向圖中的極小連通子圖。B．強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。C．在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b<a,b>。DG點(diǎn)，則該圖一定是完全圖。圖中有關(guān)路徑的定義是（ 。由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列 由不同頂點(diǎn)所形成的序C．由不同邊所形成的序列 上述定義都不是設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。A．n-1 B．n(n-1)/2 n(n+1)/2 6．要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（ ）條邊。A．n-l 7．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個(gè)有向圖中，有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ ）倍。A．1/2 8．下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（ ）有向圖 無(wú)向圖 網(wǎng) 網(wǎng)下列說(shuō)法不正確的是（ 。A．圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一B．遍歷的基本算法有兩種：深度遍歷和廣度遍歷C．圖的深度遍歷不適用于有向圖D．圖的深度遍歷是一個(gè)遞歸過(guò)程下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路：A．深度優(yōu)先遍歷 B.拓?fù)渑判?C.求最短路徑D.求關(guān)鍵路在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的Prim算法的時(shí)間復(fù)雜度( 。A.O(n) B.O(n+e) C.D.12．已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓?fù)湫蛄惺牵?。A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7GViVj（ 。A．G中有<Vi，Vj> 中有一條從Vi到Vj的路徑C．G中沒(méi)有<Vi,Vj> 中有一條從Vj到Vi的路徑關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ 。A．從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 從源點(diǎn)到匯點(diǎn)的最短路C．最長(zhǎng)回路 最短回路下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（ 。A．關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B．任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完C．所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D．某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成二、填空題具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多。設(shè)無(wú)向圖G有n個(gè)頂點(diǎn)和e條邊，每個(gè)頂點(diǎn)Vi的度為d1<=i<=，則e= 在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需條弧。下圖中的強(qiáng)連通分量的個(gè)數(shù)個(gè)。5．N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示該矩陣至少個(gè)非零元素。在有向圖的鄰接矩陣表示中計(jì)算第I個(gè)頂點(diǎn)入度的方法。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接表的表示則表頭向量大小接表的邊結(jié)點(diǎn)個(gè)數(shù)。8.已知一無(wú)向圖G（，其中V={a,b,c,d,e}現(xiàn)用某一種圖遍歷方法從頂點(diǎn)a開(kāi)始遍歷圖，得到的序列為abecd，則采用的遍歷方法。構(gòu)造連通網(wǎng)最小生成樹(shù)的兩個(gè)典型算法。有向圖G可拓?fù)渑判虻呐袆e條件。Dijkstra最短路徑算法從源點(diǎn)到其余各頂點(diǎn)的最短路徑的路徑長(zhǎng)度次序依次產(chǎn)生該算法弧上的權(quán)出情況時(shí)不能正確產(chǎn)生最短路徑。12.有向圖G=(V,E),其中<a,b,d<a,bd.E(G{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>從源點(diǎn)0到頂點(diǎn)3的最短路徑長(zhǎng)度，經(jīng)過(guò)的中間頂點(diǎn)。AOV網(wǎng)結(jié)點(diǎn)表邊表。AOE網(wǎng)中結(jié)點(diǎn)表邊表。在AOE網(wǎng)中從源點(diǎn)到匯點(diǎn)路徑上各活動(dòng)時(shí)間總和最長(zhǎng)的路徑稱。在AOV網(wǎng)中，存在環(huán)意味 的數(shù)據(jù)流圖來(lái)說(shuō)，它表明存

，這 。

的；對(duì)程序V2V1V3V5V2V1V3V5V4V6（1．列出對(duì)右圖執(zhí)行該程序后的輸出結(jié)果。（2．在程序空白處填上適當(dāng)語(yǔ)句。voidtopsort(hdnodesgraph[],intn){inti,j,k,top;node_pointerptr;top=-1;for(i=0;i<n;i++)if(!graph[i].count){graph[i].count=top;top=i;for(i=0;i<n;i++)if(1)_ {fprintf(stderr,"\ngraphhasacycleexit(1);}else{j=top;(2)_

;printf("v%d,",j);for(ptr=graph[j].link;ptr;ptr=ptr->link){k=ptr->vertex;graph[k].count--;if((3) }

){graph[k].count=top;top=k;}}}三、應(yīng)用題1．每個(gè)頂點(diǎn)的入度、出度；鄰接矩陣；鄰接表；逆鄰接表；強(qiáng)連通分量。已知圖的鄰接矩陣為：V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000當(dāng)用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)，且鄰接表都按序號(hào)從大到小排序時(shí)，試寫(xiě)出：（1．以頂點(diǎn)V1為出發(fā)點(diǎn)的唯一的深度優(yōu)先遍歷；（2．以頂點(diǎn)V1為出發(fā)點(diǎn)的唯一的廣度優(yōu)先遍歷；（3．該圖唯一的拓?fù)溆行蛐蛄?。已知一個(gè)無(wú)向圖如下圖所示，要求分別用PrimKruskal（為起點(diǎn)，試畫(huà)出構(gòu)造過(guò)程。201 11 2 5910 10

14 6 35 4 618(Pe(N(Pa)、倫敦(L)、東京(T)、墨西哥(M)世界六大城市交通里程表(單位:百公里)PENPALTMPE109828121124N109585510832PA825839792L815539589T211089795113M124329289113（1（2（3下表給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需時(shí)間（1．畫(huà)出相應(yīng)的AOE網(wǎng)（2（3工序代號(hào)ABCDEFGHIJKLMN所需時(shí)間15105081540300151206015302040先驅(qū)工作A,BBC,DBEG,IEIF,IH,J,KLG四、算法設(shè)計(jì)題n<vi,vj>(以其中之一為0n個(gè)頭結(jié)點(diǎn)（其結(jié)點(diǎn)數(shù)值域從1到。2．已知無(wú)向圖采用鄰接表存儲(chǔ)方式，試寫(xiě)出刪除邊的算法。（找到一條即可（注：圖中不存在頂點(diǎn)到自己的?。?221931065462647234n1221931065462647234對(duì)于一個(gè)使用鄰接表存儲(chǔ)的有向圖G拓?fù)渑判?。其基本思想是：在遍歷過(guò)程中，每訪問(wèn)一個(gè)頂點(diǎn)，就將其鄰接到的頂點(diǎn)的入度0（1．給出完成上述功能的圖的鄰接表定義（結(jié)構(gòu)。（2．定義在算法中使用的全局輔助數(shù)組。（3．寫(xiě)出在遍歷圖的同時(shí)進(jìn)行拓?fù)渑判虻乃惴āＡ?xí)題八查找一、單項(xiàng)選擇題順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（ ）的線性表。散列存儲(chǔ) B.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C.壓縮存儲(chǔ) D.索引存儲(chǔ)若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查一個(gè)記錄，其平均查找長(zhǎng)度ASL為( 。A．(n-1)/2 B.n/2 C.(n+1)/2 D.3．適用于折半查找的表的存儲(chǔ)方式及元素排列要求( )鏈接方式存儲(chǔ)，元素?zé)o序 B．鏈接方式存儲(chǔ)，元素有序C．順序方式存儲(chǔ)，元素?zé)o序 D．順序方式存儲(chǔ)，元素有當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)即可用折半查找也可用順序查找前者比后者的查找速( )A必定快 B不一定 C.在大部分情況下要快 D.取決于表遞增還是遞5．當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為( )A．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最小的數(shù)據(jù)組成索引塊C.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D.數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值小于其孩子的值。這種說(shuō)法（ 。正確 B.錯(cuò)誤二叉查找樹(shù)的查找效率與二叉樹(shù)有,在時(shí)其查找效率最低(1):A.高度 B.結(jié)點(diǎn)的多少 C.樹(shù)型 D.結(jié)點(diǎn)的位置(2):A.結(jié)點(diǎn)太多 B.完全二叉樹(shù) C.呈單枝樹(shù) D.結(jié)點(diǎn)太復(fù)雜。如果要求一個(gè)線性表既能較快的查找又能適應(yīng)動(dòng)態(tài)變化的要求則可采( 查法。分快查找 B.順序查找 C.折半查找 D.基于屬性9．分別以下列序列構(gòu)造二叉排序樹(shù)，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的( A（1080，90，60，121113）B（1012011138，6，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)下圖所示的4棵二叉,( 是平衡二叉樹(shù)。（A） （B） （C） 11．散列表的平均查找長(zhǎng)度（ 。與處理沖突方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)與處理沖突方法有關(guān)且與表的長(zhǎng)度有關(guān)與處理沖突方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)12.設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=keyMOD13,散列地址為1的鏈中有（ ）記錄。A．1 B.2 C.3 D.4關(guān)于雜湊查找說(shuō)法不正確的有幾( )采用鏈地址法解決沖突時(shí)，查找一個(gè)元素的時(shí)間是相同的用鏈地址法解決沖突易引起聚集現(xiàn)象再哈希法不易產(chǎn)生聚集A.1 B.2 C.3 D.4設(shè)哈希表長(zhǎng)為14，哈希函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置( )將10個(gè)元素散列到100000個(gè)單元的哈希表中，則（ ）產(chǎn)生沖突。A.一定會(huì) B.一定不會(huì) C.仍可能會(huì)二、填空題1.順序查找n個(gè)元素的順序表若查找成功則比較關(guān)鍵字的次數(shù)最多次當(dāng)用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)。2.在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù).一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一樹(shù)而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。哈希表是通過(guò)將查找碼按選定

和

換為地址進(jìn)行存儲(chǔ)的線性表。哈希方法的關(guān)鍵是_

和

。一個(gè)好的哈希函數(shù)其轉(zhuǎn)換地址應(yīng)盡可能 ，而且函數(shù)運(yùn)算應(yīng)盡可能 。平衡二叉樹(shù)又，其定義。在哈希函數(shù)H（key）=key%p中，p值最好。假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)再散列法把這k個(gè)關(guān)鍵字存入散列表中至少要進(jìn)次探測(cè)。 法構(gòu)造的哈希函數(shù)肯定不會(huì)發(fā)生沖突。動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含和 運(yùn)算后者不包含這兩種運(yùn)算。在散列存儲(chǔ)中裝填因子α的值越大α的值越小，。已知N元整型數(shù)組aN（半）查找方法統(tǒng)計(jì)成績(jī)大于或等于X#defineN/*學(xué)生人數(shù)*/intuprx(inta[N],intx) X*/{inthead=1,mid,rear=N;do{mid=(head+rear)/2;if(x<=a[mid]) (1) else (2)_ _;}while( (3)_ if(a[head]<x)returnhead-1;returnhead;}三、應(yīng)用題1．HASH方法的平均查找路長(zhǎng)決定于什么？是否與結(jié)點(diǎn)個(gè)數(shù)N有關(guān)？處理沖突的方法主要有哪些？2.設(shè)有一組關(guān)鍵字{9,01,23,14,55,20,84,27}，采用哈希函數(shù)：H（key）=keymod7，Hi=(H(key)+di)mod10(di=12,22,32,…,)解決沖突。要求：對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長(zhǎng)度。選取哈希函數(shù)Ｈ（key）=keymod查找的平均查找長(zhǎng)度。4.輸入一個(gè)正整數(shù)序列53,17,12,66,58,70,87,25,56,6，試完成下列各題。按次序構(gòu)造一棵二叉排序樹(shù)BS。依此二叉排序樹(shù)，如何得到一個(gè)從大到小的有序序列？直接在二叉排序樹(shù)中查找關(guān)鍵字K與在中序遍歷輸出的有序序列中查找關(guān)鍵字如何？為什么？1-9，請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。7.假定對(duì)有序表：(3,4,5,7,24,30,42,54,63,72,87,95)進(jìn)行折半查找，試回答下列問(wèn)題：(1).畫(huà)出描述折半查找過(guò)程的判定樹(shù)；(2).若查找元素54，需依次與那些元素比較?(3).若查找元素90，需依次與那些元素比較?(4).假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。四、算法設(shè)計(jì)題設(shè)記錄R1,R2,…,Rn按關(guān)鍵字值從小到大順序存儲(chǔ)在數(shù)組r[1..n]中,在r[n+1一個(gè)監(jiān)督哨,其關(guān)鍵字值為+∞;試寫(xiě)一查找給定關(guān)鍵字k的算法;并畫(huà)出此查找過(guò)程的判定樹(shù),求出在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。試編寫(xiě)算法求出指定結(jié)點(diǎn)在給定的二叉排序樹(shù)中所在的層數(shù)。pf習(xí)題九排序一、單項(xiàng)選擇題1．快速排序 直接插入排序C.二路歸并排序 D.簡(jiǎn)單選擇排序E.起泡排序 F.堆排序其比較次數(shù)與序列初態(tài)無(wú)關(guān)的算法是（ ）不穩(wěn)定的排序算法是（ ）在初始序列已基本有（除去n個(gè)元素中的某k個(gè)元素后即呈有序的情況下排序效率最高的算法是（ ）排序的平均時(shí)間復(fù)雜度為O(n?logn)的算法是（ ）為O(n?n)的算法是（ 2．比較次數(shù)與排序的初始狀態(tài)無(wú)關(guān)的排序方法( 。A．直接插入排序 起泡排序 快速排序 簡(jiǎn)單選擇排序排序，數(shù)據(jù)的排列次序在排序的過(guò)程中的變化（1）8447251521（2）1547258421（3）1521258447（4）1521254784則采用的排序是A.選擇( B.冒泡C.快速D.插入下列排序算法( 排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。選擇 B.冒泡 C.歸并 D.堆5．一組記錄的關(guān)鍵碼為4，7，5，3，4，8，則利用快速排序的方法，以第一記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ 。A．(38,40,46,56,79,84) B.(40,38,46,79,56,84)C．(40,38,46,56,79,84) D.(40,38,46,84,56,79)下列排序算法中，在待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的( 排序。冒泡B.希爾C.快速D.就平均性能而言，目前最好的內(nèi)排序方法( 排序法。冒泡 B.希爾插入 C.交換 D.快速下列排序算法中，占用輔助空間最多的是)歸并排序 B.快速排序 C.希爾排序 D.堆排序若用冒泡排序方法對(duì)序{10,14,26,29,41,52}從大到小排序需進(jìn)行（ 次比較A.3 B.10 C.15 D.25快速排序方法在（ ）情況下最不利于發(fā)揮其長(zhǎng)處。要排序的數(shù)據(jù)量太大 B.要排序的數(shù)據(jù)中含有多個(gè)相同值C.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) D.要排序的數(shù)據(jù)已基本有11．下列四個(gè)序列中，哪一個(gè)是堆（ 。A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10 D.75,45,65,10,25,30,20,1512.有一組數(shù)（1597820-7用堆排序的篩選方法建立的初始堆為（ A．-1，4，8，9，20，7，15，7 C．-1，4，7，8，20，15，7，9 二、填空題若待排序的序列中存在多個(gè)記錄具有相同的鍵值，經(jīng)過(guò)排序，這些記錄的相對(duì)次序仍保持不變，則稱這種排序方法的，否則稱的。按照排序過(guò)程涉及的存儲(chǔ)設(shè)備的不同，排序可分排序排序。直接插入排序用監(jiān)視哨的作用。對(duì)n個(gè)記錄的表r[1..n]進(jìn)行簡(jiǎn)單選擇排序所需進(jìn)行的關(guān)鍵字間的比較次數(shù)。下