算法與數(shù)據(jù)結(jié)構(gòu)C卷答案

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