数据结构Java版第二章习题
（按照自己的情况选作部分习题，不要抄袭）
第二章习题
顺序存储线性表
一判断题
1．线性表的逻辑顺序与存储顺序总是一致的。×
2．顺序存储的线性表可以按序号随机存取。√
3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。×
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。√
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。×6．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。√
二单选题 (请从下列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 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。
3．编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。
提示：可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。
4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R 中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。（研54）
5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表
（a1, a2, … , a m, b1, b2, … , b n）改变为：
（b1, b2, … , b n , a1, a2, … , a m）。
五上机实习题目
约瑟夫环问题
约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，
每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。
package算法设计;
import
import
import
public class YueSeFu {
public static void main(String[] args) {
Scanner scan = new Scanner;
"请输入总人数：");
int totalNum = ();
"请输入报数的大小：");
int cycleNum = ();
yuesefu(totalNum, cycleNum);
();
}
public static void yuesefu(int totalNum, int countNum) {
链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D)存储方式最节省运算时间。
(A)单链表
(B)双链表
(C)单循环链表
(D)带头结点的双循环链表
5．循环链表的主要优点是( D ) 。
(A)不在需要头指针了
(B)已知某个结点的位置后，能够容易找到他的直接前趋
(C)在进行插入、删除运算时，能更好的保证链表不断开
(D)从表中的任意结点出发都能扫描到整个链表
6．下面关于线性表的叙述错误的是( B )。
(A)线性表采用顺序存储，必须占用一片地址连续的单元；
(B)线性表采用顺序存储，便于进行插入和删除操作；
(C)线性表采用链式存储，不必占用一片地址连续的单元；
(D)线性表采用链式存储，不便于进行插入和删除操作；
7．单链表中，增加一个头结点的目的是为了（C）。
(A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置
（C）方便运算的实现 (D) 说明单链表是线性表的链式存储
8．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。
(A) 单链表 (B) 仅有头指针的单循环链表
(C) 双链表 (D) 仅有尾指针的单循环链表
9．若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（C）。
(A) 单链表 (B) 顺序表
(C) 双链表 (D) 单循环链表
三填空题
1．带头结点的单链表H为空的条件是__ H->next == NULL _____。
1．非空单循环链表L中*p是尾结点的条件是___ p->next == L________。
3．在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s->next=__ p->next ___;和p->next=____s_________的操作。
4．在一个单链表中p所指结点之前插入一个由指针f所指结点，可执行以下操作：s->next=_ p->next _______;
p->next=s;
t=p->data;
p->data=___ s->data ________;
s->data=____t_______;
四算法设计题
1. 已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的结点插入到表L中，使得L仍然有序。并且分析算法的时间复杂度。
package xiti;
class Lii{
int data;
Lii next;
public Lii(){
data=0;
}
public Lii(int id){
data=id;
}
public void display(){
" ");
}
}
class Lii_2{
public Lii first;
public Lii_2(){
f irst=new Lii();
}
public boolean isEmpty(){
r eturn ==null);
}
public boolean insert_2(int id){
Lii newnode =new Lii(id);
Lii p=first;
while!=null&& p=;
=;
=newnode;
r eturn true;
}
public void listdisplay(){
L ii p=first;
"显示链表：");
w hile(p!=null){
();
p=;
}
"**************");
}
}
public class L{
p ublic static void main(String[] args){
Lii_2 s1=new Lii_2();
for(int i=1;i<=9;i=i+2){
(i);
}
();
(2);
();
}
}
时间复杂度：O(elenum)
2. 假设有两个已排序的单链表A和B，编写一个函数将他们合并成一个链表C而不改变其排序性。
package xiti1;
class link{
int
data;
假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写一个函数删除该结点的前趋结点。
4. 已知两个单链表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B 的交集C，要求C同样以元素递增的单链表形式存储。
package xiti;
class link {
public int data;
设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq 域，在链表被起用之前，该域其值初始化为零。每当在链表进行一次Locata(L,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总是靠近表头。试写一个算法满足上述要求的Locata(L,x)算法。
五上机实习题目
1．一元多项式的相加
提示：
（1）一元多项式的表示问题：对于任意一元多项式：
P n(x)= P0+ P1X1+ P2X2+ … + P i X i+ … + P n X n
可以抽象为一个由“系数-指数”对构成的线性表，且线性表中各元素的指数项是递增的：
P=( ( P0,0), ( P1,1), ( P2,2), … , ( P n,n) )
(2 ) 用一个单链表表示上述线性表，结点结构为：
{ float coef; /*系数域*/
int exp; /*指数域*/
struct node *next; /*指针域*/
} Ploy Node;
package 一元多项式的加法;
import 一元多项式的加法.;
public class LinkedAdd {
public Node add(Elem e1,Elem e2){
Node pre=();
Node qre=();
Node p=;
Node q=;
Node result=p;
while(p!=null && q!=null){
if<{
pre=p;
p=;
}else if>{
Node temp=;
=q;
=p;
q=temp;
}else{
=+;
if==0){
=;
p=;
}else{
pre=p;
p=;
}
=;
q=;
}
}
if(q!=null){
=q;
}
return result;
}
public static void main(String[] args) { Elem node1=new Elem();
(7,0);
(12,3);
(2,8);
(5,12);
Elem node2=new Elem();
(4,1);
(6,3);
(2,8);
(5,20);
(7,28);
LinkedAdd l=new LinkedAdd();
Node node=(node1, node2);
while(node!=null){
"coef:"++" exp:"+;
node=;
}
}
}
package 一元多项式的加法;
class Elem{
public class Node{
public int coef;//系数
public int exp;//指数
public Node next=null;//下一个节点 public Node(){
coef=0;
exp=0;
}
public Node(int coef,int exp){
=coef;
=exp;
}
}
public Node first=new Node();
public void insert(int coef,int exp){//添加节点 Node node=new Node(coef,exp);
if(first==null){
=node;
}else{
Node temp=first;
while!=null){
temp=;
}
=node;
}
}
public Node getNode(){
return first;
}
}
面试时的Java数据结构与算法
精心整理面试时的Java数据结构与算法 查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。一般在面试中最常考的是 对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3.这样一次冒泡就完了，把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。 实现代码：
/** *@Description:冒泡排序算法实现*@author王旭 */ publicclassBubbleSort{ } } } } arr[i]=arr[j]; arr[j]=temp; } } 选择排序
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可 /** */ minIndex=i; for(intj=i+1;j//从i+1开始比较，因为minIndex默认为i了，i就没必要比了。 if(arr[j]arr[minIndex]){ minIndex=j; }
数据结构复习资料,java数据结构期末考试
第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长
数据结构(java)复习题及答案
一、选择题 1、数据结构在计算机内存中的表示是指____A__ A．数据的存储结构 B.数据结构 C. 数据的逻辑结构 D.数据元素之间的关系 2、若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）A．问题规模 B．语句条数 C．循环层数 D．函数数量 3、下列选项中与数据存储结构无关的术语是（ D ） A.顺序表 B.链表 C.链队列 D.栈 4、已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ D ） =(rear-1)%m; =(front+1)%m; =(front-1)%m; =(rear+1)%m; 5、栈和队列的共同点是__C______ A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 6、已知一堆栈的进栈序列为1234,则下列哪个序列为不可能的出栈序列______D__ 7、具有线性结构的数据结构是（ C ） A．树 B．图 C．栈和队列 D．广义表 8、假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ） A．3 B．37 C．50 D．97
9、若栈采用链式存储结构，则下列说法中正确的是（ B ） A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空 D．不需要判断栈满也不需要判断栈空 10、若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ C ） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 11、若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（ B ） 12、在n个结点的线索二叉树中，线索的数目为_C_______ A．n-1 B. n +1 13、一棵完全二叉树有1001个结点,其中有____B_____叶子结点 15、一个有n个顶点的无向图最多有___C____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 16、以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）
java笔试题目及答案分析
Java上市公司笔试题目及答案分析 一、选择题（不定项选题） 1下面说法正确的是（ C ） A．Java中包的主要作用是实现跨平台功能 B．package语句只能放在import语句后 C．包（package）是由一组类（class) 和接口（inter'face)组成 D．无 2不能用来修饰interface的有（ACD ） Aprivate Bpublic Cprotected Dstatic 3在Java语言中,下列关于字符编码和国际化的叙述，哪些是正确的（CD） A每个中文字符占用2个字节，每个英文字符占用1个字节 B假设数据库中的字符是以GBK编码的，那么显示数据库数据的网页也必须是GBK编码的。 CJava的char类型，通常以UTF-16 Big Endian的方式保存一个字符。 D实现国际化应用常用的手段是利用ResourceBundle类 解析： 1.不同的编码格式，字符所占用的字节数是不一样的。如GBK中每个中文占用2个字 节，UTF-8中则是变长编码，可能占用3个字节或者4个字节。因此A不正确。 2.不同的编码方式之间是可以转换的，如果数据库GBK编码，页面上可以使用任意 支持汉字编码的编码方式显示都可以，只要在向页面传输的数据过程中进行编码的转换即可。如：数据库是GBK，页面上是UTF-8,那么可以这样转换：实例代码以java语法编写 4下面代码的执行结果是（C ） public class TestDemo { public static void main(String[] args) { System.out.println(test1());
JAVA数据结构习题及解答(英)
Questions These questions are intended as a self-test for readers.Answers to the questions may be found in Appendix C. 1.In many data structures you can________a single record,_________it,and _______it. 2.Rearranging the contents of a data structure into a certain order is called _________. 30CHAPTER1Overview 3.In a database,a field is a.a specific data item. b.a specific object. c.part of a recor d. d.part of an algorithm. 4.The field used when searching for a particular record is the______________. 5.In object-oriented programming,an object a.is a class. b.may contain data and methods. c.is a program. d.may contain classes. 6.A class a.is a blueprint for many objects. b.represents a specific real-world object. c.will hold specific values in its fields. d.specifies the type of a method. 7.In Java,a class specification a.creates objects. b.requires the keyword new. c.creates references. d.none of the abov e. 8.When an object wants to do something,it uses a________. 9.In Java,accessing an object’s methods requires the_____operator. 10.In Java,boolean and byte are_____________. (There are no experiments or programming projects for Chapter1.) Questions31 Chapter1,Overview Answers to Questions 1.insert,search for,delete 2.sorting 3.c 4.search key 5.b 6.a 7.d 8.method
2009Java数据结构考题
一、单选题（每题2分，共30分） 1．以下数据结构中，（）是非线性数据结构。 A.树 B.字符串 C.队 D.栈 2．下面算法的时间复杂度为（） int f(int n) if (n==0 || n==1) return 1; else return n * f(n-1); A.O(1) B.O(n) C.O(n的平方) D.O(n!) 3．下述哪一条是Array这种数据结构的优点？（） A.存储密度大 B.插入运算方便 C.删除运算方便 D.可方便地用于各种逻辑结构的存储表示 4．下面关于字符串的叙述中，哪一个是不正确的？（） A.串是字符的有限序列 B.空串是由空格构成的串 C.模式匹配是字符串的一种重要运算 D.串既可以采用顺序存储，也可采用链式存储5．在无序数组中，允许重复会导致（）。 A.所有操作时间都会增加 B.总会增加插入时间 C.在某些情况下查找时间的增加 D.有时会减少插入时间 6．若某数据结构最常用的操作是存取任一指定序号的元素和在尾部进行插入和删除运算，则利用（）存储方式最节省时间。 A.Array B.双链表 C.带头结点的双循环链表 D.单循环链表 7．非空的循环单链表的尾结点p满足（）。 A.p.next==first B.p.next == null C.p == null D.p == first 8．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（） A.p.next = s; s.next = p.next; B.s.next = p.next;p.next = s; C.p.next = s; p.next = s.next; D.p.next = s.next; p.next = s; 9．有六个元素6,5,4,3,2,1.顺序进栈。问下列哪一个不是合法的出栈序列？（） A.5 4 3 6 1 2 B.4 5 3 1 2 6 C.3 4 6 5 2 1 D.2 3 4 1 5 6 10．在Hanoi塔问题中，若A塔上有3片圆盘。都要搬到C塔上去。则下列语句（）是错误的。 11．归并排序的主要缺点是（）。 A.没有递归 B.使用更多的存储空间 C.尽管比插入算法快，但是它比快速排序慢得多 D.需要7次才能完成工作 12．树最适合用来表示（） A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 13．引入二叉树的主要目的是（） A.加快查找结点的前驱或后继的速度 B.能较快地进行插入与删除 C.为了能方便的找到双亲 D.使遍历的结果唯一 14．要连通具有N个顶点的有向图，至少需要（）条边。 A.n-1 B.n C.n+1 D.2n
数据结构总复习题(JAVA)
一、填空题 1. 栈和队列的共同特点是（只允许在端点处插入和删除元素）。 2. 在深度为5的满二叉树中，叶子结点的个数为（31） 3. 算法分析的目的是（分析算法的效率以求改进）。 4. 由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的机率）。 5.串的长度是（串中所含字符的个数）。 6.设有两个串p和q，求q在p中首次出现位置的运算称做（模式匹配） 7. N个顶点的连通图中边的条数至少为（N-1）。 8.N个顶点的强连通图的边数至少有（N）。 9.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（N）。P259 10.假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（n(n-1)/2）。P292 11. 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 12. 在具有n个单元的循环队列中，队满时共有n-1 个元素。 13. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。 14. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。 15. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。
16．在一个循环队列中，队首指针指向队首元素的前一个位置。17．在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 18. 线性表中结点的集合是有限的，结点间的关系是一对一的。 19.数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 20. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 21. 一个算法的效率可分为时间效率和空间效率。 22. 在顺序表中访问任意一结点的时间复杂度均为O(1) ，因此，顺序表也称为随机存取的数据结构。 23. 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 24. 在具有n个单元的循环队列中，队满时共有n-1 个元素。 25. 对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 26. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32 个叶子。 27. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。
JAVA集合试题库完整
集合 一、第一模块：知识点讲解 图解集合 Set HashMap TreeMap LinkedHashMap ArrayList LinkList HashSet TreeSet LinkedHashSet Comparable comparator 1、集合的由来：我们学的语言是面向对象的语言，为了方便对多个对象进行操作， 我们就必须把对象存储。而要存储多个对象，就不能是一个基本变量，而应该是一个容器类型的变量。这样就引入了集合。 *以前接触过得容器：数组、StringBuffer 等 由于StringBuffer 的结果是一串字符，不一定能满足我们的要求，所以我们只能选择数
组，这就是对象数组。而对象数组不能适应变化的需求，因为数组的长度是固定。 2、数组和集合的区别 ①长度区别 集合的长度可变 数组长度不可变 ②内容区别 集合可以存储不同类型的元素 数组存储的是同一种类型的元素 ③元素的数据类型问题 数组可以存储基本数据类型也可以存储引用数据类型 集合只能存储引用类型 ，Java提供了不同的集合类，这多个集合的数据结构不同*数据结构:数据的存储方式 Java提供的多种集合类，他们的数据结构不同,但是，他们肯定有共性的内容（存储、获取、判断等）。通过不断的向上提取，我们就能够得到一个集合的继承体系结构图。 把上面这段话转化为图形的形式： collection
ArrayList Vector LinkedList HashSet TreeSet 通过这个图可以清楚的理解集合 现在我们从最低层开始学习
一、Collection(接口Java.util ) 1、功能：①：添加 boolean add(Object obj) 添加一个元素 boolean addAll(Collection c)添加一个集合的元素 ②：删除 void clear() 移除所有元素 boolean remove(Object obj) 移除一个元素
数据结构Java版第二章习题
（按照自己的情况选作部分习题，不要抄袭） 第二章习题 顺序存储线性表 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。√ 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。× 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。√ 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。×6．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。√ 二单选题 (请从下列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 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。 3．编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。
Java数据结构经典题
1.把二元查找树转变成排序的双向链表 题目： 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点，只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 首先我们定义的二元查找树节点的数据结构如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 2.设计包含min函数的栈。 定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。 3.求子数组的最大和 题目： 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。 4.在二元树中找出和为某一值的所有路径 题目：输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10 / \ 5 12 / \ 4 7 则打印出两条路径：10, 12和10, 5, 7。 二元树节点的数据结构定义为： struct BinaryTreeNode // a node in the binary tree { int m_nValue; // value of node BinaryTreeNode *m_pLeft; // left child of node BinaryTreeNode *m_pRight; // right child of node }; 5.查找最小的k个元素 题目：输入n个整数，输出其中最小的k个。 例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
java数据结构面试题
1.栈和队列的共同特点是（只允许在端点处插入和删除元素） 4.栈通常采用的两种存储结构是（线性存储结构和链表存储结构） 5.下列关于栈的叙述正确的是（D） A.栈是非线性结构 B.栈是一种树状结构 C.栈具有先进先出的特征 D.栈有后进先出的特征 6.链表不具有的特点是（B）A.不必事先估计存储空间 B.可随机访问任一元素 C.插入删除不需要移动元素 D.所需空间与线性表长度成正比 7.用链表表示线性表的优点是（便于插入和删除操作） 8.在单链表中，增加头结点的目的是（方便运算的实现） 9.循环链表的主要优点是（从表中任一结点出发都能访问到整个链表） 10.线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（D） A.每个元素都有一个直接前件和直接后件 B.线性表中至少要有一个元素 C.表中诸元素的排列顺序必须是由小到大或由大到小 D.除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件 11.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D） A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 12.线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构） 13.树是结点的集合，它的根结点数目是（有且只有1） 14.在深度为5的满二叉树中，叶子结点的个数为（31） 15.具有3个结点的二叉树有（5种形态） 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（13） 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba）
java数据结构测试题及答案解析
Java数据结构试题及解析 1 下列数据结构中，能用二分法进行查找的是__A____。 A、顺序存储的有序线性表 B、线性链表 C、二叉链表 D、有序线性链表 解析：二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等)。 2 在软件设计中，不属于过程设计工具的是__D____。 A、PDL(过程设计语言) B、PAD图 C、N-S图 D、DFD图 解析：软件设计工具包括：程序流程图、N-S、PAD、HIPO，判定表，PDL(伪码)。而DFD(数据流图)属于结构化分析工具。 3 在switch(expression)语句中，expression的数据类型不能是__A____。 A、double B、char C、byte D、short 解析：表达式expression只能返回这个几种类型的值：int、byte、short和char。多分支语句把表达式返回的值依次与每个case子句中的值相比较，如果遇到匹配的值，则执行该case子句后的语句序列。 4 下列叙述中，错误的是__D____。 A、父类不能替代子类 B、子类能够替代父类 C、子类继承父类 D、父类包含子类 5 通过继承实现代码复用： Java中所有的类都是通过直接或间接地继承https://www.wendangku.net/doc/2412884592.html,ng.Object类得到的。继承而得到的类称为子类，被继承的类称为父类。子类不能继承父类中访问权限为private的成员变量和方法，子类可以重写父类的方法，及命名与父类同名的成员变量。 子类通过隐藏父类的成员变量和重写父类的方法，把父类的状态和行为改变为自身的状态和行为。注意：子类中重写的方法和父类中被重写的方法要具有相同的名字，相同的参数表和相同的返回类型，只是函数体不同。 由于子类继承了父类所有的属性(私有的除外)，所以子类对象可以作为父类对象使用。程序中凡是使用父类对象的地方，都可以用子类对象来代替。一个对象可以通过引用子类的实例来调用子类的方法。 java运行时系统根据调用该方法的实例，来决定调用哪个方法。对子类的一个实例，如果子类重写了父类的方法，则运行时系统调用子类的方法;如果子类继承了父类的方法(未重写)，则运行时系统调用父类的方法。 6 自定义表格类中的model部分应实现的接口是___A___。 A、AbstractTableModel B、JTable C、TableModel D、TableModelable 7 下列代码中，将引起编译错误的行是__B____。 1)public class Exercise{ 2) public static void main(String args[]){ 3) float f=0.0; 4) f+=1.0; 5) } 6) } A、第2行 B、第3行 C、第4行 D、第6行 解析：float定义变量赋值时，需要在数值后面加f以标识它为浮点型，让系统知道该给它精确到多少位。 8 下列关于Java多线程并发控制机制的叙述中，错误的是___B___。 A、Java中对共享数据操作的并发控制是采用加锁技术 B、线程之间的交互，提倡采用suspend()/resume()方法
面试时的Java数据结构与算法
面试时的Java数据结构与算法 查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。 面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。通常查找和排序算法的考察是面试的开始，如果这些问题回答不好，估计面试官都没有继续面试下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握，有必要时要熟练写出代码。 接下来我们就分析一下常见的排序算法及其使用场景。限于篇幅，某些算法的详细演示和图示请自行寻找详细的参考。 冒泡排序 冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。举个栗子，对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3.这样一次冒泡就完了，把最小的数3排到最前面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。 实现代码： /** *@Description:冒泡排序算法实现 *@author 王旭 */ public class BubbleSort { public static void bubbleSort(int[] arr) { if(arr == null || == 0) return ; for(int i=0; i) { for(int j=; j>i; j--) { if(arr[j] ]) { swap(arr, j-1, j); } } } }
Java程序员笔试试题及答案
Java程序员笔试题 （答题时间60-90分钟，总分100，50分算通过，70分优秀） 姓名：_______________________开始时间：____ : ____ 一、基础，（数据结构、操作系统、网络基础、Web等）每题3分，共30分 1.请写正规表达式，数字0-9：_E_，整数：_A_，浮点数：_B_，26个小写英文字母组成的字符串：_G（有 歧义，选择H也可）_（本小题选择） A、-?\d+ B、(-?\d+)(\.\d+)? C、\w+ D、^[0-9]* E、\d F、\w G、[a-z]+ H、[a-z]* I、\d+(\.\d+)? （有歧义，选择H也可） 2.每1个B类地址能支持__E_（本空选择）个主机地址，192.168.1.100是__C__类地址，202.105.81.1/27 表示的地址范围是：___H__（本空选择）。 A、65536 B、256 C、16777216 D、255 E、65534 F、16777214 G、202.105.81.1 - 202.105.81.27 H、202.105.81.1 - 202.105.81.31 I、202.105.81.1 - 202.105.81.255 J、202.105.81.1 - 202.105.81.127 3.名词解析，内存LRU算法：___最近最少使用算法Least recently used______________________。 4.Linux下的chmod命令功能是___修改文件或目录的访问控制表，设定执行、读、写属性____________。 5.对于
《数据结构(Java版)(第2版)》习题解答
v1.0 可编辑可修改 数据结构（Java版）（第2版） 习题解答 叶核亚编著 目录 第0章 Java程序设计基础 (1) 【习0.1】实验哥德巴赫猜想。 (1) 【习0.2】实验杨辉三角形。 (1) 【习0.3】实验金额的中文大写形式。 (1) 【习0.4】实验下标和相等的数字方阵。 (1) 第6章树和二叉树 (3) 【习6.1】画出3个结点的各种形态的树和二叉树。 (3) 【习6.2】找出分别满足下面条件的所有二叉树。 (3) 【习6.3】输出叶子结点。 (3) 【习6.4】实验单链表的全部替换操作。 (4) 【习6.5】实验单链表的全部删除操作。 (4) 【习6.6】折半查找的递归算法。 (5) 【习6.7】二叉排序树查找的递归算法。 (6) 【习6.8】二叉排序树插入结点的非递归算法。 (7) 【习6.9】判断一棵二叉树是否为二叉排序树。 (8) 第7章排序 (10) 【习7.1】判断一个数据序列是否为最小堆序列。 (10) 【习7.2】归并两条排序的单链表。 (10) 【习7.3】说明二叉排序树与堆的差别。 (12) 图0.1 下标和相等的数字方阵算法描述 (1) 图6.1 3个结点树和二叉树的形态 (3) 图6.2 单支二叉树 (3) 图7.2 归并两条排序的单链表 (11) 表0.1 int n=4; ength; j++)
v1.0 可编辑可修改 p a b a b b a target a b a = ≠ = pattern t 0 t 1t 2(a) 第一次匹配，因p 0=p 2，可知t 2≠p 0p 0 p 1 p 2 a b a b b a target a b a = = pattern t 0p 0 = t 3t 1t 4t 5t 2t 3t 4t 5p 1 p 2 (b) 第二次匹配，从t 3开始比较 (2)
《数据结构与算法分析(java版)》期中考试试卷
数据结构与算法分析（Java版）期中考试试题 一、填空题（每空2分，共10分） 1．数据的逻辑结构分为： A.线性结构、图结构 B.顺序结构、链式存储结构 C.线性结构、树结构和图结构 D.顺序结构、树结构和图结构 2．哪种结构中，每个数据元素可有零个或若干个前驱数据元素和零个或若干个后继数据元素。 A.线性结构 B.顺序结构 C. 树结构 D.图结构 3．线性表删除第i个数据元素时： A. 从第i个数据元素起以后的所有数据元素依次后移 B. 从第i个数据元素起以后的所有数据元素依次前移 C. 从第(i+1)个数据元素起以后的所有数据元素依次后移 D. 从第(i+1)个数据元素起以后的所有数据元素依次前移 4．堆栈的运算是按照（）的原则进行的。 A.LIFO B.LILO C.FIFO D.都不正确 5．顺序循环队列会出现“假溢出”问题，在入队操作时，下列哪个运算可以解决这个问题。 A.rear=（rear+1）% maxsize B. front=（front+1）% mixsize C. rear=（front+1）% maxsize
D. front=（rear+1）% maxsize 二、填空题（每空2分，共20分） 1．数据结构是研究__________、__________以及__________的一门学科。 2. 数据的逻辑结构又称____________,数据的存储结构又称___________。 3．线性表按照存储结构的不同可分为_________和_________。 4．顺序循环队列的队空和队满问题的解决方法有三个，分别是：____________、____________和____________。 三、简答题（每题4分，共16分） 1.什么是算法？ 2.什么是线性表？ 3.什么是堆栈？ 4.什么是队列？ 四、分析下列程序，计算并用O()表示其时间复杂度(只分析基本语句的执行次 数即可) （第1和第3题各5分，第2题6分，共16分） 1. … for(int i=0;i 本科生毕业论文 题目:基于JAVA WEB的数据结构课程考试系统 姓名：*** 学号：*** 专业：计算机科学与技术 年级：2011级 学院：信息科学技术 完成日期：2015年4月 指导教师：*** 本科生毕业论文独创性声明 本人声明所呈交的毕业论文是本人在导师指导下进行的研究工作及取得的研究成果，除了文中特别加以标注和致谢的地方外，本论文中没有抄袭他人研究成果和伪造数据等行为。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 论文作者签名：日期：20年月日 本科生毕业论文使用授权声明 海南师范大学有权保留并向国家有关部门或机构送交毕业论文的复印件和磁盘，允许毕业论文被查阅和借阅。本人授权海南师范大学可以将本毕业论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复印手段保存、汇编毕业论文。 论文作者签名：日期：20年月日 指导教师签名：日期：20年月日 目录 1绪论 (2) 1.1问题的提出 (2) 1.2系统开发目标 (2) 1.3开发工具的选择 (2) 1.4开发本系统的意义 (2) 2系统分析 (3) 2.1背景分析 (3) 2.2可行性分析 (3) 2.2.1技术可行性分析 (3) 2.2.2经济可行性 (4) 2.2.3方案可行性 (4) 2.3功能要求 (4) 3系统总体设计 (5) 3.1系统数据流图 (5) 3.2系统的功能模块层次图 (6) 3.3系统功能模块 (7) 4数据库设计 (9) 4.1数据字典 (9) 4.2实体关系图 (11) 4.3数据库的连接 (12) 5详细设计 (13) 一、` 二、选择题 1、数据结构在计算机内存中的表示是指____A__ A．数据的存储结构 B.数据结构 C. 数据的逻辑结构 D.数据元素之间的关系 2、若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）A．问题规模 B．语句条数 C．循环层数 D．函数数量 3、下列选项中与数据存储结构无关的术语是（ D ） … A.顺序表 B.链表 C.链队列 D.栈 4、已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ D ） =(rear-1)%m; =(front+1)%m; =(front-1)%m; =(rear+1)%m; 5、栈和队列的共同点是__C______ A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 \ 6、已知一堆栈的进栈序列为1234,则下列哪个序列为不可能的出栈序列______D__ 7、具有线性结构的数据结构是（ C ） A．树 B．图 C．栈和队列 D．广义表 8、假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ） A．3 B．37 — C．50 D．97 9、若栈采用链式存储结构，则下列说法中正确的是（ B ） A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空 D．不需要判断栈满也不需要判断栈空 10、若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ C ） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树JAVAWEB数据结构课程考试系统
数据结构(java)复习题及答案
- 数据结构与JAVA集合框架期末考试试卷
- 数据结构(java)复习题及答案
- 数据结构总复习题(JAVA)
- java数据结构面试题
- 数据结构复习资料java数据结构期末考试
- 《数据结构与算法分析(java版)》期中考试试卷
- 面试时的Java数据结构与算法
- JAVA数据结构习题及解答(英)
- Java数据结构经典题
- java数据结构笔试题目
- 21688 数据结构(Java版)-例题项目
- 数据结构(java)复习题及答案
- 数据结构(java)复习题及答案
- 2009Java数据结构考题
- java数据结构面试题
- 数据结构(JAVA)复习题及答案
- 2012年安徽省JAVA版数据结构考试题库
- 2013山东省JAVA版数据结构最新考试题库(完整版)_图文
- 数据结构Java版第二章习题
- java数据结构测试题及答案解析