西南石油數(shù)據(jù)結(jié)構(gòu)習題集答案

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

而_ 無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它_ 不變，都不影響其外部使用8．數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是一個算法具有5個特: 、 、 ，有零或多個輸入、有一個或多個輸出。常見時間復(fù)雜性的量級有：常數(shù)階O( 、對數(shù)階O( 、線性O(shè)( 、平方階O( 、和指數(shù)階O( 。通常認為，具指數(shù)階量級的算法，而量級低于平方階的算法的。計算機執(zhí)行下面的語句時，語句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ù)的程序段，請將未完成的部分填入，使之完整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;”的時間復(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)}這里的圓括號對表示兩結(jié)點是雙向的。1004寫出這些結(jié)構(gòu)？調(diào)用下列函數(shù)f(n)試指出f(n)值的大小，并寫出f(n)假定n=5，試指出f(5)值的大小和執(zhí)行f(5)時的輸出結(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è)計求解下列問題的類C在數(shù)組A[1..n]中查找值為K的元素,若找到則輸出其位置i(1<=i<=n)0找出數(shù)組A[1..n（準操作。習題二線性表一、單項選擇題1．順序表是線性表的（ A．鏈式存儲結(jié)構(gòu) B．順序存儲結(jié)構(gòu) C．索引存儲結(jié)構(gòu) D．散列存儲結(jié)構(gòu)對于順序表，以下說法錯誤的是（ ）A．順序表是用一維數(shù)組實現(xiàn)的線性表，數(shù)組的下標可以看成是元素的絕對地B．順序表的所有存儲結(jié)點按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列C．順序表的特點邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰D．順序表的特點邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中線性表是具有n個（ ）的有限序列n>。A．表元素 字符 數(shù)據(jù)元素 數(shù)據(jù)項 信息4.以下說法錯誤的是()LocateElemO（n）讀表元運算在順序表上只需常數(shù)時間結(jié)構(gòu)在鏈表上實現(xiàn)讀表元運算的平均時間復(fù)雜度為O（1）D．插入、刪除操作在鏈表上的實現(xiàn)可在O（1）時間內(nèi)完成E．插入、刪除操作在順序表上的實現(xiàn)，平均時間復(fù)雜度為若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ 存儲方式最節(jié)省時間。A．順序表 單鏈表 雙鏈表 單循環(huán)鏈表6．設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選( 最節(jié)省時間A.單鏈表 B.單循環(huán)鏈表 C.帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點的雙循環(huán)鏈表靜態(tài)鏈表中指針表示的是（ ）.內(nèi)存地址 數(shù)組下標 下一元素地址 左、右孩子地址鏈表不具有的特點是（ ）A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正在循環(huán)鏈表中，將頭指針改設(shè)為尾指針rea）后，其頭結(jié)點和尾結(jié)點的存儲位置分是（ ）rear和rear->next->nextB．rear->next和rearC．rear->next->next和rearD．rearrear->next 對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為（ 。A．O(n)O(n) B.O(n)O(1) C.O(1)O(n) D.O(1)線性（以鏈接方式存儲時訪問第i位置元素的時間復(fù)雜性（ A．O（i） 在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是（ 。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;對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是（ ）head==NULL B．head→next==NULLC．head→next==head 二、判斷題（）1.鏈表中的頭結(jié)點僅起到標識的作用( )2．線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的( 3．順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好( )所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表( )線性表的特點是每個元素都有一個前驅(qū)和一個后繼( )循環(huán)鏈表不是線性.( )線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)( )線性表就是順序存儲的表( )鏈表是采用鏈式存儲結(jié)構(gòu)的線性,進行插入、刪除操作時，在鏈表中比在順序存儲構(gòu)中效率高。( )三、填空題在順序表中，邏輯上相鄰的元素，其物理位置 相鄰。在單鏈表中，邏輯上鄰的元素，其物理位置 相鄰。在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由 指示，首元素結(jié)點的存儲位置由 指示除首元素結(jié)點外其它任一元素結(jié)點的存儲位由 指示。在單鏈表中若在每個結(jié)點中增加一個指針,所含指針指向前驅(qū)結(jié)點，這樣構(gòu)成的鏈中有兩個方向不同的鏈，稱。對于順序表的插入算法insert_sqlist來說，若以結(jié)點移動為標準操作，則插入算法在最壞情況下的移動次數(shù)，時間復(fù)雜度。在平均情況下的移動次數(shù)，時間復(fù)雜度。線性表的常見鏈式存儲結(jié)構(gòu)、 和 。單鏈表表示法的基本思想是表示結(jié)點間的邏輯關(guān)系。線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除個元素平均需要移動元素的個數(shù)。設(shè)單鏈表的結(jié)點結(jié)構(gòu)(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點指針py指向data為y的新結(jié)點,若將結(jié)點y插入結(jié)點x之后則需要執(zhí)以下語: ； ;對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 個，單鏈表為 個。以下為順序表的定位運算，分析算法，請?zhí)幪钌险_的語句intlocate_sqlist(sqlistL,datatypeX)/*在順序表L中查找第一值等于X的結(jié)點。若找到回傳該結(jié)點序號；否則回傳0*/{ ;if( )return(i);else return(0);}對單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，完成其功能。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;下面是一個求兩個集合A和B之差C=A-B的程序，即當且僅當e是AB才是C為空；操作完成后A，B中元素按遞增排列。下面append(last,eelastdifference(A,B)實現(xiàn)集合運算C的鏈表的首結(jié)點的地址。在執(zhí)行A-B頭結(jié)點，以便新結(jié)點的添加，當A-B運算執(zhí)行完畢，再刪除并釋放表示結(jié)果集合的鏈表的表頭結(jié)點。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é)點之前，其數(shù)據(jù)域一般無意義（也就是第一元素結(jié)點，它是頭結(jié)點后邊的第一個結(jié)點。參考答案：在單鏈表中不能從當前結(jié)點（若當前結(jié)點不是第一結(jié)點）出發(fā)訪問到任何一個從當前結(jié)點向前到第一結(jié)點，向后到最后結(jié)點，可以訪問到任何一個結(jié)點。（1）說明該算法的功能（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é)點的數(shù)據(jù)域按值自小到大排序，成為非遞減（可能包括數(shù)據(jù)域值相等的結(jié)點）有序雙向循環(huán)鏈表。2）(1)r->prior=q->prior;∥將q(2)p->next->prior=q）將q結(jié)點插入(3)p->next=q;(4)r=r->next;或r=q->next;∥后移指針，再將新結(jié)點插入到適當位置。五、算法設(shè)計題A[1..sizenum各分量中，且遞增有序。請設(shè)計一個算法，將x所設(shè)計算法的時間復(fù)雜度。附加空間)逆置的算法，在原表的存儲空間內(nèi)將線性表(aa.,a)逆置為1 2 n(a.,a,an 2 1試編寫在無頭結(jié)點的單鏈表上實現(xiàn)線性表基本運算LOCATE(L,X)、INSERT(L,X，iDELETE(L,i)的算法，并和在帶頭結(jié)點的單鏈表上實現(xiàn)相的算法進行比較。4．將線性表A=(a1,a2,……am),B=(b1,b2,……bn)合并成線性表C,C=(a1,b1,……am,bm,bm+1,…….bn) 當m<=n時或C=(a1,b1,……an,bn,an+1,……am)當m>n時線性表C以單鏈表作為存儲結(jié)構(gòu)且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。nA0(n)、空間復(fù)雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素空間為常量。假設(shè)在長度大于1s*s約瑟夫環(huán)問題1,2,…,nnm,從第一個人開始順時針自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m1報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個各人的編號。例如m的初值為20n=77個人的密碼依次是：3,1,7,2,4,8,46,1,4,7,2,3,5。習題三棧和隊列一單項選擇題在作進棧運算時,應(yīng)先判別棧是否(① ),在作退棧運算時應(yīng)先判別棧是否(②)。當棧中元素為n個,作進棧運算時發(fā)生上溢,則說明該棧的最大容量為(③)。①,②:A.空B.滿 C.上溢D.下溢③:A.n-1B.n C.n+1D.n/2若已知一個棧的進棧序列是其輸出序列為若p1＝3，則p2( 。A可能是2 B一定是2 C可能是1 D一定是1有六個元素的順序進棧問下列哪一個不是合法的出棧序列A.543612 B.453126 C.346521 D.234156設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是 （ ）A.2 B.3 C.5 D.6若棧采用順序存儲方式存儲現(xiàn)兩棧共享空間代表第i個(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í)行完下列語句段后值為：（ ）int f(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2 B.4 C.8 D.表達式3*2^(4+2*2-6*3)-5求值過程中當掃描到6時，對象棧和算符棧為（ ，中^為乘冪。A.3,2,4,1,1；(*^(+*- B.C.3,2,4,2,2；(*^(- D.用鏈接方式存儲的隊列，在進行刪除運算時（ 。僅修改頭指針 B.僅修改尾指針C.頭、尾指針都要修改 D.頭、尾指針可能都要修改遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)A．隊列 多維數(shù)組 棧 D.線性表設(shè)C語言數(shù)組Data[m+1]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針則執(zhí)行出隊操作的語句為 （ front=front+1 B.mC.rear=(rear+1)%(m+1) D.front=(front+1)%(m+1)循環(huán)隊列的隊滿條件為()(sq.rear+1)%maxsize==(sq.front+1)%maxsize;(sq.front+1)%maxsize==sq.rear(sq.rear+1)%maxsize==sq.frontD.sq.rear==sq.front棧和隊列的共同點是（ 。都是先進先出 B.都是先進后出C.只允許在端點處插入和刪除元素 D.沒有共同點二、填空題棧的線性表，其運算遵的原則。一個棧的輸入序列是則不可能的棧輸出序列。用S表示入棧操作表示出棧操作，若元素入棧的順序為1234，為了得到1342出順序，相應(yīng)的S和X的操作串。循環(huán)隊列的引入，目的是為了克。隊列是限制插入只能在表的一端而刪除在表的另一端進行的線性表其特點。已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列7．表達式求值應(yīng)用的一個典型例子。循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別是front和rear，當前隊列的元素個數(shù)。以下運算實現(xiàn)在鏈棧上的初始化，請?zhí)幱谜堖m當句子予以填充VoidInitStacl(LstackTp*ls){ ;}`VoidPush（LStackTp*ls,DataType{LstackTp*p;p=malloc(sizeof(LstackTp)); p->next=ls; ;}以下運算實現(xiàn)在鏈棧上的退棧，請?zhí)幱谜堖m當句子予以填充IntPop(LstackTp*ls,DataType*x){LstackTp*p;if(ls!=NULL){p=ls;*x= ls=ls->next; return(1)；}elsereturn(0);}以下運算實現(xiàn)在鏈隊上的入隊列，請?zhí)幱眠m當句子予以填充VoidEnQueue(QueptrTp*lq,DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp)); p->next=NULL;(lq->rear)->next= ; ;}三、應(yīng)用題1．畫出對算術(shù)表達式A-B*C/D-E↑F將兩個棧存入數(shù)組V[1..m]應(yīng)如何安排最好？這時棧空、棧滿的條件是什么？四、算法設(shè)計題設(shè)表達式以字符形式已存入數(shù)組E[n中括號（’和‘）是否配對的CEXYX(E);假設(shè)以I和OI和O下面所示的序列中哪些是合法的？A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO通過對true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中。設(shè)有兩個棧S,S[O..maxsize-1],為了盡量利1 2S,S1 2和出棧的操作算法。請利用兩個棧S1S2xSTSTenqueue刪除一個元素出隊列；queue_empty（請寫明算法的思想及必要的注釋）要求循環(huán)隊列不損失一個空間全部都能得到利用，設(shè)置一個標志tag,以tag0來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此相應(yīng)的入隊與出隊算法。已知Q是一個空棧。僅用隊列和棧的ADT寫一個算法，將隊列QADTmakeEmpty(s:stack); 置空棧push(s:stack;value:datatype); 新元素value進棧pop(s:stack):datatype; 出棧，返回棧頂isEmpty(s:stack):Boolean; 隊列的ADTenqueue(q:queue:value:datatype);deQueue(q:queue):datatype;isEmpty(q:queue):boolean;

元素value進隊出隊列，返回隊頭值判隊列空否習題四串一、單項選擇題1．下面關(guān)于串的的敘述中，哪一個是不正確的？（ A．串是字符的有限序列 空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存串是一種特殊的線性表，其特殊性體現(xiàn)在（ 。A．可以順序存儲B．數(shù)據(jù)元素是一個字符C．可以鏈接存儲D．數(shù)據(jù)元素可以是多個字符3．串的長度是指（）A．串中所含不同字母的個數(shù) 串中所含字符的個數(shù)C．串中所含不同字符的個數(shù) 串中所含非空格字符的個設(shè)有兩個串p和其中q是p的子串求q在p中首次出現(xiàn)的位置的算法稱（ A．求子串 聯(lián)接 C．匹配 求串長若串S=“software”,其子串的個數(shù)是（ ）A．8 二、填空題含零個字符的串稱串。任何串中所的個數(shù)稱為該串的長度?？崭翊牵溟L度等。當且僅當兩個串相等并且各個對應(yīng)位置上的字符時，這兩個串相等一個串中任意個連續(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) )}下列算法實現(xiàn)求采用順序結(jié)構(gòu)存儲的串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）的簡寫,A=""的""含有兩個空格)。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è)計題在順序串上實現(xiàn)串的判等運算EQUAL(S,T)。在鏈串上實現(xiàn)判等運算EQUAL(S,T)。若S和T是用結(jié)點大小為1的單鏈表存儲的兩個串ST為頭指針ST以順序存儲結(jié)構(gòu)表示串，設(shè)計算法。求串S中出現(xiàn)的第一個最長重復(fù)子串及其位置并分析算法的時間復(fù)雜度（如果字符串的一個子串（其長度大于1）的各個字符均相同，稱之為等值子串。如果輸入字符串S，以“”作為結(jié)束標志。串S中不存在等值子串，則輸出信息“無等值子串”，否則求出（輸出）一個長度最大的等值子串。例如：若 S=“abc123abc123!，則輸出“無等值子串”；若S=“abceebccadddddaaadd!，則輸出dddd）寫一個遞歸算法來實現(xiàn)字符串逆序存儲，要求不另設(shè)串存儲空間。習題五數(shù)組和廣義表一、單項選擇題1．常對數(shù)組進行的兩種基本操作是（ A.建立與刪除 B.索引與修改 C.查找與修改 D.查找與索引2．對于C語言的二維數(shù)組DataTypeA[m][n],每個數(shù)據(jù)元素占K個存儲單元，二維數(shù)組任意元素a[i,j]的存儲位置可(式確.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稀疏矩陣的壓縮存儲方法是只存儲 ()非零元素 B.三元祖（i,j,aij） C.aij D.i,j數(shù)組A[0..5,0..6]的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為的內(nèi)存單元中，則元素的地址( 。A.1175 B.1180 C.1205 D.1210是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)中，則對任一上三角元素a[i][j]對應(yīng)T[k]的下標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沿鏈移動的操作為()。A.j=r[j].nextB.j=j+1C.j=j->nextD.j=r[j]->next對稀疏矩陣進行壓縮存儲目的是（ 。A．便于進行矩陣運算 便于輸入和輸C．節(jié)省存儲空間 降低運算的時間復(fù)雜度已知廣義表LS＝((a,b,c),(d,e,f)),運用head和tail函數(shù)取出LS中原子e的運算( 。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的長度和深度分別為（ 。A.1和1 B.1和3 C.1和2 D.2和3下面說法不正確的( 。廣義表的表頭總是一個廣義表 B.廣義表的表尾總是一個廣義表C.廣義表難以用順序存儲結(jié)構(gòu) D.廣義表可以是一個多層次的結(jié)構(gòu)二、填空題通常采存儲結(jié)構(gòu)來存放數(shù)組對二維數(shù)組可有兩種存儲方法一種是以 為主序的存儲方式，另一種是為主序的存儲方式。用一維數(shù)組B與列優(yōu)先存放帶狀矩陣A中的非零元素A[i,j]中的第8個元素是A中的_ 行，_ 列的元素。設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組中，若按行為主序儲，則A[i,j]對應(yīng)的B中存儲位置。所謂稀疏矩陣指的_ 。廣義表簡稱表，是由零個或多個原子或子表組成的有限序列，原子與表的差別僅在于。為了區(qū)分原子和表，一般用

表示表，用 表示原子。一個表的長度是指

，而表的深度是 設(shè)廣義表L=((),()),則head(L)是 是 ；L的長度是 ；深度是 ?；谌M的稀疏矩陣轉(zhuǎn)置的處理方法有兩種以下運算按照矩陣A的列序來進行轉(zhuǎn)置請在 處用適當?shù)木渥佑靡蕴畛洹rans_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]以行為主序存儲，設(shè)第一個元素的首地址是784，試求元素A[4,2,3]的存儲首地址。特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機存取的功能？為什么？數(shù)組，廣義表與線性表之間有什么樣的關(guān)系？(a)n*nB(1:3n-2)中，使ijB[k]=a，求：ij用i,j表示k用k表示i,j((((a),b)),(((),d),(e,f)))求下列廣義表運算的結(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運算，把原子d(((((a),b),d),e)；L＝a,(b,((d)),e。四、算法設(shè)計題給定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è)計一算法判定X的值是否在A中,要求時間復(fù)雜度為O(m+n)。設(shè)二維數(shù)組a[1..m,1..n]含有m*n個整數(shù)。寫出算法：判斷a(yes/no)；試分析算法的時間復(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習題六樹和二叉樹一、單項選擇題以下說法錯誤的是( )A．樹形結(jié)構(gòu)的特點是一個結(jié)點可以有多個直接前B．線性結(jié)構(gòu)中的一個結(jié)點至多只有一個直接后繼C．樹形結(jié)構(gòu)可以表(組)更復(fù)雜的數(shù)據(jù)D．樹(及一切樹形結(jié)構(gòu))是一種"分支層次"結(jié)構(gòu)E．任何只含一個結(jié)點的集合是一棵樹下列說法中正確的是( )A．任何一棵二叉樹中至少有一個結(jié)點的度為任何一棵二叉樹中每個結(jié)點的度都為2任何一棵二叉樹中的度肯定等于2任何一棵二叉樹中的度可以小于23．討論樹、森林和二叉樹的關(guān)系，目的是為了（ A．B．將樹、森林按二叉樹的存儲方式進行存儲C．將樹、森林轉(zhuǎn)換成二叉樹D．體現(xiàn)一種技巧，沒有什么實際意義樹最適合用來表示( )有序數(shù)據(jù)元素 無序數(shù)據(jù)元素C．元素之間具有分支層次關(guān)系的數(shù)據(jù) 元素之間無聯(lián)系的數(shù)據(jù)10210（）A．9 設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別和M3。與森F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（ 。A．M1 B．M1+M2 一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）A．250 500 C．254 D．505 以上答案都不設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)( )A．不確定 二叉樹的第I層上最多含有結(jié)點數(shù)為（ ）2I

2I-1-1

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

_；編號是i的結(jié)點所在的層次號是_

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

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

{if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL)) countleaf(t->lchild,&count);}}類型的定義如下：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) */}

;棧頂元素出棧二叉樹存儲結(jié)構(gòu)同上題，以下程序為求二叉樹深度的遞歸算法，請?zhí)羁胀晟浦甶ntdepth(bitreebt) /*bt為根結(jié)點的指*/{inthl,hr;if(bt==NULL)return((1)_

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

)(3)_ ；15．將二叉樹bt中每一個結(jié)點的左右子樹互換的C語言算法如下，其中中得空白處，完成其功能。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分別給出下圖所示二叉樹的先根、中根和后根序列。L的滿KL結(jié)點都有K1各層的結(jié)點的數(shù)目是多少？編號為n（若存在）的編號是多少？編號為ni個孩子結(jié)點（若存在）的編號是多少？編號為n請給出計算和推導(dǎo)過程。將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹（只要求給出轉(zhuǎn)換結(jié)果）ABCABCDEFGHIJKGHIJKLM N OP12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000BT6,Lchild,Rchild（l）畫出二叉樹BT的邏輯結(jié)構(gòu);畫出二叉樹的后序線索樹。設(shè)有正文AADBAACACCDACACAAD,字符集為A,B,C,D的編碼最短。五、算法設(shè)計題1．寫一個建立二叉樹的算法。寫一個判別給定的二叉樹是否是完全二叉樹的算法。完全二叉樹定義為：深度為K，具有N個結(jié)點的二叉樹的每個結(jié)點都與深度為K的滿二1N(LLINK,INFO,RLINK),ROOTp和q分別為指向該二叉樹中任意兩個結(jié)點的指針該算法找到pq。有一二叉鏈表，試編寫按層次順序遍歷二叉樹的算法。

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

，這 。

的；對程序V2V1V3V5V2V1V3V5V4V6（1．列出對右圖執(zhí)行該程序后的輸出結(jié)果。（2．在程序空白處填上適當語句。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．每個頂點的入度、出度；鄰接矩陣；鄰接表；逆鄰接表；強連通分量。已知圖的鄰接矩陣為：V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000當用鄰接表作為圖的存儲結(jié)構(gòu)，且鄰接表都按序號從大到小排序時，試寫出：（1．以頂點V1為出發(fā)點的唯一的深度優(yōu)先遍歷；（2．以頂點V1為出發(fā)點的唯一的廣度優(yōu)先遍歷；（3．該圖唯一的拓撲有序序列。已知一個無向圖如下圖所示，要求分別用PrimKruskal（為起點，試畫出構(gòu)造過程。201 11 2 5910 10

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

和

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

和

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