个人网站 名字,云南 网站模版,重庆网络推广外包,为企业开发网站模拟试题#xff08;五#xff09;
一、单项选择题#xff08;每小题 2 分#xff0c;共20分#xff09; #xff08;1#xff09;队列的特点是#xff08; #xff09;。 A#xff09;先进后出 B#xff09;先进先出 C#xff09;任意位置进出 D#xff0…模拟试题五
一、单项选择题每小题 2 分共20分 1队列的特点是 。 A先进后出 B先进先出 C任意位置进出 D前面都不正确 2有n个记录的文件如关键字位数为d基数为r则基数排序共要进行 遍分配与收集。 An Bd Cr Dn - d 3在二叉树结点的先序序列、中序序列和后序序列中所有叶子结点的先后顺序 。 A都不相同 B完全相同 C先序和中序相同而与后序不同 D中序和后序相同而与先序不同 4限定在一端加入和删除元素的线性表称为 。 A双向链表 B单向链表 C栈 D队列 5若数据元素序列1112137892345是采用下列排序方法之一得到的第二趟排序后的结果则该排序算法只能是 。 A起泡排序 B插入排序 C选择排序 D二路归并排序 6设森林F对应的二叉树为B它有m个结点B的根为pp的右子树上的结点个数为n森林F中第一棵树的结点个数是 。 Am-n-1 Bn1 Cm-n1 Dm-n 7对于具有n个顶点的强连有向图其弧条数的最小值为 。 An1 Bn Cn-1 Dn-2 8下面关于广义表的叙述中不正确的是 。 A广义表可以是一个多层次的结构 B广义表至少有一个元素 C广义表可以被其他广义表所共享 D广义表可以是一个递归表 9设二叉树根结点的层次为0一棵深度高度为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点下列关系式不正确的是 。 Afc Bcf Cf2k1-1 Dc2k-1 10设一棵二叉树中没有度为1的结点已知叶子结点数为n此树的结点数为 。 A2n2 B2n1 C2n D2n-1 二、每小题4分共8分 写出下列中缀表达式的后缀形式 13X/(Y-2)1 22X*(Y3) 三、每小题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分 1B 2B 3B 4C 5B 6D 7B 8B 9B 10D 二、每小题4分共8分 13 X * Y 2 - / 1 22 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×72×33×2/1219/12。 七、第1小题2分第2、3小题每小题3分本题8分 1图G有2个连通分量。 2按深度优先搜索所得的树如下图所示 3按深度优先搜索所得的顶点序列ABHFGCDE 八、本题8分 1树如下图所示 2C是根结点。 3FKLHDMN是叶子结点。 3深度是5。 九、本题9分 112,2,10,20,6,18,4,16,30,8,28 26,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 { // 非空二叉树 LinkQueueBinTreeNode * 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 } }
