华南理工大学数据结构复习提纲二.doc

数据结构 复习提纲 第二部分 复习提纲(不分题型) 逻辑结构、存储结构、运算、算法、时空复杂性等哪些与计算机硬件有关？无关？ 逻辑结构： 存储结构：指数据的逻辑结构在计算机存储器中的实现，存储结构是依赖于计算机的。 运算：在数据逻辑结构上定义的操作。 ◆ 例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。　　那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。　　最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。T (n) = O(f(n)) 称T (n) 为算法的渐近时间复杂度（Asymptotic Time Complexity）,简称时间复杂度。O是数量级的符号。 下面我们探讨一下如何估算算法的时间复杂度 算法 = 控制结构 + 原操作（固有数据类型的操作） 算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间 算法的执行时间与原操作执行次数之和成正比 逻辑结构与存储结构是否一一对应？ 答：否。 算法有哪些描述方法？ 答：自然语言、表格、C语言、PASCAL语言。。。。 算法评价一般考虑算法分析指-Next = = NULL 有头结点循环： HEAD-Next = =NULL 无头结点非循环： HEAD = =NULL 无头结点循环： HEAD = = NULL 循环链表主要优点？用尾指针表示循环单链表有什么好处？ 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。typedef int datatype; //结点数据类型，假设为int typedef struct node * pointer; //一般结点指针类型 struct node {//结点datatype data; pointer next; }; typedef pointer lklist; //头指针类型 void ; p=p-next; } } 5．例，判断无头结点的链表中结点是否构成等差数列。 解：链表类型定义同上题。 int detect(lklist L) { pointer p,q; //以下用q表示p的前趋 datatype x; q=L;if(q==NULL) return 1; //链表为空 p=q-next;if(p==NULL) return 1; //链表只有1个结点 x=p-data-q-data; //初始结点差 while(p-next!=NULL) { q=p;p=p-next; if(p-data-q-data!=x) return 0; //不满足等差关系 } return 1; } 1．栈、队列的基本运算有哪些？ 答：出栈、入栈，出队、入队。 2．例：三个点ABC依次进栈(在进栈的中间可能有出栈)。问ABC、BCA、CAB能否是可能的出栈序列？ 解：按先进后出的原则分析，ABC可行：即A进A出、B进B出、C进C出； BCA可行：即A进不出，B进B出、C进C出、A出； CAB不行：C出后，栈内有BA，应B先出。 3．循环队列A[m]中，已知头指针、尾指针与元素个数中的任意两个，求另一个？ len=(rear-front+m)%m; rear=(front+len)%m; front=(rear-len+m)%m; 串、长度、子串、相等、子串定位或+1 3．只有3个结点的二叉排序树有几种形态？ 解：有5种，见下图所示。 4．完全二叉树有6个叶子，则结点总数就是11吗？ 解：已知叶子数的完全二叉树一般有两棵，结点数差1，见下图： 一般，结点数n＝n0＋n1＋n2，而n0＝n2＋1(二叉树性质)，所以n＝2n0－1＋n1。完全二叉树树中