重点：几种常用的数据结构
难点：数据结构的应用
重要性：数据结构的设计和操作是编程的基础
主要内容：汇编、编译、解释系统的基础知识和基本工作原理；程序设计语言的基本成分（数据、运算、控制和传输，过程函数调用）；
数组、线性表、链表、队列、栈、树、图等的定义、存储和操作

一、程序设计语言及数据结构（20050926）在线专题授课音视频

（软考程序员、软件设计师 课程正式学员可登录学习系统，进入对应课程，在“课程资料室”内进行在线浏览。） 

二、程序设计语言及数据结构（20050926）在线答疑整理

1.正则表达式

2.有限自动机（FA）

3.语法树

S→a        (1)

S→b        (2)

S→(T)      (3)

T→TdS     (4)

T→S       (5)

句型：(Sd(T)db)

采用自上而下的方法推导，从开始符号S开始推导：

1）  考察1、2、3三个产生式，前面两个都是产生终结符了，所以是不可能的，只能用第3个。结果如下：

   　　　　　   当前串（T）

2）  可以看出来，当前串(T)和目标句型(Sd(T)db)两个括号对应上了（因为终结符是不能继续推导下去的，而且位置已经固定了，所以可以确定），接着需要T产生Sd(T)db。T产生式有两个：4和5。现在无法确定用那个，所以只能猜测。先试4。则结果如下：

                        从上至下，从左至右为当前串：（TdS）

3）  继续推导，对当前串中最左非终结符进行推导，这时仍旧不能确定是用4还是5，这次我们假设用5，结果如下：

                当前串（SdS）

4)对比（SdS）与(Sd(T)db)，可以假设认为前3个字符对应上了，那么需要前者第4个字符S产生后者的(T)db，S产生式有1、2、3这几个，很容易看出1和2不可能，第3个仍然不可能，因为S→(T)这个产生式产生的句型中最后一个非终结符肯定是)，不可能是b。所以最近的一个假设被推翻，即不能认为（SdS）与(Sd(T)db)的前3个字符对应上了。可以这时，对当前串中未匹配的最左非终结符继续推导，经分析可知，不会用1、2产生式，所以用第3个

                当前串((T)dS),很容易看出来这个和目标串不可能匹配，所以继续推翻最近的一个假设，在第3步中。返回第3步，用产生式4：

                          当前串：（TdSdS）

5)由当前串（TdSdS）与目标串(Sd(T)db)分析，它们都有两个d，如果这个推导式正确地话，它们一定要匹配的。剩下的推导分别由5号，3号和2号产生式推导，完成。

结果(Sd(T)db)出现.