點(diǎn)擊查看：2015年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考點(diǎn)測(cè)試題匯總

　　線性鏈表

　　1[單選題]對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是(　　)

　　A.冒泡排序?yàn)閚/2

　　B.冒泡排序?yàn)閚

　　C.快速排序?yàn)閚

　　D.快速排序?yàn)閚(n-1)/2

　　參考答案：D

　　參考解析：對(duì)于長(zhǎng)度為n的線性表，在最壞情況下，冒泡排序需要進(jìn)行的比較次數(shù)是n(n—1)/2，快速排序需要進(jìn)行的比較次數(shù)是n(n-1)/2，簡(jiǎn)單插入排序需要進(jìn)行的比較次數(shù)是n(n—1)/2，希爾排序需要進(jìn)行的比較次數(shù)是0(n1 5)，簡(jiǎn)單選擇排序需要進(jìn)行的比較次數(shù)是n(n-1)/2，堆排序需要進(jìn)行的比較次數(shù)是0(nl092n)。因此選項(xiàng)D正確。

　　2[單選題]在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要較的次數(shù)是(　　)。

　　參考答案：C

　　參考解析：對(duì)于長(zhǎng)度為n的線性表進(jìn)行順序查找，平均要進(jìn)行n/2次比較，在最壞情況下要進(jìn)行n次比較;對(duì)于長(zhǎng)度為n的線性表進(jìn)行二分查找，在最壞情況下要進(jìn)行l(wèi)092n次比較(但二分查找要求線性表是順序存儲(chǔ)的有序表)。因此本題的正確答案是C。

　　3[單選題]已知線性表的首元素的地址是1025，每個(gè)數(shù)據(jù)元素的長(zhǎng)度為2，則第10個(gè)兀素的地址為(　　)

　　A.1035B.1045C.1027D.1043

　　參考答案：D

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

　　參考答案：B

　　參考解析：

　　5[填空題]線性表的存儲(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ì)列的形式。

　　6[填空題]數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊(duì)列屬于________。

　　參考解析：線性【分析】帶鏈的隊(duì)列如下圖l.16所示。從圖中可以看出帶鏈的隊(duì)是線性結(jié)構(gòu)�？偨Y(jié)：常用的數(shù)據(jù)結(jié)構(gòu)比如：線性表、棧、隊(duì)列是線性結(jié)構(gòu)(不管是采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu));樹(shù)、二叉樹(shù)、圖都是非線性結(jié)構(gòu)(不管是采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))。

　　7[填空題]對(duì)長(zhǎng)度為l0的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為_(kāi)_______。

　　參考解析：45

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

　　8[單選題]在線性鏈表的插入算法中，若要把結(jié)點(diǎn)q插在結(jié)點(diǎn)P后面，下列操作正確的是：(　　)

　　A.使結(jié)點(diǎn)P指向結(jié)點(diǎn)q，再使結(jié)點(diǎn)q指向結(jié)點(diǎn)P的后件結(jié)點(diǎn)

　　B.使結(jié)點(diǎn)q指向P的后件結(jié)點(diǎn)，再使結(jié)點(diǎn)P指向結(jié)點(diǎn)q

　　C.使結(jié)點(diǎn)q指向結(jié)點(diǎn)P，再使結(jié)點(diǎn)P指向結(jié)點(diǎn)q的后件結(jié)點(diǎn)

　　D.使結(jié)點(diǎn)P指向q的后件結(jié)點(diǎn)，再使結(jié)點(diǎn)q指向結(jié)點(diǎn)P

　　參考答案：B

　　參考解析：在修改結(jié)點(diǎn)指針域的操作中，有一個(gè)操作順序的問(wèn)題。比較選項(xiàng)A和B只是操作順序顛倒了-下。A中先使結(jié)點(diǎn)p指向q后，q就成為P新的后件結(jié)點(diǎn)了，原先通過(guò)結(jié)點(diǎn)P指向的后件結(jié)點(diǎn)與結(jié)點(diǎn)P脫節(jié)了那么后面的-步操作沒(méi)有任何意義的：使結(jié)點(diǎn)q指向P的后件結(jié)點(diǎn)即使結(jié)點(diǎn)q成為自己的后件結(jié)點(diǎn)。按照B指定的順序操作就不會(huì)出現(xiàn)在引用結(jié)點(diǎn)p的指針域之前已經(jīng)把它的值修改了的情形。至于C和D項(xiàng)是命題者設(shè)計(jì)的干擾項(xiàng)想讓考生把P和(1的順序搞混。

　　總結(jié)，做這種類(lèi)型的試題，最好畫(huà)圖。插入結(jié)點(diǎn)：若結(jié)點(diǎn)p的后面是結(jié)點(diǎn)s，要在p和s之間插入結(jié)點(diǎn)q，-般先將結(jié)點(diǎn)q指向結(jié)點(diǎn)s，再將結(jié)點(diǎn)p指向q，順序不能顛倒。刪除結(jié)點(diǎn)：若結(jié)點(diǎn)p的后面是結(jié)點(diǎn)q.結(jié)點(diǎn)q的后面是結(jié)點(diǎn)s，若要?jiǎng)h除結(jié)點(diǎn)q，只需將結(jié)點(diǎn)p指向結(jié)點(diǎn)s即可。

　　9[單選題]在一個(gè)n×m的二維線性表中順序查找一個(gè)數(shù)據(jù)元素的算法時(shí)間復(fù)雜度是(　　)

　　A.O(n+m)B.O(n×m)C.O(n2)D.O(m2)

　　參考答案：B

　　參考解析：在-維線性表中順序查找一個(gè)數(shù)據(jù)元素的算法時(shí)間復(fù)雜度是O(n)，其中n是線性表的長(zhǎng)度二維線性表的順序查找方法和-維線性表相似，只不過(guò)是多了-維罷了。在二維表中進(jìn)行順序查找有兩個(gè)方法：-是把二維線性表看成是n個(gè)長(zhǎng)度為m的-維線性表，順序查找就是對(duì)這n個(gè)-維線性表依次實(shí)施順序查找，因此它的算法時(shí)間復(fù)雜度是O(n)×o(m)=o(n×m);二是直接把n×m的二維線性表看成一個(gè)n×m的-維線性表，那么在它當(dāng)中用順序查找法查捧一個(gè)元素的算法時(shí)間復(fù)雜度是O(n×m)。

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

　　參考答案：A

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

　　11[單選題]在線性鏈表的插入算法中，若要把結(jié)點(diǎn)q插在結(jié)點(diǎn)P后面，下列操作正確的是(　　)。

　　參考答案：B

　　參考解析：

　　12[單選題]在一個(gè)n×m的二維線性表中順序查找一個(gè)數(shù)據(jù)元素的算法時(shí)間復(fù)雜度是(　　)。

　　參考答案：B

　　參考解析：

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

　　答案：999

　　14[填空題]線性表的存儲(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ì)列的形式。

　　15[單選題]已知線性表的首元素的地址是1025，每個(gè)數(shù)據(jù)元素的長(zhǎng)度為2，則第10個(gè)兀素的地址為(　　)。

　　參考答案：D

　　16[單選題]下列關(guān)于鏈表結(jié)構(gòu)的敘述正確的是(　　)。

　　參考答案：A

　　17[單選題]下列敘述中正確的是(　　)。【考點(diǎn)5鏈表】

　　A.棧是“先進(jìn)先出”的線性表

　　B.隊(duì)列是“先進(jìn)后出”的線性表

　　C.循環(huán)隊(duì)列是非線性結(jié)構(gòu)

　　D.有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

　　參考答案：D

　　參考解析：本題主要考查了棧、隊(duì)列、循環(huán)隊(duì)列的概念，棧是先進(jìn)后出的線性表，隊(duì)列是先進(jìn)先出的線性表。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

　　18[單選題]在表示樹(shù)的多重鏈表中，除了要存儲(chǔ)結(jié)點(diǎn)的值和多個(gè)指針之外，還必須需要存儲(chǔ)(　　)。

　　參考答案：A

　　相關(guān)推薦：

　　2015計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考前沖刺練試題匯總

　　2015計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)精選選擇題專(zhuān)項(xiàng)練習(xí)

　　2015計(jì)算機(jī)二級(jí)《公共基礎(chǔ)知識(shí)》精選選擇題90道