最新数据结构复习题复习进程备课讲稿.doc

《最新数据结构复习题复习进程备课讲稿.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、简答题（比较两个概念的相同和异同）1.简述下列概念：数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，线性结构，非线性结构。数据:是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据类型：是具有相同性质的计算机数据的集合及其在这个数据集合上的一组操作。逻辑结构：指的是数据之间的相互关系，即数据的组织形式。存储结构：数据对象在计算机中的存储表示，也称为物理结构。线性结构：线性结构的逻辑特征是：有且仅有一个开始

2、结点和终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。非线性结构：非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。2.比较C语言与pascal语言的差异。C语言和Pascal语言是目前对计算机发展影响较深的两门计算机程序设计语言。两种语言各有特点：Pascal语言是一种结构式程序设计语言，最初是为系统地教授程序设计而发明的，语法严谨，特点是简明化和结构化，适合教学，科学计算等。C语言则是国际上应用最广泛的计算机中级语言，具有语言简洁紧凑，使用方便灵活及运算符丰富等特点，语法限制不严格，程序设计自由度大，程序可移植性好。3.试描述头指

3、针、头结点、开始结点的区别，并说明头指针和头结点的作用。开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。4.何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表

4、作为线性表的存储结构，通常有以下几方面的考虑：  1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。  2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。5.为什么在单循环链表中设置尾指针比设置头指针更好?答：尾指针是指向

5、终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。6.比较下列每队术语的区别空串和空格串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答：●空串是指不包含任何字符的串，它的长度为零。 空格串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变

6、其值的串。 串变量是可以在运行中改变其值的。  ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。  ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。  ●有效位移和无效位移：在串定位运算中，模式串从目标

7、的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。串名和串值的区别串变量的名字代表该串的首地址，即第一个字符的地址。串变量的值指的是该变量中存放的字符串。 7.比较栈与队列的区别栈与队列的相同点：1.都是线性结构。2.插入操作都是限定在表尾进行。3.都可以通过顺序结构和链式结构实现。、4.插入与删除的时间复杂度都是O（1），在空间复杂度上两者也一样。5.多链栈和多链队列的管理模式可以相同。栈与队列的

8、不同点：1.删除数据元素的位置不同，栈的删除操作在表尾进行，队列的