将N条长度均为M的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为() A. O(N * M * logN)
B. O(N*M)
C. O(N)
D. O(M)
答案:A
下设栈S的初始状态为空,元素a,b,c,d,e,f依次入栈S,出栈的序列为b,d,c,f,e,a,则栈S的容量至少为()
A. 6
B. 5
C. 4
D. 3
答案:D
大小为MAX的循环队列中,f 为当前队头元素位置,r 为当前队尾元素位置(最后一个元素的位置),则任意时刻,队列中的元素个数为()
A. r-f
B. (r-f+MAX+1)%MAX
C. r-f+1
D. (r-f+MAX)%MAX
答案:B
HASH 函数冲突处理方式不包括以下哪一项()
A. 开放定址法
B. 链地址法
C. 插入排序法
D. 公共溢出区法
答案:C
若一棵二叉树具有12个度为2的结点,6个度为1的结点,则度为0的结点个数是()
A. 10
B. 11
C. 13
D. 不确定
答案:C
()二叉排序树可以得到一个从小到大的有序序列。
A. 先序遍历
B. 中序遍历
C. 后序遍
D. 层次遍历
答案:B
已知小根堆为8,15,10,21,34,16,12,删除关键字8之后需重建堆,最后的叶子节点为()
A. 34
B. 21
C. 16
D. 12
答案:C
已知某个哈希表的n个关键字具有相同的哈希值,如果使用二次探测再散列法将这n个关键字存入哈希表,至少要进行____次探测。
A. n-1
B. n C. n+1
D. n(n+1)
E. n(n+1)/2
F. 1+n(n+1)/2
答案:E
下列选项中,不可能是快速排序第2趟排序结果的是 ()
A. 2,3,5,4,6,7,9
B. 2,7,5,6,4,3,9
C. 3,2,5,4,7,6,9
D. 4,2,3,5,7,6,9
答案:C
下列选项中,不可能是快速排序第2趟排序结果的是 ()
A. 2,3,5,4,6,7,9
B. 2,7,5,6,4,3,9
C. 3,2,5,4,7,6,9
D. 4,2,3,5,7,6,9
答案:C
年终奖
题目描述:小东所在公司要发年终奖,而小东恰好获得了最高福利,他要在公司年会上参与一个抽奖游戏,游戏在一个6*6的棋盘上进行,上面放着36个价值不等的礼物, 每个小的棋盘上面放置着一个礼物,他需要从左上角开始游戏,每次只能向下或者向右移动一步,到达右下角停止,一路上的格子里的礼物小东都能拿到,请设 计一个算法使小东拿到价值最高的礼物。
给定一个6*6的矩阵board,其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值,保证每个礼物价值大于100小于1000。
public class getMost {
//年终奖
public int getMost(int[][] borad){
int row=borad.length;
int col=borad[0].length;
//处理第一行
for (int i = 1; i < col; ++i) {
borad[0][i] +=borad[0][i-1];
}
//处理第一列
for (int i = 1; i < row; ++i) {
borad[i][0] +=borad[i-1][0];
}
//处理剩余位置
for (int i = 1; i < row; ++i) {
for (int j = 1; j < col; ++j) {
//F(i,j) = max(F(i-1 ,j), F(i,j-1)) + borad[i][j]
borad[i][j] += Math.max(borad[i-1][j],borad[i][j-1]);
}
}
return borad[row-1][col-1];
}
}
迷宫问题
题目描述:定义一个二维数组 N*M ,如 5 × 5 数组下所示:
int 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],既第一格 是可以走的路。
数据范围:2<= n,m<=10 , 输入的内容只包含0<=val<=1
输入描述:输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只 有一条通道。
输出描述:左上角到右下角的最短路径,格式如样例所示。
class Node{
int x;
int y;
public Node(int x,int y){
this.x=x;
this.y=y;
}
}
public class Main39 {
public static void main(String[] args) throws Exception{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String str;
while ((str =reader.readLine()) !=null){
String[] arr=str.split(" ");
int row=Integer.parseInt(arr[0]);
int col=Integer.parseInt(arr[1]);
//创建迷宫矩阵
int[][] mat=new int[row][col];
//读入迷宫数据
for (int i = 0; i < row; ++i) {
str=reader.readLine();
arr=str.split(" ");
for (int j = 0; j < col; ++j) {
mat[i][j]=Integer.parseInt(arr[j]);
}
}
//搜索最短路径
ArrayList<Node> path=new ArrayList<>();
ArrayList<Node> minPath=new ArrayList<>();
int[][] book=new int[row][col];
getMinPath(mat,row,col,0,0,book,path,minPath);
//打印最短路径
for (Node n: minPath) {
System.out.println("(" + n.x +","+ n.y+")");
}
}
}
//mat: 迷宫矩阵,row,col
//x,y :当前位置
//book: 标记矩阵,标记当前位置是否走过
//path: 保存当前路径的每一个位置
//minPath: 保存最短路径
public static void getMinPath(int[][] mat,int row,int col,int x,int y,int[][] book,
ArrayList<Node> path,ArrayList<Node> minPath){
//判断(x,y):是否越界,是否走过,是否有障碍
if (x < 0 || x>=row || y<0 || y>=col || book[x][y]==1 || mat[x][y]==1){
return;
}
//把当前位置存入路径中
path.add(new Node(x,y));
//标记当前位置
book[x][y]=1;
//判断当前位置是否为出口
if (x==row-1 && y==col-1){
//一条新的路径产生
//判断是否为更短的路径
if (minPath.isEmpty() || path.size()<minPath.size()){
//更新最短路径
minPath.clear();
for (Node n:path) {
minPath.add(n);
}
}
}
//继续搜索(x,y)的上下左右四个方向
getMinPath(mat,row,col,x+1,y,book,path,minPath);
getMinPath(mat,row,col,x-1,y,book,path,minPath);
getMinPath(mat,row,col,x,y-1,book,path,minPath);
getMinPath(mat,row,col,x,y+1,book,path,minPath);
//把当前位置从路径中删除,寻找新的路径
path.remove(path.size()-1);
book[x][y]=0;
}
}