文档介绍：数据结构与算法设计知识点
试题类型：
本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10%）,是非判断题（10%）, 单项选择题（40 %），算法填空题（10%），算法应用题（20 %），算法设计题（10 %）。
第一章绪论链表是一种顺序存取的结构，求以此为存储表示的线性表长
度，可设置一个计数器
3、了解有序线性表的特点（顺序有序表、有序链表）。
有序线性表：线性表中的数据元素相互之间可以比较，并且数据
元素在线性表中依值非递减或非递增有序排列，即a.，
(i = 2,3，…，n),则称该线性表为有序表(Ordered List)
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、 了解什么是堆？
堆是满足下列性质的数列{r1, r2,…，r }:
< (，品i
I i — 2i +1
第四章栈和队列
重点内容及要求：
1、掌握栈和队列的结构特点及基本操作（入栈、出栈/入队、出队）。
栈（后进先出），队列（先进先出）
构造空栈：
void InitStack_Sq （SqStack &S）
{ //构造一个空栈S
= new SElemType[maxsize];
=-1 ;
= maxsize;
;
}
栈：（入栈）
void Push_Sq （SqStack &S, SElemType e） （
if （ = -1） incrementStacksize （S）;
//