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

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

2、常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變4.一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是(C)A.231B.321C.312D.1236.若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（D）參數(shù)。A值B函數(shù)C指針D引用8.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（A）。A行號(hào)B列號(hào)C元素值D非零元素個(gè)數(shù)10.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(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對(duì)N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為__圖__。2.隊(duì)列的插入操作是在隊(duì)列的___尾_進(jìn)行，刪除操作是在隊(duì)列的_首_進(jìn)行。3.當(dāng)用長度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則表示棧滿的條件是___top==0___(要超出才為滿)

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

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

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

7、__________兩種。12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用________________________排序。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.開放定