A熟练掌握B理解C了解
第一章：绪论
1基本概念：
包括数据的逻辑结构、数据的存储结构和数据的相关运算。C
四类数据组织结构：集合、线性表、树形、图状结构C
数据的存储方式：顺序存储和链式存储。B
2算法和分析
算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度B
本章重点：分析算法时间复杂度
例1下面关于算法说法错误的是（）
A．算法最终必须由计算机程序实现
B为解决某问题的算法同为该问题编写的程序含义是相同的
C算法的可行性是指指令不能有二义性
D以上几个都是错误的
D
例2以下那一个术语与数据的存储结构无关？（）
A．栈
B哈希表
C线索树
D双向链表
A．
例3．求下段程序的时间复杂度：
voidmergesorti
tii
tj
i
tm
ifij
mij2
fmergesortim
mergesortm1j
mergeijm

其中mergesort用于对数组a
归并排序，调用方式为mergesort0
1，merge
用于两个有序子序列的合并，是非递归函数，时间复杂度为O
。
解：分析得到的时间复杂度的递归关系：
t


O12t


2


O


1


1
O
为merge（）所需的时间，设为c
（c为常量）。因此
t
2
2c
22t
22c
2c

22t
222c

2kt
2kkc

令

2k
1，有k
log2

有t
2log2
O1c
log2
c
log2
O
log2

第二章：线性表
1线性表的基本运算：…
C
2线性表的顺序存储（利用静态数组或动态内存分配）。相应的表示与操作A
3线性表的链式存储。相应的表示与操作。包括循环链表、双向链表。A
4顺序存储与链式存储的比较：基于时间的考虑分别适用于静态的和动态的操作：比如静
态查找和插入删除）；基于空间的考虑……
B
这也适用于后面用两种方式存储的其他数据结构。
★本章重点：很熟悉顺序表，单链表、双链表，循环链表的基本操作；并学会在各种链表上
f进行一些算法设计（与基本操作类似的操作或组合），请仔细复习。
例4．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将
这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结
点存放归并后的单链表。
题目分析因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比
较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排
列。故在合并的同时，将链表结点逆置。
voidU
io
Li
kListlaLi
kListlb
∥lalb分别是带头结点的两个单链表的头指针，链表中的元素r