數(shù)據(jù)結(jié)構(gòu)練習(xí)題 第二章 線性表 習(xí)題及答案

數(shù)據(jù)結(jié)構(gòu)練習(xí)題第二章線性表習(xí)題及答案

第二章線性表

一．名詞解釋

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)表示成(a1，a2,??an)，其中每

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

或______。對任意一對相鄰結(jié)點(diǎn)ai、ai┼1(1<=i<n),ai稱為ai┼1的直接______ai┼1稱為ai的直接______。

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)沒有直接______外，其他結(jié)點(diǎn)有且僅有一個(gè)直接______;除終端結(jié)點(diǎn)沒有直接______外，其它結(jié)點(diǎn)有且僅有一個(gè)直接______.

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

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

6.表長為O的線性表稱為______

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

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

9.順序表的類型定義可經(jīng)編譯轉(zhuǎn)換為機(jī)器級。假定每個(gè)datatype類型的變量占用k(k>=1)個(gè)內(nèi)存單元，其中，b是順序表的第一個(gè)存儲結(jié)點(diǎn)的第一個(gè)單元的內(nèi)存地址，那么，第i個(gè)結(jié)點(diǎn)ai的存儲地址為______。

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

Voidinsert_sqlist(sqlistL，datatypex，inti)

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

{if(L.last==maxsize)error(“表滿”)；

if((i<1)||(i>L.last+1))error(“非法位置”);

for(j=L.last;j>=i;j--)______;

L.data[i-1]=x;

L.last=L.last+1;

}

11.對于順序表的插入算法insert_sqlist來說，若以結(jié)點(diǎn)移動(dòng)為標(biāo)準(zhǔn)操作，則插入算法的最壞時(shí)間復(fù)雜性為________，量級是________。插入算法的平均時(shí)間復(fù)雜性為________，平均時(shí)間復(fù)雜性量級是________。

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

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

{if((i<1)||(i>L.last))error(“非法位置”)；

for(j=i+1;j=L.last;j++)________;

L.last=L.last-1;

}

13.對于順序表的刪除算法delete_sqlist來說，若以結(jié)點(diǎn)移動(dòng)為標(biāo)準(zhǔn)操作，最壞情況時(shí)間復(fù)雜性及其量級分別是________和________,其平均時(shí)間復(fù)雜性及其量級分別為________1

和________。

14.以下為順序表的定位運(yùn)算，分析算法，請?jiān)赺_______處填上正確的語句。intlocate_sqlist(sqlistL,datatypeX)

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

while((i≤L.last)&&(L.data[i-1]!=X))i++;

if(________)return(i);

elsereturn(0);

}

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

16.在順序表上，求表長運(yùn)算LENGTH（L）可通過輸出________實(shí)現(xiàn)，讀表元運(yùn)算GET（L，i）可通過輸出________實(shí)現(xiàn)。

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

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

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

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ù)域可以不存儲________，也可以存放一個(gè)________或________。

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

23.INITIATE()的功能是建立一個(gè)空表。請?jiān)赺_______處填上正確的語句。

lklistinitiate_lklist()/*建立一個(gè)空表*/

{________________;

________________;

return(t);

}

24.以下為求單鏈表表長的運(yùn)算，分析算法，請?jiān)赺_______處填上正確的語句。intlength_lklist(lklisthead)/*求表head的長度*/

{________;

j=0;

while(p->next!=NULL)

{________________;

j++;

}

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

}

25.以下為單鏈表按序號查找的運(yùn)算，分析算法，請?jiān)赺___處填上正確的語句。pointerfind_lklist(lklisthead,inti)

{p=head;j=0;

while(________________)

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

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

2

elsereturn(NULL);

}

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

intlocate_lklist(lklisthead,datatypex)

/*求表head中第一個(gè)值等于x的結(jié)點(diǎn)的序號。不存在這種結(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)算，分析算法，請?jiān)赺___處填上正確的語句。

voiddelete_lklist(lklisthead,inti)

{p=find_lklist(head,i-1);

if(____________________________)

{q=________________;

p->next=p->next;

free(q);

}

elseerror(“不存在第i個(gè)結(jié)點(diǎn)”)

}

28.以下為單鏈表的插入運(yùn)算，分析算法，請?jiān)赺___處填上正確的語句。

voidinsert_lklist(lklisthead,datatypex,inti)

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

{p=find_lklist(head,i-1);

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

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

s->next=________________;

p->next=s;

}

}

29.以下為單鏈表的建表算法，分析算法，請?jiān)赺___處填上正確的語句。

lklistcreate_lklist1()

/*通過調(diào)用initiate_lklist和insert_lklist算法實(shí)現(xiàn)的建表算法。假定$是結(jié)束標(biāo)志*/{ininiate_lklist(head);

i=1;

scanf(“%f”,&x);

while(x!=’$’)

{________________;

________________;

scanf(“%f”,&x);

}

return(head);

}

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

3

30.以下為單鏈表的建表算法，分析算法，請?jiān)赺___處填上正確的語句。

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

{head=malloc(size);

p=head;

scanf(“%f”,&x);

while(x!=’$’)

{q=malloc(size);

q->data=x;

p->next=q;

________________;

scanf(“%f”,&x);

}

________________;

return(head);

}

此算法的量級為________________。

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

32．循環(huán)鏈表與單鏈表的區(qū)別僅僅在于其尾結(jié)點(diǎn)的鏈域值不是_________，而是一個(gè)指向_________的指針。

33．在單鏈表中若在每個(gè)結(jié)點(diǎn)中增加一個(gè)指針域,所含指針指向前驅(qū)結(jié)點(diǎn)，這樣構(gòu)成的鏈表中有兩個(gè)方向不同的鏈，稱為______。

34．C語言規(guī)定，字符串常量按______處理，它的值在程序的執(zhí)行過程中是不能改變的。而串變量與其他變量不一樣，不能由______語句對其賦值。

35．含零個(gè)字符的串稱為______串，用______表示。其他串稱為______串。任何串中所含______的個(gè)數(shù)稱為該串的長度。

36．當(dāng)且僅當(dāng)兩個(gè)串的______相等并且各個(gè)對應(yīng)位置上的字符都______時(shí)，這兩個(gè)串相等。一個(gè)串中任意個(gè)連續(xù)字符組成的序列稱為該串的______串，該串稱為它所有子串的______串。

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

38．通常將鏈串中每個(gè)存儲結(jié)點(diǎn)所存儲的字符個(gè)數(shù)稱為______。當(dāng)結(jié)點(diǎn)大小大于1時(shí)，鏈串的最后一個(gè)結(jié)點(diǎn)的各個(gè)數(shù)據(jù)域不一定總能全被字符占滿，此時(shí)，應(yīng)在這些未用的數(shù)據(jù)域里補(bǔ)上______。

三、單向選擇題

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

①初始化INITIATE(L)，引用型運(yùn)算，其作用是建立一個(gè)空表L=Ф

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

③讀表元GET(L,i),引用型運(yùn)算。若1<=i<=LENGTH(L),其結(jié)果是線性表L的第i個(gè)結(jié)點(diǎn)；否則，結(jié)果為0

④定位LOCATE(L,X),引用型運(yùn)算.若L中存在一個(gè)或多個(gè)值與X相等的結(jié)點(diǎn)，運(yùn)算結(jié)果為這些結(jié)點(diǎn)的序號的最大值；否則運(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

4

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

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

3．順序表的一個(gè)存儲結(jié)點(diǎn)僅僅存儲線性表的一個(gè)（）①數(shù)據(jù)元素②數(shù)據(jù)項(xiàng)③數(shù)據(jù)④數(shù)據(jù)結(jié)構(gòu)

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

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

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

①順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對地址②順序表的所有存儲結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列

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

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

6.對順序表上的插入、刪除算法的時(shí)間復(fù)雜性分析來說，通常以（）為標(biāo)準(zhǔn)操作①條件判斷②結(jié)點(diǎn)移動(dòng)

③算術(shù)表達(dá)式④賦值語句

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

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

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

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

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

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

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

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

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

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

①頭指針②尾指針

③指針型變量④空指針

10.單鏈表表示法的基本思想是指針P表示結(jié)點(diǎn)間的邏輯關(guān)系，則以下說法錯(cuò)誤的是（）①任何指針都不能用打印語句輸出一個(gè)指針型變量的值

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

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

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

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

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

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

②指針域或鏈域

③指針域和鏈域

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

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

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

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

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

13.對于單鏈表表示法，以下說法錯(cuò)誤的是（）①指向鏈表的第一個(gè)結(jié)點(diǎn)的指針，稱為頭指針

5

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

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

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

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

14．有時(shí)為了敘述方便，可以對一些概念進(jìn)行簡稱，以下說法錯(cuò)誤的是（）①將“指針型變量”簡稱為“指針”

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

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

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

15．設(shè)指針P指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對稱性可用（）式來刻畫①p->prior->next->==p->next->next

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

③p->prior->next->==p->next->prior

④p->next->next==p->prior->prior

16.以下說法錯(cuò)誤的是（）

①對循環(huán)鏈表來說，從表中任一結(jié)點(diǎn)出發(fā)都能通過前后操作而掃描整個(gè)循環(huán)鏈表②對單鏈表來說，只有從頭結(jié)點(diǎn)開始才能掃描表中全部結(jié)點(diǎn)

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

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

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

①real和rear->next->next

②rear->next和real

③rear->next->next和rear

④rear和rear->next

18.以下說錯(cuò)誤的是()

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

②讀表元運(yùn)算在順序表上只需常數(shù)時(shí)間O（1）便可實(shí)現(xiàn)，因此順序表是一種隨機(jī)存取結(jié)構(gòu)③在鏈表上實(shí)現(xiàn)讀表元運(yùn)算的平均時(shí)間復(fù)雜性為O（1）

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

⑤鏈入、摘除操作在順序表上的實(shí)現(xiàn)，平均時(shí)間復(fù)雜性為O（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(S1,i,S2)

③DELETE(S,i,j)④SUBSTR(S,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è)基本操作:插入、刪除和查找，這種說法（）

6

①正確②錯(cuò)誤

23．以下說法錯(cuò)誤的是（）

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

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

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

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

24．以下說法正確的是

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

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

低

③在線性表的順序存儲結(jié)構(gòu)中，插人和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素位置有關(guān)④順序存儲的線性表的插人和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僦挥薪话氲脑匦枰苿?dòng)

25．以下說法錯(cuò)誤的是（）

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

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

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

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

26．以下說法錯(cuò)誤的是（）

①線性表的元素可以是各種各樣的，邏輯上相鄰的元素在物理位置上不一定相鄰②在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰③在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰

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

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

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

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

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

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

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

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

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

③線性表的順序存儲結(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)屬于動(dòng)態(tài)結(jié)構(gòu)

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

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

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

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

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

30.線性表L=(a1,a2,...,ai,...,an),下列說法正確的是()

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

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

7

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

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

31.線性表的邏輯順序與存儲順序總是一致的，這種說法()

①正確②不正確

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

①正確②不正確

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

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

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

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

()

①p=rear;②rear=rear->next;

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

free(p)

③rear=rear->next->next;④p=rear->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)④說明單鏈表是線性表的鏈?zhǔn)酱鎯?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ù)要相同，而且對應(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)如下：

其中：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(mào)->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;

③Q->LLink=P->LLink;

Q->Rlink=P;

8

P->LLink->Rlink=Q;

P->LLink=Q;

40.若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（）存儲方式最節(jié)省時(shí)間。

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

41．串是任意有限個(gè)

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

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

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

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

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

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

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

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

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

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

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

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

9．設(shè)有A=””,B="mule"，C="old"，D="my",試計(jì)算下列運(yùn)算的結(jié)果(注:A+B是CONCAT（A,B）的簡寫,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)

(l)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=（a1,a2,a3,......an）和B=(b1,b2,...,bm)是兩個(gè)線性表（假定所含數(shù)據(jù)元素均為

整數(shù)）。若n=m且ai=bi(i=1,...,n),則稱A=B;若ai=bi(i=1,...,j)且aj+1<bj+1（j<n<=m）,則

稱A<B;在其他情況下均稱A>B。是編寫一個(gè)比較A和B的算法，當(dāng)A<B,A=B或A>B是分別輸出-1，0或者1。

2，試編寫在無頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表基本運(yùn)算LOCATE(L,X)、INSERT(L,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，均以單鏈表作存儲結(jié)構(gòu)。編寫算9

法將A表和B表歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許值相同）排列的線性表C，并要求利用原表(即A表和B表的)結(jié)點(diǎn)空間存放表C。

5．設(shè)有線性表A=(a1,a2,...,am)和B=(b1,b2,...,bn).試寫合并A、B為線性表C的算法，

使得：

(a1,b1,...,am,bm,bm1,bn)當(dāng)mn;C=

(a1,b1,...,an,bn,an1,...,am)當(dāng)mn;

假設(shè)A、B均以單鏈表為存儲結(jié)構(gòu)(并且m、n顯示保存)。要求C也以單鏈表為存儲結(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中，使得