2012数据结构复习.docVIP

2015数据结构复习 考试题型：判断题、填空题、单选题、应用题、算法填空题、编写算法题 数据结构基础知识 1.数据、数据元素、数据结构的概念 2.数据的逻辑结构（本身固有，不依赖计算机） 3.数据的存储结构（依赖计算机） 4.从逻辑结构来划分数据结构（线性结构和非线性结构） 5.从存储结构来划分数据结构（顺序存储、链式存储） 6.数据结构的三个方面（逻辑结构、存储结构、运算） 7.时间频度（语句频度）和时间复杂度 O（1）、O（n）、O（n2）、O（nlog2n）… 8. 空间频度（语句频度）和空间复杂度 线性表 1.线性表的定义（L=(a1,a2,a3,…,an)） 2.线性表的特点（线性结构，最多一个前驱，最多一个后继） L=(e,r) e为元素集合，r为关系集合。 4.线性表的存储（顺序存储—“顺序表”和链式存储—“链表”） 5.顺序表的基本运算（插入和删除）及时间复杂性 n/2 (n-1)/2 6.单链表的建立算法实现（头插法和尾插法） /*头插法*/ #includestdio.h Struct node { int data; struct node *next; }; struct node *creatH(int n) {struct node *head,*s; int i; head=(struct node *)malloc(sizeof(struct node)); head-next=NULL; for(i=1;i=n;i++) {s=(struct node *)malloc(sizeof(struct node)); s-data=i; s-next=head-next; head-next=s; } return head;} /*尾插法*/ #includestdio.h Struct node { int data; struct node *next; }; struct node *creatR(int n) {struct node *head,*s,*t; int i; head=(struct node *)malloc(sizeof(struct node)); t=head; for(i=1;i=n;i++) {s=(struct node *)malloc(sizeof(struct node)); s-data=i; t-next=s; t=s; } t-next=NULL; return head;} 7.循环链表 8.顺序表和链表的比较 顺序表（线性表的顺序存储）：空间利用率高，可随机访问，插入删除麻烦 链表（线性表的链式存储）： 空间利用率低，只能顺序访问，插入删除方便 栈和队列 1.栈的定义 2.栈的特点LIFO 3.栈的两种存储结构（顺序栈和链栈） 4.栈的五种运算 初始化栈inistack() 进栈push() 退栈pop() 取栈顶元素getstack() 判栈空empty() 5.栈的应用（函数的嵌套和递归调用、表达式的求值） 进栈1,2,3,4,出栈可能顺序14种:1234,1243,1324,1342,1432,2134, 2143，2341，2314，2431，3214，3241，3421，4321 6.队列的定义 7.队列的特点FIFO 8.队列的两种存储结构 顺序存储有：顺序队列和循环队列 顺序队列中，队空队满都是f=r,进队r++，出队f++ 循环队列中，队空f=r，队满f=(r+1)%M,进队r=(r+1)%M, 出队f=(f+1)%M 链队列：设置队头指针和队尾指针 9.队列的五种运算 初始化队列iniqueue() 进队列ENqueue() 出队列DELqueue() 取队头元素getqueue() 判队列空empty() 10.队列的应用 串（不要求） 多维数组和广义表 多维数组的两种存储（行优先和列优先） 能写出结果即可。 树和二叉树 1.有序树和无序树 2.树的表示 3.树和二叉树中的基本术语 4.二叉树的性质 5.满二叉树和完全二叉树 6.二叉树的两种存储结构 顺序存储：必须按完全二叉树形式存储 链式存储：二叉链表 7.二叉树的五种形态 8.二叉树的遍历 先序、中序、后序和层次遍历序列 例如：写出下面二叉树的遍历序列。 先序：ABDFGJCEHKI 中序：BFDJGACHKEI 后序：FJGDBKHIECA 层次：ABCDEFGHIJK 9.二叉树的遍历算法（先序、中序的非递归） 先序的非递归 void preorder1(struct node *root) {struct node *p; p=root;inistk( );//初始化栈 while