2章：线性表
1、将图示的S所指结点加到P所指结点之后，其语句应为（ C ）。
next × next P S A．s->next=p+1；p->next=s； C．s->next=p->next；p->next=s；
next B．(*p).next=s；(*s).next=(*p).next； D．s->next=p->next；p->next=s->next；
2、在双向循环链表p所指结点之后插入s所指结点的操作是（ D ）。
A．p->next=s；s->prior=p；p->next->prior=s; s->prior=p->next; B．p->next=s；p->next->prior=s；s->prior=p; s->next=p->next; C．s->prior=p；s->next=p->next；p->next=s; p->next->prior=s; D．s->prior=p；s->next=p->next；p->next->prior=s; p->next=s;
3、线性表的存储结构是一种（ A ）的存储结构。
A． 随机存取 B． 顺序存取 C． 索引存取 D． HASH存取
4、若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,
则第12个元素的存储地址是（ B ）
5、在一个长度为n 的顺序表中，向第i个元素（1≤ i≤ n＋１）之前插入一个新元素时，
需要向后移动（ B ）个元素。 A.n-i B.n-i+1 C.n-i-1 D.i
6、删除一个双链表中结点p(非头结点和尾结点)的操作是（ B ） A. p->left->right=p->left;p->right->left=p->right B. p->left->right=p->right;p->right->left=p->ieft C. p->left=NULL;p->right=NULL
D. p->right->left=p;p->left->right=p
7、非空的循环单链表head的尾结点（由p所指向）满足（ C ）。 A.p->next=NULL; B.p=NULL; C.p->next=head; D.p=head; 8、下列描述线性表叙述错误的是（ A ）。
（Ａ）线性表的顺序存储的元素是从小到大顺序排列的 （Ｂ）线性表的链接存储，便于插入、删除操作
（Ｃ）除第一个元素和最后一个元素外，其余每个元素有且仅有一个直接前驱和直接后继 （Ｄ）线性表可以为空
9、非空的单循环链表L的尾结点P↑，满足（ C ） （A）P↑.next=NIL; (B) P=NIL;
(C)P↑.next=L; (D) P=L;
10、L是带头结点的单向链表的表头指针，则该表为空的条件是__C_ A. n=0 B. L=NIL
C. L->next=NIL D. L->next=L
11、某带头结点的单链表的头指针为head，判定该链表为非空的条件是( D ) A.head==NULL B.head->next==NULL C.head!=NULL D.head->next!=NULL
12、在一个单链表中，若要删除P结点的后继结点，则执行：_A____ A p->next=p->next->next;
B p=p->next; p->next=p->next->next; C dispose(p->next); D p=p->next->next;
13、 链表不具有的特点是___1_______。
（1）可随机访问任一元素 （2）插入删除不需要移动元素
（3）不必事先估计存储空间 （4）所需空间与线性表长度成正比
14、在有几个结点的单链表P中，查找指定结点X的后继结点Q的算法Next（P，X，Q）的时间复杂度为______________
A. O(n) B. O(1) C.O(c*n) D. O(c) (c表示一常数)
15、在单项链表中删除一个指定结点的后继的时间复杂度为 [ ] A.O(n) B.O(nlog2n) C.O(1) D.O(√n)
16、 若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用——存储方式最节省运算时间。 （1）单链表 （2）双链表
（3）单循环链表 （4）带头结点的双循环链表
3章：栈和队列
1．设数组A[0……m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作时修改指针的语句是（ ）。
A．sq.front=(sq.front+1)%m C．sq.rear=(sq.rear+1)%m
B．sq.front=(sq.front+1)%(m+1) D．sq.rear=(sq.rear+1)%(m+1)
2．设有一足够大的栈，入栈元素的顺序为W,X,Y,Z，判断下列哪一个出栈序列是不可能的序列:_______。
A．X,Y,Z,W B．Z,W,Y,X C．Z,Y,X,W D．Y,Z,X,W 3．队列的特点是（ C ）。
A．随机进出
B．先进后出
C．先进先出
D．按大小顺序进出
4．. 栈和队列的共同点是（ C ）。
A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点
5．判定一个循环队列QU(最多元素为m0)为满队列的条件是( C ) A．QU->front==QU->rear B．QU->front!=QU->rear
C．QU->front==(QU->rear+1)％m0 D．QU->front!=(QU->rear+1)％m0 6．栈上可进行的操作是（Ｃ）
A.访问栈的第i个元素 B. 在栈的第i个元素之后插入元素x C.在栈顶插入一个元素 D.删除栈底元素
7．设元长度为L，对队列q作出队DEL（q）运算后（ Ａ）
A.队头指针增量L B. 队尾指针增量L
C.队尾元素出队 D.队首、尾指针均不动
8．设有栈S和队列Q，其初始状态为空，元素a1、a2、a3、a4、a5、a6依次入栈，出栈的元素则进入队列Q，若6个元素出列的顺序是a2、a4、a3、a6、a5、a1，则栈的容量至少是（ C ）
（A） 6 （B） 4 （C） 3 （D） 2
9．设计一个判别表达式中左、右括号是否配对出现的算法，采用（ B）数据结构最佳。 （Ａ）线性表的顺序存储结构 （Ｂ）栈
（Ｃ）队列 （Ｄ）线性表的链式存储结构
10.在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为 [ ] A.O(1) B.O(√n) C.O(nlog2n) D.O(n)
11．计算递归函数如不用递归过程通常借助的数据结构是（D） A、线性表 B、双向队列 C、树 D、栈 12.导致栈上溢的操作是( ) A.栈满时执行的出栈 C.栈空时执行的出栈 为空队列的条件是( ) A.(rear-front)%m= =1
B.front= =rear
C.(rear-front)%m= =m-1 D.front= =(rear+1)%m
14．若进栈序列为１，２，３，４，假定进栈出栈可以穿插进行，则可能的出栈序列是＿D＿＿
Ａ ２，４，１，３ Ｂ ３，１，４，２ Ｃ ３，４，１，２ Ｄ １，２，３，４
B.栈满时执行的入栈 D.栈空时执行的入栈
13.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q
综合题
1.第3章习题3.2
2.把1、2、3、4依次进栈（栈初始为空），任何时刻（只要栈不空），都可以出（退）栈，试写出所有可能的出栈序列（如1234）。
3、设一数列为1,2,3,4,5,6,通过栈操作,要得到顺序为3,2,5,6,4,1和1,5,4,6,2,3的输
出序列是否可能,请阐述理由。
4.试说明抽象数据类型定义应包含哪些内容?以栈为例说明。
5章：树
1．一个深度为4的二叉树至多有（ ）个结点。
A．15
B．12
C．17
D．20
2．下列说法正确的是（ ）
A．二叉树中任何一个结点的度都为2 C．一棵二叉树的度可小于2 度为2
3．某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1、2、…n。且具有如下性质：T中任意结点v，其编号等于左子树上的最小编号减一，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加一，这是按（B ）编号的。
A．中序遍历
B．前序遍历
C．后序遍历
D．层次顺序
B．二叉树的度为2
D．任何一棵二叉树中至少有一个结点的
4．一棵有124个叶结点的完全二叉树，最多有（C ）个结点。
A．247
B．124
C．248
D．125
5若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ B ） A. 9 B. 11
C. 12 D. 不确定
6. 已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历（ D ）。
A．acbed B．decab C．deabc D．cedba 7.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（ C ） A. 根结点无右子树的二叉 B. 根结点无左子树的二叉树
C. 根结点可能有左二叉树和右二叉树 D. 各结点只有一个儿子的二叉树
8．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至
少为（ B ）。
A．2h B．2h-1 C．2h+l D．h+l
9 .设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是（ C ） A.x是y的左兄弟 B.x是y的右兄弟 C.x是y的祖先 D.x是y的后代
10．对如图示的二叉树进行中序遍历，所得结点序列为（ ） A BEFDAGIHC B BEDFAGIHC C EFDBAGIHC D EFDBAIHGC
11． 在树的度为3的三叉树中，结点的度不可能为（Ａ） A. 大于3 B. 0 C.2 D. 3
12．由权值分别为3，9，6，2，5的叶子结点生成一棵哈夫曼树，其带权路径长度为：（ ） （A）24 （B）55 （C）72 （D）53
13、在一个二叉树中，叶结点个数为50，仅有一个孩子的节点个数为30，那么总结点数为多少个？( C ) （A） 100 （B）128 （C） 129 （D） 130
14．一棵有124个叶结点的完全二叉树，最多有（ ）个结点。
A） 247 B）124 C）248 D）125
15．在一棵二叉树的先序遍历、中序遍历，后序遍历所产生的序列中，所有叶结点的先后
顺序（ B ）
（A）都不相同 （B）完全相同
（C）先序和中序相同，而与后序不同 （D）中序和后序相同，而与先序不同 16．在下列关于二叉树的叙述，选出正确的一项（ D ）
（A）在二叉树中，任何一个结点的度都是2 （B）二叉树的度为2
（C）在二叉树中至少有一个结点的度是2 （D）一棵二叉树的度可以小于2
17．如果一棵二叉树中任一结点的值都大于其左子树中所有结点的值，且小于其右子树中所有结点的值，现欲得到各结点值的递增序列，试问应采用的遍历的方法是什么（ B ） （A）先序遍历 （B）中序遍历 （C）后序遍历 （D）层次遍历
18．设森林F中有3棵树，其第一、第二和第三棵树的结点个数分别是n1、n2和n3，则与森林F对应的二叉树根结点的右子树上的结点个数是（D）
（A） n1 （B） n1+n2 （C）n3 （D）n2+n3
19．高度为
h(h>0)的二叉树最少有（ ）个结点
A.h B.h-1 C.h+1 D.2h
20．深度为5的二叉树其结点数最多为（C） A、16 B、30 C、31 D、32
21．如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的（B） A、先序排列 B、中序排列 C、后序排列 D、层序排列 22．n个结点的线索二叉树中线索的数目为（C）
A、(n-1)个 B、n个 C、（n+1）个 D、(n+2)个
23..假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在( ) A.BT[i/2] C.BT[2*i]
24.右图所示二叉树的中序序列是( ) A.DHEBAFIJCG B.DHEBAFJICG
C.DBHEAFCJIG D.DBHEAFJICG
25．在一棵二叉树的先序遍历、中序遍历，后
序遍历所产生的序列中，所有叶结点的先后顺序（ B ）
（A）都不相同 （B）完全相同
（C）先序和中序相同，而与后序不同 （D）中序和后序相同，而与先序不同 26在下列关于二叉树的叙述，选出正确的一项（ D ）
B.BT[2*i-1] D.BT[2*i+1]