【正文】 ut[i]。}void add(list amp。A, list amp。B){int i, j, x。i=。 x=0。for (j=maxlength。 j= j) { x=[j]+[i]+x。 [j]=x%10。 x=x/10。 i++。 } =。 if(x0){ 。 []=x。 } count++。} void revers(list amp。A, list amp。B){ test(A)。 if((result==0)amp。amp。(countmaxtimes)){ add(A,B)。 reverse(B,A)。}}數(shù)據(jù)結(jié)構(gòu)模擬題三參考答案 √ √ √ . √ √二．填空題隊(duì)列為空 隊(duì)列中有2個(gè)或2個(gè)以上元素 非零元素個(gè)數(shù)的一半 66 3 12 根據(jù)記錄指針從數(shù)據(jù)區(qū)中讀記錄 繼續(xù)沿指針向下一直查到該關(guān)鍵字所在樹(shù)葉 1． 0 1 2 3 4 5 6HT2715104517202． 1 2 3 4 5 6 7 8llinkrlink2305241774264180（1，17，4，16，15，9，8，14，6，16，11，12，17，2，17，17）1..char s。 int na=0,nb=0。 void count(char t, int amp。n){ int i。 i=0。 do{i++。cins。} while (s==t)。if (in) n=i 。 } void main(){ cins。 while (s!=’’){ switch(s) { case ‘A’: count(‘A’,na)。 break。 case ‘B’: count(‘B’,nb)。 } if ((s!=’A’)amp。amp。(s!=’B’)) cins。 } cout”A平臺(tái)的最大值是：”na。cout”B平臺(tái)的最大值是：”nb。}數(shù)據(jù)結(jié)構(gòu)模擬試題五參考答案一、( 共34分，每題2分)單項(xiàng)選擇題C A D A B D B D C D 1A 1D 1D 1C 1D 1C 1C二、（共30分，每空2分）填空題答：有 、無(wú)答：N、2E答：結(jié)點(diǎn)的有窮集合、K上關(guān)系的有窮集合答：順序答：棧答：中答：4 答：2, 4 答：O(nlog2n) 答：n+1, 線索三：（共11分，每題1分）判斷題√ √ √ √1四、（10分）各趟結(jié)果如下：　　　　　 [68　05　71　23　16]　72　[94　73]　　　　　 [16　05　23] 68 [71]　72　[94　73]　　　　　 [05] 16 [23] 68 [71]　72　[94　73] 　　　　　　05　16 [23] 68 [71]　72　[94　73] 　　　　　　05　16　23　68　71　 72　[94　73] 　　　　　　05　16　23　68　71　 72　[73] 94 05　16　23　68　71　 72 　73　94五、（10分）按行存儲(chǔ)時(shí)與按列存儲(chǔ)時(shí)，計(jì)算A[i][j]地址的公式分別為 LOC（i，j）=LOC（0，0）+（I*n＋j）*d及 LOC39。（i，j）=LOC（0，0）＋（j*n＋i）*d兩者相減，得LOC（i，j）－LOC39。（i，j）=LOC（0，0）＋（i*n＋j）*d－LOC（0，0）－（j*n＋i）*d =（i－j）*n*d＋（j－i）*d或： =（i－j）*（n－1）*d六、（10分）cc(00)d(01)a(100)b(101)e(11)c d e a b七、（15分）解：typedef struct node{int data。struct node *next。}link。void trans(int num,int r){link *head=NULL,*s。int n。while (num0){n=num%r。s=(link *)malloc(sizeof(link))。sdata=n。snext=head。head=s。num=num/r。}printf(“輸出r進(jìn)制的各位數(shù)字：”)；s=head。while (s!=NULL){printf(“%d”,sdata)。s=snext。}}八、（15分）解：int GetLeaves( BinTree root){ //求葉結(jié)點(diǎn)總數(shù) static int leaf=0。//此l用于記葉結(jié)點(diǎn)數(shù)，注意用靜態(tài)變量 if(root) { //遞歸計(jì)算葉結(jié)點(diǎn)數(shù) if(!(rootlchild||rootrchild)) leaf++。 //如果該結(jié)點(diǎn)無(wú)左右孩子，則葉子數(shù)加1 GetLeaves(rootlchild)。//算左子數(shù)的葉結(jié)點(diǎn)數(shù) GetLeaves(rootrchild)。//算右子樹(shù)的葉結(jié)點(diǎn)數(shù) } return leaf。 //返回結(jié)果}九、（15分）解：Void split(ListNode *L, ListNode *amp。A, ListNode *amp。B){ListNode *p=Lnext。A=(ListNode *)malloc(sizeof(ListNode ))。Anext=A。B=(ListNode *)malloc(sizeof(ListNode ))。Bnext=B。while (p!=L){if (pdata%2==1){q=p。p=pnext。qnext=Anext。Anext=q。}else {q=p。p=pnext。qnext=Bnext。Bnext=q。}}}數(shù)據(jù)結(jié)構(gòu)模擬試題四參考答案一、( 共30分，每題2分)單項(xiàng)選擇題1A 2C 3A 4C 5D 6D 7B 8C 9C 10D 11D 12D 13C 14C 15 D二、（共40分，每空2分）填空題log2n snext=p 中序 300 一對(duì)一的，一對(duì)多或多對(duì)多的 最小 4 235129 2m1 1中序，M 12，4 1鄰接矩陣 1插入排序，選擇排序 1n+1,線索三、（10分）解：設(shè)N為總結(jié)點(diǎn)數(shù)，N0為葉子結(jié)點(diǎn)數(shù)則：N=N0+N1+N2+……+Nm又有：N1=度的總數(shù)，則：N1=N1*1+N2*2+……Nm*m則有：N0=1+N2+2N3+……+(m1)Nm四、（15分）cc(00)d(01)a(100)b(101)e(11)c d e a b五、（15分）線性探測(cè)再散列的散列表：0 1 2 3 4 5 6 7 8 9 10 11 1214168275519208479231110121431139113查找成功的平均長(zhǎng)度為ASL=1/12（1*6+2*1+3*3+4*1+9）=查找不成功的平均長(zhǎng)度為ASL=1/13（1+2+3+4…….+13）=7六（15分）（1）void oesort ( int a[n]){int i,flag。do{flag=0。for (i=1。in。i+=2) //奇數(shù)掃描if (a[i]a[i+1]){ flag=1 。t=a[i+1]。a[i+1]=a[i]。a[i]=t。}for (i=2。in。 i+=2) //偶數(shù)掃描if (a[i]a[i+1]){flag=1。t=a[i+1]。a[i+1]=a[i]。a[i]=t。}} while (flag)。（2） 兩趟排序無(wú)交換出現(xiàn)（3） n1次}七（10分）（1）i=n （2）(j=i+1。j=n。j++)（3）n八（15分）void path(T,p)Bintree T,p。{Bintree stack[max],q。int tag[max],top=0,find=0。q=T。while ((q||top)amp。amp。 find==0){while (q){stack[top]=q。 tag[top++]=0。 q=qlchild。}if (top0) {q=stack[top1]。 if (tag[top1]==1) {if (q==p) {for (i=0。itop。i++) printf(“%d”,stack[i]data)。find=1。} else top。} if (top0amp。amp。!find) {q=qrchild。 tag[top1]=1。}}17