點擊查看：2015年計算機二級公共基礎知識考點測試題匯總

　　線性表及其順序存儲結構

　　1[單選題]下列敘述中正確的是(　　)。

　　參考答案：A

　　參考解析：順序存儲結構中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次連續(xù)存放的，在鏈式存儲結構中元素之間的關系通過指針來連接，所以不要求存儲空間一定是連續(xù)的;順序存儲結構(或鏈式存儲結構)既可以針對線性結構，也可以針對非線性結構，但像棧、隊列這樣的線性結構一般采用順序存儲結構(但也可以采用鏈式結構)，樹、二叉樹這樣的非線性結構一般采用鏈式存儲結構(但也可以采用順序存儲結構);鏈式存儲結構既可以存儲無序表，也可以存儲有序表，注意，鏈式存儲結構存儲的即使是有序表，也不能進行二分查找;鏈式存儲結構比順序存儲結構要多使用存儲空間，由于鏈式存儲結構中要用額外空間來保存指針。因此本題的正確答案是A。

　　2[單選題]對長度n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)/2的排序方法是(　　)

　　A.快速排序B.冒泡排序C.直接插入排序D.堆排序

　　參考答案：D

　　參考解析：排序技術有：①交換類排序法(冒泡排序法、快速排序法);②插入類排序法(簡單插入排序、希爾排序);③選擇類排序法(簡單選擇排序法、堆排序法)。在最壞情況下，希爾排序需要的比較次數(shù)是O(nl.5)、堆排序需要的比較次數(shù)是O(nlog2n)、其它排序方法需要的比較次數(shù)都是n(n.1)/2。因此本題的正確答案是D。

　　3[單選題]下列敘述中正確的是(　　)

　　A.線性鏈表是線性表的鏈式存儲結構

　　B.棧與隊列是非線性結構

　　C.雙向鏈表是非線性結構

　　D.只有根結點的二叉樹是線性結構

　　參考答案：A

　　參考解析：線性表的鏈式存儲結構稱為線性鏈表;棧、隊列、雙向鏈表都是線性結構;樹、二叉樹(不管它有多少個結點)都是非線性結構。因此本題的正確答案是A。

　　4[單選題]一個棧的初始狀態(tài)為空，現(xiàn)將元素l、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是(　)�！究键c3�！�

　　A.12345ABCDEB.EDCBA54321C.ABCDEl2345D.54321EDCBA

　　參考答案：B

　　參考解析：棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的，所以出棧順序是EDCBA54321。

　　5[單選題]下列關于鏈表結構的敘述正確的是(　　)

　　A.線性鏈表、帶鏈的棧和帶鏈的隊列的結點的結構都是相同的

　　B.雙向鏈表也就是循環(huán)鏈表

　　C.線性鏈表與帶鏈的棧的結點的結構是不同的

　　D.在循環(huán)鏈表中通過任意一個結點可以找到鏈表中其他所有的結點，而在雙向鏈表中做不到這一點

　　參考答案：A

　　6[單選題]在長度為64的有序線性表中進行順序查找，最壞情況下需要比較的次數(shù)為(　　)

　　A.63B.64C.6D.7

　　參考答案：B

　　參考解析：只要是順序查找(不管線性表是有序還是無序)，都是從表頭到表尾逐個比較，若相同則結束查找，否則-直繼續(xù)比較下一個表中元素，直到整個表都遍歷完。對于長度為64的線性表，平均要進行64/2=32次比較，在最壞情況下要進行64次比較。若采用二分(折半)查找，則最壞情況下需要比較的次數(shù)為109264=6次，但要注意采用二分(折半)查找的條件，必須是線性表采用順序存儲結構，而且線性表中的元素要有序，這兩個條件缺-不可。若對線性鏈表進行查找，則不管線性鏈表中的元素是有序還是無序只能采用順序查找。因此本題的正確答案是B。

　　7[單選題]下列對于線性鏈表的描述中正確的是(　　)

　　A.存儲空間不-定是連續(xù)，且各元素的存儲順序是任意的

　　B.存儲空間不-定是連續(xù)，且前件元素-定存儲在后件元素的前面

　　C.存儲空間必須連續(xù)，且前件元素-定存儲在后件元素的前面

　　D.存儲空間必須連續(xù)，且各元素的存儲順序是任意的

　　參考答案：A

　　參考解析：線性鏈表是通過增加一個指針域來把相鄰的數(shù)據(jù)元素鏈接成一個線性序列。線性鏈表的這種結構使得它存儲數(shù)據(jù)的空間可以是離散的，并不像順序表那樣-定要求物理上的連續(xù)空間。因此選項A正確

　　8[填空題]線性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。隊列是一種特殊的線性表，循環(huán)隊列是隊列的(　　)存儲結構。

　　參考解析：順序

　　【分析】在實際應用中，隊列的順序存儲結構一般采用循環(huán)隊列的形式。

　　9[單選題]下列敘述中正確的是(　　)。

　　A.順序存儲結構的存儲一定是連續(xù)的，鏈式存儲結構的存儲空間不一定是連續(xù)的

　　B.順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構

　　C.順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表

　　D.鏈式存儲結構比順序存儲結構節(jié)省存儲空間

　　參考答案：A

　　參考解析：順序存儲方式主要用于線性的數(shù)據(jù)結構，它把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，結點之間的關系由存儲單元的鄰接關系來體現(xiàn)。而鏈式存儲結構的存儲空間不一定是連續(xù)的。

　　10[單選題]數(shù)據(jù)的存儲結構是指(　　)

　　A.存儲在外存中的數(shù)據(jù)

　　B.數(shù)據(jù)所占的存儲空間量

　　C.數(shù)據(jù)在計算機中的順序存儲方式

　　D.數(shù)據(jù)的邏輯結構在計算機中的表示

　　參考答案：D

　　參考解析：數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間的邏輯關系的數(shù)據(jù)結構。數(shù)據(jù)的存儲結構則是數(shù)據(jù)的邏輯結構在計算機中的物理實現(xiàn)，有時也稱作數(shù)據(jù)的物理結構。兩者的區(qū)別是數(shù)據(jù)的邏輯結構只涉及到數(shù)據(jù)之間抽象的數(shù)學關系。存儲結構則涉及到如何在計算機中通過對數(shù)據(jù)的物理存儲進行組織來表達數(shù)據(jù)元素之間的邏輯關系。比如在線性表的順序存儲中是利用物理存儲空間上的連續(xù)性來表達線性表中數(shù)據(jù)的前后件關系;在線性表的鏈式存儲中是通過指針域構成的邏輯鏈條來表達數(shù)據(jù)的前后件關系。-般的，-種數(shù)據(jù)的邏輯結構對應的物理實現(xiàn)，即數(shù)據(jù)的存儲結構不止-種。因此選項D正確。

　　11[單選題]下列敘述中正確的是(　　)

　　A.順序存儲結構的存儲一定是連續(xù)的，鏈式存儲結構的存儲空間不-定是連續(xù)的

　　B.順序存儲結構只針對線性結構，鏈式存儲結構只針對非線性結構

　　C.順序存儲結構能存儲有序表，鏈式存儲結構不能存儲有序表

　　D.鏈式存儲結構比順序存儲結構節(jié)省存儲空間

　　參考答案：A

　　參考解析：順序存儲結構中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次連續(xù)存放的，在鏈式存儲結構中元素之間的關系通過指針來連接，所以不要求存儲空間-定是連續(xù)的;順序存儲結構(或鏈式存儲結構)既可以針對線性結構，也可以針對非線性結構，但像棧、隊列這樣的線性結構-般采用順序存儲結構(但也可以采用鏈式結構)，樹、二叉樹這樣的非線性結構-般采用鏈式存儲結構(但也可以采用順序存儲結構);鏈式存儲結構既可以存儲無序表，也可以存儲有序表，注意，鏈式存儲結構存儲的即使是有序表，也不能進行二分查找;鏈式存儲結構比順序存儲結構要多使用存儲空間，由于鏈式存儲結構中要用額外空間來保存指針。因此本題的正確答案是A。

　　12[單選題]支持子程序調用的數(shù)據(jù)結構是(　　)。【考點3�！�

　　A.棧B.樹C.隊列D.二叉樹

　　參考答案：A

　　參考解析：棧是一種限定在一端進行插入與刪除的線性表。主函數(shù)調用子函數(shù)時，首先會保存主函數(shù)當前的狀態(tài)，然后轉去執(zhí)行子函數(shù)，并把子函數(shù)的運行結果返回到主函數(shù)調用子函數(shù)時的位置，主函數(shù)再接著往下執(zhí)行，這種過程符合棧的特點。所以一般采用棧式存儲方式。

　　13[填空題]在長度為n的順序存儲結構的線性表中，插入(或刪除)一個元素，在平均情況下需要移動表中的________個元素，在最壞情況下需要移動表中的________個元素。

　　參考解析：

　　n/2 n

　　14[單選題]下列詵項中不屬于結構化稗序設計方法的是

　　A.自頂向下B.逐步求精C.模塊化D.可復用

　　參考答案：D

　　參考解析：結構化程序設計方法的主要原則可以概括為自頂向下、逐步求精、模塊化、限制使用GOTO語句�？蓮陀貌皇墙Y構化程序設計方法的主要原則。因此本題的正確答案是D。

　　15[單選題]長度為10的順序表的首地址是從l023開始的，順序表中每個元素的長度為2，在第4個元素前面插入一個元素和刪除第7個元素后，順序表的總長度還是不變。問在執(zhí)行插入和刪除操作前，順序表中第5個元素在執(zhí)行插入和刪除操作后在順序表中的存儲地址是(　　)。

　　參考答案：D

　　參考解析：

　　16[填空題]重復結構對應兩類循環(huán)語句，對先判斷后執(zhí)行循環(huán)體的稱為________型循環(huán)結構，對先執(zhí)行循環(huán)體后判斷的稱為________型循環(huán)結構。

　　參考解析：當【7】直到【分析】本題考查兩類循環(huán)結構，希望考生還能夠識記并辨別它們的流程圖。

　　17[填空題]數(shù)據(jù)結構分為線性結構和非線性結構，帶鏈的隊列屬于(　　)。

　　參考解析：線性

　　18[填空題]對長度為10的線性表進行冒泡排序，最壞情況下需要比較的次數(shù)為(　　)。

　　參考解析：45

　　【分析】假設線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要比較的次數(shù)為n(n一1)/2。因此本題的正確答案是10x(10—1)÷2=45。

　　19[填空題]數(shù)據(jù)結構分為邏輯結構和存儲結構，循環(huán)隊列屬于(　　)結構。

　　參考解析：存儲結構

　　20[填空題]在長度為n的順序存儲結構的線性表中，要在第i(1≦i≦n)個元素之前插入一個新元素，則需要移動表中的(　　)個元素，表的長度變?yōu)?　　);若刪除表中的第i(1≦i≦n)個元素，則需要移動表中的(　　)個元素，表的長度變?yōu)?　　)。

　　參考解析：n一i+1 、n+1 、n—i 、n一1

　　21[填空題]在長度為n的順序存儲結構的線性表中，插入(或刪除)一個元素，在平均情況下需要移動表中的(　　)個元素，在最壞情況下需要移動表中的(　　)個元素。

　　參考解析：n/2、n

　　22[填空題]已知線性表的每個元素占2個字節(jié)，它的第5個元素在內存中的存儲地址是1005，那么它的第2個元素在內存中的存儲地址是(　　)。

　　參考解析：999

　　23[填空題]數(shù)據(jù)獨立性分為邏輯獨立性與物理獨立性。當數(shù)據(jù)的存儲結構改變時，其邏輯結構可以不變，因此，基于邏輯結構的應用程序不必修改，稱為(　　)。

　　參考解析：物理獨立性性

　　【分析】數(shù)據(jù)獨立性一般分為物理獨立性性和邏輯獨立性。物理獨立性一般是指數(shù)據(jù)的物理結構(包括存儲結構、存取方式等)的改變，如存儲設備的更換、物理存儲的更換、存取方式改變等都不影響數(shù)據(jù)庫的邏輯結構，從而不致引起應用程序的改變。邏輯獨立性是指數(shù)據(jù)庫總體邏輯結構的改變，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間聯(lián)系等，不需要相應修改應用程序。

　　相關推薦：

　　2015計算機二級公共基礎知識考前沖刺練試題匯總

　　2015計算機二級公共基礎知識精選選擇題專項練習

　　2015計算機二級《公共基礎知識》精選選擇題90道