当前位置: 首页 > news >正文

笔试强训48天——day24

文章目录

  • 一. 单选
    • 1.请指出选择排序,冒泡排序,快速排序的时间复杂度分别是()
    • 2. 在单链表中,增加头结点的目的是()
    • 3.下列算法的功能是什么?
    • 4. 表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时,对象栈和运算符栈为(),其中^为乘幂
    • 5. 假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为()
    • 6. 一棵完全二叉树第六层有9个叶结点(根为第一层),则结点个数最多有()
    • 7. 有权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为()
    • 8.已知小根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆,最后的叶子节点为()
    • 9. 将10个元素散列到100000个单元的哈希表中,则()产生冲突
    • 10.下列排序算法中,元素的移动次数与关键字的初始排列次序无关的是 ()
  • 二. 编程
    • 1. 年终奖
    • 2. 迷宫问题

一. 单选

1.请指出选择排序,冒泡排序,快速排序的时间复杂度分别是()

A O(n2)、O(n2)、O(nlog2n)
B O(n
log2n)、、O(n^2)、O(nlog2n)
C O(n)、O(n2)、O(n2)
D O(n
log2n)、O(n2)、O(n2)

正确答案:A

简单排序——平方间
先进排序——对数间

 

2. 在单链表中,增加头结点的目的是()

A 标识表结点中首结点的位置
B 算法实现上的方便
C 使单链表至少有一个结点
D 说明单链表是线性表的链式存储实现

正确答案:B

如果没有头结点,在插入或删除的时候需要特殊处理,有了头结点就需要修改头结点的next指针即可
 

3.下列算法的功能是什么?

/*L是无头节点单链表*/
LinkList Demo(LinkList L){
ListNode *Q,*P;
if(L&&L->next){
Q=L;
L=L->next;
P=L;
while(P->next)
P=P->next;
p->next=Q;
} 
return L;
}

A 遍历链表
B 链表深拷贝
C 链表反转
D 单链表转变为循环链表

正确答案:D

 

4. 表达式3*2(4+2*2-6*3)-5求值过程中当扫描到6时,对象栈和运算符栈为(),其中为乘幂

A 3,2,4,1,1;(^(+-
B 3,2,8;(^-
C 3,2,4,2,2;(
^(-
D 3,2,8;*^(-

正确答案:D

表达式求值
数据栈——遇到数据就入栈
操作符栈——运算符优先级大于操作符栈中的才入栈,遇到优先级低的运算符就停止入栈,先进行对高的运算符求解——先将运算符出栈,然后从数据栈中出两个数,先出的为右数,后出的为左数——将结果重新入数据栈
当出现优先级同样大的,先出现的优先级就高,先算

 

5. 假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为()

A 3
B 37
C 97
D 50

正确答案:B

从头指针到尾指针有13个元素位置(60-47),那么先存13个,再循环过来就是37到尾(50-13),是循环队列

 

6. 一棵完全二叉树第六层有9个叶结点(根为第一层),则结点个数最多有()

A 112
B 111
C 107
D 109

正确答案:D

第六层的最多的叶子节点个数:2^(6-1) = 32
比9大,证明还有第7层,如果全是32个叶子结点,那么没有第七层
2^7-1 = 127(计算的是满七层的二叉树结点)
127-9*2 = 109(需要减去第六层9个叶子结点的子树(叶子结点没有子树,所以这9个没有第七层,要减掉)

性质1:在二叉树的第i成上至多有2^(i-1)个结点
性质2:深度为k的二叉树至多有(2^k)-1个结点

 

7. 有权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为()

A 24
B 71
C 48
D 53

正确答案:B

构造哈夫曼树——先选较小的两个值为叶子结点,他俩的和是根结点,往上构造
带权求和值最小的数

带权路径长度:用原先的这几个数来求11,8,6,2,5。
叶子结点到根结点要走几次叶子结点,最后求和
6
2+23+53+82+112 = 71

 

8.已知小根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆,最后的叶子节点为()

A 34
B 21
C 16
D 12

正确答案:C

 

9. 将10个元素散列到100000个单元的哈希表中,则()产生冲突

A 一定会
B 一定不会
C 仍可能会

正确答案:C

 

10.下列排序算法中,元素的移动次数与关键字的初始排列次序无关的是 ()

A 直接插入排序
B 起泡排序
C 基数排序
D 快速排序。
正确答案:C

 
 

二. 编程

1. 年终奖

链接

小东所在公司要发年终奖,而小东恰好获得了最高福利,他要在公司年会上参与一个抽奖游戏,游戏在一个66的棋盘上进行,上面放着36个价值不等的礼物,每个小的棋盘上面放置着一个礼物,他需要从左上角开始
游戏,每次只能向下或者向右移动一步,到达右下角停止,一路上的格子里的礼物小东都能拿到,请设计一个算法使小东拿到价值最高的礼物。
给定一个6
6的矩阵board,其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值,保证每个礼物价值大于100小于1000。

正确答案:

class Bonus {
public:
int getMost(vector<vector<int> > board)
{
// write code here
int row = board.size();
int col = board[0].size();
vector<vector<int>> allPrice(row, vector<int>(col, 0));
allPrice[0][0] = board[0][0];
for(int i=0; i<row; ++i)
{
for(int j=0; j<col; ++j)
{
//如果是起点坐标,不做任何处理。
if(i==0 && j==0)
continue;
if(i == 0) //在第一行,只能往右走
allPrice[i][j] = allPrice[i][j-1] + board[i][j];
else if(j == 0) //在第一列,只能往下走
allPrice[i][j] = allPrice[i-1][j] + board[i][j];
else
//除去两个临界边,剩下的就是既能向右走,也能向下走,
//这时候就要考虑走到当前点的所有可能得情况,也就是走到当前点
//各自路径的和是不是这些所有到达该点路径当中最大的了
allPrice[i][j] = max(allPrice[i][j-1], allPrice[i-1][j]) + board[i][j];
}
}
 // 返回最后一个坐标点的值,它就表示从左上角走到右下角的最大奖励
return allPrice[row-1][col-1];
}
};

 
 

2. 迷宫问题

链接

定义一个二维数组 N*M ,如 5 × 5 数组下所示:
maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找
出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

输入描述:
输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的
路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。
输出描述:
左上角到右下角的最短路径,格式如样例所示。

示例1:
输入
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

示例2:
输入
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0
输出
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)
说明
注意:不能斜着走!!

正确答案:

#include<iostream>
#include<vector>
using namespace std;

int ROW, COL;
vector<vector<int>> maze;
vector<vector<int>> path_tmp; //临时路劲
vector<vector<int>> path_best; //最佳路劲

void MazeTrack(int i, int j)
{
    maze[i][j] = 1; //代表(i,j)已经走过
path_tmp.push_back({i,j});
//判断是否到达出口
  if(i==ROW-1 && j==COL-1)
  {
  //寻找最短路劲
  if(path_best.empty() || path_best.size()>path_tmp.size())
  path_best = path_tmp;
  } 
//向右走
if(j+1<COL && maze[i][j+1]==0)
MazeTrack(i, j+1);
//向左走
if(j-1>=0 && maze[i][j-1]==0)
MazeTrack(i, j-1);
//向上走
if(i-1>=0 && maze[i-1][j]==0)
MazeTrack(i-1, j);
//向下走
if(i+1<ROW && maze[i+1][j]==0)
MazeTrack(i+1, j);
maze[i][j] = 0; //回溯 恢复路劲
path_tmp.pop_back();
} 
int main()
{
while(cin >> ROW >> COL)
{
maze = vector<vector<int>>(ROW, vector<int>(COL, 0)); //开辟迷宫空间
path_tmp.clear();
path_best.clear();
//首先输入迷宫
for(int i=0; i<ROW; ++i)
{
for(int j=0; j<COL; ++j)
cin>>maze[i][j];
} 
MazeTrack(0, 0); //从起始点(0,0)开始走
//输出路径
for(int i=0; i<path_best.size(); ++i)
{
cout<<"("<<path_best[i][0]<<","<<path_best[i][1]<<")"<<endl;
}
} 
return 0;
}

相关文章:

  • 【车载开发系列】UDS诊断---写入数据($0x2E)
  • ARM ACP
  • 评职称需要什么专利
  • CMake详细教程
  • CorelDRAW破解版是如何一步一步坑人的
  • 堆排序讲解
  • 网络工程师备考3章
  • 算法day42|背包问题
  • 《构建中小企业网络V7.1》实验
  • R语言贝叶斯Poisson泊松-正态分布模型分析职业足球比赛进球数
  • Matplotlib入门[05]——注释与标签
  • HarmonyOS/OpenHarmony应用开发-FA模型综述
  • Vue中的diff算法深度解析
  • redis常用数据结构基本命令
  • 公路交叉数(POJ3067)-树状数组解决逆序对
  • k8s删除node
  • 使用SpringBoot快速构建Web API
  • vue 如何获取路由详细内容信息
  • 【数据库系统】数据更新
  • 【视觉高级篇】23 # 如何模拟光照让3D场景更逼真?(上)
  • myBaits Target Capture Kits;myBaits 靶向捕获试剂盒,快速捕获富集目标序列
  • 【表格单元格可编辑】vue-elementul简单实现table表格点击单元格可编辑,点击单元格变成输入框修改数据
  • ES7-ES13 新特性
  • 【C++】打开C++的大门
  • 【深度学习】U-Net和FCN具体分析
  • Linux下 git 上传与删除 的基本指令
  • Swift 新 async/await 同步机制小技巧:消除“多余”的 await 关键字
  • Github如何使用详细介绍(保姆级教学)
  • 【ardunio+sx1268】与【esp32+sx1268】实现不同主控单片机lora通讯
  • Linux常用命令——pvscan命令
  • 旅游管理专业学什么 难就业吗
  • 2022海南高考体育专业考试时间 什么时候考试
  • 云南楚雄高考时间2021具体时间:6月7日
  • 高考什么特长可以加分 政策有哪些
  • 2022年贵州高考218分能报什么大学 218分能上哪些院校
  • 2022大专石油化工专业毕业后待遇 工资高吗
  • 中国科学院大学2021年各省录取分数线及专业分数线
  • 学英语用点读笔好不好 有效果吗
  • 2021河南职业技术学院学费多少 各专业收费标准
  • 2022广西外语口试成绩查询时间公布 什么时候查分