2017年全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)復(fù)習(xí)題及答案

1、2017年全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)復(fù)習(xí)題及答案一、選擇題（在下列各題的a）、b）、c）、d）四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是正確的，請(qǐng)將正確選項(xiàng)填涂在答題卡相應(yīng)位置上。）1.1數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及a）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)b）計(jì)算方法c）數(shù)據(jù)映象d）邏輯存儲(chǔ)正確答案：a1.2數(shù)據(jù)處理的最小單位是a）數(shù)據(jù)b）數(shù)據(jù)元素c）數(shù)據(jù)項(xiàng)d）數(shù)據(jù)結(jié)構(gòu)正確答案：c1.3根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度, 般將數(shù)據(jù)結(jié)構(gòu)分成a） 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)b） 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)c） 線性結(jié)構(gòu)和非線性結(jié)構(gòu)d） 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)正確答案：c1.

2、4數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的a） 存儲(chǔ)結(jié)構(gòu)b） 物理結(jié)構(gòu)c） 邏輯結(jié)構(gòu)d） 物理和存儲(chǔ)結(jié)構(gòu)正確答案：c1.5在計(jì)算機(jī)中，算法是指a）加工方法b）解題方案的準(zhǔn)確而完整的描述c） 排序方法d） 查詢方法正確答案：b1.6算法分析的目的是a）找出數(shù)據(jù)結(jié)構(gòu)的合理性b） 找出算法中輸入和輸出之間的關(guān)系c） 分析算法的易懂性和可靠性d） 分析算法的效率以求改進(jìn)正確答案：d1.7算法的時(shí)間復(fù)雜度是指a） 執(zhí)行算法程序所需要的時(shí)間b）算法程序的長(zhǎng)度c）算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)d）算法程序中的指令條數(shù)正確答案：c1.8算法的空間復(fù)雜度是指a）算法程序的長(zhǎng)度b） 算法程序中的指令條數(shù)c）

3、 算法程序所占的存儲(chǔ)空間d）執(zhí)行過程中所需要的存儲(chǔ)空間正確答案：d1.9鏈表不具有的特點(diǎn)是a） 不必事先估計(jì)存儲(chǔ)空間b） 可隨機(jī)訪問任一元素c） 插入刪除不需要移動(dòng)元素d）所需空間與線性表長(zhǎng)度成正比正確答案：b1.10用鏈表表示線性表的優(yōu)點(diǎn)是a） 便于隨機(jī)存取b） 花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少c） 便于插入和刪除操作d）數(shù)據(jù)元素的物理順序與邏輯順序相同正確答案：c1.11下列敘述中正確的是a） 線性表是線性結(jié)構(gòu)b） 棧與隊(duì)列是非線性結(jié)構(gòu)c） 線性鏈表是非線性結(jié)構(gòu)d） 二叉樹是線性結(jié)構(gòu)正確答案：a1.12線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是a） 順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)b

4、） 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)c） 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)d） 任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu)正確答案：b1.13線性表l=（a1,a2,a3,ai，an）,下列說法正確的是a） 每個(gè)元素都有一個(gè)直接前件和直接后件b） 線性表中至少要有一個(gè)元素c） 表中諸元素的排列順序必須是由小到大或由大到小d）除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前件和直接后件正確答案：d1.14在單鏈表中，增加頭結(jié)點(diǎn)的目的是a）方便運(yùn)算的實(shí)現(xiàn)b） 使單鏈表至少有一個(gè)結(jié)點(diǎn)c） 標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置d）說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)正確答案：a1.15非空的

5、循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向），滿足a）p-next=nullb）p=nullc）p-next=headd）p=head正確答案：c1.16循環(huán)鏈表的主要優(yōu)點(diǎn)是a） 不再需要頭指針了b） 從表中任一結(jié)點(diǎn)出發(fā)都能訪問到整個(gè)鏈表c） 在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開d）已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易的找到它的直接前件正確答案：b1.17下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是a）線性鏈表b）棧c） 循環(huán)鏈表d） 順序表正確答案：b1.18棧和隊(duì)列的共同特點(diǎn)是a） 都是先進(jìn)先出b） 都是先進(jìn)后出c） 只允許在端點(diǎn)處插入和刪除元素d） 沒有共同點(diǎn)正確答案：c1.19如果進(jìn)棧序

6、列為e1,e2,e3,e4，則可能的出棧序列是a）e3,e1,e4,e2b）e2,e4,e3,e1c）e3,e4,e1,e2d）任意順序正確答案：b1.20棧底至棧頂依次存放元素a、b、c、d，在第五個(gè)元素e入棧前，棧中元素可以出棧，貝 s 出棧序列可能是a）abcedb）dcbeac) dbcead）cdabe正確答案：b1.21棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是a）線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)b） 散列方式和索引方式c） 鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組d） 線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)正確答案：a1.22串的長(zhǎng)度是a） 串中不同字符的個(gè)數(shù)b） 串中不同字母的個(gè)數(shù)c） 串中所含字符的個(gè)數(shù)且字符個(gè)數(shù)大于零d） 串中

7、所含字符的個(gè)數(shù)正確答案：d1.23樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是a） 有且只有1b）1或多于1c）0或1d）至少2正確答案：a1.24設(shè)有下列二叉樹：對(duì)此二叉樹前序遍歷的結(jié)果為a) zbtycpxab) atbzxcypc) zbtacyxpd) atbzxcpy正確答案：b1.25已知一棵二叉樹前序遍歷和中序遍歷分別為和dbgeachf，則該二叉樹的后序遍歷為abdegcfha) gedhfbcab) dgebhfcac) abcdefghd) acbfedhg正確答案：b1.26已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是a) acbedb) deca

8、bc) deabcd) cedba正確答案：d1.27具有3個(gè)結(jié)點(diǎn)的二叉樹有a)2種形態(tài)b)4種形態(tài)c)7種形態(tài)d)5種形態(tài)正確答案：d1.28在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為a)32b)31c)16d)15正確答案：b1.29設(shè)一棵二叉樹中有3個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn), 則該二叉樹中總的結(jié)點(diǎn)數(shù)為a)12b)13c)14d)15正確答案：b1.30 n個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有a)n-1b)n(n-1)d) n+1正確答案：c1.31假設(shè)線性表的長(zhǎng)度為n,則在最壞情況下，冒泡排序需要 的比較次數(shù)為a) iog2nb) n2c) o(n 1.5)d) n(n-1)/2正確答案：d

9、1.32已知數(shù)據(jù)表a中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間, 應(yīng)采用的算法是a)堆排序b)直接插入排序c)快速排序d)直接選擇排序正確答案：b1.33最簡(jiǎn)單的交換排序方法是a)快速排序b)選擇排序c)堆排序d)冒泡排序正確答案：d1.34在下列幾種排序方法中，要求內(nèi)存量的是a）插入排序b）選擇排序c）快速排序d）歸并排序正確答案：d1.35程序設(shè)計(jì)語言的基本成分是數(shù)據(jù)成分、運(yùn)算成分、控制成a）對(duì)象成分b）變量成分c）語句成分d）傳輸成分分和正確答案：d1.36結(jié)構(gòu)化程序設(shè)計(jì)的3種結(jié)構(gòu)是a）順序結(jié)構(gòu)、選擇結(jié)構(gòu)、轉(zhuǎn)移結(jié)構(gòu)b）分支結(jié)構(gòu)、等價(jià)結(jié)構(gòu)、循環(huán)結(jié)構(gòu)c）多分支結(jié)構(gòu)、賦值結(jié)構(gòu)、等價(jià)結(jié)構(gòu)d）順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)正確答案：d1.37在設(shè)計(jì)程序時(shí)，應(yīng)采納的原則之一是a）不限制goto語句的使用b） 減少或取消注解行c） 程序越短越好d） 程序結(jié)構(gòu)應(yīng)有助于讀者理解正確答案：d1.38對(duì)建立良好的程序設(shè)計(jì)風(fēng)格，下面描述正確的是a） 程序應(yīng)簡(jiǎn)單、清晰、可讀性好b） 符號(hào)名的命名只要符合語法c） 充分