【Java笔试强训 21】
🎉🎉🎉点进来你就是我的人了
博主主页：🙈🙈🙈戳一戳,欢迎大佬指点!欢迎志同道合的朋友一起加油喔🤺🤺🤺
目录
一、选择题
二、编程题
🔥 洗牌
🔥MP3光标位置
一、选择题
1、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度（）
A O(log2n)
B O(1)
C O(n2)
D O(n)
正确答案： D
2、一个栈的初始状态为空。首先将元素5，4，3，2，1 依次入栈，然后退栈一次，再将元素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）的顺序为？
A 1DCAB2345
B 1DCBA2345
C 54321ABCD
D DCBA12345
正确答案： B
3、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次压入栈S,一个元素出栈后即进入队列Q，若出队列的顺序为e2,e4,e3,e6,e5,e1则栈S的容量要求最小值为
A 2
B 3
C 4
D 5
正确答案： B
4、给定下列程序，那么执行printf(“%d\n”, foo(20, 13));的输出结果是________。
int foo(int x, int y){
if (x <= 0 || y <= 0)
return 1;
return 3 * foo( x-6, y/2 );
}
A 3
B 9
C 27
D 81
正确答案： D
参考答案：
解析：foo(20, 13) = 3 * foo(14, 6) = 3 * 3 * foo(8, 3) = 3 * 3 * 3 * foo(2, 1) = 3 * 3 * 3 * 3 * foo(-4, 0) =3 * 3 * 3 * 3 * 1 = 81
答案：D
5、在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
正确答案： A
参考答案：
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。根据完全二叉树性质，如果共 2n 个结点，从根结点开始按层序用自然数 1 ， 2 ，…， 2n 给结点编号，则编号为 n 的结点左子结点编号为 2n ，因此叶子结点编号为 n+1,n+2, … ,2n 。故叶子结点个数为 n ，本题
答案为 A 选项。
6、下列叙述中错误的是（ ）
A 二叉链表是二叉树的存储结构
B 循环链表是循环队列的存储结构
C 栈是线性结构
D 循环队列是队列的存储结构
正确答案： B
参考答案：
循环队列是队列的一种顺序存储结构，用队尾指针 rear 指向队列中的队尾元素，用排头指针 front 指向排头元素的前一个位置。循环链表是用不连续的存储单元存储数据，它有一个表头结点，队头指针指向表头结点，最后一个结点的指针域指向表头结点。二叉链表是树的二叉链表实现方式。栈是一种特殊存取方式的线性表。故本题答案为 B 选项。
7、下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序()
A 二叉排序树
B 哈夫曼树
C AVL树
D 堆
正确答案： D
8、为提高散列（Hash）表的查找效率，可以采取的正确措施是（ ）。
Ⅰ．增大装填（载）因子
Ⅱ．设计冲突（碰撞）少的散列函数
Ⅲ．处理冲突（碰撞）时避免产生聚集（堆积）现象
A 仅Ⅰ
B 仅Ⅱ
C 仅Ⅰ、 Ⅱ
D 仅Ⅱ、 Ⅲ
正确答案： D
9、将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，数组的顺序是_____。
A 2-6-3-5-4-1-7
B 6-2-3-5-4-1-7
C 6-5-3-2-4-1-7
D 1-5-3-2-4-6-7
E 5-4-3-2-1-6-7
F 5-1-3-2-4-6-7
正确答案： C
10、下列各排序法中，最坏情况下的时间复杂度最低的是（ ）
A 希尔排序
B 快速排序
C 堆排序
D 冒泡排序
正确答案： C
参考答案：
堆排序最坏情况时间下的时间复杂度为 O(nlog2n) ；希尔排序最坏情况时间下的时间复杂度为 O(n1.5) ；快速排序、冒泡排序最坏情况时间下的时间复杂度为O(n2) 。故本题答案为 C 选项。
二、编程题
🔥 洗牌
洗牌_牛客题霸_牛客网
【解题思路】：
每次读取一个数之后，算出他经过k次洗牌后的位置，只用一个长度为2n数组用来输出
根据当前数的位置，可以算出经过一次洗牌后的位置
如果当前数小于等于n（即在左手），则他下次出现的位置是 2当前位置
与之对应的当前位置 + n（即在右手）的牌,则他下次出现的位置是 2当前位置 + 1
import java.util.*;
public class Main{
public static void playCard(int[] cards, int n, int k){
// i --> 2 * i
// i + n ---> 2 * i + 1
for(int i = 0; i < k; ++i){
//一次洗牌的过程
int[] newCards = new int[cards.length];
//遍历编号为 0 ~ n - 1
for(int j = 0; j < n; ++j){
newCards[2 * j] = cards[j];
newCards[2 * j + 1] = cards[j + n];
}
cards = newCards;
}
//从上往下打印
printCard(cards);
}
public static void printCard(int[] cards){
for(int i = 0; i < cards.length - 1; ++i){
System.out.print(cards[i] + " ");
}
System.out.println(cards[cards.length - 1]);
}
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int groups = s.nextInt();
for(int i = 0;i < groups; ++i){
//读入每组数据
int n = s.nextInt();
int k = s.nextInt();
int[] cards = new int[2 * n];
for(int j = 0; j < 2 * n; ++j){
cards[j] = s.nextInt();
}
//洗牌
playCard(cards, n, k);
}
}
}
🔥MP3光标位置
MP3光标位置_牛客题霸_牛客网
【解题思路】：
本题比较简单，通过解析指令，进行移动即可，分两种情况，歌曲数目不大于4和大于4的情况。
import java.util.*;
import java.io.*;
public class Main{
public static void mouseMove(String numStr, String orderStr){
//歌曲数量
int n = Integer.parseInt(numStr);
//指令数组： UD
char[] order = orderStr.toCharArray();
//当前鼠标所在的位置
int mouse = 1;
//显示列表所在的起始位置
int first = 1;
//指令处理
//n <=4
if(n <= 4){
//循环处理每一个指令
for(int i = 0; i < order.length; ++i){
//光标在第一首歌曲上时，按Up键光标挪到最后一首歌曲
if(mouse == 1 && order[i] == 'U')
mouse = n;
//光标在最后一首歌曲时，按Down键光标挪到第一首歌曲
else if(mouse == n && order[i] == 'D')
mouse = 1;
//其他情况下用户按Up键，光标挪到上一首歌曲
else if(order[i] == 'U')
--mouse;
//用户按Down键，光标挪到下一首歌曲
else if(order[i] == 'D')
++mouse;
}
//输出
//打印当前的显示列表
for(int i = 1; i < n; ++i)
System.out.print(i + " ");
System.out.println(n);
//打印当前歌曲
System.out.println(mouse);
}else{
//n > 4
for(int i = 0; i < order.length; ++i){
//屏幕显示的是第一页（即显示第1 – 4首）时，光标在第一首歌曲上，
//用户按Up键后，屏幕要显示最后一页（即显示第7-10首歌），
//同时光标放到最后一首歌上。
if(first == 1 && mouse == 1 && order[i] == 'U'){
//最右一页的起始位置
first = n - 3;
mouse = n;
}
//同样的，屏幕显示最后一页时，光标在最后一首歌曲上，
//用户按Down键，屏幕要显示第一页，光标挪到第一首歌上。
else if(first == n - 3 && mouse == n && order[i] == 'D'){
first = 1;
mouse = 1;
}
//屏幕显示的不是第一页时，光标在当前屏幕显示的第一首歌曲时，用户按Up键后，
//屏幕从当前歌曲的上一首开始显示，光标也挪到上一首歌曲。
else if(first != 1 && mouse == first && order[i] == 'U'){
--mouse;
--first;
}
//屏幕显示的不是第一页时,光标在当前屏幕的最后一首歌时的
//按Down键，屏幕从当前歌曲的下一首开始显示，光标也挪到下一首歌曲
else if(first != n - 3 && mouse == first + 3 && order[i] == 'D'){
first++;
mouse++;
}
//其它情况，只移动光标
else if(order[i] == 'U')
--mouse;
else if(order[i] == 'D')
++mouse;
}
//输出
//打印当前的显示列表
for(int i = first; i < first + 3; ++i)
System.out.print(i + " ");
System.out.println(first + 3);
//打印当前歌曲
System.out.println(mouse);
}
}
public static void main(String[] args) throws Exception{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String numStr;
while((numStr = reader.readLine()) != null){
String orderStr = reader.readLine();
mouseMove(numStr, orderStr);
}
}
}
