《數(shù)據(jù)結(jié)構(gòu)習(xí)題集.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)習(xí)題集.doc（42頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
第一章 緒論
一、選擇題
1. 算法的計(jì)算量的大小稱為計(jì)算的（ ）。
A．效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度
2. 算法的時(shí)間復(fù)雜度取決于（ ）
A．問(wèn)題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B
3.計(jì)算機(jī)算法指的是（1），它必須具備（2） 這三個(gè)特性。
(1) A．計(jì)算方法 B. 排序方法
C. 解決問(wèn)題的步驟序列 D. 調(diào)度方法
(2) A．可執(zhí)行性、可移植性、可擴(kuò)充性 B. 可執(zhí)行性、確定性、有窮性
C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性
4．一個(gè)算法應(yīng)該是（ ）。
A．程序 B．問(wèn)題求解步驟的描述 C．要滿足五個(gè)基本特性 D．A和C.
5. 下面關(guān)于算法說(shuō)法錯(cuò)誤的是（ ）
A．算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)
B.為解決某問(wèn)題的算法同為該問(wèn)題編寫的程序含義是相同的
C. 算法的可行性是指指令不能有二義性
D. 以上幾個(gè)都是錯(cuò)誤的
6. 下面說(shuō)法錯(cuò)誤的是（ ）
(1)算法原地工作的含義是指不需要任何額外的輔助空間
（2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法
（3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界
（4）同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低
A．(1) B.(1),(2) C.(1),(4) D.(3)
7．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。
A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)
C．線性結(jié)構(gòu)、非線性結(jié)構(gòu) D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)
8．以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（ ）。
A．循環(huán)隊(duì)列 B. 鏈表 C. 哈希表 D. 棧
9．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（ ）？
A．廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串
10．以下那一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？（ ）
A．棧 B. 哈希表 C. 線索樹 D. 雙向鏈表
11．線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（①）。
A．必須是連續(xù)的 B．部分地址必須是連續(xù)的
C．一定是不連續(xù)的 D．連續(xù)或不連續(xù)都可以
12．在以下的敘述中，正確的是（①）。
A．線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)
B．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表
C．棧的操作方式是先進(jìn)先出
D．隊(duì)列的操作方式是先進(jìn)后出
13．以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型（ ）
A．棧 B．廣義表 C．有向圖 D．字符串
14．以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)
A．樹 B．字符串 C．隊(duì) D．棧
15. 下列數(shù)據(jù)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)。
A．棧 B. 隊(duì)列 C. 完全二叉樹 D. 堆
16．連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（ ）。
A．一定連續(xù) B．一定不連續(xù) C．不一定連續(xù) D．部分連續(xù)，部分不連續(xù)
17．以下屬于邏輯結(jié)構(gòu)的是（ ）。
A．順序表 B. 哈希表 C.有序表 D. 單鏈表
18.一個(gè)數(shù)據(jù)對(duì)象是（ ）的集合。
A.相同類型的數(shù)據(jù)項(xiàng) B.相同類型的數(shù)據(jù)元素
C.不同類型的數(shù)據(jù)項(xiàng) D.不同類型的數(shù)據(jù)元素
19. ( )是數(shù)據(jù)的基本單位。
A.數(shù)據(jù)項(xiàng) B.關(guān)鍵字 C.數(shù)據(jù)元素 D.數(shù)據(jù)類型
20.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)( )。
A.對(duì)象 B.的存儲(chǔ)結(jié)構(gòu) C.類型 D.元素
21.下列程序段的時(shí)間復(fù)雜度為( )。
{ for(i=0；i<5；i++)
for(j=0；j
1)
sum=1；
for (i=0;sum=i;j--)
s;
11.下面程序段中帶下劃線的語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)是：
i：=1； WHILE i0）。
A．表元素 B．字符 C．?dāng)?shù)據(jù)元素
D．?dāng)?shù)據(jù)項(xiàng) E．信息項(xiàng)
4．若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。
A．順序表 B．雙鏈表
C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D．單循環(huán)鏈表
5．某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。
A．單鏈表 B．僅有頭指針的單循環(huán)鏈表
C．雙鏈表 D．僅有尾指針的單循環(huán)鏈表
6．設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用( )最節(jié)省時(shí)間。
A. 單鏈表 B.單循環(huán)鏈表
C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表
7．若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。
A．單鏈表 B．雙鏈表
C．單循環(huán)鏈表 D．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表
8. 靜態(tài)鏈表中指針表示的是（ ）.
A． 內(nèi)存地址 B．?dāng)?shù)組下標(biāo)
C．下一元素地址 D．左、右孩子地址
9. 鏈表不具有的特點(diǎn)是（ ）
A．插入、刪除不需要移動(dòng)元素 B．可隨機(jī)訪問(wèn)任一元素
C．不必事先估計(jì)存儲(chǔ)空間 D．所需空間與線性長(zhǎng)度成正比
10. 下面的敘述不正確的是（ ）
A．線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比
B. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)
C. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i 的值成正比
D. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)
11． 雙向鏈表中有兩個(gè)指針域，llink和rlink分別指向前趨及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，現(xiàn)要求刪去p所指結(jié)點(diǎn)，則正確的刪除是（ ）（鏈中結(jié)點(diǎn)數(shù)大于2，p不是第一個(gè)結(jié)點(diǎn)）
A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p);
B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink;
C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink;
D．以上A，B，C都不對(duì)。
12.(1) 靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元素的時(shí)間與i無(wú)關(guān)。
(2) 靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。
(3) 靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)。
以上錯(cuò)誤的是（ ）
A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）
13. 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ ）(1<=i<=n+1)。
A. O(0) B. O(1) C. O(n) D. O(n2)
14. 對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。
A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
15．線性表（ a1,a2,…,an）以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為（ ）
A．O（i） B．O（1） C．O（n） D．O（i-1）
16．非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p↑滿足（ ）。
A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head
17．循環(huán)鏈表H的尾結(jié)點(diǎn)P的特點(diǎn)是（ ）。
A．P^.NEXT:=H B．P^.NEXT:= H^.NEXT
C．P:=H D．P:=H^.NEXT
18．在一個(gè)以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是（）
A. p＾.next=h B. p＾.next=NIL C. p＾.next.＾next=h D. p＾.data=-1
19．完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作是（ ）；
A． p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next;
B． p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.next:=p^.next;
C． s^.priou:=p; s^.next:=p^.next; p^.next:=s; p^.next^.priou:=s ;
D． s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ; p^.next:=s;
20．在雙向循環(huán)鏈表中,在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q所指向的新結(jié)點(diǎn),其修改指針的操作是( )。
注:雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(llink,data,rlink)。 供選擇的答案：
A． p↑.llink：=q； q↑.rlink：=p； p↑.llink↑.rlink：=q；q↑.llink：=q；
B． p↑.llink：=q； p↑.llink↑.rlink：=q ； q↑.rlink：= p； q↑.llink:=p↑.llink；
C． q↑.rlink：=p； q↑.llink：=p↑.llink； p↑.llink↑.rlink：=q; p↑.llink：=q;
D． q↑.llink:=p↑.llink；q↑.rlink:=p； p↑.llink：=q；p↑.llink：=q；
21．在非空雙向循環(huán)鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指的鏈結(jié)點(diǎn)的過(guò)程依次為:
rlink(p) ← q; llink(p) ← llink(q); llink(q) ← p; （ ）
A．rlink(q) ← p B．rlink(llink(q)) ← p C．rlink(llink(p)) ← p D．rlink(rlink(p)) ← p
22． 雙向鏈表中有兩個(gè)指針域，llink和rlink，分別指回前驅(qū)及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為（ ）
A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;
B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink;
C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p;
D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q;
23．在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是（ ）。
A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
24．在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：（ ）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
25．對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ ）
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL
26. 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。
A． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink;
B． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p;
C． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink
D． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink;
二、填空題
1．當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_______存儲(chǔ)結(jié)構(gòu)。
2．線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是________。
3．設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn) , 若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語(yǔ)句:_______； ______;
4．在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)________個(gè)元素。
5．在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是________。
6．對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為________,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為________。
7．根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成________和_______；而又根據(jù)指針的連接方式，鏈表又可分成________和________。
8．在雙向循環(huán)鏈表中,向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是_______、_______、_______、________。
9．在雙向鏈表結(jié)構(gòu)中，若要求在p 指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句：
s^ .next:=p； s^ .prior:= ________；p^ .prior:=s；________:=s；
10.鏈接存儲(chǔ)的特點(diǎn)是利用________來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。
11.順序存儲(chǔ)結(jié)構(gòu)是通過(guò)________表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)________表示元素之間的關(guān)系的。
12. 對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共 ______個(gè)，單鏈 表為_______個(gè)。
13. 循環(huán)單鏈表的最大優(yōu)點(diǎn)是：________。
14. 已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語(yǔ)句是：________
15. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是：________
16. 在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：__
17.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是：________。
18. 在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是：_______。
三、解答題
1．線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)：
（1）如果有 n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？ 為什么？
（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？
2．線性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，在作插入或刪除操作時(shí)，需移動(dòng)大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一定都能夠克服上述三個(gè)弱點(diǎn)，試討論之。
3．若較頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)？為什么？
4．線性結(jié)構(gòu)包括______、______、_______和_______。線性表的存儲(chǔ)結(jié)構(gòu)分成______和______。請(qǐng)用類PASCＡL語(yǔ)言描述這兩種結(jié)構(gòu)。
5．線性表（a1，a2，…，an）用順序映射表示時(shí)，ai和ai+1（1<=i0) ? x* f(x-1):2);}
int i ;
i =f(f(1));
A．2 B. 4 C. 8 D. 無(wú)限遞歸
19. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是( )。
A．a(chǎn)bcd*+- B. abc+*d- C. abc*+d- D. -+*abcd
20. 表達(dá)式3* 2^(4+2*2-6*3)-5求值過(guò)程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（ ），其中^為乘冪 。
A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^-
C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(-
21. 設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。
A．線性表的順序存儲(chǔ)結(jié)構(gòu) B. 隊(duì)列
C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧
22. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（ ）。
A. 僅修改頭指針 B. 僅修改尾指針
C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改
23. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)( )。
A．僅修改隊(duì)頭指針 B. 僅修改隊(duì)尾指針
C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭,隊(duì)尾指針都可能要修改
24. 遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。
A．隊(duì)列 B．多維數(shù)組
C．棧 D. 線性表
25. 假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素,其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。
A．(rear-front+m)%m B．rear-front+1
C．(front-rear+m)%m D．(rear-front)%m
26. 循環(huán)隊(duì)列A[0..m-1]存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是( )。
A. (rear-front+m)%m B. rear-front+1
C. rear-front-1 D. rear-front
27. 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
28. 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？( )
A. 1和 5 B. 2和4
C. 4和2 D. 5和1
29. 已知輸入序列為abcd 經(jīng)過(guò)輸出受限的雙向隊(duì)列后能得到的輸出序列有（ ）。
A. dacb B. cadb C. dbca D. bdac E. 以上答案都不對(duì)
30. 若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是( )。
A. 1234 B. 4132
C. 4231 D. 4213
31. 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是 （ ）。
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front
32. 棧和隊(duì)列的共同點(diǎn)是（ ）。
A. 都是先進(jìn)先出 B. 都是先進(jìn)后出
C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)
33. 棧的特點(diǎn)是（ ① ）,隊(duì)列的特點(diǎn)是（ ② ）,棧和隊(duì)列都是（ ③ ）。若進(jìn)棧序列為1,2,3,4 則（ ④ ）不可能是一個(gè)出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為1,2,3,4 則（ ⑤ ）是一個(gè)出隊(duì)列序列。
①, ②: A. 先進(jìn)先出 B. 后進(jìn)先出
C. 進(jìn)優(yōu)于出 D. 出優(yōu)于進(jìn)
③: A.順序存儲(chǔ)的線性結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)
C.限制存取點(diǎn)的線性結(jié)構(gòu) D.限制存取點(diǎn)的非線性結(jié)構(gòu)
④, ⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1
F. 1,2,3,4 G. 1,3,2,4
34. 棧和隊(duì)都是（ ）
A．順序存儲(chǔ)的線性結(jié)構(gòu) B. 鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)
C. 限制存取點(diǎn)的線性結(jié)構(gòu) D. 限制存取點(diǎn)的非線性結(jié)構(gòu)
35. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應(yīng)該是( )。
A． 6 B. 4 C. 3 D. 2
36. 用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（ ）位置。
A．鏈頭 B．鏈尾 C．鏈中
37. 依次讀入數(shù)據(jù)元素序列{a，b，c，d，e，f，g}進(jìn)棧,每進(jìn)一個(gè)元素，機(jī)器可要求下一個(gè)元素進(jìn)?；驈棗＃绱诉M(jìn)行，則?？諘r(shí)彈出的元素構(gòu)成的序列是以下哪些序列？
A．{d ，e，c，f，b，g，a} B. {f，e，g，d，a，c，b}
C. {e，f，d，g，b，c，a} D. {c，d，b，e，f，a，g}
二、填空題
1．棧是_______的線性表，其運(yùn)算遵循_______的原則。
2．_______是限定僅在表尾進(jìn)行插入或刪除操作的線性表。
3. 一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是_______。
4. 設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過(guò)PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_______，而棧頂指針值是_______H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。
5. 當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top[1]與top[2]，則當(dāng)棧1空時(shí)，top[1]為_______，棧2空時(shí) ，top[2]為_______，棧滿時(shí)為_______。
6．兩個(gè)棧共享空間時(shí)棧滿的條件_______。
7．在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否_(1)_;在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否_(2)_；當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為_(3)_。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的空間時(shí)，應(yīng)將兩棧的_(4)_分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_(5)_時(shí)才產(chǎn)生溢出。
8. 多個(gè)棧共存時(shí)，最好用_______作為存儲(chǔ)結(jié)構(gòu)。
9．用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_______。
10. 順序棧用data[1..n]存儲(chǔ)數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_______。
11．表達(dá)式23+((12*3-2)/4+34*5/7)+108/9的后綴表達(dá)式是_______。
12. 循環(huán)隊(duì)列的引入，目的是為了克服_______。
13．用下標(biāo)0開始的N元數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，為實(shí)現(xiàn)下標(biāo)變量M加1后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)， M= _______。
14．________又稱作先進(jìn)先出表。
15. 隊(duì)列的特點(diǎn)是_______。
16．隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是_______。
17. 已知鏈隊(duì)列的頭尾指針?lè)謩e是f和r，則將值x入隊(duì)的操作序列是_______。
18．區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是______和______。
19．設(shè)循環(huán)隊(duì)列用數(shù)組A[1..M]表示，隊(duì)首、隊(duì)尾指針?lè)謩e是FRONT和TAIL，判定隊(duì)滿的條件為_______。
20. 設(shè)循環(huán)隊(duì)列存放在向量sq.data[0:M]中，則隊(duì)頭指針sq.front在循環(huán)意義下的出隊(duì)操作可表示為_______，若用犧牲一個(gè)單元的辦法來(lái)區(qū)分隊(duì)滿和隊(duì)空（設(shè)隊(duì)尾指針sq.rear）,則隊(duì)滿的條件為_______。
三、基礎(chǔ)知識(shí)題
1．名詞解釋：棧。
2．名詞解釋：隊(duì)列
3．什么是循環(huán)隊(duì)列？
4．假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。
（1）試指出判別給定序列是否合法的一般規(guī)則。
（2）兩個(gè)不同合法序列（對(duì)同一輸入序列）能否得到相同的輸出元素序列？如能得到，請(qǐng)舉列說(shuō)明。
5. 有5 個(gè)元素，其入棧次序?yàn)椋篈，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個(gè)且D第二個(gè)出棧）的次序有哪幾個(gè)？
6.如果輸入序列為1 2 3 4 5 6,試問(wèn)能否通過(guò)棧結(jié)構(gòu)得到以下兩個(gè)序列:4 3 5 6 1 2和1 3 5 4 2 6;請(qǐng)說(shuō)明為什么不能或如何才能得到。
7. 若元素的進(jìn)棧序列為：A、B、C、D、E，運(yùn)用棧操作，能否得到出棧序列B、C、A、E、D 和D、B、A、C、E？為什么？
8. 設(shè)輸入序列為a,b,c,d,試寫出借助一個(gè)?？傻玫降膬蓚€(gè)輸出序列和兩個(gè)不能得到的輸出序列。
9. 設(shè)輸入序列為2，3，4，5，6，利用一個(gè)棧能得到序列2，5，3，4，6嗎？?？梢杂脝捂湵韺?shí)現(xiàn)嗎？
10. 試證明：若借助棧由輸入序列1,2,…,n得到輸出序列為P1,P2,…,Pn（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i
下載提示(請(qǐng)認(rèn)真閱讀)
- 1.請(qǐng)仔細(xì)閱讀文檔，確保文檔完整性，對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請(qǐng)點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
9.9
積分
- 配套講稿：
如PPT文件的首頁(yè)顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
-
數(shù)據(jù)結(jié)構(gòu)
習(xí)題集
- 溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請(qǐng)勿作他用。
數(shù)據(jù)結(jié)構(gòu)習(xí)題集.doc
鏈接地址：http://m.appdesigncorp.com/p-9474909.html