點擊查看：2015年計算機(jī)二級公共基礎(chǔ)知識考點測試題匯總
線性表及其順序存儲結(jié)構(gòu)
1[單選題]下列敘述中正確的是( )。
參考答案：A
參考解析：順序存儲結(jié)構(gòu)中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次連續(xù)存放的，在鏈?zhǔn)酱鎯Y(jié)構(gòu)中元素之間的關(guān)系通過指針來連接，所以不要求存儲空間一定是連續(xù)的;順序存儲結(jié)構(gòu)(或鏈?zhǔn)酱鎯Y(jié)構(gòu))既可以針對線性結(jié)構(gòu)，也可以針對非線性結(jié)構(gòu)，但像棧、隊列這樣的線性結(jié)構(gòu)一般采用順序存儲結(jié)構(gòu)(但也可以采用鏈?zhǔn)浇Y(jié)構(gòu))，樹、二叉樹這樣的非線性結(jié)構(gòu)一般采用鏈?zhǔn)酱鎯Y(jié)構(gòu)(但也可以采用順序存儲結(jié)構(gòu));鏈?zhǔn)酱鎯Y(jié)構(gòu)既可以存儲無序表，也可以存儲有序表，注意，鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的即使是有序表，也不能進(jìn)行二分查找;鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)要多使用存儲空間，由于鏈?zhǔn)酱鎯Y(jié)構(gòu)中要用額外空間來保存指針。因此本題的正確答案是A。
2[單選題]對長度n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)/2的排序方法是( )
A.快速排序B.冒泡排序C.直接插入排序D.堆排序
參考答案：D
參考解析：排序技術(shù)有：①交換類排序法(冒泡排序法、快速排序法);②插入類排序法(簡單插入排序、希爾排序);③選擇類排序法(簡單選擇排序法、堆排序法)。在最壞情況下，希爾排序需要的比較次數(shù)是O(nl.5)、堆排序需要的比較次數(shù)是O(nlog2n)、其它排序方法需要的比較次數(shù)都是n(n.1)/2。因此本題的正確答案是D。
3[單選題]下列敘述中正確的是( )
A.線性鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)
B.棧與隊列是非線性結(jié)構(gòu)
C.雙向鏈表是非線性結(jié)構(gòu)
D.只有根結(jié)點的二叉樹是線性結(jié)構(gòu)
參考答案：A
參考解析：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表;棧、隊列、雙向鏈表都是線性結(jié)構(gòu);樹、二叉樹(不管它有多少個結(jié)點)都是非線性結(jié)構(gòu)。因此本題的正確答案是A。
4[單選題]一個棧的初始狀態(tài)為空，現(xiàn)將元素l、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是( )�！究键c3�！�
A.12345ABCDEB.EDCBA54321C.ABCDEl2345D.54321EDCBA
參考答案：B
參考解析：棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的，所以出棧順序是EDCBA54321。
5[單選題]下列關(guān)于鏈表結(jié)構(gòu)的敘述正確的是( )
A.線性鏈表、帶鏈的棧和帶鏈的隊列的結(jié)點的結(jié)構(gòu)都是相同的
B.雙向鏈表也就是循環(huán)鏈表
C.線性鏈表與帶鏈的棧的結(jié)點的結(jié)構(gòu)是不同的
D.在循環(huán)鏈表中通過任意一個結(jié)點可以找到鏈表中其他所有的結(jié)點，而在雙向鏈表中做不到這一點
參考答案：A
6[單選題]在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為( )
A.63B.64C.6D.7
參考答案：B
參考解析：只要是順序查找(不管線性表是有序還是無序)，都是從表頭到表尾逐個比較，若相同則結(jié)束查找，否則-直繼續(xù)比較下一個表中元素，直到整個表都遍歷完。對于長度為64的線性表，平均要進(jìn)行64/2=32次比較，在最壞情況下要進(jìn)行64次比較。若采用二分(折半)查找，則最壞情況下需要比較的次數(shù)為109264=6次，但要注意采用二分(折半)查找的條件，必須是線性表采用順序存儲結(jié)構(gòu)，而且線性表中的元素要有序，這兩個條件缺-不可。若對線性鏈表進(jìn)行查找，則不管線性鏈表中的元素是有序還是無序只能采用順序查找。因此本題的正確答案是B。
7[單選題]下列對于線性鏈表的描述中正確的是( )
A.存儲空間不-定是連續(xù)，且各元素的存儲順序是任意的
B.存儲空間不-定是連續(xù)，且前件元素-定存儲在后件元素的前面
C.存儲空間必須連續(xù)，且前件元素-定存儲在后件元素的前面
D.存儲空間必須連續(xù)，且各元素的存儲順序是任意的
參考答案：A
參考解析：線性鏈表是通過增加一個指針域來把相鄰的數(shù)據(jù)元素鏈接成一個線性序列。線性鏈表的這種結(jié)構(gòu)使得它存儲數(shù)據(jù)的空間可以是離散的，并不像順序表那樣-定要求物理上的連續(xù)空間。因此選項A正確
8[填空題]線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊列是一種特殊的線性表，循環(huán)隊列是隊列的( )存儲結(jié)構(gòu)。
參考解析：順序
【分析】在實際應(yīng)用中，隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式。
9[單選題]下列敘述中正確的是( )。
A.順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的
B.順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu)
C.順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表
D.鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間
參考答案：A
參考解析：順序存儲方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，結(jié)點之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。而鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的。
10[單選題]數(shù)據(jù)的存儲結(jié)構(gòu)是指( )
A.存儲在外存中的數(shù)據(jù)
B.數(shù)據(jù)所占的存儲空間量
C.數(shù)據(jù)在計算機(jī)中的順序存儲方式
D.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示
參考答案：D
參考解析：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)則是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的物理實現(xiàn)，有時也稱作數(shù)據(jù)的物理結(jié)構(gòu)。兩者的區(qū)別是數(shù)據(jù)的邏輯結(jié)構(gòu)只涉及到數(shù)據(jù)之間抽象的數(shù)學(xué)關(guān)系。存儲結(jié)構(gòu)則涉及到如何在計算機(jī)中通過對數(shù)據(jù)的物理存儲進(jìn)行組織來表達(dá)數(shù)據(jù)元素之間的邏輯關(guān)系。比如在線性表的順序存儲中是利用物理存儲空間上的連續(xù)性來表達(dá)線性表中數(shù)據(jù)的前后件關(guān)系;在線性表的鏈?zhǔn)酱鎯χ惺峭ㄟ^指針域構(gòu)成的邏輯鏈條來表達(dá)數(shù)據(jù)的前后件關(guān)系。-般的，-種數(shù)據(jù)的邏輯結(jié)構(gòu)對應(yīng)的物理實現(xiàn)，即數(shù)據(jù)的存儲結(jié)構(gòu)不止-種。因此選項D正確。
11[單選題]下列敘述中正確的是( )
A.順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不-定是連續(xù)的
B.順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu)
C.順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表
D.鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間
參考答案：A
參考解析：順序存儲結(jié)構(gòu)中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次連續(xù)存放的，在鏈?zhǔn)酱鎯Y(jié)構(gòu)中元素之間的關(guān)系通過指針來連接，所以不要求存儲空間-定是連續(xù)的;順序存儲結(jié)構(gòu)(或鏈?zhǔn)酱鎯Y(jié)構(gòu))既可以針對線性結(jié)構(gòu)，也可以針對非線性結(jié)構(gòu)，但像棧、隊列這樣的線性結(jié)構(gòu)-般采用順序存儲結(jié)構(gòu)(但也可以采用鏈?zhǔn)浇Y(jié)構(gòu))，樹、二叉樹這樣的非線性結(jié)構(gòu)-般采用鏈?zhǔn)酱鎯Y(jié)構(gòu)(但也可以采用順序存儲結(jié)構(gòu));鏈?zhǔn)酱鎯Y(jié)構(gòu)既可以存儲無序表，也可以存儲有序表，注意，鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的即使是有序表，也不能進(jìn)行二分查找;鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)要多使用存儲空間，由于鏈?zhǔn)酱鎯Y(jié)構(gòu)中要用額外空間來保存指針。因此本題的正確答案是A。
12[單選題]支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是( )�！究键c3棧】
A.棧B.樹C.隊列D.二叉樹
參考答案：A
參考解析：棧是一種限定在一端進(jìn)行插入與刪除的線性表。主函數(shù)調(diào)用子函數(shù)時，首先會保存主函數(shù)當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子函數(shù)，并把子函數(shù)的運行結(jié)果返回到主函數(shù)調(diào)用子函數(shù)時的位置，主函數(shù)再接著往下執(zhí)行，這種過程符合棧的特點。所以一般采用棧式存儲方式。
13[填空題]在長度為n的順序存儲結(jié)構(gòu)的線性表中，插入(或刪除)一個元素，在平均情況下需要移動表中的________個元素，在最壞情況下需要移動表中的________個元素。
參考解析：
n/2 n
14[單選題]下列詵項中不屬于結(jié)構(gòu)化稗序設(shè)計方法的是
A.自頂向下B.逐步求精C.模塊化D.可復(fù)用
參考答案：D
參考解析：結(jié)構(gòu)化程序設(shè)計方法的主要原則可以概括為自頂向下、逐步求精、模塊化、限制使用GOTO語句�？蓮�(fù)用不是結(jié)構(gòu)化程序設(shè)計方法的主要原則。因此本題的正確答案是D。
15[單選題]長度為10的順序表的首地址是從l023開始的，順序表中每個元素的長度為2，在第4個元素前面插入一個元素和刪除第7個元素后，順序表的總長度還是不變。問在執(zhí)行插入和刪除操作前，順序表中第5個元素在執(zhí)行插入和刪除操作后在順序表中的存儲地址是( )。
參考答案：D
參考解析：
16[填空題]重復(fù)結(jié)構(gòu)對應(yīng)兩類循環(huán)語句，對先判斷后執(zhí)行循環(huán)體的稱為________型循環(huán)結(jié)構(gòu)，對先執(zhí)行循環(huán)體后判斷的稱為________型循環(huán)結(jié)構(gòu)。
參考解析：當(dāng)【7】直到【分析】本題考查兩類循環(huán)結(jié)構(gòu)，希望考生還能夠識記并辨別它們的流程圖。
17[填空題]數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于( )。
參考解析：線性
18[填空題]對長度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為( )。
參考解析：45
【分析】假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要比較的次數(shù)為n(n一1)/2。因此本題的正確答案是10x(10—1)÷2=45。
19[填空題]數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊列屬于( )結(jié)構(gòu)。
參考解析：存儲結(jié)構(gòu)
20[填空題]在長度為n的順序存儲結(jié)構(gòu)的線性表中，要在第i(1≦i≦n)個元素之前插入一個新元素，則需要移動表中的( )個元素，表的長度變?yōu)? );若刪除表中的第i(1≦i≦n)個元素，則需要移動表中的( )個元素，表的長度變?yōu)? )。
參考解析：n一i+1 、n+1 、n—i 、n一1
21[填空題]在長度為n的順序存儲結(jié)構(gòu)的線性表中，插入(或刪除)一個元素，在平均情況下需要移動表中的( )個元素，在最壞情況下需要移動表中的( )個元素。
參考解析：n/2、n
22[填空題]已知線性表的每個元素占2個字節(jié)，它的第5個元素在內(nèi)存中的存儲地址是1005，那么它的第2個元素在內(nèi)存中的存儲地址是( )。
參考解析：999
23[填空題]數(shù)據(jù)獨立性分為邏輯獨立性與物理獨立性。當(dāng)數(shù)據(jù)的存儲結(jié)構(gòu)改變時，其邏輯結(jié)構(gòu)可以不變，因此，基于邏輯結(jié)構(gòu)的應(yīng)用程序不必修改，稱為( )。
參考解析：物理獨立性性
【分析】數(shù)據(jù)獨立性一般分為物理獨立性性和邏輯獨立性。物理獨立性一般是指數(shù)據(jù)的物理結(jié)構(gòu)(包括存儲結(jié)構(gòu)、存取方式等)的改變，如存儲設(shè)備的更換、物理存儲的更換、存取方式改變等都不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的改變。邏輯獨立性是指數(shù)據(jù)庫總體邏輯結(jié)構(gòu)的改變，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間聯(lián)系等，不需要相應(yīng)修改應(yīng)用程序。
相關(guān)推薦：
2015計算機(jī)二級公共基礎(chǔ)知識考前沖刺練試題匯總
| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |
