安徽大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷2010A

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中值