笔试强训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(nlog2n)、、O(n^2)、O(nlog2n）
C O(n)、O(n2)、O(n2)
D O(nlog2n)、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。
叶子结点到根结点要走几次叶子结点，最后求和
62+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个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始
游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。
给定一个66的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
正确答案：
class Bonus {
public:
int getMost(vector > board)
{
// write code here
int row = board.size();
int col = board[0].size();
vector> allPrice(row, vector(col, 0));
allPrice[0][0] = board[0][0];
for(int i=0; i
for(int j=0; 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
#include
using namespace std;int ROW, COL;
vector> maze;
vector> path_tmp; //临时路劲
vector> 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
while(cin >> ROW >> COL)
{
maze = vector>(ROW, vector(COL, 0)); //开辟迷宫空间
path_tmp.clear();
path_best.clear();
//首先输入迷宫
for(int i=0; i
for(int j=0; j>maze[i][j];
}
MazeTrack(0, 0); //从起始点（0，0）开始走
//输出路径
for(int i=0; i
cout<<"("<