大連東軟數(shù)據(jù)結構題庫

1、WORD格式1.6 習題1.6.1 知識點：數(shù)據(jù)構造的定義一、選擇題1數(shù)據(jù)構造通常是研究數(shù)據(jù)的A 及它們之間的相互聯(lián)系。A存儲和邏輯構造 B存儲構造 C順序構造D鏈式存儲構造2數(shù)據(jù)在計算機存儲器內表示時，物理地址與邏輯地址一樣并且是連續(xù)的，稱之為C A存儲構造B邏輯構造C順序存儲構造 D 鏈式存儲構造3線性構造是數(shù)據(jù)元素之間存在一種D 。A一對多關系B. 多對多關系 C 多對一關系 D 一對一關系4計算機內部數(shù)據(jù)處理的根本單位是B 。A. 數(shù)據(jù) B數(shù)據(jù)元素C.數(shù)據(jù)項D 數(shù)據(jù)庫5從邏輯上可以把數(shù)據(jù)構造分為C 兩大類。【*交通科技1996】A動態(tài)構造、靜態(tài)構造B順序構造、鏈式構造C線性構造、非線性

2、構造D初等構造、構造型構造二、填空題1數(shù)據(jù)構造按邏輯構造可分為四大類，它們分別是集合、 線性、 樹、 圖 。2數(shù)據(jù)的存儲構造可用四種根本的存儲方法表示，它們分別是順序、 鏈式、 散列、索引。三、判斷題（ F 1數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ T 2記錄是數(shù)據(jù)處理的最小單位。（ F 3數(shù)據(jù)的邏輯構造是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。（ T 4數(shù)據(jù)的物理構造是指數(shù)據(jù)在計算機內的實際存儲形式。四、簡答題1簡述什么是數(shù)據(jù)構造"2數(shù)據(jù)構造與數(shù)據(jù)類型有什么區(qū)別" 【*工業(yè)2001】1.6.2 知識點：算法的概念一、選擇題1計算機算法指的是CA計算方法B 排序方法C解決問題的有限運算序列D

3、調度方法2算法分析的目的是 1 C ，算法分析的兩個主要方面 2A 1A 找出數(shù)據(jù)構造的合理性B研究算法中的輸入與輸出的關系C分析算法的效率以求改進D分析算法的易查性和文檔性 2A 空間復雜度和時間復雜度B正確性和簡明性C可讀性和文檔性D數(shù)據(jù)復雜性和程序復雜性3設語句 X+ 的時間是單位時間，那么語句：for i=1;i<=n;i+x+;專業(yè)資料整理WORD格式時間復雜度為 C 。A O 1 B O n C O n2 D O n34算法的計算量的大小稱為計算的B ?！距]電 2000】A效率 B復雜性 C現(xiàn)實性 D難度5算法的時間復雜度取決于C 【中科院計算所1998】A問題的規(guī)模 B待處

4、理數(shù)據(jù)的初態(tài) CA 和 B6下面關于算法說法錯誤的選項是A 【*理工2000】A算法最終必須由計算機程序實現(xiàn)B為解決某問題的算法同為該問題編寫的程序含義是一樣的C算法的可行性是指指令不能有二義性D以上幾個都是錯誤的7下面說法錯誤的選項是 D 【*理工2000】 1算法原地工作的含義是指不需要任何額外的輔助空間 2在一樣的規(guī)模 n 下，復雜度 O n的算法在時間上總是優(yōu)于復雜度O 2n的算法（ 3 所謂時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界（ 4 同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低A 1B 1, 2C 1, 4D 38程序段 for i=n-1;i>=1;i+ f

5、or j=1;j<= i;j+if Aj>Aj+1Aj 與 Aj+1對換；其中 n 為正整數(shù)，那么最后一行的語句頻度在最壞情況下是D 【*理工1998】AOn BOnlog nO3 D O2nn2 C二、填空題1以夾雜自然語言和程序語句的形式來描述解決問題的方法稱為_偽碼 _。2一個算法的效率可分為_時間 _ 效率和 _空間 _效率3有一個程序片斷如下：for i=0;i<n;i+ x=x+1;那么其時間復雜度為：_O n _4有一個程序片斷如下：for i=0;i<n;i+ for（ j=i;j<n;j+ for k=j;k<n;k+ m=1;那么其時間復

6、雜度為：O n35有一個程序片斷如下：for i=0;i<n;i+ j=i;while j>=2 j=j/2;那么其時間復雜度為：O nlog2n三、判斷題專業(yè)資料整理WORD格式（ T 1算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。（ T 2強健的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（ F 3程序一定是算法。四、簡答題專業(yè)資料整理WORD格式1如何判斷一個算法的好壞"專業(yè)資料整理WORD格式2調用以下C 函數(shù)f n答復以下問題： 1 試指出fn值的大小，并寫出f n值的推導過程； 2 假定n= 5，試指出f 5值的大小和執(zhí)行f 5時的輸出結果。C 函數(shù)：

7、專業(yè)資料整理WORD格式int f int n 專業(yè)資料整理WORD格式 int i,j， k,sum= 0;專業(yè)資料整理WORD格式for i=l; i<n+1;i+專業(yè)資料整理WORD格式 for j=n;j>i-1; j-專業(yè)資料整理WORD格式for k=1;k<j+1;k+sum+; printf專業(yè)資料整理WORD格式（ "sum=%dn",sum ; return sum ; 【華中理工2000】2.7 習題2.7.1 知識點：線性表的邏輯構造一、選擇題1線性表12 ,an ,以下說法正確的選項是D。L= a , aA 每個元素都有一個直接前

8、驅和一個直接后繼。B線性表中至少要有一個元素。C表中諸元素的排列順序必須是由小到大或由大到小。D除第一個和最后一個元素外,其余每個元素都有一個且僅有一個直接前驅和直接后繼。2在線性表的以下運算中，不改變數(shù)據(jù)元素之間構造關系的運算是D 。A 插入B 刪除C排序D 定位3線性表是具有n 個 C 的有限序列n>0?！厩迦A1998】A 表元素B字符C數(shù)據(jù)元素D 數(shù)據(jù)項E信息項二、判斷題（ T 1線性表中的每個結點最多只有一個前驅和一個后繼。（ F 2線性表中的每個結點都至少有一個前驅結點和后繼結點。（ F 3線性表是 N 個數(shù)的有限序列。（ F 4同一線性表的數(shù)據(jù)元素可以具有不同的特性。 T 5

9、線性表的長度n 就是表中數(shù)據(jù)元素的個數(shù)，當n=0 時，稱為空表。（ T 6線性表是一個相當靈活的數(shù)據(jù)構造，它的長度可根據(jù)需要增長或縮短。（ F 7對線性表中的數(shù)據(jù)元素只能進展訪問，不能進展插入和刪除操作。專業(yè)資料整理WORD格式2.7.2 知識點：線性表的順序存儲構造一、選擇題1在一個長度為n 的順序表中，在第i 個元素 1 <= i <=n+1 之前插入一個新元素時需向后移動B 個元素A n-1B n-i+1C n-i-1D i2假設某線性表中最常用的操作是取第i 個元素和找第i 個元素的前趨元素，那么采用D 存儲方式最節(jié)省時間。A 單鏈表B雙鏈表C單向循環(huán)D 順序表3一個數(shù)組第

10、一個元素的存儲地址是100，每個元素的長度為2，那么第 5 個元素的地址是 B A110B108C 100D 1204下述哪一條是順序存儲構造的優(yōu)點A ?！颈狈浇煌?2001】A 存儲密度大B 插入運算方便C刪除運算方便D可方便地用于各種邏輯構造的存儲表示5假設長度為 n 的線性表采用順序存儲構造，在其第i 個位置插入一個新元素的算法的時間復雜度為C （ 1<=i<=n+1 ?！竞娇蘸教?1999】AO0BO1CO nD O n 26對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為C 。【* 2000】A O n O nB O n O 1C O 1 O nDO1 O1二

11、、填空題1線性表的順序存儲的缺點是在任意位置上_插入 _數(shù)據(jù)與 _刪除 _數(shù)據(jù)費時間。2設一線性表的順序存儲，總存儲容量為M ，其元素存儲位置的X圍為_0M-1_ 。3向一個長度為n 的向量中刪除第i 個元素 1 i n時，需向前移動_n-i_ 個元素。三、簡答題1線性表的存儲構造為順序表，閱讀以下算法，并答復以下問題：voidf30 SeqList *L inti， j;for i=j=0;i<L->length; i+ if L->datai>=0 if i!=j L->dataj=L->datai; j+；L->length=j; 1設線性表L=

12、 21， -7， -8， 19，0， -11，34， 30，-10，寫出執(zhí)行f30 &L 后 L 狀態(tài)； (21,19,0,34,30) 2簡述算法f30 的功能。刪除順序表中小于0 的元素四、編程題專業(yè)資料整理WORD格式1順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個算法，將x 插入到La的適宜位置上，保持該表的專業(yè)資料整理WORD格式有序性。專業(yè)資料整理WORD格式2.7.3 知識點：線性表的鏈式存儲構造一、選擇題1鏈表是一種采用B 存儲構造存儲的線性表。專業(yè)資料整理WORD格式A 順序B鏈式C星式D網(wǎng)狀2存儲的存儲構造所占存儲空間A 。A 分兩局部，一局部存放結點值，另一局部存

13、放表示結點間關系的指針。B只有一局部，存放結點值。C只有一局部，存儲表示結點間關系的指針。D分兩局部，一局部存放結點值，另一局部存放結點所占單元數(shù)。3線性表假設采用鏈式存儲構造時，要求內存中可用存儲單元的地址D 。A 必須是連續(xù)的B 局部地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)或不連續(xù)都可以4線性表在B 情況下適用于使用鏈式構造實現(xiàn)。A 需經(jīng)常修改中的結點值B 需不斷對進展刪除插入C中含有大量的結點D 中結點構造復雜5對單鏈表表示法,以下說法錯誤的選項是C。A 數(shù)據(jù)域用于存儲線性表的一個數(shù)據(jù)元素。B指針域或鏈域用于存放一個指向本結點所含數(shù)據(jù)元素的直接后繼所在結點的指針。C所有數(shù)據(jù)通過指針的而組織

14、成單鏈表。D NULL 稱為空指針，它不指向任何結點只起標志作用。6以下說法正確的選項是D。A 順序存儲方式的優(yōu)點是存儲密度大且插入、刪除運算效率高B鏈表的每個結點中都恰好包含一個指針C線性表的順序存儲構造優(yōu)于鏈式存儲構造D順序存儲構造屬于靜態(tài)構造而鏈式構造屬于動態(tài)構造7以下說法錯誤的選項是D。A 求表長、定位這兩種運算在采用順序存儲構造時實現(xiàn)的效率不比采用鏈式存儲構造時實現(xiàn)的效率低B順序存儲的線性表可以隨機存取C由于順序存儲要求連續(xù)的存儲區(qū)域,所以在存儲管理上不夠靈活D線性表的鏈式存儲構造優(yōu)于順序存儲構造8不帶頭結點的單鏈表head 為空的判定條件是A 。A head= =NULLB hea

15、d->next= =NULLC head->next= =headD head!=NULL9帶頭結點的單鏈表head 為空的判定條件是B 。A head= =NULLB head->next= =NULL專業(yè)資料整理WORD格式C head->next= =headD head!=NULL專業(yè)資料整理WORD格式10在頭指針為head 的非空單循環(huán)鏈表中，指針p 指向尾結點，以下關系成立的是A 。專業(yè)資料整理WORD格式A p->next= =headB p->next->next= =head專業(yè)資料整理WORD格式C p->next= =NU

16、LLDp= =head專業(yè)資料整理WORD格式11在一個單鏈表中，q 所指結點是 p 所指結點的前驅結點，假設在q 和 p 之間插入s 結點，那么執(zhí)行語句C。A s->next=p->next;p->next=s;B p->next=s->next;s->next=p;C q->next=s;s->next=p;D p->next=s;s->next=q;12在一個單鏈表中，假設p 所指結點不是最后結點，在p 之后插入s 結點，那么應執(zhí)行語句B 。A s->next=p:p->next=s;B s->next=p-&

17、gt;next;p->next=s;C s->next=p->next;p=s;D p->next=s;s->next=p;13在一個單鏈表中，假設刪除p 所指結點的后續(xù)結點，那么應執(zhí)行語句A 。A p->next=p->next->next;B p=p->next;p->next=p->next->next;C p->next=p->next;D p=p->next->next;14指針 p 、 q 和 r 依次指向某循環(huán)鏈表中三個相鄰的結點，交換結點*q 和結點 *r 在表中次序的程序段是 A。

18、A p->next=r ； q->next=r->next ； r->next=q ；B p->next=r ； r->next=q ； q->next=r->next ；C r->next=q ； q->next=r->next ； p->next=r ；D r->next=q ； p->next=r ； q->next=r->next ；15鏈表不具有的特點是B 【* 1998】A 插入、刪除不需要移動元素B 可隨機訪問任一元素C不必事先估計存儲空間D所需空間與線性長度成正比16下面的表達不正確

19、的選項是BC【*理工1996】A 線性表在鏈式存儲時，查找第i 個元素的時間同i 的值成正比B線性表在鏈式存儲時，查找第i 個元素的時間同i 的值無關C線性表在順序存儲時，查找第i 個元素的時間同i 的值成正比D線性表在順序存儲時，查找第i 個元素的時間同i 的值無關17下面關于線性表的表達中，錯誤的選項是哪一個？B【北方交通2001】A 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進展插入和刪除操作。C線性表采用存儲，不必占用一片連續(xù)的存儲單元。D線性表采用存儲，便于插入和刪除操作。18在一個以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是 A 【*理工199

20、8】A p->next=h B p->next=NULLC p->next->next=h D p->data=-119假設某線性表最常用的操作是存取任一指定序號的元素和在最后進展插入和刪除運算，那么利用A 存儲方式最節(jié)省時間?！?工業(yè) 2001】A 順序表 B雙鏈表 C帶頭結點的雙循環(huán)鏈表 D單循環(huán)鏈表20某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，那么采用D 存儲方式最節(jié)省運算時間。 【南開 2000】A 單鏈表 B僅有頭指針的單循環(huán)鏈表C雙鏈表 D 僅有尾指針的單循環(huán)鏈表21設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，那么

21、選用D最節(jié)省時間。 【*工業(yè) 2000】專業(yè)資料整理WORD格式A 單鏈表 22線性表B單循環(huán)鏈表C帶尾指針的單循環(huán)鏈表a1, a 2 , ,an以方式存儲時，訪問第D 帶頭結點的雙循環(huán)鏈表 i 位置元素的時間復雜性為C 專業(yè)資料整理WORD格式【*1999】專業(yè)資料整理WORD格式A O i B O 1 C O n D O i-1 23完成在雙循環(huán)鏈表結點p 之后插入s 的操作是 D ?！颈狈浇煌ˋ p->next:=s ; s->priou:=p; p->next->priou:=s ; s->next:=p->next;B p->next->

22、;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;1999】專業(yè)資料整理WORD格式24在雙向循環(huán)鏈表中【郵電1998】【*,在 p 指針所指向的結點前插入一個指針2000】注 :雙向鏈表的結

23、點構造為q 所指向的新結點,其修改指針的操作是llink,data,rlink 。 供選擇的答案：C。專業(yè)資料整理WORD格式A p->llink=q；q->rlink=p；p->llink->rlink=q；q->llink=q；專業(yè)資料整理WORD格式Bp->llink=q；p->llink->rlink=q；q->rlink= p；q->llink=p->llink；專業(yè)資料整理WORD格式Cq->rlink=p；q->llink=p->llink；p->llink->rlink=q; p-&

24、gt;llink=q;專業(yè)資料整理WORD格式Dq->llink=p->llink； q->rlink:=p；p->llink=q； p->llink=q；專業(yè)資料整理WORD格式25在雙向鏈表存儲構造中，刪除p 所指的結點時需修改指針A p->prior->next=p->nextp->next->prior=p->prior;B p->prior =p-> prior-> priorp-> prior-> next=p;C p-> prior-> prior:=pp-> nex

25、t=p-> next -> nextD p-> next = p-> prior -> priorp-> prior=p-> next-> nextA ?！?電子科技1998】專業(yè)資料整理WORD格式二、填空題專業(yè)資料整理WORD格式1線性表的鏈式存儲是用_malloc_ 語句實現(xiàn)空間單元動態(tài)分配。專業(yè)資料整理WORD格式2單鏈表是_線性表 _的存儲表示。專業(yè)資料整理WORD格式3頭結點地址指針為L 的循環(huán)單鏈表，空表的判別標志是_L->next=NULL_。專業(yè)資料整理WORD格式4在一個單鏈表中刪除p 所指結點時，應執(zhí)行以下操作：q=p

26、->next;p-專業(yè)資料整理WORD格式>data=p->next->data;p->next=q->next_;free q;專業(yè)資料整理WORD格式5下段程序的功能：有一頭指針為head 的鏈表 ,將new 指針指向的節(jié)點插入到data 域為7 的節(jié)點的后邊。專業(yè)資料整理WORD格式將程序補充完整。P = head;專業(yè)資料整理WORD格式while P != NULL專業(yè)資料整理WORD格式 if P ->data = 7專業(yè)資料整理WORD格式/* 找到位置插入結點后跳出循環(huán)*/專業(yè)資料整理WORD格式 1 _new->next=p-&

27、gt;next_;專業(yè)資料整理WORD格式 2 _p->next=new_; _break_ ; else 3 專業(yè)資料整理WORD格式 4 _p=p->next_; /* 指針后移 */if P = NULL 專業(yè)資料整理WORD格式printfn the position isntexist!;專業(yè)資料整理WORD格式6假設某個不設頭指針的無頭結點單向循環(huán)鏈表的長度大于 1， s 為指向鏈表中某個結點的指針。算法的功能是，刪除并返回鏈表中指針 s 所指結點的前驅。請在空缺處填入適宜的內容，使其成為完整的算法。f 30專業(yè)資料整理WORD格式typedef struct node

28、 DataType data；struct專業(yè)資料整理WORD格式node *next ； *LinkList；專業(yè)資料整理WORD格式DataType f 30 LinkList s 專業(yè)資料整理WORD格式LinkList pre ， p；DataType e ；while 1 _p->next!=s_pre=s ； pre=p;p=s->next；專業(yè)資料整理WORD格式 2 p=p->next_ ;pre ->next= 3_p->next_ ; e=p->data; free p ; return e;專業(yè)資料整理WORD格式三、判斷題（ F 1單

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

30、存取構造？為什么？順序表4假設本測試中使用的鏈表如圖2.45 所示，結點定義如下：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í)行以下程序段，要求分別畫出結果圖。（ 1 Q=head->next->next;Q指向7（ 2 R->data=P->data;專業(yè)資料整理WORD格式3 變 5（ 3 R->data=P->next->data

31、;3 變 7 4S=P;while S->next!=NULL S->data=S->data*2; S=S->next; 4 101468 5S=P;while S!=NULL S->data=S->data*2; S=S->next; 4 10146165假設本測試中使用的鏈表如圖 2.45 所示，結點定義如第 4 題所示。畫出執(zhí)行如下程序段后各指針及鏈表的示意圖。head= Link malloc sizeof Node ; head->data=0; head-專業(yè)資料整理WORD格式>next=NULL; P=head; for

32、i=1;i<4;i+專業(yè)資料整理WORD格式 new= Link malloc sizeof Node ; new->next=NULL;new->data=2*i;專業(yè)資料整理WORD格式P->next=new;P=new;專業(yè)資料整理WORD格式創(chuàng)立了一個鏈表，數(shù)據(jù)元素為0,2,4,6，并且p 和new 都指向尾結點專業(yè)資料整理WORD格式6有一鏈表如以下列圖所示，閱讀程序給出程序的輸出結果。圖 2.46 6 題圖P = head;while P != NULL printf n data=%d , P-> data ; P = P->next; if

33、P != NULL P = P ->next;Data=1Data=3Data=5五、編程題專業(yè)資料整理WORD格式1一個單鏈表，其頭指針為head，編寫一個函數(shù)計算數(shù)據(jù)域為x專業(yè)資料整理WORD格式的節(jié)點個數(shù)。專業(yè)資料整理WORD格式2單鏈表La 中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫出算法，將元素x 插入到La的合專業(yè)資料整理WORD格式適位置上，保持該表的有序性： 1La 帶頭結點；2 La 不帶頭結點。專業(yè)資料整理WORD格式3試寫一個算法，實現(xiàn)順序表的就地逆置，即在原表的存儲空間將線性表n- 1,a n逆置為 an ,aa1,a 2 , ,an- 1, a2 ,a1

34、。4設計一個算法，求A 和 B 兩個單鏈表表示的集合的交集、并集合差集。3.7 習題3.7.1 知識點：棧的根本概念一、選擇題1以下哪種數(shù)據(jù)構造常用于函數(shù)調用A。棧隊列鏈表數(shù)組2編譯器中通常以哪種數(shù)據(jù)構造處理遞歸程序調用C 隊列數(shù)組C棧D 記錄3以下哪些數(shù)據(jù)構造可用來實現(xiàn)棧D。 1鏈表 2數(shù)組 3樹 4圖 2， 32， 4C 1， 4D 1， 24元素的入棧序列是a,b,c,d，那么棧的不可能的輸出序列是C 。A dcbaB abcdC dcabD cbad5棧的最大容量為4。假設進棧序列為1，2， 3， 4，5， 6，且進棧和出?？梢源┎暹M展,那么可能出現(xiàn)的出棧序列為C。A 5， 4，3，

35、2， 1，6B2， 3，5，6，1，4C 3， 2， 5，4， 1， 6D 1， 4，6， 5， 2，36假設以 S 和 X 分別表示進棧和退棧操作，那么對初始狀態(tài)為空的棧可以進展的棧操作系列是D 。A SXSS* B S*SXSSXC SXS*SSXD SSS*S*7對于棧操作數(shù)據(jù)的原那么是B ?！? 2001】A 先進先出B 后進先出C 后進后出D不分順序8棧在 D 中應用?！? 1998】A 遞歸調用B子程序調用C表達式求值D A ，9一個棧的輸入序列為123 n，假設輸出序列的第一個元素是n，輸出第i 1<=i<=n 個元素是 B ?！?1999】A 不確定B n-i+1C

36、 iD n-i10假設一個棧的輸入序列為1,2,3,，,n輸出序列的第一個元素是i ，那么第 j 個輸出元素是 D ?！?2000】A i-j-1B i-jC j-i+1D 不確定的11有六個元素6， 5， 4， 3， 2， 1 的順序進棧，問以下哪一個不是合法的出棧序列？C 【北方交通2001】A543612 B453162C346521 D23415612輸入序列為ABC ，可以變?yōu)镃BA 時，經(jīng)過的棧操作為B 【* 1999】A push,pop,push,pop,push,popBpush,push,push,pop,pop,popC push,push,pop,pop,push,po

37、pDpush,pop,push,push,pop,pop13設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用D 數(shù)據(jù)構造最正確。 【*電子科技1996】專業(yè)資料整理WORD格式A 線性表的順序存儲構造B隊列 C線性表的鏈式存儲構造D 棧二、填空題1棧是一種特殊的線性表，允許插入和刪除運算的一端稱為棧頂 ，不允許插入和刪除運算的一端稱為棧底 。2對于順序存儲的棧，因為棧的空間是有限的，在進展入棧運算時，可能發(fā)生棧的上溢，在進展出棧運算時，可能發(fā)生棧的下溢。3表達式求值是棧應用的一個典型例子。4棧是 _一種特殊 _的線性表，其運算遵循_先進后出 _的原那么。【科技 1997】5設有一個空棧，

38、棧頂指針為1000H 十六進制 ， 現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，輸出序列是2,3， _ ，而棧頂指針值是_1000C_H 。設棧為順序棧，每個元素占4 個字節(jié)?！?電子科技1998】6用 S 表示入棧操作，X 表示出棧操作，假設元素入棧的順序為1234，為了得到 1342 出棧順序，相應的S 和X 的操作串為 _sxssxs*_ ?！疚髂辖煌?000】三、判斷題（ F 1棧具有先進先出的特性。（ T 2棧用于實現(xiàn)子程序調用。（ F 3棧和鏈表是兩種不同的數(shù)據(jù)構造。（ T 4棧頂?shù)奈恢檬请S著操作而變化的。（ T

39、5棧和隊列邏輯上都是線性表。 T 6棧是實現(xiàn)過程和函數(shù)等子程序所必需的構造?！?工業(yè)2000】（ F 7即使對不含一樣元素的同一輸入序列進展兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定一樣?！距]電 1999】 T 8假設輸入序列為1,2,3,4,5,6,那么通過一個?？梢暂敵鲂蛄?,2,5,6,4,1?！?海運1995】 F 9假設輸入序列為1， 2， 3， 4， 5， 6，那么通過一個?？梢暂敵鲂蛄?， 5， 4， 6， 2， 3?！?海運1999】四、簡答題1什么是棧？試舉兩個應用實例。2簡述棧和線性表的差異。3計算表達式6*3/2-5*1 ，要求繪出堆棧的處理過程。5有 5

40、個元素，其入棧次序為：A ， B， C， D ，E，在各種可能的出棧次序中，以元素C，D 最先出棧專業(yè)資料整理WORD格式即C 第一個且D 第二個出棧的次序有哪幾個？【西南交通2000】專業(yè)資料整理WORD格式3.7.2 知識點：棧的存儲一、選擇題1如果以鏈表作為棧的存儲構造，那么入棧操作時B 。A 必須判別棧是否滿B對棧不作任何判別C必須判別棧是否空D 判別棧元素的類型2上溢現(xiàn)象通常出現(xiàn)在A 。A 順序棧的入棧操作過程中B 順序棧的出棧操作過程中C鏈棧的入棧操作過程中D 鏈棧的出棧操作過程中3判定一個棧ST最多元素為m0為空的條件是B 專業(yè)資料整理WORD格式 ST->top！ =0

41、ST->top= =0 ST->top！ =m0 ST->top= =m04鏈表仿真堆棧時，?？盏臈l件是B 。A top<maxsize-1B top= =NULLC 沒有限制D top<05鏈表仿真堆棧時，棧滿的條件是C。A top<maxsize-1B top= =NULLC 沒有限制D top<06在用鏈表仿真堆棧時假設stack 為棧頂指針，將new 指針指向的節(jié)點執(zhí)行入棧操作應執(zhí)行B new->next=stack->next ； stack=new； new->next=stack ； stack=new； new->

42、;next=stack ； stack=new->next ； stack=new ； stack->next=new->next ；7假設一個棧以向量V1 n 存儲，初始棧頂指針top 為 n+1 ，那么下面x 進棧的正確操作是C 。【*理工1998 】專業(yè)資料整理WORD格式A top=top+1; V top=x C top=top-1; V top=xB V top =x; top=top+1 D V top=x; top=top-1專業(yè)資料整理WORD格式8執(zhí)行完以下語句段后，i 值為： B ?！? 2000】 int f int x return x>0 " x* f x-1 :2 ; int i ;i =f f 1 ;A2B4C8D無限遞歸二、填空題1以下語句是堆棧的入棧操作，用全局數(shù)組