数据结构与算法分析模拟试题及答案6
模拟试题（六）
一、单项选择题（每小题 2 分，共20分）
（1）设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树采用二叉链表存储时空指针域个数为（ ）。
A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1 D）2n0+n1
（2）若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择（ ）。
A）快速排序 B）堆排序 C）归并排序 D）直接插入排序
（3）对于有n个顶点的有向图，由弗洛伊德（Floyd）算法求每一对顶之间的最短路径的时间复杂度是（ ）。
A）O(1) B）O(n) C）O(n) D）O(n3)
（4）对n个元素的序列进行并归排序，所需要的辅助存储空间为（ ）。
A）O（1） B）O（log2n） C）O（n） D）O（n2）
（5）哈夫曼树中一定不存在（ ）。
A）度为0的结点 B）度为1的结点 C）度为2的结点 D）带权的结点
（6）设D={A,B,C,D}，R={<C,A>,<A,B>,<B,D>,<D,C>,<D,A>}，则数据结构(D,{R})是（ ）。
A）树 B）图 B）线性表 D）前面都正确
（7）（ ）关键字序列不符合堆的定义。
A）‘A’、‘C’、‘D’、‘G’、‘H’、‘M’、‘P’、‘Q’、‘R’、‘X’
B）‘A’、‘C’、‘M’、‘D’、‘H’、‘P’、‘X’、‘G’、‘Q’、‘R’
C）‘A’、‘D’、‘P’、‘R’、‘C’、‘Q’、‘X’、‘M’、‘H’、‘G’
D）‘A’、‘D’、‘C’、‘M’、‘P’、‘G’、‘H’、‘X’、‘R’、‘Q’
（8）一组记录的排序码为(48,24,18,53,16,26,40)，采用冒泡排序法进行排序，则第一趟排序需要进行记录交换的次数是（ ）。
A）3 B）4 C）5 D）6
（9）下面（ ）可以判断出一个有向图中是否有环（回路）？
A）求关键路径 B）拓扑排序
C）求最短路径 D）前面都不正确
（10）对线性表进行二分法查找，其前提条件是（ ）。
A）线性表以顺序方式存储，并且按关键字值排好序
B）线性表以顺序方式存储，并且按关键字值的检索频率排好序
C）线性表以链接方式存储，并且按关键字值排好序
D）线性表以链接方式存储，并且按关键字值的检索频率排好序
二、（本题8分）
在如下表所示的数组A中链接存储了一个线性表，表头指针存放在A[0].next，试写出该线性表。
三、（本题8分）
已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ，试画出这棵二叉树。
四、（本题8分）
已知一个图的顶点集V为： V={1,2,3,4,5,6,7}，弧如下表所示。
试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。
五、（本题8分）
向最小根堆中依次插入数据4, 2, 5, 8, 3, 6, 10, 1时，画出每插入一个数据后堆的变化。
六、（本题8分）
有二叉树中序序列为：ABCEFGHD；后序序列为：ABFHGEDC；请画出此二叉树。
七、（每小题4分，共8分）
对给定的有7个顶点的有向图的邻接矩阵如下：
（l）画出该有向图；
（2）若将图看成是AOE-网，画出关键路径。
八、（本题8分）
给出一组关键字29、18、25、47、58、12、51、10，分别写出按下列各种排序方法进行排序时的变化过程：
（1）归并排序，每归并一次书写一个次序。
（2）快速排序，每划分一次书写一个次序以及最后排好序后的序列。
（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
九、（本题9分）
试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。
十、（本题15分）
已知两个带头结点的单链表A和B分别表示两个集合，元素值递增有序，设计算法求出A，B的交集C，并同样以递增的形式存储。
模拟试题（六）参考答案
一、单项选择题（每小题 2 分，共20分）
（1）D （2）C （3）D （4）C （5）B
（6）B （7）C （8）C （9）B （10）A
二、（本题8分）
线性表为：(90,40,78,50,34,60)
三、（本题8分）
四、（本题8分）
用克鲁斯卡尔算法得到的最小生成树为：
(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7
五、（本题8分）
如下图所示：
六、（本题8分）
根据后序序列知根结点为C，所以左子树：中序序列为AB，后序序列为AB；右子树：中序序列为EFGHD，后序序列为FHGED，以此类推得该二叉树结构如下图所示。
七、（每小题4分，共8分）
（1）由邻接矩阵所画的有向图如下图所示：
（2）关键路径如下图所示：
(25,47)(12,58)(l0,51)
(l8,25,29,47)(10,12,51,58)
(l0,12,18,25,29,47,51,58)
（2）快速排序： (10,18,25,12)29(58,51,47)
(10(18,25,12)29((47,51)58)
(10((12)18(25))29((47(51))58)
(10,12,18,25,29,47,51,58)
（3）堆排序： 初始堆（大顶推）：(58,47,51,29,18,12,25,10)
第一次调整：(51,47,25,29,18,12,10)(58)
第二次调整：(47,29,25,10,18,12)(51,58)
第三次调整：(29,18,25,10,12)(47,51,58)
第四次调整：(25,18,12,10)(29,47,51,58)
第五次调整：(l8,10,12)(25,29,47,51,58)
第六次调整：(l2,10)(18,25,29,47,51,58)
第七次调整：(l0,12,18,25,29,47,51,58)
九、（本题9分）
具有3个结点的树的不同形态如下图所示。
具有3个结点的二叉树的不同形态如下图所示。
十、（本题15分）
解答：由于单链表A和B是递增有序的，可设置两个整型变量分别表示两个单链表的当前元素的位置，依次取出A与B的元素进行比较，当A的数据元素小于B的值时，将指向A的当前位置都后移；当A的数据元素大于B的值时，将指向B的当前位置都后移，否则复将A（或B）的当前元素制到C中，并同时将A与B的当前位置后移。具体算法如下：
用单链表la表示集合 la，用单链表lb表示集合 lb，用单链表lc表示集合 lc，具体算法如下：
// 文件路径名:exam6\alg.h
template
void Interaction(const LinkList &la, const LinkList &lb,
LinkList &lc)
// 初始条件: la和lb中数据元素递增有序
// 操作结果: lc返回la与lb表示的集合的交集，并使lc中数据元素仍递增有序
{
ElemType aItem, bItem; // la和lb中当前数据元素
int aLength = la.Length(), bLength = lb.Length(); // la和lb的长度
int aPosition = 1, bPosition = 1; // la和lb的当前元素序号
lc.Clear();// 清空lc
while (aPosition <= aLength && bPosition <= bLength )
{// 取出la和lb中数据元素进行归并
la.GetElem(aPosition, aItem);// 取出la中数据元素
lb.GetElem(bPosition, bItem);// 取出lb中数据元素
if (aItem < bItem)
{// aItem插入到lc
aPosition++;// 指向la下一数据元素
}
else if (aItem > bItem)
{// lb后移
bPosition++;// 指向lb下一数据元素
}
else
{// aItem == bItem，la和lb同时后移
lc.Insert(lc.Length() + 1, aItem);// 插入aItem到lc
aPosition++;// 指向la下一数据元素
bPosition++;// 指向lb下一数据元素
}
}
}
原文地址：https://blog.csdn.net/m0_54748666/article/details/143813459
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！