数据结构考研复习要点
- 格式：docx
- 大小：609.95 KB
- 文档页数：12
考研题型包括：
简答题；
方法选择（分析）；
构造题；
算法题。
第一章 绪论
1. 数据结构的基本概念：数据、数据元素、数据对象、数据结构
2. 抽象数据类型：数据对象、逻辑关系、一组操作。
ADT的特点：数据抽象、信息隐蔽
3. 数据结构三要素：数据元素间的逻辑关系、物理存储和一组操作。
元素间的逻辑关系：集合、线性、树、图
元素在计算机内存中的存储结构： 顺序、非顺序
4. 算法的定义：规则的有限集合，为了解决某个特定问题而规定的一系列基本操作。
算法特性：有限性、确定性、可行性、输入、输出
算法设计目标：正确性、可读性、鲁棒性、高效率低存储
5. 算法性能评价：时间和空间
算法时间复杂度：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
求解算法的时间复杂度的具体步骤是：
⑴ 找出算法中的基本语句；
⑵ 计算基本语句的执行次数的数量级；
保留基本语句执行次数的函数中的最高次幂，忽略所有低次幂和最高次幂的系数。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < { O(2^n) < O(n!) < O(n^n) }
【例】分析下面各算法的时间复杂度 算法1：
int fact(int n)
{ if (n<=1) return 1;
return n*fact(n-1);
}
算法2：
i=l;
while (i
{
for(j=l;j<=n;j++)
x=x+l;
i=i*2;
}
算法3：
for(i=l;i<=n;i++)
{ j=l;
while (j<=i)
{x+=l; j++;}
}
算法:4
void sort(int b[]， int n)
{ int i, j, k;
for (i=0; i
{ k = i;
for (j=i+1; j
if (b[k] > b[j]) k = j;
x = b[i]; b[i] = b[k]; b[k] = x;
}
}
算法5
void add(int n)
{ int i = 0, s = 0;
while (s
{ i++;
s = s + i;
}
}
设while循环语句执行次数为T(n),则
算法6 void hanoi(int n, char a, char b, char c)
{ if (n==1) printf("move %d disk from %c to %c \n", n, a, c);
else
{ hanoi(n-1, a, c, b);
printf("move %d disk from %c to %c \n", n, a, c);
hanoi(n-1, b, a, c);
}
}
算法7：
void PreOrder(BiTree T)
{ if (T)
{ visit(T->daata)
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
算法空间复杂度：空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。
【例】分析下面各算法的空间复杂度
void PreOrder(BiTree T)
{ if (T)
{ visit(T->daata)
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
第二章 线性表
一、概念（可能会出的简答题）
1. 线性结构特点:
2. 线性表定义
3. 线性表顺序存储和链式存储各自的优缺点
4. 线性表的顺序存储表示与一维数组的关系是什么？
同：一维数组与顺序表都可按元素下标直接（或随机）存取元素；
异：
一维数组中各元素间可以有空元素，而顺序表中的元素必须按顺序存放；
一维数组的基本操作只有按下标存取，而顺序表可以有线性表的所
一维数组的大小一经分配便不可变，而顺序表的长度是可变的。
5. 线性表的特点是：除第一个元素外其他每个元素有且只有一个直接前驱，除最后一个元素外其他每个元素都有且只有一个直接后继。那么，循环链表的每一个结点都有直接后继，双向链表的每一个结点都有直接前驱和直接后继，它们还是线性表吗？
6. 在一个单链表L中，P为中间某结点，在P前插入S结点，可否在O(1)时间复杂度内完成。（可能是分析题）
7. 给定一个单链表头指针和指向某结点的指针，如何在时间复杂度O(1)内，删除该结点。
二、算法设计
1. （顺序表）已知长度为n的线性表L采用顺序存储，请写一时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法是删除线性表中所有值为item的数据元素。
2.（顺序表）编写算法，其功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素。时间复杂度为O(n)，空间复杂度为O(1)
3. （单链表）给定一个字符串，编写统计算法，用链表依次存储字符串中各字符及其出现的次数(不区分字母的大小写)。
4. （单链表）某个带头结点的单链表L，编写算法删除值最小的元素。
5. （单链表）一单链表，以第一个元素为基准，将小于该元素的结点全部放到前面，大于该元素的结点全部放到其后。
6. （单链表和循环链表）已知一个带头结点的单链表List，在不改变链表的前提下，设计一个尽可能有效的算法，查找倒数第k个位置上的结点。若查找成功，算法输出该结点的值，并返回1；否则返回0。
7. （循环链表）某链表L，可能是单链表，也可能循环链表（为元素的指针域可指向链表中的任意一结点），编写算法判断该链表的类型。
8. （单链表）某一元多项式采用带头结点的单链表存储，编写算法求其导数。函数声明：void Derivative(PolyNode *PL)，参数为一元多项式的头指针，该多项式按照幂次递增的次序排列，结果仍为PL所指的链表。
9. （单链表和排序）设主串s和子串t分别以单链表存储，t和s 中每个字符均用一结点表示（如图）。实现在链式存储方式下的模式匹配，即求子串t在主串s中第一次出现的位置指针。
10. （单链表）单链表的就地逆置。
11. （单链表和栈）已知一个循环单链表la,av是可用栈的头指针，请用3个赋值语句，实现释放整个循环单链表功能的操作。（将单链表中的节点归还到可用栈）
12. 从尾到头打印单链表，要求不改变该链表顺序。(递归或栈)
13. 两个有序单链表的合并。
14. 给定一个单链表头指针和指向某结点的指针，如何在时间复杂度O(1)内，删除该结点。
15. 编写高效算法，找出链表的中间结点。（两个指针，一个步长为1，一个为2）
17. 判断两个链表是否相交；求相交的第一个结点。（求出两个链表总长度，第一个先走长度差步，然后一起走，碰头的地方就是相交点）
第三章 栈和队列
一、概念（可能会出的简答题）
1. 栈和队列的异同？它们分别有什么用途？
2. 栈和队列为什么是限定性线性表？
3. 递归进层、退层时做哪些事情？
4. 递归算法有哪些缺点？如何消除递归？
二、算法设计
1. 链栈的进栈和出栈算法。 data Next 2. 利用栈的基本操作，实现将一个十进制数n，转换为r(r<=16)进制并输出的算法。
3. 设一个栈的输入序列为1,2，…，n，编写算法，判断一个序列p1,p2,…,pn是否是一个合理的输出序列。
4. 利用栈的基本操作，将中缀表达式转换为后缀表达式（逆波兰式）。
5. 循环队列的进队和出队算法。
区别队空，队满有两个办法：一是少用一个单元;二是设置标志；三是用一个计数器。每个办法下如何定义队列结构体、初始化、进队、出队算法都要会写。
6. 用带尾指针的循环队列表示队列。给出此时队列的结构体定义以及队列的初始化、出队和入队操作。
第四章 串
一、概念（可能会出的简答题）
1. 串为什么也是限定性线性表？
2. 什么是串的模式匹配？
3. 某串长度为n，该串有多少个子串？
二、算法设计
1. 写出顺序串的模式匹配BF算法。StrIndex(SString s,int pos, SString t)
2. 写出堆串的串删除操作。StrDelete(HString *s，int pos，int len)
……
第五章 数组和广义表
一、简答题
1. 数组和广义表属于线性表的原因？
2. 什么是特殊矩阵？你了解到的特殊矩阵有哪些？
3. 特殊矩阵的压缩原则有哪些？
4. 什么是稀疏矩阵？一般用什么方法压缩稀疏矩阵？
二、分析或计算。
1. 一维、二维、三维数组的地址计算。（多维时，注意按行按列）
