數(shù)據(jù)結(jié)構(gòu)習(xí)題全真模擬題

第一章概論

一、名詞解釋

數(shù)據(jù)表示2.數(shù)據(jù)史理3.數(shù)據(jù)4.數(shù)據(jù)元素5.邏輯關(guān)系6.邏輯結(jié)構(gòu)7.結(jié)構(gòu)

8.運(yùn)算9.基本運(yùn)算10.存儲結(jié)構(gòu)11.順序存儲結(jié)構(gòu)12.鏈?zhǔn)酱鎯Y(jié)構(gòu)

13.索引存儲結(jié)構(gòu)14.散列存儲結(jié)構(gòu)15.算法16.運(yùn)行終止的程序可執(zhí)行部分

17.偽語言算法18.非形式算法19.時空性能20.時間復(fù)雜性21.數(shù)據(jù)結(jié)構(gòu)

二、填空題

L計算機(jī)專業(yè)人員必須完成的兩項基本任務(wù)是：和。

2.數(shù)據(jù)在計算機(jī)存儲器中的存在形式稱為_______0

3.概括地說，數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容包括：數(shù)據(jù)的、定義在、數(shù)據(jù)

的的實現(xiàn)。此外，該課程還要考慮各種結(jié)構(gòu)和實現(xiàn)方法的。

4.由--種結(jié)構(gòu)和一組________構(gòu)成的整體是實際問題的一種數(shù)學(xué)模型,這種數(shù)

學(xué)模型的建立、選擇和實現(xiàn)是數(shù)據(jù)結(jié)構(gòu)的核心問題。

5.存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的實現(xiàn)。

6.數(shù)據(jù)表示任務(wù)是逐步完成的，即數(shù)據(jù)表示形式的變化過程是

->__________->__________O

7.數(shù)據(jù)處理任務(wù)也是逐步完成的，即轉(zhuǎn)化過程是->->。

8.從數(shù)據(jù)結(jié)構(gòu)的觀點看，通常所說的〃數(shù)據(jù)“應(yīng)分成二個不同的層次，即、

和0

9.根據(jù)需要，數(shù)據(jù)元素又被稱為、、或。

10.在有些場合下，數(shù)據(jù)項又稱為或_________，它是數(shù)據(jù)的不可分割的最小標(biāo)

識單位。

11.從某種意義上說，數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項實際反映了數(shù)據(jù)組織的三個層次，數(shù)據(jù)

可由若干個構(gòu)成，數(shù)據(jù)元素可由若干個構(gòu)成。

12.根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有、、、

四類基本邏輯結(jié)構(gòu)，它們反映了四類基本的數(shù)據(jù)組織形式。

13.根據(jù)操作的效果，可將運(yùn)算分成以下兩種基本類型：

①型運(yùn)算，其操作改變了原邏輯結(jié)構(gòu)的“值”，如結(jié)點個數(shù)、某些結(jié)點的內(nèi)容等;

②型運(yùn)算，其操作不改變原邏輯結(jié)構(gòu)，只從中提取某些信息作為運(yùn)算的結(jié)果。

14.將以某種邏輯結(jié)構(gòu)S為操作對象的運(yùn)算稱為“________"，簡稱“___________

15.一般地，可能存在同一邏輯結(jié)構(gòu)S上的兩個運(yùn)算A和B,A的實現(xiàn)需要或可以利用B,而

B的實現(xiàn)不需要利用A。在這種情況下，稱A可以“__________”為B。

16.存儲實現(xiàn)的基本目標(biāo)是建立數(shù)據(jù)的。

17.一般地，一個存儲結(jié)構(gòu)包括、、三個主要部分。

18.通常，存儲結(jié)點之間可以有、、、四種關(guān)聯(lián)

方式，稱為四種基本存儲方式。

19.可用任何?種存儲方式所規(guī)定的存儲結(jié)點之間的關(guān)聯(lián)方式來間接表達(dá)給定邏輯

結(jié)構(gòu)S中數(shù)據(jù)元素之間的邏輯關(guān)系。由此得到的存儲結(jié)構(gòu)，稱為或

O

20.一個運(yùn)算的實現(xiàn)是指一個完成該運(yùn)算功能的o運(yùn)算實現(xiàn)的核心是處

理步驟的規(guī)定，即o

21.任何算法都必須用某種語言加以描述。根據(jù)描述算法的語言的不同，可將算法分

為：、、三類。

22.數(shù)據(jù)結(jié)構(gòu)課程著重評論算法的__________,又稱為“____________

23.通常從、、、等幾方面評價算法的(包

括程序)的質(zhì)量。

24.一個算法的時空性能是指該算法的和,前者是算法

包含的，后者是算法需要的。

25.通常采用下述辦法來估算求解某類問題的各個算法在給定輸入下的計算量：

①根據(jù)該類問題的特點合理地選擇一種或幾種操作作為“”；

②確定每個算法在給定愉入下共執(zhí)行了多少次___________,并將此次數(shù)規(guī)定為該算法在

給定輸入下的o

26.通常，一個算法在不同輸入下的計算量是不同的。則可用以下兩種方式來確定一個算法

的計算量：

①以算法在所有輸入下的計算量的最大值作為算法的計算量，這種計算量稱為算法的

或o

②以算法在所有輸入下的計算量的加權(quán)平均值作為算法的計算量，這種計算量稱為算法的

________或___________。

27.最壞情況時間復(fù)雜性和平均時間復(fù)雜性統(tǒng)稱為或o

28.在一般情況下，一個算怙的時間復(fù)雜性是_________的函數(shù)。

29.一個算法的輸入規(guī)?；騿栴}的規(guī)模是指、

30.常見時間復(fù)雜性的量級有：常數(shù)階0()、對數(shù)階0()、線性階0

()、平方階0()、和指數(shù)階0()。通常認(rèn)為，具有指數(shù)

階量級的算法是,而量級低于平方階的算法是的。

31.數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的__________和o

32.數(shù)據(jù)結(jié)構(gòu)的課程的主要內(nèi)容可以概括為：、、和

◎

33.與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。

34.從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類，它們是和o

35.程序段“for(i=l;i〈=n;i++){k++;for(j=l;j<=n;j++)l+=k;}”的時間復(fù)雜度T(n)=

36.程序段Mi=l;while(i<=n)i=i*2;w的時間復(fù)雜度T(n)=______。

三、單項選擇題

1.以下說法錯誤的是

①用數(shù)字式計算機(jī)解決問題的實質(zhì)是對數(shù)據(jù)的加工處理

②程序設(shè)計的實質(zhì)是數(shù)據(jù)處理

③數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)的組織形式，基本運(yùn)算規(guī)定了數(shù)據(jù)的基本操作方式

④運(yùn)算實現(xiàn)是完成運(yùn)算功能的算法，或這些算法的設(shè)計

⑤數(shù)據(jù)處理方式總是與數(shù)據(jù)某種相應(yīng)的表示形式相聯(lián)系，反之亦然

2.根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基木的

數(shù)據(jù)組織形式。以下解釋錯誤的是()

①集合中任何兩個結(jié)點之間都有邏輯關(guān)系但組織形式松散

②線性結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列形成一條〃鎖鏈〃

③樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點像自然界中的樹

④圖狀結(jié)構(gòu)中的各個結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接

3.關(guān)于邏輯結(jié)構(gòu)，以下說法錯誤的是（）

①邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形成、內(nèi)容無關(guān)

②邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對位置有關(guān)

③邏輯結(jié)構(gòu)與所含結(jié)點個數(shù)無關(guān)

④一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

⑤邏輯結(jié)構(gòu)是數(shù)據(jù)組織的某種〃本質(zhì)性”的東西

4.根據(jù)操作的效果，可將運(yùn)算分成加工型運(yùn)算、引用型運(yùn)算兩種基本類型。對「表格

處理中的五種功能以下解釋錯誤的是（）

①查找引用型運(yùn)算，功能是找出滿足某種條件的結(jié)點在s（線形結(jié)構(gòu)）中的位置

②讀取引用型運(yùn)算功能是讀出s（線形結(jié)構(gòu)）中某指定位置結(jié)點的內(nèi)容

③插入引用型運(yùn)算，功能是在s（線形結(jié)構(gòu)）的某指定位置上增加一個新結(jié)點

④刪除加工型運(yùn)算，功能是撤消s（線形結(jié)構(gòu)）某指定位置上的結(jié)點

⑤更新加工型運(yùn)算，功能是修改s（線形結(jié)構(gòu)）中某指定結(jié)點的內(nèi)容

5.一般地，一個存儲結(jié)構(gòu)包括以下三個主要部分。以下說法錯誤的是（）

①存儲結(jié)點每個存儲結(jié)點可以存放一個或一個以上的數(shù)據(jù)元素

②數(shù)據(jù)元索之間關(guān)聯(lián)方式的表示也就是邏輯結(jié)構(gòu)的機(jī)內(nèi)表示

③附加設(shè)施，如為便于運(yùn)算實現(xiàn)而設(shè)置的“啞結(jié)點”等等

6.一般地，一個存儲結(jié)構(gòu)包括以下三個主要部分。以下說法錯誤的是

①每個存儲結(jié)點只能存放一個數(shù)據(jù)元素（）

②數(shù)據(jù)元素之間的關(guān)敵方式可由存儲結(jié)點之間的關(guān)聯(lián)方式直接表達(dá)

③一種存儲結(jié)構(gòu)可以在兩個級別上討論。其一是機(jī)器級，其二是語言級

④語言級描述可經(jīng)編譯自動轉(zhuǎn)換成機(jī)器級因此也可以看成是?種機(jī)內(nèi)表示

7.通常從正確性、易讀性、健壯性、高效性等四個方面評價算法（包括程序）的質(zhì)

量。以下解釋錯誤的是（）

①正確性算法應(yīng)能正確地實現(xiàn)預(yù)定的功能（即處理要求）

②易讀性算法應(yīng)易于閱讀和理解以便于調(diào)試修改和擴(kuò)充

③健壯性當(dāng)環(huán)境發(fā)生變化時，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會產(chǎn)生不霞要的

運(yùn)行結(jié)果

④高效性即達(dá)到所需要的時間性能

8.對于數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容，以下解釋正確的是（）

①數(shù)據(jù)結(jié)構(gòu)的定義，包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本運(yùn)算集

②數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，包括存儲實現(xiàn)、運(yùn)算實現(xiàn)和基本運(yùn)算集

③數(shù)據(jù)結(jié)構(gòu)的評價和選擇，包括邏輯結(jié)構(gòu)的選擇、基本運(yùn)算集的選擇和存儲

選擇

9,與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（）

①存儲結(jié)構(gòu)②存儲實現(xiàn)③邏輯結(jié)構(gòu)④運(yùn)算實現(xiàn)10順序存儲結(jié)構(gòu)

（）

①僅適合于靜態(tài)查找表的存儲

②僅適合于動態(tài)查找表的存儲

③既適合靜態(tài)又適合動態(tài)查找表的存儲

④既不適合靜態(tài)又不適合動態(tài)查找表的存儲

11.算法的時間復(fù)雜度，都要以通過算法中執(zhí)行頻度最高的語句的執(zhí)行次數(shù)來確定這種

觀點（）

①正確②錯誤

12以下說法正確的是（）

①所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的邏輯關(guān)系。

②邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)

③順序文件只適合于存放在磁帶上，索引文件只能存放在磁盤上

④基于某種邏輯結(jié)構(gòu)之上的運(yùn)算，其實現(xiàn)是惟一的

13以下說法正確的是（）

①數(shù)據(jù)元素是數(shù)據(jù)的最小單位

②數(shù)據(jù)項是數(shù)據(jù)的基本單位

③數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合

④數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合

14以下說法錯誤的是（）

①所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的邏輯關(guān)系的整體

②數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要而建立的

③數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機(jī)中的映象分別稱為存儲結(jié)構(gòu)、結(jié)點、數(shù)據(jù)域

④數(shù)據(jù)項足數(shù)據(jù)的基本單位

15通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）

①數(shù)據(jù)元素具有同一特點

②不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致

③每個數(shù)據(jù)元素都一樣

④數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等

四、簡答及應(yīng)用

1數(shù)據(jù)與數(shù)據(jù)元素有何區(qū)別？

2?為什么說數(shù)據(jù)元素之間的邏輯關(guān)系是數(shù)據(jù)內(nèi)部組織的主要方面？

3?邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么美系？

4?運(yùn)算與運(yùn)算的實現(xiàn)是K么關(guān)系?有哪些相同點和不同點？

5,類C語言與標(biāo)準(zhǔn)C語言的主要區(qū)別是什么？

五、算法設(shè)計

1、設(shè)計求解下列問題的類C語言算法，并分析其最壞情況時間復(fù)雜性及其量級。

（1）在數(shù)組A[l..n]中查找值為K的元素,若找到則輸出其位置i（K=i<=n）,否則輸

出。作為標(biāo)志。

（2）找出數(shù)組A[L.n]中元素的最大值和次最大值（本小題以數(shù)組元素的比較為標(biāo)

準(zhǔn)操作）。

第二章線性表

一.名詞解釋

1.線性結(jié)構(gòu)2.數(shù)據(jù)結(jié)構(gòu)的順序?qū)崿F(xiàn)3.順序表4.鏈表5.數(shù)據(jù)結(jié)構(gòu)的鏈接實

現(xiàn)

6.建表7.字符串8.串9.順序串10.鏈串

二、填空題

1.為了便于討論,有時將含n（n〉=0）個結(jié)點的線性結(jié)構(gòu)表示成3,az,……an）,其中每

個ai代表一個。在稱為結(jié)點，須稱為結(jié)點，i稱為祗在線性表中的

或o對任意一對相鄰結(jié)點&、ai+i(l〈=i〈n),ai稱為ai+i的直接_____&+i稱

為&的直接。

2.為了滿足運(yùn)算的封閉性，通常允許一種邏輯結(jié)構(gòu)巴現(xiàn)不含任何結(jié)點的情況。不含任何

結(jié)點的線性結(jié)構(gòu)記為或。

3.線性結(jié)構(gòu)的基本特征是:若至少含有一個結(jié)點，則除起始結(jié)點沒有直接_外，其

他結(jié)點有且僅有一個直接_____；除終端結(jié)點沒有直接______外，其它結(jié)點有且僅有一個直

接.

4.所有結(jié)點按1對1的鄰接關(guān)系構(gòu)成的整體就是結(jié)構(gòu)。

5.線性表的邏輯結(jié)構(gòu)是結(jié)構(gòu)。其所含結(jié)點的個數(shù)稱為線性表的,簡稱

6.表長為0的線性表稱為

7.線性表典型的基本運(yùn)算包括:、、、、、等

六種。

8.順序表的特點是。

9.順序表的類型定義可經(jīng)編譯轉(zhuǎn)換為機(jī)器級。假定每個datatype類型的變量占用

k(k>=l)個內(nèi)存單元，其中，b是順序表的第一個存儲結(jié)點的第一個單元的內(nèi)存地址，那么，

第i個結(jié)點儀的存儲地址為。

10.以下為順序表的插入運(yùn)算，分析算法，請在處填上正確的語句。

Voidinsert_sqlist(sqlistL,datatypex,inti)

/*將X插入到順序表L的第i-1個位置*/

{(“表滿”);

if((i〈l)ll(i“非法位置”)；

i；尸)；

i-l]=x;

+1；

)

11.對于順序表的插入算法insert_sqlist來說，若以結(jié)點移動為標(biāo)準(zhǔn)操作，則插入算

法的最壞時間復(fù)雜性為，量級是。插入算法的平均時間復(fù)雜性為,

平均時間復(fù)雜性量級是________。

12.以下為順序表的刪除運(yùn)算，分析算法，請在處填上正確的語句。

voiddelete_sqlist(sqlistL,inti)/*刪除順序表L中的第iT個位置上的結(jié)點*/

{if((i<l)||(i”非法位置”);

for(j=i

)

13.對于順序表的刪除算法delele_sqlist來說，若以結(jié)點移動為標(biāo)準(zhǔn)操作，最壞情況

時間復(fù)雜性及其量級分別是_____和,其平均時間復(fù)雜性及其量級分別為

和。

14.以下為順序表的定位運(yùn)算，分析算法，請在_處填上正確的語句。

intlocatesqlist(sqlistL,datatypeX)

/*在順序表L中查找第一值等于X的結(jié)點。若找到回傳該結(jié)點序號；否則回傳0*/

while((iWiT]!=X))i++;

if()return(i);

elsereturn(0);

}

15.對?于順序表的定位算法，若以取結(jié)點值與參數(shù)X的比較為標(biāo)準(zhǔn)操作，平均時間復(fù)雜

性量級為o求表長和讀表元算法的時間復(fù)雜性為。

16.在順序表上，求表長運(yùn)算LENGTH(L)可通過輸出實現(xiàn)，讀表元運(yùn)算

GET(L,i)可通過輸出實現(xiàn)。

17.線性表的常見鏈?zhǔn)酱鎯Y(jié)構(gòu)有___、_________和________.

18.單鏈表表示法的基本思想是用表示結(jié)點間的邏輯關(guān)系。

19.所有結(jié)點通過指針的鏈接而組織成o

20.為了便下實現(xiàn)各種運(yùn)算，通常在單鏈表的第一個結(jié)點之前增設(shè)一個類型相同的結(jié)點,

稱為，其它結(jié)點稱為。

21.在單鏈表中，表結(jié)點中的第一個和最后一個分別稱為和.頭結(jié)點

的數(shù)據(jù)域可以不存儲,也可以存放一個或。

22.單鏈表INITIATE:L)的功能是建立一個空表?？毡碛梢粋€和一個一

組成。

23.INITIATE。的功能是建立一個空表。請在處填上正確的語句。

Iklistinitiate」klist()/*建立一個空表*/

return(t);

}

24.以下為求單鏈表表長的運(yùn)算，分析算法，請在處填上正確的語句。

intlength_lklist(Iklisthead)/*求表head的長度*/

j=O;

while(p->next!=NULL)

j++；

)

return(j);/*回傳表長*/

)

25.以下為單鏈表按序號查找的運(yùn)算，分析算法，請在一處填上正確的語句。

pointerfindlklist(Ikiisthead,inti)

{p=head;j=0;

whi1e()

{p=p->next;j++;}

if(i==j)return(p);

elsereturn(NULL);

)

26.以下為單鏈表的定位運(yùn)算，分析算法，請在—處填上正確的語句。

intlocate_lklist(Ikiisthead,datatypex)

/*求表head中第一個值等于x的結(jié)點的序號。不存在這種結(jié)點時結(jié)果為0*/

{p=head;j=0;

while(){p=p->next;j++;)

if(p->data==x)return(j);

elsereturn(0);

)

27.以下為單鏈表的刪除運(yùn)算，分析算法，請在—處填上正確的語句。

voiddeletelklist(lklisthead,inti)

{p=find_]klist(head,i-1);

if()

(q=；

p->next=p->next;

free(q);

)

elseerror。'不存在第i個結(jié)點〃)

}

28.以下為單鏈表的插入運(yùn)算，分析算讓，請在一處填上正確的語句。

voidinsert_lklist(lklisthead,datatypex,inti)

/*在表head的第i個位置上插入一個以x為值的新結(jié)點*/

(p=find_lklist(head,i-l);

if(p==NULL)error(''不存在第i個位置”):

else{s=;s->data=x;

s->noxt=;

p->next=s;

)

)

29.以下為單鏈表的建表算法，分析算法，請在—處填上正確的語句。

Iklistcreate_lklistl()

/*通過調(diào)用initiateIklist和insertIklist算法實現(xiàn)的建表算法。假定$是結(jié)束標(biāo)志

*/

{ininiate_lklist(head);

i=l；

scanf(''%￡〃,&x);

while(x!=z$z)

scanf&x);

)

return(head);

}

該建表算法的時間復(fù)雜性約等于,其量級為

30.以下為單鏈表的是表算法，分析算法，請在—處填上正確的語句。

Iklistcreate」klist2()/*直接實現(xiàn)的建表算法。*/

{head=malloc(size);

p=head;

scanf&x);

while(x!=/$z)

(q=malloc(size);

q->data=x;

p->next=q;

scanf;

)

return(head);

)

此算法的量級為。

31.除單鏈表之外，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)還有和等。

32.循環(huán)鏈表與單鏈表的區(qū)別僅僅在于其尾結(jié)點的鏈域值不足,而足一個指

向的指針。

33.在單鏈表中若在每個結(jié)點中增加一個指針域，所含指針指向前驅(qū)結(jié)點，這樣構(gòu)成的

鏈表中有兩個方向不同的旌，稱為0

34.C語言規(guī)定，字符串常量按處理，它的值在程序的執(zhí)行過程中是不能改變的。

而串變量與其他變量不一樣，不能由_____語句對其賦值。

35.含零個字符的串稱為串，用表示。其他串稱為串。任何串中所

含的個數(shù)稱為該串的長度。

36.當(dāng)且僅當(dāng)兩個串的相等并且各個對應(yīng)位置上的字符都時，這兩個串相

等。一個串中任意個連續(xù)字符組成的序列稱為該串的串，該串稱為它所有子串的

_串。

37.串的順序存儲有兩種方法：一種是每個單元只存一個字符，稱為格式，另一

種是每個單元存放多個字符，稱為______格式。

38.通常將鏈串中每個存儲結(jié)點所存儲的字符個數(shù)稱為。當(dāng)結(jié)點大小大于1時，

鏈用的最后一個結(jié)點的各個數(shù)據(jù)域不一定總能全被字符占滿，此時，應(yīng)在這些未用的數(shù)據(jù)域

里補(bǔ)上o

三、單向選擇題

1.對于線性表基本運(yùn)算，以下結(jié)果是正確的是()

①初始化INmATE(L),引用型運(yùn)算，其作用是建立一個空表1尸中

.②求表長LENGTH(L),引用型運(yùn)算，其結(jié)果是線性表L的長度

③讀表元GET(L,i),引用型運(yùn)算。若l〈=i<=LEN(；TH(L),其結(jié)果是線性表L的第i個結(jié)點;

否則，結(jié)果為0

④定位LOCATES,X),引用型運(yùn)算.若L中存在一個或多個值與X相等的結(jié)點，運(yùn)算結(jié)果

為這些結(jié)點的序號的最大值；否則運(yùn)算結(jié)果為0

⑤插入INSERT(L,X,i),加工型運(yùn)算。其作用是在線性表L的第i+1個位置上增加一個以

X為值的新結(jié)點

⑥刪除DELETE（L,i）,引用型運(yùn)算.其作用是撤銷線性表L的第i個結(jié)點Ai

2.線性結(jié)構(gòu)中的一個結(jié)點代表一個（）

①數(shù)據(jù)元素②數(shù)據(jù)項③數(shù)據(jù)④數(shù)據(jù)結(jié)構(gòu)

3.順序表的一個存儲結(jié)點僅僅存儲線性表的一個（）

①數(shù)據(jù)元素②數(shù)據(jù)項③數(shù)據(jù)④數(shù)據(jù)結(jié)構(gòu)

4.順序表是線性表的（）

①鏈?zhǔn)酱鎯Y(jié)構(gòu)②順序存儲結(jié)構(gòu)③索引存儲結(jié)構(gòu)④散列存儲結(jié)構(gòu)

5.對于順序表，以下說法錯誤的是（）

①順序表是用一維數(shù)組實現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對地址

②順序表的所有存儲結(jié)點按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列

③順序表的特點是:邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰

④順序表的特點是:邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中

6.對順序表上的插入、刪除算法的時間兔雜性分析來說，通常以（）為標(biāo)準(zhǔn)操作

①條件判斷②結(jié)點移動

③算術(shù)表達(dá)式④獻(xiàn)值語句

7.對于順序表的優(yōu)缺點，以下說法錯誤的是（）

①無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間

②可以方便地隨機(jī)存取表中的任一結(jié)點

③插人和刪除運(yùn)算較方便

④由于順序表要求占用連續(xù)的空間，存儲分配只能預(yù)先進(jìn)行（靜態(tài)分配）

⑤容易造成一部分空間長期閑置而得不到充分利用

8.指針的全部作用就是（）

①指向某常量②指向某變量

③指向某結(jié)點④存儲某數(shù)據(jù)

9.除了（），其它任何指針都不能在算法中作為常量出現(xiàn)，也無法顯示。

①頭指針②尾指針

③指針型變量④空指針

10.單鏈表表示法的基本思想是指針P表示結(jié)點間的邏輯關(guān)系，則以下說法錯誤的是

（）

①任何指針都不能用打印語句輸出一個指針型變量的值

②如果要引用（如訪問）P所指結(jié)點，只需寫出p（以后跟域名）即可

③若想修改變量p的值（比如讓P指向另一個結(jié)點），則應(yīng)直接對p賦值

④對于一個指針型變量P的值。只需知道它指的是哪個結(jié)點

⑤結(jié)點*P是由兩個域組成的記錄，p->data是一個數(shù)據(jù)元素，p->next的值是一個指針

11.單鏈表的一個存儲結(jié)點包含（）

①數(shù)據(jù)域或指針域

②指針域或鏈域

③指針域和鏈域

④數(shù)據(jù)域和鏈域

12.對于單鏈表表示法，以下說法錯誤的是（）

①數(shù)據(jù)域用于存儲線性表的一個數(shù)據(jù)元素

②指針域或鏈域用于存放一個指向本結(jié)點所含數(shù)據(jù)元素的直接后繼所在結(jié)點的指針

③所有數(shù)據(jù)通過指針的旌接而組織成單鏈表

④NULL稱為空指針，它不指向任何結(jié)點，只起標(biāo)志作用

13.對于單鏈表表示法，以下說法錯誤的是)

①指向徒表的第一個結(jié)點的指針，稱為頭指針

②單鏈表的每一個結(jié)點都被一個指針?biāo)?/p>

③任何結(jié)點只能通過指向它的指針才能引用

④終端結(jié)點的指針域就為NULL

⑤尾指針變量具標(biāo)識單進(jìn)表的作用，故常用尾指針變量來命名單.鏈表

14.有時為了敘述方便，可以對一些概念進(jìn)行簡稱，以下說法錯誤的是（）

①將“指針型變量”簡稱為“指針”

②將“頭指針變量”稱為“頭指針”

③將“修改某指針型變量的值”稱為“修改某指針”

④將“P中指針?biāo)附Y(jié)點”稱為“P值”

15.設(shè)指針P指向雙鏈表的某一結(jié)點，則雙鏈表結(jié)構(gòu)的對稱性可用（）式來刻畫

?p->prior->next->==p->next->next

②p->prior->prior->==p->next->prior

@p>prior>next>==p>next>prior

④p->ncxt->noxt=p->prior->prior

16.以下說法錯誤的是（）

①對循環(huán)鏈表來說，從表中任一結(jié)點出發(fā)都能通過前后操作而掃描整個循環(huán)鏈表

②對單鏈表來說，只有從頭結(jié)點開始才能掃描表中全部結(jié)點

③雙鏈表的特點是找結(jié)點的前趨和后繼都很容易

④對雙鏈表來說，結(jié)點xP的存儲位置既存放在其前趨結(jié)點的后繼指針域中，也存放在它

的后繼結(jié)點的前趨指針域中。

17.在循環(huán)鏈表中，將頭指針改設(shè)為尾指針（rear）后，其頭結(jié)點和尾結(jié)點的存儲位置分別

是（）

①real和rear->next->next

②rear->next和real

@rear->next->next和rear

?rear和rear->next

18.以下說錯誤的是（）

①對于線性表來說，定位運(yùn)算在順序表和單鏈表上的量級均為0（n）

②讀表元運(yùn)算在順序表上只需常數(shù)時間0（1）便可實現(xiàn)，因此順序表是一種隨機(jī)存取結(jié)

構(gòu)

③在鏈表上實現(xiàn)讀表元運(yùn)算的平均時間復(fù)雜性為（）（1）

④鏈入、摘除操作在鏈表.上的實現(xiàn)可在0（1）時間內(nèi)完成

⑤鏈入、摘除操作在順序表上的實現(xiàn)，平均時間復(fù)雜性為0（n）

19.在串的基本運(yùn)算中，屬于加工型運(yùn)算的有（）

①EQAL（S,T）②LENGTH（S）

③CONCAT（S,T）④REPLACE（S,T,R）⑤INDEX（S,T）

20.在串的基本運(yùn)算中，屬于引用型運(yùn)算的有（）

①ASSIGN（S,T）②INSERT（SI,i,S2）

③DELETE（S,i,j）④SUBSTR⑸i,j）⑤REPLACE（S,T,R）

21.循環(huán)鏈表主要優(yōu)點是（）

①不再需要頭指針了

②己知某個結(jié)點的位置后，能夠容易找到它的直接前趨

③在進(jìn)行插入、刪除運(yùn)算時，能更好地保證鏈表不斷開

④從表中任一結(jié)點出發(fā)都能掃描到整個鏈表

22,每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作:插入、刪除和查找，這種說法（）

①正確②錯誤

23.以下說法錯誤的是（）

①數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機(jī)內(nèi)實際的存儲形式

②算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的

③對鏈表進(jìn)行插人和刑除操作時，不必移動結(jié)點

④雙鏈表中至多只有一個結(jié)點的后繼指針為空

24.以下說法正確的是

①線性結(jié)構(gòu)的基本特征是：每個結(jié)點有且僅有一個直接前趨和一個直接后繼

②線性表的各種基本運(yùn)算在順序存儲結(jié)構(gòu)上的實現(xiàn)均比在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)效率

要低

③在線性表的順序存儲結(jié)構(gòu)中，插人和刪除元素時，移動元素的個數(shù)與該元素位置有關(guān)

④順序存儲的線性表的插人和刪除操作不需要付出很大的代價，因為平均每次操只有近

一半的元素需要移動

25.以下說法錯誤的是（）

①求表長、定位這二種運(yùn)算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時

實現(xiàn)的效率低

②順序存儲的線性表可以隨機(jī)存取

③由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活

④線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)

26.以下說法錯誤的是（）

①線性表的元素可以是各種各樣的，邏輯上相鄰的元素在物理位置上不一定相鄰

②在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不?定相鄰

③在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰

④線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素

27.以下說法正確的是（）

①在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結(jié)點進(jìn)行

查找任何一個元素

②在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存

取的存儲結(jié)構(gòu)

③順序存儲結(jié)構(gòu)屬于鄲態(tài)結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)

④順序存儲方式只能用于存儲線性結(jié)構(gòu)

28.以下說法正確的是（）

①順序存儲方式的優(yōu)點是存儲密度大、且插入、刪除運(yùn)算效率高

②鏈表的每個結(jié)點中都恰好包含一個指針

③線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)

④順序存儲結(jié)構(gòu)屬于斡態(tài)結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)

29.下面關(guān)于線性表的敘述正確的是（）

①線性表采用順序存儲，必須占用一片連續(xù)的存儲單元

②線性表采用順序存儲，便于進(jìn)行插人和刪除操作

③線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元

④線性表采用鏈接存儲，不便于插人和刪除操作

30.線性表L=（aba2...a）,下列說法正確的是（）

①每個元素都有一個直接前驅(qū)和直接后繼

②線性表中至少要有一個元素

③表中諸元素的排列順序必須是由小到大或由大到小的

④除第一個元素和最后一個元素外其余每個元素都有一個且僅有一個直接前驅(qū)和直接

后繼

31.線性表的邏輯順序與存儲順序總是?致的，這種說法（）

①正確②不正確

32.設(shè)p,q是指針,若p=q,則*p二*q,這種說法（）

①正確②不正確

33.線性表若采用鏈表存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（）

①必需是聯(lián)系的②部分地址必須是連續(xù)的

③一定是不連續(xù)的④連續(xù)不連續(xù)都可以

34.設(shè)REAR是指向非空苗頭結(jié)點的循環(huán)單鏈表的尾指針，則刪除表首結(jié)點的操作可表示為

①p二rear;(2)rear=rear->next;

rear=rear->next;free(rear);

free(p)

(3)rcar=rcar->next->ncxt;④p=reai'->next->next;

free(rear);rear->next->next=p->next;

free(p);

35.單鏈表中，增加頭結(jié)點的目的是為了（）

①使單鏈表至少有一個結(jié)點②標(biāo)示表結(jié)點中首結(jié)點的位置

③方便運(yùn)算的實現(xiàn)④說明單鏈表是線性表的鏈?zhǔn)酱鎯崿F(xiàn)

36線性結(jié)構(gòu)中的一個結(jié)點代表一個數(shù)據(jù)元素，通常要求同一線性結(jié)構(gòu)的所有結(jié)點所代表的

數(shù)據(jù)元素具有相同的特性，這意味著

①每個結(jié)點所代表的數(shù)據(jù)元素都一樣。

②每個結(jié)點所代表的數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)要相等

③不僅數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致

④結(jié)點所代表的數(shù)據(jù)元素有同一特點

37.帶頭結(jié)點的單鏈表Head為空的判定條件是

①Head=Null②Head-〉next二NULL③Head->next=Head

38.非空的單循環(huán)鏈表L的尾結(jié)點*P,滿足

P->next=NULLP:NULLP->next=LP=L.

39.雙向鏈表結(jié)點結(jié)構(gòu)如下：

LLinkdataRLink

其中：LLink是指向前驅(qū)結(jié)點的指針域:

data是存放數(shù)據(jù)元素的數(shù)據(jù)域;

Rlink是指向后繼結(jié)點的指針域。

下面給出的算法段是要把一個新結(jié)點*Q作為非空雙向鏈表中的結(jié)點*p的前驅(qū)，插入到此雙

向鏈表中。不能正確完成要求的算法段是

?Q->LLink=P->LLink;②P->LLink=Q;

Q->Rlink=P;Q->Rlink=P;

P->LLink-Q;P->LLink->Rlink'Q;

P->LLink->Rlink=Q;Q->LLink=P->LLink;

(3)Q->LLink=P->LLink;

Q->Rlink=P;

P->LLink->R1ink=Q;

P->LLink=Q;

40.若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用()

存儲方式最節(jié)省時間。

①順序表②單捱表③雙鏈表④單循環(huán)鏈表

41.申是任意有限個

①符號構(gòu)成的集合②符號構(gòu)成的序列

③字符構(gòu)成的集合④字符構(gòu)成的序列

四、簡答及應(yīng)用

1.請用類C語言描述順序表，并予以解釋說明。

2.請用類C語言描述單鏈表的類型定義，并予以解釋說明。

3.請用類C語言描述雙鏈表的類型定義，并予以解釋說明。

4.請用類C語言描述順序串的類型定義。

5.請用類C語言描述鏈串的類型定義。

6.敘述以卜概念的區(qū)別：頭指針變量、頭指針、頭結(jié)點、首結(jié)點，并說明頭指針變量和頭結(jié)

點的作用。

7.有哪些鏈表可僅由一個尾指針來惟一確定，即從尾指針出發(fā)能訪問到鏈表上任何一個結(jié)

點°

8.簡述下列每對術(shù)語的區(qū)別：

空串和空格串；串變量和串常量;主串和子串；串變量的名字與串變量的值。

9.設(shè)有A=〃C=*old\D="my",試計算下列運(yùn)算的結(jié)果(注:A+B是C0NCAT

(A,B)的簡寫,A=〃〃的”〃含有兩個空格)。

(a)A+B

(b)B+A

(c)D+C+B

(d)SUBSTR(B,3,2)

(e)SUBSTR(C,1,0)

(f)LENGTH(A)

(g)LENGTH(D)

(h)INDEX(B,D)

(i)INDEX(C,"d")

(j)INSERT(D,2,C)

(k)INSERT(B,1,A)

(1)DELETE(B,2,2)

(m)DELETE(B,2,0)

10.已知:S=〃(xyz)*〃,T="(x+z)*y"°試?yán)眠B接、求子串和置換等基本運(yùn)算,將S轉(zhuǎn)換為T。

五、算法設(shè)計

1.設(shè)八二(a-.....an)和B=(bi,b2,...,b.)是兩個線性表(假定所含數(shù)據(jù)元素均為

整數(shù))。若n二m且ai=bi(i=l,...,n),則稱A=B;若ai=B(i=l,...,j)且a?i<bj，i(j<n<=m),

則稱A<B;在其他情況下均稱A>Bo是編寫一個比較A和B的算法，當(dāng)A<B,A=B或A>B是分別

輸出-1,0或者1。

2,試編寫在無頭結(jié)點的羊鏈表上實現(xiàn)線性表基本運(yùn)算LOCATE(L,X)、INSERTS,X,i)和

DELETE(L,i)的算法，并和在帶頭結(jié)點的單鏈表上實現(xiàn)相的算法進(jìn)行比較。

3.試編寫在不帶頭結(jié)點的單鏈表上實現(xiàn)線性表基本運(yùn)算LENGTH(L)的算法。

4.假設(shè)有兩個按數(shù)據(jù)元素值遞增有序排列的線性表A和B,均以單鏈表作存儲結(jié)構(gòu)。編寫

算法將A表和B表歸并成一個按元素值遞減有序(即非遞增有序，允許值相同)排列的線性

表C,并要求利用原表(即A表和B表的)結(jié)點空間存放表C。

5.設(shè)有線性表A=(a】,M和B=(bi,b2,..試寫合并A、B為線性表C的算法,

使得：

f(al,bl,...,am,bm,bm+l,bn^m<=n;

C="

(al,bl,…,an,bn,an+1,…,am)當(dāng)m>n;

假設(shè)A、B均以單鏈表為存儲結(jié)構(gòu)(并且m、n顯示保存)。要求C也以單鏈表為存儲結(jié)構(gòu)并利

用單鏈表A、B的結(jié)點空間。

6,設(shè)線性表存放在向量A[arrsize]的前elenum分量中，且遞增有序。試寫一算法，將X

插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜性。

7.已知單鏈表L中的結(jié)點是按值非遞減有序排列的，試寫一算法將他為x的結(jié)點插入表L

中，使得L仍然有序。

8,試分別以順序表和單鏈表作存儲結(jié)構(gòu)，各寫一個實現(xiàn)線性表的就地(即使用盡可能少的附

加空間)逆置的算法，在原表的存儲空間內(nèi)將線性表(&,a%...,%)逆置為(a0,...，a2,a)。

9.假設(shè)分別以兩個元素值遞增有序的線性表A、B表示兩個集合(即同一線性表中的元素各

不相同)，現(xiàn)要求構(gòu)成一個新的線性表C,C表示集合A與B的交，且C中元素也遞增有序。

試分別以順序表和單鏈表為存儲結(jié)構(gòu)，填寫實現(xiàn)上述運(yùn)算的算法。

10,已知A、B和C為三個元素值遞增有序的線性表，現(xiàn)要求對表A作如下運(yùn)算：刪去那些

既在表B中出現(xiàn)又在表C中出現(xiàn)的元素。試分別以兩種存儲結(jié)構(gòu)(一處種順序結(jié)構(gòu)，一種鏈

式的)編寫實現(xiàn)上述運(yùn)算的算法。

11.假設(shè)在長度大于1的循環(huán)鏈表中，既無頭結(jié)點也無頭指針。s為指向鏈表中某個結(jié)點的

指針，試編寫算法刪除結(jié)點*s的前趨結(jié)點。

12.已知一單鏈表中的數(shù)據(jù)元素含有三個字符(即:字母字符、數(shù)字字符和其它字符)。試編

寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類的字符，且利用原表中的結(jié)點空

間作為這三個表的結(jié)點空間(頭結(jié)點可另辟空間)。

13.(Josephus環(huán))任給正整數(shù)n、k,按下述方法可得排列L2,……，n的一個置換:將數(shù)字

1,2,...,n環(huán)形排列（如圖算法設(shè)計題13.所示），按順時針方向從1開始計數(shù)；計滿K

時輸出該為之上的數(shù)字（并從環(huán)中刪去該數(shù)字），然后從下?個數(shù)字開始繼續(xù)計數(shù)，直到環(huán)中

所有數(shù)字均被輸出為止。例如，n=10,k=3時，輸出的置換是3,6,9,2,7,1,8,5,10,

算法設(shè)計題13.a

4o試編寫一算法，對輸入的任意正整數(shù)n、k,輸出相應(yīng)的置換

14?在雙鏈表上實現(xiàn)線性表的下列基本運(yùn)算（a）初始化；（b）定位⑹插入（d）刪除。

15?設(shè)有一雙鏈表，每個結(jié)點中除有prior、data和next三個域外，還有一個訪問頻度域

freq,在鏈表被起用之前，其值均初始化為零。每當(dāng)在雙鏈表上進(jìn)行一次LOCATEL,X）運(yùn)算

時，令元素值為X的結(jié)點中freq域的值增1,并使此鏈表中結(jié)點保持按訪問頻度遞減的順

序排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試編寫實現(xiàn)符合上述要求的LOCATE運(yùn)算的

算法。

16?若X和Y是用結(jié)點大小為1單鏈表表示的串，設(shè)計一個算法找出X中第一個不在y中出

現(xiàn)的字符。

17.在順序用上實現(xiàn)用的判等運(yùn)算EQUAL（S,T）o

18.在鏈串上實現(xiàn)判等運(yùn)算EQUALS,T）。

19.若S和T是用結(jié)點大小為1的單鏈表存儲的兩個串（S、T為頭指針），設(shè)計一個算法將

串S中首次與串T匹配的子串逆值。

20.用串的其他運(yùn)算構(gòu)造串的子串定位運(yùn)算index。

第三章棧、隊列和數(shù)組

一、名詞解釋：

1.棧、棧頂、棧底、棧頂元素、空棧2.順序棧3.鏈棧4.遞歸5.隊列、隊尾、隊頭6.順序

隊7.循環(huán)隊8.隊滿9.鏈隊10.隨機(jī)存儲結(jié)構(gòu)11.特殊矩陣12.稀疏矩陣13.對稱方陣14.上

（下）三角矩陣

二、填空題：

1.棧修改的原則是或稱,因此，棧又稱為線性表。在棧

頂進(jìn)行插入運(yùn)算，被稱為________或________，在棧頂進(jìn)行刪除運(yùn)算，被稱為

或。

2.棧的基本運(yùn)算至少應(yīng)包括、、、、五

種。

3.對于順序棧，若棧頂下標(biāo)值top=0,此時，如果作退棧運(yùn)算，則產(chǎn)生“二

4.對于順序棧而言，在棧滿狀態(tài)下，如果此時在作進(jìn)校運(yùn)算，則會發(fā)生“二

5.一般地，棧和線性表類似有兩種實現(xiàn)方法，即實現(xiàn)和實現(xiàn)。

6.top=0表示______，此時作退棧運(yùn)算，則產(chǎn)生"_______":top二sqstackmaxsizeT

表示,此時作進(jìn)棧運(yùn)算，則產(chǎn)生“二

7.以下運(yùn)算實現(xiàn)在順序棧上的初始化，請在處用適當(dāng)?shù)木渥佑枰蕴畛洹?/p>

intInitStack（SqStackTp*sq）

return(1);)

8.以下運(yùn)算實現(xiàn)在順序棧上的進(jìn)棧，請在處用適當(dāng)?shù)恼Z句予以填充。

IntPush(SqStackTp*sq,DataTypex)

{if(sp->top==sqstack_maxsizcT}(error(''棧滿〃)；return(0);}

else{:

return(l);}

)

9.以下運(yùn)算實現(xiàn)在順序棧上的退棧，請在用適當(dāng)句子予以填充。

IntPop(SqStackTp*sq,DataType*x)

{if(sp-〉top==0){error(''下溢〃);return(0);}

else{*x=;

______________________________________________9

return(1);}

}

10.以下運(yùn)算實現(xiàn)在順序棧上判?？?，請在處用適當(dāng)句子予以填充。

IntEmptyStack(SqStackTp*sq)

{if()return(1);

elsereturn(0);

)

11.以下運(yùn)算實現(xiàn)在順序棧上取棧頂元素，請在_______________處用適當(dāng)句子予以填

充。

IntGetTop(SqStackTp*sq?DataType*x)

{if(_______________)return(0);

else{*x=;

return(l);}

)

12.以下運(yùn)算實現(xiàn)在鏈棧上的初始化，請在_______________處用請適當(dāng)句子予以填

充。

VoidInitStacl(LstackTp*ls){;}

13.,以下運(yùn)算實現(xiàn)在鏈棧上的進(jìn)棧，請在處用請適當(dāng)句子予以填充。

VoidPush(LStackTp*ls,DataTypex)

{LslackTp*p;p=mal1oc(sizeof(LstackTp));

p->next=ls;

14.以下運(yùn)算實現(xiàn)在璉棧上的退枝，請在處用請適當(dāng)句子予以填充。

IntPop(LstackTp*ls,DataType*x)

{LstackTp*p;

if(ls!=NULL)

{p=ls;

*x=_

ls=ls->noxt;

rcturn(l)；

}elsereturn(0);

)

15.以下運(yùn)算實現(xiàn)在捱棧上讀棧頂元素，請在