清華大學(xué)數(shù)據(jù)結(jié)構(gòu)試題及答案

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

2、存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變4.4.一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是()A.231B.321C.312D.1235.5.AOV網(wǎng)是一種（）。A有向圖B無向圖C無向無環(huán)圖D有向無環(huán)圖6.6.采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（）。A低于鏈接法處理沖突B.高于鏈接法處理沖突C與鏈接法處理沖突相同D高于二分查找7.7.若需要利用形

3、參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（）參數(shù)。A值B函數(shù)C指針D引用8.8.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（）。A行號(hào)B列號(hào)C元素值D非零元素個(gè)數(shù)9.9.快速排序在最壞情況下的時(shí)間復(fù)雜度為（）。AO(log2n)BO(nlog2n)C0(n)D0(n2)10.10.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為()。A.O(n)B.O(1)C.O(log2n)D.O(n2)二、二、二、二、運(yùn)算題（

4、每題運(yùn)算題（每題6分，共分，共24分）分）1.1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_____________________。2.2.隊(duì)列的插入操作是在隊(duì)列的___尾______進(jìn)行，刪除操作是在隊(duì)列的____首______進(jìn)行。3.3.當(dāng)用長度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則表示棧滿的條件是___top==0___(要超出才為滿)

5、_______________。4.4.對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_________，在表尾插入元素的時(shí)間復(fù)雜度為____________。5.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ù)元素共占用＿_(dá)____＿個(gè)字節(jié)。W中第6行的元素和第4列的元素共占用＿_(dá)______＿個(gè)字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元

6、素W[6，3]的起始地址為＿_(dá)_______＿。6.6.廣義表A=(a(ab)((ab)c))則它的深度為____________，它的長度為____________。7.7.二叉樹是指度為2的____________________樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)點(diǎn)的度的總和是_____________。8.8.對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)______________。對(duì)一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行

7、后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的__________________。(1)(1)指出該算法的功能；(2)(2)該算法的時(shí)間復(fù)雜度是多少？2.2.寫出下述算法的功能：voidAJ(adjlistGLintiintn)QueueQInitQueue(Q)coutadjvexif(!visited[j])coutnext五、五、五、五、算法填空（共算法填空（共8分）分）如下為二分查找的非遞歸算法，試將其填寫完整。IntBinsch(E

8、lemTypeA[]intnKeyTypeK)intlow=0inthigh=n1while(low=high)int=_______________________________；if(K==A[].key)return查找成功，返回元素的下標(biāo)elseif(K[].key)______________________________________在左子表上繼續(xù)查找else______________________________