A．n-iB．n-i+lC．n-i-1D．i
8.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行
A．s->next=p->next;p->next=s
B．q->next=s;s->next=p
C．p->next=s->next;s->next=p
D．p->next=s;s->next=q
9.以下关于线性表的说法不正确的是______。
A．线性表中的数据元素可以是数字、字符、记录等不同类型。
B．线性表中包含的数据元素个数是有限的。
C．线性表中的每个结点都有且只有一个直接前趋和直接后继。
D．存在这样的线性表：
表中各结点都没有直接前趋和直接后继。
10.线性表的顺序存储结构是一种_______的存储结构。
A．随机存取B．顺序存取C．索引存取D．散列存取
11.在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。
A．基地址B．结点大小
C．向量大小D．基地址和结点大小
12.在等概率情况下，顺序表的插入操作要移动______结点。
A．全部B．一半
C．三分之一 D．四分之一
13.在______运算中，使用顺序表比链表好。
A．插入 B．删除
C．根据序号查找 D．根据元素值查找
14.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。
A．O
（1） B．O（n）
C．O（n2）D．O（log2n）
15.设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列__________。
A．A,B,C,D,EB．B,C,D,E,A
C．E,A,B,C,DD．E,D,C,B,A
16.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。
A．top不变B．top=0C．top--D．top++
17.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行______。
A．hs->next=s;
B．s->next=hs;hs=s;
C．s->next=hs->next;hs->next=s;
D．s->next=hs;hs=hs->next;
18.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。
A．rear％n==frontB．（front+l）％n==rear
C．rear％n-1==frontD．（rear+l）％n==front
19.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为________。
A．rear％n==frontB．front+l=rear
C．rear==frontD．（rear+l）％n=front
20.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为________。
A．front=front->next B．rear=rear->next
C．rear=front->next D．front=rear->next
二、填空题
1.线性表是一种典型的_________结构。
2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。
3.顺序表中逻辑上相邻的元素的物理位置________。
4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。
5.在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。
6.在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。
7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。
相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。
8.顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。
9.线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。
10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。
11.在单链表中设置头结点的作用是________。
12.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。
13.对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。
为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。
14.设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是_________。
15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。
三、简答题
1.描述以下三个概念的区别：
头指针，头结点，表头结点。
2.线性表的两种存储结构各有哪些优缺点？
3.对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？
为什么？
4.对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？
试说明理由。
5.在单循环链表中设置尾指针比设置头指针好吗？
为什么?
6.假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。
7.什么是队列的上溢现象？
一般有几种解决方法，试简述之。
8.下述算法的功能是什么?
LinkList*Demo（LinkList*L）
{//L是无头结点的单链表
LinkList*q,*p;
if（L&&L->next）
{q=L;L=L->next;p=L;
while（p->next）
p=p->next;
p->next=q;q->next=NULL;
}
return（L）;
}
四、算法设计题
1.设计在无头结点的单链表中删除第i个结点的算法。
2.在单链表上实现线性表的求表长ListLength（L）运算。
3.设计将带表头的链表逆置算法。
4.假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：
data,next和prior。
其中data为整型数域，next和prior均为指针域。
现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。
5.已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。
试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。
6.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。
设计一个删除表中所有值小于max但大于min的元素的算法。
7.假定用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：
（1）向循环链队列插入一个元素值为x的结点；
（2）从循环链队列中删除一个结点。
8.设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。
习题4（数组和广义表）
一、单项选择题
1.设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（）。
A.p+[i*n+j-1]*kB.p+[（i-1）*n+j-1]*k
C.p+[（j-1）*n+i-1]*kD.p+[j*n+i-1]*k
2.已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（）。
A.520B.522C.524D.518
3.若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（）。
A.LOC（a00）+[j*m+i]B.LOC（a00）+[j*n+i]
C.LOC（a00）+[（j-1）*n+i-1]D.LOC（a00）+[（j-1）*m+i-1]
4.设有广义表D=（a,b,D），其长度为（B），深度为（A）。
A.无穷大B.3C.2D.5
5.广义表A=（a），则表尾为（）。
A.aB.（（））C.空表D.（a）
6.广义表A=（（x,（a,B））,（x,（a,B）,y）），则运算head（head（tail（A）））的结果为（）。
A.xB.（a,B）C.（x,（a,B））D.A
7.下列广义表用图来表示时，分支结点最多的是（）。
A.L=（（x,（a,B））,（x,（a,B）,y））B.A=（s,（a,B））
C.B=（（x,（a,B）,y））D.D=（（a,B）,（c,（a,B）,D）
8.通常对数组进行的两种基本操作是（）。
A.建立与删除B.索引和修改
C.查找和修改D.查找与索引
9.假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（）。
A.80B.100C.240D.270
10.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（）。
A.SA+141B.SA+144C.SA+222D.SA+225
11.稀疏矩阵一般的压缩存储方法有两种，即（）。
A.二维数组和三维数组B.三元组和散列
C.三元组和十字链表D.散列和十字链表
12.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）。
A.正确B.不正确
13.一个广义表的表头总是一个（）。
A.广义表B.元素C.空表D.元素或广义表
14.一个广义表的表尾总是一个（）。
A.广义表B.元素C.空表D.元素或广义表
15.数组就是矩阵，矩阵就是数组，这种说法（）。
A.正确B.错误
C.前句对，后句错D.后句对
二、填空题
1.一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。
2.对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。
3.一个广义表为（a,（a,b）,d,e,（（i,j）,k）），则该广义表的长度为_____，深度为_____。
4.一个稀疏矩阵为，则对应的三元组线性表为_____________。
5.一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______________。
6.已知广义表A=（（a,b,c）,（d,e,f）），则运算head（tail（head（A）））=____________。
7.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a
为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a
的地址为______________。
8.已知广义表Ls=（a,（b,c,d）,e），运用head和tail函数取出Ls中的原子b的运算是______________。
9.三维数组R[c1…d1,c2…d2,c3…d3]共含有______________个元素。
（其中：
c1≤d1,c2≤d2,c3≤d3）
习题5（树和二叉树）
一、单项选择题
1.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。
A.4B.5C.6D.7
2.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。
A.15B.16C.17D.47
3.一棵有n个叶子结点的哈夫曼树，它的结点总数为（）。
A.2n+2B.2n+1C.2n-1D.2n
4.在一棵二叉树上第4层的结点数最多为（）。
A.2B.4C.6D.8
5.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（）。
A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]
6.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。
A.24B.48C.72D.53
7.线索二叉树是一种（）结构。
A.逻辑B.逻辑和存储C.存储D.线性
8.线索二叉树中，结点p没有左子树的充要条件是（）。
A.p->lc=NULLB.p->ltag=1
C.p->ltag=1且p->lc=NULLD.以上都不对
9.设n,m为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（）。
A.n在m右方B.n在m左方
C.n是m的祖先D.n是m的子孙
10.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是（）。
A.空B.深度等于其结点数C.只有一个结点D.完全二叉树
11.具有3个结点的二叉树有（）种。
A.5B.4C.3D.6
12.下面叙述正确的是（）。
A.二叉树不能为空
B.二叉树等价于度为2的树
C.完全二叉树必为满二叉树
D.二叉树的左右子树有次序之分
13.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。
A.不发生改变B.发生改变
C.不能确定D.以上都不对
14.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。
A.1B.2C.3D.4
15.根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（）。
A.
升级会员 