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