A.O
（1）B.O（n）C.O（log2n）D.O（n2）
第二章线性表（讲课4学时，实验4学时）
1．教学内容：
线性表的逻辑结构；
线性表的基本运算；
线性表的顺序存储结构；
在顺序表上实现的数据结构的基本运算；
线性表的链式存储结构：
单链表、循环链表、双向链表；
在链式存储结构上实现的数据结构的基本运算
2．教学要求：
理解线性表的逻辑结构定义、抽象数据类型定义。
掌握线性表的两种存储结构（顺序的和链式的）的描述方法，及其在顺序存储结构和各种链表结构上实现的基本操作：
如查找、插入和删除的算法。
掌握静态链表及运算。
了解一元多项式的表示及相加算法。
3．教学重点：
线性表的定义、逻辑特点；线性表各种存储结构的特点﹑数据类型描述；在各种存储结构（顺序表、单向链表、循环链表、双向链表）中实现线性表操作（如插入、删除、查找等算法）的基本方法。
教学难点：
链表本质及其操作的实现算法。
4．教学策略：
讲授法配合板书
5．教学预习：
线性表的基本概念及有关操作。
6．习题：
（1）若某线性表采用顺序存储结构，每个元素占四个存储单元，首地址为100，则下标为11的（第12个）元素的存储地址为（）。
（2）下列说法正确的是（）。
A.线性表的逻辑顺序与存储顺序总是一致的
B.线性报第链式存储结构中，内存中可用的存储单元可以使连续的，也可以不连续
C.线性表弟顺序存储结构优于链式存储结构
D.每种数据结构都具有插入、删除和查找三种基本运算
（3）L是线性表，已知ListLength（L）的值是5，运算DeleteList（L，2）后ListLength（L）的值是（）。
A.5B.0C.4D.6
（4）线性表中哪些元素只有一个直接前驱和一个直接后继（）。
A.首元素B.尾元素C.中间元素D.所有的元素
（5）线性表（L）经运算InitList（L）后，函数IEmpty（L）的值是（）。
A.0B.,falseC.1D.Null
（6）指针P指向循环链表L的首元素的条件是（）。
A.P=LB.P->nest=LC.L->nest=PD.P->nest=null
（7）线性表中各元素之间的关系是（）关系。
A.层次B.网状C.有序D.集合
（8）在单链表的一个结点中有（）个指针。
A.1B.2C.0D.3
（9）在双向链表的一个结点中有（）个指针。
A.1B.2C.0D.3
（10）设非空单链表的数据字段为data，指针字段为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i+1个结点，下列算法段能正确完成上述要求的是（）。
A.s->next=p->next=s；B.p->next=s；s->next=p->next；
C.s->next=p->next；p->next=s；交换p->data和s->data；D.p=s；s->next=p
（11）设双链表中结点的前趋指针的字段分别为t1和rl，则删除双链表中指针s所指结点的操作为（）。
A.s->t1-r1=s->t1；s-r1=s->r1；B.s->t1-r1=s->r1；s->r1=s->t1；
C.s->r1=s->t1；s->t1=s->r1->t1；D.s->t1=s-t1->r1；s->r1=s->t1；
（12）假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针字段，现要把一个指针s所指的新结点作为非空双链表中q所指结点（中间结点）的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是（）。
A.q->right=s；s-left=q；q-right->left=s；s-right=q->right；
B.s->left=q；q->right=s；q->right->left=s；s->right=q->right；
C.s->left=q;s-right=q->right;q->right-left=s;q-right=s;
D.以上都不对
第三章栈和队列（讲课4学时，实验2学时）
1．教学内容：
栈的概念、存储结构及其基本操作；
队列的概念、存储结构及其基本操作；
栈与队列的应用举例；
2．教学要求：
理解栈和队列的结构特性及抽象数据类型定义，并能在相应的应用问题中正确选用；理解函数调用时运行栈机制；理解递归算法执行过程中栈的状态变化过程。
掌握在两种存储结构上（顺序的和链式的）如何实现栈和队列的基本操作以及栈和队列在程序设计中的应用。
3．教学重点：
栈和队列的定义、特征；顺序栈、链栈的描述及基本操作实现算法；循环队列和链队列的基本操作实现算法。
教学难点：
栈满、栈空的条件及描述方法；队满和队空的描述方法；循环队列上的插入、删除操作。
4．教学策略：
讲授法配合板书
5．教学预习：
栈与队列的概念及基本操作。
6．习题：
（1）栈是限定在处进行插入或删除操作的线性表（）。
A、端点B、栈底C、栈顶D、中间
（2）在栈顶一端可进行的全部操作时（）。
A、插入B、删除C、插入和删除D、进栈
（3）4个元素按A、B、C、D、顺序连续进Szhan栈，进行Pop（S，x）元素后，x的值是（）。
A、AB、BC、CD、D
（4）栈的特点是（）。
A先进先出B后进先出C后进后出D不进不出
（5）栈结构的元素个数是（）。
A不变的B可变的C任意的D0
（6）4个元素进S栈的顺序是A、B、C、D，进行两次Pop（S，x）操作后，栈顶元素的值是（）。
A、AB、BC、CD、D
（7）同一个栈内各元素的类型（）。
A必须一致B可以不一致C不能一致D不必不一致
（8）顺序栈存储空间的实现使用（）。
A链表B数组C循环链表D变量
（9）一个顺序栈一旦说明，其占用空间的大小（）。
A已固定B可以改变C不能固定D动态变化
（10）栈是一个线性表结构（）。
A不加限制的B加了限制的C推广了的D非
（11）栈与一般线性表区别主要在方面（）。
A元素个数B元素类型C逻辑结构D插入、删除元素的位置
（12）顺序栈是空栈的条件是（）。
A.top==0B.top==1C.top==-1D.top==m
（13）元素A、B、C、D依次进顺序栈后，栈顶元素是（）。
A.AB.BC.CD.D
（14）经过下列栈的运算后GetTop（s）的值是（）。
InitStack（s）；Push（s，a）；Push（s，b）；Pop（s）；
A.aB.bC.1D.2
（15）经过下列栈的运算后EmptyStack（s）的值是（）。
InitStack（s）；Push（s，a）；Push（s，b）；Pop（s，x）；Pop（s，x）；
A.aB.bC.1D.0
（16）队列是限定在处进行插入操作的线性表（）。
A.端点B.队头C.队尾D.中间
（17）队列是限定在处进行删除操作的线性表（）。
A.端点B.队头C.队尾D.中间
（18）队列的特点是。
A.先进先出B.后进先出C.先进后出D.不进不出
（19）循环队列Sq是空队列的条件是（）。
ASq->read==Sq->frontB（Sq->read+1）％maxsize==Sq->front
CSq->read==0DSq->front==0
（20）循环队列Sq是满队列的条件是（）。
ASq->read==Sq->frontB（Sq->read+1）％maxsize==Sq->front
CSq->read==0DSq->front==0
（21）当循环队列Sq是满队列时，存放队列元素的数组data有n个元素，则data中存放个队列元素（）。
A.nB.n-1C.n-2D.0
（22）经过下列运算后GetHead（Q）的值是（）。
InitQueue（Q）；EnQueue（Q，a）；EnQueue（Q,b）；OutQueue（Q，x）；
A.aB.bC.1D.2
（23）链栈ls是空栈的条件是（）。
A.ls==nullB.ls->next==nullC.Ls==0D.ls->next==ls
（24）设将整数1,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
①若入、出栈次序为Push
（1），Pop（），Push
（2），Push（3），Pop（），Pop（），Push（4），Pop（），则出栈的数字序列为何（这里Push（i）表示进栈，Pop（）表示出栈）？
②能否得到出栈序列1423和1432？
并说明为什么不能得到或者如何得到。
③请分析1,2,3,4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。
第四章串（4学时）
1．教学内容：
串的定义、存储结构和基本运算、模式匹配；熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法；
熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。
掌握串的堆存储结构以及在其上实现串操作的基本方法。
了解串操作的应用方法和特点。
2．教学要求：
了解串的抽象数据类型定义。
掌握串的定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现及其应用；串的模式匹配算法。
理解KMP算法。
3．教学重点：
串的数据类型定义；串的三种存储表示；串的模式匹配算法。
难点：
KMP模式匹配算法。
4．教学策略：
讲授法配合板书
5．教学预习：
串的定义、存储结构和基本运算、模式匹配。
6．习题：
（1）设S=“IAMASTUDENT”，其长度是（）。
（2）串是一种特殊的线性表，其特征体现在。
A可以顺序存储B数据元素是一个字符
C可以链接存储D数据元素可以使多个字符
（3）设有两个串p和q,求q在p中首次出现的位置的运算称作（）。
A连接B模式匹配C求串长D求子串
（4）设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算：
S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（）。
A、BCDEFB、BCDEFGC、BCDPQRSTD、BCDEFER
（5）判断题
空格串和孔串的长度均为1。
（）
串是一种特殊的线性表，其特殊性体现在数据元素可以使多个字符。
（）
判断两个串是否相等，只需要判断这两个串是否包含相同的字符即可。
（）
将一个n×n的对称矩阵，以行为主序或以列为主序存入内存，其容量至少为n2。
（）
若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行标和列标互换，就完成了对该矩阵的转置运算。
（）
第五章数组和广义表（4学时）
1．教学内容：
了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。
掌握对特殊矩阵进行压缩存储时的下标变换公式。
了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。
2．教学要求：
了解多维数组的结构特点和抽象数据类型定义；了解稀疏矩阵的两种压缩存储方法的特点和适用范围；理解以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。
掌握数组的两种存储表示方法以及数组元素存储位置的计算公式；掌握特殊矩阵压缩存储方法及地址变换公式；掌握广义表的结构特点及其存储表示方法。
理解广义表的递归算法。
3．教学重点：
数组的两种存储表示方式及元素存储地址的计算公式；特殊矩阵和稀疏矩阵的压缩存储方法；广义表的定义、长度﹑深度﹑广义表的存储结构以及广义表的表头、表尾操作。
难点：
特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现。
4．教学策略：
讲授法配合板书
5．教学预习：
数组的存储表示。
6．习题：
（1）对于一个二维数组A[0..m][0..n]，若按行序为主序存储，则人一元素A[i][j]的存储地址为（）。
（2）设数组R[1..10，-2..6，2..8]以行序为主序存储，设第一个元素的首地址为100，每个元素占3个存储单元，则元素A[5，0，7]的存储地址为（）。
（3）设有一个10阶对称矩阵A采用压缩存储方式以行序为主序位存储，a85的存储地址为（）。
（4）数组的基本操作主要包括（）。
A建立与删除B索引与修改C访问与修改D访问与索引
（5）稀疏矩阵一般的压缩存储方法有两种，即（）。
A二维数组和三维数组B三元组和散列
C三元组和十字链表D散列和十字链表
（6）设矩阵A是一个对称矩阵，为了节省空间，将其下三角矩阵按行序存放在一维数组B[1，n（n+1）/2]中，对下三角部分中任一元素aij（i≥j），在一维数B中下标k的值是（）。
Ai（i-1）/2+j-1Bi（i-1/2+jCi（i+1）/2+j-1Di（i+1）/2+j
第六章树和二叉树（讲课8学时，实验4学时）
1．教学内容：
树的定义和存储结构；
二叉树的定义、性质、存储结构；
二叉树的遍历、线索算法；
树和二叉树的转换；
哈夫曼树及其应用
2．教学要求：
掌握二叉树的定义、性质和存储结构，二叉树遍历的方法和算法。
理解二叉树线索化的实质，掌握二叉树的线索化过程以及在线索二叉树上找给定结点的前驱和后继的方法。
了解树和森林的定义、各种存储结构及其特点；理解树和森林的遍历；掌握树的性质、树和森林与二叉树的相互转换方法。
掌握最优二叉树的定义、建立哈夫曼和哈夫曼编码的方法，理解构造哈夫曼树及求哈夫曼编码的算法。
3．教学重点：
二叉树的定义、性质、存储结构及各种存储结构的特点及适用范围；二叉树的遍历方法及各种遍历策略的递归和非递归算法；二叉树线索化算法；树的性质、存储结构、与二叉树的转换；哈夫曼树的定义、构造方法及其应用。
教学难点：
深入理解二叉树的递归定义，灵活运用二叉树的遍历方法解决相关应用问题。
4．教学策略：
讲授法配合板书
5．教学预习：
树的概念和存储、性质、基本操作。
6．习题：
填空题
（1）假定一棵树的嵌套括号表示法为A（B（E）,C（F（H,I,J）,G）,D），则该树的度为（），树的深度为（），终端点的个数为（），分支结点的个数为（），双分支结点为（），三分支结点的个数为（），C结点的双亲结点为（），其孩子结点为（）和（）。
（2）设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针字段为空的结点有（）。
（3）对于一个具有n个结点的二叉树，当它储存在二叉树表中时，其指针字段的总数为（）个，其中（）个用于链接孩子点，（）个空暇，
（4）一棵深度为K的满二叉树结点总数为（），一棵深度为K的完全二叉树的结点总数的最小值为（），最大值为（）。
（5）如果T2是由有序树T转换而来的二叉树，那么T中结点的（）序是T2中结点的（）。
（6）具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的分支结点序号为（），编号最小的分支结点序号为（），编号最大的叶子结点序号为（），编号最小的叶子结点序号为（）。
（7）有m个叶子结点的哈夫曼树，其结点总数为（）。
（8）由三个结点构成的二叉树，共有（）种不同的结构。
选择题
（1）将一棵有100个结点的完全二叉树，从根这一层开始，每一层从左到右依次对结点编号，根据点的编号为1，则编号为49的结点的双亲的编号为（）。
A.24 B.25C.23D无法确定
（2）深度为６（根据的层次为１）的二叉树至多有（）结点。
A64B63C31D32
（3）设二叉树有n个结点，则其深度为。
An-1BnC㏒2nD无法确定
（4）设森林Ｔ中有三棵树，第一、第二、三棵数的活结点个数分别为n1n2n3,那么将森林转换成二叉树后，其根结点的右子树上有（）个结点。
An1-1Bn2+n3Cn1+n2+n3Dn1
（5）设森林Ｔ中有三棵树，第一、二、三棵数的结点个数分别为n1n2n3，那么将森林转换成二叉树后，其根结点的左子树上有（）个结点。
Ａ.n1-1 Ｂ.n2+n3 Ｃ.n1+n2+n3 Ｄ.n1
（6）设深度为Ｋ的二叉树上只有度为０或度为２的结点，则这类二叉树上所含结点总数至少（）。
Ａ.Ｋ＋１ Ｂ.２Ｋ Ｃ２Ｋ—１ Ｄ２Ｋ＋１
（7）树转换成二叉树后，以下结论正确的是（）。
A树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B树的先根遍历序列与其对应的二叉树的中序遍历序列相同
C树的后根遍历序列与其对应的二叉树的后序遍历序列相同
D以上都不对
（8）某二叉树的前序遍历结点访问顺序为，ABDGCDFH中序遍历结点访问顺序为DGBAECHE，则其后续遍历结点访问顺序为（）。
A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GD
升级会员 