【正文】 (A)選擇排序法(B)快速排序法(C)堆排序法(D)冒泡排序法。 （A）16,25,35,48,23,40,79,82,36,72（B）16,25,35,48,79,82,23,36,40,72（C）16,25,48,35,79,82,23,36,40,72（D）16,25,35,48,79,23,36,40,72,82,從未排序序列中依次取出元素與己排序序列(初始時(shí)為空)中的元素進(jìn)行比較,將其放入己排序序列的正確位置上的方法,稱為（ ） （A）希爾排序（B）起泡排序（C）插入排序（D）選擇排序 ,從未排序序列中挑選元素并將其依次放入己排序序列(初始為空)的一端的方法,稱為（ ） （A）希爾排序（B）歸并排序（C）插入排序（D）選擇排序 (25,84,21,47,15,27,68,35,20)進(jìn)行排序時(shí),元素序列的變化情況如下: (1)25,84,21,47,15,27,68,35,20 ??(2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 ??(4)15,20,21,25,27,35,47,68,845則所采用的排序方法是（ ）。} 第九章 排序 一、選擇題 ，關(guān)鍵字比較的次數(shù)與記錄得初始排列次序無關(guān)的是（ ） （A）希爾排序 （B）起泡排序 （C）插入排序 （D）選擇排序 ,希望用最快的速度挑選出其中前10個(gè)最大的元素,最好（ ）排序法。}else{q=p。while ((!found)amp。else if (hash[t]= =K) hash[t]=hash[t]next。 五、應(yīng)用題 設(shè)閉散列表容量為7，給定表（30，36，47，52，34），散列函數(shù)H（K）＝k mod 6，采用線性探測(cè)解決沖突，要求： （1）構(gòu)造此散列表(散列地址為0~6)： （2）求查找34需要進(jìn)行比較的次數(shù)。 (A）散列表 （1）查找和存取速度快,但插入和刪除速度慢。 (87,25,310,8,27,132,68,95,187,123,70,63,47),散列函數(shù)為h(k)=k%13,采用鏈接法處理沖突。表中已有4個(gè)結(jié)點(diǎn):addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空，如用二次探測(cè)再散列處理沖突,關(guān)鍵字為49的結(jié)點(diǎn)的地址是（ ）。 （A）散列存儲(chǔ)（B）順序存儲(chǔ)或鏈接存儲(chǔ)（C）壓縮存儲(chǔ)（D）索引存儲(chǔ) ,要求線性表必須（ ）。[1..20]上進(jìn)行二分查找,則比較一次查找成功的結(jié)點(diǎn)數(shù)為_________,則比較二次查找成功的結(jié)點(diǎn)數(shù)為__________,則比較三次查找成功的結(jié)點(diǎn)數(shù)為_________,則比較四次查找成功的結(jié)點(diǎn)數(shù)為________,則比較五次查找成功的結(jié)點(diǎn)數(shù)為_________,平均查找長度為_________。 ,平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查法方法是_________,且是__________。（ ） （key）=key%p(p=m)這種方法是直接定址法。 ，試以鄰接矩陣和鄰接表為存儲(chǔ)結(jié)構(gòu)，分別寫出算法： (1)求頂點(diǎn)vi到頂點(diǎn)vj(ij)的最短路徑 (2)求源點(diǎn)vi到其余各頂點(diǎn)的最短路徑 要求輸出路徑上的所有頂點(diǎn)(提示：利用BFS遍歷的思想)，寫一個(gè)基于DFS遍歷策略的算法，求圖中通過某頂點(diǎn)vk的簡單回路(若存在)。Q,padjvex)。//置訪問標(biāo)記 printf(%c,Gadjlist[i].vertex。//k入隊(duì) while(!QueueEmpty(amp。 四、算法設(shè)計(jì)： ： (1)往圖中插入一個(gè)頂點(diǎn) (2)往圖中插入一條邊 (3)刪去圖中某頂點(diǎn) (4)刪去圖中某條邊 ，試以下圖中的v0為源點(diǎn)執(zhí)行該算法，請(qǐng)回答下述問題：(1)對(duì)圖中頂點(diǎn)vn+1，它需入隊(duì)多少次？它被重復(fù)訪問多少次?(2)若要避免重復(fù)訪問同一個(gè)頂點(diǎn)的錯(cuò)誤，應(yīng)如何修改此算法?void BFS(ALGraph *G,int k){//以下省略局部變量的說明，visited各分量初值為假 InitQueue(amp。 ，則該圖一定是____________。 (A){（1，4），（3，4），（3，5），（2，5）}(B){（5，4），（5，3），（5，6）}　　　 (C){（1，2），（2，3），（3，5）}　　　 (D){（3，4），（3，5），（4，5），（1，4）} 三、填空題 。 （A）n （B）n+1（C）n1（D）n/2,若采用鄰接矩陣表示,則該矩陣的大?。?） （A）n （B）(n1) 2（C）n1 （D）n2,若采用鄰接表表示,則表頭向量的大小為（ ），所有鄰接表中的結(jié)點(diǎn)總數(shù)是（ ）。 （A）1/2（B）1（C）2（D）4（ ）條邊。（ ） 。}if(i==100) return(1)。amp。a[i]==39。for(i=1。change(tlchild,2*i)。amp。t2==NULL) return(0)。else if(t1==NULL amp。}int like(NODE *t1,NODE *t2) //判定兩顆二叉樹是否相似{int like1,like2。 p=plchild。prchild==NULL ||plchild==NULLamp。int top=0,num=0。num2=depth(trchild )。if(tlchild ==NULLamp。if(prchild!=NULL)q[tail++]=prchild。head=0。p=prchild。 q=p。else qrchild=NULL。amp。return。amp。 }}void delk(NODE **root,char k) //刪去并釋放數(shù)據(jù)值為k的葉結(jié)點(diǎn){ NODE *p,*s[100],*q。s[++top]=p。 //q為p的雙親結(jié)點(diǎn)int top=0。amp。}}int sum(NODE *t) //統(tǒng)計(jì)出二叉樹中所有結(jié)點(diǎn)數(shù){if(t==NULL) return(0)。trchild==NULL)return(onechild(tlchild)+onechild(trchild)+1)。else if(tlchild==NULLamp。prchild!=NULL)(*num1)++。if(plchild!=NULLamp。amp。void count(NODE *p) //統(tǒng)計(jì)出二叉樹中單孩子的結(jié)點(diǎn)數(shù)方法1{if(p!=NULL){count(plchild)。? } }void inorder(NODE *p) //中序編歷二叉樹{ if(p!=NULL){ inorder(plchild)。create(amp。 39。NODE *T。child(a,n,i)。printf(請(qǐng)輸入i:)。printf( 請(qǐng)輸入二叉樹的結(jié)點(diǎn)個(gè)數(shù):)。if(p!=i)printf(%d ,a[p1])。}void child(int a[],int n,int i) /*i為序號(hào) */{int queue[MAX],front=0,tail=0,p。除根外，每個(gè)分支引出一個(gè)結(jié)點(diǎn)，則樹共有k*n1 +1個(gè)結(jié)點(diǎn)。五、算法設(shè)計(jì) 已知一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹被順序存儲(chǔ)在一維數(shù)組A[n]中,試編寫一個(gè)算法輸出A[i]結(jié)點(diǎn)的雙親和所有孩子。(1)試畫出對(duì)應(yīng)的編碼哈夫曼樹(要求左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán))。(2)分別計(jì)算在BT中查找各元素所要進(jìn)行的元素間的比較次數(shù)及平均比較次數(shù)。(2)整棵樹結(jié)點(diǎn)數(shù)。這棵二叉樹中度為2的結(jié)點(diǎn)有______________________個(gè)。1）先序和中序遍歷，得到的結(jié)點(diǎn)訪問順序一樣。（ ）、右子樹的高度之差的絕對(duì)值不大于2（ ）三、填空題 ,___________,_______________。（A）二叉鏈表（B）廣義表存儲(chǔ)結(jié)構(gòu)（C）三叉鏈表（D）順序存儲(chǔ)結(jié)構(gòu),m個(gè)樹葉,n個(gè)結(jié)點(diǎn),深度為h,則（ ）（A）n=h+m （B）h+m=2n（C）m=h1（D）n=2h1,中序?yàn)閡wtvs,那么該二叉樹的后序?yàn)椋?）（A）uwvts （B）vwuts（C）wuvts （D）wutsv（ ）個(gè)結(jié)點(diǎn)。（A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca、小于其右孩子的值。}第六章 樹和二叉樹一、選擇題 ,t所指結(jié)點(diǎn)沒有左子樹的充要條件是（ ）（A）t〉left==NULL （B）t〉ltag==1（C）t〉ltag=1且t〉left=NULL（D）以上都不對(duì),任一結(jié)點(diǎn)均有指向其前趨和后繼的線索,這種說法（A）正確 （B）錯(cuò)誤 （C）不同情況下答案不確定,任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面,這種說法（ ）(A)正確 (B)錯(cuò)誤 （C）不同情況下答案不確定,所以二叉樹是一種特殊的樹,這種說法（ ）（A）正確 （B）錯(cuò)誤 （C）不同情況下答案不確定,則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（ ）。printf(copy after:)。p)。}}main(){NODE *hd,*hc。h=depth(q)。p==NULL) return 1。NODE *q。if(plink!=NULL)m=sum(plink)。}int sum(NODE *p) /*求原子結(jié)點(diǎn)的數(shù)據(jù)域之和函數(shù) */{ int m,n。qlink=copy_GL(plink)。q=(NODE *)malloc(sizeof(NODE))。if(plink!=NULL){printf(,)。if(p ==NULL)printf( )。)hlink =creat_GL(s)。ch=*(*s)。h=creat_GL(s)。){h=(NODE*)malloc(sizeof(NODE))。ch=*(*s)。struct node *link。}}} 3.include include typedef struct node{ int tag。if(count==m){printf(% d ,a[j])。d=0。/* n=m*/for(j=0。int count,d,j,m,n。} 2.算法思想:本題用一個(gè)含有n個(gè)元素的數(shù)組a,初始時(shí)a[i]中存放猴子的編號(hào)i,計(jì)數(shù)器似的值為0。jn。i1++)if(a[i1][j]max [j]) max[j]=a[i1][j]。jn。for(j=1。int min[m],max[n]。(2)計(jì)算廣義表原子結(jié)點(diǎn)個(gè)數(shù)的函數(shù)count_GL()。,選舉辦法如下:所有猴子按1,2,...,n編號(hào)圍坐一圈,從1號(hào)開始按...、m報(bào)數(shù),凡報(bào)m號(hào)的退出到圈外,如此循環(huán)報(bào)數(shù),直到圈內(nèi)剩下只猴子時(shí),這只猴子就是大王。[1..n*(n+1)/2]中,若按行序?yàn)橹鞔鎯?chǔ),則A[i][j]對(duì)應(yīng)的S中的存儲(chǔ)位置是________________。（A）正確（B）錯(cuò)誤,為了節(jié)省存儲(chǔ),將其下三角部分按行序存放在一維數(shù)組B[1,n(n1)/2]中,對(duì)下三角部分中任一元素ai,j(i=j),在一組數(shù)組B的下標(biāo)位置k的值是（ ）。（A）80（B）100（C）240（D）270[8][10]中,每個(gè)元素A的長度為3個(gè)字節(jié),從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi),該數(shù)組按行存放時(shí),元素A[7][4]的起始地址為（ ）。t1=t2。p1!=NULL) {p1=p1link。while(t1!=NULL){p1=p。int L_index(NODE *t,NODE *p) {NODE *t1,*p1,*t2。return(s2)。}t2link=NULL。sdata=t1data。else{t1=s1。struct node *link。i++)s2[i]=s1[i]。}void S_strcpy(char s1[],char s2[]) //{int i。s[i]!=39。(一個(gè)結(jié)點(diǎn)存放一個(gè)字符)方式下,寫出采用簡單算法實(shí)現(xiàn)串的模式匹配的C語言函數(shù)int L_index(t,p)。push(s1,x)。}pop(s2,amp。top2=0。void enqueue(elemtype x){if(top1==MAXSIZE) return(1)。*px=stack[top2]。*px=stack[top1]。if(i==2)stack[top2]=x。 一個(gè)棧s1用于插入元素,另一個(gè)棧s2用于刪除元素.參考答案：一、選擇題1. C 3. B 4. B 5. B C C C D 二、填空題先進(jìn)先出；先進(jìn)后出線性 ； 任何 ；棧頂；隊(duì)尾；對(duì)頭正確的 3三、算法設(shè)計(jì)題1.define M 100elemtype stack[M]。試編寫對(duì)任一棧作進(jìn)棧和出棧運(yùn)算的C函數(shù)push（x,i)和pop(i),i=l,2。、棧和隊(duì)列都是_____________________結(jié)構(gòu),可以在線性表的______________位置插入和刪除元素，對(duì)于棧只能在________插入和刪除元素，對(duì)于隊(duì)列只能在_______插入元素和_________刪除元素。（A） ST〉top!=0 （B）ST〉t