第1章緒論

一、判斷題

1.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關。（M）

2.一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的一個基本運算集構(gòu)成的整體。（M）

3.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（X）

4.數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是相同的。（X）

5.程序和算法原則上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時可以通用。（X）

6.從邏輯關系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。（，）

7.數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映象。（M）

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

9.數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計算機的。（X）

10.算法是對解題方法和步驟的描述。（M）

二、填空題

1.數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩種結(jié)構(gòu)。

2.數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。

3.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)°

4.樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。

5.在樹形結(jié)構(gòu)中，除了樹根結(jié)點以外，其余每個結(jié)點只有L個前驅(qū)結(jié)點。

6.在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后繼結(jié)點數(shù)可口任意多個。

7.數(shù)據(jù)的存儲結(jié)構(gòu)又叫物理結(jié)構(gòu)。

8.數(shù)據(jù)的存儲結(jié)構(gòu)形式包括順序存儲、鏈式存儲、索引存儲和散列存儲。

9.線性結(jié)構(gòu)中的元素之間存在一?對一的關系。

10.樹形結(jié)構(gòu)中的元素之間存在mU的關系。

11.圖形結(jié)構(gòu)的元素之間存在多對多的關系。

12.數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法（或運算）3個方面的內(nèi)容。

13.數(shù)據(jù)結(jié)構(gòu)被定義為（D,R）,其中D是數(shù)據(jù)的有限集合，R是D上的關系有限集合。

14.算法是一個有窮指令的集合。

15.算法效率的度最可以分為事先估算法和事后統(tǒng)計法。

16.一個算法的時間復雜度是算法輸入規(guī)模的函數(shù)。

17.算法的空間復雜度是指該算法所耗費的存儲空間，它是該算法求解問題規(guī)模的n的函數(shù)。

18.若一個算法中的語句頻度之和為T（n）=6n+3nlog2n，則算法的時間復雜度為。（nl。咫n）。

19.若一個算法的語句頻度之和為丁（0=3什可。/+/則算法的時間復雜度為O（n2）

20.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序問題中計算機的圜包象，以及它們之間的關系和運算的學

科。

三、選擇題

1.數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A）及它們之間的相互關系。

A.存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)B.存儲和抽象C.莪系和抽象D.聯(lián)系與邏輯

2.在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（Oo

A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)。

3.數(shù)據(jù)在計算機存儲內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（C）。

A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲結(jié)構(gòu)D.鏈式存儲結(jié)構(gòu)

4.非線性結(jié)構(gòu)中的每個結(jié)點（D）。

A.無直接前驅(qū)結(jié)點.B.無直接后繼結(jié)點.

c.只有一個直接前驅(qū)結(jié)點和一個直接后繼結(jié)點D.可能有多個直接前驅(qū)結(jié)點和多個直接后繼結(jié)點

5.鏈式存儲結(jié)構(gòu)所占存儲空間（A）。

A.分兩部分，一部分存放結(jié)點的值，另一個部分存放表示結(jié)點間關系的指針。

B.只有一部分，存放結(jié)點的值。C.只有一都分，存儲表示結(jié)點間關系的指針。

D.分兩部分，一部分存放結(jié)點的值，另一部分存放結(jié)點所占單元素

6.算法的計算量大小稱為算法的（C）。

A.現(xiàn)實性B.難度C.時間復雜性D.效率

7.數(shù)據(jù)的基本單位（B）o

A.數(shù)據(jù)結(jié)構(gòu)B.數(shù)據(jù)元素C.數(shù)據(jù)項D.文件

8.每個結(jié)點只含有?個數(shù)據(jù)元素，所有存儲結(jié)點相繼存放在?個連續(xù)的存儲空間里，這種存儲結(jié)構(gòu)稱為

（A）結(jié)構(gòu)。

A.順序結(jié)構(gòu)B.鏈式結(jié)構(gòu)C.索引結(jié)構(gòu)D.散列結(jié)構(gòu)

9.每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（B）o

A.順序B.鏈式C.索引D.散列

10.以下任何兩個結(jié)點之間都沒有邏輯關系的是（D）。

A.圖形結(jié)構(gòu)B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.集合

11.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是（C）。

A.物理結(jié)構(gòu)B.存儲結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.邏輯和存儲結(jié)構(gòu)

12.下列4種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關系最弱的是（A）。

A.集合B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖形結(jié)構(gòu)

13.與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的（A）。

A.邏輯結(jié)構(gòu)B.存儲結(jié)構(gòu)C.邏輯實現(xiàn)D.存儲實現(xiàn)

14.每一個存儲結(jié)點只含有一個數(shù)據(jù)元素，存儲結(jié)點存放在連續(xù)的存儲空間，另外有一組指明結(jié)點存儲位

置的表，該存儲方式是（。存儲方式。

A.順序B.鏈式C.索引D.散列

15.算法能正確的實現(xiàn)預定功能的特性稱為算法的（A）。

A.正確性B.易讀性C.健壯性D.高效性

16.算法在發(fā)生非法操作時可以作出相應處理的特性稱為算法的（C）。

A.正確性B.易讀性C.健壯性D.高效性

17.下列時間復雜度中最壞的是（D）。

A.O(1)B.O(n)C.O(log2n)D.OCn2)

18.下列算法的時間復雜度是（D）。

fbr(i=0;i<n;i++)

for(j=o;i<n;j++)

c[i]D]=i+j；

A.O(1)B.O(n)C,(Ic&n)D.OCn2)

19.算法分析的兩個主要方面是（A）。

A.空間復雜性和時間復雜性B.正確性和簡明性

C.可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性

20.計算機算法必須具備輸入、輸出和（Oo

A.計算方法B.排序方法C.解決問題的有限運算步驟D.程序設計方法

精品

第2章線性表

一、判斷題

1.線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲。（X）

2.鏈表的每個結(jié)點都恰好包含一個指針域。（X）

3.在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。（M）

4.順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。（X）

5,線性鏈表的刪除算法簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前

移動。（X）

6順序表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復雜類型。（X）

7.線性表鏈式存儲的特點是可以用一?組任意的存儲單元存儲表中的數(shù)據(jù)元素。（M）

8.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。（M）

9.順序表結(jié)構(gòu)適宜進行順序存取，而鏈表適宜進行隨機存取。（X）

10.插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中是最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。（x）

二、填空題

1.順序表中邏輯上相鄰的元素在物理位置上必須相鄰。

2.線性表中結(jié)點的集合是有限的，結(jié)點間的關系是二21二關系。

3.順序去相對于鏈表的優(yōu)點是節(jié)省存儲和隨機存取。

4.鏈表相對于順序表的優(yōu)點是插入、刪除方便。

5.當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快速度存取線性表中的

元素時，應采用順序存儲結(jié)構(gòu)。

6.順序表中訪問任意一個結(jié)點的時間匆:雜度均為O（Do

7.鏈表相對于順序表的優(yōu)點是插入、刪除方便；缺點是存儲密度處。

8.在雙向鏈表中要刪除已知結(jié)點*P,其時間復雜度為O（Do

9-在單向鏈表中要在已知結(jié)點*口之前插入一個新結(jié)點，需找到*P的直接前驅(qū)結(jié)點的地址，其查找的

時間復雜度為

10.在單向鏈表中需知道頭指固才能遍歷整個鏈表。

11.線性表中第一個結(jié)點沒有直接前驅(qū)，稱為四結(jié)點。

12.在一個長度為n的順序表中刪除第i個元素，要移動n-i個元素。

13.在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移n-i+1個元素。

14.在無頭結(jié)點的單向鏈表中，第一個結(jié)點的地址存放在頭指針中，而其他結(jié)點的存儲地址存放在

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

15.線性表的元素總數(shù)不確定，且經(jīng)常需要進行插入和刪除操作，應采用鏈子存儲結(jié)構(gòu)。

16.在線性表中的鏈式存儲中，元素之間的邏輯關系是通過指針決定。

17.在雙向鏈表中，每個結(jié)點都有兩個指針域，它們一個指向其前趨結(jié)點,另一個指向其后繼結(jié)

點。

18.對一個需要經(jīng)常進行插入和刪除操作的線性表，采用鏈式存儲結(jié)構(gòu)為宜。

19.雙向鏈表中，設P是指向其中待刪除的結(jié)點，則需要執(zhí)行的操作為p->prior->nex『p>next；

p->next->prior二p->prior

20.在如圖所示的鏈表中，若在指針P所在的結(jié)點之后插入數(shù)據(jù)域值為a和b的兩個結(jié)點，則可用語

句S->next->next=p->next和P->next=S；來實現(xiàn)該操作。

精品

pQR

指向鏈表Q結(jié)點的前驅(qū)的指釬是（B）0

A.LB.PC.QD.R

13.設p為指向單循環(huán)鏈表上某結(jié)點的指針，則*p的直接前驅(qū)（C）＜,

A.找不到B.查找時間復雜度為。（1）

C.查找時間復雜度為。（n）D.查找結(jié)點的次數(shù)約為「

14.等概率情況下，在有n個結(jié)點的順序表上做插入結(jié)點運算，需平均移動結(jié)點的數(shù)目為（8）。

A.nB.(n-l)/2C.n/2D.(n+l)/2

15在下列鏈表中不能從當前結(jié)點出發(fā)訪問到其余各結(jié)點的是（C）。

A.雙向鏈表B.單循環(huán)鏈表C.單向鏈表【＞雙向循冊鏈表

16.在順序表中，只要知道（D）,就可以求出任一結(jié)點的存儲地址。

A.基地址B.結(jié)點大小C.向量大小D.基地址和結(jié)點大小

17.在雙向鏈表中做插入運算的時間復雜度為（A）。

A.O(1)B.O(n)C.Ofn2)D.O(logani

18.鏈表不具備的特點是（A）。

A.隨機訪問B.不必事先估計存儲空間C.插入刪除時不需要移動元素D.所需空間與線性表成正比

19.以下關于線性表的論述，不正確的為（C）。

A.線性表中的元素可以是數(shù)字、字符、記錄等不同類型B.線性順序表中包含的元素個數(shù)不足任意的

C.線性表中的每個結(jié)點都有且僅有一個直接前驅(qū)和一個直接后繼

D.存在這樣的線性表，即表中沒有任何結(jié)點

20.在（B）的運算中，使用順序表比鏈表好。

A.插入B.根據(jù)序號查找C.刪除D,根據(jù)元索查找

精品

第3章棧

一、判斷題

1.棧是運算受限制的線性表。（M）

2.在?？盏那闆r下，不能作出棧操作，否則產(chǎn)生下溢。（M）

3.棧一定是順序存儲的線性結(jié)構(gòu)。（X）

4.棧的特點是“后進先出”。（M）

5.空棧就是所有元素都為0的棧。（X）

6.在C（或C++）語言中設順序棧的長度為MAXLEN,則top二MAXLEN時表示棧滿。（X）

7,鏈棧與順序棧相比，其特點之一是通常不會出現(xiàn)棧滿的情況。（M）

8.一個棧的輸入序列為：A,B,C,D,可以得到輸出序列：C,A,B,D。（X）

9.遞歸定義就是循環(huán)定義。（X）

10.將十進制數(shù)轉(zhuǎn)換為二進制數(shù)是棧的典型應用之一。（M）

二、填空題

1.在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂°

2.在順序棧中，當棧頂指針top=1時，表示棧空。

3.在有n個元素的棧中，進棧操作時間復雜度為O（1）o

4.在棧中，出棧操作時間免雜度為0（1）、

5.已知表達式，求它的后綴表達式足棧的典型應用。

6.在一個鏈棧中，若棧頂指針等于NULL,則表示?？铡?/p>

7.向一個棧頂指針為top的鏈棧插入一個新結(jié)點*p時，應執(zhí)行p->ncxt=top;top=p；操作。

8.順序棧S存儲在數(shù)組S->data[。…MAXLEN-1]中，進棧操作時要執(zhí)行的語句有:S>tcp匕。域S->top+l）

S->data[S->top]=x

9.鏈棧IS,指向棧頂元素的指針是LSAncxt。

10.從一個棧刪除元素時，首先取出棧頂元素，然后再移動棧頂指針。

11.由于鏈棧的操作只在鏈表的頭部進行，所以沒有必要設置一頭結(jié)點。

12.已知順序棧S,在對S進嗤操作之前首先要判斷棧是否滿o

13.已知順序棧S,在對S出戌操作之前首先要判斷棧是否空。

14.若內(nèi)在空間充足，?？梢圆欢x棧滿運算。

15.鏈棧LS為空的條件是I5>ncxt=、l；LL,

16.鏈棧LS的棧頂元素是鏈袋的首元素。

17.同一棧的各元素的類型相同°

18.若進棧的次序是A、B、C、D、E,執(zhí)行3次出棧操作以后，棧頂元素為B。

19.A+B/GD*E的后綴表達式是ABC/+DE*-。

20.4個元素A、B、C、D順序進S棧，執(zhí)行兩次Pop（S㈤運算后，x的值是C0

三、選擇題

1.插入和刪除操作只能在一端進行的線性表，稱為（C）。

A.隊列B.循環(huán)隊列C.棧D.循環(huán)棧

2.設有編號為1,2o3,4的4輛列車，順序進入一個棧結(jié)構(gòu)的站臺，下列不可能的出站順序為（D）o

A.1234B,1243C.1324D.1423

3.如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（B）0

A.必須判別棧是否滿B.必須判別棧是否為空C,必須判別棧元素類型D.?？刹蛔鋈魏闻袆e

精品

4.元素A、B、C、D依次達棧以后，棧頂元素是（D）

A.AB.BC.CD.D

5.順序棧存儲空間的實現(xiàn)使用（B）存儲元素。

A.鏈表B.數(shù)組C.循環(huán)鏈表D.變量

6.在C（或C++）語言中，一個順序棧一旦被聲明,其占用空間的大小（A）o

A.已固定B.不固定C.可以改變D.動態(tài)變化

7.帶頭結(jié)點的鏈棧LS的示意圖如下，棧頂元素是（A）o

IS

A.AB.BD.D

8.

鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是（B）0

A.插入操作更加方便B.通常不會出現(xiàn)棧滿的情況C不會出現(xiàn)?？盏那闆rD.刪除操作更加方便

9.從一個棧頂指針為top的段棧中刪除一個結(jié)點時，用x保存被刪除的結(jié)點，應執(zhí)行下列（d）命令。

A.x=top;top->next;B.top=top->next;x=top->data

C.x=top->data;D.x=top->data;top=top->next

10.在一個棧頂指針為US的鏈找中，將一個S指針所指的結(jié)點入枝，應執(zhí)行下列（B）命令。

A.HS->next=SB.S->ncxt=HS->ncxt;HS->next=S;

C.S->ncxt=HS->ncxt;HS=S;D.S->ncxt=HS=HS->ncxt

11.4元素按A、B、C、D順序進S棧，執(zhí)行兩次Pop（S,期運算后，棧頂元素的值是（B）。

A.AB.BC.CD.D

12.元素A、B、C、D依次逮棧以后，棧底元素是（A）。

A.AB.BC.CD.D

13.經(jīng)過下列棧的運算后，再執(zhí)行ReadTop(s)的值是(A)0

InitStack(s);Push(s,a);Push(s,b);Pob(s);

A.aB.bD.O

14.經(jīng)過下列棧的運算后，x的值是（B）。

InitStack（s）（初始化棧）;Push（s,a）;Push（s,b);RcadTop(s)；Pob(s,x)；

A.aB.bC.lD.O

15.經(jīng)過下列棧的運算后，x的值是(B)。

InitStack(s)(初始化棧);Push(s,a);Pob(s,x);Push(s,b);Pob(s,x)；

B.bD.O

16.經(jīng)過下列棧的運算后,SEmpty⑤的值是(C)。

InitStack(s)(初始化棧)；Push(s,a);Push(s,b);Pob(s,x);Pob(s,x)；

B.bC.lD.O

17.向順序棧中輸入元素時（B）。

A.先存入元素，后移動棧頂指針B.先移動棧頂指針,后存入元素

C.誰先誰后無關緊要D.同時進行

18.初始化一個空間大小為5的順序棧S后，S-Xop的值是（B）。

A.0B.-1C.不再改變D.動態(tài)變化

19.設有一個入棧的次序A、B、C、D、E,則棧不可能的輸出序列是（C）。

A.EDCBAB.DECBAC.DCEABD.ABCDE

精品

20.設有一個順序棧S,元素A、B、C、D、E、F依次進棧，如果6個元素出棧的順序是B、D、C、F、

E、A,則棧的容量至少應是（A）。

A.3B.4C.5D.6

精品

第4章隊列

一、判斷題

1.隊列是限制在兩端進行操作的線性表。（M）

2.判斷順序隊列為空的標準是頭指針和尾指針都指向同一個結(jié)點。（M）

3.在鏈隊列上做出隊操作時，會改變front指針的值。（X）

4.在循環(huán)隊列中，若尾指針rear大于頭指針front,其元素個數(shù)為rear-front。（M）

5.在單向循環(huán)鏈表中，若頭指針為h,那么p所指結(jié)點為尾結(jié)點的條件是p二h。（X）

6.鏈隊列在一定范圍內(nèi)不會出現(xiàn)隊滿的情況。（M）

7.在循環(huán)鏈隊列中無溢出現(xiàn)象。（X）

8.棧和隊列都是順序存儲的線性結(jié)構(gòu)。（X）

9.在隊列中允許刪除的一端稱為隊尾。（X）

10.順序隊和循環(huán)隊關于隊滿和隊空的判斷條件是一樣的。（X）

二、填空題

1.在隊列中存取數(shù)據(jù)應遵循的原則是先進先出。

2.隊列是被限定為只能在袤的一端進行插入運算,在表的另一端進行刪除運算線性表。

3.在隊列中，允許插入的一端稱為隊尾。

4.在隊列中，允許刪除的一端稱為隊首（或隊頭）。

5.隊列在進行出隊操作時，首先要判斷隊列是否為空。

6.順序隊列在進行入隊操作時，首先在判斷隊列是否為滿°

7.順序隊列初始化后，初始化后，front=rcar=l0

8.解決順序隊列“假溢出”的方法是采用循環(huán)隊列°

9.循環(huán)隊列的隊指針為front,隊尾指針為rear,則隊空的條件為front==rear0

10.鏈隊列LQ為空時，LQ->front->next=NULL

11.設長度為n的鏈隊列用單循環(huán)表表示，若只設頭指針，則入隊操作的時間復雜度為0（0。

12.設長度為n的鏈隊列用單循環(huán)表表示，若只設尾指針，則入隊操作的時間復雜度為。⑴。

13.在一個鏈隊列中，若隊首指針與隊尾指針的值相同，則表示該隊列為空.

14.設循環(huán)隊列的頭指針front指向隊首元素，尾指針rear指向隊尾元素后的一個空閑元索，隊列的最大

空間為MAXLEN,則隊滿標志為front=二（rear+l）%MAXLEN。

15.在一個鏈隊列中,若隊首指針為front,隊尾指針為rear,則判斷隊列只有一個結(jié)點的條件為front二二rear

或front!。

16.向一個循環(huán)隊列中插入元素時，首先要判斷隊尾指針，然后再向指針所指的位置寫入新的數(shù)據(jù)。

17.讀隊首元素的操作不改變或不影響隊列元素的個數(shù)。

1&設循環(huán)隊列的容量為40（序號0?39）,現(xiàn)經(jīng)過一系列的入隊和出隊的運算后,front=1l,rear=19,則

循環(huán)隊列中還有8個元素。

經(jīng)過下列運算：InitQucue（Q）（初始化隊列）；InQueue（Q,a）；InQueue（Q,b）;OutQueue（Q,x）;

ReadFront（Q,x）;QEmpty（Q）;后的值是8。

20.隊列Q經(jīng)過InitQucue（Q）：初始化隊列）；InQucue（Q,a）；lnQueue（Q,b）；ReadFront（Q,x）后，x的值是___

三、選擇題

1.隊列是限定在（D）進行操作的線性表。

A.中間者B?隊首C.隊尾D.端點

2.隊列中的元素個數(shù)是（B）。

A.不變的B.可變的C.任意的D.0

精品

3.同一隊列內(nèi)的各元素的類型（A）。

A.必須一致B.不能一致C.可以不一致D.不限制

4.隊列是一個（C）線性表結(jié)構(gòu)。

A.不加限制的B.推廣了的C.加了限制的D.非

5.當利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最后一個元素的下標為（B）o

A.n-2B.n-1C.nD.n+1

6.一個循環(huán)隊列一旦說明，其占用空間的大?。ˋ）。

A.已固定B.可以變動C.不能固定D.動態(tài)變化

7.循環(huán)隊列占用的空間（A）。

A.必須連續(xù)B.不必連續(xù)C.不能連續(xù)D.可以不連續(xù)

8.存放循環(huán)隊列元素的數(shù)組data有10個元素，則data數(shù)組的下標范圍是（B）。

A.0?10B.0?9C.1-9D.1?10

9.若進隊的序列為A、B、C、D,則出隊的序列是（C）o

ABC、D、AB.A、C、B、DC.A、B、C、DD.C、B、D、A

10.4個元素按A、B、C、D順序連續(xù)進隊Q,則隊尾元素是（D）

A.AB.13C.CD.D

11.4個元素按A、B、C、D順序連續(xù)進隊Q,執(zhí)行一次QutQueuc（Q）操作后，隊頭元素是（B）。

A.AB.BC.CD.D

12.4個元素按A、B、C、D順序連續(xù)進隊Q,執(zhí)行4次Q“Queue（Q）操作后，再執(zhí)行QEmpty（Q）;后的

值是（B）o

A.0B.lC.2D.3

13.隊列Q,經(jīng)過下列運算后，x的值是(B)。InitQucuc(Q)(初始化隊列)；InQueue(Q,a)；InQucuc(Q.b);

OutQueue(Q,x);ReadFrort(Q,x);

A.aB.bC.OD.l

14.循環(huán)隊列SQ隊滿的條件是(B)o

A.SQ->rear==SQ->frontB.(SQ->rear+1)%MAXLEN==SQ->front

C.SQ->rcar==0D.SQ->front==0

15.設鏈棧中結(jié)點的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針，若想在鏈棧的棧頂插入一

個由指針$所指的結(jié)點，則應執(zhí)行下列（A）操作。

A.s->next=top->next;top->next=s;B.top->next=s;

C.s->next=top;top->next;D.s->next=top;top=s;

16.帶頭結(jié)點的鏈隊LQ示意圖如下，鏈隊列的隊頭元素是（A）。

LQ->rear

A.AB.BC.CD.D

17.帶頭結(jié)點的鏈隊列LQ示意圖如下，指向鏈隊列的隊頭指針是（C）。

精品

LQ->rear

A.LQ->frontB.T,Q->rearC.T?Q->front->nextD.LQ->rcar->ncxt

18.帶頭結(jié)點的鏈隊列LQ示意圖如下，在進行進隊的運算時指針LQ->frnot(A).

LQ->front

H------->A------->B------->C------->DA

LQ->rear

A.始終不改變B.有時改變C.進隊時改變D.出隊時改變

19.隊列Q,經(jīng)過下列運算后，再執(zhí)行QEmpty(Q)的值是(C：io

lnitQucuc(Q)(初始化隊列)；lnQucuc(Q,a)；lnQucuc(Q,b)；OutQucuc(Q^)；RcadQucuc(Q,x);

A.aB上C.OD.l

20.若用一個大小為6數(shù)組來實現(xiàn)循環(huán)隊列，且當前front和rear的值分別為3和0,當從隊列中刪除一個元

素，再加入兩個元素后，front和rear的值分別為(B)e

A.5和1B.4和2C.2和4D.1和5

精品

第5章串

一、判斷題

1.串是n個字母的有限序列。（X）

2.串的數(shù)據(jù)元素是一個字符。（M）

3.串的長度是指串中不同字符的個數(shù)。（X）

4.如果兩個串含有相同的字符，則說明它們相等。（X）

5.如果一個串中所有的字母均在另一個串中出現(xiàn)，則說明前者是后者的子串。（X）

6.串的堆分配存儲是一種動態(tài)存儲結(jié)構(gòu)。（M）

7.“DT”是“DATA”的子串。（X）

8.串中任意個字符組成的子序列稱為該串的子串。（X）

9.子串的定位運算稱為模式匹配。（M）

10.在鏈串中為了提高存儲密度，應該增大結(jié)點的大小。（，）

二、填空題

1.由零個或多個字符組成的有限序列稱為字符串（或串）。

2.字符串按存儲方式可以分為順序存儲、鏈接存儲和堆分配存儲°

3.串的順序存儲結(jié)構(gòu)簡稱為順序串。

4.由順序存儲非緊湊格式的缺點是一空間利用率低。

5.串順序存儲緊湊格式的缺點是對串的字符處理效率低。

6.串鏈接存儲的優(yōu)點是插入、刪除方便，缺點是空間利用率。

7.在C或C++語言中，以字符_義_表示串值的終結(jié)。

8.空格串的長度等于空格的個數(shù)。

9.在空串和空格串中，長度不為0的是一空格串。

10.兩個串相等是指兩個串長度相等，且對應位置的字符都相同。

11.設“S=MyMusic"，則l￡nStr（s）=8。

12.兩個字符串分別為；S產(chǎn)"Todayis"、S2="30July,2（X）5",ConcatStrCS.,S2）的結(jié)果是Todayis30

July,2005。

13.求子串函數(shù)SubStr（"Todayis30July,2005”,13,4）的結(jié)果是July。

14.在串的運算中，EqualStr（f^ia,aab）的返回值<0。

15.在串的運算中，EqualStrQaaaa）的返回值0。

16.在子串的定位運算中，被匹配的主串稱為目標串，子串稱為模式。

17.模式匹配成功的起始位置稱為有效位移。

18.設S="abccdcdccbaaw,T="cdcc",則第6次匹配成功。

19.設S="c:/mydocumcnt/texrl.docw,T="mydont",則字符定位的位置為。。

20.若n為主串長度，m為子串長度，n?m,則模式匹配算法最壞情況下的時間復雜度為（n-m+l）*m。

三、選擇題

1.串是和種特殊的線性表，其特殊體現(xiàn)在（B）o

A.可能順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字

符

2.某串的長度小于一常數(shù)，則采用（B）存儲方式最節(jié)省空間。

A.鏈式B.順序C.堆結(jié)構(gòu)D.無法確定

3.以下論述正確的是（C）o

A.空串與空格串是相同的B.“tel"是“Teleptone"的子串

C.空串是零個字符的串D.空串的長度等于1

精品

4.以下論述正確的是(B)o

A.空串與空格串是相同的B."ton"是“Teleptone”的子串

C.空格串是有空格的串D.空串的長度等于1

5.以下論斷正確的是(A)。

A.全部由空格組成的串是空格串B."BEUIJING"是“BEIJING”的子串

C.something"<"Something"D.BIT"="BITE"

6.設有兩個串&和S2,則EqualStr(S),S2)運算稱作(D)o

A.串連接B.模式匹配C.求子串D.串比較

7.串的模式匹配是指⑴)。

A.判斷兩個串是否相等B.對兩個串比較大小

C.找某字符在主串中第一次出現(xiàn)的位置D.找某子串在主串中第一次出現(xiàn)的第一個字符位置

8.若字符串"ABCDEFG”采用鏈式存儲，假設每個字符占用1個字節(jié)，每個指針占用2個字節(jié)。則該

字符串的存儲密度為(D)。

A.20%B.40%C.50%D.33.3%

9.若字符串"ABCDEFG”采用鏈式存儲，假設每個指針占用2個字節(jié)，若希望存儲密度為50%,則每

個結(jié)點應存儲(A)個字符。

A.2B.3C.4D.5

w

10.設串S產(chǎn)“1AM”,S2=ASDUDENT”,則ConcatStr(S]，S*=(B)。

A."IAM"B.”IAMASDUDENT”C.”IAMASDUDENT”D.”A

SDUDENT”

11.設S=""，則LenStr(S尸(A)o

A.OB.lC.2D.3

12.設目標串T二"AABBCCDDE"，模式P二"ABCDE”,則該模式匹配的有效位移為(A)。

A.OB.lC.2D.3

13.設目標串T二"AABBCCDDEEFF”,模式P二"CCD"，則該模式匹配的有效位移為(D)。

A.2B.3C.4D.5

14.設目標串T="aabaababaabaa"，模式P二"abab”，模式匹配算法的外層循環(huán)進行了(D)次。

A.lB.9C.4D.5

15.模式匹配算法在最壞情況下的時間復雜是(D)。

A.O(m)B.()(n)C.()(m+n)D.O(mXn)

16.S二"morning”，執(zhí)行求子串函數(shù)SubSur(S,2,2)后結(jié)果為(B)。

A.moD.orC.inL).ng

17.S[="good",S?"morning",執(zhí)行串連接函數(shù)ConcatSrr(S],S*后結(jié)果為(A)o

A.”goodmorningwB."goodmorning"C.