（按照自己的情况选作部分习题，不要抄袭）
第二章习题
顺序存储线性表
总是一致的。×
2．顺序存储的线性表可以按序号随机存取。√
3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。×
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。√
2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。
3．编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。
提示：可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。
3．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。√
4．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。×
二单选题(请从下列A，B，C，D选项中选择一项)
1．线性表是(A)。
(A)一个有限序列，可以为空；(B)一个有限序列，不能为空；
(C)一个无限序列，可以为空；(D)一个无序序列，不能为空。
2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A）个元素。
(A)n/2 (B) n+1/2 (C) n -1/2 (D) n
三填空题
1．在顺序表中做插入操作时首先检查___表是否满了______________。
四算法设计题
1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。
System.out.print("请输入总人数：");
inttotalNum = scan.nextInt();
System.out.print("请输入报数的大小：");
intcycleNum = scan.nextInt();
yuesefu(totalNum, cycleNum);
scan.close();
start.remove(start.size() - 1);
k = 0;
}else{
System.out.println(start.get(k));
start.remove(k);
}
}
}
}
链式存储线性表
一判断题
1．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。×
2．线性表的链式存储结构优于顺序存储结构。×
（a1, a2, … , am, b1, b2, … , bn）改变为：
（b1, b2, … , bn, a1, a2, … , am）。
五上机实习题目
约瑟夫环问题
约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。
2．线性表采用链式存储时，其地址(D)。
(A)必须是连续的；(B)部分地址必须是连续的；
(C)一定是不连续的；(D)连续与否均可以。
3．用链表表示线性表的优点是 （C）。
(A)便于随机存取
(B)花费的存储空间较顺序存储少
(C)便于插入和删除
(D)数据元素的物理顺序与逻辑顺序相同
4.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用(D)存储方式最节省运算时间。
}
publicstaticvoidyuesefu(inttotalNum,intcountNum) {
//初始化人数
List<Integer> start =newArrayList<Integer>();
for(inti = 1; i <= totalNum; i++) {
start.add(i);
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。×
6．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。√
二单选题(请从下列A，B，C，D选项中选择一项)
1．线性表是(A)。
(A)一个有限序列，可以为空；(B)一个有限序列，不能为空；
(C)一个无限序列，可以为空；(D)一个无序序列，不能为空。
}
//从第K个开始计数
intk = 0;
while(start.size() >0) {
k = k + countNum;
//第m人的索引位置
k = k % (start.size()) - 1;
//判断是否到队尾
if(k < 0) {
System.out.println(start.get(start.size()-1));
(A)单链表
(B)双链表
(C)单循环链表
(D)带头结点的双循环链表
5．循环链表的主要优点是(D)。
(A)不在需要头指针了
(B)已知某个结点的位置后，能够容易找到他的直接前趋
(C)在进行插入、删除运算时，能更好的保证链表不断开
(D)从表中的任意结点出发都能扫描到整个链表
6．下面关于线性表的叙述错误的是(B)。
4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。（研54）
5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表
package算法设计;
importjava.util.ArrayList;
importjava.util.List;
importjava.util.Scanner;
publicclassYueSeFu {
publicstaticvoidmain(String[] args) {
Scanner scan =newScanner(System.in);