第一篇：2012廣西壯族自治區(qū)JAVA版數(shù)據(jù)結(jié)構(gòu)試題及答案
1、下列序列中，執(zhí)行第一趟快速排序后得到的序列是（A）。A）[d,a,e,d,b]f[h,g] B)[c,e,a,d]f[h,g,b] C)[g,a,e,c,b]f[d,h] D)[a,b,c,d,]f[e,g,h]
2、設(shè)給定問(wèn)題的規(guī)模為變量n，解決該問(wèn)題的算法所需時(shí)間為Tn=O(f(n)),Tn表示式中記號(hào)O表示（A）。
A）一個(gè)數(shù)量級(jí)別 B）一個(gè)平均值 C）一個(gè)最大值 D）一個(gè)均方值
3、（C）在進(jìn)行插入操作時(shí)，常產(chǎn)生假溢出現(xiàn)象。A）順序棧 B）循環(huán)隊(duì)列 C）順序隊(duì)列 D）鏈隊(duì)列
4、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a??11為第一個(gè)元素，其存儲(chǔ)地址為1，每元素占1個(gè)地址空間，則a85的地址為（B）。A）13 B）33 C）18 D）40
5、n個(gè)頂點(diǎn)的圖的最小生成樹(shù)必定（D），是不正確的描述。A）不唯一 B）權(quán)的總和唯一
C）不含回路 D）有n條邊
6、用一維數(shù)組A進(jìn)行順序存儲(chǔ)時(shí)，若起始地址為loc(A1)，元素長(zhǎng)度為c，則A的第i個(gè)數(shù)組單元在存放地址loc(Ai)，等于（B）。A）loc(A1)+i*c B）loc(A1)+(i-1)*c C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c
7、與無(wú)向圖相關(guān)的術(shù)語(yǔ)有（C）。A）強(qiáng)連通圖 B）入度 C）路徑 D）弧
8、鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（A）。
A）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B）只有一部分，存放結(jié)點(diǎn)值
C）只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針
D）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)
9、若采用鄰接矩陣法存儲(chǔ)一個(gè)n個(gè)頂點(diǎn)的無(wú)向圖，則該鄰接矩陣是一個(gè)（D）。A）上三角矩陣 B)稀疏矩陣 C)對(duì)角矩陣 D)對(duì)稱矩陣
10、在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為（C）。
A）top不變 B）top=0 C）top--D）top++
11、棧進(jìn)行插入和刪除操作的特點(diǎn)是（A）。A）LIFO B）FIFO C）FCFS D）HPF
12、與無(wú)向圖相關(guān)的術(shù)語(yǔ)有（C）。A）強(qiáng)連通圖 B）入度 C）路徑 D）弧
13、n個(gè)頂點(diǎn)，e條邊的有向圖的鄰接矩陣中非零元素有（C）個(gè)。A）n B）2e C）e D）n+e
14、已知棧的最大容量為4。若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行,則可能出現(xiàn)的出棧序列為（C）。
A)5，4，3，2，1，6
B)2，3，5，6，1，4 C)3，2，5，4，1，6
D)1，4，6，5，2，3
15、在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為（B）。
A)rear=rear->next;B)front=front->next;C)rear=front->next;
D)front=rear->next;
第二篇：java數(shù)據(jù)結(jié)構(gòu)測(cè)試題及答案解析
Java數(shù)據(jù)結(jié)構(gòu)試題及解析 下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是__A____。
A、順序存儲(chǔ)的有序線性表 B、線性鏈表 C、二叉鏈表 D、有序線性鏈表
解析：二分法查找只適用于順序存儲(chǔ)的有序表。在此所說(shuō)的有序表是指線性表中的元素按值非遞減排列(即從小到大，但允許相鄰元素值相等)。
在軟件設(shè)計(jì)中，不屬于過(guò)程設(shè)計(jì)工具的是__D____。
A、PDL(過(guò)程設(shè)計(jì)語(yǔ)言)B、PAD圖 C、N-S圖 D、DFD圖
解析：軟件設(shè)計(jì)工具包括：程序流程圖、N-S、PAD、HIPO，判定表，PDL(偽碼)。而DFD(數(shù)據(jù)流圖)屬于結(jié)構(gòu)化分析工具。在switch(expression)語(yǔ)句中，expression的數(shù)據(jù)類型不能是__A____。
A、double B、char C、byte D、short
解析：表達(dá)式expression只能返回這個(gè)幾種類型的值：int、byte、short和char。多分支語(yǔ)句把表達(dá)式返回的值依次與每個(gè)case子句中的值相比較，如果遇到匹配的值，則執(zhí)行該case子句后的語(yǔ)句序列。下列敘述中，錯(cuò)誤的是__D____。
A、父類不能替代子類 B、子類能夠替代父類 C、子類繼承父類 D、父類包含子類
通過(guò)繼承實(shí)現(xiàn)代碼復(fù)用：
Java中所有的類都是通過(guò)直接或間接地繼承java.lang.Object類得到的。繼承而得到的類稱為子類，被繼承的類稱為父類。子類不能繼承父類中訪問(wèn)權(quán)限為private的成員變量和方法，子類可以重寫父類的方法，及命名與父類同名的成員變量。
子類通過(guò)隱藏父類的成員變量和重寫父類的方法，把父類的狀態(tài)和行為改變?yōu)樽陨淼臓顟B(tài)和行為。注意：子類中重寫的方法和父類中被重寫的方法要具有相同的名字，相同的參數(shù)表和相同的返回類型，只是函數(shù)體不同。
由于子類繼承了父類所有的屬性(私有的除外)，所以子類對(duì)象可以作為父類對(duì)象使用。程序中凡是使用父類對(duì)象的地方，都可以用子類對(duì)象來(lái)代替。一個(gè)對(duì)象可以通過(guò)引用子類的實(shí)例來(lái)調(diào)用子類的方法。
java運(yùn)行時(shí)系統(tǒng)根據(jù)調(diào)用該方法的實(shí)例，來(lái)決定調(diào)用哪個(gè)方法。對(duì)子類的一個(gè)實(shí)例，如果子類重寫了父類的方法，則運(yùn)行時(shí)系統(tǒng)調(diào)用子類的方法;如果子類繼承了父類的方法(未重寫)，則運(yùn)行時(shí)系統(tǒng)調(diào)用父類的方法。自定義表格類中的model部分應(yīng)實(shí)現(xiàn)的接口是___A___。
A、AbstractTableModel B、JTable C、TableModel D、TableModelable 下列代碼中，將引起編譯錯(cuò)誤的行是__B____。
1)public class Exercise{
2)public static void main(String args[]){
3)float f=0.0;
4)f+=1.0;
5)}
6)}
A、第2行 B、第3行 C、第4行 D、第6行
解析：float定義變量賦值時(shí)，需要在數(shù)值后面加f以標(biāo)識(shí)它為浮點(diǎn)型，讓系統(tǒng)知道該給它精確到多少位。下列關(guān)于Java多線程并發(fā)控制機(jī)制的敘述中，錯(cuò)誤的是___B___。
A、Java中對(duì)共享數(shù)據(jù)操作的并發(fā)控制是采用加鎖技術(shù)
B、線程之間的交互，提倡采用suspend()/resume()方法
C、共享數(shù)據(jù)的訪問(wèn)權(quán)限都必須定義為private
D、Java中沒(méi)有提供檢測(cè)與避免死鎖的專門機(jī)制，但應(yīng)用程序員可以采用某些策略防止死鎖的發(fā)生 解析：
1)Java中對(duì)共享數(shù)據(jù)操作的并發(fā)控制是采用傳統(tǒng)的封鎖技術(shù)。一個(gè)程序中單獨(dú)的、并發(fā)的線程對(duì)同一個(gè)對(duì)象進(jìn)行訪問(wèn)的代碼段，稱為臨界區(qū)。在Java語(yǔ)言中，臨界區(qū)可以是一個(gè)語(yǔ)句塊或是一個(gè)方法，并且用“synchronized”關(guān)鍵字標(biāo)識(shí)。Java平臺(tái)將每個(gè)由synchronized(Object)語(yǔ)句指定的對(duì)象設(shè)置一個(gè)鎖，稱為對(duì)象鎖。
2)共享數(shù)據(jù)的所有訪問(wèn)都必須作為臨界區(qū)，使用“synchronized”進(jìn)行加鎖控制。用“synchronized”保護(hù)的數(shù)據(jù)也必須是私有的，使線程不能直接訪問(wèn)這些數(shù)據(jù)，必須通過(guò)對(duì)象的方法。
3)Java中沒(méi)有檢測(cè)與避免死鎖的專門機(jī)制，因此完全由程序進(jìn)行控制，防止死鎖的發(fā)生。
4)有時(shí)，某個(gè)線程進(jìn)入“synchronized”塊后，共享數(shù)據(jù)的狀態(tài)并不一定滿足線程的需要，它要等待其他線程將共享數(shù)據(jù)改變?yōu)樗枰臓顟B(tài)后才能繼續(xù)執(zhí)行，但由于此時(shí)它占有了該對(duì)象的鎖，其他線程無(wú)法對(duì)共享數(shù)據(jù)進(jìn)行操作，為此Java引入wait()和notify()，這兩個(gè)方法使java.lang.object類的方法，使實(shí)現(xiàn)線程通信的兩個(gè)方法。
下列操作中，不屬于Applet安全限制的是___D___。
A、加載本 B、讀寫本地文件系統(tǒng) C、運(yùn)行本地可執(zhí)行程序 D、與同一個(gè)頁(yè)面中的Applet通信 在進(jìn)行模塊測(cè)試時(shí)，要為每個(gè)被測(cè)試的模塊另外設(shè)計(jì)兩類模塊：驅(qū)動(dòng)模塊和承接模塊(樁模塊)。其中，驅(qū)動(dòng)模塊相當(dāng)于被測(cè)試模塊的主程序，它接收測(cè)試數(shù)據(jù)，并傳給被測(cè)試模塊，輸出實(shí)際測(cè)試結(jié)果。承接模塊通常用于代替被測(cè)試模塊調(diào)用的其他模塊，其作用僅做少量的數(shù)據(jù)操作，是一個(gè)模擬子程序，不必將子模塊的所有功能帶入。
Java語(yǔ)言具有可移植性、高性能、健壯性、安全性和獨(dú)立于體系結(jié)構(gòu)的__跨平臺(tái)____特點(diǎn)。
解析：Java語(yǔ)言是一種跨平臺(tái)，適合于分布式計(jì)算環(huán)境的面向?qū)ο蟮木幊陶Z(yǔ)言。具體來(lái)說(shuō)，它具有如下特性：簡(jiǎn)單性、面向?qū)ο?、分布式、解釋型、可靠、安全、平臺(tái)無(wú)關(guān)、可移植、高性能、多線程、動(dòng)態(tài)性等。在運(yùn)行時(shí)，由Java解釋器自動(dòng)導(dǎo)入，而不用import語(yǔ)句引入的包是__java.lang____。
解析：因?yàn)榘黬ava.lang所包含的類和接口對(duì)所有實(shí)際的Java程序都是必要的，所以，它被自動(dòng)導(dǎo)入所有的程序且它是Java最廣泛使用的包。下列程序的功能是創(chuàng)建了一個(gè)顯示5個(gè)“Hello!”的線程并啟動(dòng)運(yùn)行，請(qǐng)將程序補(bǔ)充完整。
public class ThreadTest extends Thread{
public static void main(String args[]){
ThreadTest t=new __ThreadTest()____;
t.start();}
public void run(){int i=0;
while(true){System.out.println(“Hello!”);
if(i++==4)break;
}
}
解析：ThreadTest繼承java.lang.Thread類，重寫了run()方法，實(shí)現(xiàn)了Java中的線程。ThreadTest t定義了空的線程對(duì)象，下面t.start()啟動(dòng)了這個(gè)線程，因此ThreadTest t=new ______;就應(yīng)該是實(shí)例化該線程對(duì)象，所以空格中應(yīng)填ThreadTest()。
Swing的頂層容器有：JApplet、JWindow、JDialog和__JFrame____。
頂層容器：JFrame、JApplet、JDialog和JWindow共4個(gè)。
中間容器：JPanel、JScrollPane、JSplitPane、JToolBar。
特殊容器：JInternalFrame、JLayeredPane、JRootPane。
基本控件：JButton、JComboBox、JList、JMenu、JSlider、JTextField。
不可編輯信息的構(gòu)件：JLabel、JProgressBar、ToolTip、可編輯信息的構(gòu)件：JColorChooser、JFileChooser、JFileChooser、JTable、JTextArea 所有的這些構(gòu)件的分類都是按功能來(lái)劃分的。14 下列敘述中正確的是___D___。
A、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)
B、數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu)
C、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率
D、一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率
解析：一般來(lái)說(shuō)，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)，常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。
Java的圖形用戶界面的最基本的組成部分就是構(gòu)件(Component)，構(gòu)件是一個(gè)可以以圖形化的方式顯示在屏幕上并能與用戶交互的對(duì)象，但構(gòu)件不能獨(dú)立地顯示出來(lái)，必須將構(gòu)件放在一定的容器中才可以顯示出來(lái)。解析：容器Container是一個(gè)類，因?yàn)槿萜鞅旧硪彩且粋€(gè)構(gòu)件，具有構(gòu)件的所有性質(zhì)，因此繼承之Component類。
下列敘述中，錯(cuò)誤的是__A____。
A、File類能夠存儲(chǔ)文件 B、File類能夠讀寫文件C、File類能夠建立文件D、File類能夠獲取文件目錄信息
解析：文件類File是java.io包中的一個(gè)重要的非流類，它以一種與系統(tǒng)無(wú)關(guān)的方式表示一個(gè)文件對(duì)象的屬性。而目錄在Java中作為一種特殊文件，即文件名的列表，通過(guò)類File所提供的方法，可得到文件或目錄的描述信息(包括名字、路徑、長(zhǎng)度、可讀、可寫等)，也可以生成新文件、目錄、修改文件和目錄，查詢文件屬性，重命名文件或者刪除文件。
下列敘述中，正確的是___C___。
A、Reader是一個(gè)讀取字符文件的接口 B、Reader是一個(gè)讀取數(shù)據(jù)文件的抽象類
C、Reader是一個(gè)讀取字符文件的抽象類 D、Reader是一個(gè)讀取字節(jié)文件的一般類
解析：Java中的流分為兩種，一種是字節(jié)流，另一種是字符流，分別由四個(gè)抽象類來(lái)表示(每種流包括輸入和輸出兩種，所以一共四個(gè))：InputStream，OutputStream，Reader，Writer。Java中其他多種多樣變化的流均是由它們派生出來(lái)的。
在這其中InputStream和OutputStream在早期的Java版本中就已經(jīng)存在了，它們是基于字節(jié)流的，而基于字符流的Reader和Writer是后來(lái)加入作為補(bǔ)充的。在這四個(gè)抽象類中，InputStream和Reader定義了完全相同的接口：
int read()
int read(char cbuf[])
int read(char cbuf[], int offset, int length)
而OutputStream和Writer也是如此：
int write(int c)
int write(char cbuf[])
int write(char cbuf[], int offset, int length)用于輸入壓縮文件格式的ZipInputStream類所屬包是___D___。
A、java.util B、java.io C、java.nio D、java.util.zip
解析：ZipInputStream該對(duì)象用于從ZIP壓縮文件中創(chuàng)建輸入流對(duì)象。
對(duì)象定義結(jié)構(gòu)：java.util.zip.ZipInputStream
靜態(tài)成員變量：CENATT、CENATX、CENCRC……，這些靜態(tài)成員變量用于定義在壓縮過(guò)程中采用的壓縮算法。
構(gòu)造方法：ZipInputStream(InputStream in)應(yīng)用輸入流對(duì)象創(chuàng)建從ZIP文件中讀取數(shù)據(jù)的輸入流對(duì)象。
成員方法：
int available()判斷當(dāng)前入口指定的壓縮原始文件中是否還有未讀數(shù)據(jù)。
void close()關(guān)閉ZIP輸入流對(duì)象。
void closeEntry()關(guān)閉被讀取的ZIP入口，并移動(dòng)到下一壓縮原始文件入口。
protectedZipEntry createZipEntry(String name)利用指定的名稱創(chuàng)建ZipEntry對(duì)象實(shí)例。
ZipEntry getNextEntry()將輸入流對(duì)象移動(dòng)到下一入口對(duì)象。
int read(byte[] b, int off, int len)從當(dāng)前ZipEntry中讀取字節(jié)數(shù)組。
long skip(long n)將輸入流指定的讀取數(shù)據(jù)位置移動(dòng)n個(gè)字節(jié)。
在Swing中用輕量級(jí)的構(gòu)件替代了AWT中的重量級(jí)的構(gòu)件，而且Swing的替代構(gòu)件中都包含有一些其他的特性。與AWT構(gòu)件不同，Swing構(gòu)件不能直接添加到頂層容器中，它必須添加到一個(gè)與Swing頂層容器相關(guān)聯(lián)的內(nèi)容面板(contentPane)上。
查找隨機(jī)文件的記錄時(shí)，應(yīng)使用的方法是___C___。
A、readInt()B、readBytes(int n)C、seek(long l)D、readDouble()
文件操作中經(jīng)常需要的是隨機(jī)訪問(wèn)，Java中的RandomAccessFile類提供隨機(jī)訪問(wèn)文件的功能，其中的seek方法實(shí)現(xiàn)了查找隨機(jī)文件記錄的功能，格式如下：
void seek(long pos);//用于移動(dòng)文件指針到指定的位置 20 下列關(guān)于棧的描述中錯(cuò)誤的是___B___。
A、棧是先進(jìn)后出的線性表 B、棧只能順序存儲(chǔ) C、棧具有記憶作用
D、對(duì)棧的插入與刪除操作中，不需要改變棧底指針 21 對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是___D___。
A、冒泡排序?yàn)閚/2 B、冒泡排序?yàn)閚 C、快速排序?yàn)閚 D、快速排序?yàn)閚(n-1)22 對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為_(kāi)_C____。
A、B、n/2 C、n D、n+1 23 在進(jìn)行順序查找過(guò)程中，如果線性表中的第一個(gè)元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高;但如果被查找的元素是線性表中的最后一個(gè)元素，或者被查找的元素根本就不在線性表中，則為了查找這個(gè)元素需要與線性表中所有的元素進(jìn)行比較，這是順序查找的最壞情況。所以對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下需要比較n次。模塊獨(dú)立性是指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的聯(lián)系最少且接口簡(jiǎn)單。耦合性與內(nèi)聚性是模塊獨(dú)立性的兩個(gè)定性標(biāo)準(zhǔn)，耦合與內(nèi)聚是相互關(guān)聯(lián)的。在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。一般較優(yōu)秀的軟件設(shè)計(jì)，應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨(dú)立性。
計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。軟件具有以下特點(diǎn)：①軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性;②軟件的生產(chǎn)過(guò)程與硬件不同，它沒(méi)有明顯的制作過(guò)程;③軟件在運(yùn)行、使用期間不存在磨損、老化問(wèn)題;④軟件的開(kāi)發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致軟件移植的問(wèn)題;⑤軟件復(fù)雜性高，成本昂貴;⑥軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。
數(shù)據(jù)獨(dú)立性是數(shù)據(jù)庫(kù)技術(shù)的重要特點(diǎn)之一。所謂數(shù)據(jù)獨(dú)立性是指__D____。
A、數(shù)據(jù)與程序獨(dú)立存放 B、不同的數(shù)據(jù)被存放在不同的文件中
C、不同的數(shù)據(jù)只能被對(duì)應(yīng)的應(yīng)用程序所使用 D、以上三種說(shuō)法都不對(duì)
在讀字符文件Employee.dat時(shí)，使用該文件作為參數(shù)的類是___D___。
A、BufferedReader B、DataInputStream C、DataOutputStream D、FileInputStream 下列不是InputStream子類的是__C____。
A、文件輸入流FileInputStream B、對(duì)象輸入流ObjectInputStream
C、字符輸入流CharInputStream D、壓縮文件輸入流ZipInputStream 28 Java中沒(méi)有CharInputStream流。
下列方法中可以用來(lái)創(chuàng)建一個(gè)新線程的是___C___。
A、實(shí)現(xiàn)java.lang.Runnable接口并重寫start()方法
B、實(shí)現(xiàn)java.lang.Runnable接口并重寫run()方法
C、繼承java.lang.Thread類并重寫run()方法
D、繼承java.lang.Thread類并重寫start()方法 下列關(guān)于線程優(yōu)先級(jí)的說(shuō)法中，正確的是__C____。
A、線程的優(yōu)先級(jí)是不能改變的 B、線程的優(yōu)先級(jí)是在創(chuàng)建線程時(shí)設(shè)置的 C、在創(chuàng)建線程后的任何時(shí)候都可以設(shè)置 D、B和C 下列代碼中，將引起一個(gè)編譯錯(cuò)誤的行是__D____。
1)public class Test{
2)int m,n;
3)public Test(){}
4)public Test(int a){m=a;}
5)public static void main(String args[]){
6)Test t1,t2;
7)int j,k;
8)j=0;k=0;
9)t1=new Test();
10)t2=new Test(j,k);
11)}
12)}
A、第3行 B、第5行 C、第6行 D、第10行
閱讀下列代碼后
public class Person{
int arr[]=new int[10];
public static void main(String args[]){
System.out.println(arr[1]);
}
}
正確的說(shuō)法是__A____。
A、編譯時(shí)將產(chǎn)生錯(cuò)誤 B、編譯時(shí)正確，運(yùn)行時(shí)將產(chǎn)生錯(cuò)誤 C、輸出為零 D、輸出為空
32請(qǐng)閱讀下列程序代碼，然后將程序的執(zhí)行結(jié)果補(bǔ)充完整。
程序代碼：
class throwsException
{
static void Proc(int sel)throws ArithmeticException,ArrayIndexOutOfBoundsException
{
System.out.println(“In Situation”+sel);
if(sel==0){
System.out.println(“no Exception caught”);
return;
}
else if(sel==1){
int iArray[]=new int[4];
iArray[1]=3;
}
}
public static void main(String[] args)
{
try{
Proc(0);
Proc(1);
}catch(ArrayIndexOutOfBoundsException e){
System.out.println(“Catch”+e);
}finally{
System.out.println(“in Proc finally”);
}
}
} 執(zhí)行結(jié)果：
In Situation0
no Exception caught
__In Situation1____
in Proc finally
解析：調(diào)用Proc(1)時(shí)，執(zhí)行語(yǔ)句System.out.println(“In Situation”+sel);控制臺(tái)輸出In Situation1。然后在if語(yǔ)句中執(zhí)行sel==1分支，該分支中無(wú)任何輸出語(yǔ)句。
當(dāng)使用Thread t=new Thread(r)創(chuàng)建一個(gè)線程時(shí)，表達(dá)式：r instanceof Thread的值是___false___。
表達(dá)式：r instanceof Thread的語(yǔ)義即“r是否為Thread的實(shí)例(instance)”。再看Thread的構(gòu)造方法(Thread有許多構(gòu)造方法，以下是最典型的構(gòu)造方法，其它構(gòu)造方法都是從下面的構(gòu)造方法中“減掉”一些參數(shù)形成的)：
Thread(ThreadGroup group, Runnable target, String name)
可見(jiàn)，Thread構(gòu)造方法中沒(méi)有類型為Thread的參數(shù)，故r不可能是Thread的實(shí)例
第三篇：數(shù)據(jù)結(jié)構(gòu)試題及答案
數(shù)據(jù)結(jié)構(gòu)試卷
（二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯(cuò)誤的是（）。
(A)線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間
(B)線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(C)線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D)線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)
2．設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（）個(gè)空指針域。
(A)2m-1(B)2m(C)2m+1(D)4m 3．設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（）。
(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹(shù)得到序列為（）。
(A)BADC(B)BCDA(C)CDAB(D)CBDA 5．設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（）條邊。
(A)n(n-1)/2(B)n(n-1)(C)n
2(D)n2-1 6．設(shè)某棵二叉樹(shù)中有2000個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的最小高度為（）。
(A)9(B)10(C)11(D)12 7．設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。
(A)n-1(B)n(C)n+1(D)2n-1 8．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。
(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8
二、填空題(24分)1.1.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問(wèn)題是____________________和__________________________。
2.2.下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語(yǔ)句。
typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”);
else {____________________;_________________;} } 3.3.中序遍歷二叉排序樹(shù)所得到的序列是___________序列（填有序或無(wú)序）。4.4.快速排序的最壞時(shí)間復(fù)雜度為_(kāi)__________，平均時(shí)間復(fù)雜度為_(kāi)_________。5.5.設(shè)某棵二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹(shù)中度數(shù)為2的結(jié)點(diǎn)數(shù)為_(kāi)________；若采用二叉鏈表作為該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則該二叉樹(shù)中共有_______個(gè)空指針域。
6.6.設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=_______。
7.7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為_(kāi)__________________________。
v1??3??2??4v2??1??3v3??1??4??28.8.設(shè)某無(wú)向圖G的鄰接表為v4??1??3，則從頂點(diǎn)V1開(kāi)始的深度優(yōu)先遍歷序列為_(kāi)__________；廣度優(yōu)先遍歷序列為_(kāi)___________。
三、應(yīng)用題(36分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡(jiǎn)單選擇排序和第4趟直接插入排序后的結(jié)果。
2． 2． 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink）。
3． 3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。
4． 4． 設(shè)一棵樹(shù)T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹(shù)的存儲(chǔ)結(jié)構(gòu)并將該樹(shù)轉(zhuǎn)化成對(duì)應(yīng)的二叉樹(shù)。5． 5． 設(shè)有無(wú)向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。
6． 6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程。
數(shù)據(jù)結(jié)構(gòu)試卷
（二）參考答案
一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C
二、填空題
1.1.構(gòu)造一個(gè)好的HASH函數(shù)，確定解決沖突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序
4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4)
三、應(yīng)用題
1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹(shù)略
5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略
數(shù)據(jù)結(jié)構(gòu)試卷
（三）一、選擇題(30分)1．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。
(A)線性結(jié)構(gòu)(B)樹(shù)型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu) 2．下面程序的時(shí)間復(fù)雜為（）
for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（）。
(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；
(C)q=p->next；p->next=q->next；free(q)；
(D)q=p->next；p->data=q->data；free(q)；
4．設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（）個(gè)輔助記錄單元。
(A)1(B)n(C)nlog2n(D)n2
5．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21 6．設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（）。
(A)n，e(B)e，n(C)2n，e(D)n，2e 8.設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（）條邊。
(A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。
(A)快速排序(B)堆排序(C)歸并排序(D)插入排序 10.下列四種排序中（）的空間復(fù)雜度最大。
(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序
二、填空殖(48分，其中最后兩小題各6分)1.1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。
2.2.設(shè)一棵完全二叉樹(shù)中有500個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的深度為_(kāi)_________；若用二叉鏈表作為該完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則共有___________個(gè)空指針域。
3.3.設(shè)輸入序列為1、2、3，則經(jīng)過(guò)棧的作用后可以得到___________種不同的輸出序列。
4.4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的________，第i列上所有元素之和等于頂點(diǎn)i的________。
5.5.設(shè)哈夫曼樹(shù)中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有________個(gè)度數(shù)為1的結(jié)點(diǎn)。6.6.設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為_(kāi)________。
7.7.__________遍歷二叉排序樹(shù)中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列（填先序、中序或后序）。
8.8.設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。
9.9.不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為_(kāi)___________。
10.10.設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從自上到下、從左到右從1開(kāi)始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為_(kāi)___________，右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)__________。11.11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為_(kāi)__________________________。
12.12.設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓?fù)湫蛄袨開(kāi)___________________。
13.13.下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。
struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}
if(_______________________)return(j);else return(-1);} 14.14.下列算法實(shí)現(xiàn)在二叉排序樹(shù)上查找關(guān)鍵值k，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。
typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){
if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;}
數(shù)據(jù)結(jié)構(gòu)試卷
（三）參考答案
一、選擇題
1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，然后將結(jié)點(diǎn)B的值復(fù)制到結(jié)點(diǎn)A中，最后刪除結(jié)點(diǎn)B。
第9小題分析：9快速排序、歸并排序和插入排序必須等到整個(gè)排序結(jié)束后才能夠求出最小的10個(gè)數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時(shí)間復(fù)雜度為O(log2n)。
二、填空題
1.1.順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小題分析：二分查找的過(guò)程可以用一棵二叉樹(shù)來(lái)描述，該二叉樹(shù)稱為二叉判定樹(shù)。在有序表上進(jìn)行二分查找時(shí)的查找長(zhǎng)度不超過(guò)二叉判定樹(shù)的高度1+log2n。
}
數(shù)據(jù)結(jié)構(gòu)試卷
（四）一、選擇題(30分)1．設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有（）個(gè)結(jié)點(diǎn)。
(A)2k-1(B)2k(C)2k-1(D)2k-1 3．設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則該無(wú)向圖中所有頂點(diǎn)的入度之和為（）。
(A)n(B)e(C)2n(D)2e 4．在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。
(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（）條有向邊。
(A)n(B)n-1(C)m(D)m-1 6．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。
(A)3(B)4(C)5(D)8 7．設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（）。
(A)必須判別棧是否為滿(B)必須判別棧是否為空
(C)判別棧元素的類型(D)對(duì)棧不作任何判別 8．下列四種排序中（）的空間復(fù)雜度最大。
(A)快速排序(B)冒泡排序(C)希爾排序(D)堆
9．設(shè)某二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（）。
(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)（）。
(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)
二、填空題(42分)1． 1． 設(shè)有n個(gè)無(wú)序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為_(kāi)_______，快速排序的平均時(shí)間復(fù)雜度為_(kāi)________。
2． 2． 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列為_(kāi)________________________________________________________（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。3． 3． 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹(shù)的高度為_(kāi)___________。4． 4． 深度為k的完全二叉樹(shù)中最少有____________個(gè)結(jié)點(diǎn)。5． 5． 設(shè)初始記錄關(guān)鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個(gè)元素開(kāi)始進(jìn)行篩選。
6． 6． 設(shè)哈夫曼樹(shù)中共有99個(gè)結(jié)點(diǎn)，則該樹(shù)中有_________個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹(shù)中有_____個(gè)空指針域。
7． 7． 設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)________個(gè)隊(duì)列元素；當(dāng)前實(shí)際存儲(chǔ)________________個(gè)隊(duì)列元素（設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針指向當(dāng)前隊(duì)尾元素的位置）。
8． 8． 設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)元素。9． 9． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為_(kāi)_____________________________。
10．10．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_(kāi)_______________________。
11．11．設(shè)某無(wú)向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是______________________。
12．12．設(shè)無(wú)向圖對(duì)應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個(gè)數(shù)_________第i列上非0元素的個(gè)數(shù)（填等于，大于或小于）。
13．13．設(shè)前序遍歷某二叉樹(shù)的序列為ABCD，中序遍歷該二叉樹(shù)的序列為BADC，則后序遍歷該二叉樹(shù)的序列為_(kāi)____________。
14．14．設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語(yǔ)句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時(shí)返回指向關(guān)鍵字的指針，不成功時(shí)返回標(biāo)志0。
typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;i
數(shù)據(jù)結(jié)構(gòu)試卷
（四）參考答案
一、選擇題
1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A
二、填空題
1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s
數(shù)據(jù)結(jié)構(gòu)試卷
（五）一、選擇題(30分)
1．?dāng)?shù)據(jù)的最小單位是（）。
(A)數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量
2．設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（）。
(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個(gè)長(zhǎng)度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（）。
(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（）。
(A)“STRUCTURE”(B)“DATA”
(C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（）。
(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設(shè)一棵m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（）。
(A)Nl+N2+……+Nm
(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm
7．設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（）次。
(A)25(B)10(C)7(D)1 8．設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。
(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設(shè)輸入序列是1、2、3、……、n，經(jīng)過(guò)棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（）。
(A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（）。
(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80
二、填空題(共30分)1.1.設(shè)有一個(gè)順序共享?xiàng)[0：n-1]，其中第一個(gè)棧項(xiàng)指針top1的初值為-1，第二個(gè)棧頂指針top2的初值為n，則判斷共享?xiàng)M的條件是____________________。
2.2.在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是____________________。
3.3.設(shè)有一個(gè)n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽?duì)角線上元素）存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則A[i][j]與A[0][0]之間有_______個(gè)數(shù)據(jù)元素。
4.4.棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為_(kāi)_________表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為_(kāi)________表。
5.5.設(shè)一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF，則該二叉樹(shù)的前序遍歷序列為_(kāi)__________，中序遍歷序列為_(kāi)__________，后序遍歷序列為_(kāi)__________。
6.6.設(shè)一棵完全二叉樹(shù)有128個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為_(kāi)_______，有__________個(gè)葉子結(jié)點(diǎn)。
7.7.設(shè)有向圖G的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣A來(lái)表示，則A中第i行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的________，第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的__________。
8.8.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對(duì)i=1，2，…，n/2而言滿足的條件為_(kāi)______________________________。
9.9.下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++)
if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){
int low=0,mid,high=n-1;
while(low<=high){
________________________________;
if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1;
}
return(0);}
三、應(yīng)用題(24分)
1.1.設(shè)某棵二叉樹(shù)的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹(shù)的的后序遍歷序列。2.2.設(shè)無(wú)向圖G（如右圖所示），給出該圖的最小生成樹(shù)上邊的集合并計(jì)算最小生成樹(shù)各邊上的權(quán)值之和。
3.3.設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時(shí)的平均查找長(zhǎng)度。
4.4.設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計(jì)算出用線性探測(cè)法和鏈地址法作為解決沖突方法的平均查找長(zhǎng)度。
數(shù)據(jù)結(jié)構(gòu)試卷
（五）參考答案
一、選擇題 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C
二、填空題
1.1.top1+1=top2 2.2.可以隨機(jī)訪問(wèn)到任一個(gè)頂點(diǎn)的簡(jiǎn)單鏈表
3.3.i(i+1)/2+j-1 4.4.FILO，F(xiàn)IFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度
8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k
三、應(yīng)用題
1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3
數(shù)據(jù)結(jié)構(gòu)試卷
（六）一、選擇題(30分)1． 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)路徑長(zhǎng)度之和為（）。
(A)20(B)30(C)40(D)45 2．執(zhí)行一趟快速排序能夠得到的序列是（）。
(A)[41，12，34，45，27] 55 [72，63](B)[45，34，12，41] 55 [72，63，27](C)[63，12，34，45，27] 55 [41，72](D)[12，27，45，41] 55 [34，63，72] 3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。
(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序
5．設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)滿足的條件是（）。
(A)空或只有一個(gè)結(jié)點(diǎn)(B)高度等于其結(jié)點(diǎn)數(shù)
(C)任一結(jié)點(diǎn)無(wú)左孩子(D)任一結(jié)點(diǎn)無(wú)右孩子
6．一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（）。
(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序 7．設(shè)某棵三叉樹(shù)中有40個(gè)結(jié)點(diǎn)，則該三叉樹(shù)的最小高度為（）。
(A)3(B)4(C)5(D)6 8．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（）。
21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹(shù)中最少有（）個(gè)結(jié)點(diǎn)。
(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（）。
(A)front->next=s；front=s；(B)s->next=rear；rear=s；
(C)rear->next=s；rear=s；(D)s->next=front；front=s；
12.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.設(shè)某哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有（）個(gè)葉子結(jié)點(diǎn)。
(A)99(B)100(C)101(D)102 14.設(shè)二叉排序樹(shù)上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（）。
(A)第i行非0元素的個(gè)數(shù)之和(B)第i列非0元素的個(gè)數(shù)之和
(C)第i行0元素的個(gè)數(shù)之和(D)第i列0元素的個(gè)數(shù)之和
二、判斷題(20分)1．調(diào)用一次深度優(yōu)先遍歷可以訪問(wèn)到圖中的所有頂點(diǎn)。（）
2．分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。（）3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4．滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。（）
5．設(shè)一棵二叉樹(shù)的先序序列和后序序列，則能夠唯一確定出該二叉樹(shù)的形狀。（）6．層次遍歷初始堆可以得到一個(gè)有序的序列。（）
7．設(shè)一棵樹(shù)T可以轉(zhuǎn)化成二叉樹(shù)BT，則二叉樹(shù)BT中一定沒(méi)有右子樹(shù)。（）8．線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（）
9．中序遍歷二叉排序樹(shù)可以得到一個(gè)有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（）
三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時(shí)間復(fù)雜度為_(kāi)________。
2．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的新結(jié)點(diǎn)X，則進(jìn)行插入操作的語(yǔ)句序列為_(kāi)_________________________（設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext）。3．設(shè)有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓?fù)渑判蛐蛄衉_________。4．設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖中每個(gè)頂點(diǎn)的度數(shù)最多是_________。5．設(shè)二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹(shù)中總共有_______個(gè)結(jié)點(diǎn)數(shù)。
6．設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為_(kāi)____________________。
7．設(shè)二叉樹(shù)中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_____________________________________________。8．簡(jiǎn)單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為_(kāi)__________。
9．快速排序算法的空間復(fù)雜度平均情況下為_(kāi)_________，最壞的情況下為_(kāi)_________。10.散列表中解決沖突的兩種方法是_____________和_____________。
數(shù)據(jù)結(jié)構(gòu)試卷
（六）參考答案
一、選擇題 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B
二、判斷題
1．錯(cuò) 2．對(duì) 3．對(duì) 4．對(duì) 5．錯(cuò) 6．錯(cuò) 7．對(duì) 8．錯(cuò) 9．對(duì) 10．對(duì)
三、填空題
1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.開(kāi)放定址法，鏈地址法
數(shù)據(jù)結(jié)構(gòu)試卷
（七）一、選擇題(30分)1．設(shè)某無(wú)向圖有n個(gè)頂點(diǎn)，則該無(wú)向圖的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。
(A)2n(B)n(C)n/2(D)n(n-1)2．設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹(shù)上有（）條邊。
(A)n(B)n-1(C)2n(D)2n-1 3．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。
(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。
(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷
5．設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（）。
(A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（）。
(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．設(shè)某棵二叉樹(shù)的高度為10，則該二叉樹(shù)上葉子結(jié)點(diǎn)最多有（）。
(A)20(B)256(C)512(D)1024 9．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（）。
(A)1(B)2(C)3(D)4 10.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（）。
(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next;
三、填空題(30分)1.1.設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_(kāi)________=p；s->right=p->right；__________=s； p->right->left=s；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right）。2.2.設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有________條有向條；設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中共有________條無(wú)向邊。
3.3.設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個(gè)元素開(kāi)始進(jìn)行篩選。
4.4.解決散列表沖突的兩種方法是________________和__________________。
5.5.設(shè)一棵三叉樹(shù)中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹(shù)中度數(shù)為3的結(jié)點(diǎn)數(shù)有______個(gè)。
6.6.高度為h的完全二叉樹(shù)中最少有________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。7.7.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。
8.8.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡(jiǎn)單選擇排序結(jié)束后的結(jié)果的是__________________________________。
9.9.設(shè)一棵二叉樹(shù)的前序序列為ABC，則有______________種不同的二叉樹(shù)可以得到這種序列。
10.10.下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。
struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){
int j=t;struct record x=r[s];i=s;
while(i while(i while(____________________)i=i+1;if(i } _________________;} 數(shù)據(jù)結(jié)構(gòu)試卷 （七）一、選擇題 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B 三、填空題 1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.開(kāi)放定址法，鏈地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i 5．B 10．D 數(shù)據(jù)結(jié)構(gòu)試卷 （八）一、選擇題(30分)1.1.字符串的長(zhǎng)度是指（）。 (A)串中不同字符的個(gè)數(shù)(B)串中不同字母的個(gè)數(shù) (C)串中所含字符的個(gè)數(shù)(D)串中不同數(shù)字的個(gè)數(shù) 2.2.建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為（） (A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個(gè)字符串相等的充要條件是（）。 (A)兩個(gè)字符串的長(zhǎng)度相等(B)兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等 (C)同時(shí)具備(A)和(B)兩個(gè)條件(D)以上答案都不對(duì) 4.4.設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（）。 (A)99(B)97(C)91(D)93 5.5.在二叉排序樹(shù)中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)?)。 (A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.7.設(shè)一棵完全二叉樹(shù)中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為（）。 (A)8(B)7(C)6(D)5 8.8.設(shè)一棵三叉樹(shù)中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（）個(gè)度數(shù)為0的結(jié)點(diǎn)。 (A)5(B)6(C)7(D)8 9.9.設(shè)無(wú)向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（）。 (A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.隊(duì)列是一種（）的線性表。 (A)先進(jìn)先出(B)先進(jìn)后出(C)只能插入(D)只能刪除 三、填空題(30分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_(kāi)____________________________。 2． 2． 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列：s->next=p->next;_________________。4． 4． 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。 5． 5． 設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_(kāi)_________。 6． 6． 完全二叉樹(shù)中第5層上最少有__________個(gè)結(jié)點(diǎn)，最多有_________個(gè)結(jié)點(diǎn)。7． 7． 設(shè)有向圖中不存在有向邊 8． 8． 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_(kāi)____________________________。 9． 9． 設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹(shù)上有___________條邊。10． 10． 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。 數(shù)據(jù)結(jié)構(gòu)試卷 （八）參考答案 一、選擇題 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A 三、填空題 1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50 一、單項(xiàng)選擇題 （B）1.計(jì)算機(jī)算法必須具備輸入、輸出和 等5個(gè)特性。A)可行性、可移植性和可擴(kuò)充性 B)可行性、確定性和有窮性 C)確定性、有窮性和穩(wěn)定性 D)易讀性、穩(wěn)定性和安全性 （C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)； A)存儲(chǔ) B)物理 C)邏輯 D)物理和存儲(chǔ) （C）3.算法分析的目的是： A)找出數(shù)據(jù)結(jié)構(gòu)的合理性 B)研究算法中的輸入和輸出的關(guān)系 C)分析算法的效率以求改進(jìn) D)分析算法的易懂性和文檔性 （A）4.算法分析的兩個(gè)主要方面是： A)空間復(fù)雜性和時(shí)間復(fù)雜性 B)正確性和簡(jiǎn)明性 C)可讀性和文檔性 D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 （C）5.計(jì)算機(jī)算法指的是： A)計(jì)算方法 B)排序方法 C)解決問(wèn)題的有限運(yùn)算序列 D)調(diào)度方法 6．?dāng)?shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（A）和（B）以及它們之間的相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的（C），設(shè)計(jì)出相應(yīng)的（D），從而確保經(jīng)過(guò)這些運(yùn)算后所得到的新結(jié)構(gòu)是（E）結(jié)構(gòu)類型。供選擇的答案 A.B: 1.理想結(jié)構(gòu) 2.抽象結(jié)構(gòu) 3.物理結(jié)構(gòu) 4邏輯結(jié)構(gòu) C.D.E: 1.運(yùn)算 2.算法 3.結(jié)構(gòu) 4.規(guī)則 5.現(xiàn)在的 6.原來(lái)的 解答：34126 7.（A）是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中被計(jì)算機(jī)程序加工處理的符號(hào)的結(jié)合。（B）是數(shù)據(jù)的基本單位，即數(shù)據(jù)結(jié)合中的個(gè)體。有時(shí)一個(gè)（B）由若干個(gè)（C）組成，在這種情況下，稱（B）為記錄。（C）是數(shù)據(jù)的最小單位。（D）是具有相同特性的數(shù)據(jù)元素的集合。（E）是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的結(jié)合。 被計(jì)算機(jī)加工的數(shù)據(jù)元素不是孤立無(wú)關(guān)的，它們彼此之間一般存在著某種聯(lián)系，通常將數(shù)據(jù)元素的這種聯(lián)系關(guān)系稱為（G）。算法的計(jì)算量和問(wèn)題規(guī)模的聯(lián)系用（H）表示。供選擇的答案： A-F: 1.數(shù)據(jù)元素 2.符號(hào) 3.記錄 4.文件 5.數(shù)據(jù) 6.數(shù)據(jù)項(xiàng) 7.數(shù)據(jù)對(duì)象 8.關(guān)鍵字 9.數(shù)據(jù)結(jié)構(gòu) G: 1.規(guī)則 2.集合 3.結(jié)構(gòu) 4.運(yùn)算 H: 1.現(xiàn)實(shí)性 2.難度 3．復(fù)雜性 4.效率 解答：5167933 二、判斷題 1, 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 解答：錯(cuò)，因?yàn)閿?shù)據(jù)元素是數(shù)據(jù)的基本單位，通常它是由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)才是數(shù)據(jù)的最小單位。 2, 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的結(jié)合。解答：正確 3, 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映像（或表示）分別稱為存儲(chǔ)結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。解答：正確 4, 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。 解答：錯(cuò)，因?yàn)閿?shù)據(jù)元素才是數(shù)據(jù)的基本單位 5, 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)之間的邏輯關(guān)系，是用戶按使用需要而建立的。解答：正確 6, 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。解答：正確 三、簡(jiǎn)答題 1、簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。解答： ● 數(shù)據(jù)：指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息載體。 ● 數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素有時(shí)可以由若干數(shù)據(jù)項(xiàng)組成?！駭?shù)據(jù)項(xiàng)是不可分割的最小單位。 ● 數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。● 邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。 ● 存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 ● 線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。 ● 非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)組、廣義表、樹(shù)和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。 2、按增長(zhǎng)率由小至大的順序排列下列各函數(shù)： 2100,(3/2)n，(2/3)n，nn ,n0.5 , n!，2n，lgn ,nlgn, n(3/2)解答： 常見(jiàn)的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列,依次為:常數(shù)階0(1)、對(duì)數(shù)階0(log2n)、線性階0(n)、線性對(duì)數(shù)階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)。 先將題中的函數(shù)分成如下幾類： 常數(shù)階：2100 對(duì)數(shù)階：lgn K次方階：n0.5、n(3/2) 指數(shù)階(按指數(shù)由小到大排)：nlgn、(3/2)n、2n、n!、nn 注意：(2/3)^n由于底數(shù)小于1，所以是一個(gè)遞減函數(shù)，其數(shù)量級(jí)應(yīng)小于常數(shù)階。根據(jù)以上分析按增長(zhǎng)率由小至大的順序可排列如下： (2/3)n < 2100 < lgn < n0.5 < n(3/2)< nlgn <(3/2)n < 2n < n!< nn 3、試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算三個(gè)方面的內(nèi)容。解答：略 4、常用的存儲(chǔ)表示方法有哪幾種? 解答：順序和鏈?zhǔn)?，省?00字 5、設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行，其執(zhí)行時(shí)間分別為100n2和2n,要使前者快于后者，n至少要多大? 解答： 6、算法的時(shí)間復(fù)雜度僅與問(wèn)題的規(guī)模相關(guān)嗎? 解答：是 第一章 作業(yè) 1.任何計(jì)算機(jī)系統(tǒng)的主存可以看作是一個(gè)一維數(shù)組，多維數(shù)組實(shí)際存儲(chǔ)仍是一組連續(xù)單元。請(qǐng)從數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的角度分析? 答：通過(guò)一個(gè)下標(biāo)計(jì)算公式將二維數(shù)組的下標(biāo)(i，j)映成一維數(shù)組的下標(biāo)。例圖b，下標(biāo)=4×(J—l)十I 2.選擇解決某種問(wèn)題的最佳數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)是什么? 1）算法所需要的時(shí)間； ①程序運(yùn)行時(shí)所需輸入的數(shù)據(jù)總量； ②對(duì)源程序進(jìn)行編譯所需的時(shí)間； ③計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間； ④程序中的指令重復(fù)執(zhí)行的次數(shù)（數(shù)據(jù)結(jié)構(gòu)中討論算法時(shí)的重點(diǎn)）2）所需的存儲(chǔ)空間量。 3.有一疊撲克脾，在計(jì)算機(jī)中存儲(chǔ)這一疊撲克牌的內(nèi)容(信息)答：用一個(gè)結(jié)點(diǎn)表示一張牌，每張撲克牌的內(nèi)容包括牌的正反面（0、1）、花色（梅花 1、方塊 2、紅心 3、黑桃4）、點(diǎn)數(shù)、名稱、下一張牌 邏輯結(jié)構(gòu)是線性表；存儲(chǔ)結(jié)構(gòu)可以用鏈表或者順序表表示 I=1執(zhí)行n次 4、語(yǔ)句S的執(zhí)行次數(shù)(B) I=2執(zhí)行n-1次 （1）for(i=1;i<=n-1;i++) I=n-1執(zhí)行2次 for(j=n;j>=i;j--)n+(n-1)+………..2 S;(A)n(n+2)/2(B) (n-1)(n+2)/2 (C) n(n+1)/2(D) (n-1)(n+2)(2)I=0; (A) Do{ J=I;Do{ S; J++; }while(j<=n);I++; }while(i<=n);(A)（n+2）(n+1)/2(B) n(n-1)/2 (C) n!(D) n2 5、計(jì)算下面程序的時(shí)間復(fù)雜度（1）for(i=1;i<=m;i++) （C） for(j=1;j<=n;j++) A[i][j]=i*j;(A) O(m2)(B) O(n2) (C) O(m*n)(D) O(m+n) （2）I=0; （A） s=0;while(s<=n){ I++;S+=I;} (3)語(yǔ)句S的時(shí)間復(fù)雜度為O(1)，(D)for(i=1;i<=n-1;i++) for(j=n;j>=i;j--) S;(A)O(n2/2)(B) O((n-1)(n+2)/2) (C) O(n2+n)(D)O(n2) 同題4（1） S=1+2+3。。。。X=n X為執(zhí)行次數(shù) I=0，j 0~n，執(zhí)行n+1次 I=1，j 1~n，執(zhí)行n次 I=n，j n~n，執(zhí)行1次(n+1)+………..1 x(x?1)?n2x2?x?2n?0x??1?1?8n2(A) O(n)(B)O(2n) (C) O(n)(D) O(n2) 6、寫出下面程序的時(shí)間復(fù)雜度（1）for(i=1;i<=n,i++) for(j=1;j<=i,j++)for(k=1;k<=j,k++)x+=delta; 1+（1+2）+（1+2+3）…..(1+2+….n) 答：O(n3) (2)i=1;j=0;while(i+j<=n){ if(i>j)j++;else i++; } 答：O(n) 把（i+j）看成整體，每次遞增1，頻率n 1、串的邏輯結(jié)構(gòu)與（D）的邏輯結(jié)構(gòu)不相同。A）線性表 B）棧 C）隊(duì)列 D）集合 2、廣義表head(((a,b),(c,d)))的運(yùn)算結(jié)果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)） 3、鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（A）。 A）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B）只有一部分，存放結(jié)點(diǎn)值 C）只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針 D）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù) 4、設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為（A）。 A）p->next=p->next->next;B）p=p->next;C）p=p->next->next;D）p->next=p; 5、在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為（C）。 A）top不變 B）top=0 C）top--D）top++ 6、數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容是（D）。 A）數(shù)據(jù)的邏輯結(jié)構(gòu) B）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) C）建立在相應(yīng)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)上的算法 D）包括以上三個(gè)方面 7、向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（D）。A)hs->next=s; B)s->next=hs->next;hs->next=s;C)s->next=hs;hs=s;D)s->next=hs;hs=hs->next; 8、設(shè)一數(shù)列的順序?yàn)?，2，3，4，5，6，通過(guò)棧結(jié)構(gòu)不可能排成的順序數(shù)列為（B）。A）3，2，5，6，4，1 B）1，5，4，6，2，3 C）2，4，3，5，1，6 D）4，5，3，6，2，1 9、廣義表head(((a,b),(c,d)))的運(yùn)算結(jié)果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)） 10、若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)是(B)。A）9 B）11 C）15 D）不能確定 11、在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為（B）。A)rear=rear->next;B)front=front->next;C)rear=front->next; D)front=rear->next; 12、n個(gè)頂點(diǎn)的圖的最小生成樹(shù)必定（D），是不正確的描述。A）不唯一 B）權(quán)的總和唯一 C）不含回路 D）有n條邊 13、串的邏輯結(jié)構(gòu)與（D）的邏輯結(jié)構(gòu)不同。A）線性表 B）棧 C）隊(duì)列 D）樹(shù)第四篇：數(shù)據(jù)結(jié)構(gòu)(Java)復(fù)習(xí)題及答案 1緒論
第五篇：2013臺(tái)灣省數(shù)據(jù)結(jié)構(gòu)試題及答案（推薦）
點(diǎn)擊咨詢 