一、選擇題
1.D。【解析】算法的空間複雜度，是指執行這個算法所需的存儲空間。算法所佔用的存儲空間包括算法程序所佔用的空間、輸入的初始數據所佔用的存儲空間及算法執行過程中所需要的額外空間。
2.C。【解析】數據結構是相互之間存在一種或多種特定關係的數據元素的集合。”關係”描述的是數據元素之間的邏輯關係，因此又稱數據的邏輯結構。數據的存儲結構是指數據結構(數據的邏輯結構)在計算機中的表示，又稱物理結構。數據的存儲結構有順序存儲結構和鏈式存儲結構兩種。不同存儲結構的數據處理效率不同。由於鏈表採用鏈式存儲結構，元素的物理順序並不連續，對於插入和刪除無需移動元素，很方便，當查找元素時就需要逐個元素查找，因此查找的時間相對更長。
3.B。【解析】二叉樹的遍歷有3種：前序、中序和後序。後序遍歷首先遍歷左子樹或左子結點，然後遍歷右子樹或右子結點，最後訪問根結點;中序遍歷首先遍歷左子樹或左子結點，然後訪問根結點，最後遍歷右子樹或右子結點;後序遍歷首先訪問根結點，然後遍歷左子樹或左子結點，最後遍歷右子樹或右子結點。本題根據前序遍歷和中序遍歷的
結果可以得出二叉樹的結構，然後再對其進行後序遍歷，因此答案爲選項B。
4.A。【解析】二分法查找只適用於順序存儲的有序線性表，對於順序存儲的非有序線性表和線性鏈表，都只能採用順序查找。
5.B。【解析】程序的三種基本控制結構包括：順序、選擇和重複(循環)，這三種結構就足以表達出各種其他形式的結構。
6.C。【解析】在模塊化程序設計中，模塊之間的聯繫可以通過程序的控制結構來實現，在自頂向下、逐步細化的設計過程中，首先要考慮全局目標，而不是細節。在程序設計中模塊化和結構化可以同時使用，一個模塊的內部結構也要符合結構化設計原則。
7.B。【解析】設計軟件結構，是在軟件概要設計階段進行的，而概要設計屬於軟件開發期。
8.B。【解析】在數據庫系統中，需要對數據進行集中、統一的管理，以達到被多個應用程序共享的目標。
9.D。【解析】物理設計階段主要解決選擇文件存儲結構和確定文件存取的方法的問題，包括：選擇存儲結構、確定存取方法、選擇存取路徑、確定數據的存放位置。
10.D。【解析】文件系統所管理的數據文件基本上是分散、相互獨立的。因此相對於數據庫系統，以此爲基礎的數據處理存在3個缺點：數據冗餘大、數據的不一致性、程序與數據的相互依賴(簡稱爲數據依賴)。
11.A。【解析】分塊查找是將表分成若干塊，分塊的原則是數據元素的關鍵字在塊與塊之間是有序的，而塊內元素的關鍵字是無序的。分塊法可以適應動態變化的要求。其他三種是在順序存儲的一組記錄內進行查找的。
12.B。【解析】順序結構邏輯上相鄰的結點物理上也是相鄰的。因此，其存儲密度大，存儲空間利用率高，但插入、刪除運算操作不方便，需移動大量的結點。
13.C。【解析】直接插入排序的基本算法是：當插入第i(i>一1)個對象時，前面的V[o]，V[1]，…，V[i一1]已經排好序，這時，用V[i]的關鍵碼與V[i一1]，[i一2]…的關鍵碼順序進行比較，找到插入位置即將vEi]插入，原來位置上的對象則向後移。由此可知，直接插入排序法的關鍵碼比較次數與對象的.初始排列有關。在本題中，序列已經排好序，所以其i的取值達到了最大，也就是序列中元素的個數，其實根本無需比較和交換，所以這種方法是最佳的。
14.B。【解析】完全二叉樹中除最下面一層外，各層都被結點充滿了，每一層結點個數恰是上一層結點個數的2倍。因此，從一個結點的編號就可推知它的雙親及左、右子樹結點的編號。當i≤n/2時，編號爲i的結點的左子樹的編號是2i，否則結點i沒有左子樹。當i≤(n-1)/2時，編號爲i的結點的右子樹的編號是2i+1，否則結點i沒有右子樹。當i≠1時，編號爲i的結點的雙親是結點i/2。
15.C。【解析】其帶權外部路徑長度爲：2×16+2×21+2×30+3×10+3×12=200。
16.B。【解析】本題考查JDK實用工具的使用。選項A錯誤，是Java語言解釋器，直接從類文件執行Java應用程序字節代碼，可接受class文件並啓動Java虛擬機執 行;選項B正確，是Java語言編譯器，將Java源代碼轉換成字節碼;選項C錯誤，是根據Java源代碼及說明語句生成HTML，文檔;選項D錯誤，是反彙編器，顯示編譯類文件中的可訪問功能和數據，同時顯示字節代碼含義。
17.D。【解析】本題考查Java語言的基本特點。選項A正確，Java最大的特點之一是跨平臺、面向對象;選項B正確，解釋同A;選項C正確，多線程是Java的一個主要特性，它使可執行程序具有同時保持幾個線程執行的能力;選項D錯誤，Java不支持宏定義。
18.B。【解析】Java是一個完全面向對象的語言，利用類把對象的屬性和方法封裝在一起，只對外界提供有限的接口。
19.B。【解析】本題考查File類的基本知識。File類是通過文件名列表來描述一個文件對象的屬性，通過File類提供的方法，可以獲得文件的名稱、長度、所有路徑等信息，還可以改變文件的名稱、刪除文件等。
20.D。【解析】Java語言的標識符是以字母、下畫線和符號$爲首字符的字符串，首字符後面可以跟字母、下畫線、$和數字，且標識符是區分大小寫的，標識符的字符數沒有限制。A選項中含有非法符號”/”，故是錯誤的：B選項是以符號”+”開始的字符串也不符合規則;同理，C選項也是錯誤的。
21.D。【解析】在Java中，常量null、false、true都是小寫的。所以A、B和C選項中的字符串都不是Java的保留字。
22.B。【解析】Java語言中八進制整數爲整型常量中的一種，以0開始，後加數字0～7組成。故只有B選項0144符合要求。
23.B。【解析】由於5和2都是int型，所以語句tln(5/2)的輸出爲2。由於操作數3.0爲double型(Java語言中浮點數的默認值爲double型)，所以結果爲double型，即1.0。
24.D。【解析】Java語言中，char類型被封裝在acter中。
25.A。【解析】本題考查對位運算符和邏輯運算符的理解。位運算符”&”和”|¨用於按位將兩個數進行與和或的操作，兩個操作數可以是整型、字節型、長整型和短整型，但不能是浮點型數據。邏輯運算符&&只能對兩個布爾型的數據進行運算，返回的結果也是布爾型的。
26.D。【解析】本題考查內部類的概念。在一個類的內部嵌套定義的類稱爲內部類，它的類名在定義它的類或程序段中或在表達式內部可以匿名使用，外部使用它時必須給出類的全名，所以選項D說法正確;內部類的類名不允許與它包含的類名相同，選項A說法錯誤;內部類可以使用它所在類的靜態成員變量和實例成員變量，也可以使用它所在類的方法中的局部變量，選項B說法錯誤;內部類不僅可以用abstract修飾定義爲抽象類，也可用private或protected定義，選項C說法錯誤。同時還要注意，內部類可作爲其他類的成員，而且可訪問它所在類的成員，除static內部類外，不能在類中聲明static成員。
27.D。【解析】本題考查字符串數組變量的聲明。選項A和選項B的效果是一樣的，都是用來定義一個字符串數組，但沒有指明數組個數，不滿足題目要求;選項C是一個二維的字符數組，在C語言中，一個二維的字符數組就可以表示一個一維的字符串數組，而在Java中，字符char是基本類型，字符串String則是以對象的形式來表示的;選項D正確，它定義了一個含有l0個元素的字符串數組，如果沒有給字符串數組賦值，則默認爲null。
28.C。【解析】本題考查在Java中接口的實現。接口是一種只含有抽象方法或變量的特殊的抽象類。在類的聲明中用implements子句來表示一個類使用某個接口。選項A在方法內沒有參數值;選項B只是定義了一個類，並沒有實現與A的接口;選項C中使用關鍵字implements實現了該接口，這裏接口中的方法並沒有使用abstract修飾，所以不是抽象的;選項D中extends是用來繼承父類的，而A並不是一個類，不能用extends.
29.D。【解析】本題考查繼承和構造函數的用法。首先要明確對一個類的繼承是指在父類的基礎上構建了一個子類，子類繼承了父類的方法和狀態。題目所給程序段創建的是Extension類的實例，在運行時，從main()函數進入程序，所有調用add()方法的過程將始終和Extension類的add()方法動態綁定。初始值：i=0;創建實例newExtension();先調用父類的默認構造函數Base()，並在父類的默認構造函數中執行add(1)，i=O+1×2，所以i=2，再調用子類的默認構造函數Extension()，子類的默認構造函數中執行add
(2)，i-2+2×2，所以i=6;執行add(8);i=6+8×2，因此，最終i=22，正確答案爲選項D。
30.A。【解析】本題考查事件探聽器的概念。每類事件都有對應的事件探聽器，探聽器是接口，根據動作來定義方法。AWT的構件類中提供註冊和註銷探聽器的方法。註冊探聽器：public void add(listener);註銷探聽器：public void remove(listener)。由此可見，選項A正確。
31.B。【解析】本題考查Java語言中字節類型的概念。在Java語言中，byte是字節類型，用1字節表示;boolean是布爾類型，用true和false表示，它們的表示方法並不一樣，
也不提供它們之間的轉換，選項A錯誤。Java內部用整數來表示char，通常可以在方法調用和其他語句中互換使用char和int，選項B正確。char用2字節表示，byte字節類型
用1字節表示，Java內部也不允許互換使用它們，選項C錯誤。String在Java語言中是一個類，它提供對字符串的一系列操作，而char是Java語言中的一個基本類型，它不是一個類，兩者有本質的區別，故而它們是不能互換使用的，選項D錯誤。需要注意的是，在Java語言中提供的類都是以大寫字母開頭，基本類型都用小寫字母表示。
32.D。【解析】本題考查Applet中HTML標記方法。 URLgetDocumentBase()返回包含Applet的HTML文件的 URL，而不是返回Applet主類的URL，選項A錯誤。 URLgetC0deBase()返回Applet主類的URL，而環是返回 包含Applet的HTML文件的URL，選項B錯誤。String
getParameter(stringname)返回定義在HTML文件的指定參數，如果指定參數在HTML中無說明，該方法將返回"null"，而不是"0"，因此選項C錯誤。
