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

devtools/2024/11/18 20:10:12/

模拟试题(五)

一、单项选择题(每小题 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
}
}


http://www.ppmy.cn/devtools/135025.html

相关文章

机器学习1

学习分类&#xff1a;监督学习、半监督学习、无监督学习、强化学习 监督学习&#xff1a;从有标签的训练数据中学习模型&#xff0c;然后对某个给定的新数据利用模型预测它的标签。 半监督学习&#xff1a;利用少量标注数据和大量无标注数据进行学习的模式 无监督学习&#…

unity小:shaderGraph不规则涟漪、波纹效果

实现概述 在本项目中&#xff0c;我们通过结合 Sine、Polar Coordinates 和 Time 节点&#xff0c;实现了动态波纹效果。以下是实现细节&#xff1a; 核心实现 Sine 波形生成&#xff1a; 使用 Sine 节点生成基本的波形。该节点能够创建周期性变化&#xff0c;为波纹效果提供…

4.1 Android NDK 简介

原生开发套件&#xff08;NDK&#xff09;是一套工具&#xff0c;使您能够在 Android 应用中使用 C/C 代码&#xff0c;并提供众多平台库&#xff0c;您可以使用这些平台库管理原生 activity 和访问实体设备组件&#xff0c;例如传感器和触控输入。如果您需要实现以下一个或多个…

Java-02 深入浅出 MyBatis - MyBatis 快速入门(无 Spring) POM Mapper 核心文件 增删改查

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; 大数据篇正在更新&#xff01;https://blog.csdn.net/w776341482/category_12713819.html 目前已经更新到了&#xff1a; MyBatis&#xff…

Java结合ElasticSearch根据查询关键字,高亮显示全文数据。

由于es高亮显示机制的问题。当全文内容过多&#xff0c;且搜索中标又少时&#xff0c;就会出现高亮结果无法覆盖全文。因此需要根据需求手动替换。 1.根据es的ik分词器获取搜索词的分词结果。 es部分&#xff1a; //中文分词解析 post /_analyze {"analyzer":"…

支持用户注册和登录、发布动态、点赞、评论、私信等功能的社交媒体平台创建!!!

需要整体源代码的可以在我的代码仓下载https://gitcode.com/speaking_me/social-media-platformTest.git 社交媒体平台 描述&#xff1a;社交媒体平台需要支持用户注册、发布动态、点赞、评论、私信等功能。 技术栈&#xff1a; 前端&#xff1a;React, Angular, Vue.js后端…

飞创直线电机模组 VS 传统丝杆模组:谁是自动化传动领域的王者?

在现代自动化技术领域&#xff0c;直线电机模组与传统丝杆模组作为两种常见的传动方式&#xff0c;各自有独特的特点和优势。然而&#xff0c;随着科学的不断进步和应用需求的日益提高&#xff0c;两者在精度、速度、寿命及可拓展性方面的差异愈发显著。本文将重点对比飞创直线…

[模板总结] - 单向链表LinkedList操作

题目汇总 Leetcode 21, 82, 160, 206, 237, 268 Leetcode 21. 合并两个有序链表 归并排序的思路&#xff0c;创建一个哨兵节点从两个链表中按大小插入即可。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(…