數(shù)據(jù)結(jié)構(gòu)期末模擬試題01(有答案)

吉首大學試題庫課程測試試題〔卷〕----------------------以下為教師填寫--------------------I、命題院〔部〕：數(shù)學與計算機科學學院II、課程名稱：數(shù)據(jù)結(jié)構(gòu)III、測試學期：20－20學年度第學期IV、測試對象：學院專業(yè)級班V、問卷頁數(shù)〔A4〕：頁VI、答卷頁數(shù)〔A4〕：頁VII、考試方式：閉卷〔開卷、閉卷或課程小論文，請?zhí)顚懬宄砎III、問卷內(nèi)容：〔請老師在出題時安排緊湊，填空題象征性的留出一點空格，學生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號〕單項選擇題〔每題2分，共20分〕對一個算法的評價，不包括如下〔〕方面的內(nèi)容。A．健壯性和可讀性B．并行性C．正確性D．時空復雜度在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，那么執(zhí)行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;對線性表，在以下哪種情況下應(yīng)當采用鏈表表示？()A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變一個棧的輸入序列為123，那么以下序列中不可能是棧的輸出序列的是()A.231 B.321C.312 D.123AOV網(wǎng)是一種〔〕。A．有向圖B．無向圖C．無向無環(huán)圖D．有向無環(huán)圖采用開放定址法處理散列表的沖突時，其平均查找長度〔〕。A．低于鏈接法處理沖突B.高于鏈接法處理沖突C．與鏈接法處理沖突相同D．高于二分查找假設(shè)需要利用形參直接訪問實參時，應(yīng)將形參變量說明為〔〕參數(shù)。A．值B．函數(shù)C．指針D．引用在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的〔〕。A．行號B．列號C．元素值D．非零元素個數(shù)快速排序在最壞情況下的時間復雜度為〔〕。A．O(log2n)B．O(nlog2n)C．0(n)D．0(n2)從二叉搜索樹中查找一個元素時，其時間復雜度大致為()。A.O(n)B.O(1)C.O(log2n)D.O(n2)運算題〔每題6分，共24分〕數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。當結(jié)點之間存在M對N〔M：N〕的聯(lián)系時，稱這種結(jié)構(gòu)為_____________________。隊列的插入操作是在隊列的_________進行，刪除操作是在隊列的__________進行。當用長度為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？眨敲幢硎緱M的條件是_____________________。對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標i從0到7，列下標j從0到3，那么二維數(shù)組W的數(shù)據(jù)元素共占用＿_____＿個字節(jié)。W中第6行的元素和第4列的元素共占用＿_______＿個字節(jié)。假設(shè)按行順序存放二維數(shù)組W，其起始地址為100，那么二維數(shù)組元素W[6，3]的起始地址為＿________＿。廣義表A=(a,(a,b),((a,b),c)),那么它的深度為____________，它的長度為____________。二叉樹是指度為2的____________________樹。一棵結(jié)點數(shù)為N的二叉樹，其所有結(jié)點的度的總和是_____________。對一棵二叉搜索樹進行中序遍歷時，得到的結(jié)點序列是一個______________。對一棵由算術(shù)表達式組成的二叉語法樹進行后序遍歷得到的結(jié)點序列是該算術(shù)表達式的__________________。對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_____________個，其中_______________個用于指向孩子，_________________個指針是空閑的。假設(shè)對一棵完全二叉樹從0開始進行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點存儲到A[0]中。其余類推，那么A[i]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。當待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_______________排序；當待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用________________________排序。運算題〔每題6分，共24分〕一個65稀疏矩陣如下所示，試：寫出它的三元組線性表；給出三元組線性表的順序存儲表示。設(shè)有一個輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。對于圖6所示的有向圖假設(shè)存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出：(1)從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2)從頂點②出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；一個圖的頂點集V和邊集E分別為：圖6V={1,2,3,4圖6E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};假設(shè)存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。閱讀算法〔每題7分，共14分〕intPrime(intn){inti=1;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;}指出該算法的功能；該算法的時間復雜度是多少？寫出下述算法的功能：voidAJ(adjlistGL,inti,intn){ QueueQ; InitQueue(Q); cout<<i<<''; visited[i]=true; QInsert(Q,i);while(!QueueEmpty(Q)){ intk=QDelete(Q); edgenode*p=GL[k]; while(p!=NULL) { intj=p->adjvex; if(!visited[j]){ cout<<j<<''; visited[j]=true; QInsert(Q,j); } p=p->next; } }}算法填空〔共8分〕如下為二分查找的非遞歸算法，試將其填寫完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0;inthigh=n-1;while(low<=high){intmid=_______________________________；if(K==A[mid].key)returnmid;//查找成功，返回元素的下標 elseif(K<[mid].key)______________________________________;//在左子表上繼續(xù)查找 else__________________________________;//在右子表上繼續(xù)查找}return-1;//查找失敗，返回-1}編寫算法〔共8分〕HL是單鏈表的頭指針，試寫出刪除頭結(jié)點的算法。ElemTypeDeleFront(LNode*&HL)參考答案單項選擇題〔每題2分，共20分〕1.B2.A3.B4.C5.D6.B7.D8.A9.D10.C填空題〔每空1分，共26分〕聯(lián)系圖〔或圖結(jié)構(gòu)〕尾首top==0O〔1〕O〔n〕128441083365565515132-145-2515637圖7有序序列后綴表達式〔或逆波蘭式〕2nn-1n+12i+12i+2(i-1)/2開放定址法鏈接法快速歸并運算題〔每題6分，共24分〕〔1〕((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)〔2〕三元組線性表的順序存儲表示如圖7示。圖8如圖8圖8DFS：BFS：拓樸排序為：4365721閱讀算法〔每題7分，共14分〕(1)判斷n是否是素數(shù)〔或質(zhì)數(shù)〕〔2〕O〔〕功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表G