數(shù)據(jù)結(jié)構(gòu)試題試卷2006-2007.2dsb

一、選擇題(每題2分，共20分串的長(zhǎng)度是指A．串中所含不同字母的個(gè) B．串中所含字符的個(gè)C．串中所含不同字符的個(gè) D．串中所含非空格字符的個(gè)一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是( A.edcba C.一定是不連續(xù) 的位置是)T41,2,344,2,1,1T()A.B.C.D.A（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，)有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為：( A. B C. D.nA以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B［1..(n(n+1))/2］中，則在B中確定aij（i<j）的位置k的關(guān)系為()。A.i*(i- B.j*(j- C.i*(i-1)/2+j- D.j*(j-1)/2+i-一個(gè)7個(gè)頂點(diǎn)的連通圖，其邊的數(shù)目不可能為 )A. B. C. D.（1）84472515 （2）15472584（3）15212584 （4）15212547則采用的排序是 )A.選 B.冒 C.快 D.插二、綜合填空題(每空2分，共24分在循環(huán)隊(duì)列中用數(shù)組A[0..m-1]存放隊(duì)列元素其隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear， 有n個(gè)葉子 樹(shù)的結(jié)點(diǎn)總數(shù) 一棵二叉樹(shù)有17個(gè)結(jié)點(diǎn)，則這棵二叉樹(shù)的高度最大為 ，最小 已知串S='cbacbcac',其N(xiāo)ext數(shù)組值 設(shè)森林FB，B有mp，p的右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)為n,F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù) 在單鏈表中，指針p所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件 設(shè)有一個(gè)順序棧S，元素s1,s2,s3,s4,s5,s66s3,s4,s6,s5s2,s1，則順序棧的容量至少應(yīng) _nexthaexp{ if(pa->exp==0 ); //} pa->coef=( q= // //}}三、算法閱讀題(共16分以下函數(shù)中,L 結(jié)點(diǎn)的非空線性鏈表的頭指針：(8分n sym(LinkListL) p=p->next;} }// return return}//已知BiTree為二叉樹(shù)的鏈?zhǔn)?結(jié)構(gòu)，visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)，閱讀下列算法，闡述其功能：(8分)voidFun(BiTreeT,void(*visit)( InitStack(S); p=T;while(p||!StackEmpty(S)){if(p){(*visit)(p->data);Push(S,p);p=p-}elsePop(S, p=p->rchild;}}四、算法應(yīng)用題(共30分S=‘a(chǎn)abaabaabaac'P=‘a(chǎn)abaac',SP作模式串，試給出利用KMP算法的匹配過(guò)程。(6分)(此題本次考試超綱)AOE網(wǎng)絡(luò)(7分bbd2a64f5ce請(qǐng)把圖a的樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)。(6分A 設(shè)一組數(shù)據(jù)為{1,14,27,29,55,68,10,11,23}，現(xiàn)采用的哈希函數(shù)是H(key)=keyMOD13，即關(guān)鍵字對(duì)13取模， 用鏈地址法解決，設(shè)哈希表的為T(mén)[0 12]，試畫(huà)出插入上述數(shù)據(jù)后的哈希表并求出在等概率情況下,查找成功的平均查找長(zhǎng)度。(7分)（125926324排序每趟的結(jié)果。(4分五、算法設(shè)計(jì)題(共10分在一個(gè)循環(huán)鏈隊(duì)中只有尾指針（記為rear，結(jié)點(diǎn)結(jié)構(gòu)為數(shù)據(jù)域data，指針域next，請(qǐng)專(zhuān)業(yè) 班級(jí) 學(xué) 學(xué)專(zhuān)業(yè) 班級(jí) 學(xué) 學(xué)生簽名數(shù)據(jù)結(jié) 課 課程類(lèi)別： 開(kāi)卷(范圍)(僅 題—二三四五六七八九十總計(jì)分簽題得考生注意事項(xiàng)：18100120一、選擇題(每題2分，共20分123456789123456789二、填空題