主要内容：① 各种线性结构的特点、基本运算及其实现。
② 矩阵元素的存储方式，广义表的定义及基本运算。
③ 树的特点、基本运算及其实现。
④ 图的特点、存储结构、常用算法及实现。
⑤ 顺序查找和二分查找方法及实现。
⑥ 二叉排序树的定义和查找、插入及删除运算和实现。
⑦ 平衡二叉树的定义及其平衡处理方法，B-树的概念及查找。
⑧ 各种查找算法的查找性能分析方法。
⑨ 各种排序方法及实现。

软件设计师专题三：数据结构(20080815)在线专题授课音视频

●输入受限的双端队列是指元素只能从队列的一端输入、但可以从队列的两端输出，如下图所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列（57） 。
A 2 8 14 B 1 4 2 8 C 4 2 18 D 2 1 4 8
参考答案：D

●设栈s和队列q的初始状态为空，元素a、b、c、d、e和f依次通过栈s，每个元素出栈后立刻进入队列q。若这6个元素出队列的顺序是b、d、c、f、e和a，则栈s的容量至少应该是___(1)___。
【供选择的答案】
（1） A．3 B．4 C．5 D．6
参考答案：A

●若广义表L＝((1,2,3))，则L的长度和深度分别为___(1)___。
【供选择的答案】
（1）A. 1和1 B. 1和2 C. 1和3 D. 2和2
参考答案：B

●已知某二叉树的先序和中序遍历序列分别为ABCDEF和CBAEDF，则该二叉树的后序遍历序列是___(1)___，其层序遍历序列是___(2)___。
【供选择的答案】
（1） A．CBDEFA B．CBEFDA C．CBFEDA D．CDEFBA
（2） A．ACBEDF B．ABCDEF C．ABDECF D．ABDCEF
参考答案：B D

●二叉树的前序、中序和后序遍历法最适合采用___(1)___来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为___(2)___，而使上述路径长度总和达到最小的树称为___(3)___，它一定是___(4)___。在关于树的几个叙述中，只有___(5)___是正确的。
【供选择的答案】
（1） A. 递归程序 B. 迭代程序 C. 队列操作 D. 栈操作
（2） A. 路径和 B. 内部路径长度 C. 总深度 D. 深度和
（3） A. B-树 B. B+树 C. 丰满树 D. 穿线树
（4） A. B-树 B. 平衡树 C. 非平衡树 D. 穿线树
（5） A. 用指针方式存储有n个结点二叉树，至少要有n+1个指针
B. m阶B-树中，每个非椰子结点的后件个数≥[m/2]
C. m阶B-树中，具有k个后件的结点，必含有k-1个键值
D. 平衡树一定是丰满树
参考答案：A B C B C