csp認(rèn)證考試題庫(kù)及答案初賽

一、單項(xiàng)選擇題（每題2分，共10題）1.以下哪種數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)？（）A.數(shù)組B.鏈表C.樹(shù)D.棧答案：C2.在計(jì)算機(jī)中，1KB等于多少字節(jié)？（）A.512B.1000C.1024D.2048答案：C3.以下哪種排序算法的時(shí)間復(fù)雜度在最壞情況下為O(n2)？（）A.快速排序B.堆排序C.歸并排序D.冒泡排序答案：D4.設(shè)二叉樹(shù)的高度為h，且只有度為0和2的結(jié)點(diǎn)，則此二叉樹(shù)的結(jié)點(diǎn)數(shù)為（）A.2h-1B.2h+1C.2hD.h+1答案：A5.一個(gè)算法的時(shí)間復(fù)雜度為O(nlog?n)，當(dāng)n=1024時(shí)，運(yùn)行時(shí)間約為10秒，當(dāng)n=2048時(shí)，運(yùn)行時(shí)間約為（）A.11秒B.15秒C.20秒D.25秒答案：C6.在C++語(yǔ)言中，以下哪種函數(shù)不能被重載？（）A.成員函數(shù)B.非成員函數(shù)C.構(gòu)造函數(shù)D.析構(gòu)函數(shù)答案：D7.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若元素出隊(duì)的順序?yàn)閑2，e4，e3，e5，e1，則棧S的容量至少為（）A.2B.3C.4D.5答案：B8.對(duì)于一個(gè)有向圖，如果從頂點(diǎn)i到頂點(diǎn)j有路徑，則稱頂點(diǎn)i和頂點(diǎn)j是（）A.強(qiáng)連通的B.連通的C.可達(dá)的D.相鄰的答案：C9.在C語(yǔ)言中，若有定義inta[10];，則以下表達(dá)式中不能表示a[1]地址的是（）A.a+1B.&a[0]+1C.&a[1]D.a++答案：D10.以下關(guān)于遞歸函數(shù)的說(shuō)法正確的是（）A.遞歸函數(shù)必須有返回值B.遞歸函數(shù)不能調(diào)用自身C.遞歸函數(shù)的運(yùn)行效率通常比非遞歸函數(shù)高D.遞歸函數(shù)可以用來(lái)解決具有遞歸性質(zhì)的問(wèn)題答案：D二、多項(xiàng)選擇題（每題2分，共10題）1.以下屬于面向?qū)ο蟪绦蛟O(shè)計(jì)的特性的有（）A.封裝B.繼承C.多態(tài)D.過(guò)程調(diào)用答案：ABC2.以下哪些是圖的遍歷算法？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.最短路徑算法答案：AB3.在C++中，動(dòng)態(tài)內(nèi)存分配可以使用（）A.new運(yùn)算符B.malloc函數(shù)C.calloc函數(shù)D.realloc函數(shù)答案：A4.以下關(guān)于數(shù)組的說(shuō)法正確的有（）A.數(shù)組的元素在內(nèi)存中是連續(xù)存儲(chǔ)的B.數(shù)組的大小在定義后不能改變C.二維數(shù)組可以看作是數(shù)組的數(shù)組D.數(shù)組的下標(biāo)從1開(kāi)始答案：ABC5.以下哪些操作可以對(duì)二叉樹(shù)進(jìn)行？（）A.插入節(jié)點(diǎn)B.刪除節(jié)點(diǎn)C.查找節(jié)點(diǎn)D.遍歷答案：ABCD6.以下關(guān)于鏈表的說(shuō)法正確的有（）A.鏈表的節(jié)點(diǎn)在內(nèi)存中是離散存儲(chǔ)的B.鏈表插入和刪除節(jié)點(diǎn)操作比數(shù)組方便C.單向鏈表只能從頭節(jié)點(diǎn)開(kāi)始遍歷D.循環(huán)鏈表的最后一個(gè)節(jié)點(diǎn)的next指針指向頭節(jié)點(diǎn)答案：ABCD7.在計(jì)算機(jī)網(wǎng)絡(luò)中，以下屬于網(wǎng)絡(luò)層協(xié)議的有（）A.IP協(xié)議B.ARP協(xié)議C.TCP協(xié)議D.UDP協(xié)議答案：AB8.以下關(guān)于函數(shù)模板的說(shuō)法正確的有（）A.函數(shù)模板可以用來(lái)創(chuàng)建函數(shù)族B.函數(shù)模板的參數(shù)可以是類型參數(shù)C.函數(shù)模板可以提高代碼的復(fù)用性D.函數(shù)模板在編譯時(shí)會(huì)被實(shí)例化為具體的函數(shù)答案：ABCD9.以下哪些是算法的評(píng)價(jià)標(biāo)準(zhǔn)？（）A.正確性B.可讀性C.健壯性D.時(shí)間復(fù)雜度和空間復(fù)雜度答案：ABCD10.在數(shù)據(jù)庫(kù)中，以下屬于關(guān)系型數(shù)據(jù)庫(kù)的有（）A.MySQLB.OracleC.MongoDBD.SQLServer答案：ABD三、判斷題（每題2分，共10題）1.二叉樹(shù)的中序遍歷序列是唯一的。（）答案：對(duì)2.棧是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。（）答案：錯(cuò)3.在C語(yǔ)言中，函數(shù)可以嵌套定義。（）答案：錯(cuò)4.所有的排序算法在最好情況下的時(shí)間復(fù)雜度都是O(n)。（）答案：錯(cuò)5.圖的鄰接矩陣表示法中，矩陣的對(duì)角線元素一定為0。（）答案：錯(cuò)6.在C++中，類的私有成員只能被類的成員函數(shù)訪問(wèn)。（）答案：對(duì)7.動(dòng)態(tài)規(guī)劃算法通常用于解決具有最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題。（）答案：對(duì)8.哈希表中不存在相同的鍵值對(duì)。（）答案：對(duì)9.在計(jì)算機(jī)中，補(bǔ)碼是用來(lái)表示有符號(hào)整數(shù)的一種編碼方式。（）答案：對(duì)10.一個(gè)無(wú)向圖的連通分量個(gè)數(shù)一定小于等于該圖的頂點(diǎn)個(gè)數(shù)。（）答案：對(duì)四、簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。答案：棧是后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素只能從棧頂進(jìn)出；隊(duì)列是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素從隊(duì)尾進(jìn)，隊(duì)頭出。2.什么是二叉搜索樹(shù)？答案：二叉搜索樹(shù)是一種二叉樹(shù)，它的左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值，右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值。3.簡(jiǎn)述快速排序的基本思想。答案：快速排序選擇一個(gè)基準(zhǔn)元素，將數(shù)組分為兩部分，左邊元素小于基準(zhǔn)，右邊元素大于基準(zhǔn)，然后對(duì)左右兩部分遞歸排序。4.解釋什么是面向?qū)ο笾械亩鄳B(tài)。答案：多態(tài)是指同一操作作用于不同的對(duì)象，可以有不同的解釋，產(chǎn)生不同的執(zhí)行結(jié)果。五、討論題（每題5分，共4題）1.討論在什么情況下應(yīng)該選擇數(shù)組而不是鏈表來(lái)存儲(chǔ)數(shù)據(jù)。答案：當(dāng)數(shù)據(jù)規(guī)模固定，需要頻繁隨機(jī)訪問(wèn)元素時(shí)，數(shù)組更合適，因?yàn)閿?shù)組元素連續(xù)存儲(chǔ)，隨機(jī)訪問(wèn)效率高。2.分析動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)和缺點(diǎn)。答案：優(yōu)點(diǎn)是效率高，避免重復(fù)計(jì)算；缺點(diǎn)是空間復(fù)雜度可能較高，且設(shè)計(jì)狀態(tài)和狀態(tài)轉(zhuǎn)移方程