安徽大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷2010A_第1頁(yè)
安徽大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷2010A_第2頁(yè)
安徽大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷2010A_第3頁(yè)
安徽大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷2010A_第4頁(yè)
安徽大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷2010A_第5頁(yè)
已閱讀5頁(yè),還剩1頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、院/系 年級(jí) 專(zhuān)業(yè) 姓名 學(xué)號(hào) 答 題 勿 超 裝 訂 線(xiàn)-裝-訂-線(xiàn)-安徽大學(xué)20 09 20 10學(xué)年第 2 學(xué)期 數(shù)據(jù)結(jié)構(gòu) 考試試卷(A卷)(閉卷 時(shí)間120分鐘)題 號(hào)一二三四五六七總分得 分閱卷人得分一、填空題(每空1分,共15分)1、在線(xiàn)性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn) 前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)前驅(qū)結(jié)點(diǎn);最后一個(gè)結(jié)點(diǎn) 后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有 個(gè)后續(xù)結(jié)點(diǎn)。2、下面程序段的時(shí)間復(fù)雜度是 。for (i=0;i<n;i+) for (j=0;j<m;j+) Aij=0;3、在具有n個(gè)單元的循環(huán)隊(duì)列中,隊(duì)滿(mǎn)時(shí)共有 個(gè)元素。4、假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18,則它的最小深度為

2、 ,最大深度為 。5、在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行下面的操作:snext=_ _;pnext=_;6、從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時(shí),其查找長(zhǎng)度分別為 和 。7、.一棵二叉樹(shù)有67個(gè)結(jié)點(diǎn),這些結(jié)點(diǎn)的度要么是0,要么是2。這棵二叉樹(shù)中度為2的結(jié)點(diǎn)有_個(gè)。8、在堆排序和快速排序中,若原始記錄接近正序或反序,則選用_。9、若采用鄰接表的存儲(chǔ)結(jié)構(gòu),則圖的廣度優(yōu)先搜索類(lèi)似于二叉樹(shù)的_遍歷。得分二、單向選擇題(每小題1.5分,共15分)1、n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有( )。A、nl條有向邊 B、n條有向邊C、n(n1)

3、2條有向邊 D、n(n一1)條有向邊2、在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表HL中,若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn),執(zhí)行( )。A、 HLp; p一>nextHL; B、 p一>nextHL;HLp;C、 p一>nextHL; pHL; D、 p一>nextHL一>next; HL一>nextp;3、采用線(xiàn)性鏈表表示一個(gè)向量時(shí),要求占用的存儲(chǔ)空間地址( )。A: 必須是連續(xù)的 B 部分地址必須是連續(xù)的C: 一定是不連續(xù)的 D: 可連續(xù)可不連續(xù)4、如果想在4092個(gè)數(shù)據(jù)中只需要選擇其中最小的5個(gè),采用( )方法最好。A: 起泡排序 B: 堆排序 C: 錦標(biāo)賽排序 D

4、: 快速排序5、在循環(huán)隊(duì)列中用數(shù)組A0.m-1 存放隊(duì)列元素,其隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是( )。 A: ( front - rear + 1) % m B: ( rear - front + 1) % mC: ( front - rear + m) % m D: ( rear - front + m) % m6、數(shù)組A0.5,0.6的每個(gè)元素占五個(gè)字節(jié),將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中,則元素A5,5的地址是(      )。A: 1175   

5、0;        B: 1180            C: 1205            D: 12107、已知廣義表LS(a,b,c),(d,e,f),運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是(     )A: head(tail(LS) &

6、#160;                    B: tail(head(LS)C: head(tail(head(tail(LS)           D: head(tail(tail(head(LS)8、某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪(fǎng)問(wèn)順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪(fǎng)問(wèn)順序是dgbaechf,則其后

7、序遍歷的結(jié)點(diǎn)訪(fǎng)問(wèn)順序是( )。A: bdgcefha B: gdbecfha C: bdgaechf D: gdbehfca 9、在一個(gè)無(wú)向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的( )倍。 A: 1/2 B: 1 C: 2D:410、設(shè)串s1=ABCDEFG,s2=PQRST,函數(shù)con (x,y)返回x和y串的連接串,subs(s,i,j)返回串s的從序號(hào)i的字符開(kāi)始的j個(gè)字符組成的子串,len(s)返回串s的長(zhǎng)度,則con (subs (s1,2,len (s2), subs (s1,len (s2),2)的結(jié)果串是( )。A: BCDEF B: BCDEFGC:BCPQRST D:BCD

8、EFEF得分 三、應(yīng)用題(每小題8分,共32分)1 一棵深度為h的滿(mǎn)m叉樹(shù)具有如下性質(zhì):第h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn),其余各層上每個(gè)結(jié)點(diǎn)都有m棵非空子樹(shù)。若按層次從上到下,每層從左到右的順序從1開(kāi)始對(duì)全部結(jié)點(diǎn)編號(hào),試計(jì)算:(1)第k層結(jié)點(diǎn)數(shù)(1kh)。(2)整棵樹(shù)結(jié)點(diǎn)數(shù)。(3)編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)。(4)編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)(若有)的編號(hào)。 答 題 勿 超 裝 訂 線(xiàn)-裝-訂-線(xiàn)-2已知圖G的鄰接表如圖1所示,請(qǐng)寫(xiě)出:(1)其從頂點(diǎn)v1出發(fā)的深度有限搜索序列;(2)其從頂點(diǎn)v1出發(fā)的廣度優(yōu)先搜索序列。v1v2v3v4 v5v6 V2V5V4 v3V5 V4V6V3 V6 圖1

9、圖G的鄰接表3、 以關(guān)鍵碼序列(503,087,512,061,908,170,897,275,653,426),為例,手工執(zhí)行快速排序排序算法,寫(xiě)出每一趟排序結(jié)束時(shí)的關(guān)鍵碼狀態(tài): 答 題 勿 超 裝 訂 線(xiàn)-裝-訂-線(xiàn)-4使用哈希函數(shù)H(key)=key % 11,把一個(gè)整數(shù)值轉(zhuǎn)換成哈希表下標(biāo),現(xiàn)要把數(shù)據(jù)1、13、12、34、38、33、27、22插入到哈希表(表1)中。(1)使用線(xiàn)性探測(cè)再散列法構(gòu)造哈希表,請(qǐng)?jiān)诒?所示的哈希表中與哈希地址對(duì)應(yīng)的位置上,填寫(xiě)出相應(yīng)的關(guān)鍵字值和元素插入時(shí)的探查次數(shù)。(2)假設(shè)查找每個(gè)元素的概率相同,求出查找成功時(shí)的平均查找長(zhǎng)度。表1哈希地址0123456789

10、10關(guān)鍵字值探查次數(shù)得分四、算法閱讀題(每小題9分,共18分)1、完成二叉樹(shù)按層遍歷的算法。void leveltravel ( struct treenode *bt) struct treenode *p,*an; int rear=front = -1; p=bt; rear =_; arear=p; while (rear != front) front = _; p=afront; printf(“%c”,p->data);If ( p->left !=null) rear =(rear +1)% n arear= _; If (p->right!= null) r

11、ear = (rear +1)%n ; arear=_; 2、下面算法是對(duì)直接插入排序算法的改進(jìn),請(qǐng)?zhí)顚?xiě)完整void weizhisort(struct node r n+1,int n) int low,high,mid,j,i; for(i=2;i<=n;i+) r0=ri; low=_; high=_; while(low<=high) mid=(low+high)/2; if(r0.key<rmid.key) _; else low=mid+1; for(j=i-1;j>=low;j-) rj+1=rj; rlow=r0; 五、算法設(shè)計(jì)題(每小題10分,共20分)1、 已知二叉樹(shù)中的結(jié)點(diǎn)類(lèi)型BinTreeNode定義為:struct BinTreeNodeElemType data;BinTreeNode *left,*right;其中data為結(jié)點(diǎn)值域,left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。請(qǐng)寫(xiě)一函數(shù),功能是返回二叉樹(shù)BT中值

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論