數(shù)據(jù)結(jié)構(gòu)與算法分析—期末復(fù)習(xí)題及答案

1、單選題（每題單選題（每題2分，共分，共20分）分）1.對一個算法的評價，不包括如下（B）方面的內(nèi)容。A健壯性和可讀性B并行性C正確性D時空復(fù)雜度2.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行(A)。A.pnext=HLnextHLnext=pB.pnext=HLHL=pC.pnext=HLp=HLD.HL=ppnext=HL3.對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？(B)A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)

2、常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變4.一個棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是(C)A.231B.321C.312D.1236.若需要利用形參直接訪問實(shí)參時，應(yīng)將形參變量說明為（D）參數(shù)。A值B函數(shù)C指針D引用8.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點(diǎn)都具有相同的（A）。A行號B列號C元素值D非零元素個數(shù)10.從二叉搜索樹中查找一個元素時，其時間復(fù)

3、雜度大致為(C)。A.O(n)B.O(1)C.O(log2n)D.O(n2)二、二、運(yùn)算題（每題運(yùn)算題（每題6分，共分，共24分）分）1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_聯(lián)系。當(dāng)結(jié)點(diǎn)之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為__圖__。2.隊(duì)列的插入操作是在隊(duì)列的___尾_進(jìn)行，刪除操作是在隊(duì)列的_首_進(jìn)行。3.當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top==N表示棧空，則表示棧滿的條件是___top==0___(要超出才為滿)

4、_______________。4.對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為___O（1）__，在表尾插入元素的時間復(fù)雜度為___O（n）___。5.設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到3，則二維數(shù)組W的數(shù)據(jù)元素共占用＿128__個字節(jié)。W中第6行的元素和第4列的元素共占用__44_個字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W[6，3]的起始地

5、址__108_。7.二叉樹是指度為2的___有序___樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)點(diǎn)的度的總和是___n1____。8.對一棵二叉搜索樹進(jìn)行中序遍歷時，得到的結(jié)點(diǎn)序列是一個_有序序列__。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的__后綴表達(dá)式____。9.對于一棵具有n個結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_____________個，其中_______________個用于指向孩子，

6、_________________個指針是空閑的。10.若對一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點(diǎn)存儲到A[0]中。其余類推，則A[i]元素的左孩子元素為________右孩子元素為_______________，雙親元素為____________。11.在線性表的散列存儲中，處理沖突的常用方法有________________________和___________________

7、__________兩種。12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用________________________排序。Q(Qi)while(!QueueEmpty(Q))intk=Q(Q)edgenodep=GL[k]while(p!=NULL)intj=padjvexif(!visited[j])coutnex

8、t五、五、算法填空（共算法填空（共8分）分）如下為二分查找的非遞歸算法，試將其填寫完整。IntBinsch(ElemTypeA[]intnKeyTypeK)intlow=0inthigh=n1while(low=high)int=_______________________________；if(K==A[].key)return查找成功，返回元素的下標(biāo)elseif(K[].key)__________________________

9、____________在左子表上繼續(xù)查找else__________________________________在右子表上繼續(xù)查找return1查找失敗，返回1六、六、編寫算法（共編寫算法（共8分）分）HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。ElemTypeDeleFront(LNode&HL)參考答案1.7.有序n12.8.有序序列后綴表達(dá)式（或逆波蘭式）3.9.2nn1n14.10.2i12i2(i1)25.11.開放定