广州大学 学年第 学期考试卷
课程 数据结构与算法 考试形式（闭卷，考试）
信息学院 系 专业 级 班 学号： 姓名：
题次 | 一 | 二 | 三 | 四 | 五 | 六 | 总分 | 评卷人 |
分数 | 20 | 10 | 10 | 30 | 20 | 10 | 100 | |
评分 | ||||||||
一、填空题：（每空2分，共20分）
1．具有10个顶点的无向图，边的总数最多为 。
2. 设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有 个结点。
3．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为 。
4．如果结点A有3个兄弟，而且B是A的双亲，则B的度是数据结构与算法分析答案
5．一个无序序列可以通过构造一棵 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
6． 法构造的哈希函数肯定不会发生冲突。
7. 求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间为 ms
8. 设一棵后序线索树的高度是50，结点x是树中的一个结点，其双亲是结点y， y的右子树高度是31，x是y的左孩子，则确定x的后继最多需经过 个 中间结点（不含后继及x本身）
9．对于单向链表，在两个结点之间插入一个新结点时需修改的指针
共有 个。
10 .有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当用折半法查值为82的结点时，经过 次比较查成功。
二、单项选择题（每题1分，共10分）
1. ( )在一个长度为n的顺序表中向第i个元素（0<i<=n+1）之前插入一个新元素时，需向后移动（ ）个元素
A.n-i
B.n-i+1
C.n-i-1
D.i
2. ( ) 设有一个栈，元素的进栈次序为A，B，C，D，E，下列( )是不可能的出栈序列
A.A，B，C，D，E
B.B，C，D，E，A
C.E，A，B，C，D
D.E，D，C，B，A
3. ( ) 具有842个结点的完全三叉树，其叶子结点共有（ ）个
A. 421 B. 422 C.420 D.423 E.以上都不是
4.（ ）顺序查方法适用于存储结构为（ ）的线性表
A. 压缩存储 B. 散列存储 C. 顺序存储 D. 链式存储
E 以上都不是
5.（ ）以下序列不是堆的是（ ）
A．（100，85，98，77，80，60，82，40，20，10，66）
B. （100，98，85，82，80，77，66，60，40，20，10）
C．（10，20，40，60，66，77，80，82，85，98，100）
D．（100，85，40，77，80，60，66，98，82，10，20）
6．（ ）如果要求一个线性表既能较快地查，又能适应动态变化的要求，则可采用的查方法是（ ）
A．分块查 B. 顺序查 C. 折半查 D. 基于属性
7. （ ）一棵有n个结点的二叉树，按层次从上到下，同一层从左到右的顺序存储在一维数组]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ ）
A. A[2i] (2i<=n) B.A[2i+1] (2i+1<=n) C. A[i/2] D.条件不充分，无法确定
8．（ ）有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（ ）
A. 45，24，53，12，37，96，30
B. 37，24，12，30，53，45，96
C. 12，24，30，37，45，53，96
D. 30，24，12，37，45，96，53
9．( )在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是( )
A. G中有弧<Vi,Vj> B.G中有一条从Vi到Vj的路径
C. G中没有弧<Vi,Vj> D. G中有一条从Vj到Vi的路径
10. ( )设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是( )
A. m-n B. m-n-1 C. n+1 D. 条件不足，无法确定
三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）
1 （ ）在栈空的情况下，不能做退栈运算，否则产生下溢。
2 ( ) 任何一棵前序线索二叉树，都可以不用栈实现前序遍历。
3 （ ）就平均查长度而言，分块查最小，折半查次之，顺序查最大
4 （ ）用Shell方法排序时，若关键字的排列杂乱无序，则效率最高。
5 （ ）在任何条件下，快速排序的效率总是最好的。
6 （ ）两叉树是树的一种特殊情况。
7 （ ）N个顶点的图至少含有N-1条边
8 （ ）拓扑排序是判断一个有向图是否存在回路的唯一方法。
9 （ ）在一棵二叉排序树T中，先删除结点N，然后再插入结点N，得到新的二叉排序树T1，则T和T1相同。
10 （ ）栈和队列都是限制存取点的线性结构。
四、画图/计算/证明 (30分)
1． 试说明一棵二叉树进行前序、中序、后序遍历，其叶结点的相对次序是否会发生改变？为什么？（5分）
2．n个结点的m叉树转化为二叉树所需存储资源比未转化前用定长结点存储节省多少？（设链域占两个单元，数据域占一个单元）（5分）
3. 已知一棵二叉树的中序遍历序列为:BAFDJGCKHLEIM，后序遍历序列为BFJGDKLHMIECA.请完成（6分）
1．构造出这颗二叉树；
2．画出这颗二叉树中序线索化后的结构
4. 对长度为8的有序表，给出折半查的判定树，给出等概率情况下的平均查长度。（5分）
5. (9分) 已知一个图G=(V,E)，其中V={a,b,c,d,e,f};
E={<a,b>,<a,d>,<a,e>,<d,e>,<e,b>,<c,b>,<c,e>,<c,f>,<f,e>}
(1) 请画出该图，并写出邻接矩阵
(2) 根据邻接矩阵，分别给出从顶点a出发的深度优先和广度优先遍历序列
(3) 画出由此得到的深度优先和广度优先生成树（或森林）
五. 程序填空题 （20分，每个函数5分）
1.用链表表示数据的简单选择排序，结点的域为数据域data，指针域next，链表首指针为head，链表无头结点。
selectsort(head)
{ p=head;
while (p )
{ q=p;
r= ;
while ( )
{ if ( q->next->data > r->data ) q=r;
r= ;
}
tmp=q->data;
q->data=p->data;
p->data=tmp;
p= ;
}
}
2.n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。注：
（1）图的顶点号从0开始计；
（2）indegree是有n个分量的一维数组，放顶点的入度；
（3）函数crein用于计算顶点的入度；
（4）有三个函数push(data)、pop( )、check( )，它们的含义为数据data进栈、退栈和测试栈是否为空（不空返回1，否则返回0）。
# include<iostream.h>
crein (array, indegree, n)
{
for (i=0; i<n; i++)
indegree[i]= ;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
indegree[i]+=array [ ] [ ];
}
topsort( array, indegree, n)
{ count= ;
for (i=0; i<n; i++)
if ( )
push(i);
while (check( ))
{ vex=pop();
cout<<vex;
count++;
for (i=0; i<n; i++)
{ k=array ;
if ( )
{ indegree[i]--;
if ( ) push(i);
}
}
}
}
3．设顺序表la的数据结构定义如下：
typedef struct
{ Datatype list[Maxnum];
int num;
} SeqList;
试将下面删除顺序表la中所有值为x的数据元素的算法补充完整。
void DeleteSeqList ( SeqList * la, Datatype x)
{ int j, k;
for (j=1; j<=la->num; j++)
{ if ( )
{for (k=j; k<la->num; k++) ;
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论