第一篇：java數(shù)據(jù)結(jié)構(gòu)測試題及答案解析

Java數(shù)據(jù)結(jié)構(gòu)試題及解析 下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進行查找的是__A____。

A、順序存儲的有序線性表 B、線性鏈表 C、二叉鏈表 D、有序線性鏈表

解析：二分法查找只適用于順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列(即從小到大，但允許相鄰元素值相等)。

在軟件設計中，不屬于過程設計工具的是__D____。

A、PDL(過程設計語言)B、PAD圖 C、N-S圖 D、DFD圖

解析：軟件設計工具包括：程序流程圖、N-S、PAD、HIPO，判定表，PDL(偽碼)。而DFD(數(shù)據(jù)流圖)屬于結(jié)構(gòu)化分析工具。在switch(expression)語句中，expression的數(shù)據(jù)類型不能是__A____。

A、double B、char C、byte D、short

解析：表達式expression只能返回這個幾種類型的值：int、byte、short和char。多分支語句把表達式返回的值依次與每個case子句中的值相比較，如果遇到匹配的值，則執(zhí)行該case子句后的語句序列。下列敘述中，錯誤的是__D____。

A、父類不能替代子類 B、子類能夠替代父類 C、子類繼承父類 D、父類包含子類

通過繼承實現(xiàn)代碼復用：

Java中所有的類都是通過直接或間接地繼承java.lang.Object類得到的。繼承而得到的類稱為子類，被繼承的類稱為父類。子類不能繼承父類中訪問權(quán)限為private的成員變量和方法，子類可以重寫父類的方法，及命名與父類同名的成員變量。

子類通過隱藏父類的成員變量和重寫父類的方法，把父類的狀態(tài)和行為改變?yōu)樽陨淼臓顟B(tài)和行為。注意：子類中重寫的方法和父類中被重寫的方法要具有相同的名字，相同的參數(shù)表和相同的返回類型，只是函數(shù)體不同。

由于子類繼承了父類所有的屬性(私有的除外)，所以子類對象可以作為父類對象使用。程序中凡是使用父類對象的地方，都可以用子類對象來代替。一個對象可以通過引用子類的實例來調(diào)用子類的方法。

java運行時系統(tǒng)根據(jù)調(diào)用該方法的實例，來決定調(diào)用哪個方法。對子類的一個實例，如果子類重寫了父類的方法，則運行時系統(tǒng)調(diào)用子類的方法;如果子類繼承了父類的方法(未重寫)，則運行時系統(tǒng)調(diào)用父類的方法。自定義表格類中的model部分應實現(xiàn)的接口是___A___。

A、AbstractTableModel B、JTable C、TableModel D、TableModelable 下列代碼中，將引起編譯錯誤的行是__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ù)值后面加f以標識它為浮點型，讓系統(tǒng)知道該給它精確到多少位。下列關于Java多線程并發(fā)控制機制的敘述中，錯誤的是___B___。

A、Java中對共享數(shù)據(jù)操作的并發(fā)控制是采用加鎖技術

B、線程之間的交互，提倡采用suspend()/resume()方法

C、共享數(shù)據(jù)的訪問權(quán)限都必須定義為private

D、Java中沒有提供檢測與避免死鎖的專門機制，但應用程序員可以采用某些策略防止死鎖的發(fā)生 解析：

1)Java中對共享數(shù)據(jù)操作的并發(fā)控制是采用傳統(tǒng)的封鎖技術。一個程序中單獨的、并發(fā)的線程對同一個對象進行訪問的代碼段，稱為臨界區(qū)。在Java語言中，臨界區(qū)可以是一個語句塊或是一個方法，并且用“synchronized”關鍵字標識。Java平臺將每個由synchronized(Object)語句指定的對象設置一個鎖，稱為對象鎖。

2)共享數(shù)據(jù)的所有訪問都必須作為臨界區(qū)，使用“synchronized”進行加鎖控制。用“synchronized”保護的數(shù)據(jù)也必須是私有的，使線程不能直接訪問這些數(shù)據(jù)，必須通過對象的方法。

3)Java中沒有檢測與避免死鎖的專門機制，因此完全由程序進行控制，防止死鎖的發(fā)生。

4)有時，某個線程進入“synchronized”塊后，共享數(shù)據(jù)的狀態(tài)并不一定滿足線程的需要，它要等待其他線程將共享數(shù)據(jù)改變?yōu)樗枰臓顟B(tài)后才能繼續(xù)執(zhí)行，但由于此時它占有了該對象的鎖，其他線程無法對共享數(shù)據(jù)進行操作，為此Java引入wait()和notify()，這兩個方法使java.lang.object類的方法，使實現(xiàn)線程通信的兩個方法。

下列操作中，不屬于Applet安全限制的是___D___。

A、加載本 B、讀寫本地文件系統(tǒng) C、運行本地可執(zhí)行程序 D、與同一個頁面中的Applet通信 在進行模塊測試時，要為每個被測試的模塊另外設計兩類模塊：驅(qū)動模塊和承接模塊(樁模塊)。其中，驅(qū)動模塊相當于被測試模塊的主程序，它接收測試數(shù)據(jù)，并傳給被測試模塊，輸出實際測試結(jié)果。承接模塊通常用于代替被測試模塊調(diào)用的其他模塊，其作用僅做少量的數(shù)據(jù)操作，是一個模擬子程序，不必將子模塊的所有功能帶入。

Java語言具有可移植性、高性能、健壯性、安全性和獨立于體系結(jié)構(gòu)的__跨平臺____特點。

解析：Java語言是一種跨平臺，適合于分布式計算環(huán)境的面向?qū)ο蟮木幊陶Z言。具體來說，它具有如下特性：簡單性、面向?qū)ο蟆⒎植际?、解釋型、可靠、安全、平臺無關、可移植、高性能、多線程、動態(tài)性等。在運行時，由Java解釋器自動導入，而不用import語句引入的包是__java.lang____。

解析：因為包java.lang所包含的類和接口對所有實際的Java程序都是必要的，所以，它被自動導入所有的程序且它是Java最廣泛使用的包。下列程序的功能是創(chuàng)建了一個顯示5個“Hello!”的線程并啟動運行，請將程序補充完整。

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()方法，實現(xiàn)了Java中的線程。ThreadTest t定義了空的線程對象，下面t.start()啟動了這個線程，因此ThreadTest t=new ______;就應該是實例化該線程對象，所以空格中應填ThreadTest()。

Swing的頂層容器有：JApplet、JWindow、JDialog和__JFrame____。

頂層容器：JFrame、JApplet、JDialog和JWindow共4個。

中間容器：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)件的分類都是按功能來劃分的。14 下列敘述中正確的是___D___。

A、一個邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲結(jié)構(gòu)

B、數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲結(jié)構(gòu)屬于非線性結(jié)構(gòu)

C、一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)不影響數(shù)據(jù)處理的效率

D、一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率

解析：一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。

Java的圖形用戶界面的最基本的組成部分就是構(gòu)件(Component)，構(gòu)件是一個可以以圖形化的方式顯示在屏幕上并能與用戶交互的對象，但構(gòu)件不能獨立地顯示出來，必須將構(gòu)件放在一定的容器中才可以顯示出來。解析：容器Container是一個類，因為容器本身也是一個構(gòu)件，具有構(gòu)件的所有性質(zhì)，因此繼承之Component類。

下列敘述中，錯誤的是__A____。

A、File類能夠存儲文件 B、File類能夠讀寫文件C、File類能夠建立文件D、File類能夠獲取文件目錄信息

解析：文件類File是java.io包中的一個重要的非流類，它以一種與系統(tǒng)無關的方式表示一個文件對象的屬性。而目錄在Java中作為一種特殊文件，即文件名的列表，通過類File所提供的方法，可得到文件或目錄的描述信息(包括名字、路徑、長度、可讀、可寫等)，也可以生成新文件、目錄、修改文件和目錄，查詢文件屬性，重命名文件或者刪除文件。

下列敘述中，正確的是___C___。

A、Reader是一個讀取字符文件的接口 B、Reader是一個讀取數(shù)據(jù)文件的抽象類

C、Reader是一個讀取字符文件的抽象類 D、Reader是一個讀取字節(jié)文件的一般類

解析：Java中的流分為兩種，一種是字節(jié)流，另一種是字符流，分別由四個抽象類來表示(每種流包括輸入和輸出兩種，所以一共四個)：InputStream，OutputStream，Reader，Writer。Java中其他多種多樣變化的流均是由它們派生出來的。

在這其中InputStream和OutputStream在早期的Java版本中就已經(jīng)存在了，它們是基于字節(jié)流的，而基于字符流的Reader和Writer是后來加入作為補充的。在這四個抽象類中，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該對象用于從ZIP壓縮文件中創(chuàng)建輸入流對象。

對象定義結(jié)構(gòu)：java.util.zip.ZipInputStream

靜態(tài)成員變量：CENATT、CENATX、CENCRC……，這些靜態(tài)成員變量用于定義在壓縮過程中采用的壓縮算法。

構(gòu)造方法：ZipInputStream(InputStream in)應用輸入流對象創(chuàng)建從ZIP文件中讀取數(shù)據(jù)的輸入流對象。

成員方法：

int available()判斷當前入口指定的壓縮原始文件中是否還有未讀數(shù)據(jù)。

void close()關閉ZIP輸入流對象。

void closeEntry()關閉被讀取的ZIP入口，并移動到下一壓縮原始文件入口。

protectedZipEntry createZipEntry(String name)利用指定的名稱創(chuàng)建ZipEntry對象實例。

ZipEntry getNextEntry()將輸入流對象移動到下一入口對象。

int read(byte[] b, int off, int len)從當前ZipEntry中讀取字節(jié)數(shù)組。

long skip(long n)將輸入流指定的讀取數(shù)據(jù)位置移動n個字節(jié)。

在Swing中用輕量級的構(gòu)件替代了AWT中的重量級的構(gòu)件，而且Swing的替代構(gòu)件中都包含有一些其他的特性。與AWT構(gòu)件不同，Swing構(gòu)件不能直接添加到頂層容器中，它必須添加到一個與Swing頂層容器相關聯(lián)的內(nèi)容面板(contentPane)上。

查找隨機文件的記錄時，應使用的方法是___C___。

A、readInt()B、readBytes(int n)C、seek(long l)D、readDouble()

文件操作中經(jīng)常需要的是隨機訪問，Java中的RandomAccessFile類提供隨機訪問文件的功能，其中的seek方法實現(xiàn)了查找隨機文件記錄的功能，格式如下：

void seek(long pos);//用于移動文件指針到指定的位置 20 下列關于棧的描述中錯誤的是___B___。

A、棧是先進后出的線性表 B、棧只能順序存儲 C、棧具有記憶作用

D、對棧的插入與刪除操作中，不需要改變棧底指針 21 對于長度為n的線性表，在最壞情況下，下列各排序法所對應的比較次數(shù)中正確的是___D___。

A、冒泡排序為n/2 B、冒泡排序為n C、快速排序為n D、快速排序為n(n-1)22 對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為__C____。

A、B、n/2 C、n D、n+1 23 在進行順序查找過程中，如果線性表中的第一個元素就是被查找元素，則只需做一次比較就查找成功，查找效率最高;但如果被查找的元素是線性表中的最后一個元素，或者被查找的元素根本就不在線性表中，則為了查找這個元素需要與線性表中所有的元素進行比較，這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找，在最壞情況下需要比較n次。模塊獨立性是指每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他模塊的聯(lián)系最少且接口簡單。耦合性與內(nèi)聚性是模塊獨立性的兩個定性標準，耦合與內(nèi)聚是相互關聯(lián)的。在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強，則耦合性越弱。一般較優(yōu)秀的軟件設計，應盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有利于提高模塊的獨立性。

計算機軟件是計算機系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關文檔的完整集合。軟件具有以下特點：①軟件是一種邏輯實體，而不是物理實體，具有抽象性;②軟件的生產(chǎn)過程與硬件不同，它沒有明顯的制作過程;③軟件在運行、使用期間不存在磨損、老化問題;④軟件的開發(fā)、運行對計算機系統(tǒng)具有依賴性，受計算機系統(tǒng)的限制，這導致軟件移植的問題;⑤軟件復雜性高，成本昂貴;⑥軟件開發(fā)涉及諸多的社會因素。

數(shù)據(jù)獨立性是數(shù)據(jù)庫技術的重要特點之一。所謂數(shù)據(jù)獨立性是指__D____。

A、數(shù)據(jù)與程序獨立存放 B、不同的數(shù)據(jù)被存放在不同的文件中

C、不同的數(shù)據(jù)只能被對應的應用程序所使用 D、以上三種說法都不對

在讀字符文件Employee.dat時，使用該文件作為參數(shù)的類是___D___。

A、BufferedReader B、DataInputStream C、DataOutputStream D、FileInputStream 下列不是InputStream子類的是__C____。

A、文件輸入流FileInputStream B、對象輸入流ObjectInputStream

C、字符輸入流CharInputStream D、壓縮文件輸入流ZipInputStream 28 Java中沒有CharInputStream流。

下列方法中可以用來創(chuàng)建一個新線程的是___C___。

A、實現(xiàn)java.lang.Runnable接口并重寫start()方法

B、實現(xiàn)java.lang.Runnable接口并重寫run()方法

C、繼承java.lang.Thread類并重寫run()方法

D、繼承java.lang.Thread類并重寫start()方法 下列關于線程優(yōu)先級的說法中，正確的是__C____。

A、線程的優(yōu)先級是不能改變的 B、線程的優(yōu)先級是在創(chuàng)建線程時設置的 C、在創(chuàng)建線程后的任何時候都可以設置 D、B和C 下列代碼中，將引起一個編譯錯誤的行是__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]);

}

}

正確的說法是__A____。

A、編譯時將產(chǎn)生錯誤 B、編譯時正確，運行時將產(chǎn)生錯誤 C、輸出為零 D、輸出為空

32請閱讀下列程序代碼，然后將程序的執(zhí)行結(jié)果補充完整。

程序代碼：

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)時，執(zhí)行語句System.out.println(“In Situation”+sel);控制臺輸出In Situation1。然后在if語句中執(zhí)行sel==1分支，該分支中無任何輸出語句。

當使用Thread t=new Thread(r)創(chuàng)建一個線程時，表達式：r instanceof Thread的值是___false___。

表達式：r instanceof Thread的語義即“r是否為Thread的實例(instance)”。再看Thread的構(gòu)造方法(Thread有許多構(gòu)造方法，以下是最典型的構(gòu)造方法，其它構(gòu)造方法都是從下面的構(gòu)造方法中“減掉”一些參數(shù)形成的)：

Thread(ThreadGroup group, Runnable target, String name)

可見，Thread構(gòu)造方法中沒有類型為Thread的參數(shù)，故r不可能是Thread的實例

第二篇：數(shù)據(jù)結(jié)構(gòu)(Java)復習題及答案 1緒論

一、單項選擇題

（B）1.計算機算法必須具備輸入、輸出和 等5個特性。A)可行性、可移植性和可擴充性 B)可行性、確定性和有窮性 C)確定性、有窮性和穩(wěn)定性 D)易讀性、穩(wěn)定性和安全性

（C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù)的 結(jié)構(gòu)； A)存儲 B)物理 C)邏輯 D)物理和存儲

（C）3.算法分析的目的是：

A)找出數(shù)據(jù)結(jié)構(gòu)的合理性 B)研究算法中的輸入和輸出的關系 C)分析算法的效率以求改進 D)分析算法的易懂性和文檔性

（A）4.算法分析的兩個主要方面是：

A)空間復雜性和時間復雜性 B)正確性和簡明性 C)可讀性和文檔性 D)數(shù)據(jù)復雜性和程序復雜性

（C）5.計算機算法指的是：

A)計算方法 B)排序方法 C)解決問題的有限運算序列 D)調(diào)度方法

6．數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（A）和（B）以及它們之間的相互關系，并對這種結(jié)構(gòu)定義相應的（C），設計出相應的（D），從而確保經(jīng)過這些運算后所得到的新結(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.運算 2.算法 3.結(jié)構(gòu) 4.規(guī)則 5.現(xiàn)在的 6.原來的 解答：34126

7.（A）是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中被計算機程序加工處理的符號的結(jié)合。（B）是數(shù)據(jù)的基本單位，即數(shù)據(jù)結(jié)合中的個體。有時一個（B）由若干個（C）組成，在這種情況下，稱（B）為記錄。（C）是數(shù)據(jù)的最小單位。（D）是具有相同特性的數(shù)據(jù)元素的集合。（E）是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的結(jié)合。

被計算機加工的數(shù)據(jù)元素不是孤立無關的，它們彼此之間一般存在著某種聯(lián)系，通常將數(shù)據(jù)元素的這種聯(lián)系關系稱為（G）。算法的計算量和問題規(guī)模的聯(lián)系用（H）表示。供選擇的答案：

A-F: 1.數(shù)據(jù)元素 2.符號 3.記錄 4.文件 5.數(shù)據(jù) 6.數(shù)據(jù)項 7.數(shù)據(jù)對象 8.關鍵字 9.數(shù)據(jù)結(jié)構(gòu)

G: 1.規(guī)則 2.集合 3.結(jié)構(gòu) 4.運算 H: 1.現(xiàn)實性 2.難度 3．復雜性 4.效率 解答：5167933

二、判斷題

1, 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。

解答：錯，因為數(shù)據(jù)元素是數(shù)據(jù)的基本單位，通常它是由若干個數(shù)據(jù)項組成，數(shù)據(jù)項才是數(shù)據(jù)的最小單位。

2, 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的結(jié)合。解答：正確

3, 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像（或表示）分別稱為存儲結(jié)構(gòu)、結(jié)點、數(shù)據(jù)域。解答：正確

4, 數(shù)據(jù)項是數(shù)據(jù)的基本單位。

解答：錯，因為數(shù)據(jù)元素才是數(shù)據(jù)的基本單位

5, 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)之間的邏輯關系，是用戶按使用需要而建立的。解答：正確

6, 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式。解答：正確

三、簡答題

1、簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。解答：

● 數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體。

● 數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、頂點、記錄。數(shù)據(jù)元素有時可以由若干數(shù)據(jù)項組成?！駭?shù)據(jù)項是不可分割的最小單位。

● 數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。一般包括三個方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算?！?邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關系。

● 存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。

● 線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都有且只有一個直接前趨和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。棧、隊列、串等都是線性結(jié)構(gòu)。

● 非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個結(jié)點可能有多個直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。

2、按增長率由小至大的順序排列下列各函數(shù)：

2100,(3/2)n，(2/3)n，nn ,n0.5 , n!，2n，lgn ,nlgn, n(3/2)解答：

常見的時間復雜度按數(shù)量級遞增排列,依次為:常數(shù)階0(1)、對數(shù)階0(log2n)、線性階0(n)、線性對數(shù)階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)。

先將題中的函數(shù)分成如下幾類： 常數(shù)階：2100 對數(shù)階：lgn K次方階：n0.5、n(3/2)

指數(shù)階(按指數(shù)由小到大排)：nlgn、(3/2)n、2n、n!、nn

注意：(2/3)^n由于底數(shù)小于1，所以是一個遞減函數(shù)，其數(shù)量級應小于常數(shù)階。根據(jù)以上分析按增長率由小至大的順序可排列如下：

(2/3)n < 2100 < lgn < n0.5 < n(3/2)< nlgn <(3/2)n < 2n < n!< nn

3、試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容。解答：略

4、常用的存儲表示方法有哪幾種? 解答：順序和鏈式，省略200字

5、設有兩個算法在同一機器上運行，其執(zhí)行時間分別為100n2和2n,要使前者快于后者，n至少要多大? 解答：

6、算法的時間復雜度僅與問題的規(guī)模相關嗎? 解答：是

第一章 作業(yè)

1.任何計算機系統(tǒng)的主存可以看作是一個一維數(shù)組，多維數(shù)組實際存儲仍是一組連續(xù)單元。請從數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的角度分析? 答：通過一個下標計算公式將二維數(shù)組的下標(i，j)映成一維數(shù)組的下標。例圖b，下標=4×(J—l)十I

2.選擇解決某種問題的最佳數(shù)據(jù)結(jié)構(gòu)的標準是什么? 1）算法所需要的時間；

①程序運行時所需輸入的數(shù)據(jù)總量； ②對源程序進行編譯所需的時間； ③計算機執(zhí)行每條指令所需的時間；

④程序中的指令重復執(zhí)行的次數(shù)（數(shù)據(jù)結(jié)構(gòu)中討論算法時的重點）2）所需的存儲空間量。

3.有一疊撲克脾，在計算機中存儲這一疊撲克牌的內(nèi)容(信息)答：用一個結(jié)點表示一張牌，每張撲克牌的內(nèi)容包括牌的正反面（0、1）、花色（梅花

1、方塊

2、紅心

3、黑桃4）、點數(shù)、名稱、下一張牌 邏輯結(jié)構(gòu)是線性表；存儲結(jié)構(gòu)可以用鏈表或者順序表表示

I=1執(zhí)行n次

4、語句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、計算下面程序的時間復雜度（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)語句S的時間復雜度為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、寫出下面程序的時間復雜度（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

第三篇：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、設給定問題的規(guī)模為變量n，解決該問題的算法所需時間為Tn=O(f(n)),Tn表示式中記號O表示（A）。

A）一個數(shù)量級別 B）一個平均值 C）一個最大值 D）一個均方值

3、（C）在進行插入操作時，常產(chǎn)生假溢出現(xiàn)象。A）順序棧 B）循環(huán)隊列 C）順序隊列 D）鏈隊列

4、設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a??11為第一個元素，其存儲地址為1，每元素占1個地址空間，則a85的地址為（B）。A）13 B）33 C）18 D）40

5、n個頂點的圖的最小生成樹必定（D），是不正確的描述。A）不唯一 B）權(quán)的總和唯一

C）不含回路 D）有n條邊

6、用一維數(shù)組A進行順序存儲時，若起始地址為loc(A1)，元素長度為c，則A的第i個數(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、與無向圖相關的術語有（C）。A）強連通圖 B）入度 C）路徑 D）弧

8、鏈式存儲的存儲結(jié)構(gòu)所占存儲空間（A）。

A）分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關系的指針 B）只有一部分，存放結(jié)點值

C）只有一部分，存儲表示結(jié)點間關系的指針

D）分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)

9、若采用鄰接矩陣法存儲一個n個頂點的無向圖，則該鄰接矩陣是一個（D）。A）上三角矩陣 B)稀疏矩陣 C)對角矩陣 D)對稱矩陣

10、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（C）。

A）top不變 B）top=0 C）top--D）top++

11、棧進行插入和刪除操作的特點是（A）。A）LIFO B）FIFO C）FCFS D）HPF

12、與無向圖相關的術語有（C）。A）強連通圖 B）入度 C）路徑 D）弧

13、n個頂點，e條邊的有向圖的鄰接矩陣中非零元素有（C）個。A）n B）2e C）e D）n+e

14、已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行,則可能出現(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、在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為（B）。

A)rear=rear->next;B)front=front->next;C)rear=front->next;

D)front=rear->next;

第四篇：JAVA數(shù)據(jù)結(jié)構(gòu)存儲剖析

JAVA數(shù)據(jù)結(jié)構(gòu)存儲剖析

實用舉例：

1:堆棧(stack)

方法的參數(shù)值

public void sun(int a , int b)

//調(diào)用方法是在棧內(nèi)存中為參數(shù)分配存儲空間，方法結(jié)束自動釋放。

局部變量

public static void main(String[] args){int a = 5;}

//在方法中的局部變量，存儲在棧內(nèi)存中，方法結(jié)束時候，釋放內(nèi)存

引用變量

Person p = new Person(“zhaoyue”, 22);

//調(diào)用構(gòu)造方法的時候，“形參”先在堆棧中開辟內(nèi)存，存放“實參”，再把“實參”的//一份拷貝傳入對象之中。此時，“實參”的拷貝存放在堆(heap)中，構(gòu)造方法結(jié)束，//堆棧中的內(nèi)存釋放。

堆棧的存儲要領：壓棧，出棧，自動清除！

2：堆(heap)

成員變量

public class Person{ String name;int age;}

// New 的時候存儲在堆中。

new得到的對象

Person p = new Person(“zhaoyue”, 22);

// New 的時候存儲在堆中。

3：數(shù)據(jù)區(qū)(Data segment)

3.1：靜態(tài)存儲(static storage)

靜態(tài)變量

public static int a = 5;

//JVM運行時首先為其開辟空間，位置不變,程序運行結(jié)束時空間釋放。并且在運行時只加載一次。

靜態(tài)方法

public static void run(){print(“hello”);}

//JVM運行時首先為其開辟空間，位置不變,程序運行結(jié)束時空間釋放。并且在運行時只加載一次。

3.2地址池（address pool）

非new的字符串

String s = “hello world”;

3.3常量存儲（constant storage）

常量

public final int a = 5;

4：Code segment(代碼區(qū))

4.1：Code segment

存放代碼

4.2：方法區(qū)（method area）

成員方法

Public void run(){System.out.println(“I’m run!”);}

//類裝載的時候存儲在方法區(qū),初始時被隱藏，實例化對象時被激活。

具體解釋：

在java中有6中存取機制:

1： 寄存器(register)

2： 堆棧(stack)

3： 堆(heap)

4： 靜態(tài)存儲(static storage)

5： 常量存儲(constant storage)

6： 非RAM存儲寄存器(register)：這是最快的存儲區(qū)，因為它位于不同于其他存儲區(qū)的地方——處理器內(nèi)部。但是寄存器的數(shù)量極其有限，所以寄存器由編譯器根據(jù)需求進行分配。你不能直接控制，也不能在程序中感覺到寄存器存在的任何跡象。堆棧(stack)：位于通用RAM中，但通過它的“堆棧指針”可以從處理器哪里獲得支持。堆棧指針若向下移動，則分配新的內(nèi)存；若向上移動，則釋放那些內(nèi)存。這是一種快速有效的分配存儲方法，僅次于寄存器。創(chuàng)建程序時候，JAVA編譯器必須知道存儲在堆棧內(nèi)所有數(shù)據(jù)的確切大小和生命周期，因為它必須生成相應的代碼，以便上下移動堆棧指針。這一約束限制了程序的靈活性，所以雖然某些JAVA數(shù)據(jù)存儲在堆棧中——特別是對象引用，但是JAVA對象不存儲其中。堆(heap)：一種通用性的內(nèi)存池（也存在于RAM中），用于存放所有的JAVA對象。堆不同于堆棧的好處是：編譯器不需要知道要從堆里分配多少存儲區(qū)域，也不必知道存儲的數(shù)據(jù)在堆里存活多長時間。因此，在堆里分配存儲有很大的靈活性。當你需要創(chuàng)建一個對象的時候，只需要new寫一行簡單的代碼，當執(zhí)行這行代碼時，會自動在堆里進行存儲分配。當然，為這種靈活性必須要付出相應的代碼。用堆進行存儲分配比用堆棧進行存儲存儲需要更多的時

間。

4: 靜態(tài)存儲(static storage)：這里的“靜態(tài)”是指“在固定的位置”。靜態(tài)存儲里存放程序運行時一直存在的數(shù)據(jù)。你可用關鍵字static來標識一個對象的特定元素是靜態(tài)的，但JAVA對象本身從來不會存放在靜態(tài)存儲空間里。

5: 常量存儲(constant storage)：常量值通常直接存放在程序代碼內(nèi)部，這樣做是安全的，因為它們永遠不會被改變。有時，在嵌入式系統(tǒng)中，常量本身會和其他部分分割離開，所以在這種情況下，可以選擇將其放在ROM中

6: 非RAM存儲：如果數(shù)據(jù)完全存活于程序之外，那么它可以不受程序的任何控制，在程序沒有運行時也可以存在。

速度：

就速度來說，有如下關系：

寄存器 > 堆棧 > 堆 > 其他

關系：

然后我主要要說下堆與堆棧的關系：

堆：堆是heap，是所謂的動態(tài)內(nèi)存，其中的內(nèi)存在不需要時可以回收，以分配給新的內(nèi)存請求，其內(nèi)存中的數(shù)據(jù)是無序的，即先分配的和隨后分配的內(nèi)存并沒有什么必然的位置關系，釋放時也可以沒有先后順序。一般由使用者自由分配，在C語言中malloc分配的就是堆，需要手動釋放。

堆棧:就是stack。實際上是只有一個出入口的隊列，即后進先出(frist in , last out)，先分配的內(nèi)存必定后釋放。一般由，由系統(tǒng)自動分配，存放函數(shù)的參數(shù)值，局部變量等，自動清除。

還有，堆是全局的，堆棧是每個函數(shù)進入的時候分一小塊，函數(shù)返回的時候就釋放了，靜態(tài)和全局變量，new得到的變量，都放在堆中，局部變量放在堆棧中，所以函數(shù)返回，局部變量就全沒了。

JAVA中的基本類型，其實需要特殊對待。因為，在JAVA中，通過new創(chuàng)建的對象存儲在“堆”中，所以用new 創(chuàng)建一個小的、簡單的變量，如基本類型等，往往不是很有效。因此，在JAVA中，對于這些類型，采用了與C、C++相同的方法。也就是說，不用new 來創(chuàng)建，而是創(chuàng)建一個并非是“引用”的“自動”變量。這個變量擁有它的“值”，并置于堆棧中，因此更高效。

再說一說類的實例方法！

類的實例方法在內(nèi)存中是只有一份,不過肯定不會是第一個對象中,如果是第一個對象的話,那么當?shù)谝粋€對象被銷毀的時候,那么后面的對象就永遠無法調(diào)用了。

類的實例方法存在一個專門的區(qū)叫方法區(qū)（method area）,事實上類剛裝載的時候就被裝載好了,不過它們在“睡眠”,只是這些方法必須當有對象產(chǎn)生的時候才會“蘇醒”.(比如,一個輸出類的成員變量的方法,如果連對象都沒有,何來的輸出成員變量).所以,方法在裝載的時候就有了,但是不可用,因為它沒有指象任何一個對象。

而靜態(tài)的又不一樣了,靜態(tài)的東西存在靜態(tài)存儲(static storage)區(qū),他們和類是一個等級的，就是說只要類被裝載,它們就可以直接用.(用類名來調(diào)用).他們不依賴與任何對象,所以也不能輸出任何對象的成員屬性.(除非成員屬性也是靜態(tài)的).每個對象在new的時候都會在堆區(qū)中開辟內(nèi)存,用來保存對象的屬性和方法.(實際上方法保存的只是方法區(qū)的引用,如果保存的是方法本身,那么試想一下,有多少個對象就得有多少個方法,那么又和第一點中“實例方法在內(nèi)存中只有一份拷貝”相矛盾了。另外我補充一點，在父類的引用指向子類對象的時候，父類可以調(diào)用子類從父類繼承的屬性和方法，子類覆寫父類的屬性和方法，在動態(tài)綁定（也就是多態(tài)）時，子類對象有一個方法區(qū)得引用，動態(tài)new的時候這個引用指向子類的方法，從而實現(xiàn)了父類可以調(diào)用子類覆寫父類的方法。這也是動態(tài)綁定得名的原因。)

如果您認真看完這篇文章，估計java中內(nèi)存方面肯定會有所幫助，這篇文章是我總結(jié)歸納出來的，并非完全自己寫的。有什么不對的地方，歡迎批評指正。

第五篇：java部分數(shù)據(jù)結(jié)構(gòu)總結(jié)

package datastructtest;

import java.io.File;

import java.io.FileReader;

import java.io.FileWriter;

import java.io.IOException;

import java.util.LinkedList;

import java.util.Scanner;

import javax.swing.JFrame;

public class Testbase {

public static void main(String[] args)throws IOException{

//100之內(nèi)被3或7整除的數(shù)的個數(shù)

//int m=0,n=0;

//for(int i=0;i<100;i++){

//if(i%3==0){

//m++;

//}

//if(i%7==0){

//n++;

//}

//}

//System.out.println(“m=”+m+“ ；”);

//System.out.println(“n=”+n+“ ；”);

//1~100之間的整數(shù)累加和，并顯示每個整數(shù)和當前累加和的對應關系 //int sum=0;

//for(int i=1;i<=100;i++){

//

//System.out.print(“i=”+i+“,sum=”+sum);

//sum+=i;

//System.out.println(“;i+sum=”+sum);

//}

//計算30的階乘

//int m=jiecheng(30);

//System.out.println(m);

//直接插入排序

//int[] test={64,5,7,89,6,24};

//int n=test.length;

//insertSort(test);

//for(int i=0;i

//System.out.print(test[i]+“,”);

//}

//希爾排序

//int[] test={65,34,25,87,12,38,56,46,14,77,92,33};//int n=test.length;

//int d[]={6,3,1};//每次循環(huán)用到的增量值

//int numOfD=d.length;//共進行幾次循環(huán)

//shellSort(test,d,numOfD);

//for(int i=0;i

//System.out.print(test[i]+“,”);

// }

//直接選擇排序

//int[] test={65,34,25,87,12,38,56,46,14,77,92,33};

//int n=test.length;

//

//selectSort(test);

//for(int i=0;i

//System.out.print(test[i]+“,”);

// }

////字符串逆轉(zhuǎn)

//char[]a={'a','f','g','h','j'};

//char[]b=reverse1(a);

//for(int i=0;i

//System.out.print(b[i]+“,”);

//}

//Scanner類的應用和split的使用

//System.out.println(“請輸入帶逗號的字符：”);

//Scanner sc=new Scanner(System.in);

//

//while(sc.hasNext()){

//StringBuffer str=new StringBuffer();

//str=str.append(sc.next());

////System.out.println(str);

//String st=str.toString();

//String[] a=st.split(“,”);

//System.out.println(“字符串被逗號分割之后：”);

//for(int i=0;i

//System.out.println(a[i]);

//}

//}

//寫文件和讀文件復制文件aa到bb

//FileReader filein=new FileReader(new File(“d://aa.txt”));//此句會產(chǎn)生異常

//FileWriter fileout=new FileWriter(new File(“d://bb.txt”));//int c;

//while((c=filein.read())!=-1){

//fileout.write(c);

//}

//filein.close();

//fileout.close();

//

}

private static int jiecheng(int n){

if(n==1)

return 1;

else

return n*jiecheng(n-1);

}

//棧

private LinkedList list=new LinkedList();

public void push(Object v){

list.addFirst(v);

}

public Object top(){

return list.getFirst();

}

public Object pop(){

return list.removeFirst();

}

//直接插入排序

public static void insertSort(int[] a){

int i,j,temp;

int n=a.length;

for(i=0;i

temp=a[i+1];

j=i;

while(j>-1&&temp<=a[j]){

a[j+1]=a[j];

j--;

}

a[j+1]=temp;

}

//for(i=0;i

//temp=a[i+1];

//// j=i;

//while(i>-1&&temp<=a[i]){

//a[i+1]=a[i];

//i--;

//}

//a[i+1]=temp;

//}

}

//希爾排序

public static void shellSort(int[]a,int[]d,int numOfD){

int i,j,k,m,span;

int temp;

int n=a.length;

for(m=0;m

span=d[m];//取本次的增量值

for(k=0;k

for(i=k;i

temp=a[i+span];

j=i;

while(j>-1&&temp<=a[j]){

a[j+span]=a[j];

j=j-span;

}

a[j+span]=temp;

}

}

}

}

//直接選擇排序

public static void selectSort(int[]a){

int i,j,small;

int temp;

int n=a.length;

for(i=0;i

small=i;//設第i個數(shù)據(jù)元素最小

for(j=i+1;j

if(a[j]

if(small!=i){

temp=a[small];

for(j=small;j>i;j--)//把該區(qū)段尚未排序元素依次后移

a[j]=a[j-1];

a[i]=temp;//插入找出的最小元素

}

}

}

public static char[] reverse1(char[]a){

int n=a.length;

char[]b=new char[n];

for(int i=0;i

b[n-i-1]=a[i];

}

return b;

}

}