2．线性结构的基本特征是：
若至少含有一个结点，则除起始结点没有直接__前驱_______外，其他结点有且仅有一个直接___前驱_____；除终端结点没有直接__后继_______外，其他结点有且仅有一个直接______后继___。
3．所有结点按一对一的邻接关系构成的整体就是____线形______结构。
4．线性表的逻辑结构是__线性_结构，其所含结点的个数称为线性表的___长度、_______。
5．在单链表中，删除p所指结点的直接后继的操作是___q=p->next；p->next=q->next；free（q）；__·
6．对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为___O
（1）_______，在给定值为x的结点后插入新结点的时间复杂度为__O（n）_______。
7．单链表表示法的基本思想是用___指针_________表示结点间的逻辑关系。
8．在顺序表中插入或删除一个元素，平均需要移动_____一半___元素，具体移动的元素个数与____元素位置_____有关。
9．在单链表中，若p和s是两个指针，且满足p->next与s相同，则语句p->next=s->next的作用是__删除__s指向的结点。
10．在单链表中，指针p所指结点为最后一个结点的条件是__p->next=NULL_________。
11．在单链表中，若要在p所指结点之前插入s所指的结点，可进行下列操作：
s->next=__p->next_________；p->next=s；temp=p->data；
p->data=_s->data_________；s->data=_temp________；
四、应用题
1．描述以下三个概念的区别：
头指针，头结点，首元结点（第一个元素结点）。
答：
首元结点是指链表中存储的线性表中的第一个数据元素的结点。
为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。
头指针是指向链表中的第一个结点的指针。
2．在顺序表中插入和删除一个结点需平均移动多少个结点？
具体的移动次数取决于哪两个因素？
答：
平均移动表中大约一半的结点，插入操作平均移动n/2个结点，删除操作平均移动（n-1）/2个结点。
具体移动的次数取决于表长和插入、删除的结点的位置。
3．如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。
在此情况下，应选择哪一种存储结构？
为什么？
答：
应选用链式存储结构。
因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。
而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。
4．若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？
为什么？
答：
应选用顺序存储结构。
因为顺序存储结构存取元素操作的时间复杂度为O
（1）。
补充：
何时选用顺序表，何时选用链表作为线性表的存储结构为宜？
答：
从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。
从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。
对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。
第三章栈和队列
一、选择题
1．设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是（）。
A．2B．3C．5D．6
2．设有一顺序栈已经含有3个元素，如下图所示，元素a4正等待入栈。
以下序列中不可能出现的出栈序列是（）。
A．a3，a1，a4，a2B．a3，a2，a4，a1C．a3，a4，a2，a1D．a4，a3，a2，a1
a1
a2
a3
top
3．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。
A．e，d，c，b，aB．d，e，c，b，aC．d，c，e，a，bD．a，b，c，d，e
4．一个队列的入队序列是1，2，3，4，则队列的可能的输出序列是（）。
A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，1
二、判断题
对1．在顺序栈栈满情况下，不能再入栈，否则会产生“上溢”。
错2．与顺序栈相比，链栈的一个优点是插入和删除操作更加方便。
错3．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2．
对4．一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。
三、填空题
1．在具有n个单元的循环队列中，队满时共有__n-1____个元素。
2．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为___bceda__________。
3．栈的逻辑特点是_先进后出__，队列的逻辑特点是_先进先出______，二者的共同特点是___操作受限________。
4．____栈______可以作为实现递归函数调用的一种数据结构。
5．在队列中，新插入的结点只能添加到__队尾__________。
6．设有一个空栈，假设以push和pop分别表示入栈和出栈操作，现在输入序列为1，2，3，4，5，经过push，push，pop，push，pop，push后，栈顶指针所指元素是___4____。
四、综合题
1.已知当前循环队的状态如图所示，请写出依次执行如下操作时队的状态。
d
e
f
frontrear
（1）g,h,i,j入队；
d
e
f
g
h
i
j
frontrear
（2）d,e出队；
f
g
h
i
j
frontrear
（3）k,l,m,n,o,p入队
l
m
n
f
g
h
i
j
k
rearfront
第四章树
一、选择题
1．以下说法错误的是（）。
A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B．在三叉链表上，二叉树的求双亲操作很容易实现
C．在二叉链表上，求根以及求左、右孩子等操作很容易实现
D．在二叉链表上，求双亲操作的时间性能很好
2．以下说法错误的是（）。
A．一般在哈夫曼树中，权值越大的叶子离根结点越近
B．哈夫曼树中没有度数为1的分支结点
C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点
D．若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树
3．深度为6的二叉树最多有（）个结点。
A．64B．63C．32D．31
4．将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为（）。
A．10B．11C．41D．20
5．一棵二叉树满足下列条件：
对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。
现采用（）遍历方式就可以得到这棵二叉树所有结点的递减序列。
A．前序B．中序C．后序D．层次
6．如图6-1所示的二叉树的中序遍历序列是（）。
A．abcdgefB．dfebagcC．dbaefcgD．defbagc
7．已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是（）。
A．acbedB．baedcC．dceabD．cedba
8．在图6-2中的二叉树中，（）不是完全二叉树。
9．哈夫曼树的带权路径长度是（）。
A．所有结点权值之和B．所有叶结点带权路径长度之和
C．带权结点的值D．除根以外所有结点权值之和
10．设有一棵22个结点的完全二叉树，那么整棵二叉树有（）个度为0的结点。
A．6B．7C．8D．11
11．已知完全二叉树有26个结点，则整棵二叉树有（）个度为1的结点。
A．0B．1C．2D．13
12．已知如图6-3所示的哈夫曼树，那么电文CDAA的编码是（）。
A．110100B．11011100C．010110111D．11111100
13．在n个结点的完全二叉树中，对任一结点i（1≤i≤n），i的左孩子可能是（）。
A．i/2B．2i+1C．2iD．都不是
14．已给出图6-3所示的二叉树，A，B，C，D的权值分别为7，5，2，4，则该树的带权路径长度为（）。
A．46B．36C．35D．都不是
二、填空题
1．树（及一切树形结构）是一种_________结构。
在树中，_________结点没有直接前驱。
对树上任一结点x来说，x是它的任一子树的根结点惟一的________。
2．二叉树第i（i>0）层上至多有__________个结点。
3．深度为k（k>0）的二叉树至多有__________个结点。
4．对任何二叉树，若度为2的节点数为n2，则叶子数n0=__________。
5．满二叉树上各层的节点数已达到了二叉树可以容纳的_________。
满二叉树也是__________二叉树，但反之不然。
6．具有n个结点的完全二叉树的深度为__________。
7．二叉树通常有_____________存储结构和__________存储结构两类存储结构。
8．每个二叉链表必须有一个指向_______结点的指针，该指针具有标识二叉链表的作用。
9．对二叉链表的访问只能从__________指针开始。
10．具有100个结点的完全二叉树的深度是__________。
11．在__________遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。
12．若一棵二叉树的叶子数为n，则该二叉树中左、右子树皆非空的结点个数为__________。
13．一棵树的形状如图6-5所示，它的根结点是________，叶结点是____________________________，结点H的度是______，这棵树的度是_______，这棵树的深度是________，结点F的儿子结点是_______，结点G的父结点是_________。
14．含有2n个结点的二叉树高度至少是________，至多是________（仅含根结点的二叉树高度为1）。
三、应用题
1．分别写出图6-7所示二叉树的前序、中序和后序序列。
2．已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树，并写出其前序遍历序列。
3．设某密码电文由8个字母组成，a,b,c,d,e,f,g,h，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼树及编码。
4．对于一个关键字序列15,28,3,38,12,2,56,17,20，请生成一个二叉排序树，并给出依次删除38,28后的结果。
第五章图
一、选择题
1．在一个图中，所有顶点的度数之和等于所有边数的（）倍。
A．1／2B．1C．2D．4
2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A．1／2B．1C．2D．4
3．一个有N个顶点的无向图最多有（）条边。
A．NB．N*（N-1）C．N*（N-1）／2D．2N
4．具有4个顶点的无向完全图有（）条边，
A．6B．12C．16D．20
5．具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。
A．5B．6C．7D．8
6．一个具有N个顶点的无向图中，要连通全部顶点至少需要（）条边。
A．NB．N+1C．N-1D．N／2
7．对于一个具有N个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。
A．NB．（N-1）*（N-1）C．N-1D．N*N
8．对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为（
（1））；所有邻接表中的结点总数是（
（2））。
（1）A．NB．N+1C．N-1D．N+E
（2）A．E/2B．EC．2ED．N+E
二、填空题
1．对无向图，其邻接矩阵是一个关于主对角线对称的矩阵。
2．在有向图的邻接矩阵上，由第i行可一得到第个结点的出度，而由第j列可得到第个结点的入度。
3．对无向图，设有n个结点e条边，则其邻接表表示中需要个表结点。
对有向图，设有n个顶点e条弧，则其邻接表表示需要个表结点。
4．在无权图G的邻接矩阵A中，若（Vi，Vj）或属于图G的边集，则对应元素A[i，j]等于，否则等于。
5．遍历图的基本方法有优先搜索和优先搜索两种。
三、应用题
1．给出如图5-1所示的无向图G1的邻接矩阵和邻接表。
2．分别给出图5-1所示的G2的邻接矩阵、邻接表和逆邻接表。
图5-1
第六章查找
一、选择题
1．顺序查找法适合于（）存储结构的查找表。
A．压缩B．散列C．索引D．顺序或链式
2．对采用折半查找法进行查找操作的查找表，要求按（）方式进行存储。
A．顺序存储B．链式存储
C．顺序存储且结点按关键字有序D．链式存储且结点按关键字有序
3．设有序表的关键字序列为（1，4，6，10，18，35，42，53，67，71，78，84，92，99），当用折半查找法查找键值为35的结点时，经（）次比较后查找成功。
A．
升级会员 