数据结构(Java版)(第二版)(叶核亚主编)源码_tree
//二叉树的二叉链表结点类
public class BinaryNode
{
public E data; //数据元素
public BinaryNode
public BinaryNode(E data, BinaryNode
{ //构造结点，指定元素和左、右孩子结点this.data = data;
this.left = left;
this.right = right;
}
public BinaryNode(E data) //构造有值的叶子结点
{
this(data, null, null);
}
public BinaryNode()
{
this(null, null, null);
}
public boolean isLeaf() //判断是否叶子结点
{
return this.left==null && this.right==null;
}
public String toString()
{
return this.data.toString();
}
}
//二叉树的二叉链表结点类
import dataStructure.tree.BinaryNode; //二叉树的二叉链表结点类
import dataStructure.linearList.LinkedQueue; //链式队列
import dataStructure.linearList.LinkedStack; //链式栈
public class BinaryTree
{
protected BinaryNode
public BinaryTree() //构造空二叉树
{
root=null;
}
public BinaryTree(BinaryNode
{
this.root=root;
}
public boolean isEmpty() //判断是否空二叉树
{
return this.root==null;
}
public BinaryNode
{
return this.root;
}
//6.3.3 二叉树的遍历
public void preOrder() //先根次序遍历二叉树
{
System.out.print("\n先根序列：");
preOrder(root);
}
private void preOrder(BinaryNode
if (p!=null) //若二叉树不空
{
System.out.print(p.data+" "); //访问当前结点
preOrder(p.left); //按先根次序遍历当前结点的左子树
preOrder(p.right); //按先根次序遍历当前结点的右子树}
}
public void inOrder() //中根次序遍历二叉树
{
System.out.print("\n中根序列：");
inOrder(root);
}
private void inOrder(BinaryNode
if (p!=null)
{
inOrder(p.left); //中根次序遍历左子树
System.out.print(p.data+" ");
inOrder(p.right); //中根次序遍历右子树
}
}
public void postOrder() //后根次序遍历二叉树
{
System.out.print("\n后根序列：");
postOrder(root);
}
private void postOrder(BinaryNode
if (p!=null)
{
postOrder(p.left);
postOrder(p.right);
System.out.print(p.data+" ");
}
}
//【例6.1】构造并遍历二叉树。
//3. 基于遍历的操作
public int count() //求一棵二叉树中所有结点个数
{
return count(root);
}
public int count(BinaryNode
{
if (p!=null)
return 1+count(p.left)+count(p.right);
else
return 0;
}
public int depth() //求二叉树的深度
{
return depth(root);
}
public int depth(BinaryNode
{
if (p!=null)
{
int ld = depth(p.left); //求左子树的深度
int rd = depth(p.right);
return (ld>=rd) ? ld+1 : rd+1;
}
return 0;
}
public BinaryNode
{
return search(root, value);
}
public BinaryNode
{ //先根次序遍历，返回查找到结点，若未找到返回null
BinaryNode
if (p!=null && value!=null)
{
if (p.data.equals(value))
find = p; //查找成功
else
{
find = search(p.left, value); //在左子树中查找
if (find==null)
find=search(p.right, value); //若左子树中未找到，则继续在右子树中查找}
}
return find; //返回找到结点
}
public BinaryNode
if (root==null || node==null || node==root)
return null;
return getParent(root, node);
}
public BinaryNode
{ //在以p为根的子树中查找并返回node 结点的父母结点
BinaryNode
if (p!=null)
{
if (p.left==node || p.right==node)
find = p; //查找成功
else
{
find = getParent(p.left, node); //在左子树中查找
if (find==null)
find = getParent(p.right, node); //若左子树中未找到，则继续在右子树中查找
}
}
return find; //返回找到的父母结点}
//6.3.4 构造二叉树
public BinaryTree(E[] preorder) //以标明空子树的先根序列构造一棵二叉树{
root=create(preorder);
}
private int i=0;
private BinaryNode
if (i { E elem=preorder[i]; i++; if (elem!=null) { p = new BinaryNode p.left = create(preorder); //建立p的左子树 p.right = create(preorder); //建立p的右子树 } } return p; } //【例6.2】输出二叉树中指定结点的所有祖先结点。 //6.3.5 二叉树的插入和删除操作 public void insert(BinaryNode { //若leftChild为true，插入结点作为左孩子，否则作为右孩子 if (p!=null) { BinaryNode if (leftChild) { q.left = p.left; //p结点的原左孩子成为q结点的左孩子 p.left = q; //q结点作为p结点的左孩子 } else { q.right = p.right; //p结点的原右孩子成为q结点的右孩子 p.right = q; //q结点作为p结点的右孩子 } } } public void insert(BinaryNode insert(p, element, true); } public void remove(BinaryNode { //若leftChild为true，删除左子树，否 则删除右子树 if (p!=null) { if (leftChild) p.left = null; else p.right = null; } } public void remove(BinaryNode { remove(p, true); } //6.3.6 二叉树遍历的非递归算法 public void preOrderTraverse() //先根次序遍历二叉树的非递归算法 { System.out.print("先根次序遍历（非递归）："); LinkedStack BinaryNode while(p!=null || !stack.isEmpty()) //p非空或栈非空时 if(p!=null) { System.out.print(p.data+" "); //访问结点 stack.push(p); //p结点入栈 p=p.left; //进入左子树 } else //p为空且栈非空时 { p=stack.pop(); //p指向出栈结点 p=p.right; //进入右子树 } System.out.println(); } public void inOrderTraverse() //中根次序遍历二叉树的非递归算法 { System.out.print("中根次序遍历（非递归）："); LinkedStack BinaryNode while(p!=null || !stack.isEmpty()) //p非空或栈非空时 if(p!=null) { stack.push(p); //p结点入栈 p=p.left; //进入左子树 } else //p为空且栈非空时 { p=stack.pop(); //p指向出栈结点 System.out.print(p.data+" "); //访问结点 p=p.right; //进入右子树 } System.out.println(); } //后根次序未写 //6.3.7 二叉树的层次遍历 public void levelOrder() //按层次遍历二叉树 { LinkedQueue BinaryNode System.out.print("层次遍历："); while(p!=null) { System.out.print(p.data+ " "); if(p.left!=null) que.enqueue(p.left); //p的左孩子结点入队 if(p.right!=null) que.enqueue(p.right); //p的右孩子结点入队 p = que.dequeue(); //p指向出队结点 } System.out.println(); } //第6章习题 public void leaf() //遍历输出叶子结点 { leaf(root); } private void leaf(BinaryNode { if(p!=null) { if (p.isLeaf()) System.out.print(p.data+" "); leaf(p.left); leaf(p.right); } } public int countLeaf() //求一棵二叉树中所有叶子结点个数 { return countLeaf(root); } private int countLeaf(BinaryNode if (p==null) return 0; if (p.isLeaf()) return 1; return countLeaf(p.left)+countLeaf(p.right); } public BinaryTree(BinaryTree { this.root = copy(bitree.root); } private BinaryNode { BinaryNode if(p!=null) { q = new BinaryNode q.left = copy(p.left); //复制左子树 q.right = copy(p.right); //复制右子树 } return q; //返回建立子树的根结点} public boolean equals(Object obj) //比较两棵二叉树是否相等 { if (obj == this) return true; if (obj instanceof BinaryTree) { BinaryTree return equals(this.root, bitree.root); } return false; } private boolean equals(BinaryNode { //递归方法 if(p==null && q==null) return true; if(p!=null && q!=null) return (p.data.equals(q.data)) && equals(p.left, q.left) && equals(p.right, q.right); return false; } public boolean replace(E old, E value) //将首次出现的值为old结点值替换为value { BinaryNode if(find!=null) find.data = value; //替换结点元素值 return find!=null; } public void replaceAll(E old, E value) //将值为old的结点全部替换为value { replaceAll(root, old, value); } private void replaceAll(BinaryNode { if(p!=null) { if(p.data.equals(old)) p.data = value; replaceAll(p.left, old, value); replaceAll(p.right, old, value); } } public static void main(String args[]) { String[] preorder = {"A","B","D",null,"G",null,null,null,"C","E",null,null,"F","H"}; BinaryTree preorder[0]="Z"; bitree.preOrder(); bitree.inOrder(); bitree.postOrder(); System.out.println("\n结点个数："+bitree.count()); System.out.println("高度："+bitree.depth()); System.out.print("叶子结点："); bitree.leaf(); System.out.println(" , 共"+bitree.countLeaf()+"个"); BinaryTree System.out.println("两棵二叉树相等? "+bitree.equals(bitree2)); System.out.println("第2棵二叉树替换(\"D\",\"F\")："+bitree2.replace("D","F")); System.out.println("两棵二叉树相等? "+bitree.equals(bitree2)); System.out.println("第2棵二叉树全部替换(\"F\",\"Y\") "); bitree2.replaceAll("F","Y"); bitree2.preOrder(); BinaryNode bitree.insert(find, "Z"); System.out.println("插入Z作为"+find.data+" 的左孩子\n"); bitree.levelOrder(); bitree.preOrderTraverse(); bitree.inOrderTraverse(); String[] preorder2 = {"A","B",null,null,"C"}; //标明空子树的先根序列 BinaryTree bitree3.preOrder(); bitree3.inOrder(); bitree3.postOrder(); /* BinaryTree bitree4.root = bitree4.create(preorder2); //错，i越界，私有化可避免问题bitree4.preOrder(); */ String[] preorder3 = {"D","B","A",null,null,"C",null,null,"E"}; //二叉排序树 BinaryTree bitree5.inOrder(); System.out.println("\n二叉排序树? "+bitree5.isSorted()); } //第8章习题 public boolean isSorted() //判断一棵二叉树是否为二叉排序树 { return isSorted(this.root); } public boolean isSorted(BinaryNode { boolean yes = true; if (p!=null) { if (!(p.data instanceof Comparable)) return false; Comparable cmpobj = (Comparable)p.data; if ((p.left==null || p.left!=null && https://www.wendangku.net/doc/9c16218378.html,pareTo(p.left.data)>0) && (p.right==null || p.right!=null && https://www.wendangku.net/doc/9c16218378.html,pareTo(p.right.data)<0)) { yes = isSorted(p.left); if (yes) yes = isSorted(p.right); } else yes = false; } return yes; } } /* 程序运行结果如下： 先根序列： A B D G C E F H 中根序列： D G B A E C H F 后根序列：G D B E H F C A 结点个数：8 高度： 4 叶子结点：G E H , 共3个 两棵二叉树相等? true 第2棵二叉树替换("D","F")：true 两棵二叉树相等? false 第2棵二叉树全部替换("F","Y") 先根序列： A B Y G C E Y H 第1棵二叉树查找： D 层次遍历： A B C D E F Z G H 先根次序遍历（非递归）： A B D Z G C E F H 中根次序遍历（非递归）：Z D G B A E C H F 先根序列： A B D G C E F H 中根序列： D G B A E C H F 后根序列：G D B E H F C A 中根序列： A B C D E 二叉排序树? true */ //二叉树接口 public interface BinaryTTree { boolean isEmpty(); //判断是否空二叉树 BinaryNode BinaryNode BinaryNode void inOrder(); //中根次序遍历二叉树 void postOrder(); //后根次序遍历二叉树 void levelOrder(); //按层次遍历二叉树 BinaryNode void insert(BinaryNode void remove(BinaryNode } //线索二叉树的二叉链表结点类 public class ThreadBinaryNode { public E data; //数据元素 public ThreadBinaryNode public int ltag, rtag; //左、右线索标记 public ThreadBinaryNode(E data, ThreadBinaryNode { //构造结点，指定元素和左、右孩子结点this.data = data; this.left = left; this.right = right; this.ltag = this.rtag = 0; } public ThreadBinaryNode(E data) //构造有值结点 { this(data, null, null); } public ThreadBinaryNode() { this(null, null, null); } public String toString() { return"("+this.data+","+this.ltag+","+this.rtag+")"; } } //中序线索二叉树 import dataStructure.tree.ThreadBinaryNode; public class ThreadBinaryTree { private ThreadBinaryNode public ThreadBinaryTree() //构造空线索二叉树 { root=null; } public ThreadBinaryTree(E[] preorder) //以标明空子树的先根序列构造一棵二叉树并进行中序线索化 { root=create(preorder); inorderThread(root); //中序线索化二叉树 // System.out.print("中序线索化：\r\n"+instr); } private int i=0; private ThreadBinaryNode { //返回所创建子树的根结点 ThreadBinaryNode if(i { E elem=preorder[i]; i++; if(elem!=null) { p = new ThreadBinaryNode p.left = create(preorder); //建立p的左子树 p.right = create(preorder); //建立p的右子树 } } return p; } private ThreadBinaryNode // private String instr=""; private void inorderThread(ThreadBinaryNode { if(p!=null) { inorderThread(p.left); //中序线索化p的左子树if(p.left==null) //若p的左子树为空 { p.ltag=1; //设置左线索标记 p.left=front; //设置p.left为指向前驱front的线索 } if(p.right==null) //若p的右子树为空 p.rtag=1; //设置右线索标记 if(front!=null && front.rtag==1) front.right=p; //设置前驱front.right为指向后继p的线索 /* if(front!=null) //显示中间结果 instr += "front="+front.data+"\t"; else instr += "front=null\t"; instr += "p="+p.data+"\r\n"; */ front=p; inorderThread(p.right); //中序线索化p的右子树 } } public ThreadBinaryNode { if(p.rtag==1) //若右子树为空 p=p.right; //p.right就是指向后继结点的线索 else { p=p.right; //进入右子树 while(p.ltag==0) //找到最左边的后代结点 p=p.left; } return p; } public void inOrder() //中根次序遍历中序线索二叉树，非递归算法 { ThreadBinaryNode if(p!=null) { System.out.print("中根次序遍历： "); while(p.ltag==0) p=p.left; //找到根的最左边的后代结点do { System.out.print(p.data+" "); p=inNext(p); //返回p在中根次序下的后继结点 } while(p!=null); System.out.println(); } } public ThreadBinaryNode { if(p.ltag==0) //若左子树非空 p=p.left; //左孩子就是p的后继结点else//否则，后继是右兄弟或某个中序祖先的右孩子 { if(p.rtag==0) //若左子树为空而右子树非空 p=p.right; //右孩子是p的后继结点 else { while(p.rtag==1 && p.right!=null) //叶子结点 p=p.right; //后继是其某个中序祖先的右孩子 p=p.right; } } return p; } public void preOrder() //先根次序遍历中序线索二叉树 { ThreadBinaryNode if(p!=null) { System.out.print("先根次序遍历： "); do { System.out.print(p.data+" "); p=preNext(p); }while(p!=null); System.out.println(); } } public ThreadBinaryNode { if(p.ltag==1) //若左子树为空 p=p.left; //p.left就是指向后继结点的线索 else//若左子树非空 { p=p.left; //进入左子树 while(p.rtag==0) //找到最右边的子孙结点 p=p.right; } return p; } public void inOrder_previous() //中根次序遍历中序线索二叉树，非递归算法 { ThreadBinaryNode if(p!=null) { System.out.print("中根次序遍历（反序）： "); while(p.rtag==0) p=p.right; //找到根的最右边子孙结点do { System.out.print(p.data+" "); p=inPrevious(p); //返回p的前驱结点 } while(p!=null); System.out.println(); } } public ThreadBinaryNode 根次序下的前驱结点 { if(p.rtag==0) //右子树非空 p=p.right; //右孩子是p的前驱结点else//否则，前驱是左兄弟或其某 个中序祖先的左孩子 { while(p.ltag==1 && p.left!=null) p=p.left; //寻找其某个中序祖先 p=p.left; //左孩子是p的前驱结点 } return p; } public void postOrder_previous() //后根次序遍历中序线索二 叉树，非递归算法 { ThreadBinaryNode if(p!=null) { System.out.print("后根次序遍历（反序）： "); do { System.out.print(p.data+" "); p=postPrevious(p); //返回p在后根次序下的前驱 结点 } while(p!=null); System.out.println(); } } public static void main(String args[]) { String[] preorder = {"A","B","D",null,null,"E","G",null,null,null,"C","F",null,"H",null,null,"K"}; ThreadBinaryTree tbtree.preOrder(); //先根次序遍历 tbtree.inOrder(); //中根次序遍历 tbtree.inOrder_previous(); //中根次序遍历（求前驱） tbtree.postOrder_previous(); //后根次序遍历（求前驱） } } /* 先根次序遍历： A B D E G C F H K 中根次序遍历： D B G E A F H C K 中根次序遍历（反序）： K C H F A E G B D 后根次序遍历（反序）： A C K F H B E G D */ //树接口 public interface TTree { boolean isEmpty(); //判断是否空树 E getRoot(); //返回根结点元素 E getParent(E child); //返回child的父母结点 int getChildCount(E parent); //返回parent的孩子结点数 E getFirstChild(E parent); //返回parent的一个孩子结点 E getNextSibling(E element); //返回element的下一个兄弟结点 void traverse(); //遍历树 void insert(E parent, E element); //插入element作为parent的孩子结点void remove(E parent); //删除以parent为根结点的子树 void clear(); //清空 } 精心整理面试时的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; } 第二章算法分析 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 Java 语言基础知识....................................................................................................1 基本数据类型及运算.......................................................................................1 流程控制语句...................................................................................................3 字符串...............................................................................................................3 数组...................................................................................................................5 Java 的面向对象特性................................................................................................7 类与对象...........................................................................................................7 继承...................................................................................................................9 接口.................................................................................................................10 异常.........................................................................................................................11 Java 与指针..............................................................................................................12 数据结构与算法基础.............................................................................................15 数据结构.................................................................................................................15 基本概念.........................................................................................................15 抽象数据类型.................................................................................................17 小结.................................................................................................................19 算法及性能分析.....................................................................................................19 算法.................................................................................................................19 时间复杂性.....................................................................................................20 空间复杂性.....................................................................................................24 算法时间复杂度分析.....................................................................................25 最佳、最坏与平均情况分析.........................................................................27 均摊分析.........................................................................................................29 线性表.....................................................................................................................32 线性表及抽象数据类型.........................................................................................32 线性表定义.....................................................................................................32 线性表的抽象数据类型.................................................................................32 List 接口 ..........................................................................................................34 Strategy 接口 ...................................................................................................35 线性表的顺序存储与实现.....................................................................................36 线性表的链式存储与实现.....................................................................................42 单链表.............................................................................................................42 双向链表.........................................................................................................46 线性表的单链表实现.....................................................................................48 两种实现的对比.....................................................................................................53 基于时间的比较.............................................................................................53 基于空间的比较.............................................................................................53 链接表.....................................................................................................................54 基于结点的操作.............................................................................................54 链接表接口.....................................................................................................54 基于双向链表实现的链接表.........................................................................56 1.1 1.1.1 1.1.2 1.1.3 1.1.4 1.2 1.2.1 1.2.2 1.2.3 1.3 1.4 第二章 2.1 2.1.1 2.1.2 2.1.3 2.2 2.2.1 2.2.2 2.2.3 2.2.4 2.2.5 2.2.6 第三章 3.1 3.1.1 3.1.2 3.1.3 3.1.4 3.2 3.3 3.3.1 3.3.2 3.3.3 3.4 3.5 3.4.1 3.4.2 3.5.1 3.5.2 3.5.3 一、选择题 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 ） 第0章Java程序设计基础 (1) 【习0.1】实验0.1 哥德巴赫猜想。 (1) 【习0.2】实验0.2 杨辉三角形。 (1) 【习0.3】实验0.3 金额的中文大写形式。 (1) 【习0.4】实验0.4 下标和相等的数字方阵。 (1) 【习0.5】实验0.5 找出一个二维数组的鞍点 (2) 【习0.6】实验0.6 复数类。 (2) 【习0.7】实验0.8 图形接口与实现图形接口的类 (2) 第1章绪论 (3) 【习1.1】实验1.1 判断数组元素是否已按升序排序。 (3) 【习1.2】实验1.3 用递归算法求两个整数的最大公因数。 (3) 第2章线性表 (5) 【习2.1】习2-5 图2.19的数据结构声明。 (5) 【习2.2】习2-6 如果在遍历单链表时，将p=p.next语句写成p.next=p，结果会怎样？ (5) 【习2.3】实验2.2 由指定数组中的多个对象构造单链表。 (5) 【习2.4】实验2.2 单链表的查找、包含、删除操作详见8.2.1。 (5) 【习2.5】实验2.2 单链表的替换操作。 (6) 【习2.6】实验2.2 首尾相接地连接两条单链表。 (6) 【习2.7】实验2.2 复制单链表。 (6) 【习2.8】实验2.2 单链表构造、复制、比较等操作的递归方法。 (7) 【习2.9】建立按升序排序的单链表（不带头结点）。 (8) 【习2.10】实验2.6 带头结点的循环双链表类，实现线性表接口。 (10) 【习2.11】实验2.5 建立按升序排序的循环双链表。 (14) 第3章栈和队列 (17) 【习3.1】习3-5 栈和队列有何异同？ (17) 【习3.2】能否将栈声明为继承线性表，入栈方法是add(0,e)，出栈方法是remove(0)？为什么？ (17) 【习3.3】能否用一个线性表作为栈的成员变量，入栈方法是add(0,e)，出栈方法是remove(0)？ 为什么？ (17) 【习3.4】能否将队列声明为继承线性表，入队方法是add(e)，出队方法是remove(0)？为什么？ (17) 第4章串 (18) 【习4.1】实验4.6 找出两个字符串中所有共同的字符。 (18) 【习4.2】习4-9(1) 已知目标串为"abbaba"、模式串为"aba"，画出其KMP算法的匹配过程，并给出比较次数。 (18) 数据结构(Java版)-线性表的实现与应用完整版 实验报告 课程名称数据结构 实验项目线性表的实现及应用 实验仪器PC机一台 学院_____ 专业 班级/学号 姓名 实验日期 成绩 指导教师 北京信息科技大学 信息管理学院 （数据结构课程上机）实验报告 专业: 班级: 学号: 姓名: 成绩: 实验名称线性表的实现及应用实验地点实验时间 1.实验目的： （1）理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。 （2）熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。 2.实验要求： （1）学时为8学时； （2）能在机器上正确、调试运行程序； （3）本实验需提交实验报告； （4）实验报告文件命名方法：数据结构实验_信管16xx_学号_姓名.doc。 3.实验内容和步骤： 第一部分顺序表的实现与应用 （1）基于顺序表实现线性表的以下基本操作： public interface LList 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()); A I N D E X 练习题答案 第一章练习题答案(a) n+(n–1)+(n–2)+…+2+1 = 2)1 (+ n n (b) n+(n–1)+(n–2)+…+2+1 = 2 )1 (+ n n f(n)≦c.g(n) →f(n)=O(g(n)) (a) f(n)=100n+9 c=101, g(n)=n, n0=10 得知f(n)=O(n) (b) f(n)=1000n2+100n–8 c=2000, g(n)= n2, n0=1 得知f(n)=O(n2) (c) f(n)=5*2n+9 n2+2 c=10, n0=5 得知f(n)=O(2n) f(n)≧c g(n) →f(n)=Ω(g(n)) (a) f(n)=3n+1 c=2, n0=1, g(n)=n 得知f(n)=Ω(n)(b) f(n)=100n2+4n+5 c=10, n0=1, g(n)= n2 得知f(n)=Ω(n2) (c) f(n)=8*2n+8n+16 c=8, n0=1, g(n)= 2n 得知f(n)=Ω(n2) c1.g(n)≦f(n)≦c2.g(n) →f(n)= Θ(g(n)) (a) f(n)=3n+2 c1=3, c2=6, n0=1 得知f(n) = Θ (n) (b) f(n)=9n2+4n+2 c1=9, c2=16, n0=1 得知f(n) = Θ (n2) (c) f(n)=8n4+5n3+5 c1=8, c2=20, n0=1 得知f(n) = Θ (n4) 练习题解答 第二章练习题答案 1. 分别以行为主和以列为主说明之。 (a) 以行为主 A(i, j)=l0+(i–1)*u2*d+(j–1)*d (b) 以列为主 A(i, j)=l0+(j–1)*u1*d+(i–1)*d 2. 以列为主 A(i, j)=l0+(j–12)*md+(i–l1)d m=u1–l1+1=5–(–3)+1=9 m=u2–l2+1=2–(–4)+1=7 A(1, 1) =100+(1–(–4))*9+(1–(–3)) =100+45+4=149 3. 分别以行为主和以列为主的说明。 由于数组为A(1：u1, 1：u2, 1：u3)，因此p = u1-l1+1, q = u2- l2+1, r = u3- l3+1 所以p = u1-1+1 = u1, q = u2-1+1 = u2, r = u3-1+1 = u3 (a) 以行为主 A(i, j, k)=l0 + (i–1)*u2*u3*d + (j–1)*u3*d +(k-1) (b) 以列为主 A(i, j, k)=l0 + (k–1)*u1*u2*d + (j–1)*u1*d + (i-1)*d 4. 以列为主：A(i, j, k)=l0 + (k–l3)*pqd + (j–l2)*pd + (i-l1)*d p = 5-(-3) + 1 = 9, q = 2-(-4)+1 = 7, r = 5-1+1 = 5 A(2, 1, 2) = 100 + (2-1)*9*7*1 + (1-(-4))*9*1 + (2-(-3))*1 = 100 + 63 + 45 + 5 = 253 （按照自己的情况选作部分习题，不要抄袭） 第二章习题 顺序存储线性表 一判断题 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)个人按顺时针方向围坐一圈， 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 长沙民政学院2015年上学期期末考试卷（A卷） 考试科目：《数据结构》考试形式：闭卷 适应班级：软开 1431-1439 一、单项选择（共20题，每题2分, 共40分） 1、以下数据结构中哪一个是非线性结构（） A. 队列 B. 栈 C.二叉树 D. 线性表 2、（）不是算法的主要特性。 A．输入性 B．输出性 C．有穷性 D．高效性 3、（）不是线性表的存储结构。 A．叉链表 B．单链表 C．双向链表 D．循环链表 4、线性表是： A.一个有限序列，可以为空； B. 一个有限序列，不能为空； C. 一个无限序列，可以为空； D. 一个无序序列，不能为空 5、用链表表示线性表的优点是（）。 A.便于随机存取 B.花费的存储空间较顺序存储少 C.便于插入和删除 D.数据元素的物理顺序与逻辑顺序相同 6、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D.仅有尾指针的单循环链表 7、栈中元素的进出原则是（） A. 先进先出 B.后进先出 C. 栈空则进 D. 栈满则出 8、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为( ) A．i B．n=i C．n-i+1 D．不确定 9、若依次输入数据元素序列{a，b，c，d，e，f，g}进栈，出栈操作可以和入栈操作间隔进行，则下列哪个元素序列可以由出栈序列得到( ) A．{ c，d，b，e，g，a，f} B．{ f，e，g，d，a，c，b} C．{e，f，d，g，b，c，a} D．{d，e，c，f，b，g，a} 10、一个栈的入栈序列是1,2,3,4,5，则下列序列中不可能的出栈序列是( ) A． 2,3,4,1,5 B． 2,3,1,4,5 C．5,4,1,3,2 D．1,5,4,3,2 11、判断一个循环队列( m0为最大队列长度（以元素为单位），front和rear分别为队列的队头指针和队尾指针 ) 为空队列的条件是( )。 A． front == rear B． front != rear C． front == (rear+1) % m0 D． front != (rear+1) % m0 12、判断一个循环队列( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 )为满队列的条件是( )。 A． front== rear B．front!= rear C． front==( rear+1) % m0 D． front!=( rear+1) % m0 13、串是一种特殊的线性表，其特殊性体现在（）。 A．可以顺序存储B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符 14、假设S=“abcaabcaaabca”，T=“bca”， (T,3) （其中3为索引号，索引号从0开始编号）的结果是（） A．1 B．5 C．10 D．0 15、二叉树的数据结构描述了数据之间的（）关系。 A．链接关系 B．层次关系 C．网状关系 D．随机关系 16、（）遍历方法在遍历它的左子树和右子树后再遍历它自身。 A．先序遍历 B.后序遍历 C. 中序遍历 D. 层次遍历 17、在构造哈夫曼树的过程中说法正确的是（）。 A. 使权值越大的叶结点越远离根结点，而权值越小的叶结点越靠近根结点 B.使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点 C. 最终是带权路径长度最大的二叉树 D. 构造的过程是一次到位 18、55为最第一趟快速排序的基准值，执行一趟快速排序能够得到的序列是（A ）。 A. [12，27，45，41] 55 [34，63，72] B. [45，34，12，41] 55 [72，63，27] C. [63，12，34，45，27] 55 [41，72] D. [41，12，34，45，27] 55 [72，63] 19、对线性表进行二分查找时，要求线性表必须( )。 A．以顺序方式存储 B．以链接方式存储 一、单选题（每题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 一、填空题 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的出度。 集合 一、第一模块：知识点讲解 图解集合 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数据结构与算法
数据结构复习资料,java数据结构期末考试
数据结构与算法(JAVA语言版)_
数据结构(java)复习题及答案
《数据结构Java版》习题解答
数据结构(Java版)-线性表的实现与应用完整版
java笔试题目及答案分析
数据结构(Java版)习题解答
数据结构Java版第二章习题
JAVA数据结构习题及解答(英)
《数据结构(Java语言版)》试卷1
2009Java数据结构考题
数据结构总复习题(JAVA)
JAVA集合试题库完整
- java数据结构测试题及答案解析
- 《数据结构(Java版)(第2版)》习题解答
- 数据结构总复习题(JAVA)
- Java数据结构
- 数据结构Java版第二章习题汇编
- 数据结构Java版习题解答
- 数据结构 JAVA 复习题及答案
- 6数据结构复习资料,JAVA数据结构期末考试
- 数据结构(Java)复习题及答案 1绪论
- java笔试题目及答案分析
- JAVA集合试题库完整
- JAVA语言程序设计考试试题的答案
- Java程序员笔试试题及答案
- JAVAWEB数据结构课程考试系统
- 数据结构复习资料,java数据结构期末考试
- 数据结构JAVA语言描述习题答案(刘小晶等主编).pdf总复习
- 京东笔试题目整理
- 面试时的Java数据结构与算法
- 2012湖南省JAVA版数据结构最新考试题库(完整版)_图文
- 数据结构(java)复习题及答案