【正文】 價(jià)格、數(shù)量和鏈指針三個(gè)域。 4. pnext=snext。( )相鄰， 單鏈表中邏輯上相鄰的元素物理位置_________相鄰。（C）pnext=pnext。pnext=s。j++) for ( k=1。 i++)for(j =1。 ,每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以_________。 ① （A）計(jì)算方法（B）排序方法（C）解決問(wèn)題的有限運(yùn)算序列（D）調(diào)度方法 ② （A）可執(zhí)行性、可移植性和可擴(kuò)充性（B）可行性、確定性和有窮性 （C）確定性、有窮性和穩(wěn)定性 （D）易讀性、穩(wěn)定性和安全性 二、判斷題 。 （A）理想結(jié)構(gòu)，物理結(jié)構(gòu) （B）理想結(jié)構(gòu)，抽象結(jié)構(gòu) （C）物理結(jié)構(gòu)，邏輯結(jié)構(gòu) （D）抽象結(jié)構(gòu)，邏輯結(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é)構(gòu) （C）線性結(jié)構(gòu)和非線性結(jié)構(gòu)（D）內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) （①）以及它們之間的（②）和運(yùn)算等的學(xué)科。（ ） 三、填空題 、________、_________ 和_________四種類型,其中樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為_____。 ,為了最快的存儲(chǔ)某元素,數(shù)據(jù)結(jié)構(gòu)宜用_________結(jié)構(gòu),為了方便插入一個(gè)元素,數(shù)據(jù)結(jié)構(gòu)宜用____________結(jié)構(gòu)。i=n。 (A) 必須是連續(xù)的 (B) 部分地址必須是連續(xù)的 (C) 一定是不連續(xù)的 (D) 連續(xù)與否均可以 4. 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（ ） （A）snext=p。，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（ ） （A）pnext=pnextnext。（ ） =pnext完成了指針賦值并使p指針得到了p指針?biāo)负罄^結(jié)點(diǎn)的數(shù)據(jù)域值。 ，是從下列提供的答案中選擇合適的語(yǔ)句序列，分別實(shí)現(xiàn)： （1）表尾插入s結(jié)點(diǎn)的語(yǔ)句序列是_______________________________(2) 表尾插入 s結(jié)點(diǎn)的語(yǔ)句序列是_______________________________1. pnext=s。 9. while(pnext!=null) p=pnext。 =(a0,a1,a2,...,an1),B=(b0,b1,b2,...,bm1)是兩個(gè)給定的線性表,它們的結(jié)點(diǎn)個(gè)數(shù)分別是n和m,且結(jié)點(diǎn)值均是整數(shù)。 。int aver(NODE *head){int i=0,sum=0,ave。}include include typedef struct node{int data。q=qlink。amp。int num。q!=head){p=q。}}順序表： 算法思想：從0開始掃描線性表，用k記錄下元素值在a與b之間的元素個(gè)數(shù)，對(duì)于不滿足該條件的元素，前移k個(gè)位置，最后修改線性表的長(zhǎng)度。p= head。 qdatab){r=q。amp。amp。else if(a[i]b[i]) return(1)。p!=NULL。elemtype temp。convert(list,0,m1)。q=*head。rlink=p。while(alink!=ahamp。}if(alink==ah) /*a的結(jié)點(diǎn)個(gè)數(shù)小于等于b的結(jié)點(diǎn)個(gè)數(shù) */{alink=b。struct node *link。p=plink。 qlink=qh。}}12.typedef struct node{elemtype data。q=qlink。（A）STtop!=0 （B）STtop==0 （C）STtop!=m01（D）STtop==m01,2,3,4,則隊(duì)列的輸出序列是（ ）。其中i=1表示左邊的棧，,i=2表示右邊的棧。return(0)。return(0)。while(!empty(s1)){pop(s1,amp。}}第四章 串 一、選擇題 ，正確的是（ ）　(A)一個(gè)串的字符個(gè)數(shù)即該串的長(zhǎng)度 (B)一個(gè)串的長(zhǎng)度至少是1　　(C)空串是由一個(gè)空格字符組成的串 (D)兩個(gè)串S1和S2若長(zhǎng)度相同，則這兩個(gè)串相等abaaabab的nextval值為(? )(A)(0,1,01,1,0,4,1,0,1) (B)(0,1,0,0,0,0,2,1,0,1)(C)(0,1,0,1,0,0,0，1,1) (D)(0,1,0,1,0,1,0,1,1),其中head和tail的定義同廣義表類似,如head(‘xyz’)= ‘x’,tail(‘xyz’)= ‘yz’,則s=( )。\039。s2[i]=39。t2=(NODE *)malloc(sizeof(NODE))。s=s2。?int i。t1=t1link。（A）SA+141（B）SA+144（C）SA+222（D）SA+225[8][10]中,每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié),從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi),該數(shù)組按列存放時(shí),元素A[4][7]的起始地址為（ ）。6的二維數(shù)組,其每個(gè)元素占用3個(gè)存儲(chǔ)單元,并且A[0][0]的存儲(chǔ)地址為1000,元素A[1][3]的存儲(chǔ)地址為___________,該數(shù)組共占用_______________個(gè)存儲(chǔ)單元。(3)計(jì)算廣義表所有原子結(jié)點(diǎn)數(shù)據(jù)域(設(shè)數(shù)據(jù)域?yàn)檎汀抵偷暮瘮?shù)sum_GL()。jn。}for(i1=0。從a[i]開始循環(huán)報(bào)數(shù),每報(bào)一次,計(jì)數(shù)器的值加1,凡報(bào)到m時(shí)便打印出a[i]值(退出圈外的猴子的編號(hào)),同時(shí)將a[i]的值改為O(以后它不再參加報(bào)數(shù)),計(jì)數(shù)器值重新置為0。jn。a[j]=0。}NODE。if(ch==39。(*s)++。elseprn_GL(p )。qtag=ptag。if(p==NULL) return(0)。if(ptag==0) return(0)。}if(hmaxdh)maxdh=h。prn_GL(head(hd))。（A）2h （B）2h1（C）2h+1（D）h+1。（A）10（B）12（C）15（D）17二、判斷題 。_________________________2）后序和中序遍歷，得到的結(jié)點(diǎn)訪問(wèn)順序一樣。(3)編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)。(2)求出每個(gè)字符的晗夫曼編碼。所以 n0+n1=k*n1+1n0=(k1)*n1+1五、算法設(shè)計(jì)void parent(int a[],int n,int i){if(i==1) {printf(無(wú)雙親 \n)。 /*自身不輸出 */if(2*p=n)queue[tail++]=2*p。scanf(%d,amp。void create(NODE **T) //創(chuàng)建二叉樹{ char ch。((*T)lchild))。if(plchild!=NULLamp。amp。amp。else return(sum(tlchild)+sum(trchild)+1)。 //top為棧頂指針p=root。 //q為p的雙親結(jié)點(diǎn)int top=0。}p=*root。 free(p)。 }}void lev_traverse(NODE *T) //按層次從上到下,每層從右到左的順序列出二叉樹所有結(jié)點(diǎn)的數(shù)據(jù)信息{NODE *q[100],*p。if(plchild!=NULL)q[tail++]=plchild。if(num1num2)return(num1+1)。amp。if(t1==t2amp。else{like1=like(t1lchild,t2lchild)。change(trchild,2*i+1)。\039。else return(0)。 （A）n （B）n(n1)（C）n(n1）/2（D）2n（ ）條邊。 ，若存在一條從頂點(diǎn)i到頂點(diǎn)j的弧，則在頂點(diǎn)的拓?fù)湫蛄兄?，頂點(diǎn)i與頂點(diǎn)j的先后次序是_________________。Q)。//訪問(wèn)vifor(p=Gadjlist[i].firstedge。 (若存在)，分析算法的時(shí)間復(fù)雜度。 ,首先查找__________,然后再查找相應(yīng)的___________。 （A）以順序方式存儲(chǔ)（B）以鏈接方式存儲(chǔ) （C）以順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序 （D）以鏈接方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序 ,每個(gè)元素的平均查找長(zhǎng)度為（ ） （A）n （B）n/2（C）(n+1)/2（D）(n1)/2,每個(gè)元素的平均查找長(zhǎng)度為（ ） （A）O(n2)（B）O(log2n)（C）O(n)（D）O(log2n)（ ）。設(shè)計(jì)出這種鏈表結(jié)構(gòu),并求該表平均查找長(zhǎng)度。 六、算法設(shè)計(jì) 哈希表的刪除 參考答案：一、判斷題 √二、填空題 (n+1)/2；((n+1)*log2(n+1))/n1；(s2+2s+n)/2s；log2(n/s+1)+s/2；1+α 哈希表查找 順序；有序的 索引；塊 15 小于表長(zhǎng)的最大素?cái)?shù) ①1 ②2 ③4 ④8 ⑤5 ⑥ ①O(n) ② O(log2n) 10 三、選擇題 1. B 3. C 4. D 5. B 8. B 六、算法設(shè)計(jì) 哈希表的刪除 hashtable del_hashtable (hashtable amp。amp。 （A）起泡排序（B）快速排序（C）堆排序（D）基數(shù)排序 ,效率最高的排序方法是（ ） （A）插入排序（B）選擇排序（C）快速排序（D）歸并排序 (46,79,56,38,40,84),則利用堆排序的方法建立的初始推為（ ）。 ，不穩(wěn)定的方法是（ ） (A)直接插入排序 (B)冒泡排序 (C)歸并排序　(D)直接選擇排序 。 （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(25,48,16,35,79,82,23,40,36,72),其中含有5個(gè)長(zhǎng)度為2的有序表,按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（ ）。qnext=pnext。if ( hash[t]= = null) return (infeasible)。 。 （A）1（B）2（C）4（D）8=14,哈希函數(shù)H(key)=key%11。 (key)=key%p中,p應(yīng)取_______________。（ ） 。p=pnext)//依次搜索vi的鄰接點(diǎn)vj(不妨設(shè)padjvex=j)if(!visited[padjvex])//若vj沒(méi)有訪問(wèn)過(guò) EnQueue(amp。Q,k)。 4. 如果從一個(gè)頂點(diǎn)出發(fā)又回到該頂點(diǎn)，則此路徑叫做_______。 （A）5（B）6（C）7（D）8,要連通全部頂點(diǎn)至少需要（ ）條邊。（ ） 。if(flagamp。change(t,1)。return(like1amp。t2==NULL) return(1)。s[++top]=p。}}int onechild3(NODE *root) //非遞歸統(tǒng)計(jì)出二叉樹共有多少個(gè)度為1的結(jié)點(diǎn){ NODE *p,*s[100]。if(t==NULL) return(0)。q[0]=T。}s[++top]=p。while((p!=NULL)||(top0)){ while(p!=NULL){if(plchild==NULLamp。if((*root)lchild==NULL amp。while((p!=NULL)||(top0)){ while(p!=NULL){printf(%d ,pdata)。else if(tlchild==NULLamp。amp。amp。prchild==NULL||plchild==NULLamp。((*T)rchild))。if(ch==39。parent(a,n,i)。}main(){int a[MAX],n,i。}Elseprintf(雙親:%d\n,a[(i1)/2])。(4)并譯出編碼系列1100011100010101的相應(yīng)電文。：一個(gè)滿k叉樹上的葉子結(jié)點(diǎn)數(shù)n0和非葉子結(jié)點(diǎn)數(shù)n1之間滿足以下關(guān)系： n0=（k1）n1+1(50,28,78,65,23,36,13,42,71）,請(qǐng)完成以下操作:(1)畫出按元素排列順序逐點(diǎn)插入所生成的二叉排序樹BT。__________________________，可能達(dá)到的最大深度和最小深度各是多少？____________________，這些結(jié)點(diǎn)的度要么是0，要么是2。（ ）。（A）acbed （B）decab（C）deabc （D）cedba,那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的（ ）（A）前序（B）中序（C）后序（D）層次序,中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是（ ）。hc=copy_GL(hd)。}return(maxdh+1)。amp。else n=sum(p)。elseq =p。if(ptag==1)printf())。,39。){htag=1。char ch。d++。count=0。因此,現(xiàn)本題功能的程序如下:include main(){int a[100]。i1++)for(j=0。}for