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.在無頭結(jié)點的單鏈表中，第1個結(jié)點的地址存放在頭指針中，其他結(jié)點的存儲地址存放在______結(jié)點的next域中。3.為了實現(xiàn)逐層訪問，算法中使用了一個______，以記憶正在訪問的這一層和上一層的頂點，以便于向下一

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

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

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

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

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

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