算法與數(shù)據(jù)結構C卷答案

2009–2010學年第1學期期末考試試卷（C卷）開課學院：數(shù)計學院課程名稱：算法與數(shù)據(jù)結構考試形式：閉卷所需時間：120分鐘題號一二三四五六七八總分得分評卷人注意事項：1、教師出題時請勿超出邊界虛線；2、學生答題前將密封線外的內容填寫清楚，答題不得超出密封線；3、答題請用藍、黑鋼筆或圓珠筆。一、選擇題（每小題2分，共計20分）1.計算機算法指的是（C）A．計算方法B.排序方法C.解決問題的步驟序列D.調度方法2．線性表是具有n個（B）的有限序列（n>0）。A．字符B．數(shù)據(jù)元素C．數(shù)據(jù)項D．信息項3．設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用(D)最節(jié)省時間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結點的雙循環(huán)鏈表4.一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（B）。A.不確定B.n-i+1C.iD.n-i5.用不帶頭結點的單鏈表存儲隊列時,其隊頭指針指向隊頭結點,其隊尾指針指向隊尾結點，則在進行刪除操作時(D)。A．僅修改隊頭指針B.僅修改隊尾指針C.隊頭、隊尾指針都要修改D.隊頭,隊尾指針都可能要修改6.設樹T的度為4，其中度為1，2，3和4的結點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（D）A．5B．6C．7D．87.下面關于二分查找的敘述正確的是(C)A.表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B.表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型C.表必須有序，且表只能以順序方式存儲D.表必須有序，而且只能從小到大排列8.一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：(B)。A.0B.1C.2D.不確定9．某內排序方法的穩(wěn)定性是指(D)。A．該排序算法不允許有相同的關鍵字記錄B．該排序算法允許有相同的關鍵字記錄C．平均時間為0（nlogn）的排序方法D．以上都不對10．圖中有關路徑的定義是（A）。A．由頂點和相鄰頂點序偶構成的邊所形成的序列B．由不同頂點所形成的序列C．由不同邊所形成的序列D．上述定義都不是二、填空題（每空1分，共計10分）1.下面程序段的時間復雜度為__O(n)______。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;2.已知指針p指向單鏈表L中的某結點，則刪除其后繼結點的語句是：_u=p->next;p->next=u->next;free(u);3.一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是__312_____。4.順序棧用data[1..n]存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是___data[++top]=x；____。5.設循環(huán)隊列存放在向量sq.data[0:M]中，若用犧牲一個單元的辦法來區(qū)分隊滿（設隊尾指針sq.rear）,則隊滿的條件為_(sq.rear+1)%(M+1)==sq.front；。6．在完全二叉樹中，編號為i和j的兩個結點處于同一層的條件是__?log2i?=?log2j?____。7.順序查找n個元素的順序表，當使用監(jiān)視哨查找失敗，則比較關鍵字的次數(shù)為__n+1。。8．具有N個結點的二叉樹，采用二叉鏈表存儲，共有__N+1____個空鏈域。9．若不考慮基數(shù)排序，則在排序過程中，主要進行的兩種基本操作是關鍵字的__比較____和記錄的移動。10．N個頂點的連通圖的生成樹含有__N-1____條邊。三、判斷題（每小題2分，共計20分）1.數(shù)據(jù)結構的抽象操作的定義與具體實現(xiàn)有關。(×)2.順序存儲結構的主要缺點是不利于插入或刪除操作。(√)3.棧是實現(xiàn)過程和函數(shù)等子程序所必需的結構。（√）4.棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。（√）5.二叉樹是度為2的有序樹。(×)6．對一棵二叉樹進行層次遍歷時，應借助于一個棧。(×)7.空字符串是只包含“空白”字符的字符串。（×）8.折半查找法的查找速度一定比順序查找法快。（×）9．當待排序的元素很大時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復雜度的主要因素。（√）10．在n個結點的無向圖中，若邊數(shù)大于n-1,則該圖必是連通圖。（×）四、應用題（每小題5分，共計30分）1、畫出下圖采用鄰接表表示的示意圖。答：2、已知一棵二叉樹的中根周游結點序列為DGBAECHIF，后根周游結點序列為GDBEIHFCA，試畫出該二叉樹并寫出其先根周游序列。先根周游序列：ABDGCEFHI3、已知元素個數(shù)為12的字典，其元素集合為：{jan,feb,mar,apr,may,june,july,aug,sep,oct,nov,dec}試按元素的次序依次插入一棵初始時為空的二叉排序樹，請畫出插入完成之后的二叉排序樹，并求其在等概率情況下檢索成功的平均檢索長度。AVL=(1*1+2*2+3*3+4*3+5*2+6*1)/12=42/12=3.5(次)4、設有一組元素的關鍵碼集為：05,10,18,25,27,32,41,51,68,73,99,試給出采用二分法檢索關鍵碼9的具體過程。答：step1:low=1,high=11,mid=(1+11)/2=6,key=32>10step2:high=mid-1=5,mid=(1+5)/2=3,key=18>10step3:high=mid-1=2,mid=(1+2)/2=1,key=05<10step4:low=mid+1=2,mid=(2+2)/2=2,key=10>9step5:high=mid-1=1,high<low查找失敗5、對于初始排序碼[49,38,65,97,76,13,27,49’初始排序碼：[49,38,65,97,76,13,27,49’i=1[273813]49[76976549’i=2[13]27[38]49[76976549’i=31327[38]49[76976549’i=413273849[76976549’i=513273849[49’i=61327384949’i=71327384949’最后1327384949’6、采用Kruskal算法，畫出下圖最小生成樹的生成過程。答：五、算法與編程（每小題10分，共計20分）1、寫一算法，在帶頭結點的單鏈表llist中，p所指結點前面插入值為x的新結點，并返回插入成功與否的標志。注：單鏈表數(shù)據(jù)結構定義如下：structNode;/*結點類型*/typedefstructNode*Pnode;/*結點指針類型*/structNode{/*結點結構*/DataTypeinfo;/*數(shù)據(jù)域*/Pnodelink;/*指針域/}typedefstructNode*LinkList;/*單鏈表類型*/答：intinsertPre_link(LinkListllist,Pnodep,DataTypex){Pnodep1;if(llist==NULL)return0;p1=llist;/*尋找p所指結點的前趨結點*/while(p1!=NULL&&p1->link!=p)p1=p1->link;if(p1==NULL)return0;PNodeq=(PNode)malloc(sizeof(structNode));if(q==NULL){printf(“OVERFLOW!\n”);return0;}q->info=x;q->link=p1->link;p1->link=q;return1;}2、試給出二叉樹鏈接存儲方式的描述，并寫一算法計算給定二叉樹中葉子結點數(shù)（給定二叉樹采用鏈接存儲方式）。答：structBinTreeNode;/*二叉中結點*/typedefstructBinTreeNode*PbinTreeNode;/*結點的指針類型*/structBinTreeNode{DataTypeinfo;/*數(shù)據(jù)域*/PbinTreeNodellink;/*左指針*/PbinTreeNoderlink;/*右指針*/};typedefstructBinTreeNode*BinTree;typedefBinTree*P