一、選擇題(每小題1分，共40小題，共40分)
    1．算法的空間復雜度是指( )。
    A．算法程序的長度
    B．算法程序中的指令條數
    C．算法程序所占的存儲空間
    D．算法執(zhí)行過程中所需要的存儲空間
    2．用鏈表表示線性表的優(yōu)點是( )。
    A．便于隨機存取
    B．花費的存儲空間較順序存儲少
    C．便于插入和刪除操作
    D．數據元素的物理順序與邏輯順序相同
    3．已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為( )。
    A．GEDHFBCA
    B．DGEBHFCA
    C．ABCDEFGH
    D．ACBFEDHG
    4．下列數據結構中，能用二分法進行查找的是( )。
    A．順序存儲的有序線性表
    B．線性鏈表
    C．二叉鏈表
    D．有序線性鏈表
    5．結構化程序設計的3種基本結構是( )。
    A．過程、子程序和分程序
    B．順序、選擇和重復
    C．遞歸、堆棧和隊列
    D．調用、返回和轉移
    6．下列敘述中正確的是( )。
    A．在模塊化程序設計中，一個模塊應該盡量多的包括與其他模塊聯系的信息
    B．在自頂向下、逐步細化的設計過程中，首先應設計解決問題的第一個細節(jié)
    C．在模塊化程序設計中，一個模塊內部的控制結構也要符合結構化原則
    D．在程序設計過程中，不能同時采用結構化程序設計
    方法與模塊化程序設計方法
    7．設計軟件結構是在軟件生命周期的( )。
    A．軟件定義期
    B．軟件開發(fā)期
    C．軟件維護期
    D．以上3個都不是
    8．數據庫技術的根本目標是要解決數據的( )。
    A．存儲問題
    B．共享問題
    C．安全問題
    D．保護問題
    9．設計數據庫的存儲結構屬于( )階段。
    A．需求分析
    B．概念設計
    C．邏輯設計
    D．物理設計
    10．相對于數據庫系統(tǒng)，文件系統(tǒng)的主要缺陷有數據依賴、數據不一致性和( )。
    A．可重用性差
    B．安全性差
    C．非持久性
    D．冗余性
    11．如果要求一個線性表既能較快地查找，又能適應動態(tài)變化的要求，則可采用的方法是( )。
    A．分塊法
    B．順序法
    C．二分法
    D．散列法
    12．順序存儲結構的優(yōu)點是( )。
    A．刪除運算方便
    B．存儲空間利用率高
    C．插入運算方便
    D．可以方便地運用到各種邏輯結構的存儲表中
    13．用下列4種排序方法，對一個已排好序(由小到大)的序列進行由小到大排序時，選擇( )方法。
    A．冒泡排序
    B．直接選擇排序
    C．直接插入排序
    D．歸并排序
    14．按層次次序將一棵有n-個結點的完全二叉樹的所有結點從l～n編號，當i≤n／2時，編號為i的結點的左子樹的編號是( )。
    A．2i-1
    B．2i
    C．2i+1
    D．不確定
    15．對于給出的一組權w={10，12，16，21，30}，通過霍夫曼算法求出的擴充二叉樹的帶權外部路徑長度為( )。
    A．89
    B．189
    C．200
    D．300
    16．JDK中，用( )命令對其源文件進行編譯，生成字節(jié)碼文件。
    A．java．exe
    B．javac．exe
    C．javadoc．exe
    D．javap．exe
    17．以下敘述中不屬于Java語言特點的是( )。
    A．面向對象
    B．可移植性
    C．多線程
    D．宏定義
    18．在Java語言中，封閉是借助于( )實現酊。
    A．對象
    B．類
    C．數組
    D．成員
    19．Java對文件類提供了許多操作方法，能獲得文件對象父路徑名的方法是( )。
    A．getAbsolutePath()
    B．getParentFile()
    C．getAbsoluteFile()
    D．getName()
    20．下列各項中屬于合法標識符的是( )。
    A．myid／2
    B．+void
    C．-5
    D．_vacl
    一、選擇題
    1．D?！窘馕觥克惴ǖ目臻g復雜度，是指執(zhí)行這個算法所需的存儲空間。算法所占用的存儲空間包括算法程序所占用的空間、輸入的初始數據所占用的存儲空間及算法執(zhí)行過程中所需要的額外空間。
    2．C?！窘馕觥繑祿Y構是相互之間存在一種或多種特定關系的數據元素的集合?！标P系”描述的是數據元素之間的邏輯關系，因此又稱數據的邏輯結構。數據的存儲結構是指數據結構(數據的邏輯結構)在計算機中的表示，又稱物理結構。數據的存儲結構有順序存儲結構和鏈式存儲結構兩種。不同存儲結構的數據處理效率不同。由于鏈表采用鏈式存儲結構，元素的物理順序并不連續(xù)，對于插入和刪除無需移動元素，很方便，當查找元素時就需要逐個元素查找，因此查找的時間相對更長。
    3．B?！窘馕觥慷鏄涞谋闅v有3種：前序、中序和后序。后序遍歷首先遍歷左子樹或左子結點，然后遍歷右子樹或右子結點，最后訪問根結點；中序遍歷首先遍歷左子樹或左子結點，然后訪問根結點，最后遍歷右子樹或右子結點；后序遍歷首先訪問根結點，然后遍歷左子樹或左子結點，最后遍歷右子樹或右子結點。本題根據前序遍歷和中序遍歷的
    結果可以得出二叉樹的結構，然后再對其進行后序遍歷，因此答案為選項B。
    4．A。【解析】二分法查找只適用于順序存儲的有序線性表，對于順序存儲的非有序線性表和線性鏈表，都只能采用順序查找。
    5．B。【解析】程序的三種基本控制結構包括：順序、選擇和重復(循環(huán))，這三種結構就足以表達出各種其他形式的結構。
    6．C。【解析】在模塊化程序設計中，模塊之間的聯系可以通過程序的控制結構來實現，在自頂向下、逐步細化的設計過程中，首先要考慮全局目標，而不是細節(jié)。在程序設計中模塊化和結構化可以同時使用，一個模塊的內部結構也要符合結構化設計原則。
    7．B。【解析】設計軟件結構，是在軟件概要設計階段進行的，而概要設計屬于軟件開發(fā)期。
    8．B。【解析】在數據庫系統(tǒng)中，需要對數據進行集中、統(tǒng)一的管理，以達到被多個應用程序共享的目標。
    9．D。【解析】物理設計階段主要解決選擇文件存儲結構和確定文件存取的方法的問題，包括：選擇存儲結構、確定存取方法、選擇存取路徑、確定數據的存放位置。
    10．D。【解析】文件系統(tǒng)所管理的數據文件基本上是分散、相互獨立的。因此相對于數據庫系統(tǒng)，以此為基礎的數據處理存在3個缺點：數據冗余大、數據的不一致性、程序與數據的相互依賴(簡稱為數據依賴)。
    11．A?！窘馕觥糠謮K查找是將表分成若干塊，分塊的原則是數據元素的關鍵字在塊與塊之間是有序的，而塊內元素的關鍵字是無序的。分塊法可以適應動態(tài)變化的要求。其他三種是在順序存儲的一組記錄內進行查找的。
    12．B?！窘馕觥宽樞蚪Y構邏輯上相鄰的結點物理上也是相鄰的。因此，其存儲密度大，存儲空間利用率高，但插入、刪除運算操作不方便，需移動大量的結點。
    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?！窘馕觥科鋷嗤獠柯窂介L度為：2×16+2×21+2×30+3×10+3×12=200。
    16．B。【解析】本題考查JDK實用工具的使用。選項A錯誤，java．exe是Java語言解釋器，直接從類文件執(zhí)行Java應用程序字節(jié)代碼，可接受class文件并啟動Java虛擬機執(zhí) 行；選項B正確，javac．exe是Java語言編譯器，將Java源代碼轉換成字節(jié)碼；選項C錯誤，javadoc．exe是根據Java源代碼及說明語句生成HTML，文檔；選項D錯誤，javap．exe是反匯編器，顯示編譯類文件中的可訪問功能和數據，同時顯示字節(jié)代碼含義。
    17．D?！窘馕觥勘绢}考查Java語言的基本特點。選項A正確，Java的特點之一是跨平臺、面向對象；選項B正確，解釋同A；選項C正確，多線程是Java的一個主要特性，它使可執(zhí)行程序具有同時保持幾個線程執(zhí)行的能力；選項D錯誤，Java不支持宏定義。
    18．B?！窘馕觥縅ava是一個完全面向對象的語言，利用類把對象的屬性和方法封裝在一起，只對外界提供有限的接口。
    19．B?！窘馕觥勘绢}考查File類的基本知識。File類是通過文件名列表來描述一個文件對象的屬性，通過File類提供的方法，可以獲得文件的名稱、長度、所有路徑等信息，還可以改變文件的名稱、刪除文件等。
    20．D?！窘馕觥縅ava語言的標識符是以字母、下畫線和符號$為首字符的字符串，首字符后面可以跟字母、下畫線、$和數字，且標識符是區(qū)分大小寫的，標識符的字符數沒有限制。A選項中含有非法符號”／”，故是錯誤的：B選項是以符號”+”開始的字符串也不符合規(guī)則；同理，C選項也是錯誤的。