文档介绍：数据结构与算法设计知识点
试题类型：本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %），算法设计题（10 %）。
第一章据元素或数据元素的映象）单链表是一种顺序存取的结构，求以此为存储表示的线性表长度，可设置一个计数器
3、了解有序线性表的特点（顺序有序表、有序链表）。
有序线性表：线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即a $a 或a W
i i-1 i
a （i = 2,3,…，n）,则称该线性表为有序表（Ordered List）
i-1
4、学会对线性表设计相关的算法进行相应的处理。
第三章排序
重点内容及要求：
1、掌握对顺序表数据记录进行排序的基本思路和常规操作（比较、移动），了解排序算法的稳定性问题。
2、掌握简单选择排序、直接插入排序、冒泡排序算法，了解各种排序算法的特点及时间复杂度。
排序：将一组“无序”的记录序列按某一关键字调整为“有序” 的记录序列。
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之则为外部排序。
选择排序：从记录的无序子序列中“选择”关键字最小或最大的
记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度
基本代码如下
for(i=0;i<n-1;i++)/*外循环控制趟数，n个数选n-1趟*/
{
k=i；/*假设当前趟的第一个数为最值，记在k中*/
for(j=i+1;j<n;j++)/*从下一个数到最后一个数之间找最值*/
if(a[k]<a[j])/*若其后有比最值更大的*/
k=j;/*则将其下标记在k中*/
if(k! = i)/*若k不为最初的i值，说明在其后找到比其更大的数*/
{
t二a[k];a[k]二a[i];a[ i]二t ;}/*则交换最值和当前序列的第一个数*/
}
插入排序：插入排序是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
代码如下：void InsertSort ( SqList &L) //对顺序表L作插入排序
{
for ( i=2; i<=; ++i )
if ( [i].key < [i-1].key )
{
[0] = [i]; //复制为哨兵
for ( j=i-1; [0].key < [j].key; --j )
[j+1] = [j]; //记录后移
[j+1] = [0]; //插入到正确位置
}
}
冒泡排序：泡排序是一种最直观的排序方法，在排序过程中，将相邻的记录的关键字进行比较，若前面记录的关键字大于后面记录的关键字，则将它们交换，否则不交换。或者反过来，使较大关键字的记录后移，像水中的气泡一样，较小的记录向前冒出，较大的记录
像石头沉入后部。故称此方法为冒泡排序法
代码如下：
void BubbleSort( SqList &L )
{ RcdType W；
i = ;
while (i >1) { // i>1 表明上一趟曾进行过记录的交换
lastExchangeIndex = 1;
for (j = 1; j < i; j++){
if ([j+1].key < [j].key) {
W=[j]；[j] =[j+1]；[j+1] = W； // 互换记录
lastExchangeIndex = j;
}
}
i = lastExchangeIndex; // 一趟排序中无序序列中最后一个记录的位置
3、了解什么是堆？
堆是满足下列性质的数列{r , r ,…，r }:
1 2 n
r （小顶堆r
r （大顶堆）
< i 2i <
i 2i
r < r
r > r
J i 2i +1
J i 2i +1
第四章栈和队列
重点内容及要求：
1、掌握栈和队列的结构特点及基本操作(入栈、出栈/入队、出队)。
栈(后进先出)，队列(先进先出)
构造空栈：
void InitStack_Sq (SqStack &S)
{ // 构造一个空栈 S
= new SElemType[maxsize];
=-1;
= maxsize;
=incresize;
}
栈：(入栈)
void Push_Sq