设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度（）
A. O(log2n)
B. O(1)
C. O(n2)
D. O(n)
答案：D
一个栈的初始状态为空。首先将元素5，4，3，2，1 依次入栈，然后退栈一次，再将元素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的 元素）的顺序为（）
A. 1DCAB2345
B. 1DCBA2345
C. 54321ABCD
D. DCBA12345
答案：B
设栈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
给定下列程序，那么执行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
在具有 2n 个结点的完全二叉树中，叶子结点个数为（）
A. n
B. n+1
C. n-1
D. n/2
答案：A
下列叙述中错误的是（ ）
A. 二叉链表是二叉树的存储结构
B. 循环链表是循环队列的存储结构
C. 栈是线性结构
D. 循环队列是队列的存储结构
答案：B
下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）
A. 二叉排序树
B. 哈夫曼树
C. AVL树
D. 堆
答案：D
为提高散列（Hash）表的查找效率，可以采取的正确措施是（ ） Ⅰ．增大装填（载）因子 Ⅱ．设计冲突（碰撞）少的散列函数 Ⅲ．处理冲突（碰撞）时避免产生聚集（堆积）现象
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、 Ⅱ
D. 仅Ⅱ、 Ⅲ
答案：D
将整数数组（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-4-7-5-6-3-2
答案：C
下列各排序法中，最坏情况下的时间复杂度最低的是（ ）
A. 希尔排序
B. 快速排序
C. 堆排序
D. 冒泡排序
答案：C
洗牌
题目描述：洗牌在生活中十分常见，现在需要写一个程序模拟洗牌的过程。 现在需要洗2n张牌，从上到下依次是第1张，第2张，第3张一直到第2n张。首先，我们把这2n 张牌分成两堆，左手拿着第1张到第n张（上半堆），右手拿着第n+1张到第2n张（下半堆）。接着就开始洗牌的过程，先放下右手的最后一张牌，再放下左手的 最后一张牌，接着放下右手的倒数第二张牌，再放下左手的倒数第二张牌，直到最后放下左手的第一张牌。接着把牌合并起来就可以了。 例如有6张牌，最开始 牌的序列是1,2,3,4,5,6。首先分成两组，左手拿着1,2,3；右手拿着4,5,6。在洗牌过程中按顺序放下了6,3,5,2,4,1。把这六张牌再次合成一组牌之后，我们按照从 上往下的顺序看这组牌，就变成了序列1,4,2,5,3,6。 现在给出一个原始牌组，请输出这副牌洗牌k次之后从上往下的序列。
输入描述：第一行一个数T(T ≤ 100)，表示数据组数。对于每组数据，第一行两个数n,k(1 ≤ n,k ≤ 100)，接下来一行有2n个数a1,a2,...,a2n(1 ≤ ai ≤ 1000000000)。表示原始牌组从上到下的序列。
输出描述：对于每组数据，输出一行，最终的序列。数字之间用空格隔开，不要在行末输出多余的空格。
public class Main34 { //洗牌 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 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]; 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 main(String[] args) { Scanner scanner=new Scanner(System.in); int groups=scanner.nextInt(); for (int i = 0; i < groups; ++i) { //读入每组数据 int n=scanner.nextInt(); int k=scanner.nextInt(); int[] cards=new int[2*n]; for (int j = 0; j < 2*n; ++j) { cards[j]=scanner.nextInt(); } //洗牌 playCard(cards,n,k); } } }
MP3光标位置
链接：MP3光标位置__牛客网
来源：牛客网
MP3 Player因为屏幕较小，显示歌曲列表的时候每屏只能显示几首歌曲，用户要通过上下键才能浏览所有的歌曲。为了简化处理，假设每屏只能显示4首歌曲，光标初始的位置为第1首歌。
现在要实现通过上下键控制光标移动来浏览歌曲列表，控制逻辑如下：
- 歌曲总数<=4的时候，不需要翻页，只是挪动光标位置。
光标在第一首歌曲上时，按Up键光标挪到最后一首歌曲；光标在最后一首歌曲时，按Down键光标挪到第一首歌曲。
特殊翻页：屏幕显示的是第一页（即显示第1 – 4首）时，光标在第一首歌曲上，用户按Up键后，屏幕要显示最后一页（即显示第7-10首歌），同时光标放到最后一首歌上。同样的，屏幕显示最后一页时，光标在最后一首歌曲上，用户按Down键，屏幕要显示第一页，光标挪到第一首歌上。
其他情况，不用翻页，只是挪动光标就行。
数据范围：命令长度1≤s≤100 1\le s\le 100\ 1≤s≤100 ，歌曲数量1≤n≤150 1\le n \le 150\ 1≤n≤150
进阶：时间复杂度：O(n) O(n)\ O(n) ，空间复杂度：O(n) O(n)\ O(n)
输入描述:
输入说明：
1 输入歌曲数量
2 输入命令 U或者D
输出描述:
输出说明
1 输出当前列表
2 输出当前选中歌曲
示例1
输入
10
UUUU
输出
7 8 9 10
7
import java.util.*; public class Main { public static void MP3PlayerLow4(String str, int n) { char[] ch = str.toCharArray(); int begin = 1, cur = 1; // 起始序号，当前歌曲序号 for (int i = 0; i < ch.length; i++) { if (cur == 1 && ch[i] == 'U') { // 光标在第一首歌曲上时，按Up键光标 cur = n; continue; } if (cur == n && ch[i] == 'D') { // 光标在最后一首歌曲时，按Down键光标 cur = 1; continue; } if (ch[i] == 'U') { cur -= 1; } if (ch[i] == 'D') { cur += 1; } } for (int i = 0; i < n; i++) { if (i==0) { System.out.print(begin); }else{ System.out.print(" "+(begin+i)); } } System.out.println(); System.out.println(cur); } public static void MP3PlayerUp4(String str, int n) { char[] ch = str.toCharArray(); int begin = 1, cur = 1; // 起始序号，当前歌曲序号 for (int i = 0; i < ch.length; i++) { if (begin==1 && cur == 1 && ch[i] == 'U') { // 光标在第一页 ,第一首歌曲上时,按Up键光标 cur = n; begin = n-3; continue; } if (begin==n-3 && cur == n && ch[i] == 'D') { // 光标在最后一页,最后一首歌曲时，按Down键光标 cur = 1; begin = 1; continue; } if (ch[i] == 'U' && begin==cur ) { // 光标在非第一页，第一首歌曲时，按Up键后，从当前歌曲的上一首开始显示，光标也挪到上一首歌曲。 cur -= 1; begin-= 1; continue; } if (ch[i] == 'D' && begin+3==cur) { cur += 1; begin+= 1; continue; } if(ch[i] == 'U'){ cur -= 1; }else{ cur += 1; } } System.out.println(begin + " " + (begin + 1) + " " + (begin + 2)+ " " + (begin + 3)); System.out.println(cur); } public static void main(String[] args) { Scanner input = new Scanner(System.in); while (input.hasNextInt()) { int n = input.nextInt(); // 歌曲数量 String str = input.next(); // 操作序列 if (n<=4) MP3PlayerLow4(str, n); else MP3PlayerUp4(str, n); } } }
