習(xí)題記
1餐济,設(shè)棧的存儲(chǔ)空間為 S(1:50) 耘擂,初始狀態(tài)為 top=51 。現(xiàn)經(jīng)過(guò)一系列正常的入棧與退棧操作后絮姆, top=50 醉冤,則棧中的元素個(gè)數(shù)為(1)秩霍。
解析:棧的存儲(chǔ)1,2蚁阳,……铃绒,50。當(dāng)棧頂為50時(shí)只剩50這一個(gè)元素螺捐〉咝或者51-50=1
2,靜態(tài)鏈表中指針表示的是(下一個(gè)元素在數(shù)組中的位置)
解析:用數(shù)組描述的鏈表 定血,即稱(chēng)為靜態(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ù)稱(chēng)為線索二叉樹(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∥苹牵總結(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)路徑稱(chēng)為完成工程的最短時(shí)間。
關(guān)鍵路徑:路徑長(zhǎng)度最長(zhǎng)的路徑稱(chē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í)間惯悠,則稱(chēng)這樣的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 )和用戶(hù)自定義類(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)盈匾,是用戶(hù)自定義加載器的默認(rèn)父加載器。
用戶(hù)自定義類(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廷雅,折半查找(二分查找)
二分查找是一種效率比較高的查找算法耗美,但是它依賴(lài)于數(shù)組有序的存儲(chǔ),二分查找的過(guò)程可以用二叉樹(shù)來(lái)形容描述:把當(dāng)前查找區(qū)間的中間位置上的結(jié)點(diǎn)作為根榜轿,左子表和右子表中的結(jié)點(diǎn)分別作為根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。由此得到的二叉樹(shù)朵锣,稱(chēng)為描述二分查找樹(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