一、填空题（每空2分，共20分）
1.当线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
2.设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为_______；如按列优先顺序存储,则元素A[-18,-25]的存储地址为_______。
3.具有N个结点的二叉树，采用二叉链表存储，共有_______个空链域。
4.Prim（普里姆）算法的时间复杂度是_______，适用于求_______图的最小生成树；kruskal（克鲁斯卡尔）算法的时间复杂度是_______，适用于求_______图的最小生成树。
5.一个n个顶点的强连通图，其边的个数至少为_______，至多为_______。
二、选择题（每小题2分，共20分）
1．以下那一个术语与数据的存储结构无关？（ ）
A．栈 B. 哈希表 C. 线索树 D. 双向链表
2．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
3. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的
4. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。
A．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改
5. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。
A. (rear+1) MOD n==front B. rear==front
C．rear+1==front D. (rear-l) MOD n==front
6. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。 A. head(tail(LS)) B. tail(head(LS))
C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS))))
7．在一棵度为3的树中,度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个 A．4 B．5 C．6 D．7
8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。
A．M1 B．M1+M2 C．M3 D．M2+M3
9．下述编码中哪一个不是前缀码（ ）。
A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）
10 关键路径是事件结点网络中（ ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
三、判断题（每小题1分，共10分，正确打√，错误打×）
1. 数据元素是数据的最小单位。
2. 循环队列通常用指针来实现队列的头尾相接。
3. 一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。
4. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。
5. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；
6. 循环队列也存在空间溢出问题。
7. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。8. 二叉树是度为2的有序树。
9. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。
10. 对AOV网进行拓扑排序时，如果还有顶点没有被输出，且这些顶点的入度均＞0，则该网必定有环存在。
四、综合题（共35分）
1．设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C
（1）画出这棵二叉树。（5分）
（2）画出这棵二叉树的后序线索树。（5分）
（3）将这棵二叉树转换成对应的树（或森林）。（5分）
2．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问：（1）T树的最大深度Kmax=?最小可能深度Kmin=?（4分）
（2）T树中共有多少非叶结点？（2分）
（3）若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。（4分）
3．下面的邻接表表示一个给定的无向图：
（1）给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列；（5分）
（2）给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。（5分）
五、算法设计题（共15分）
1、二叉树采用二叉链表存储，编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。（7分）
2、写出将无向图的邻接矩阵转换成邻接表的算法。（8分）
浙公网安备 33021202002483