学院领导 审批并签名 | A B卷 | |
广州大学 学年第 学期考试卷
课程 数据结构与算法 考试形式（闭卷，考试）
信息学院 系 专业 级 班 学号： 姓名：
题次 | 一 | 二 | 三 | 四 | 五 | 六 | 总分 | 评卷人 |
分数 | 20 | 10 | 10 | 30 | 20 | 10 | 100 | |
评分 | ||||||||
一、填空题：（每格2分，共20分）
1．已知二叉树的中序遍历序列为B,H,D,C,E,F,A,G，后遍历序列为H,D,F,E,C,B,G,A,其前序遍历列为 。
2．若一个非连通的无向图最多有21条边，则该无向图至少有 个顶点。
3．若具有n个顶点的无向连通图采用邻接矩阵表示，则邻接矩阵中至少有________个非零元素。
4．若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个________________图。
5．将数据元素2，4，6，8，10，12，14，16，18，20依次存放于一个一维数组中（设该数组第一个元素的下标为1），然后采用折半查元素15，被比较过的数组元素的下标依次为_____________。
6．顺序查法，折半查法，树形查法和散列查法这四种方法中，只有_____________________的平均查长度与元素的个数n无关。
7．设无向连通图G的顶点数与边数和一立方体相同，即有8个顶点和12条边。任意一棵G的生成树共有________________条边
8．字符串’abcd’中共有________________个长度大于0小于4的子串。
9．将字符数组a[0..7,0..7]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素a[6,2]的地址是：__________________________
10．已知某带权连通无向图采用邻接矩阵存储方式，邻接矩阵以三元组表形式给出，部包括主对角线元素在内的下三角形部分元素对应的各三元组分别为(2,1,7),(3,1,6),(3,2,8),(4,1,9)(4,2,4),(4,3,6),(5,1,),(5,2,4),(5,3,),(5,4,2)。该连通图的最小生成树的权值之和是 。
二、单项选择题（每题1分，共10分）
1． （ ）堆排序的时间复杂度和需附加的存储空间分别是：
A O(n2) 和O(1)
B O(nlog2n) 和O(1)
C O(nlog2n)和O(n)
D O(n2)和O(n)
2．（ ）最佳二叉排序数的结构特点是：
A 除最下两层可以不满外，其余都是满的
B 除最下一层可以不满外，其余都是满的
C 每个结点的左右子树的高度之差的绝对值不大于1
D 最下层的叶子结点必须在最左边
3．（ ）设计一个判别表达式中左、右括号是否配对出现的算法，采用什么数据结构最佳？
A、线性表的顺序存储结构 B、队列
C、线性表的链式存储结构 D、栈
4．（ ）线索二叉树是一种什么结构？
A 逻辑 B 逻辑和存储 C 物理 D线性
5．（ ）下列排序中，哪个是堆？
A．（100，80，55，60，50，40，58，35，20）
B．（100，80，55，60，50，40，35，58，20）
C．（100，80，55，58，50，40，60，35，20）
D．（100，70，55，60，50，40，58，35，20）
6．（ ）若某完全二叉树的深度为h（设单结点的树的深度为1），则该完全二叉树中至少有几个结点？
A． B． C． D．
7．（ ）在二叉排序树中进行查的时间效率与什么有关？二叉树中序遍历非递归算法
A．二叉排序树的深度 B．二叉排序树的结点的个数
C．被查结点的度 D．二叉排序树的存储结构
8. （ ）若二叉树中度为2的结点有15个，度为1的结点有10个，则该二叉树有几个结点？
A．41 B．31 C．25 D．30
9．（ ）只能在顺序存储结构上才能实现的查方法是哪种？
A．顺序查 B．树型查 C．折半查 D．散列查
10．（ ）从未排序序列中任选一个元素，该元素将未排序序列分成前后两个部分，前一部分中所有元素均小于所选元素，而后一部分中所有元素均大于等于所选元素，所选元素处在排序的最终位置，分别对被分成的两部分中元素个数超过1的部分重复上述过程，直至整个排序结束。这种排序方法称为？
A．快速排序法 B．插入排序法 C．选择排序法 D．堆积排序法
三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）
1．（ ）凡是用数组存储的线形表一定是顺序表。
2．（ ）队列是一种运算受限的线性表。
3．（ ）一个非空的广义表的表尾一定是一个原子。
4．（ ）已知一棵树的先序序列和后序序列一定能构造出该树。
5．（ ）任意一棵非空的二叉树的后序序列中的第一个结点一定是一个叶子结点。
6．（ ）若从v0开始对有向图g进行深度遍历序列惟一，则可惟一确定该图。
7．（ ）图g的顶点v的入度等于其邻接矩阵中第v列中的1的个数。
8．（ ）一棵平衡二叉树中的任意两个叶子结点具有相同的层次。
9．（ ）以同一组数的不同序列来构造平衡二叉树，可能会得到不同的解。
10．（ ）直接选择排序是不稳定的排序。
四、1（8分）用相邻矩阵表示有向图，其主对角线以下的元素均为零。
（1）试问此图是否存在回路？（2分）
（2）证明你的结论．（６分）
2 对下面数据表，写出采用快速排序算法排序的每一趟结果。（7分）
（84,8,0,41,7,51,51,96,43,55）
3、（7分）判断以下序列是否为最小堆，如果不是，则把它调整为堆：
(12,70,33,65,24,56,48,92,86).
4、设G=(V,E)以邻接表存储，如图所示，试画出从结点5开始的深度优先和广度优先生成树。（8分）
五、程序填空： 每格2分
(1) 裴波那契数列的非递归算法：
long fib(int n) // 裴波那契数列的递归算法
long fib(int n) // 裴波那契数列的递归算法
{ if (n==0||n==1) return n;
else return fib(n-1)+fib(n-2);
}
long fib2(int n) // 裴波那契数列的非递归算法，实现上面函数的功能
{ if (n==0||n==1) return n;
else
{ long int oneBack=1,twoBack=0,current;
for(int i=2;i<=n;i++)
{ current=oneBack+twoBack;
twoBack= ;
;
}
return ;
}
}
（2）//对连通图从顶点v开始用visit()先广访问
void AdjMWGraph::BroadFirstSearch(const int v, int visited[],void visit(VerT item))
{ VerT u,w;
SeqQueue queue; //定义队列queue
队列的类SeqQueue的类函数：
void QInsert(const Datatype& item)
把item插入队列
Datatype QDelete(void);
弹出队首元素
int QueueEmpty(void)const
判断队列是否为空
int GetSize(void)const
返回队列长度
visit(GetValue(v)); visited[v]=1;
queue.QInsert(v);
while( )
{ u= ;
w=GetFirstNeighbor(u);
while(w!=-1)
{ if(!visited[w])
{ visit(GetValue(w));
visited[w]=1;
;
}
w=GetNextNeighbor(u,w);
}
}
}
（3）二叉树：计算树的高度（深度），设单结点的深度为0
template<class T>
int Depth(BTNode<T>* &root)
{ int depthleft, depthright, depthval;
If (root==NULL) depthval=-1;
else { depthleft=Depth(root->Left());
depthright= ;
depthval= ;
}
return depthval;
}
// 计算二叉树中叶结点的数目
template<class T>
int CountLeaf(BTNode<T>* &t)
{ if(t==NULL) return 0;
else if(t->Left()==NULL&&t->Right()==NULL) ;
else return ;
}
六、算法设计：已知递增有序的单链表a,b和c分别存储了一个集合，设计算法实现a=a∪(b∩c)，并使求解结构a仍保持递增。要求算法的时间复杂度为O（∣a∣+∣b∣+∣c∣）。其中，∣a∣为集合a的元素个数。（10分）
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论