大連東軟 數(shù)據(jù)結(jié)構(gòu)題庫

1、精選文檔1.6 習(xí)題 1.6.1 知識點：數(shù)據(jù)結(jié)構(gòu)的定義 一、選擇題 1 數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（ A ）及它們之間的相互聯(lián)系。 A存儲和邏輯結(jié)構(gòu) B存儲結(jié)構(gòu) C順序結(jié)構(gòu) D鏈式存儲結(jié)構(gòu) 2 數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為（ C ） A存儲結(jié)構(gòu) B邏輯結(jié)構(gòu) C 順序存儲結(jié)構(gòu) D鏈式存儲結(jié)構(gòu) 3 線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ D ）。 A一對多關(guān)系 B. 多對多關(guān)系 C 多對一關(guān)系 D 一對一關(guān)系 4 計算機內(nèi)部數(shù)據(jù)處理的基本單位是（ B ）。 A. 數(shù)據(jù) B數(shù)據(jù)元素 C.數(shù)據(jù)項 D數(shù)據(jù)庫 5 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C ）兩大類?！疚錆h交通科技

2、 1996】 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初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)二、填空題 1 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為四大類，它們分別是 集合 、 線性 、 樹 、 圖 。 2 數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是 順序 、 鏈式 、 散列 、 索引 。 三、 判斷題 （ F）1 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 （ T ）2 記錄是數(shù)據(jù)處理的最小單位。 （ F ）3 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系。 （ T ）4 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。 四、 簡答題 1 簡述什么是數(shù)據(jù)結(jié)構(gòu)? 2 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型有什么區(qū)別? 【

3、哈爾濱工業(yè) 2001】 1.6.2 知識點：算法的概念 一、選擇題 1 計算機算法指的是（C ） A計算方法B排序方法 C解決問題的有限運算序列D調(diào)度方法 2 算法分析的目的是（ （1）C ），算法分析的兩個主要方面（ （2）A ） （1） A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中的輸入與輸出的關(guān)系 C分析算法的效率以求改進D分析算法的易查性和文檔性 （2） A空間復(fù)雜度和時間復(fù)雜度B正確性和簡明性 C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 3 設(shè)語句 X+的時間是單位時間，則語句： for（i=1;i=1;i+） for（ j=1;jAj+1） Aj與 Aj+1對換； 其中 n 為正整數(shù)，則最后一

4、行的語句頻度在最壞情況下是（ D ）【南京理工 1998】 AO（n） BO（nlog2 n） C O（n3） D O（n2） 二、填空題 1 以夾雜自然語言和程序語句的形式來描述解決問題的方法稱為_偽碼_。 2 一個算法的效率可分為_時間_效率和_空間_效率 3 有一個程序片斷如下： for（i=0;in;i+） x=x+1; 則其時間復(fù)雜度為：_O（n）_ 4 有一個程序片斷如下： for（i=0;in;i+） for（j=i;jn;j+） for（k=j;kn;k+） m=1; 則其時間復(fù)雜度為： O（n3） 5 有一個程序片斷如下： for（i=0;i=2） j=j/2; 則其時間復(fù)雜

5、度為： O（nlog2 n） 三、 判斷題 （ T ）1 算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。 （ T ）2 健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。 （ F ）3 程序一定是算法。 四、 簡答題 1 如何判斷一個算法的好壞? 2 調(diào)用下列 C 函數(shù) f（n） 回答下列問題 ：（1） 試指出 f（n）值的大小，并寫出 f（n）值的推導(dǎo)過程；（2） 假定 n= 5，試指出 f（5）值的大小和執(zhí)行 f（5）時的輸出結(jié)果。 C 函數(shù)： int f（int n） int i,j，k,sum= 0; for（i=l; ii-1; j-） for（k=1;k0）?！厩迦A 1998

6、】 A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項 E信息項二、判斷題 （ T ）1 線性表中的每個結(jié)點最多只有一個前驅(qū)和一個后繼。 （ F ）2 線性表中的每個結(jié)點都至少有一個前驅(qū)結(jié)點和后繼結(jié)點。 （ F ）3 線性表是 N 個數(shù)的有限序列。 （ F）4 同一線性表的數(shù)據(jù)元素可以具有不同的特性。 （ T ）5 線性表的長度 n 就是表中數(shù)據(jù)元素的個數(shù)，當 n=0 時，稱為空表。 （ T ）6 線性表是一個相當靈活的數(shù)據(jù)結(jié)構(gòu)，它的長度可根據(jù)需要增長或縮短。 （ F ）7 對線性表中的數(shù)據(jù)元素只能進行訪問，不能進行插入和刪除操作。 2.7.2 知識點：線性表的順序存儲結(jié)構(gòu) 一、選擇題 1 在一個長度為

7、n 的順序表中，在第 i 個元素（1 = i =n+1）之前插入一個新元素時需向后移動（ B ）個元素 An-1 Bn-i+1 Cn-i-1 Di 2 若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ D ）存儲方式最節(jié)省時間。 A單鏈表 B雙鏈表 C單向循環(huán) D順序表 3 一個數(shù)組第一個元素的存儲地址是 100，每個元素的長度為 2，則第 5 個元素的地址是（ B ） A110 B108 C100 D120 4 下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點（ A ）?！颈狈浇煌?2001】 A存儲密度大 B插入運算方便 C刪除運算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲表示 5 若長

8、度為 n 的線性表采用順序存儲結(jié)構(gòu)，在其第 i 個位置插入一個新元素的算法的時間復(fù)雜度為（ C ）（1=i=n+1）?！颈本┖娇蘸教?1999】 AO（0） BO（1） CO（n） DO（n 2 ） 6 對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為（ C ）。【青島 2000】 AO（n） O（n） BO（n） O（1） CO（1） O（n） DO（1） O（1） 二、 填空題 1 線性表的順序存儲的缺點是在任意位置上_插入_數(shù)據(jù)與_刪除_數(shù)據(jù)費時間。 2 設(shè)一線性表的順序存儲，總存儲容量為 M，其元素存儲位置的范圍為_0M-1_。 3 向一個長度為 n 的向量中刪除第 i 個

9、元素（1in）時，需向前移動_n-i_個元素。 三、 簡答題 1 已知線性表的存儲結(jié)構(gòu)為順序表，閱讀下列算法，并回答問題： void f30 （SeqList *L） int i，j; for （i=j=0;ilength; i+） if（L-datai=0） if（i!=j）L-dataj=L-datai; j+； L-length=j; （1） 設(shè)線性表 L=（21，-7，-8，19，0，-11，34，30，-10），寫出執(zhí)行 f30（&L）后L狀態(tài)；(21,19,0,34,30) （2） 簡述算法 f30 的功能。刪除順序表中小于 0 的元素四、編程題 1 已知順序表 La 中數(shù)據(jù)元素按

10、非遞減有序排列。試寫一個算法，將 x 插入到 La 的合適位置上，保持該表的有序性。 2.7.3 知識點：線性表的鏈式存儲結(jié)構(gòu) 一、選擇題 1 鏈表是一種采用（ B ）存儲結(jié)構(gòu)存儲的線性表。 A順序 B鏈式 C星式 D網(wǎng)狀 2 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（ A ）。 A分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。 B只有一部分，存放結(jié)點值。 C只有一部分，存儲表示結(jié)點間關(guān)系的指針。 D分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)。 3 線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ D ）。 A必須是連續(xù)的 B部分地址必須是連續(xù)的 C一定是不連續(xù)的

11、D連續(xù)或不連續(xù)都可以 4 線性表在（ B ）情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。 A需經(jīng)常修改中的結(jié)點值 B需不斷對進行刪除插入 C中含有大量的結(jié)點 D中結(jié)點結(jié)構(gòu)復(fù)雜 5 對單鏈表表示法,以下說法錯誤的是（C ）。 A數(shù)據(jù)域用于存儲線性表的一個數(shù)據(jù)元素。 B指針域（或鏈域）用于存放一個指向本結(jié)點所含數(shù)據(jù)元素的直接后繼所在結(jié)點的指針。 C所有數(shù)據(jù)通過指針的鏈接而組織成單鏈表。 DNULL 稱為空指針，它不指向任何結(jié)點只起標志作用。 6 以下說法正確的是（D ）。 A順序存儲方式的優(yōu)點是存儲密度大且插入、刪除運算效率高 B鏈表的每個結(jié)點中都恰好包含一個指針 C線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu) D順序

12、存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)而鏈式結(jié)構(gòu)屬于動態(tài)結(jié)構(gòu) 7 以下說法錯誤的是（D ）。 A求表長、定位這兩種運算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈式存儲結(jié)構(gòu)時實現(xiàn)的效率低 B順序存儲的線性表可以隨機存取 C由于順序存儲要求連續(xù)的存儲區(qū)域,所以在存儲管理上不夠靈活 D線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu) 8 不帶頭結(jié)點的單鏈表 head 為空的判定條件是（ A ）。 Ahead= =NULL Bhead-next= =NULL Chead-next= =head Dhead!=NULL 9 帶頭結(jié)點的單鏈表 head 為空的判定條件是（ B ）。 Ahead= =NULL Bhead-next= =N

13、ULL Chead-next= =head Dhead!=NULL 10 在頭指針為 head 的非空單循環(huán)鏈表中，指針 p 指向尾結(jié)點，下列關(guān)系成立的是（ A ）。 Ap-next= =head Bp-next-next= =head Cp-next= =NULL Dp= =head 11 在一個單鏈表中，已知 q 所指結(jié)點是 p 所指結(jié)點的前驅(qū)結(jié)點，若在 q 和 p 之間插入 s 結(jié)點，則執(zhí)行語句（ C ）。 As-next=p-next;p-next=s; Bp-next=s-next;s-next=p; Cq-next=s;s-next=p; Dp-next=s;s-next=q; 1

14、2 在一個單鏈表中，若 p 所指結(jié)點不是最后結(jié)點，在 p 之后插入 s 結(jié)點，則應(yīng)執(zhí)行語句（ B ）。 As-next=p:p-next=s; Bs-next=p-next;p-next=s; Cs-next=p-next;p=s; Dp-next=s;s-next=p; 13 在一個單鏈表中，若刪除 p 所指結(jié)點的后續(xù)結(jié)點，則應(yīng)執(zhí)行語句（ A ）。 Ap-next=p-next-next; Bp=p-next;p-next=p-next-next; Cp-next=p-next; Dp=p-next-next; 14 指針 p、q 和 r 依次指向某循環(huán)鏈表中三個相鄰的結(jié)點，交換結(jié)點*q 和

15、結(jié)點*r 在表中次序的程序段是（ A ）。 Ap-next=r； q-next=r-next； r-next=q； Bp-next=r； r-next=q； q-next=r-next； Cr-next=q； q-next=r-next； p-next=r； Dr-next=q； p-next=r； q-next=r-next； 15 鏈表不具有的特點是（ B ） 【福州 1998】 A插入、刪除不需要移動元素 B可隨機訪問任一元素C不必事先估計存儲空間 D所需空間與線性長度成正比 16 下面的敘述不正確的是（BC ）【南京理工 1996】 A線性表在鏈式存儲時，查找第 i 個元素的時間同 i

16、 的值成正比 B線性表在鏈式存儲時，查找第 i 個元素的時間同 i 的值無關(guān) C線性表在順序存儲時，查找第 i 個元素的時間同 i 的值成正比 D線性表在順序存儲時，查找第 i 個元素的時間同 i 的值無關(guān) 17 下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ B ）【北方交通 2001】A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 B線性表采用順序存儲，便于進行插入和刪除操作。 C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。 D線性表采用鏈接存儲，便于插入和刪除操作。 18 在一個以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是（A）【南京理工 1998】 Ap-next=h Bp-

17、next=NULL Cp-next-next=h D p-data=-1 19 若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ A）存儲方式最節(jié)省時間?！竟枮I工業(yè) 2001】 A順序表 B雙鏈表 C帶頭結(jié)點的雙循環(huán)鏈表 D單循環(huán)鏈表 20 某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ D）存儲方式最節(jié)省運算時間?！灸祥_ 2000】 A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表 21 設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用（ D ）最節(jié)省時間?！竞戏使I(yè) 2000】 A單鏈表

18、B單循環(huán)鏈表 C帶尾指針的單循環(huán)鏈表 D帶頭結(jié)點的雙循環(huán)鏈表 22 線性表（a1, a 2 ,a n ）以鏈接方式存儲時，訪問第i 位置元素的時間復(fù)雜性為（C ）【中山 1999】 A O（i） BO（1） CO（n） DO（i-1） 23 完成在雙循環(huán)鏈表結(jié)點 p 之后插入 s 的操作是（D ）?！颈狈浇煌?1999】 Ap-next:=s ; s-priou:=p; p-next-priou:=s ; s-next:=p-next; Bp-next-priou:=s; p-next:=s; s-priou:=p; s-next:=p-next; Cs-priou:=p; s-next:=p

19、-next; p-next:=s; p-next-priou:=s ; Ds-priou:=p; s-next:=p-next; p-next-priou:=s ; p-next:=s; 24 在雙向循環(huán)鏈表中,在 p 指針所指向的結(jié)點前插入一個指針 q 所指向的新結(jié)點,其修改指針的操作是（ C ）?！颈本┼]電 1998】【青島 2000】注:雙向鏈表的結(jié)點結(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-rlin

20、k= 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； 25 在雙向鏈表存儲結(jié)構(gòu)中，刪除 p 所指的結(jié)點時需修改指針（ A）?！疚靼搽娮涌萍?1998】 Ap-prior-next=p-next p-next-prior=p-prior; Bp-prior =p- prior- prior p- prior- next=p; Cp- prior- prior:=p p- next=p- n

21、ext - next Dp- next =（p- prior） - prior p- prior=p- next- next 二、填空題 1 線性表的鏈式存儲是用_malloc_語句實現(xiàn)空間單元動態(tài)分配。 2 單鏈表是_線性表_的鏈接存儲表示。 3 頭結(jié)點地址指針為 L 的循環(huán)單鏈表，空表的判別標志是_L-next=NULL_。 4 在一個單鏈表中刪除 p 所指結(jié)點時，應(yīng)執(zhí)行以下操作： q=p-next; p-data=p-next-data; p-next=q-next_; free（q）; 5 下段程序的功能：有一頭指針為 head 的鏈表,將 new 指針指向的節(jié)點插入到 data 域為

22、 7 的節(jié)點的后邊。將程序補充完整。 P = head; while（P != NULL） if （P -data = 7） /*找到位置插入結(jié)點后跳出循環(huán)*/ （1）_new-next=p-next_; （2） _p-next=new_; （3） _break_ ; else （4）_p=p-next_; /*指針后移*/ if（P = NULL） printf（“n the position isnt exist! ”）; 6 假設(shè)某個不設(shè)頭指針的無頭結(jié)點單向循環(huán)鏈表的長度大于 1，s 為指向鏈表中某個結(jié)點的指針。算法 f 30 的功能是，刪除并返回鏈表中指針 s 所指結(jié)點的前驅(qū)。請在空缺

23、處填入合適的內(nèi)容，使其成為完整的算法。 typedef struct node DataType data； struct node *next； *LinkList； DataType f 30（LinkList s） LinkList pre，p； DataType e； pre=s； p=s-next； while（1）_p-next!=s_ ） pre=p; （2）p=p-next_ ; pre -next=（3）_p-next_ ; e=p-data; free（p）; return e; 三、 判斷題 （F ）1 單鏈表從任何一個結(jié)點出發(fā)，都能訪問到所有結(jié)點。 （ F ）2 線性表

24、的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。 四、 簡答題 1 描述以下幾個概念：順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、順序表、有序表。 2 描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點。在單鏈表中設(shè)置頭結(jié)點的作用是什么？ 3 線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表，試問： (1)如果有 n 個線性表同時共存，并且在處理過程中各表的長度會動態(tài)地發(fā)生變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？為什么？鏈表 (2)若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存取結(jié)構(gòu)？為什么？順序表 4 假設(shè)本測試中使用

25、的鏈表如圖 2.45 所示，結(jié)點定義如下： struct List int data; struct List *next; ; typedef struct List Node; typedef Node *Link; Link P,Q,R,S,head; Link pointer,back,new; 對以下單鏈表分別執(zhí)行下列程序段，要求分別畫出結(jié)果圖。 （1） Q=head-next-next; Q 指向 7 （2）R-data=P-data; 3 變 5 （3）R-data=P-next-data; 3 變 7 （4） S=P; while（S-next!=NULL） S-data=S-

26、data*2; S=S-next; 4 10 14 6 8 （5） S=P; while（S!=NULL） S-data=S-data*2; S=S-next; 4 10 14 6 16 5 假設(shè)本測試中使用的鏈表如圖 2.45 所示，結(jié)點定義如第 4 題所示。畫出執(zhí)行如下程序段后各指針及鏈表的示意圖。 head=（Link）malloc（sizeof（Node）; head-data=0; head-next=NULL; P=head; for（i=1;idata=2*i; new-next=NULL; P-next=new; P=new; 創(chuàng)建了一個鏈表，數(shù)據(jù)元素為 0,2,4,6，并且

27、p 和 new 都指向尾結(jié)點 6 有一鏈表如下圖所示，閱讀程序給出程序的輸出結(jié)果。 圖 2.46 6 題圖 P = head; while（P != NULL） printf（“n data=%d”, P - data）; P = P-next; if（ P != NULL） P = P -next; Data=1 Data=3 Data=5 五、編程題 1 一個單鏈表，其頭指針為 head，編寫一個函數(shù)計算數(shù)據(jù)域為 x 的節(jié)點個數(shù)。 2 已知單鏈表 La 中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫出算法，將元素 x 插入到 La 的合適位置上，保持該表的有序性：（1）La 帶頭結(jié)點；

28、（2）La 不帶頭結(jié)點。 3 試寫一個算法，實現(xiàn)順序表的就地逆置，即在原表的存儲空間將線性表（a1,a 2 ,an1,a n ）逆置為（a n ,a n1, a 2 ,a1）。 4 設(shè)計一個算法，求 A 和 B 兩個單鏈表表示的集合的交集、并集合差集。 3.7 習(xí)題 3.7.1 知識點：棧的基本概念 一、選擇題 1 下列哪種數(shù)據(jù)結(jié)構(gòu)常用于函數(shù)調(diào)用（ A ）。 棧 隊列 鏈表 數(shù)組 2 編譯器中通常以哪種數(shù)據(jù)結(jié)構(gòu)處理遞歸程序調(diào)用（ C ） 隊列 數(shù)組 C棧 D記錄 3 下列哪些數(shù)據(jù)結(jié)構(gòu)可用來實現(xiàn)棧（ D ）。 （1）鏈表 （2）數(shù)組 （3）樹 （4）圖 （2），（3） （2），（4） C（1），

29、（4） D（1），（2） 4 元素的入棧序列是 a,b,c,d，則棧的不可能的輸出序列是（ C ）。 Adcba Babcd Cdcab Dcbad 5 已知棧的最大容量為 4。若進棧序列為 1，2，3，4，5，6，且進棧和出?？梢源┎暹M行,則可能出現(xiàn)的出棧序列為（ C ）。 A5，4，3，2，1，6 B2，3，5，6，1，4 C3，2，5，4，1，6 D1，4，6，5，2，3 6 若以 S 和 X 分別表示進棧和退棧操作，則對初始狀態(tài)為空的棧可以進行的棧操作系列是（ D ）。 ASXSSXXXX BSXXSXSSX CSXSXXSSX DSSSXXSXX 7 對于棧操作數(shù)據(jù)的原則是（ B ）

30、?！厩鄭u 2001】 A 先進先出 B后進先出 C后進后出 D不分順序 8 棧在（ D ）中應(yīng)用?！局猩?1998】 A遞歸調(diào)用 B子程序調(diào)用 C表達式求值 DA， 9 一個棧的輸入序列為 123n，若輸出序列的第一個元素是 n，輸出第 i（1=itop！=0 ST-top= =0 ST-top！=m0 ST-top= =m0 4 鏈表仿真堆棧時，?？盏臈l件是（B ）。 Atopmaxsize-1 Btop= =NULL C沒有限制 Dtop0 5 鏈表仿真堆棧時，棧滿的條件是（ C）。 Atopmaxsize-1 Btop= =NULL C沒有限制 Dtopnext=stack-next；

31、stack=new； new-next=stack； stack=new；new-next=stack；stack=new-next； stack=new；stack-next=new-next； 7 若一個棧以向量 V1n存儲，初始棧頂指針 top 為 n+1，則下面 x 進棧的正確操作是（ C ）?！灸暇├砉?1998】 Atop=top+1; V top=x BV top =x; top=top+1 Ctop=top-1; V top=x DV top=x; top=top-1 8 執(zhí)行完下列語句段后，i 值為：（ B）?！菊憬?2000】 int f（int x） return （x0

32、） ? x* f（x-1）:2）; int i ; i =f（f（1）; A 2 B 4 C 8 D 無限遞歸 二、 填空題 1 以下語句是堆棧的入棧操作，用全局數(shù)組 stack 仿真堆棧，數(shù)組類型是 int，大小是 MaxSize，棧頂指針是 top，初始化等于1。 01 void push（int value） 02 03 if（topMaxSize-1） 04 return 1; 05 else 06 07 top+; 08 stacktop=value; 09 10 指出有錯誤的語句：_3_ 寫出改正后的語句：_ top=MaxSize-1_ 2 以下語句是數(shù)據(jù)從堆棧中取出操作,top

33、 為棧頂指針,stack 為堆棧數(shù)組。 01 int pop（） 02 03 int temp; 04 if（top0） 05 return 1; 06 else 07 08 temp = stacktop; 09 top ; 10 11 return temp; 12 指出有錯誤的語句：_ 寫出改正后的語句：_8,9 互換_ 三、 編程題 1 假設(shè)一個算術(shù)表達式中可以包含圓括號“（”和“）”，編寫判別給定表達式中所含括號是否正確配對出現(xiàn)的算法。 2 編寫斐波那契（Fibonacci） 數(shù)列的遞歸算法和迭代算法。 F0 = 0,F1 =1, F Fn= n 1 +F nn 2( = 2)3.7

34、.3 知識點：隊列的基本概念及其應(yīng)用 一、選擇題 1 下列哪種數(shù)據(jù)結(jié)構(gòu)常用于系統(tǒng)程序的作業(yè)調(diào)度（ B ） A棧 B隊列 C鏈表 D數(shù)組 2 在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū), 主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機則從該緩沖區(qū)中取出數(shù)據(jù)打印該緩沖區(qū)應(yīng)該是一個（ B ）結(jié)構(gòu) A堆棧 B隊列 C數(shù)組 D線性表 3 設(shè)棧 S 和隊列 Q 的初始狀態(tài)為空，元素 e1、e2、e3、e4、e5、e6 依次通過棧 S，一個元素出棧后即進入隊列 Q，若 6 個元素出隊的序列是 e2、e4、e3、e6、e5、e1，則棧 S 的容量至少應(yīng)該是（ C ） A6 B4 C3

35、 D2 4 棧和隊列的共同點是（ C ）?！狙嗌?2001 一、1（2 分）】 A 都是先進先出B都是先進后出 C 只允許在端點處插入和刪除元素D 沒有共同點二、填空題 1 棧和隊列都是線性結(jié)構(gòu)，對于棧只能在_棧頂_ 位置插入和刪除元素，對于隊列只能在_隊尾_位置插入元素和_隊頭_位置刪除元素。 2 隊列的隊尾位置通常是隨著_入隊_操作而變化的。 3 隊列的特點是_先進先出_。【北京理工 2000】 4 循環(huán)隊列的引入，目的是為了克服_假溢出_?！緩B門 2001】三、判斷題 （ T ）1 隊列中所有的插入操作都發(fā)生在表的一端，刪除則發(fā)生在表的另一端。 （ F ）2 隊列為先進后出的結(jié)構(gòu)。 （

36、F ）3 隊列必須用數(shù)組來表示。 （ T ）4 隊列用于操作系統(tǒng)中的作業(yè)調(diào)度。 （ T ）5 棧和隊列邏輯上都是線性表。 （ T ）6 棧和隊列是在程序中常用的兩種數(shù)據(jù)結(jié)構(gòu)。 （ T ）7 棧與隊列是一種特殊操作的線性表?！厩鄭u 2001】 （ T ）8 棧和隊列都是限制存取點的線性結(jié)構(gòu)?！局锌圃很浖?1999】 （ F）9 隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)?！旧虾：＿\ 1998】 （ F ）10 通常使用隊列來處理函數(shù)或過程的調(diào)用?！灸暇┖娇蘸教?1997】 （ F ）11 隊列邏輯上是一個下端和上端既能增加又能減少的線性表。【上海交通 1998】

37、（ T ）12 棧和隊列都是線性表，只是在插入和刪除時受到了一些限制?！颈本┼]電 2002】四、簡答題 1 什么是隊列？試舉兩個應(yīng)用實例。 2 說明線性表、棧和隊列的異同點。 3 順序隊的“假溢出”是怎樣產(chǎn)生的？什么是循環(huán)隊列？如何知道循環(huán)隊列是空還是滿？ 五、編程題 1 假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如abba和abcba是回文，abcde 和ababab則不是回文。試寫一個算法判別讀入的一個以為結(jié)束符的字符序列是否是“回文”。 3.7.4 知識點：隊列的存儲一、選擇題 1 循環(huán)隊列用數(shù)組 Amaxsize 表示，下面哪個選項表示該循環(huán)隊列隊滿（ B ） rear= =max

38、size-1 B front= =（rear+1）%maxsize C rear-front= =maxsize D rear-front= =maxsize-1 2 在用數(shù)組 queuemaxsize仿真隊列時（temp 為 int 型變量），假設(shè)隊列中至少有一個元素，出隊列操作應(yīng)執(zhí)行以下（ D ） Atemp=queuerear; rear-; B rear+; temp=queuerear; Ctemp=queuefront; front-; D front+; temp=queuefront; 3 數(shù)組用來表示一個循環(huán)隊列，為當前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的

39、個數(shù)小于，計算隊列中元素的公式為（ D ） rf; （nfr）% n; nrf （nrf）% n 4 判斷一個隊列 QU（最多元素為 m0）為空的條件是（ C ）。 Arear- front= =m0 Brear- front-1= =m0 Cfront= = rear Dfront= = rear+1 5 一個隊列（數(shù)組仿真，最多元素為 MaxSize）下列哪個選項表示了隊列空間全部被利用？（ A ） Arear front = = MaxSize Brear front = = MaxSize 1 Crear = = front Drear + 1 = = front 6 判定一個循環(huán)隊列（數(shù)組仿真，最多元素為 MaxSize）為空的條件是？（ A ） Afront = = rear Bfront != rear Cfront = = （rear + 1）%MaxSize Dfront != （rear + 1）%MaxSize 7 用單鏈表表示的鏈式隊列的隊頭在鏈表的（ A ）位置?！厩迦A 1998】 A鏈頭 B鏈尾 C鏈中 D任何 8 用不帶頭結(jié)點的單鏈表存儲隊列時,其隊頭指針指向隊頭結(jié)點,其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時（ D ）?！颈本├砉?2001】 A僅修改隊頭指針 B僅修