數(shù)據(jù)結(jié)構(gòu)填空作業(yè)題答案

1、1《數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)》填空作業(yè)題答案填空作業(yè)題答案第1章緒論緒論（已校對無誤）1數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算三方面的內(nèi)容。2程序包括兩個內(nèi)容：數(shù)據(jù)結(jié)構(gòu)和算法。3.數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組：DataStructure=（D，S）。4.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。5.數(shù)據(jù)的邏輯結(jié)構(gòu)可以分類為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。6.在圖狀結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后繼結(jié)點數(shù)

2、可以有多個。7.在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間存在一對多的關(guān)系。8.數(shù)據(jù)的物理結(jié)構(gòu)，指數(shù)據(jù)元素在計算機(jī)中的標(biāo)識（映象），也即存儲結(jié)構(gòu)。9.數(shù)據(jù)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)3種類型，樹型結(jié)構(gòu)和有向圖結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。10.順序存儲結(jié)構(gòu)是把邏輯上相鄰的結(jié)點存儲在物理上連續(xù)的存儲單元里，結(jié)點之間的邏輯關(guān)系由存儲單元位置的鄰接關(guān)系來體現(xiàn)。11.鏈?zhǔn)酱鎯Y(jié)構(gòu)是把邏輯上相鄰的結(jié)點存儲在物理上任意的存儲單元里，節(jié)點之間的邏輯關(guān)系由附加的

3、指針域來體現(xiàn)。12.數(shù)據(jù)的存儲結(jié)構(gòu)可用4種基本的存儲方法表示，它們分別是順序存儲、鏈?zhǔn)酱鎯?、索引存儲和散列存儲?3.線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對多或多對多。14.數(shù)據(jù)結(jié)構(gòu)在物理上可分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。15.我們把每種數(shù)據(jù)結(jié)構(gòu)均視為抽象類型，它不但定義了數(shù)據(jù)的表示方式，還給出了處理數(shù)據(jù)的實現(xiàn)方法。16.數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。17.算法分析的兩個主要方面是時間復(fù)雜度和空間

4、復(fù)雜度。18.一個算法的時間復(fù)雜度是用該算法所消耗的時間的多少來度量的，一個算法的空間復(fù)雜度是用該算法在運行過程中所占用的存儲空間的大小來度量的。19.算法具有如下特點：有窮性、確定性、可行性、輸入、輸出。20.對于某一類特定的問題，算法給出了解決問題的一系列操作，每一操作都有它的確切的定義，并在有窮時間內(nèi)計算出結(jié)果。21.下面程序段的時間復(fù)雜度為㏒3n。317.在單鏈表中，指針p所指結(jié)點為最后一個結(jié)點的條件是pnext==NULL。1

5、8.循環(huán)鏈表的最大優(yōu)點是從表中任意結(jié)點出發(fā)都可訪問到表中每一個元素（或從表中任意結(jié)點出發(fā)都可遍歷整個鏈表）。19.設(shè)rear是指向非空、帶頭結(jié)點的循環(huán)單鏈表的尾指針，則該鏈表首結(jié)點的存儲位置是rearnextnext。20.帶頭結(jié)點的雙向循環(huán)表L為空表的條件是Lpri==Lnext。21.在循環(huán)鏈表中，可根據(jù)任一結(jié)點的地址遍歷整個鏈表，而單鏈表中需知道頭指針才能遍歷整個鏈表。22.將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較

6、次數(shù)是1。第3章棧和隊列棧和隊列（已校對無誤）1.棧又稱為后進(jìn)先出表，隊列又稱為先進(jìn)先出表。2.向一個順序棧插入一個元素時，首先使棧頂指針后移一個位置，然后把待插入元素寫入（或插入）到這個位置上。3.從一個棧刪除元素時，需要前移一位棧頂指針。4.在一個順序棧中，若棧頂指針等于－1，則為空棧；若棧頂指針等于maxSize－1，則為滿棧。5.在一個鏈?zhǔn)綏Ｖ?，若棧頂指針等于NULL，則為空棧；在一個鏈?zhǔn)疥犃兄?，若隊頭指針與隊尾指針的值相同，則

7、表示該隊列為空或該隊列只含有一個結(jié)點。6.向一個鏈?zhǔn)綏２迦胍粋€新結(jié)點時，首先把棧頂指針的值賦給新結(jié)點的指針域，然后把新結(jié)點的存儲位置賦給棧頂指針。7在求表達(dá)式值的算符優(yōu)先算法中使用的主要數(shù)據(jù)結(jié)構(gòu)是棧。8設(shè)有一個順序棧S，元素s1，s2，s3，s4，s5，s6依次進(jìn)棧，如果6個元素的出棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為3。9.設(shè)有一個空棧，現(xiàn)輸入序列為1，2，3，4，5。經(jīng)過push，push，pop，pus

8、h，pop，push，pop，push后，輸出序列是234。10.在按算符優(yōu)先法求解表達(dá)式3－1＋52時，最先執(zhí)行的運算是，最后執(zhí)行的運算是－。11.在棧的ADT定義中，除初始化操作外，其他基本操作的初始條件都要求棧存在。12.僅允許在同一端進(jìn)行插入和刪除的線性表稱為棧。13.在順序棧s中，棧為空的條件是s.top==s.base，棧為滿的條件是s.top－s.base＞=s.stacksize。14.設(shè)有算術(shù)表達(dá)式x＋a（y－b）－c