信息學(xué)院2012年《數(shù)據(jù)結(jié)構(gòu)》筆試題及答案

信息學(xué)院考試試卷及參考答案信息學(xué)院考試試卷及參考答案2012學(xué)年第一學(xué)期

課程名稱：數(shù)據(jù)結(jié)構(gòu)一、填空殖(每空1分共20分)數(shù)據(jù)的物理結(jié)構(gòu)主要包括 和 兩種情況。設(shè)一棵完全二叉樹中有500個(gè)結(jié)點(diǎn)，則該二叉樹的深度為 ；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有 個(gè)空指針域。設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到 種不同的輸出序列。設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的 ，第i列上所有元素之和等于頂點(diǎn)i的 。設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有 個(gè)度數(shù)為1的結(jié)點(diǎn)。設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d,則e和d的關(guān)系為 遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列(填先序、中序或后序)。&設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較 次就可以斷定數(shù)據(jù)元素X是否在查找表中。不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第iTOC\o"1-5"\h\z個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為 ，右孩子結(jié)點(diǎn)的編號為 。設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為 。設(shè)有向圖G中有向邊的集合E={vl,2＞，＜2，3＞，＜1，4＞，＜4，2＞，＜4，3＞}，則該圖的一種拓?fù)湫蛄袨?。下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請?jiān)谙聞澗€處填上正確的語句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk){inti,j;j=i=k%p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=( )%m;if(i==j)return(-1);}if( )return(j);elsereturn(-1);}下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請?jiān)谙聞澗€處填上正確的語句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(t==0)return(0);elsewhile(t!=0)if(t-＞key==k) ;elseif(t-＞key＞k)t=t-＞lchild;else ;}二、計(jì)算題(每題10分，共30分)1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為［0..6］，假定選用的散列函數(shù)是H（K）=Kmod7,若發(fā)生沖突采用線性探查法處理，試：（1）計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表：' 0 1 2 3 4 5 62）求出在查找每一個(gè)元素概率相等情況下的平均查找長度。已知序列（10,18,4,3,6,12,1,9,18,8）請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。三、算法設(shè)計(jì)題（每題15分，共30分）1．設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。2.設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。參考答案一、填空題1.順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)2.9，5013.5出度，入度0e=d中序7O(1)i/2，2i+1(5，16，71，23，72，94，73)(1，4，3，2)13.j+1，hashtable[j].key==k14.return(t)，t=t->rchild第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)行二分查找時(shí)的查找長度不超過二叉判定樹的高度l+log2n。二、計(jì)算題H](22)=(1+1)mod7=2;H](22)=(1+1)mod7=2;?…沖突H2(22)=(2+1)mod7=3;2、H(36)=36mod7=1;H(15)=15mod7=1;....沖突H(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;?…沖突633615224034 5 6(1)01234 5 61+2+1+1+3 [”(2)ASL= =1.63、(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(處,18)1,(3,4,6),8,9,10,12,1K(18)(4,6),8,9,10,12,18,184,6,8,9,10,12,18,18三、算法設(shè)計(jì)題設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->next){for(q=p->next,s=q;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->