Java面向对象编程

设一个有序的单链表中有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首歌。

现在要实现通过上下键控制光标移动来浏览歌曲列表，控制逻辑如下：

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);
		}
	}
}