目录
- 一、选择题
- 二、编程题
- 2.1 MP3光标位置
- 2.1.1 题目
- 2.1.2 题解
- 2.2 洗牌
- 2.2.1 题目
- 2.2.2 题解
一、选择题
(1)下列叙述错误的是(B)
A.二叉链表是二叉树的存储结构
B.循环链表是循环队列的存储结构
C.栈是线性结构
D.循环队列是队列的存储结构
循环队列的存储结构是数组
(2)下述二叉树中,哪一种满足性质:从任意节点出发到根的路径上所经过的节点序列按其关键字有序(D)
A.二叉排序树
B.哈夫曼树
C.AVL树
D.堆
AVL树是平衡二叉排序树(二叉搜索树)
哈夫曼树是带权值的树,与元素大小顺序无关
堆是满足题目要求的,在堆中的所有节点都满足根节点大于(或小于)左右孩子
(3)为提高散列(Hash)表的查找效率,可以采取的措施是(D)
- 增大装载因子
- 设计冲突少的散列函数
- 处理冲突时避免产生聚集现象
A.1
B.2
C.1,2
D.2,3
增大装载因子,会增加冲突概率,查找效率变慢
(4)下列排序算法中,最坏情况下的时间复杂度最低的是(C)
A.希尔排序
B.快速排序
C.堆排序
D.冒泡排序
希尔排序最坏情况下的时间复杂度为O(N^2)
快速排序,当出现大量重复元素或数组几乎有序的时候,递归退化成链表,时间复杂度O(N^2)
堆排序的时间复杂度始终是O(N*logN)
冒泡排序的时间复杂度O(N^2)
二、编程题
2.1 MP3光标位置
2.1.1 题目
2.1.2 题解
思路:按照题目给出的翻页要求转化成代码即可
当歌曲数目小于4的情况比较简单,我们主要讨论一下当歌曲数目大于四的情况
使用变量mouse保存光标位置,begin保存光标所在页的起始位置
初始情况mouse=1,begin=1
(1)屏幕显示的是第一页时,光标显示的第一首歌曲时,也就是mouse=1,begin=1时,如果当前命令为U,此时需要将光标移动到最后一首歌,并将begin移动到最后一首歌所在页的第一首歌的位置
mouse=n;
begin=n-3;
(2)屏幕显示的是最后一页时,光标显示的最后一首歌曲时,也就是当mouse=n,如果当前命令是D,需要将光标移动到第一首歌,并将begin也移动到第一首歌
mouse=1;
begin=1;
(3)屏幕显示的不是第一页时,光标在当前屏幕显示的第一首歌曲时,也就是begin==mouse的情况,且用户按Up键后
begin–;
mouse–;
(4)屏幕显示的不是第一页时,光标在当前屏幕显示的最后一首歌曲时,也就是begin+3 == mouse的情况,且用户按Down键后
mouse++;
beign++;
(5)其他情况根据命令,移动光标位置即可,beign位置不用移动
【注意】:
要先判断(1)和(2)的情况,后判断(3)和(4) 的情况,最后判断(5)
代码:
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();String str = scanner.next();int mouse = 1;int begin = 1;if (n < 4) {for (int i = 0; i < str.length(); i++) {if (mouse == 1 && str.charAt(i) == 'U') {mouse = n;} else if (mouse == n && str.charAt(i) == 'D') {mouse = 1;} else if (str.charAt(i) == 'U') {mouse--;} else if (str.charAt(i) == 'D') {mouse++;}}for (int i = 1; i <= n; i++) {System.out.print(i + " ");}System.out.println();System.out.println(mouse);} else {for (int i = 0; i < str.length(); i++) {if (begin == 1 && mouse == 1 && str.charAt(i) == 'U') {mouse = n;begin = n - 3;} else if (mouse == n && str.charAt(i) == 'D') {begin = 1;mouse = 1;} else if ( begin == mouse && str.charAt(i) == 'U') {begin--;mouse--;} else if (begin + 3 == mouse && str.charAt(i) == 'D') {mouse++;begin++;} else if (str.charAt(i) == 'U') {mouse--;} else if (str.charAt(i) == 'D') {mouse++;}}System.out.println(begin + " " + (begin + 1) + " " + (begin + 2) + " " +(begin + 3));System.out.println(mouse);}}
2.2 洗牌
2.2.1 题目
2.2.2 题解
思路:
代码:
import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int m = scanner.nextInt();while (m > 0) {int n = scanner.nextInt();int k = scanner.nextInt();int[] arr=new int[2*n];for(int i=0;i<2*n;i++){int pos=i;for(int j=0;j<k;j++){if(pos<n){pos=2*pos;}else {pos=2*(pos-n)+1;}}arr[pos]=scanner.nextInt();}for(int i=0;i<2*n;i++){System.out.print(arr[i]+" ");}System.out.println();m--;}}}