例题：

解：

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）应该选择链式存储结构，入队和出队操作的时间复杂度为O(1)

2）队列初始状态为空

3）第一个元素入队后队列状态

4）

栈在表达式求值中的应用：

    中缀表达式：A+B*(C-D)-E/F

    后缀表达式：ABCD-*+EF/-

后缀转中缀表达式——操作数从左向右找操作符向前插入到操作数之间

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

递归中的栈

队列在层次遍历中的应用

例题：

解：a出——a

+入栈，b出——ab

+出栈（栈底+划掉），-入栈——ab+

a出，*、(、(入栈——ab+a

c出，+入栈，d出——ab+acd                     故选A

+出栈，）配对的（出栈——ab+acd+

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

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

-出栈，）配对的（出栈——ab+acd+e/f-

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

+入栈、出栈——ab+acd+e/f-*-g+

解：先调用main()压栈，再调用打印的S1压栈，再调用s（n-1）压栈。故选A

特殊矩阵和串

    特殊矩阵的压缩算法

    

求22所在一维数组的位置（第4行第2列）a4,2=4*（4-1）/2+2-1=7

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

求22所在一维数组的位置（第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| |^），

例题：