A[i][j]=0;
2）i=1;
while（i<=n）i=i*3;
4.在n个结点的顺序表中，算法的时间复杂度是O
（1）的操作是：
（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
（B）在第i个结点后插入一个新结点（1≤i≤n）
（C）删除第i个结点（1≤i≤n）
（D）将n个结点从小到大排序
第二章线性表
知识点：
顺序表、单链表、双向链表（插入、查找、删除运算）循环链表（单双向）特点，
考点：
基本操作、复杂度、特点、算法应用
1.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是
（ ）
A.p->next=qB.p->next=q->next
C.p=q->nextD.p->next=q->next->next
2、在一个头指针为head的带头结点单链表中，要向表头插入一个由指针p指向的结点,则应执行、。
在双链表中，在指针P所指结点前面插入一个结点S时的语句序列是：
S->next=P;S->prior=P->prior;P->prior=S;____S->prior->next=S___；
3.在双向链表指针p的结点前插入一个指针q的结点操作是（）。
A.p->Prior=q;q->Next=p;p->Prior->Next=q;q->Prior=p->Prior;
B.p->Prior=q;p->Prior->Next=q;q->Next=p;q->Prior=p->Prior;
C.q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p->Prior=q;
D.q->Prior=p->Prior;q->Next=p;p->Prior=q;p->Prior->Next=q;
4.已知p结点是某双向链表的中间结点，要删除p结点的直接后继结点的语句序列是：
A.p->next->next->prior=p;p->next=p->next->next;q=p->next;free（q）;
B.q=p->next;p->next=p->next->next;p->next->next->prior=p;free（q）;
C.q=p->next;p->next->prior=p;p->next=p->next->next;free（q）;
D.q=p->next;p->next=p->next->next;p->next->prior=p;free（q）;
5.设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___________；r=s;r->next=null;。
7对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为,在给定值为x的结点后插入一个新结点的时间复杂度为___。
8.在顺序表中访问任意一结点的时间复杂度均为，因此顺序表也称为的数据结构。
9、线性链表不具有的特点是（）。
A．随机访问B．不必事先估计所需存储空间大小
C．插入与删除时不必移动元素D．所需空间与线性表长度成正比
10.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。
A.单链表B.双链表
C.带头结点的双循环链表D.单循环链表
11.带头结点的双循环链表L为空表的条件是_______。
12.不带头结点的单链表head为空的判定条件是。
15.对于长度为n的顺序表执行删除操作，则其结点的移动次数（ ）
A.最少为0，最多为nB.最少为1，最多为n
C.最少为0，最多为n-1D.最少为1，最多为n-1
16.线性表的长度是线性表所占用的存储空间的大小。
（对还是错）
17.双循环链表中，任意一结点的后继指针均指向其逻辑后继。
（对还是错）
18、线性表Ｌ在情况下适用于使用链式结构实现。
Ａ、需经常修改Ｌ中的结点值Ｂ、需不断对Ｌ进行删除插入
Ｃ、Ｌ中含有大量的结点Ｄ、Ｌ中结点结构复杂
19若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
①单链表②双链表③单向循环④顺序表
1.假设线性表L=（a1,a2,……,an）用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为（an,……,a2,a1）。
2．试编写算法，以统计带头结点单链表的元素个数。
3.设某单链表Ｌ的结点结构为data|next,试编写算法判断该链表的元素是否是递增的。
4.已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点（若表中有这样的结点），同时释放被删结点的空间，这里min 和 max是两个给定的参数。
请分析你的算法的时间复杂度。
第3章栈和队列
知识点：
栈、循环队列
考点：
出入栈操作、栈和队列特点、循环队列操作（元素个数、队头队尾指针）、应用
1．一个栈的入栈序列是1、2、3、4，若第二个出栈的元素是4，则最后出栈的元素可能是 。
2.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）
A.23415B.54132
C.23145D.15432
3.在对链队列作出队操作时，不会改变front指针的值。
（对还是错）
4.若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=n-i+1（i=1,2...,n）（对还是错）
5.栈是一种特殊的线性表，允许插入和删除运算的一端称为,不允许插入和删除运算的一端称为。
6、如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为______。
7．有5个元素，其入栈次序为：
A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
8、向顺序栈中压入新元素时，应当（）。
A．先移动栈顶指针，再存入元素B．先存入元素，再移动栈顶指针
C．先后次序无关紧要D．同时进行
9.设一个链栈的栈顶指针是ls，栈中结点格式为info|link,栈空的条件是__________.如果栈不为空，则退栈操作为p=ls；___；free（p）;。
10.如果以链表作为栈的存储结构，则退栈操作时（）
1必须判别栈是否满
2对栈不作任何判别
3必须判别栈是否空
4判别栈元素的类型
11.判定一个栈ST（最多元素为m0）为空的条件是
Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0
13.判定一个队列QU（最多元素为m0）为满队列的条件是
A．QU->rear－QU->front==m0B．QU->rear－QU->front－1==m0
C．QU->front==QU->rearD．QU->front==QU->rear+1
14.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？
15、假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为______。
16.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）
①front=front+1②front=（front+1）%m
③rear=（rear+1）%m④front=（front+1）%（m+1）
12.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ）
A．队列 B．栈
C．线性表 D．有序表
13.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。
A．树B.队列C.栈D.图
17.简述以下算法的功能（栈和队列的元素类型均为int）。
voidalgo3（Queue&Q）{
StackS;intd;
InitStack（S）;
while（!
QueueEmpty（Q））{
DeQueue（Q,d）;Push（S,d）;
};
while（!
StackEmpty（S））{
Pop（S,d）;EnQueue（Q,d）;
}
}
第4章数组
知识点：
二维数组的存储、特殊矩阵
1.假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。
已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为。
2.假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储，其基地址为1000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（）。
（无第0行第0列元素）
（Ａ）．4454（Ｂ）．6904（Ｃ）．7902（Ｄ）．答案A,B,C均不对
3．数组A［５］［６］的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，５］的地址为（）
A.1140B.1145
C.1120D.1125
4.二维数组A［15］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（ ）
A.700B.1120
C.1180D.1140
7.下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。
i
j
v
7
6
6
1
4
7
2
1
8
3
5
9
4
2
7
6
5
3
7
3
1
8、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中（）位置。
A．32B．33C．41D．65
9、假设有100行200列的二维数组a[100][200]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第45行第67列的元素a[44][66]的存储地址为。
11.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B中（注：
B下标从0开始），求矩阵中任一元素ai,j（i≤j）和一维数组B中下标k的对应关系。
第5章二叉树
知识点：
树、二叉树（完全二叉树）、森林基本概念（度、），存储结构，遍历
1、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。
A．n-1B．nC．n+1D．n+2
2．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有__________个叶子的结点。
5、若一棵二叉树中度为2的结点数是10，则叶子结点数为个。
6.深度为6（根的层次为1）的二叉树至多有（）结点。
164②32③31④63
7.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。
编号为49的结点X的双亲编号为（）
①24②25③23④无法确定
8.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点；有个度为2的结点，有个度为1的结点。
9.一棵具有２５７个结点的完全二叉树，它的深度为。
10、已知完全二叉树的第8层有8个结点，则其叶子结点数是68。
11.在完全的二叉树中，若一个结点没有，则它必定是叶结点。
A.左子结点B.右子结点C.左子结点或者没有右子结点D.兄弟
12.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是（）的二叉树。
A.空或只有一个结点B.高度等于其结点数
C.任一结点无左孩子D.任一结点无右孩子
13.在有n个结点的二叉链表中，值为非空的链域的个数为（）
A.n-1B.2n-1
C.n+1D.2n+1
14.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（）
A.0B.1
C.2D.不确定
15.DFS算法的时间复杂度为（）
A.O（n）B.O（n3）
C.O（n2）D.O（n+e）
16、有n个叶子结点的哈夫曼（Huffman）树所具有的结点数为
22.给定二叉树的两种遍历序列，分别是：
中序遍历序列：
DCBGEAHFIJK；后序遍历序列：
DCEGBFHKJIA。
（1）请画出该树。
23.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为
a
b
c
d
e
f
g
h
0.07
0.19
0.02
0.06
0.32
0.03
0.21
0.10
要求：
（1）为这8个字母设计哈夫曼编码，并画出哈夫曼树。
（2）求该哈夫曼树的带权路径长度。
26.已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
data
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
parent
0
1
1
1
2
2
3
3
4
4
5
6
6
7
8
第6章图
知识点：
基本概念（度、完全图、连通子图、生成树、最小生成树），图的存储（邻接矩阵、邻接表），图的遍历，最小生成树，拓扑排序，最短路径，关键路径
2.有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的非零元个数。
（对还是错）
3.有向图的邻接表和逆邻接表中的结点数一定相同。
（对还是错）
5.在一个图中，所有顶点的度数之和等于图的边数的倍。
A．1/2B.1C.2D.4
6.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。
A．1/2B.1C.2D.4
7.已知图的邻接表如下图1所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是
A．0132B.0231C.0321D.0123
8．有n个顶点的强连通有向图G至少有条弧。
17.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。
A．树B.队列C.栈D.图
2.已知图的邻接矩阵，根据算法，分别求从顶点0出发按深度和广度优先遍历的结点序列。
5.已知某有向图的邻接矩阵如右图所示，要求：
（1）确定图中每个顶点的入/出度；
（2）画出该图；
（3）画出该图的邻接表
（4）画出该图的逆邻接表。
第7章查找
知识点：
折半查找过程，堆概念，二叉排序树，哈希查找
1.对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标依次为（）
A.1，2，3B.9，5，2，3
C.9，5，3D.9，4，2，3
2、对表长为900的索引顺序表进行分块查找，假设每一块的长度均为15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为_____。
3.在表长为ｎ的链表中进行线性查找，它的平均查找长度为。
7、）假定对有序表：
（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。
（1）画出描述折半查找过程的判定树；
（2）若查找元素54，需依次与哪些元素比较？
（3）若查找元素90，需依次与哪些元素比较？
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
8、设哈希（Hash）表的地址范围为0～15，哈希函数为：
H（Key）＝Keymod13。
Key为关键字，用线性探测法再散列法处理冲突，输入关键字序列：
（10，24，32，17，31，30，46，48，41，65，49）
造出Hash表，试回答下列问题：
（1）画出哈希表的示意图；
（2）若查找关键字30，需要依次与哪些关键字进行比较？
12.下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。
typedefstructpnode
{intkey;
structpnode*left,*right;
}pnode;
voidsearchinsert（intx,pnodet）/*t为二叉排序树根结点的指针*／
{if（）
{p=malloc（size）;
p->key=x;p->lchild=null;
p->rchild=null;t=p;
}elseif（xkey）searchinsert（x,t->lchild）
else_________;
}
13．设n个元素的有序表为Ｒ，Ｋ为一个给定的值，二分查找算法如下：
intbinsearch（sqlistR,keytypeK）
{j=1;h=n;suc=0;
while（（j<=h）&&（!
suc））
{mid=（j+h）/2;
switch
{caseK=R[mid].key:
suc=1;break;
caseKh=mid-1;break;
caseK>R[mid].key:
j=mid+1
}
}
if（suc）return（mid）;elsereturn（0）;
}
将上述算法中划线语句改为：
Kh=mid.
（1）改动后，算法能否正常工作？
请说明原因。
（2）若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。
14.从空树起，依次插入关键字37，50，42，18，12，56，30，23，构造一棵二叉排序树。
（1）画出该二叉排序树。
（2）画出从
（1）所得树中删除关键字为37的结点之后的二叉排序树。
第九章排序
知识点：
排序算法的稳定性，各类排序算法执行过程、复杂性分析，
3.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行（按递增排序）， 冒泡排序 最省时间，快速排序 最费时间。
5、堆是一种排序。
Ａ.插入Ｂ.选择Ｃ.交换Ｄ.归并
6、若一组记录的排序码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为
Ａ.38,40,46,56,79,84Ｂ.40,38,46,79,56,84
Ｃ.40,38，46,56,79,84Ｄ.40,38,46,84,56,79
8.在插入和选择排序中，若初始数据基本正序，则选用；若初始数据基本反序，则选用。
10.冒泡排序在最好情况下时间复杂度为。
11.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？
A.直接插入排序 B.起泡排序 C.快速排序 D.直接选择排序
13．从未排序序列中挑选元素，并将其依次插入已排序序列的一端的方法，称为
（Ａ）.希尔排序（Ｂ）.归并排序Ｃ.插入排序Ｄ.选择排序
17．有一组键值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。
升级会员 