中国科学技术大学2023年复试资料。
1．接受咨询；领取材料；签署协议。
2．材料审核：按序号分组进行。
3．专业面试：专业面试10-15分钟一位。
4. 英语面试：身份验证后参加英语面试室。英语面试5-8分钟一位。
5. 综合素质测试和专业测试（c语言和数据结构）
特别注意的是调剂的学生，所有参加调剂的考生须上教育部研招网调剂。
1.时间复杂度。
按数量级递增排列，常见的时间复杂度有：常数阶o(1)，对数阶o(log2n)，线性阶o(n)，线性对数阶o(nlog2n)，平方阶o(n)，立方阶o(n)， k 次方阶o(n)，指数阶o(2)。
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
2.各种排序的时间复杂度和性能比较。
3.什么是堆，有什么作用。
堆是一种数据结构，可以把堆看成一棵完全二叉树，这个完全二叉树满足：任何一个非叶结点的值都不大于（或不小于）其左右孩子结点的值。若父亲大孩子小，则这样的堆叫做大顶堆；若父亲小孩子大，则这样的堆叫做小顶堆。
利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小（大）数选出放在堆顶，来实现堆排序。
4.时间复杂度为o(nlog2n)的排序方法。
时间复杂度为o(nlog2n)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好。
5.直接插入算法。
注：程序中pelem[0]是哨兵，作用：避免不必要的判断语句，提高效率。
6.折半插入算法。
7.什么叫堆排序？与快速排序有什么不同？
答案请参看上表 ：快速排序1、每趟排序不产生有序区；2、时间复杂度与待排序数据顺序有关；3、空间复杂度与待排序数据顺序有关。
8.循环队列的顺序表示中，为什么要空一个位置？
循环队列那个空位置为了便于辨别对空和队满。
9.什么是二叉查找树，原理。
二叉排序树（binary sort tree）又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；
步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。
中序遍历二叉查找树可得到一个关键字的有序序列。
10.排序算法最优的时间复杂度（11,13）
基于比较的排序算法中最好时间复杂度为o(nlog2n)。
11.哈夫曼树（11,12,13）
给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若带权路径长度（wpl）达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(huffman tree)。
特点：(1)权值越大的结点，距离根结点越近。
(2)树中没有度为1的结点。哈夫曼树又称为严格的(正则的)二叉树。
12.哈夫曼树的应用：哈夫曼编码。
任一字符的编码都不是另一个字符的编码的前缀，这种编码成为前缀编码。
设计一棵哈夫曼树，由此得到的二进制编码前缀编码便称为哈夫曼编码。
构造方法：假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
1) 将 w1、w2、…，wn 看成是有 n 棵树的森林(每棵树仅有一个结点)；
2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
13.什么是哈希冲突，及如何解决（13）
哈希表：散列表（hash table，也叫哈希表），是根据关键码值(key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
常用散列函数：
1、 直接寻址法。
2、 数字分析法。
假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字若干数位组成哈希地址。
3、 平方取中法。
取关键字平方后的中间几位为哈希地址，取的位数由表长决定。
4、 折叠法。
将关键字分割成位数相同的几部分（最后一部分位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
5、 随机数法。
h(key)=random(key)， random为随机函数。
6、 除留余数法。
h(key)=key % p, p<=m(表长)。
处理冲突的方法：
1、 开放寻址法： (
根据的取法分。
1) 线性探测法： =
2) 平方探测法： (
3) 伪随机序列法： =伪随机数序列链地址法。
2、 再哈希法： ;
3、 链地址法：将所有关键字为同义词的记录存储在同一线性表中；
4、 建立一个公共溢出区。
散列因子：α=填入表中的元素个数 / 散列表的长度。
是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
14.深度、广度搜索的过程。
图的深度优先遍历：
假设给定图 g 的初态是所有顶点均未曾访问过。在 g 中任选一顶点 v 为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点 v，并将其标记为已访问过；然后选取与v邻接的未被访问的任意一个顶点w，并访问它，再以 w 为新的出发点继续进行深度优先遍历，直至图中所有和源点 v 有路径相通的顶点 (亦称为从源点可达的顶点)均已被访问为止。
若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(depth-first search)。
相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。
图的深度优先遍历耗费的时间取决于所采用的存储结构。当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为。
使用数据结构：堆栈。
图的广度优先遍历：
首先访问起始点v，然后依次访问v的各个未曾访问过的邻接点，再分别从这些邻接点出发依次访问它们的邻接点（已经访问过的除外），并且要使得“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点“被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
图的广度优先遍历类似于树的层次遍历。采用的搜索方法的特点是尽可能先对广度方向进行搜索。这种搜索方法称为广度优先搜索(breadth-first search)。
相应地，用此方法遍历图就很自然地称之为图的广度优先遍历。
图的广度优先搜索遍历图的时间复杂图和深度优先搜索遍历相同。
使用数据结构：队列。
15.图的深度优先遍历序列是否唯一？为什么？
不一定唯一。当从某顶点 x 出发搜索时，若 x 的邻接点有多个顶点尚未访问过，则我们可任选一个访问之。
16.迪杰斯特拉算法的过程。
dijkstra (迪杰斯特拉) 算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
dijkstra 一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用 open, close 表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
算法步骤如下：
1. 初使时令 s=,t=，t 中顶点对应的距离值若存在，d(v0,vi)为弧上的权值若不存在，d(v0,vi)为∝
2. 从 t 中选取一个其距离值为最小的顶点 w 且不在 s 中，加入 s
3. 对 t 中顶点的距离值进行修改：若加进 w 作中间顶点，从 v0 到 vi 的距离值比不加 w 的路径要短，则修改此距离值重复上述步骤，直到 s 中包含所有顶点，即 s=t 为止。
17.链表查询某个元素，平均时间复杂度是多少？
18.链表可以用什么实现，循环链表的实现方式？ 如何快速找到位于单链表中间的节点？
链表可由指针和数组来实现。
循环链表：将单链表的最后一个结点的null指针改为指向开始结点即可。
设置两个指针* fast、*slow都指向单链表的头节点。其中* fast的移动速度是* slow的2倍。当* fast指向末尾节点的时候，slow正好就在中间了。
19.图的存储方式。
邻接矩阵。用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。在用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外还有图的顶点数和边数。
2019考研复试宝典
2011考研复试宝典 新闻传播类专业。2011年03月22日 13 31 跨考教育 2011年的考研初试已经结束，接下来进入复试调剂阶段。由于各院校分数刚陆续公布，国家线还没出来，此时是广大研友最紧张 焦虑和无助的时刻，甚至许多研友都开始了匆忙的调剂之旅，有的则开始做复试的准备。究竟怎样进行复试阶段...
2019考研复试宝典
考研结果即将揭晓，近期很多考生发短信咨询如何准备复试的问题，我把个人的经验整理出来供大家参考，希望对你们有帮助！面对即将而来的考研复试，考生该做哪些准备呢？一 了解考研复试内容，最好充足准备 主要说来，考研复试主要考听力和口语，然后就是专业课。下面我们分开来看下该如何准备这些内容。1.听力和口语 听...
2023年考研调剂宝典
校内调剂别急着调剂其他院校。王同学 2010级研究生，报考首都师范大学教育学学术型硕士调剂到专业型硕士。当时考试分数线过了国家线，但让师姐帮我打听排名后，知道自己没复试资格了。我很着急，但还希望能进首师大，最后幸运地被调剂为教育专业硕士。对于校内调剂，我给出以下几点经验 第一，查完排名发现可能会失去...