數(shù)據(jù)結(jié)構(gòu)試題5

GDOU-B-11-302廣東海洋大學(xué)2008——2009學(xué)年第一學(xué)期班;級(jí)::!11i1《數(shù)據(jù)結(jié)構(gòu)》課程試題、里壬口口^考試05卷□閉卷課程號(hào)：1620068口！!口i1ii姓￡名密:1題號(hào)一二三四五六七八九十總分閱卷教師各題分?jǐn)?shù)201510202015100實(shí)得分?jǐn)?shù)一、填空題（10x2’=20分）:1、數(shù)據(jù)的邏輯結(jié)構(gòu)是指（）元素之間（）關(guān)系的整體。'2、抽象數(shù)據(jù)類型是一個(gè)（）結(jié)構(gòu)及定義在該結(jié)構(gòu)上的一組（）的總稱。:3、一個(gè)非空的線性表可記為L=（）。學(xué)：4、入橙時(shí)，橙頂指針（）1,出橙時(shí)，橙頂指針（）1。::5、稀疏矩陣的壓縮存儲(chǔ)有（）和（）兩種存儲(chǔ)。封6、廣義表（（a）,（（（b）,c））,（d））的長度為（），深度為（）。'7、樹中各結(jié)點(diǎn)度的（）稱為該樹的（）。:8、鄰接表是一種（）與（）相結(jié)合的存儲(chǔ)方法。:9、一棵包含50個(gè)關(guān)鍵碼的3階B-樹，其最小高度為（），最大高度為（）。:10、主程序第一次調(diào)用遞歸函數(shù)被稱為（），遞歸函數(shù)自己調(diào)用自己被稱為（），:它們都需要利用（）保存調(diào)用后的（）地址。二、選擇題（10x2’=20分）1、數(shù)據(jù)的邏輯結(jié)構(gòu)可形式地用一個(gè)二元組B=（D,R）來表示，其中D是（）的集合。A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)對(duì)象C.數(shù)據(jù)元素D.數(shù)據(jù)類型2、算法指的是（）。A.計(jì)算機(jī)程序B.解決問題的計(jì)算方法C.排序算法D.解決問題的有限運(yùn)算序列3、下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（）A.存儲(chǔ)密度大B-插入運(yùn)算方便C.刪除運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示4、指針的全部作用就是（）A.指向某常量B.指向某變量C.指向某結(jié)點(diǎn)D.存儲(chǔ)某數(shù)據(jù)5、鏈表不具有的特點(diǎn)是（）A-插入、刪除不需要移動(dòng)元素B.可隨機(jī)訪問任一元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性長度成正比6、在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（）。As->link=p;p->link=s;Bs->link=p->link;p->link=s;Cs->link=p->link;p=s;Dp->link=s;s->link=p;7、設(shè)串sl="DataStructureswithJava”,s2="it”，則子串定位函數(shù)index（s1,s2）的值為（）A.15B.16C.17D.188、以下說法錯(cuò)誤的是（）A.樹形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)最多只有一個(gè)直接前趨8、樹形結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼。.樹形結(jié)構(gòu)可以表達(dá)（組織）更復(fù)雜的數(shù)據(jù)。.樹形結(jié)構(gòu)是一種"分支層次"結(jié)構(gòu)9、判斷一個(gè)有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用（）A.求關(guān)鍵路徑的方法B.求最短路徑的Dijkstra方法C.深度優(yōu)先遍歷算法D.廣度優(yōu)先遍歷算法10、在用Dijkstra算法求解帶權(quán)有向圖的最短路徑問題時(shí)，要求圖中每條邊所帶的權(quán)值必須是（）。A-非零B.非整C.非負(fù)D.非正三、判斷題（10x2’=20分）1、數(shù)據(jù)是計(jì)算機(jī)加工處理的對(duì)象。（）2、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)都是依賴于計(jì)算機(jī)的。（）3、樹的遍歷會(huì)得到一種線性結(jié)構(gòu)，故非線性結(jié)構(gòu)和線性結(jié)構(gòu)可以相互轉(zhuǎn)換。（）4、單鏈表從任意結(jié)點(diǎn)出發(fā)都能訪問到所有結(jié)點(diǎn)。（）5、隊(duì)列是一種先進(jìn)后出的線性表。（）6、串的長度是指串中包含字符的個(gè)數(shù)。（）7、樹的最大特點(diǎn)是一對(duì)多的層次結(jié)構(gòu)。（）8、樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹的結(jié)點(diǎn)的最大度數(shù)為2。（）9、圖的最小生成樹是唯一的。（）10、按深度優(yōu)先搜索遍歷圖時(shí)，與始結(jié)點(diǎn)相鄰的結(jié)點(diǎn)總是先于不于始結(jié)點(diǎn)相鄰的結(jié)點(diǎn)訪問。（）四、算法閱讀題（4x5’=20分）閱讀下面程序，在指定處填空。1、判斷隊(duì)列是否為空template<classT>boolLinkQueue<T>::Empty（）（if（front==（1））return（2）;elsereturn（3）;2、刪除棧頂元素template<classT>TLinkStack<T>::Pop()(Node<T>*p;intx;if(top==(1))throw〃下溢〃;x=top->data;//暫存棧頂元素p=(2);top=top->next;//將棧頂結(jié)點(diǎn)摘鏈delete(3);returnx;}閱讀下面程序，指出其算法的功能。3、template<classT>voidALGraph<T>::DeleteVex(inti){if(i<0||i>MaxSize)throw"位置”；〃頂點(diǎn)輸入錯(cuò)誤則拋出異常intk;for(k=0;k<vertexNum;k++)〃刪掉入度邊if(k!=i)DeleteArc(k,i);ArcNode*s;//生成一個(gè)邊表結(jié)點(diǎn)sif(adjlist[i].firstedge!=NULL){ArcNode*s;s=adjlist[i].firstedge->next;while(s!=NULL){ArcNode*p;p=s;adjlist[i].firstedge->next=s->next;s=s->next;deletep;〃刪除p結(jié)點(diǎn)}s=adjlist[i].firstedge;adjlist[i].firstedge=NULL;deletes;}for(k=i;k<vertexNum;k++){adjlist[k]=adjlist[k+1];〃存儲(chǔ)頂點(diǎn)信息}vertexNum--;//頂點(diǎn)數(shù)減1for(k=0;k<vertexNum;k++)if(adjlist[k].firstedge!=NULL){s=adjlist[k].firstedge;〃將結(jié)點(diǎn)s插入到結(jié)點(diǎn)i的邊表的表頭while(s!=NULL){if(s->adjvex>i)〃搜索i結(jié)點(diǎn)s->adjvex--;s=s->next;}}}4、template<classT>TLinkList::Delete(inti){p=first;j=0;〃工作指針p初始化while(p&&j<i-1)〃查找第i-1個(gè)結(jié)點(diǎn){p=p->next;j++;}if(!p||!p->next)throw"位置”；〃結(jié)點(diǎn)p不存在或結(jié)點(diǎn)p的后繼結(jié)點(diǎn)不存在else{q=p->next;x=q->data;〃暫存被刪結(jié)點(diǎn)p->next=q->next;〃摘鏈deleteq;returnx;}}五、算法設(shè)計(jì)題(25’=10分)1、已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個(gè)循環(huán)鏈表，使每個(gè)循環(huán)鏈表中只含同一類字符。2、設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。六、綜合題(10分)一最小最大堆(minmaxheap)是一種特定的堆，其最小層和最大層交替出現(xiàn)，根總是處于最小層。最小最大堆中的任一結(jié)點(diǎn)的關(guān)鍵字值總是在以它為根的子樹中的所有元素中最小(或最大)。如圖所示為一最小最大堆；畫出在上圖中插入關(guān)鍵字為5的結(jié)點(diǎn)后的最小最大堆。畫出在上圖中插入關(guān)鍵字為80的結(jié)點(diǎn)后的最小最大堆；編寫一算法實(shí)現(xiàn)最小最大堆的插入功能。假定最小最大堆存放在數(shù)組中，關(guān)鍵字為整數(shù)。［提示］從插入位置進(jìn)行調(diào)整，調(diào)整過程由下到上。首先根據(jù)元素個(gè)數(shù)求出插入元素所在層次數(shù)，以確定其插入層是最大層還是最小層。若插入元素在最大層，則先比較