cin>>temp;
node*t=newnode;
t->data=temp;
t->next=tail->next;
tail->next=t;
tail=t;
i++;
}
第3章栈和队列
1、填空题
1.栈和队列在本质上都是___线性表__________。
2.栈的操作特点是__后进先出_。
队列的操作特点是_先进先出__。
2、选择题
1.消除递归不一定需要使用栈，此说法___A____。
A.正确 B.错误
2.对于栈，输入序列为（1，2，3，4），不可能得到的输出序列有__D_____。
（A）（1，2，3，4） （B）（4，3，2，1）
（C）（1，3，4，2） （D）（3，1，2，4）
3.用单循环链表表示队列，正确的说法是B。
（A）可设一个头指针使入队、出队都方便；
（B）可设一个尾指针使入队、出队都方便；
（C）必须设头尾指针才能使入队、出队都方便；
（D）无论如何,只可能使入队方便。
3、判断题
1.栈的特点是先进先出。
（×）
2.可以在队列的任意位置插入元素。
（×）
3.递归程序化非递归程序必须用到栈。
（×）
4.如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。
（√）
5.在用顺序表表示的循环队列中，可用标志位来区分队空或队满的条件。
（√）
第4章串
1、选择题
1.设有两个串p和q，求q在p中首次出现的位置的运算称作（B）
A．连接B．模式匹配C．求子串D．求串长
2、判断题
1.空串和空格串是同一个概念，二者没有区别。
（×）
第5章数组和广义表
1、填空题
1.二维数组在内存中存储可以有两种存储方式，一种是___行__优先存储，一种是列优先存储。
2.设广义表L＝（（），（），（（）））。
则head（L）是 （） ；
tail（L）是 （（），（（）））；L的长度是 3 ；L的深度是3。
3.设广义表L＝（（a），（b），（（c））） 则head（L）是__（a）__；
tail（L）是_（（b），（（c）））___。
2、选择题
1.在C语言中，如果有数组定义intA[8][9]；假定每个整型数据占2字节，则数组元素A[4][4]的地址是（A）。
A.A+80B.A+76C.A+82D.以上都不对
2.广义表A=（a,b,（c,d）,（e,（f,g）））,则下面式子的值为（ D ）；
Head（Tail（Head（Tail（Tail（A）））））
A．（g） B.（d） C.c D.d
3、判断题
1.在C语言中，多维数组的存储采取的是行优先的方式。
（√）
2.广义表在本质上也是线性表。
（×）
3.可以用三元组存储法来压缩存储稀疏矩阵。
（√）
4.已知广义表A=（（a,b,c）,（d,e,f））,从A中取出原子e的运算是head（tail（head（tail（A））））。
（√）
第6章树和二叉树
1、填空题
1.一棵62个叶结点的完全二叉树,最多有___62*2=124______个结点。
2.若规定仅有根的二叉树的高度为1，那么高为h的完全二叉树最多有____2^h-1___________个结点，最少有___2^（h-1）______个结点。
3.设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为____2^（k+1）-1____________，最小结点数为____k+1____________。
4.设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为_______2^k-1_________，最小结点数为____k______。
2、选择题
1.具有N个结点的完全二叉树的深度是__B______。
（A）⌊log2N⌋（B）⌊log2N⌋+1
（C）⌊log2（N）⌋（D）⌊log2N⌋-1
2.设二叉树的树根为第一层，则第i层上至多有__C_____结点。
（A）1 （B）2 （C）2i-1 （D）2i-1
3、判断题
1.二叉树的左右子树次序是严格的，不能够任意改变。
（√）
2.若根为第一层，则深度为k的满二叉树的结点为2^k-1。
（√）
3.二叉树的三叉链表存储结构可以方便的访问到双亲结点。
（√）
4、应用题
1.在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。
请回答下列问题：
（1）什么是哈夫曼树？
（3分）
（2）根据题目所给频率值，画出相应的哈夫曼树。
（11分）
（3）给出各个字符对应的哈夫曼编码。
（6分）
（4）该段文字经过哈夫曼编码后，长度是多少。
（4分）
参考答案如下：
（1）答案为：
带权路径长度最小的二叉树称为哈夫曼树。
（3分）
（2）根据题目所给频率值，画出相应的哈夫曼树。
（11分，每个结点1分）
（3）给出各个字符对应的哈夫曼编码。
（6分）
a:
1110b:
1111c:
110d:
00e:
01f:
10
（4）该段文字经过哈夫曼编码后，长度是多少。
（4分）
（7+9）*4+12*3+（22+23+27）*2=244
或者100+45+55+28+16=244
2.设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。
（15分）
参考答案如下：
（1）画出二叉树（10分）
错一个结点扣2分。
（2）后序遍历序列为：
bdeca（5分）
3.通信报文中出现的字符A、B、C、D、E，在报文中出现的频率分别为0.23、0.2、0.32、0.12、0.13，分别给出相应字符的哈夫曼编码（要求画出哈夫曼树，并且把权值小的结点放在左边）。
（共14分）
参考答案如下：
为处理方便，关键字都乘以100，为{23，20，32，12，13}
构造哈夫曼树为：
（9分,每个结点1分）
所以编码为：
A：
01B：
00C：
11D：
100E：
101（5分，每个编码1分）
4.某二叉树结点的中序序列为H，B，C，D，E，F，G，后序序列为B，D，C，H，F，G，E，请据此画出该二叉树，再给该树加上中序线索。
（共15分）
对应的二叉树为：
（7分,每个结点1分）对应中序线索树为：
（8分，每条线索1分）
55.请证明对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
（10分）
证明：
令树中结点总数为N，度为1的结点个数为n1。
则树中结点数满足下列公式：
n0+n1+n2=N
从度的角度来考虑，满足下列公式：
2n2+n1+1=N
从而得证：
n0=n2+1
5.请按照孩子-兄弟表示法，将图1所示树转化为二叉树。
（共14分）
解：
（每个结点2分）
6.
设二叉树如图2所示。
分别写出它的先序遍历、中序遍历、后序遍历序列。
（共15分）
8.
（1）写出如图所示二叉树的中序遍历结果。
（8分）
（2）画出二叉树的中序后继线索。
（10分）
（1）中序遍历结果：
ADBCHFEG——共8分，每个字符1分
（2）二叉树的中序后继线索如图
——共10分，每个后继线索2分
9.
已知某二叉树的前序遍历序列为：
ABCDEFG
和中序遍历序列为：
CBEDAFG。
请画出该二叉树。
答案如下：
10.
已知通信联络中只可能出现A、B、C、D、E、F、G、H共8种字符，其出现次数分别为5，28，7，9，14，23，3，11次。
（1）请画出赫夫曼树（权值小的结点在左边）。
（15分）
（2）计算该树的带权路径长度。
（3分）
答案：
此答案错误！
！
！
（1）赫夫曼树构造如下。
树中结点位置正确者，每个1分，共15分。
（2）该树的带权路径长度为
（5+3+7+8）*4+（11+14）*3+（23+29）*2=271
————3分
5、读程序写结果
已知二叉树的结点结构如下：
structNode
{
intdata;
Node*lchild,*rchild;
};
某棵二叉树的形态如右图：
根据要求解答下题：
1、（共5分）
intfun1（Node*root）
{
if（root==0）return0;
intl,r;
l=fun1（root->lchild）;
r=fun1（root->rchild）;
if（l>=r）returnl+1;
elsereturnr+1;
}
（1）当root是指向结点A的指针时，函数fun1的返回值是多少？
（2分）
函数fun1的返回值是3。
（2）函数fun1的功能是什么？
（3分）
函数fun1的功能是求二叉树的高度。
2、（共6分）
intfun2（Node*root）
{
if（root==0）return0;
intl=fun2（root->lchild）;
intr=fun2（root->rchild）;
returnl+r+1;
}
（1）当root是指向结点A的指针时，函数fun1的返回值是多少？
（2分）
函数fun1的返回值是5。
（2）函数fun1的功能是什么？
（4分）
函数fun1的功能是求二叉树中所有结点的个数
第7章图
1、填空题
1.有n个顶点的有向连通图最多有n（n-1）条边，最少有n-1条边。
2.具有n个顶点的完全无向图有__2/n（n-1）______条边，完全有向图有______n（n-1）__条边。
2、选择题
1._____b_____方法可以判断出一个有向图中是否有环（回路）。
（A）深度优先遍历（B）拓扑排序
（C）求最短路径 （D）求关键路径
2.关键路径是指__b________。
（A）从开始事件到终止事件路径长度最短的路径
（B）从开始事件到终止事件路径长度最长的路径
（C）从开始事件到终止事件活动最少的路径
（D）从开始事件到终止事件活动最多的路径
7.方法b可以判断出一个有向图中是否有环（回路）。
（A）深度优先遍历（B）拓扑排序
（C）求最短路径 （D）求关键路径
3、判断题
1.具有n个顶点的有向图最多有n*（n-1）条边。
（t）
2.在AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为先决条件。
（t）
4、应用题
1、已知某图的存储结构如下，试写出该图从顶点A开始的深度优先遍历序列。
（11分）
A
B
C
D
E
F
G
H
I
J
K
A
0
1
1
1
1
1
0
0
0
0
0
B
0
0
0
0
0
0
1
0
0
0
0
C
0
0
0
0
0
0
0
1
0
0
0
D
0
0
0
0
0
0
0
0
1
0
0
E
0
0
0
0
0
0
0
0
0
1
0
F
0
0
0
0
0
0
0
0
0
0
1
G
0
1
0
0
0
0
0
0
0
0
0
H
0
0
1
0
0
0
0
0
0
0
0
I
0
0
0
1
0
0
0
0
0
0
0
J
0
0
0
0
1
0
0
0
0
0
0
K
0
0
0
0
0
1
0
0
0
0
0
答案为：
ABGCHDIEJFK（对一个1分）
2.请给出图1的所有最小生成树。
（10分）
共两棵。
第一棵为：
（5分）错一条边扣1分。
第二棵为：
（5分）错一条边扣1分。
3.请给出图2的所有拓扑排序序列。
（16）
答案如下：
仅有两个
第一个：
abcdefgh（错一个字符扣1分）
第二个：
abcdegfh（错一个字符扣1分）
4、对于有向无环图（如图2），写出它的所有不同的拓扑有序序列。
（共16分）
序列为：
1、3、2、4、5、6、7、8
6.已知某图采取如图2所示的邻接矩阵表示法，请回答下列问题。
（共12分）
0
高中英语不规则动词表
steal偷stolestolen
1
forgive原谅forgaveforgiven2
arise出现arosearisen3
speak说spokespoken4
5
go去wentgone6
1
A
buy买boughtbought
wake醒着woke/wakedwoke/waked/woken1
0
swim游泳swamswum1
wake醒着woke/wakedwoke/waked/woken1
0
0
0
2
B
2
1
0
0
1
1
0
3
C
3
1
0
0
0
1
1
4
D
4
0
1
0
0
0
0
5
E
5
0
1
1
0
0
0
6
F
6
0
0
1
0
0
0
图2
（1）请画出该图。
（6分）
（2）对其从顶点A开始进行深度优先遍历，写出遍历序列。
（6分）
（1）请画出该图。
（6分）错一个结点扣1分。
（2）对其从顶点A开始进行深度优先遍历，写出遍历序列。
（6分,错一个字符扣1分）
序列为：
ABDECF
7、（本题总计7分）
构造该图的最小生成树。
图的最小生成树如下——每条边1分，共7分
第9章查找
1、选择题
1.若在线性表中采用二分查找法查找元素，该线性表应该（ a ）。
A．元素按值有序 B．采用顺序存储结构
C．元素按值有序，且采用顺序存储结构
D．元素按值有序，且采用链式存储结构
2.对二叉排序树进行_____b____遍历，可以得到该二叉树所有结点构成的有序序列。
（A）前序 （B）中序 （C）后序 （D）按层次
3.利用逐点插入法建立序列（51，71，43，81，74，20，34，45，64，30）对应的二叉排序树以后，查找元素34要进行（ a ）元素间的比较。
A．4次 B．5次 C.7次 D．10
4.对二叉排序树进行_______b_____遍历，可以得到该二叉树所有结点构成的有序序列。
（A）前序 （B）中序 （C）后序 （D）按层次
5.散列函数有一个共同性质，即函数值应按（ c）取其值域的每一个值。
A.最大概率 B.最小概率 C.同等概率 D.平均概率
6.一个哈希函数被认为是“好的”，如果它满足条件____d_____。
（A）哈希地址分布均匀
（B）保证不产生冲突
（C）所有哈希地址在表长范围内
（D）满足（B）和（C）
7.哈希表的平均查找长度是_______d___的函数。
（A）哈希表的长度（B）表中元素的多少
（C）哈希函数（D）哈希表的装满程度
8.平均查找长度最短的查找方法是__________c__。
（A）折半查找（B）顺序查找（C）哈希查找（4）其他
2、判断题
1.在有序表的查询过程中，设立“哨兵”的作用是为了提高效率。
（t）
2.对于折半查找，其前提条件是待查找序列只要是有序的即可。
（f）
3、应用题
1.
输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。
（1）按输入次序构造一棵二叉排序树（只要求画出最终二叉排序树）。
（2）依此二叉排序树，如何得到一个从小到大的有序序列？
2、若一棵排序二叉树的关键字输入序列为{80，6，10，7，8，25，100，90}，请画出该二叉树。
解：
二叉排序树为：
（16分，每个结点2分）
3.
已知一组关键字为{1,14,27,29,55,68,10,11,23}，则按哈希函数H（key）=keyMOD13和链地址法处理冲突来构造哈希表。
（1）画出所构造的哈希表。
（2）在记录的查找概率相等的前提下，计算该表查找成功时的平均查找长度。
（1）画出所构造的哈希表。
——9个结点，每个1分
0
∧
1
1
14
27
∧
2
∧
3
29
55
68
∧
4
∧
5
∧
6
∧
7
∧
8
∧
9
∧
升级会员 