2014年9月份考試數(shù)據(jù)結(jié)構(gòu)第三次作業(yè)

1、20142014年9月份考試數(shù)據(jù)結(jié)構(gòu)第三次作業(yè)月份考試數(shù)據(jù)結(jié)構(gòu)第三次作業(yè)一、填空題（本大題共一、填空題（本大題共1010分，共分，共5小題，每小題小題，每小題2分）分）1.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的______和數(shù)據(jù)的______。2.在無(wú)頭結(jié)點(diǎn)的單鏈表中，第1個(gè)結(jié)點(diǎn)的地址存放在頭指針中，其他結(jié)點(diǎn)的存儲(chǔ)地址存放在______結(jié)點(diǎn)的next域中。3.為了實(shí)現(xiàn)逐層訪問(wèn)，算法中使用了一個(gè)______，以記憶正在訪問(wèn)的這一層和上一層的頂點(diǎn)，以便于向下一

2、層訪問(wèn)。4.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的______位置。5.弗洛伊德Floyd算法的時(shí)間復(fù)雜度為______。二、名詞解釋題（本大題共二、名詞解釋題（本大題共1010分，共分，共2小題，每小題小題，每小題5分）分）1.請(qǐng)解釋名詞“頭指針”2.請(qǐng)解釋名詞“目標(biāo)串”三、程序閱讀題（本大題共三、程序閱讀題（本大題共2020分，共分，共2小題，每小題小題，每小題1010分）分）1.指出下述程序段的功能是什么voidDemo2(Se

3、qStackSintm)設(shè)DataType為int型SeqStackTintiInitStack(while(!StackEmpty(S))if((i=Pop(S))!=m)Push(while(!StackEmpty(Push(Si)2.下述算法的功能是什么LinkListDemo(LinkListL)L是無(wú)頭結(jié)點(diǎn)單鏈表ListNodeQPif(LL=LnextP=Lwhile(Pnext)P=PnextPnext=QQnext=NU

4、LLreturnLDemo四、簡(jiǎn)答題（本大題共四、簡(jiǎn)答題（本大題共2020分，共分，共4小題，每小題小題，每小題5分）分）1.如何判別循環(huán)隊(duì)列的空和滿2.實(shí)際中，需根據(jù)不同的情況采用不同的哈希函數(shù)。通常，考慮的因素有那些？3.以關(guān)鍵字序列(265，301，751，129，937，863，742，694，076，438)為例，寫出執(zhí)行直接選擇排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。4.在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向

5、某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)p從相應(yīng)的鏈表中刪去若可以，其時(shí)間復(fù)雜度各為多少五、程序設(shè)計(jì)題（本大題共五、程序設(shè)計(jì)題（本大題共4040分，共分，共4小題，每小題小題，每小題1010分）分）1.編寫算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。2.編寫算法，在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的基本操作REPLACE（&S，T，V）3.假設(shè)以結(jié)點(diǎn)大小為1（且附設(shè)頭結(jié)點(diǎn)）的鏈表結(jié)構(gòu)表示串。試編寫實(shí)現(xiàn)下列6種

6、串的基本操作StrAssignStrCopyStrCompareStrLengthConcat和評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：每空2分二、名詞解釋題（二、名詞解釋題（1010分，共分，共2題，每小題題，每小題5分）分）1.參考答案：參考答案：頭指針是一指向鏈表開始結(jié)點(diǎn)的指針（沒(méi)有頭結(jié)點(diǎn)時(shí)）。解題方案：解題方案：評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：2.參考答案：參考答案：在串匹配運(yùn)算過(guò)程中，將主串稱為目標(biāo)串。解題方案：解題方案：評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：三、程序閱讀題（

7、三、程序閱讀題（2020分，共分，共2題，每小題題，每小題1010分）分）1.參考答案：參考答案：程序段的功能是利用棧T，將一個(gè)非空棧S中值等于m的元素全部刪去。解題方案：解題方案：評(píng)分標(biāo)準(zhǔn)：評(píng)分標(biāo)準(zhǔn)：2.參考答案：參考答案：答：該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。解題方案：解題方案：答：該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)