習(xí)題記

1，設(shè)棧的存儲(chǔ)空間為 S(1:50) ，初始狀態(tài)為 top=51 ?，F(xiàn)經(jīng)過(guò)一系列正常的入棧與退棧操作后， top=50 ，則棧中的元素個(gè)數(shù)為（1）。

解析：棧的存儲(chǔ)1，2，……，50。當(dāng)棧頂為50時(shí)只剩50這一個(gè)元素?；蛘?1-50=1

2，靜態(tài)鏈表中指針表示的是(下一個(gè)元素在數(shù)組中的位置)

解析：用數(shù)組描述的鏈表 ，即稱為靜態(tài)鏈表。所謂靜態(tài)鏈表就是沒(méi)有指針的，用下標(biāo)模仿這個(gè)指針的功能的，因此其指針指表示的是下一元素在數(shù)組中的位置。靜態(tài)鏈表由數(shù)據(jù)域和游標(biāo)構(gòu)成。

3，try與finally同時(shí)使用return

以下代碼執(zhí)行后輸出結(jié)果為（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是一定要執(zhí)行的，不管出沒(méi)出現(xiàn)異常，那么當(dāng)try，catch和finally中都有return時(shí)，只會(huì)執(zhí)行finally中的。PS：return的兩個(gè)作用：返回?cái)?shù)據(jù)、結(jié)束方法運(yùn)行

4，二叉樹(shù)中序線索化后,存在空指針域

解析：n個(gè)節(jié)點(diǎn)的二叉樹(shù)中含有n+1個(gè)空指針域。利用二叉樹(shù)中的空指針域 來(lái)存放在某種遍歷次序下的前驅(qū)和后繼 ，這種指針叫“線索”。這種加上了線索的二叉樹(shù)稱為線索二叉樹(shù)。線索二叉樹(shù)節(jié)點(diǎn)：
pleft Ltag data Rtag pRight
Ltag 標(biāo)記是否有左子樹(shù) (有前驅(qū)·) ，Rtag 標(biāo)記是否有右子樹(shù)（有后繼）
非空二叉樹(shù)中序遍歷（無(wú)頭結(jié)點(diǎn)的情況）線索化后，第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)，最后一個(gè)結(jié)點(diǎn)無(wú)后繼。

5，在用堆排序算法排序時(shí),如果要進(jìn)行增序排序,則需要采用"大根堆"

解析： 在用堆排序算法排序時(shí),如果要進(jìn)行增序排序,則需要采用“大根堆”，減序排列則要采用“小根堆”。
堆排序的方法：首先，將當(dāng)前的數(shù)組調(diào)整為堆，也就是建立堆。然后把根與最后的元素交換，重新調(diào)整堆，然后再把調(diào)整后的根與倒數(shù)第二個(gè)元素交換，再重新調(diào)整堆，直到全部元素交換完畢。這樣，對(duì)于大根堆，最大元素排列到了最后，是遞增排序。而小根堆，最小元素排列到了最后，是遞減排序。

6，繼承權(quán)限

根據(jù)以下代碼段，下列說(shuō)法中正確的是(    )。
public class Parent {
    private void m1(){}
    void m2(){}
    protected void m3(){}
    public static void m4(){}
}
a.子類(lèi)中一定能夠繼承和覆蓋Parent類(lèi)的m1方法
b.子類(lèi)中一定能夠繼承和覆蓋Parent類(lèi)的m2方法
c.子類(lèi)中一定能夠繼承和覆蓋Parent類(lèi)的m3方法
d.子類(lèi)中一定能夠繼承和覆蓋Parent類(lèi)的m4方法

解析：通過(guò)繼承，子類(lèi)可以擁有所有父類(lèi)對(duì)其可見(jiàn)的方法和域
A.私有方法只能在本類(lèi)中可見(jiàn)，故不能繼承，A錯(cuò)誤
B.缺省訪問(wèn)修飾符只在本包中可見(jiàn)，在外包中不可見(jiàn)，B錯(cuò)誤
C.保護(hù)修飾符凡是繼承自該類(lèi)的子類(lèi)都能訪問(wèn)，當(dāng)然可被繼承覆蓋；C正確
D.static修飾的成員屬于類(lèi)成員，父類(lèi)字段或方法只能被子類(lèi)同名字段或方法遮蔽，不能被繼承覆蓋，D錯(cuò)誤

7，設(shè)某棵二叉樹(shù)中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（2n-1）個(gè)結(jié)點(diǎn)。

解析：二叉樹(shù)中一個(gè)性質(zhì)：度為0的結(jié)點(diǎn)（葉子節(jié)點(diǎn)）個(gè)數(shù)n0等于度為2的結(jié)點(diǎn)個(gè)數(shù)n2加1，即N2=N0-1?？偨Y(jié)點(diǎn)數(shù)N=N0+N1+N2=N0+0+(No-1)=2N0-1。N1表示樹(shù)中度為1的結(jié)點(diǎn)。

8，圖的幾個(gè)術(shù)語(yǔ)

路徑長(zhǎng)度：路徑上各活動(dòng)持續(xù)時(shí)間的總和（即路徑上所有權(quán)之和）。
完成工程的最短時(shí)間：從工程開(kāi)始點(diǎn)（源點(diǎn)）到完成點(diǎn)（匯點(diǎn)）的最長(zhǎng)路徑稱為完成工程的最短時(shí)間。
關(guān)鍵路徑：路徑長(zhǎng)度最長(zhǎng)的路徑稱為關(guān)鍵路徑。關(guān)鍵路徑是AOE網(wǎng)絡(luò)中的概念。
AOE網(wǎng)：邊表示活動(dòng)的網(wǎng)?？捎脕?lái)估算工程的完成時(shí)間。
AOV網(wǎng)：頂點(diǎn)表示活動(dòng)的網(wǎng)。弧表示優(yōu)先關(guān)系。（拓?fù)渑判颍?br> AOV（拓?fù)渑判颍┚W(wǎng)絡(luò)中，如果邊上的權(quán)表示完成該活動(dòng)所需的時(shí)間，則稱這樣的AOV為AOE網(wǎng)絡(luò)。其中關(guān)鍵路徑是AOE網(wǎng)絡(luò)中最長(zhǎng)的一條路徑。

9，java中，StringBuilder和StringBuffer的區(qū)別

解析：Java中的String是一個(gè)類(lèi)，而并非基本數(shù)據(jù)類(lèi)型。String是值傳入，不是引用傳入。 StringBuffer和StringBuilder可以算是雙胞胎了，這兩者的方法沒(méi)有很大區(qū)別。但在線程安全性方面，StringBuffer允許多線程進(jìn)行字符操作。 這是因?yàn)樵谠创a中StringBuffer的很多方法都被關(guān)鍵字 synchronized 修飾了，而StringBuilder沒(méi)有。 StringBuilder的效率比StringBuffer稍高，如果不考慮線程安全，StringBuilder應(yīng)該是首選。另外，JVM運(yùn)行程序主要的時(shí)間耗費(fèi)是在創(chuàng)建對(duì)象和回收對(duì)象上。
String對(duì)String 類(lèi)型進(jìn)行改變的時(shí)候其實(shí)都等同于生成了一個(gè)新的 String 對(duì)象，然后將指針指向新的 String 對(duì)象；
String為字符串常量，而StringBuilder和StringBuffer均為字符串變量，即String對(duì)象一旦創(chuàng)建之后該對(duì)象是不可更改的，但后兩者的對(duì)象是變量，是可以更改的。

10，用三叉鏈表作二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，當(dāng)二叉樹(shù)中有n個(gè)結(jié)點(diǎn)時(shí)，有(n+2)個(gè)空指針。（三叉鏈表與二叉鏈表的主要區(qū)別在于，它的結(jié)點(diǎn)比二叉鏈表的結(jié)點(diǎn)多一個(gè)指針域，該域用于存儲(chǔ)一個(gè)指向本結(jié)點(diǎn)雙親的指針。）

解析1：三叉鏈表每個(gè)節(jié)點(diǎn)有三個(gè)指針域（左、親、右），共3n個(gè)指針。
其中非空指針=親（n-1個(gè)，因?yàn)楦?jié)點(diǎn)沒(méi)有雙親）+左右（n-1，因?yàn)閚個(gè)節(jié)點(diǎn)的二叉樹(shù)有n-1條邊）=2n-2；所以空指針=3n-(2n-2)=n+2。
解析二：三叉鏈表，每個(gè)節(jié)點(diǎn)有三個(gè)指針，左孩子，右孩子，父節(jié)點(diǎn)。
對(duì)于有n個(gè)節(jié)點(diǎn)的樹(shù)結(jié)構(gòu)，有n-1條邊，每條邊是孩子節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針，也是父節(jié)點(diǎn)指向孩子節(jié)點(diǎn)的孩子指針， 所以一共是2(n-1)個(gè)指針，總的指針就是3n-2(n-1)=n+2

11，若無(wú)向圖G = （V.E）中含7個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（）

解析：要保證無(wú)向圖G 在任何情況下都是連通的，即任意變動(dòng)圖G 中的邊，G 始終保持連通。任何情況都連通的最少邊數(shù)表示邊分布最浪費(fèi)的最少邊情況，取點(diǎn)數(shù)減一的完全圖6*5/2=15再加一條邊得結(jié)果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è)點(diǎn)中的任何一個(gè)就可以了
G的任意6個(gè)結(jié)點(diǎn)構(gòu)成完全聯(lián)通子圖G1，需要15條邊，然后在添加一條邊使第7結(jié)點(diǎn)與G 1連起來(lái)，共需16條邊

12，java關(guān)鍵字和保留字

1，Java 關(guān)鍵字列表 (依字母排序 共50組)：
abstract, assert, boolean, break, byte, case, catch, char, class, const（保留關(guān)鍵字）, continue, default, do, double, else, enum, extends, final, finally, float, for, goto（保留關(guān)鍵字）, 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保留字是指現(xiàn)有Java版本尚未使用，但以后版本可能會(huì)作為關(guān)鍵字使用：
byValue, cast, false, future, generic, inner, operator, outer, rest, true, var, goto （保留關(guān)鍵字） , const （保留關(guān)鍵字） , null

13，在一個(gè)長(zhǎng)為33厘米的光滑凹軌上，在第3厘米、第6厘米、第19厘米、第22 厘米、第26厘米處各有一個(gè)鋼珠，凹軌很細(xì)，不能同時(shí)通過(guò)兩個(gè)鋼珠，開(kāi)始時(shí)，鋼珠運(yùn)動(dòng)方向是任意的。兩個(gè)鋼珠相撞后，以相同速度反向運(yùn)動(dòng)。假設(shè)所有鋼珠初 始速度為每秒運(yùn)動(dòng)1厘米，那么所有鋼珠離開(kāi)凹軌的最長(zhǎng)可能時(shí)間是（30）

解析：穿越問(wèn)題，類(lèi)似螞蟻的問(wèn)題,碰撞后理解為身體都穿過(guò)去了。

14，方法重載（overload）和重寫(xiě)（override）

方法重載（overload）：
1.必須是同一個(gè)類(lèi)
2方法名（也可以叫函數(shù)）一樣
3參數(shù)類(lèi)型不一樣或參數(shù)數(shù)量不一樣

方法的重寫(xiě)（override）兩同兩小一大原則：
方法名相同，參數(shù)類(lèi)型相同
子類(lèi)返回類(lèi)型小于等于父類(lèi)方法返回類(lèi)型，
子類(lèi)拋出異常小于等于父類(lèi)方法拋出異常，
子類(lèi)訪問(wèn)權(quán)限大于等于父類(lèi)方法訪問(wèn)權(quán)限。

15，設(shè)順序循環(huán)隊(duì)列Q[0，M-1]的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列的元素個(gè)數(shù)為（（R-F+M）%M ）

解析：書(shū)中定義的隊(duì)列長(zhǎng)度為：(rear-front+QueueSize)%QueueSize
傳統(tǒng)的定義：int front;//頭指針，隊(duì)非空時(shí)指向隊(duì)頭元素，int rear;//尾指針，隊(duì)非空時(shí)指向隊(duì)尾元素的下一位置

16，java類(lèi)加載器

類(lèi)的加載是由類(lèi)加載器完成的，類(lèi)加載器包括：根加載器（ BootStrap ）、擴(kuò)展加載器（ Extension ）、系統(tǒng)加載器（ System ）和用戶自定義類(lèi)加載器（ java.lang.ClassLoader 的子類(lèi)）。從 Java 2 （ JDK 1.2 ）開(kāi)始，類(lèi)加載過(guò)程采取了父親委托機(jī)制（ PDM ）。 PDM 更好的保證了 Java 平臺(tái)的安全性，在該機(jī)制中， JVM 自帶的 Bootstrap 是根加載器，其他的加載器都有且僅有一個(gè)父類(lèi)加載器。類(lèi)的加載首先請(qǐng)求父類(lèi)加載器加載，父類(lèi)加載器無(wú)能為力時(shí)才由其子類(lèi)加載器自行加載。 JVM 不會(huì)向 Java 程序提供對(duì) Bootstrap 的引用。下面是關(guān)于幾個(gè)類(lèi)加載器的說(shuō)明：
Bootstrap ：一般用本地代碼實(shí)現(xiàn)，負(fù)責(zé)加載 JVM 基礎(chǔ)核心類(lèi)庫(kù)（ rt.jar ）；
Extension ：從 java.ext.dirs 系統(tǒng)屬性所指定的目錄中加載類(lèi)庫(kù)，它的父加載器是 Bootstrap ；
system class loader ：又叫應(yīng)用類(lèi)加載器，其父類(lèi)是 Extension 。它是應(yīng)用最廣泛的類(lèi)加載器。它從環(huán)境變量 classpath 或者系統(tǒng)屬性 java.class.path 所指定的目錄中記載類(lèi)，是用戶自定義加載器的默認(rèn)父加載器。
用戶自定義類(lèi)加載器： java.lang.ClassLoader 的子類(lèi)
父類(lèi)委托機(jī)制是可以修改的，有些服務(wù)器就是自定義類(lèi)加載器優(yōu)先的。

17，用數(shù)組r存儲(chǔ)靜態(tài)鏈表,結(jié)點(diǎn)的next域指向后繼,工作指針j指向鏈中結(jié)點(diǎn),使j沿鏈移動(dòng)的操作為(j=r[j].next)

解析：靜態(tài)鏈表和動(dòng)態(tài)鏈表。
1、靜態(tài)鏈表是用類(lèi)似于數(shù)組方法實(shí)現(xiàn)的，是順序的存儲(chǔ)結(jié)構(gòu)，在物理地址上是連續(xù)的，而且需要預(yù)先分配地址空間大小。所以靜態(tài)鏈表的初始長(zhǎng)度一般是固定的，在做插入和刪除操作時(shí)不需要移動(dòng)元素，僅需修改指針。每一個(gè)結(jié)點(diǎn)包含兩部分內(nèi)容，一部分是data（即有意義的數(shù)據(jù)），另一部分是cur（存儲(chǔ)該元素下一個(gè)元素所在數(shù)組對(duì)應(yīng)的下標(biāo)）。
2、動(dòng)態(tài)鏈表是用內(nèi)存申請(qǐng)函數(shù)（malloc/new）動(dòng)態(tài)申請(qǐng)內(nèi)存的，所以在鏈表的長(zhǎng)度上沒(méi)有限制。動(dòng)態(tài)鏈表因?yàn)槭莿?dòng)態(tài)申請(qǐng)內(nèi)存的，所以每個(gè)節(jié)點(diǎn)的物理地址不連續(xù)，要通過(guò)指針來(lái)順序訪問(wèn)。

18，父類(lèi)沒(méi)有無(wú)參的構(gòu)造函數(shù)，子類(lèi)需要在自己的構(gòu)造函數(shù)中顯式調(diào)用父類(lèi)的構(gòu)造函數(shù)。

class Person {
    String name = "No name";
    public Person(String nm) {
        name = nm;
    }
     
}
class Employee extends Person {
    public Employee(String nm) {
    //需要此行，顯式調(diào)用
        super(nm);  // 否則報(bào)錯(cuò)：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，副本與原數(shù)據(jù)是不相關(guān)的，不會(huì)相互影響的。不過(guò)一般方法傳遞時(shí)候，只有基本數(shù)據(jù)類(lèi)型和String才會(huì)傳遞副本，其他的類(lèi)型是按引用的傳遞的。

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，折半查找（二分查找）

二分查找是一種效率比較高的查找算法，但是它依賴于數(shù)組有序的存儲(chǔ)，二分查找的過(guò)程可以用二叉樹(shù)來(lái)形容描述：把當(dāng)前查找區(qū)間的中間位置上的結(jié)點(diǎn)作為根，左子表和右子表中的結(jié)點(diǎn)分別作為根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。由此得到的二叉樹(shù)，稱為描述二分查找樹(shù)的判定樹(shù)（Decision Tree）或比較樹(shù)（Comprision Tree）。時(shí)間復(fù)雜度為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//沒(méi)找到；
        {
            if(findnum < data[mid])//要找的數(shù)在根節(jié)點(diǎn)的左邊；
                high=mid-1;
            else
                low=mid+1;
        }
    }
    return -1;
}

20，import java.util.Arrays; Arrays.sort(array); //對(duì)輸入的數(shù)組進(jìn)行排序,使用java.util.Arrays類(lèi)完成排序。

21，Java中的四類(lèi)八種基本數(shù)據(jù)類(lèi)型

第一類(lèi)：整數(shù)類(lèi)型 byte short int long
第二類(lèi)：浮點(diǎn)型 float double
第三類(lèi)：邏輯型 boolean(它只有兩個(gè)值可取true false)
第四類(lèi)：字符型 char