【正文】 0,b1,...,bm1）的存儲(chǔ)結(jié)構(gòu),頭指針分別為ah和bh，設(shè)計(jì)C函數(shù)，把兩個(gè)線性表合并成形如（a0,b0,a1,b1,…）的線性表，要求不開辟新的動(dòng)態(tài)空間,利用原來循環(huán)鏈表的結(jié)點(diǎn)完成合并操作,結(jié)構(gòu)仍為循環(huán)鏈表,頭指針為head,并分析算法的時(shí)間復(fù)雜度。 ,試寫出刪除x結(jié)點(diǎn)的C函數(shù)。 (1)6) 3)(2) 2) 9）1) 7)四、算法設(shè)計(jì)題include include typedef struct node{int data。 NODE *p。sum=sum+pdata。 /* 假設(shè)數(shù)據(jù)域?yàn)檎?*/struct node *link。q=headlink。free(s)。p=head。q!=head){p=q。if(qnum==0){pnext=qnext。struct node *next。q=headnext。q=qnext。snum=num。 void del（elemtype list[]，int *n，elemtype a，elemtype b） {int i=0，k=0； while（in){if(list[i]=aamp。i++。q=plink。q=qlink。q=qlink。int n,m。inamp。amp。i==n) return(1)。if(inamp。}void del(DUNODE　**head,int i){DUNODE *p。}　 Else{for(j=0。j++)p=pnext。free(p)。for(i=h。list[l+hi]=temp。convert(list,m,n+m1)。void convert(NODE **head,int n,int m){NODE *p,*q,*r。for(i=0。qlink=NULL。 }該算法的時(shí)間復(fù)雜度為O(n+m),但比順序存儲(chǔ)節(jié)省時(shí)間(不需要移動(dòng)元素,只需改變指針),空間復(fù)雜度為O(1)9.typedef struct node{elemtype data。head=ah。amp。blink=r。while(blink!=bh)b=blink。blink=r。}NODE。while(p!=NULL){rlink=p。if(p!=NULL){qlink=p。}}rhdata=i。} 11.typedef struct node{elemtype data。p=head。struct node *link。 p=y。p=q。（A） edcba（B）decba（C）dceab （D）abcde （ ）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1[0,m1]存放其元素值,已知其頭尾指針分別是front和rear則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（ ）（A）(rearfront+m)%m （B） rearfront+1 （C）rearfront1（D）rearfront（ ）（A） 都是先進(jìn)后出 （B）都是先進(jìn)先出（C）只允許在端點(diǎn)處插入和刪除元素（D）沒有共同點(diǎn)*(b+c)d的后綴表達(dá)式是（ ）。(正確/錯(cuò)誤)，元素a1，a2，a3，a4，a5和a6依次通過一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a3，a5，a4，a6，a2，a1則棧S至少應(yīng)該容納_____個(gè)元素。要求在整個(gè)數(shù)組元素都被占用時(shí)才產(chǎn)生溢出。int push(elemtype x,int i){if(top1top2==1) return(1)。} int pop(elemtype *px,int i){if(i==1)if(top1==0) return(1)。}elseif(i==2)if(top2==M1) return(1)。}}2.elemtype s1[MAXSIZE],s2[MAZSIZE]。return(0)。x)。while(!empty(s2)){pop(s2,amp。 concat(head(tail(s)),head(tail(tail(s))))= ‘dc’。int S_strlen(char s[]){int i。i++)。s1[i]!=39。\039。NODE *L_strcpy(NODE *s1) {NODE *s2,*t1,*t2,*s。s2=t2。t2=s。s2=s2link。struct node *link。t1=t。while(p1data==t1dataamp。}if(p1==NULL) return(i)。}第五章 數(shù)組和廣義表一、選擇題 1. 常對數(shù)組進(jìn)行的兩種基本操作是（ ）（A）建立與刪除（B）索引和修改（C）查找和修改（D）查找與索引(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串,行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,M按行存儲(chǔ)時(shí)元素M[3][5]的起始地址與M按列存儲(chǔ)時(shí)元素( ) 的起始地址相同。（A）SA+141（B）SA+180（C）SA+222（D）SA+225,即（ ）。[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ),每個(gè)元素占一個(gè)存儲(chǔ)單元,并且A[0][0]的存儲(chǔ)地址是200,則A[6][12]的地址是________________。三、算法設(shè)計(jì) [i][j]滿足條件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,則稱之為該矩陣的一個(gè)馬鞍點(diǎn)。編寫一程序?qū)崿F(xiàn)上述函數(shù)。 參考答案：一、選擇題1. C 3. C 4. C 5. B B B 二、填空題loc(A[0][0])+(n*i+j)*k 332 42 i*(i+1)/2+j+1 1039；72 三、算法設(shè)計(jì)題1.算法思想：依題意,先求出每行的最小值元素,放入min[m]之中,再求出每列的最大值元素,放入max[n]之中,若某元素既在min[i]中,又在max[j]中,則該元素A[i][j]便是馬鞍點(diǎn),找出所有這樣的元素,即找到了所有馬鞍點(diǎn)。i1m。j++)if(a[i1][j]min[i1]) min[i1]=a[i1][j]。for(i1=1。i1m。have=1。該函數(shù)一直進(jìn)行到n只猴子全部退出圈外為止,最后退出的猴子就是大王。m,amp。j++)a[j]=j+1。jn。count=0。char data。NODE *creat_GL(char **s){NODE *h。if(ch!=39。(39。h=ch。if(h!=NULL)if(ch==39。return(h)。}elseprintf(%c,p)。}}}NODE *copy_GL(NODE *p){NODE *q。if(ptag)q =copy_GL(p )。}NODE *head(NODE *p) /*求表頭函數(shù) */{return(p)。else{ if(ptag==0) n=p。return(n+m)。else if(ptag==1amp。while(p!=NULL){if(ptag==0) h=0。p=plink。p=gets(s)。prn_GL(tail(hd))。 printf(sum:%d\n,sum(hd))。中序遍歷序列是debac,它的前序遍歷序列是（ ）。（A）3（B）4（C）5（D）6,根結(jié)點(diǎn)的右邊（ ）（A）只有右子樹上的所有結(jié)點(diǎn)（B）只有右子樹上的部分結(jié)點(diǎn)（C）只有左子樹上的部分結(jié)點(diǎn)（D）只有左子樹上的所有結(jié)點(diǎn)（ ）。（ ）。,中序序列為DBGEAHFIJC,寫出后序序列_______________。_________________________3）先序和后序遍歷，得到的結(jié)點(diǎn)訪問順序一樣。四、問答題 :第h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn),其余各層上每個(gè)結(jié)點(diǎn)都有m棵非空子樹。(4)編號為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)(若有)的編號。,其權(quán)值分別為3,7,8,2,6,10,14,試以它們?yōu)槿~結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(請按照每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造〉,并計(jì)算出帶權(quán)路徑長度WPL及該樹的結(jié)點(diǎn)總數(shù)。(3)求出傳送電文的總長度。 樹可采用二叉樹的存儲(chǔ)結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題。return。tail++。if(2*p+1=n) queue[tail++]=2*p+1。n)。i)。struct node *lchild,*rchild。ch=getchar()。else{ *T=(NODE *)malloc(sizeof(NODE))。create(amp。? inorder(prchild)。amp。count(prchild)。prchild==NULL||plchild==NULLamp。}}int onechild(NODE *t) //統(tǒng)計(jì)出二叉樹中單孩子的結(jié)點(diǎn)數(shù)方法2{int num1,num2。trchild!=NULL||tlchild!=NULLamp。num2=onechild(trchild)。}int leaf(NODE *t) //統(tǒng)計(jì)出二叉樹中葉子結(jié)點(diǎn)數(shù){if(t==NULL) return(0)。elsereturn(leaf(tlchild)+leaf(trchild))。q=p。 }p=s[top]。 //top為棧頂指針if((*root)==NULL)return。amp。q=p。amp。return。 }p=s[top]。int head,tail。while(headtail){p=q[head++]。}}int depth(NODE *t) //求二叉樹的深度{int num1,num2。trchild ==NULL) return(1)。elsereturn(num2+1)。while((p!=NULL)||(top0)){ while(p!=NULL){if(plchild!=NULLamp。prchild!=NULL)num++。 p=prchild。amp。t2!=NULL||t1!=NULLamp。like2=like(t1rchild ,t2rchild )。}}char a[100]。}}int plete(NODE *t) //判斷二叉樹是否為完全二叉樹{int i,flag=0。i++){if(!flagamp。) flag=1。\039。}第七章 圖 一、判斷題 。（ ） 二、選擇題 ,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ ）倍。 （A）6（B）12（C）16（D）20（ ）條邊才能確保是一個(gè)連通圖。 （A）先序遍歷（B）中序遍歷（C）后序遍歷（D）按層遍歷 （ ）。 ，若表結(jié)點(diǎn)的個(gè)數(shù)是m，則圖中邊的條數(shù)是________________條。 7. 一個(gè)連通圖的生成樹是該圖的________連通子圖。//置空隊(duì)列 EnQueue(amp。Q)。p。 (或生成森林)的算法，要求打印出所有的樹邊。參考答案：一、判斷題√二、選擇題 1. C 3. C 4. A 5. A B A、C A D 1D 1B 三、填空題n1 i在前，j在后 m/2 回路 強(qiáng)連通圖 按層 極大；n1第八章 查找 一、判斷題 ，這個(gè)順序表可以是按各鍵值排好序的，也可以是沒有按鍵值排好序的。( )：隨機(jī)性好、均勻性好和盡量避免沖突。 ,采用分塊查找法,每塊的最佳長度是____________。 (12,18,20,25,29,32,40,62,83,90,95,98),當(dāng)二分查找值為29和90的元素時(shí),分別需要________次和____________次比較才能查找成功；若采用順序查找時(shí),分別需要___________次和_________次比較才能查找成功。 （A）相同? （B）不相同? （C）無法比較 {1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí),（ ）次比較后查找成功。 （A）10（B）25（C）6（D）625,又能適應(yīng)動(dòng)態(tài)變化的要求,可以采用（ ）查找方法。 (32,75,63,48，94,25,36,18,70),散列地址空間為[0...10],若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突,試給出它們對應(yīng)的散列表,并求出在等概率情況下的平均查找長度。 (C)順序表 (3）插入、刪除和順序存取速度快,但查找速度慢。hash, keytype K){t=h(k)。q=hash[t]。(p null))if ( pkey= =K){found=1。}if(!found) return (infeasible)。 （A）79,46,56,38,40,80 （B）84,79,56,38,40,46（C）84,79,56,46,40,38 （D）84,56,79,40,46,38(46,79,56,38,40,84),則利用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。 （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序