數(shù)據(jù)結構習題全真模擬題

第一章概論

一、名詞解釋

數(shù)據(jù)表示2.數(shù)據(jù)史理3.數(shù)據(jù)4.數(shù)據(jù)元素5.邏輯關系6.邏輯結構7.結構

8.運算9.基本運算10.存儲結構11.順序存儲結構12.鏈式存儲結構

13.索引存儲結構14.散列存儲結構15.算法16.運行終止的程序可執(zhí)行部分

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

二、填空題

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

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

3.概括地說，數(shù)據(jù)結構課程的主要內容包括：數(shù)據(jù)的、定義在、數(shù)據(jù)

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

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

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

5.存儲結構是邏輯結構的實現(xiàn)。

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

->__________->__________O

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

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

和0

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

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

識單位。

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

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

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

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

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

①型運算，其操作改變了原邏輯結構的“值”，如結點個數(shù)、某些結點的內容等;

②型運算，其操作不改變原邏輯結構，只從中提取某些信息作為運算的結果。

14.將以某種邏輯結構S為操作對象的運算稱為“________"，簡稱“___________

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

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

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

17.一般地，一個存儲結構包括、、三個主要部分。

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

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

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

結構S中數(shù)據(jù)元素之間的邏輯關系。由此得到的存儲結構，稱為或

O

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

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

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

為：、、三類。

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

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

括程序)的質量。

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

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

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

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

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

給定輸入下的o

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

的計算量：

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

或o

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

________或___________。

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

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

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

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

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

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

31.數(shù)據(jù)結構的基本任務是數(shù)據(jù)結構的__________和o

32.數(shù)據(jù)結構的課程的主要內容可以概括為：、、和

◎

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

34.從邏輯關系上講，數(shù)據(jù)結構主要分為兩大類，它們是和o

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

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

三、單項選擇題

1.以下說法錯誤的是

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

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

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

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

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

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

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

①集合中任何兩個結點之間都有邏輯關系但組織形式松散

②線性結構中結點按邏輯關系依次排列形成一條〃鎖鏈〃

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

④圖狀結構中的各個結點按邏輯關系互相纏繞，任何兩個結點都可以鄰接

3.關于邏輯結構，以下說法錯誤的是（）

①邏輯結構與數(shù)據(jù)元素本身的形成、內容無關

②邏輯結構與數(shù)據(jù)元素的相對位置有關

③邏輯結構與所含結點個數(shù)無關

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

⑤邏輯結構是數(shù)據(jù)組織的某種〃本質性”的東西

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

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

①查找引用型運算，功能是找出滿足某種條件的結點在s（線形結構）中的位置

②讀取引用型運算功能是讀出s（線形結構）中某指定位置結點的內容

③插入引用型運算，功能是在s（線形結構）的某指定位置上增加一個新結點

④刪除加工型運算，功能是撤消s（線形結構）某指定位置上的結點

⑤更新加工型運算，功能是修改s（線形結構）中某指定結點的內容

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

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

②數(shù)據(jù)元索之間關聯(lián)方式的表示也就是邏輯結構的機內表示

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

6.一般地，一個存儲結構包括以下三個主要部分。以下說法錯誤的是

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

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

③一種存儲結構可以在兩個級別上討論。其一是機器級，其二是語言級

④語言級描述可經編譯自動轉換成機器級因此也可以看成是?種機內表示

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

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

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

②易讀性算法應易于閱讀和理解以便于調試修改和擴充

③健壯性當環(huán)境發(fā)生變化時，算法能適當?shù)刈龀龇磻蜻M行處理，不會產生不霞要的

運行結果

④高效性即達到所需要的時間性能

8.對于數(shù)據(jù)結構課程的主要內容，以下解釋正確的是（）

①數(shù)據(jù)結構的定義，包括邏輯結構、存儲結構和基本運算集

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

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

選擇

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

①存儲結構②存儲實現(xiàn)③邏輯結構④運算實現(xiàn)10順序存儲結構

（）

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

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

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

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

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

觀點（）

①正確②錯誤

12以下說法正確的是（）

①所謂數(shù)據(jù)的邏輯結構指的是數(shù)據(jù)元素之間的邏輯關系。

②邏輯結構與數(shù)據(jù)元素本身的內容和形式無關

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

④基于某種邏輯結構之上的運算，其實現(xiàn)是惟一的

13以下說法正確的是（）

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

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

③數(shù)據(jù)結構是帶有結構的各數(shù)據(jù)項的集合

④數(shù)據(jù)結構是帶有結構的數(shù)據(jù)元素的集合

14以下說法錯誤的是（）

①所謂數(shù)據(jù)的邏輯結構指的是數(shù)據(jù)元素之間的邏輯關系的整體

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

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

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

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

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

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

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

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

四、簡答及應用

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

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

3?邏輯結構與存儲結構是什么美系？

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

5,類C語言與標準C語言的主要區(qū)別是什么？

五、算法設計

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

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

出。作為標志。

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

準操作）。

第二章線性表

一.名詞解釋

1.線性結構2.數(shù)據(jù)結構的順序實現(xiàn)3.順序表4.鏈表5.數(shù)據(jù)結構的鏈接實

現(xiàn)

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

二、填空題

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

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

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

為&的直接。

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

結點的線性結構記為或。

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

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

接.

4.所有結點按1對1的鄰接關系構成的整體就是結構。

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

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

7.線性表典型的基本運算包括:、、、、、等

六種。

8.順序表的特點是。

9.順序表的類型定義可經編譯轉換為機器級。假定每個datatype類型的變量占用

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

第i個結點儀的存儲地址為。

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

Voidinsert_sqlist(sqlistL,datatypex,inti)

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

{(“表滿”);

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

i；尸)；

i-l]=x;

+1；

)

11.對于順序表的插入算法insert_sqlist來說，若以結點移動為標準操作，則插入算

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

平均時間復雜性量級是________。

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

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

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

for(j=i

)

13.對于順序表的刪除算法delele_sqlist來說，若以結點移動為標準操作，最壞情況

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

和。

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

intlocatesqlist(sqlistL,datatypeX)

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

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

if()return(i);

elsereturn(0);

}

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

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

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

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

17.線性表的常見鏈式存儲結構有___、_________和________.

18.單鏈表表示法的基本思想是用表示結點間的邏輯關系。

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

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

稱為，其它結點稱為。

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

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

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

組成。

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

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

return(t);

}

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

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

j=O;

while(p->next!=NULL)

j++；

)

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

)

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

pointerfindlklist(Ikiisthead,inti)

{p=head;j=0;

whi1e()

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

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

elsereturn(NULL);

)

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

intlocate_lklist(Ikiisthead,datatypex)

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

{p=head;j=0;

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

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

elsereturn(0);

)

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

voiddeletelklist(lklisthead,inti)

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

if()

(q=；

p->next=p->next;

free(q);

)

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

}

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

voidinsert_lklist(lklisthead,datatypex,inti)

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

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

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

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

s->noxt=;

p->next=s;

)

)

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

Iklistcreate_lklistl()

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

*/

{ininiate_lklist(head);

i=l；

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

while(x!=z$z)

scanf&x);

)

return(head);

}

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

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.除單鏈表之外，線性表的鏈式存儲結構還有和等。

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

向的指針。

33.在單鏈表中若在每個結點中增加一個指針域，所含指針指向前驅結點，這樣構成的

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

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

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

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

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

36.當且僅當兩個串的相等并且各個對應位置上的字符都時，這兩個串相

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

_串。

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

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

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

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

里補上o

三、單向選擇題

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

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

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

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

否則，結果為0

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

為這些結點的序號的最大值；否則運算結果為0

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

X為值的新結點

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

2.線性結構中的一個結點代表一個（）

①數(shù)據(jù)元素②數(shù)據(jù)項③數(shù)據(jù)④數(shù)據(jù)結構

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

①數(shù)據(jù)元素②數(shù)據(jù)項③數(shù)據(jù)④數(shù)據(jù)結構

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

①鏈式存儲結構②順序存儲結構③索引存儲結構④散列存儲結構

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

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

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

③順序表的特點是:邏輯結構中相鄰的結點在存儲結構中仍相鄰

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

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

①條件判斷②結點移動

③算術表達式④獻值語句

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

①無需為表示結點間的邏輯關系而增加額外的存儲空間

②可以方便地隨機存取表中的任一結點

③插人和刪除運算較方便

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

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

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

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

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

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

①頭指針②尾指針

③指針型變量④空指針

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

（）

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

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

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

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

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

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

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

②指針域或鏈域

③指針域和鏈域

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

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

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

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

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

④NULL稱為空指針，它不指向任何結點，只起標志作用

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

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

②單鏈表的每一個結點都被一個指針所指

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

④終端結點的指針域就為NULL

⑤尾指針變量具標識單進表的作用，故常用尾指針變量來命名單.鏈表

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

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

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

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

④將“P中指針所指結點”稱為“P值”

15.設指針P指向雙鏈表的某一結點，則雙鏈表結構的對稱性可用（）式來刻畫

?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)鏈表來說，從表中任一結點出發(fā)都能通過前后操作而掃描整個循環(huán)鏈表

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

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

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

的后繼結點的前趨指針域中。

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

是（）

①real和rear->next->next

②rear->next和real

@rear->next->next和rear

?rear和rear->next

18.以下說錯誤的是（）

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

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

構

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

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

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

19.在串的基本運算中，屬于加工型運算的有（）

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

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

20.在串的基本運算中，屬于引用型運算的有（）

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

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

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

①不再需要頭指針了

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

③在進行插入、刪除運算時，能更好地保證鏈表不斷開

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

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

①正確②錯誤

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

①數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內實際的存儲形式

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

③對鏈表進行插人和刑除操作時，不必移動結點

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

24.以下說法正確的是

①線性結構的基本特征是：每個結點有且僅有一個直接前趨和一個直接后繼

②線性表的各種基本運算在順序存儲結構上的實現(xiàn)均比在鏈式存儲結構上的實現(xiàn)效率

要低

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

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

一半的元素需要移動

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

①求表長、定位這二種運算在采用順序存儲結構時實現(xiàn)的效率不比采用鏈式存儲結構時

實現(xiàn)的效率低

②順序存儲的線性表可以隨機存取

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

④線性表的鏈式存儲結構優(yōu)于順序存儲結構

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

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

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

③在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上不一定相鄰

④線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素

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

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

查找任何一個元素

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

取的存儲結構

③順序存儲結構屬于鄲態(tài)結構，鏈式結構屬于動態(tài)結構

④順序存儲方式只能用于存儲線性結構

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

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

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

③線性表的順序存儲結構優(yōu)于鏈式存儲結構

④順序存儲結構屬于斡態(tài)結構，鏈式結構屬于動態(tài)結構

29.下面關于線性表的敘述正確的是（）

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

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

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

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

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

①每個元素都有一個直接前驅和直接后繼

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

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

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

后繼

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

①正確②不正確

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

①正確②不正確

33.線性表若采用鏈表存儲結構時，要求內存中可用存儲單元的地址（）

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

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

34.設REAR是指向非空苗頭結點的循環(huá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.單鏈表中，增加頭結點的目的是為了（）

①使單鏈表至少有一個結點②標示表結點中首結點的位置

③方便運算的實現(xiàn)④說明單鏈表是線性表的鏈式存儲實現(xiàn)

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

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

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

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

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

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

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

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

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

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

39.雙向鏈表結點結構如下：

LLinkdataRLink

其中：LLink是指向前驅結點的指針域:

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

Rlink是指向后繼結點的指針域。

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

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

?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.申是任意有限個

①符號構成的集合②符號構成的序列

③字符構成的集合④字符構成的序列

四、簡答及應用

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

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

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

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

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

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

點的作用。

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

點°

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

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

9.設有A=〃C=*old\D="my",試計算下列運算的結果(注: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"°試利用連接、求子串和置換等基本運算,將S轉換為T。

五、算法設計

1.設八二(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的算法，當A<B,A=B或A>B是分別

輸出-1,0或者1。

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

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

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

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

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

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

5.設有線性表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)當m>n;

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

用單鏈表A、B的結點空間。

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

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

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

中，使得L仍然有序。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1,2,...,n環(huán)形排列（如圖算法設計題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,

算法設計題13.a

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

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

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

freq,在鏈表被起用之前，其值均初始化為零。每當在雙鏈表上進行一次LOCATEL,X）運算

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

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

算法。

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

現(xiàn)的字符。

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

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

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

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

20.用串的其他運算構造串的子串定位運算index。

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

一、名詞解釋：

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

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

（下）三角矩陣

二、填空題：

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

頂進行插入運算，被稱為________或________，在棧頂進行刪除運算，被稱為

或。

2.棧的基本運算至少應包括、、、、五

種。

3.對于順序棧，若棧頂下標值top=0,此時，如果作退棧運算，則產生“二

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

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

6.top=0表示______，此時作退棧運算，則產生"_______":top二sqstackmaxsizeT

表示,此時作進棧運算，則產生“二

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

intInitStack（SqStackTp*sq）

return(1);)

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

IntPush(SqStackTp*sq,DataTypex)

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

else{:

return(l);}

)

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

IntPop(SqStackTp*sq,DataType*x)

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

else{*x=;

______________________________________________9

return(1);}

}

10.以下運算實現(xiàn)在順序棧上判?？眨堅谔幱眠m當句子予以填充。

IntEmptyStack(SqStackTp*sq)

{if()return(1);

elsereturn(0);

)

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

充。

IntGetTop(SqStackTp*sq?DataType*x)

{if(_______________)return(0);

else{*x=;

return(l);}

)

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

充。

VoidInitStacl(LstackTp*ls){;}

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

VoidPush(LStackTp*ls,DataTypex)

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

p->next=ls;

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

IntPop(LstackTp*ls,DataType*x)

{LstackTp*p;

if(ls!=NULL)

{p=ls;

*x=_

ls=ls->noxt;

rcturn(l)；

}elsereturn(0);

)

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