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

而_ 無關，即不論其內部結構如何變化，只要它_ 不變，都不影響其外部使用8．數據結構中評價算法的兩個重要指標是一個算法具有5個特: 、 、 ，有零或多個輸入、有一個或多個輸出。常見時間復雜性的量級有：常數階O( 、對數階O( 、線性O( 、平方階O( 、和指數階O( 。通常認為，具指數階量級的算法，而量級低于平方階的算法的。計算機執行下面的語句時，語句s的執行次數為 for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;m.nn的數目。例f(5,3)=553+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。以下是該函數的程序段，請將未完成的部分填入，使之完整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) );}執行程序，f(6,4)= 。程序段“i=1;while(i<=n)i=i*2;”的時間復雜度T(n)= 四、應用題們分別屬于何種結構。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)}這里的圓括號對表示兩結點是雙向的。1004寫出這些結構？調用下列函數f(n)試指出f(n)值的大小，并寫出f(n)假定n=5，試指出f(5)值的大小和執行f(5)時的輸出結果。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);}設計求解下列問題的類C在數組A[1..n]中查找值為K的元素,若找到則輸出其位置i(1<=i<=n)0找出數組A[1..n（準操作。習題二線性表一、單項選擇題1．順序表是線性表的（ A．鏈式存儲結構 B．順序存儲結構 C．索引存儲結構 D．散列存儲結構對于順序表，以下說法錯誤的是（ ）A．順序表是用一維數組實現的線性表，數組的下標可以看成是元素的絕對地B．順序表的所有存儲結點按相應數據元素間的邏輯關系決定的次序依次排列C．順序表的特點邏輯結構中相鄰的結點在存儲結構中仍相鄰D．順序表的特點邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中線性表是具有n個（ ）的有限序列n>。A．表元素 字符 數據元素 數據項 信息4.以下說法錯誤的是()LocateElemO（n）讀表元運算在順序表上只需常數時間結構在鏈表上實現讀表元運算的平均時間復雜度為O（1）D．插入、刪除操作在鏈表上的實現可在O（1）時間內完成E．插入、刪除操作在順序表上的實現，平均時間復雜度為若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ 存儲方式最節省時間。A．順序表 單鏈表 雙鏈表 單循環鏈表6．設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選( 最節省時間A.單鏈表 B.單循環鏈表 C.帶尾指針的單循環鏈表 D.帶頭結點的雙循環鏈表靜態鏈表中指針表示的是（ ）.內存地址 數組下標 下一元素地址 左、右孩子地址鏈表不具有的特點是（ ）A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正在循環鏈表中，將頭指針改設為尾指針rea）后，其頭結點和尾結點的存儲位置分是（ ）rear和rear->next->nextB．rear->next和rearC．rear->next->next和rearD．rearrear->next 對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為（ 。A．O(n)O(n) B.O(n)O(1) C.O(1)O(n) D.O(1)線性（以鏈接方式存儲時訪問第i位置元素的時間復雜性（ A．O（i） 在單鏈表指針為p的結點之后插入指針為s的結點，正確的操作是（ 。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的帶頭結點的單鏈表，判定該表為空表的條件是（ ）head==NULL B．head→next==NULLC．head→next==head 二、判斷題（）1.鏈表中的頭結點僅起到標識的作用( )2．線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續的( 3．順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好( )所謂靜態鏈表就是一直不發生變化的鏈表( )線性表的特點是每個元素都有一個前驅和一個后繼( )循環鏈表不是線性.( )線性表只能用順序存儲結構實現( )線性表就是順序存儲的表( )鏈表是采用鏈式存儲結構的線性,進行插入、刪除操作時，在鏈表中比在順序存儲構中效率高。( )三、填空題在順序表中，邏輯上相鄰的元素，其物理位置 相鄰。在單鏈表中，邏輯上鄰的元素，其物理位置 相鄰。在帶頭結點的非空單鏈表中，頭結點的存儲位置由 指示，首元素結點的存儲位置由 指示除首元素結點外其它任一元素結點的存儲位由 指示。在單鏈表中若在每個結點中增加一個指針,所含指針指向前驅結點，這樣構成的鏈中有兩個方向不同的鏈，稱。對于順序表的插入算法insert_sqlist來說，若以結點移動為標準操作，則插入算法在最壞情況下的移動次數，時間復雜度。在平均情況下的移動次數，時間復雜度。線性表的常見鏈式存儲結構、 和 。單鏈表表示法的基本思想是表示結點間的邏輯關系。線性表L=（a1,a2,…,an）用數組表示，假定刪除表中任一元素的概率相同，則刪除個元素平均需要移動元素的個數。設單鏈表的結點結構(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結點指針py指向data為y的新結點,若將結點y插入結點x之后則需要執以下語: ； ;對于雙向鏈表,在兩個結點之間插入一個新結點需修改的指針共 個，單鏈表為 個。以下為順序表的定位運算，分析算法，請處填上正確的語句intlocate_sqlist(sqlistL,datatypeX)/*在順序表L中查找第一值等于X的結點。若找到回傳該結點序號；否則回傳0*/{ ;if( )return(i);else return(0);}對單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結點指針。請填充算法中標出的空白處，完成其功能。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)實現集合運算C的鏈表的首結點的地址。在執行A-B頭結點，以便新結點的添加，當A-B運算執行完畢，再刪除并釋放表示結果集合的鏈表的表頭結點。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);*/四、應用題是為了操作的統一、方便而設立的，放在第一元素結點之前，其數據域一般無意義（也就是第一元素結點，它是頭結點后邊的第一個結點。參考答案：在單鏈表中不能從當前結點（若當前結點不是第一結點）出發訪問到任何一個從當前結點向前到第一結點，向后到最后結點，可以訪問到任何一個結點。（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）本算法功能是將雙向循環鏈表結點的數據域按值自小到大排序，成為非遞減（可能包括數據域值相等的結點）有序雙向循環鏈表。2）(1)r->prior=q->prior;∥將q(2)p->next->prior=q）將q結點插入(3)p->next=q;(4)r=r->next;或r=q->next;∥后移指針，再將新結點插入到適當位置。五、算法設計題A[1..sizenum各分量中，且遞增有序。請設計一個算法，將x所設計算法的時間復雜度。附加空間)逆置的算法，在原表的存儲空間內將線性表(aa.,a)逆置為1 2 n(a.,a,an 2 1試編寫在無頭結點的單鏈表上實現線性表基本運算LOCATE(L,X)、INSERT(L,X，iDELETE(L,i)的算法，并和在帶頭結點的單鏈表上實現相的算法進行比較。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以單鏈表作為存儲結構且C表利用A表和B表中的結點空間構成。注意：單鏈表的長度值m和n均未顯式存儲。nA0(n)、空間復雜度為0(1)的算法，該算法刪除線性表中所有值為item的數據元素空間為常量。假設在長度大于1s*s約瑟夫環問題1,2,…,nnm,從第一個人開始順時針自1開始順序報數，報到m時停止報數。報m的人出列，將他的密碼作為新的m1報數，如此下去，直至所有的人全部出列為止。試設計一個各人的編號。例如m的初值為20n=77個人的密碼依次是：3,1,7,2,4,8,46,1,4,7,2,3,5。習題三棧和隊列一單項選擇題在作進棧運算時,應先判別棧是否(① ),在作退棧運算時應先判別棧是否(②)。當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為(③)。①,②: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設有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應該是 （ ）A.2 B.3 C.5 D.6若棧采用順序存儲方式存儲現兩棧共享空間代表第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]執行完下列語句段后值為：（ ）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.頭、尾指針可能都要修改遞歸過程或函數調用時，處理參數及返回地址，要用一種稱為（ ）的數據結構A．隊列 多維數組 棧 D.線性表設C語言數組Data[m+1]作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針則執行出隊操作的語句為 （ front=front+1 B.mC.rear=(rear+1)%(m+1) D.front=(front+1)%(m+1)循環隊列的隊滿條件為()(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出順序，相應的S和X的操作串。循環隊列的引入，目的是為了克。隊列是限制插入只能在表的一端而刪除在表的另一端進行的線性表其特點。已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列7．表達式求值應用的一個典型例子。循環隊列用數組A[0..m-1]存放其元素值，已知其頭尾指針分別是front和rear，當前隊列的元素個數。以下運算實現在鏈棧上的初始化，請處用請適當句子予以填充VoidInitStacl(LstackTp*ls){ ;}`VoidPush（LStackTp*ls,DataType{LstackTp*p;p=malloc(sizeof(LstackTp)); p->next=ls; ;}以下運算實現在鏈棧上的退棧，請處用請適當句子予以填充IntPop(LstackTp*ls,DataType*x){LstackTp*p;if(ls!=NULL){p=ls;*x= ls=ls->next; return(1)；}elsereturn(0);}以下運算實現在鏈隊上的入隊列，請處用適當句子予以填充VoidEnQueue(QueptrTp*lq,DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp)); p->next=NULL;(lq->rear)->next= ; ;}三、應用題1．畫出對算術表達式A-B*C/D-E↑F將兩個棧存入數組V[1..m]應如何安排最好？這時棧空、棧滿的條件是什么？四、算法設計題設表達式以字符形式已存入數組E[n中括號（’和‘）是否配對的CEXYX(E);假設以I和OI和O下面所示的序列中哪些是合法的？A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO通過對true，否則返回false（假定被判定的操作序列已存入一維數組中。設有兩個棧S,S[O..maxsize-1],為了盡量利1 2S,S1 2和出棧的操作算法。請利用兩個棧S1S2xSTSTenqueue刪除一個元素出隊列；queue_empty（請寫明算法的思想及必要的注釋）要求循環隊列不損失一個空間全部都能得到利用，設置一個標志tag,以tag0來區分頭尾指針相同時的隊列狀態的空與滿，請編寫與此相應的入隊與出隊算法。已知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．下面關于串的的敘述中，哪一個是不正確的？（ A．串是字符的有限序列 空串是由空格構成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存串是一種特殊的線性表，其特殊性體現在（ 。A．可以順序存儲B．數據元素是一個字符C．可以鏈接存儲D．數據元素可以是多個字符3．串的長度是指（）A．串中所含不同字母的個數 串中所含字符的個數C．串中所含不同字符的個數 串中所含非空格字符的個設有兩個串p和其中q是p的子串求q在p中首次出現的位置的算法稱（ A．求子串 聯接 C．匹配 求串長若串S=“software”,其子串的個數是（ ）A．8 二、填空題含零個字符的串稱串。任何串中所的個數稱為該串的長度。空格串是，其長度等。當且僅當兩個串相等并且各個對應位置上的字符時，這兩個串相等一個串中任意個連續字符組成的序列稱為該串串，該串稱為它所有子串串。INDE‘DATASTRUCTUR‘STR）= 。模式串P=‘abaabcac’的next函數值序列。下列程序判斷字符串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) )}下列算法實現求采用順序結構存儲的串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)}}三、應用題1．設有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)設主串S‘xxyxxxyxxxxyxyT‘xxyxTS給出字符串‘abacabaaad’在KMPnextnextvals＝（xy）＋＊t＝＋）s轉化為t。四、算法設計題在順序串上實現串的判等運算EQUAL(S,T)。在鏈串上實現判等運算EQUAL(S,T)。若S和T是用結點大小為1的單鏈表存儲的兩個串ST為頭指針ST以順序存儲結構表示串，設計算法。求串S中出現的第一個最長重復子串及其位置并分析算法的時間復雜度（如果字符串的一個子串（其長度大于1）的各個字符均相同，稱之為等值子串。如果輸入字符串S，以“”作為結束標志。串S中不存在等值子串，則輸出信息“無等值子串”，否則求出（輸出）一個長度最大的等值子串。例如：若 S=“abc123abc123!，則輸出“無等值子串”；若S=“abceebccadddddaaadd!，則輸出dddd）寫一個遞歸算法來實現字符串逆序存儲，要求不另設串存儲空間。習題五數組和廣義表一、單項選擇題1．常對數組進行的兩種基本操作是（ A.建立與刪除 B.索引與修改 C.查找與修改 D.查找與索引2．對于C語言的二維數組DataTypeA[m][n],每個數據元素占K個存儲單元，二維數組任意元素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數組A[0..5,0..6]的每個元素占五個字節，將其按列優先次序存儲在起始地址為的內存單元中，則元素的地址( 。A.1175 B.1180 C.1205 D.1210是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數中，則對任一上三角元素a[i][j]對應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用數組rnextjj沿鏈移動的操作為()。A.j=r[j].nextB.j=j+1C.j=j->nextD.j=r[j]->next對稀疏矩陣進行壓縮存儲目的是（ 。A．便于進行矩陣運算 便于輸入和輸C．節省存儲空間 降低運算的時間復雜度已知廣義表LS＝((a,b,c),(d,e,f)),運用head和tail函數取出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）設廣義表La,b,，則L的長度和深度分別為（ 。A.1和1 B.1和3 C.1和2 D.2和3下面說法不正確的( 。廣義表的表頭總是一個廣義表 B.廣義表的表尾總是一個廣義表C.廣義表難以用順序存儲結構 D.廣義表可以是一個多層次的結構二、填空題通常采存儲結構來存放數組對二維數組可有兩種存儲方法一種是以 為主序的存儲方式，另一種是為主序的存儲方式。用一維數組B與列優先存放帶狀矩陣A中的非零元素A[i,j]中的第8個元素是A中的_ 行，_ 列的元素。設n行n列的下三角矩陣A已壓縮到一維數組中，若按行為主序儲，則A[i,j]對應的B中存儲位置。所謂稀疏矩陣指的_ 。廣義表簡稱表，是由零個或多個原子或子表組成的有限序列，原子與表的差別僅在于。為了區分原子和表，一般用

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

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

2I-1-1

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

_；編號是i的結點所在的層次號是_

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

樹而變成一個有序序列，構造樹的過程即若一個二叉樹的葉子結點是某子樹的中序遍歷序列中的最后一個結點，則它必是該子樹的 序列中的最后一個結點。若作為葉子結點的權值構造哈夫曼樹則其帶權路徑長度。以下程序段采用先根遍歷方法求二叉樹的葉子數，請在橫線處填充適當的語句。Voidcountleaf(bitreptrt,intt，假定葉子數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) */}

;棧頂元素出棧二叉樹存儲結構同上題，以下程序為求二叉樹深度的遞歸算法，請填空完善之intdepth(bitreebt) /*bt為根結點的指*/{inthl,hr;if(bt==NULL)return((1)_

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

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

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

，這 。

的；對程序V2V1V3V5V2V1V3V5V4V6（1．列出對右圖執行該程序后的輸出結果。（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;}}}三、應用題1．每個頂點的入度、出度；鄰接矩陣；鄰接表；逆鄰接表；強連通分量。已知圖的鄰接矩陣為：V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000當用鄰接表作為圖的存儲結構，且鄰接表都按序號從大到小排序時，試寫出：（1．以頂點V1為出發點的唯一的深度優先遍歷；（2．以頂點V1為出發點的唯一的廣度優先遍歷；（3．該圖唯一的拓撲有序序列。已知一個無向圖如下圖所示，要求分別用PrimKruskal（為起點，試畫出構造過程。201 11 2 5910 10

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

和

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

和

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