数据结构与算法分析模拟试题及答案5

模拟试题（五）

一、单项选择题（每小题 2 分，共20分）
（1）队列的特点是（　　　）。
A）先进后出 B）先进先出
C）任意位置进出 D）前面都不正确
（2）有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（　　　）遍分配与收集。
A）n B）d C）r D）n - d
（3）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（　　　）。
A）都不相同 B）完全相同
C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同
（4）限定在一端加入和删除元素的线性表称为（　　　）。
A）双向链表 B）单向链表 C）栈 D）队列
（5）若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（　　　）。
A）起泡排序 B）插入排序 C）选择排序 D）二路归并排序
（6）设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（　　　）。
A）m-n-1 B）n+1 C）m-n+1 D）m-n
（7）对于具有n个顶点的强连有向图，其弧条数的最小值为（　　　）。
A）n+1 B）n C）n-1 D）n-2
（8）下面关于广义表的叙述中，不正确的是（　　　）。
A）广义表可以是一个多层次的结构 B）广义表至少有一个元素
C）广义表可以被其他广义表所共享 D）广义表可以是一个递归表
（9）设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是（　　　）。
A）f>=c B）c>f C）f=2k+1-1 D）c>2k-1
（10）设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（　　　）。
A）2n+2 B）2n+1 C）2n D）2n-1
二、（每小题4分，共8分）
写出下列中缀表达式的后缀形式：
（1）3X/(Y-2)+1
（2）2+X*(Y+3)
三、（每小题4分，共8分）
试对如下图中的二叉树画出其：

（1）顺序存储表示；
（2）二叉链表存储表示的示意图。
四、（每小题4分，共8分）
判断以下序列是否是小根堆? 如果不是，将它调整为小根堆。
（1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 }
（2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 }
五、（本题8分）
已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。
六、（每小题2分，共8分）
设有12个数据25,40,33,47,12,66,72,87,94,22,5,58，它们存储在散列表中，利用线性探测再散列处理冲突，取散列函数为H(key)=key % 13。
（1）顺次将各个数据散列到表中，并同时列出各元素的比较次数。
（2）计算查找成功的平均查找次数。
七、（第1小题2分，第2、3小题每小题3分，本题8分）
对于如下图所示的图G，邻接点按从小到大的次序。

（1）图G有几个连通分量？
（2）按深度优先搜索所得的树是什么？
（3）按深度优先搜索所得的顶点序列是什么？
八、（本题8分）
已知一棵树边为：
{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<C,B>,<G,L>,<G,K>,<A,G>,<A,F>,<A,H>,<C,A>}
试画出这棵树，并回答下列问题：
（1）哪个是根结点？
（2）哪些是叶子结点？
（3）树的深度是多少？
九、（本题9分）
给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18)。写出用下列算法从小到大排序时第一趟结束时的序列。
（1）希尔排序（第一趟排序的增量为5）
（2）快速排序（选第一个记录为枢轴）
十、（本题15分）
编写复制一棵二叉树的非递归算法。

模拟试题（五）参考答案

一、单项选择题（每小题 2 分，共20分）
（1）B （2）B （3）B （4）C （5）B
（6）D （7）B （8）B （9）B （10）D
二、（每小题4分，共8分）
（1）3 X * Y 2 - / 1 +
（2）2 X Y 3 + * +
三、（每小题4分，共8分）
（1）二叉树的顺序存储表示如下所示：

（2）二叉树的二叉链表存储表示的示意图如下图所示：

四、（每小题4分，共8分）
（1）不是小根堆。调整为：{12,24,33,65,33,56,48,92,86,70}
（2）是小根堆。
五、（本题8分）
普里姆算法从顶点1出发得到最小生成树为：
(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20
六、（每小题2分，共8分）
（1）取散列函数为H(key)=key % 13。
（2）顺次将各个数据散列到表中，并同时列出各元素的比较次数如下表所示。

（4）计算查找成功的平均查找次数=（1×7+2×3+3×2）/12=19/12。
七、（第1小题2分，第2、3小题每小题3分，本题8分）
（1）图G有2个连通分量。
（2）按深度优先搜索所得的树如下图所示：

（3）按深度优先搜索所得的顶点序列：ABHFGCDE
八、（本题8分）
（1）树，如下图所示：

（2）C是根结点。
（3）F，K，L，H，D，M，N是叶子结点。
（3）深度是5。
九、（本题9分）
（1）（12,2,10,20,6,18,4,16,30,8,28）
（2）（6,2,10,4,8,12,28,30,20,16,18）
十、（本题15分）
将算法实现函数声明为二叉树类的友元函数，可采用层次遍历的方式进行复制，将已复制的结点进入一个队列中即可。
具体算法实现如下：

// 文件路径名:exam5\alg.h
template
void CopyBitree(BinaryTree *fromBtPtr, BinaryTree *&toBtPtr)
// 操作结果: 复制二叉树fromBt到toBt的非递归算法
{
if (toBtPtr != NULL) delete toBtPtr; // 释放toBtPtr
if (fromBtPtr->Empty())
{ // 空二叉树
toBtPtr = NULL; // 空二叉树
}
else
{ // 非空二叉树
LinkQueue<BinTreeNode *> fromQ, toQ; // 队列
BinTreeNode *fromPtr, *toPtr, *fromRoot, *toRoot;
fromRoot =(BinTreeNode *) fromBtPtr->GetRoot(); // 取出fromBtPtr的根
toRoot = new BinTreeNode(fromRoot->data); // 复制根结点
fromQ.InQueue(fromRoot); toQ.InQueue(toRoot); // 入队
while (!fromQ.Empty())
{ // fromQ非空
fromQ.OutQueue(fromPtr); // 出队
toQ.OutQueue(toPtr); // 出队
if (fromPtr->leftChild != NULL)
{ // 左子树非空
toPtr->leftChild = new BinTreeNode(fromPtr->leftChild->data);
// 复制fromPtr左孩子
fromQ.InQueue(fromPtr->leftChild); toQ.InQueue(toPtr->leftChild); // 入队
}
if (fromPtr->rightChild != NULL)
{ // 右子树非空
toPtr->rightChild = new BinTreeNode(fromPtr->rightChild->data);
// 复制fromPtr左孩子
fromQ.InQueue(fromPtr->rightChild); toQ.InQueue(toPtr->rightChild); // 入队
}
}
toBtPtr = new BinaryTree(toRoot); // 生成toBtPtr
}
}