數(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.存儲(chǔ)結(jié)構(gòu)11.順序存儲(chǔ)結(jié)構(gòu)12.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

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

二、填空題

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

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

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

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

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

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

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

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

->__________->__________O

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

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

和0

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

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

識(shí)單位。

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

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

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

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

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

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

②型運(yùn)算，其操作不改變?cè)壿嫿Y(jié)構(gòu)，只從中提取某些信息作為運(yùn)算的結(jié)果。

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

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

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

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

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

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

方式，稱為四種基本存儲(chǔ)方式。

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

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

O

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

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

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

為：、、三類。

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

23.通常從、、、等幾方面評(píng)價(jià)算法的(包

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

24.一個(gè)算法的時(shí)空性能是指該算法的和,前者是算法

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

25.通常采用下述辦法來(lái)估算求解某類問(wèn)題的各個(gè)算法在給定輸入下的計(jì)算量：

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

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

給定輸入下的o

26.通常，一個(gè)算法在不同輸入下的計(jì)算量是不同的。則可用以下兩種方式來(lái)確定一個(gè)算法

的計(jì)算量：

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

或o

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

________或___________。

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

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

29.一個(gè)算法的輸入規(guī)?；騿?wèn)題的規(guī)模是指、

30.常見(jiàn)時(shí)間復(fù)雜性的量級(jí)有：常數(shù)階0()、對(duì)數(shù)階0()、線性階0

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

階量級(jí)的算法是,而量級(jí)低于平方階的算法是的。

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)容和形式無(wú)關(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;}”的時(shí)間復(fù)雜度T(n)=

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

三、單項(xiàng)選擇題

1.以下說(shuō)法錯(cuò)誤的是

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

①存儲(chǔ)結(jié)點(diǎn)每個(gè)存儲(chǔ)結(jié)點(diǎn)可以存放一個(gè)或一個(gè)以上的數(shù)據(jù)元素

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

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

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

①每個(gè)存儲(chǔ)結(jié)點(diǎn)只能存放一個(gè)數(shù)據(jù)元素（）

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

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

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

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

量。以下解釋錯(cuò)誤的是（）

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

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

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

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

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

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

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

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

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

選擇

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

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

（）

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

②僅適合于動(dòng)態(tài)查找表的存儲(chǔ)

③既適合靜態(tài)又適合動(dòng)態(tài)查找表的存儲(chǔ)

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

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

觀點(diǎn)（）

①正確②錯(cuò)誤

12以下說(shuō)法正確的是（）

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

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

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

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

13以下說(shuō)法正確的是（）

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

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

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

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

14以下說(shuō)法錯(cuò)誤的是（）

①所謂數(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ù)項(xiàng)在計(jì)算機(jī)中的映象分別稱為存儲(chǔ)結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域

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

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

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

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

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

④數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等

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

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

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

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

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

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

五、算法設(shè)計(jì)

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

（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)的鏈接實(shí)

現(xiàn)

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

二、填空題

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

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

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

為&的直接。

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

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

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

他結(jié)點(diǎn)有且僅有一個(gè)直接_____；除終端結(jié)點(diǎn)沒(méi)有直接______外，其它結(jié)點(diǎn)有且僅有一個(gè)直

接.

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

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

6.表長(zhǎng)為0的線性表稱為

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

六種。

8.順序表的特點(diǎn)是。

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

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

第i個(gè)結(jié)點(diǎn)儀的存儲(chǔ)地址為。

10.以下為順序表的插入運(yùn)算，分析算法，請(qǐng)?jiān)谔幪钌险_的語(yǔ)句。

Voidinsert_sqlist(sqlistL,datatypex,inti)

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

{(“表滿”);

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

i；尸)；

i-l]=x;

+1；

)

11.對(duì)于順序表的插入算法insert_sqlist來(lái)說(shuō)，若以結(jié)點(diǎn)移動(dòng)為標(biāo)準(zhǔn)操作，則插入算

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

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

12.以下為順序表的刪除運(yùn)算，分析算法，請(qǐng)?jiān)谔幪钌险_的語(yǔ)句。

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

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

for(j=i

)

13.對(duì)于順序表的刪除算法delele_sqlist來(lái)說(shuō)，若以結(jié)點(diǎn)移動(dòng)為標(biāo)準(zhǔn)操作，最壞情況

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

和。

14.以下為順序表的定位運(yùn)算，分析算法，請(qǐng)?jiān)赺處填上正確的語(yǔ)句。

intlocatesqlist(sqlistL,datatypeX)

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

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

if()return(i);

elsereturn(0);

}

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

性量級(jí)為o求表長(zhǎng)和讀表元算法的時(shí)間復(fù)雜性為。

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

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

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

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

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

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

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

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

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

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

組成。

23.INITIATE。的功能是建立一個(gè)空表。請(qǐng)?jiān)谔幪钌险_的語(yǔ)句。

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

return(t);

}

24.以下為求單鏈表表長(zhǎng)的運(yùn)算，分析算法，請(qǐng)?jiān)谔幪钌险_的語(yǔ)句。

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

j=O;

while(p->next!=NULL)

j++；

)

return(j);/*回傳表長(zhǎng)*/

)

25.以下為單鏈表按序號(hào)查找的運(yùn)算，分析算法，請(qǐng)?jiān)谝惶幪钌险_的語(yǔ)句。

pointerfindlklist(Ikiisthead,inti)

{p=head;j=0;

whi1e()

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

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

elsereturn(NULL);

)

26.以下為單鏈表的定位運(yùn)算，分析算法，請(qǐng)?jiān)凇幪钌险_的語(yǔ)句。

intlocate_lklist(Ikiisthead,datatypex)

/*求表head中第一個(gè)值等于x的結(jié)點(diǎn)的序號(hào)。不存在這種結(jié)點(diǎn)時(shí)結(jié)果為0*/

{p=head;j=0;

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

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

elsereturn(0);

)

27.以下為單鏈表的刪除運(yùn)算，分析算法，請(qǐng)?jiān)凇幪钌险_的語(yǔ)句。

voiddeletelklist(lklisthead,inti)

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

if()

(q=；

p->next=p->next;

free(q);

)

elseerror。'不存在第i個(gè)結(jié)點(diǎn)〃)

}

28.以下為單鏈表的插入運(yùn)算，分析算讓，請(qǐng)?jiān)谝惶幪钌险_的語(yǔ)句。

voidinsert_lklist(lklisthead,datatypex,inti)

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

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

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

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

s->noxt=;

p->next=s;

)

)

29.以下為單鏈表的建表算法，分析算法，請(qǐng)?jiān)凇幪钌险_的語(yǔ)句。

Iklistcreate_lklistl()

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

*/

{ininiate_lklist(head);

i=l；

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

while(x!=z$z)

scanf&x);

)

return(head);

}

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

30.以下為單鏈表的是表算法，分析算法，請(qǐng)?jiān)凇幪钌险_的語(yǔ)句。

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

{head=malloc(size);

p=head;

scanf&x);

while(x!=/$z)

(q=malloc(size);

q->data=x;

p->next=q;

scanf;

)

return(head);

)

此算法的量級(jí)為。

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

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

向的指針。

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

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

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

而串變量與其他變量不一樣，不能由_____語(yǔ)句對(duì)其賦值。

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

含的個(gè)數(shù)稱為該串的長(zhǎng)度。

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

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

_串。

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

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

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

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

里補(bǔ)上o

三、單向選擇題

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

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

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

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

否則，結(jié)果為0

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

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

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

X為值的新結(jié)點(diǎn)

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

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

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

3.順序表的一個(gè)存儲(chǔ)結(jié)點(diǎn)僅僅存儲(chǔ)線性表的一個(gè)（）

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

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

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

5.對(duì)于順序表，以下說(shuō)法錯(cuò)誤的是（）

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

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

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

④順序表的特點(diǎn)是:邏輯上相鄰的元素，存儲(chǔ)在物理位置也相鄰的單元中

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

①條件判斷②結(jié)點(diǎn)移動(dòng)

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

7.對(duì)于順序表的優(yōu)缺點(diǎn)，以下說(shuō)法錯(cuò)誤的是（）

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

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

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

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

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

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

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

③指向某結(jié)點(diǎn)④存儲(chǔ)某數(shù)據(jù)

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

①頭指針②尾指針

③指針型變量④空指針

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

（）

①任何指針都不能用打印語(yǔ)句輸出一個(gè)指針型變量的值

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

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

④對(duì)于一個(gè)指針型變量P的值。只需知道它指的是哪個(gè)結(jié)點(diǎn)

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

11.單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含（）

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

②指針域或鏈域

③指針域和鏈域

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

12.對(duì)于單鏈表表示法，以下說(shuō)法錯(cuò)誤的是（）

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

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

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

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

13.對(duì)于單鏈表表示法，以下說(shuō)法錯(cuò)誤的是)

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

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

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

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

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

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

①將“指針型變量”簡(jiǎn)稱為“指針”

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

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

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

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

?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.以下說(shuō)法錯(cuò)誤的是（）

①對(duì)循環(huán)鏈表來(lái)說(shuō)，從表中任一結(jié)點(diǎn)出發(fā)都能通過(guò)前后操作而掃描整個(gè)循環(huán)鏈表

②對(duì)單鏈表來(lái)說(shuō)，只有從頭結(jié)點(diǎn)開始才能掃描表中全部結(jié)點(diǎn)

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

④對(duì)雙鏈表來(lái)說(shuō)，結(jié)點(diǎn)xP的存儲(chǔ)位置既存放在其前趨結(jié)點(diǎn)的后繼指針域中，也存放在它

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

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

是（）

①real和rear->next->next

②rear->next和real

@rear->next->next和rear

?rear和rear->next

18.以下說(shuō)錯(cuò)誤的是（）

①對(duì)于線性表來(lái)說(shuō)，定位運(yùn)算在順序表和單鏈表上的量級(jí)均為0（n）

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

構(gòu)

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

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

⑤鏈入、摘除操作在順序表上的實(shí)現(xiàn)，平均時(shí)間復(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)點(diǎn)是（）

①不再需要頭指針了

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

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

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

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

①正確②錯(cuò)誤

23.以下說(shuō)法錯(cuò)誤的是（）

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

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

③對(duì)鏈表進(jìn)行插人和刑除操作時(shí)，不必移動(dòng)結(jié)點(diǎn)

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

24.以下說(shuō)法正確的是

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

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

要低

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

④順序存儲(chǔ)的線性表的插人和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僦挥薪?/p>

一半的元素需要移動(dòng)

25.以下說(shuō)法錯(cuò)誤的是（）

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

實(shí)現(xiàn)的效率低

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

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

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

26.以下說(shuō)法錯(cuò)誤的是（）

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

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

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

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

27.以下說(shuō)法正確的是（）

①在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)進(jìn)行

查找任何一個(gè)元素

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

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

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

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

28.以下說(shuō)法正確的是（）

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

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

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

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

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

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

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

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

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

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

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

②線性表中至少要有一個(gè)元素

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

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

后繼

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

①正確②不正確

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

①正確②不正確

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

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

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

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

①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é)點(diǎn)的目的是為了（）

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

③方便運(yùn)算的實(shí)現(xiàn)④說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)

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

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

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

②每個(gè)結(jié)點(diǎn)所代表的數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等

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

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

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

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

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

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

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

LLinkdataRLink

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

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

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

下面給出的算法段是要把一個(gè)新結(jié)點(diǎn)*Q作為非空雙向鏈表中的結(jié)點(diǎn)*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個(gè)元素和找第i個(gè)元素的前趨元素，則采用()

存儲(chǔ)方式最節(jié)省時(shí)間。

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

41.申是任意有限個(gè)

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

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

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

1.請(qǐng)用類C語(yǔ)言描述順序表，并予以解釋說(shuō)明。

2.請(qǐng)用類C語(yǔ)言描述單鏈表的類型定義，并予以解釋說(shuō)明。

3.請(qǐng)用類C語(yǔ)言描述雙鏈表的類型定義，并予以解釋說(shuō)明。

4.請(qǐng)用類C語(yǔ)言描述順序串的類型定義。

5.請(qǐng)用類C語(yǔ)言描述鏈串的類型定義。

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

點(diǎn)的作用。

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

點(diǎn)°

8.簡(jiǎn)述下列每對(duì)術(shù)語(yǔ)的區(qū)別：

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

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

(A,B)的簡(jiǎn)寫,A=〃〃的”〃含有兩個(gè)空格)。

(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è)計(jì)

1.設(shè)八二(a-.....an)和B=(bi,b2,...,b.)是兩個(gè)線性表(假定所含數(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是編寫一個(gè)比較A和B的算法，當(dāng)A<B,A=B或A>B是分別

輸出-1,0或者1。

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

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

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

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

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

表C,并要求利用原表(即A表和B表的)結(jié)點(diǎn)空間存放表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均以單鏈表為存儲(chǔ)結(jié)構(gòu)(并且m、n顯示保存)。要求C也以單鏈表為存儲(chǔ)結(jié)構(gòu)并利

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

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

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

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

中，使得L仍然有序。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1,2,...,n環(huán)形排列（如圖算法設(shè)計(jì)題13.所示），按順時(shí)針?lè)较驈?開始計(jì)數(shù)；計(jì)滿K

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

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

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

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

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

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

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

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

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

算法。

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

現(xiàn)的字符。

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

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

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

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

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

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

一、名詞解釋：

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

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

（下）三角矩陣

二、填空題：

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

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

或。

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

種。

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

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

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

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

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

7.以下運(yùn)算實(shí)現(xiàn)在順序棧上的初始化，請(qǐng)?jiān)谔幱眠m當(dāng)?shù)木渥佑枰蕴畛洹?/p>

intInitStack（SqStackTp*sq）

return(1);)

8.以下運(yùn)算實(shí)現(xiàn)在順序棧上的進(jìn)棧，請(qǐng)?jiān)谔幱眠m當(dāng)?shù)恼Z(yǔ)句予以填充。

IntPush(SqStackTp*sq,DataTypex)

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

else{:

return(l);}

)

9.以下運(yùn)算實(shí)現(xiàn)在順序棧上的退棧，請(qǐng)?jiān)谟眠m當(dāng)句子予以填充。

IntPop(SqStackTp*sq,DataType*x)

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

else{*x=;

______________________________________________9

return(1);}

}

10.以下運(yùn)算實(shí)現(xiàn)在順序棧上判棧空，請(qǐng)?jiān)谔幱眠m當(dāng)句子予以填充。

IntEmptyStack(SqStackTp*sq)

{if()return(1);

elsereturn(0);

)

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

充。

IntGetTop(SqStackTp*sq?DataType*x)

{if(_______________)return(0);

else{*x=;

return(l);}

)

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

充。

VoidInitStacl(LstackTp*ls){;}

13.,以下運(yùn)算實(shí)現(xiàn)在鏈棧上的進(jìn)棧，請(qǐng)?jiān)谔幱谜?qǐng)適當(dāng)句子予以填充。

VoidPush(LStackTp*ls,DataTypex)

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

p->next=ls;

14.以下運(yùn)算實(shí)現(xiàn)在璉棧上的退枝，請(qǐng)?jiān)谔幱谜?qǐng)適當(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)算實(shí)現(xiàn)在捱棧上讀棧頂元素，請(qǐng)?jiān)?/p>