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