一、简答题。
数据类型和抽象数据类型的概念；
算法的定义、特性、评价准则；
数据元素的逻辑关系；
顺序存储与链式存储的优缺点；
栈和队列的异同；
递归进层、退层时做哪些事情；
什么是特殊矩阵，其压缩原则有哪些？
折半查的前提条件；
分块查的基本思想；
图的遍历中，访问标志数组的作用；
冒泡、直接插入或者简单选择排序在什么情况下排序性能最好，什么时候最差；
什么是平衡二叉排序树和平衡因子；
分析二叉排序树的查性能。
二、方法选择
比如:
在一个很大的集合中，很少的几个最小或最大的元素出来，哪些排序方法比较合适。
在图中距离某顶点v的最短路径为K的顶点，应该用什么方法？深度遍历图还是广度遍历图？
二叉树的性质3，即n0=n2+1，要会证明。
三、构造结果
一般主要分布在树、图、查和排序这几章。
树：
二叉树中序遍历非递归算法
1、二叉树逻辑结构《-》三种遍历序列;
2、二叉树的逻辑结构和二叉树的顺序存储结构之间相互转换。
3、根据扩展先序序列，画出二叉树。
4、构建哈弗曼树，进行哈曼满编码，并计算WPL;
图：
1、图的遍历，深度优先生成树，广度优先生成树
2、最小生成树：普里姆算法，克鲁斯卡尔算法
查：
1、构建折半判定树，考察折半查，分析查性能，即查成功和不成功
的平均查长度。
2、构建二叉排序树，分析查性能。
3、构建哈希表哈希表，分析查性能。
排序：
1、给定排序序列，能写出几种常用的排序过程，如直接插入、希尔、冒泡、
快速、简单选择、归并排序。
2、能利用堆排序构建初堆。
四、算法
涉及全书内容，但重点在链表、栈、队列、树、图这几章，是难点。
链表：
1、一带头结点的单链表，删除最大（最小）元素。
2、一带头结点的单链表，将奇数元素全部放在前面，偶数元素全部放在后面。
3、某个带头结点的有序单链表L（元素从小到大），编写算法插入值为x的元素，使插入后的链表依旧有序。
4、已知带头结点的单链表L，编写算法删除L中从第k个结点开始的n个结点。
栈和队列：
1、链栈的进栈和出栈算法。
2、循环队列的进队和出队算法。
区别队空，队满有两个办法：一是少用一个单元；二是设置标志。每个办法下如何初始化，进队，出队算法都要会写.
3、用带尾指针的循环队列表示队列。队列的出队和入队操作。
二叉树：
1、二叉树的遍历，根据实际问题，选择遍历序列。
2、二叉树如何线索化。（中序、先序、后序，也是遍历的应用）
3、在线索二叉树中如何某结点前驱或后继。
4、树以孩子-兄弟链存储时，如何统计叶子、求高度、按凹入表示打印树、层
次遍历或者按（双亲，孩子）的形式打印的算法。
5、二叉树的层次遍历。
6、最容易和二叉排序一起考。既考了二叉排序树，又考了二叉树遍历。
图：
1、要能根据输入，建立一个图。（无向图、有向图，图的存储结构为邻接
矩阵或邻接表）
2、要在能图的邻接矩阵或邻接表存储结构上实现图的深度或广度优先遍
历。
3、编写算法，在某图中，判断从vi到vj是否有路径相通。(两种存储结构
上都能完成)
查：
因为只讲了顺序查、折半查、分块查、二叉排序树。算法题一般就下面几个：
1、折半查的递归和非递归算法
2、二叉排序按递增顺序输出。（中序遍历）
排序：
排序这章涉及很多排序算法，题目一般为简单、分析或构造题。算法会少一些。
1. 一趟快速排序
2. 单链表存储结构中的简单选择排序。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。