第3章 栈和队列
一、单项选择题：
1．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。 A. edcba B. decba C．dceab D．abcde。 2.栈结构通常采用的两种存储结构是（ ）。
A. 顺序存储结构和链表存储结构 B．散列方式和索引方式
C．链表存储结构和数组 D．线性存储结构和非线性存储结构 3．栈的特点是（ B ），队列的特点是（ A ）。 A. 先进先出 B．先进后出
4．一个队列的入列序列是1，2，3，4，则队列的输出序列是( )。
A. 4，3，2，l B. 1，2，3，4 C．l，4，3，2 D．3，2，4，l 5．判定一个循环队列 QU（最大空间是 mo）为空的条件是( )。 A. QU.front= =QU.rear B. QU.front！=QU.rear
C． QU.front==（QU.rear＋l）%mo D．QU.front！=（QU.rear＋1）％mo 6．判定一个循环队列QU（最大空间是mo）为满队列的条件是( )。 A．QU.front＝＝QU.rear B．QU.front！=QU.rear
C. QU.front==（QU.rear＋l）%mo D．QU.front！=（QU.rear＋l）%mo 7．循环队列用数组 A［0，m－l］存放其元素值，已知其头尾指针分别是 front和 rear，
则当前队列中的元素个数是( )。
A.（rear-front＋m）% m B. rear-front + 1 C．rear－front－1 D． rear－front 8．栈和队列的共同点是( )。
A．都是先进后出 B．都是先进先出 C．只允许在端点处插入和删除元素 D．没有共同点
9．向一个栈顶指针为 top的链栈中插入一个S所指结点时，则执行( )。 A .top－＞next=s； B．s-＞next＝top-＞next； top－＞next＝s； C． s-＞next＝top；top＝s； D． s-＞next＝top；top＝top－＞next; 10．从一个栈顶指针为top的链栈中删除一结点时，用X保存被删结点的值，则执行( ). A. x=top；top=top－＞next； B． x＝top－＞data；
C． top＝top-＞next；x＝top-＞data； D． x＝top-＞data；top＝top-＞next
11．在链队列中，设front和rear分别为队首和队尾指针，插入s所指结点的运算为（ ）。
A . front－＞next=s； front=s； B． rear-＞next＝s；rear＝s； C． s-＞next＝rear；rear＝s； D． s－＞next=front；front=s； 12．在链队中，设front和rear分别为队首和队尾指针，则删除一个结点的运算为（ ）。 A． rear＝front-＞next； B． rear＝rear-＞next； C． front＝front－＞next； D． front＝rear-＞next 13．插入和删除只能在一端进行的线性表，称为（）。 A．队列 B．循环队列 C．栈 D．循环栈 14.在栈中，出栈操作的时间复杂度为（）。
A. O（1） B．O（log2n） C．O（n） D．O（n）
15．设长度为n的单循环链队列，若只设头指针，则入队操作的时间复杂度为（）。 A. O(1) B．O（log2n） C．O（n） D．O（n）
21.设长度为n的单循环链队列，若只设尾指针，则出队操作的时间复杂度为（）。 A. O（1） B．O（log2n） C．O（n） D．O（n）
二、填空题：
1． 线性表、栈和队列都是( 线性)结构，可以在线性表的（任何）位置插入和删除元素；对于栈只能在（ 栈顶 ）插入和删除元素；对于队列只能在（ 队尾）插入元素和（ 对头 ）删除元素。
2．向顺序栈中压入元素的操作是（判断栈是否已满，如果未满，将元素存入栈顶指针指向的存储位置，栈顶指针增一 ；否则先增加栈的空间，然后压栈。 ）。向链栈中压入元素的操作是（压入元素的指针指向链栈的头指针，再修改链栈的头指针指向刚压入的元素 ）。
3．对顺序栈进行出栈时的操作是（如果栈空，出栈失败；否则，栈顶指针减一，并将栈顶指针指向的元素取出）。对链栈进行出栈时的操作是（如果栈空，出栈失败；否则，取出栈顶指针指向的元素，并将栈顶指针指向下一个元素）。
4．在一个循环队列中，队首指针指向队首元素的（ 存储位置 ）。
5．从循环队列中删除一个元素时，其操作是（ 如果队列空，删除失败；否则，取出队首指针指向的元素，然后修改队首指针指向下一个元素的存储位置）。 6．在具有n个单元的循环队列中，队满时共有（ n-1 ）个元素。 7．一个栈的输入序列是12345，则栈的输出序列43512是（ 错误的 ）。
22
2
8．一个栈的输入序列是12345，则栈的输出序列12345是（正确的）。
9．在有n个元素的栈中，进栈和出栈操作的时间复杂度为（ O（1） ）和（O（1） ）。 10．设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（O（n） ）和（ O（1） ）；若只设尾指针，则人队和出队操作的时间复杂度分别为（ O（1））和（ O（1） ）。
11．在循环队列中，设队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素。
(1) 在循环队列中，队空标志为( Q.rear==Q.front )；队满标志为( (Q.rear+1)%maxsize==Q.front )。
(2)当rear＞=front时，队列长度为( Q.rear-Q.front 或 (Q.rear-Q.front+ m ) % m ) ；当 rear＜ front时，队列长度是( (Q.rear-Q.front+ m ) % m )( 设循环队列长度为m)。
12．在顺序队列中，为了避免（假溢出）现象引入了循环队列的概念。其入队和出队操作为( Q.base[Q.rear]=e;Q.rear=(Q.rear+1）%maxsize ） 和 （ e=Q.base[Q.front];Q.front=(Q.front+1）%maxsize ）。
第4章 串
一、选择题
1. 空串与空格串是相同的，这种说法
A. 正确 B.不正确
2. 串是一种特殊的线性表，其特殊性体现在
A. 可以顺序存储 B.数据元素是一个字符 C. 可以链接存储 D.数据元素可以是多
个字符
3. 设有两个串p和q， 求q在p中首次出现的位置的运算称作
A 连接 B 模式匹配 C求子串 D 求串长
4. 设串s1=‘ABCDEFG’,s2='PQRST',函数con(x,y)返回x和y串的连接串，subs（s,i,j）返回串s的从序号i的字符开始的j个字符组成的字串， len(s)返回串s的长度，则con(subs(s1,2,len(s2)), subs(s1,len(s2),2))的结果串是
A）BCDEF B）BCDEFG C）BCPQRST D）BCDEFEF
二、填空题
1. 串的两种最基本的存储方式是 顺序存储 和 链式存储
2. 两个串相等的充分必要条件是 串的长度相等且各个位置的字符相同 3. 空串是 零个字符的串 ，其长度等于 0 。
4. 空格串是 一个或多个空格组成的串 ， 其长度等于 空格字符的个数 。 5. 设s='I_AM_A_TEACHER', 其长度是 14 三、操作题：
1. 已知两个串为 s1=\cad cabcadf\，s2=\，试求两个串的长度，并判断s2串是否是s1串的子串；如果s2是s1的子串，请指出s2在s1中的起始位置。9
4. 针对串的两种存储表示各设计一算法，判断该字符串是否是回文（即正读与反读相同，如\是一个回文，而\则不是）（仅写出算法思想）。
第5章 数组与广义表
1. 设二维数组A5×6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少字节？120 A的终端结点a45的起始地址为何？1116 按行和按列优先存储时，a25的起始地址分别为何？ 行优先：1068 列优先：1108 2．稀疏矩阵的存储方法及其分类。 三元组及其行列数
分类：三元组顺序表，行逻辑链接的顺序表，十字链表 3．广义表的概念和存储结构：如何区分表结点和原子结点 4．求下列广义表运算的结果： 1) GetHead((p,h,w)) ：p 2) GetTail((b,k,p,h)) ：（k, p, h） 3) GetHead(((a,b),(c,d))) ：（a, b） 4) GetTail(((a,b),(c,d))) ：((c,d)) 5) GetHead(GetTail(((a,b),(c,d))) ：（c,d） 6) GetTail(GetHead(((a,b),(c,d))) ： （b）
第6章 树和二叉树
一、单项选择题：
1．对于任何一棵二叉树T，如果其终端结点数为no，度为2的结点数为n2，则（）。 A．no=n2+1 B． n2=n0+1 C．n0=2n2+1 D．n2=2n0+1
2．设X是一棵树，x’是对应于X的二叉树，则X的先序遍历和X’的（）遍历相同。 A．先序 B．中序 C．后序 D．不确定
3．深度为K的二叉树至多有（）个结点。 A. 2 B. 2 –1 C. 2
k
k
k-1
D. 2
k-1
-1
4．对于二叉树来说，第i层上至多有（）个结点。 A. 2 B. 2 –1 C. 2
i
i
i-1
D. 2
i-1
-1
5．结点先序为XYZ的不同二叉树，那么它有（）不同形态。 A．3 B．4 C．5 D．6
6．某二叉树的前序遍历序列为IJKLMNO，中序遍历序列为JLKNMOI，则后序遍历序列为（）。
A．JLKMNOI B．LKNOMI C．LKJNOMI D．LNOMKJI
7.某二叉树的后序遍历序列为dabec，中序遍历序列为debac，则前序序列遍历为（ ）。 A．ached B．decab C. deabc D．cedba 8．具有35个结点的完全二叉树的深度为（）。 A．5 B. 6 C．7 D．8
9．将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）。 A．98 B．99 C．50 D．48
10．某二叉树的前序和后序序列正好相反，则该二又树一定是（）的二叉树。
A．空或只有一个结点 B、高度等于其结点数 C．任一结点无左孩子 D．任一结点无右孩子
11．设X是一棵树，x’是对应于X的二叉树，则X的后序遍历和X’的（）遍历相同。 A．先序 B．中序 C．后序 D．层次序 12．树最适合用来表示（）。
A．有序数据元素 B.无序数据元素
C.元素之间无联系的数据 D.元素之间有分支层次关系 13．对于一棵满二叉树，m个树叶，n个结点，深度为h，则（）。 A． n＝h＋m B． h＋m=2n C．m＝h-1 D．n＝2-l 14.判断线索二叉树中某结点p有左孩子的条件是（）。
A． p！＝null B．p-＞lchild!=null C．p->ltag==0 D．p-＞ltag==1 15．二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法
（ ）。 A.正确 B．错误
h