习题记

1，设栈的存储空间为 S(1:50) ，初始状态为 top=51 。现经过一系列正常的入栈与退栈操作后， top=50 ，则栈中的元素个数为（1）。

解析：栈的存储1，2，……，50。当栈顶为50时只剩50这一个元素。或者51-50=1

2，静态链表中指针表示的是(下一个元素在数组中的位置)

解析：用数组描述的链表 ，即称为静态链表。所谓静态链表就是没有指针的，用下标模仿这个指针的功能的，因此其指针指表示的是下一元素在数组中的位置。静态链表由数据域和游标构成。

3，try与finally同时使用return

以下代码执行后输出结果为（return value of getValue(): 1 ）
public class Test {
    public static void main(String[] args) {
        System.out.println("return value of getValue(): " +
        getValue());
    }
     public static int getValue() {
         try {
             return 0;
         } finally {
             return 1;
         }
     }
 }

解析：finally是一定要执行的，不管出没出现异常，那么当try，catch和finally中都有return时，只会执行finally中的。PS：return的两个作用：返回数据、结束方法运行

4，二叉树中序线索化后,存在空指针域

解析：n个节点的二叉树中含有n+1个空指针域。利用二叉树中的空指针域 来存放在某种遍历次序下的前驱和后继 ，这种指针叫“线索”。这种加上了线索的二叉树称为线索二叉树。线索二叉树节点：
pleft Ltag data Rtag pRight
Ltag 标记是否有左子树 (有前驱·) ，Rtag 标记是否有右子树（有后继）
非空二叉树中序遍历（无头结点的情况）线索化后，第一个结点无前驱，最后一个结点无后继。

5，在用堆排序算法排序时,如果要进行增序排序,则需要采用"大根堆"

解析： 在用堆排序算法排序时,如果要进行增序排序,则需要采用“大根堆”，减序排列则要采用“小根堆”。
堆排序的方法：首先，将当前的数组调整为堆，也就是建立堆。然后把根与最后的元素交换，重新调整堆，然后再把调整后的根与倒数第二个元素交换，再重新调整堆，直到全部元素交换完毕。这样，对于大根堆，最大元素排列到了最后，是递增排序。而小根堆，最小元素排列到了最后，是递减排序。

6，继承权限

根据以下代码段，下列说法中正确的是(    )。
public class Parent {
    private void m1(){}
    void m2(){}
    protected void m3(){}
    public static void m4(){}
}
a.子类中一定能够继承和覆盖Parent类的m1方法
b.子类中一定能够继承和覆盖Parent类的m2方法
c.子类中一定能够继承和覆盖Parent类的m3方法
d.子类中一定能够继承和覆盖Parent类的m4方法

解析：通过继承，子类可以拥有所有父类对其可见的方法和域
A.私有方法只能在本类中可见，故不能继承，A错误
B.缺省访问修饰符只在本包中可见，在外包中不可见，B错误
C.保护修饰符凡是继承自该类的子类都能访问，当然可被继承覆盖；C正确
D.static修饰的成员属于类成员，父类字段或方法只能被子类同名字段或方法遮蔽，不能被继承覆盖，D错误

7，设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（2n-1）个结点。

解析：二叉树中一个性质：度为0的结点（叶子节点）个数n0等于度为2的结点个数n2加1，即N2=N0-1。总结点数N=N0+N1+N2=N0+0+(No-1)=2N0-1。N1表示树中度为1的结点。

8，图的几个术语

路径长度：路径上各活动持续时间的总和（即路径上所有权之和）。
完成工程的最短时间：从工程开始点（源点）到完成点（汇点）的最长路径称为完成工程的最短时间。
关键路径：路径长度最长的路径称为关键路径。关键路径是AOE网络中的概念。
AOE网：边表示活动的网。可用来估算工程的完成时间。
AOV网：顶点表示活动的网。弧表示优先关系。（拓扑排序）
AOV（拓扑排序）网络中，如果边上的权表示完成该活动所需的时间，则称这样的AOV为AOE网络。其中关键路径是AOE网络中最长的一条路径。

9，java中，StringBuilder和StringBuffer的区别

解析：Java中的String是一个类，而并非基本数据类型。String是值传入，不是引用传入。 StringBuffer和StringBuilder可以算是双胞胎了，这两者的方法没有很大区别。但在线程安全性方面，StringBuffer允许多线程进行字符操作。 这是因为在源代码中StringBuffer的很多方法都被关键字 synchronized 修饰了，而StringBuilder没有。 StringBuilder的效率比StringBuffer稍高，如果不考虑线程安全，StringBuilder应该是首选。另外，JVM运行程序主要的时间耗费是在创建对象和回收对象上。
String对String 类型进行改变的时候其实都等同于生成了一个新的 String 对象，然后将指针指向新的 String 对象；
String为字符串常量，而StringBuilder和StringBuffer均为字符串变量，即String对象一旦创建之后该对象是不可更改的，但后两者的对象是变量，是可以更改的。

10，用三叉链表作二叉树的存储结构，当二叉树中有n个结点时，有(n+2)个空指针。（三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域，该域用于存储一个指向本结点双亲的指针。）

解析1：三叉链表每个节点有三个指针域（左、亲、右），共3n个指针。
其中非空指针=亲（n-1个，因为根节点没有双亲）+左右（n-1，因为n个节点的二叉树有n-1条边）=2n-2；所以空指针=3n-(2n-2)=n+2。
解析二：三叉链表，每个节点有三个指针，左孩子，右孩子，父节点。
对于有n个节点的树结构，有n-1条边，每条边是孩子节点指向父节点的指针，也是父节点指向孩子节点的孩子指针， 所以一共是2(n-1)个指针，总的指针就是3n-2(n-1)=n+2

11，若无向图G = （V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）

解析：要保证无向图G 在任何情况下都是连通的，即任意变动图G 中的边，G 始终保持连通。任何情况都连通的最少边数表示边分布最浪费的最少边情况，取点数减一的完全图6*5/2=15再加一条边得结果16
5+4+3+2+1=15,15+1=16
v0连v1、v2、v3、v4、v5，5条边
v1连v2、v3、v4、v5，4条边
……
最后再让v6连v0-v5这六个点中的任何一个就可以了
G的任意6个结点构成完全联通子图G1，需要15条边，然后在添加一条边使第7结点与G 1连起来，共需16条边

12，java关键字和保留字

1，Java 关键字列表 (依字母排序 共50组)：
abstract, assert, boolean, break, byte, case, catch, char, class, const（保留关键字）, continue, default, do, double, else, enum, extends, final, finally, float, for, goto（保留关键字）, if, implements, import, instanceof, int, interface, long, native, new, package, private, protected, public, return, short, static, strictfp, super, switch, synchronized, this, throw, throws, transient, try, void, volatile, while
2，保留字列表 (依字母排序 共14组)，Java保留字是指现有Java版本尚未使用，但以后版本可能会作为关键字使用：
byValue, cast, false, future, generic, inner, operator, outer, rest, true, var, goto （保留关键字） , const （保留关键字） , null

13，在一个长为33厘米的光滑凹轨上，在第3厘米、第6厘米、第19厘米、第22 厘米、第26厘米处各有一个钢珠，凹轨很细，不能同时通过两个钢珠，开始时，钢珠运动方向是任意的。两个钢珠相撞后，以相同速度反向运动。假设所有钢珠初 始速度为每秒运动1厘米，那么所有钢珠离开凹轨的最长可能时间是（30）

解析：穿越问题，类似蚂蚁的问题,碰撞后理解为身体都穿过去了。

14，方法重载（overload）和重写（override）

方法重载（overload）：
1.必须是同一个类
2方法名（也可以叫函数）一样
3参数类型不一样或参数数量不一样

方法的重写（override）两同两小一大原则：
方法名相同，参数类型相同
子类返回类型小于等于父类方法返回类型，
子类抛出异常小于等于父类方法抛出异常，
子类访问权限大于等于父类方法访问权限。

15，设顺序循环队列Q[0，M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位，尾指针R总是指向队尾元素的当前位置，则该循环队列的元素个数为（（R-F+M）%M ）

解析：书中定义的队列长度为：(rear-front+QueueSize)%QueueSize
传统的定义：int front;//头指针，队非空时指向队头元素，int rear;//尾指针，队非空时指向队尾元素的下一位置

16，java类加载器

类的加载是由类加载器完成的，类加载器包括：根加载器（ BootStrap ）、扩展加载器（ Extension ）、系统加载器（ System ）和用户自定义类加载器（ java.lang.ClassLoader 的子类）。从 Java 2 （ JDK 1.2 ）开始，类加载过程采取了父亲委托机制（ PDM ）。 PDM 更好的保证了 Java 平台的安全性，在该机制中， JVM 自带的 Bootstrap 是根加载器，其他的加载器都有且仅有一个父类加载器。类的加载首先请求父类加载器加载，父类加载器无能为力时才由其子类加载器自行加载。 JVM 不会向 Java 程序提供对 Bootstrap 的引用。下面是关于几个类加载器的说明：
Bootstrap ：一般用本地代码实现，负责加载 JVM 基础核心类库（ rt.jar ）；
Extension ：从 java.ext.dirs 系统属性所指定的目录中加载类库，它的父加载器是 Bootstrap ；
system class loader ：又叫应用类加载器，其父类是 Extension 。它是应用最广泛的类加载器。它从环境变量 classpath 或者系统属性 java.class.path 所指定的目录中记载类，是用户自定义加载器的默认父加载器。
用户自定义类加载器： java.lang.ClassLoader 的子类
父类委托机制是可以修改的，有些服务器就是自定义类加载器优先的。

17，用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中结点,使j沿链移动的操作为(j=r[j].next)

解析：静态链表和动态链表。
1、静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。每一个结点包含两部分内容，一部分是data（即有意义的数据），另一部分是cur（存储该元素下一个元素所在数组对应的下标）。
2、动态链表是用内存申请函数（malloc/new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。

18，父类没有无参的构造函数，子类需要在自己的构造函数中显式调用父类的构造函数。

class Person {
    String name = "No name";
    public Person(String nm) {
        name = nm;
    }
     
}
class Employee extends Person {
    public Employee(String nm) {
    //需要此行，显式调用
        super(nm);  // 否则报错：Implicit super constructor Person() is undefined. Must explicitly invoke another constructor
        // TODO Auto-generated constructor stub
    }
 
    String empID = "0000";
}
public class Test {
    public static void main(String args[]) {
        Employee e = new Employee("123");
        System.out.println(e.empID);
    }
}

19，副本与原数据是不相关的，不会相互影响的。不过一般方法传递时候，只有基本数据类型和String才会传递副本，其他的类型是按引用的传递的。

package algorithms.com.guan.javajicu; 
public class Example { 
  String str = new String("good"); 
  char[] ch = {'a','b','c'}; 
  public static void main(String[] args) { 
     Example ex = new Example(); 
     ex.change(ex.str, ex.ch); 
     System.out.print(ex.str +"and"); 
     System.out.print(ex.ch);  
  } 
    
  public void change(String str, char ch[]){ 
     str= "test ok"; 
     ch[0]= 'g'; 
  } 
} 
//输出  goodandgbc

20，折半查找（二分查找）

二分查找是一种效率比较高的查找算法，但是它依赖于数组有序的存储，二分查找的过程可以用二叉树来形容描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根节点的左子树和右子树。由此得到的二叉树，称为描述二分查找树的判定树（Decision Tree）或比较树（Comprision Tree）。时间复杂度为O(logN)。

int Two_Find(int *data,int n,int findnum)
{
    int high=n-1;
    int low=0;
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(data[mid]==findnum)//找到；
        {
            return findnum;
        }
        else//没找到；
        {
            if(findnum < data[mid])//要找的数在根节点的左边；
                high=mid-1;
            else
                low=mid+1;
        }
    }
    return -1;
}

20，import java.util.Arrays; Arrays.sort(array); //对输入的数组进行排序,使用java.util.Arrays类完成排序。

21，Java中的四类八种基本数据类型

第一类：整数类型 byte short int long
第二类：浮点型 float double
第三类：逻辑型 boolean(它只有两个值可取true false)
第四类：字符型 char