例題：

解：

A中1、2出隊輸出，3、4、5出隊入棧，5出棧輸出，6出隊輸出，4、3出棧輸出；

B中1出隊入棧，2、3、4、5、6出隊輸出，1出棧輸出；

C中1、2出隊入棧，3、4、5、6出隊輸出，2先出棧輸出，故選C；

D中1、2、3、4、5、6出隊入棧，6、5、4、3、2、1出棧輸出。

解：

A中右邊入隊1、2，左邊入隊3、4、5，左邊出隊得到序列54312

B中右邊入隊1、2，左邊入隊3，右邊入隊4，左邊入隊5，得到序列

C中左邊入隊1、2，右邊入隊3，左邊入隊4，右邊入隊5，得到序列

D中左邊入隊1，2左右入隊都不在1旁邊，故得不到序列

解：1）應(yīng)該選擇鏈式存儲結(jié)構(gòu)，入隊和出隊操作的時間復(fù)雜度為O(1)

2）隊列初始狀態(tài)為空

3）第一個元素入隊后隊列狀態(tài)

4）

棧在表達式求值中的應(yīng)用：

????中綴表達式：A+B*(C-D)-E/F

????后綴表達式：ABCD-*+EF/-

后綴轉(zhuǎn)中綴表達式——操作數(shù)從左向右找操作符向前插入到操作數(shù)之間

AB（C-D）——>AB*（C-D）——>A+B*（C-D）——>A+B*（C-D）EF——>A+B*（C-D）E/F——>A+B*（C-D）-E/F

遞歸中的棧

隊列在層次遍歷中的應(yīng)用

例題：

解：a出——a

+入棧，b出——ab

+出棧（棧底+劃掉），-入?！猘b+

a出，*、(、(入?！猘b+a

c出，+入棧，d出——ab+acd? ? ? ? ? ? ? ? ? ? ?故選A

+出棧，）配對的（出?！猘b+acd+

/入棧，e出——ab+acd+e

/出棧，-入棧，f出——ab+acd+e/f

-出棧，）配對的（出?！猘b+acd+e/f-

*、-出棧，g出——ab+acd+e/f-*-g

+入棧、出?！猘b+acd+e/f-*-g+

解：先調(diào)用main()壓棧，再調(diào)用打印的S1壓棧，再調(diào)用s（n-1）壓棧。故選A

特殊矩陣和串

????特殊矩陣的壓縮算法

????

求22所在一維數(shù)組的位置（第4行第2列）a4,2=4*（4-1）/2+2-1=7

可得公式：ai,j=i*（i-1）/2+j-1

求22所在一維數(shù)組的位置（第2行第4列）a2,4=4*（4-1）/2+2-1=7

可得公式：ai,j=j*（j-1）/2+i-1

例題：

解：選A

解：選C

?

解：選B

稀疏矩陣

a行b列有非零元素（a——>b），依次類推b行c列（b——>c）、c行無列，d行b列（d——>b），^表示空

十字鏈表

a行|元素位置|in|out? ? ? ? ?——注意箭頭與指向相反

????a行b列（b行指向a行），b行c列（c行指向b行），c行空，（a行指向d行）

a行b列有元素in空out有（a|^| ——>a|b|?|^），

例題：