2007-09(2)數(shù)據(jù)結(jié)構(gòu)期末試卷(B)

--#-汕頭職業(yè)技術(shù)學(xué)院TOC\o"1-5"\h\z2007-2009學(xué)年第二學(xué)期期末試卷（ B）課程名稱數(shù)據(jù)結(jié)構(gòu) 學(xué)分_題人何漢陽審題人r。系校區(qū)計算機系班級學(xué)號姓名題號一二三四五六七八總分評卷入得分TOC\o"1-5"\h\z一、判斷題（每小題1分，共15分）1、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。（ ）2、分配給單鏈表的內(nèi)存地址必須是連續(xù)的。（ ）3、在有n個元素的順序表中，刪除任意一個元素所需移動結(jié)點的平局次數(shù)為n-1。（ ）4、對于單循環(huán)鏈表，從表中任一結(jié)點都能掃描表中的全部結(jié)點。（ ）5、棧是一種對進棧、出棧操作總次數(shù)做了限制的線性表。（ ）6、無論是順序隊列還是鏈接隊列，插入和刪除元素運算的時間復(fù)雜度都是0（1）。（ ）7、表示稀疏矩陣的三元組順序中，各元素的排列順序與矩陣元素值的大小有關(guān)。（ ）8、完全二叉樹中只有度為0和度為2的結(jié)點。（）9、已知二叉樹的先序序列和后序序列，并不能唯一確定這棵二叉樹。（ ）10、哈夫曼樹中，權(quán)值較大的葉結(jié)點一般都離根結(jié)點較遠。（ ）11、如果表示有向圖的鄰接矩陣是對稱矩陣，則該有向圖一定是完全有向圖。（ ）12、有向圖的遍歷不可采用廣度優(yōu)先搜索方法。（ ）13、順序表和單鏈表表示的有序表均可使用二分查找法來提高查找速度。（ ）14、只有在記錄的關(guān)鍵字的初始狀態(tài)為逆序排列的情況下，直接選擇排序過程中元素的移動次數(shù)才會達到最大值。（ ）15、內(nèi)排序中的快速排序方法，在任何情況下均可得到最快的排序效果。（ ）二、選擇題（每小題2分，共40分）1． 中_任_何_兩_個_結(jié)點之間都沒有邏輯關(guān)系。集合 圖狀結(jié)構(gòu) 樹型結(jié)構(gòu) 線性結(jié)構(gòu)2．計算機算法指的是 。 計算方法 調(diào)度方法排序方法 解決某一問題的有限運算序列3．下面 的_時_間_復(fù)_雜_性_最好，即執(zhí)行時間最短。.在一個長度為的順序表中，向第個元素1W 位置插入一個新元素時，需要從后向前依次后移 個_元_素_。5對順序存儲的線性表，設(shè)其長度為，在任何位置上插入或刪除操作都是等概率的，插入一個元素時平均移動表中的 個_元_素_。TOC\o"1-5"\h\z/ /6．單鏈表要求內(nèi)存中可用存儲單元的地址 。必須是連續(xù)的 一定是不連續(xù)的部分地址必須是連續(xù)的 可以是連續(xù)的，也可以是不連續(xù)的7在一個單鏈表中，若要刪除指針所指向結(jié)點的后繼結(jié)點，則執(zhí)行 。8．若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用___存_儲方式最節(jié)省時間。單鏈表 雙鏈表 單循環(huán)鏈表 帶頭結(jié)點的雙循環(huán)鏈表9．采用鏈接方式存儲線性表的優(yōu)點是 。 便于隨機存取 花費的存儲空間較順序存儲少便于插入和刪除操作 數(shù)據(jù)元素的物理順序和邏輯順序相同10．在下面棧的基本運算中，不是加工型運算的是 。___初始化 進棧 退棧 判棧空1．1在順序棧中進行退棧操作時， 。 誰先誰后都可以 先移動棧頂指針，后取出元素不分先后，同時進行 先取出元素，后移動棧頂指針.假設(shè)一個棧的輸入序列為AB,DE則下列序列中不可能是棧的輸出序列的是 _.在由個單元組成的順序存儲的循環(huán)隊列中，假定和分別為隊頭指針和隊尾指針，則判斷隊滿的條件是 。___十% % %1.4樹最適合于表示 。 有序數(shù)據(jù)元素 無序數(shù)據(jù)元素元素之間無聯(lián)系的數(shù)據(jù) 元素之間具有分支層次關(guān)系的數(shù)據(jù).在一棵深度為的完全二叉樹中，所含結(jié)點個數(shù)不小于 _

6．在下列存儲形式中，6．在下列存儲形式中，雙親表示法孩子兄弟表示法_不_是_樹_的存儲形式。順序存儲表示孩子鏈表表示法1．7對于長度為8的順序存儲結(jié)構(gòu)的有序表，若采用二分查找法查找，在等概率的情況下的平均查找長度為 的_值_除_以__8。.若對個元素進行直接插入排序，則進行第趟排序過程前，有序表中的元素個數(shù)為.在對個元素進行冒泡排序的過程中，第一趟排序至多需要進行 _對相鄰元素之間的交換。／A2)nB)n-1C)nD)n+l20.以下四種排序方法中，需要附加的內(nèi)存空間最大的是 。_插入排序 選擇排序 快度排序 歸并排序三、列表說明用算法求解下圖最小生成樹的生成過程。(分)四、試編寫在帶頭結(jié)點的單鏈表中刪除（一個）最小值結(jié)點的“高效”算法。（10分）五、關(guān)鍵碼序列為47,7,29,11,16,92,，2哈2希,函數(shù)8為,H3（,k）%5=畫出其開散列表處理沖突示意圖，并計算查找成功的平均查找長度。（10分）。六、寫出順序表上將監(jiān)視哨設(shè)在高端的順序查找算法子程序，并要寫出在 主函數(shù)中調(diào)用的過程語句。查找表的結(jié)構(gòu)定義同課本一致，查找表的元素值和長度通過鍵盤輸入。（10分）。2007-2009學(xué)年第二學(xué)期期末試卷（B）答案課程名稱數(shù)據(jù)結(jié)構(gòu)擬題人何漢陽、判斷題（每小題1分，共15分）?、JXXJX?0xxxvx、xxxjx、選擇題（每小題2分，共40分）1?5、ADCDA 6?10、DCDCD11?15、DBADD16?20、DBCBDU={0},V-U={1,2,3,4,5,6}Adjvex/000000k=5Lowcost028ggg10g(0,5)U={0,5},V-U={1,2,3,4,6}Adjvex/000500k=4Lowcost028gg250g(5,4)U={0,5,4},V-U={1,2,3,6}Adjvex/004504k=3Lowcost028g220024(4,3)U={0,5,4,3},V-U={1,2,6}Adjvex/034503k=2Lowcost0281200018(3,2)U={0,5,4,3,2},V-U={1,6}Adjvex/234503k=1Lowcost016000018(2,1)U={0,5,4,3,2,1},V-U={6}Adjvex/234501k=6Lowcost00000014(1,6)U={0,5,4,3,2,1,6},V-U={}三、解：（1、分）設(shè)從頂點0出發(fā)四、解：(10分)voidDelMinNode(LINKLIST*head){LINKLIST*p,*q,*r; 為指向最小值結(jié)點的前一個結(jié)點p=head->next;q=head;r=q;/假/設(shè)第一個值結(jié)點最小while(p<>NULL){q=p;p=p->next;if(p->data<r->next->data)r=q;}if(r->next->next==NULL)/若/最小值是尾結(jié)點{p=r->next;r->next=NULL;free(p);}else{p=r->next;r->next=p->next;free(p);}00288881081280168881428160128883881202281848882202524510888250868148182480五、解：（10分）012345678910查找成功的平均查找長度 =（六、解：(10分)#include<stdio.h>#defineMAXSIZE100typedefstruct{intkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intseq_search(intk,SSTABLEst){intj=0;st.r[st.len].key=k;while(st.r[j].key!=k)j++;if(j<st.len)returnj+1;elsereturn0;}voidmain(){intk,i;SSTABLEst;printf("InputLen