計(jì)算機(jī)二級數(shù)據(jù)結(jié)構(gòu)與算法答案

1、文檔供參考，可復(fù)制、編制，期待您的好評與關(guān)注！ 第一章 數(shù)據(jù)結(jié)構(gòu)與算法一、選擇題：1、棧和隊(duì)列的共同特點(diǎn)是()A、都是先進(jìn)先出 B、都是后進(jìn)先出C、只允許在端點(diǎn)處插入和刪除數(shù)據(jù) D、沒有共同點(diǎn)2、已知二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是()A、acbed B、decab C、debac D、cedba3、下面敘述正確的是()A、算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)。B、算法的空間復(fù)雜度是指算法程序中指令(或語句)的條數(shù)。C、算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止。D、算法的時(shí)間復(fù)雜度是指執(zhí)行算法程序所需要的時(shí)間。4、以下數(shù)據(jù)結(jié)構(gòu)屬于非線性數(shù)據(jù)

2、結(jié)構(gòu)的是()A、隊(duì)列 B、線性表 C、二叉樹 D、棧5、算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成?()A、循環(huán)、分支、遞歸 B、順序、循環(huán)、嵌套C、循環(huán)、遞歸、選擇 D、順序、選擇、循環(huán)6、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指()A、數(shù)據(jù)所占的存儲(chǔ)空間量 B、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示C、數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D、存儲(chǔ)在外存中的數(shù)據(jù)7、鏈表不具有的特點(diǎn)是()A、不必事先估計(jì)存儲(chǔ)空間 B、可隨機(jī)訪問任一元素C、插入刪除不需要移動(dòng)元素 D、所需空間與線性表長度成正比8、算法的時(shí)間復(fù)雜度是指()A、執(zhí)行算法程序所需要的時(shí)間 B、算法程序的長度C、算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) D、算法程序中的指令條數(shù)9

3、、在一棵二叉樹上第八層的結(jié)點(diǎn)數(shù)最多是()A、8 B、16 C、128 D、25610、若一棵二叉樹中只有葉結(jié)點(diǎn)和左右子樹皆非空的結(jié)點(diǎn)，設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為k，則左右子樹皆非空的結(jié)點(diǎn)個(gè)數(shù)是()A、2k B、k-1 C、2k-1 D、2k-111、設(shè)無向樹T有7片樹葉，其余頂點(diǎn)數(shù)均為3，則T中3度頂點(diǎn)的個(gè)數(shù)為()A、3 B、4 C、5 D、612、已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH 和DBGEACHF，則該二叉樹的后序遍歷為()A、GEDHFBCA B、DGEBFCA C、ABCDEFGH D、ACBFEDHG13、樹是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是()A、有且只有1個(gè) B、1個(gè)或多

4、于1個(gè) C、0個(gè)或1個(gè) D、至少2個(gè)14、下列敘述中正確的是()A線性表是線性結(jié)構(gòu) B、棧和隊(duì)列是非線性結(jié)構(gòu)C、線性鏈表是非線性結(jié)構(gòu) D、二叉樹是線性結(jié)構(gòu)15、堆棧存儲(chǔ)器存取數(shù)據(jù)的方式是()A、先進(jìn)先出 B、隨機(jī)存取 C先進(jìn)后出 D、不同于前三種方式16、如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是()A、e3,e1,e4,e2 B、e4,e3,e2,e1 C、e3,e4,e1,e2 D、任意順序17、在設(shè)計(jì)程序時(shí)應(yīng)采用的原則之一是()A、不限制goto語句的使用 B、減少或取消注釋行C、程序越短越好 D、程序結(jié)構(gòu)應(yīng)助于讀者理解18、下面關(guān)于完全二叉樹的敘述中，錯(cuò)誤的是()A、除了

5、最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值B、可能缺少若干個(gè)左右葉子結(jié)點(diǎn)C、完全二叉樹一般不是滿二叉樹D、具有幾個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+119、下列關(guān)于棧的敘述中正確的是()A、在棧中只能插入數(shù)據(jù) B、在棧中只能刪除數(shù)據(jù)C、棧是先進(jìn)先出的線性別 D、棧是先進(jìn)后出的線性表20、在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為()A、32 B、31 C、16 D、1521、一個(gè)算法應(yīng)該具有“確定性”等五個(gè)特性，下面對另外四個(gè)特性的描述中錯(cuò)誤的是（）A、有零個(gè)或多個(gè)輸入 B、有零個(gè)或多個(gè)輸出 C、有窮形 D、可行性22、若想將數(shù)據(jù)序列使用插入排序算法由小到大排序，則每次放到有序子列合適位置上的元

6、素，應(yīng)從無序序列中選擇()A、固定位置的 B、最小的 C、任意的 D、最大的23、算法的空間復(fù)雜度是指()A、算法程序的長度 B、算法程序中的指令條數(shù)C、算法程序所占的存儲(chǔ)空間 D、執(zhí)行過程中所需要的存儲(chǔ)空間24、用鏈表表示線性表的優(yōu)點(diǎn)是()A、便于隨機(jī)存取 B、花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少C、便于插入和刪除操作 D、數(shù)據(jù)元素的物理順序與邏輯順序相同25、鏈表不具備的特點(diǎn)是()A、可隨機(jī)訪問任意一個(gè)結(jié)點(diǎn) B、插入和刪除不需要移動(dòng)任何元素C、不必事先估計(jì)存儲(chǔ)空間 D、所需空間與其長度成正比26、數(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、物理與邏輯結(jié)

7、構(gòu)27、希爾排序法屬于()類型的排序法。A、交換 B、插入 C、選擇 D、建堆28、下列關(guān)于棧的敘述正確的是().A、棧是非線性結(jié)構(gòu) B、棧是一種樹狀結(jié)構(gòu)C、棧具有先進(jìn)先出的特征 D、棧具有后進(jìn)先出的特征29、下列關(guān)于隊(duì)列的敘述中正確的是()A、在隊(duì)列中只能插入數(shù)據(jù) B、在隊(duì)列中只能刪除數(shù)據(jù)C、隊(duì)列是先進(jìn)先出的線性表 D、隊(duì)列具有后進(jìn)先出的特征30、對長度為N的線性表進(jìn)行順序查找，在最壞情況下所需的比較次數(shù)為()A、N+1 B、N C、(N+1)/2 D、N/231、一些重要的程序語言(若C語言和Pascal語言)允許過程的遞歸調(diào)用，而實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用()。A、棧 B、堆 C、數(shù)

8、組 D、鏈表32、數(shù)據(jù)處理的最小單位是()A、數(shù)據(jù) B、數(shù)據(jù)元素 C、數(shù)據(jù)項(xiàng) D、數(shù)據(jù)結(jié)構(gòu)33、數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)科學(xué)的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)，對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及()。A、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B、計(jì)算方法 C、數(shù)據(jù)映像 D、邏輯結(jié)構(gòu)34、串的長度是()A、串中不同字符的個(gè)數(shù) B、串中不同字母的個(gè)數(shù)C、串中所含字符的個(gè)數(shù)且字符個(gè)數(shù)大于零 D、串中所含字符的個(gè)數(shù)35、在下列幾種排序方法中，要求內(nèi)存量最大的是()A、插入排序 B、選擇排序 C、快速排序 D、歸并排序36、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(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é)

9、構(gòu) D、集合結(jié)構(gòu)與非集合結(jié)構(gòu)37、在計(jì)算機(jī)中，算法是指()A、加工方法 B、解題方案的準(zhǔn)確而完整的描述C、排序方法 D、查詢方法38、下列敘述中，錯(cuò)誤的是()A、線性表是由n個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列。B、線性表是一種線性結(jié)構(gòu)，數(shù)據(jù)元素之間的相對位置是線性的。C、線性表的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)和一個(gè)后繼。D、線性表可以是空表。39、下列數(shù)據(jù)結(jié)構(gòu)具有記憶功能的是()A、隊(duì)列 B、循環(huán)隊(duì)列 C、棧 D、順序表40、假設(shè)線性表的長度為n，則在最壞的情況下，冒泡排序需要的比較次數(shù)為()。A、log2n B、n2 C、O(n1.5) D、n(n-1)/241、算法分析的目的是()A、找出數(shù)據(jù)結(jié)構(gòu)的合

10、理性 B、找出算法中輸入和輸出之間的關(guān)系C、分析算法的易懂性和可靠性 D、分析算法的效率以求改進(jìn)42、線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是()A、順序存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B、隨機(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)43、線性表L=(a1,a2,a3,ai,an)，下列說法正確的是()A、每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。B、線性表中至少要有一個(gè)元素。C、表中諸元素的排列順序必須由小到大或由大到小。D、除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼

11、44、在單鏈表中，增加頭結(jié)點(diǎn)的目的是()A、方便運(yùn)算的實(shí)現(xiàn) B、使單鏈表至少有一個(gè)結(jié)點(diǎn)C、標(biāo)志表表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置 D、說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)45、下列敘述中，正確的是()A、線性鏈表中的各元素在存儲(chǔ)空間中的位置必須是連續(xù)的B、線性鏈表中的表頭元素一定存儲(chǔ)在其他元素的前面C、線性表中的各元素在存儲(chǔ)空間中的位置不一定是連續(xù)的，但表頭元素一定存儲(chǔ)在元素的前面。D、線性鏈表中的各元素在存儲(chǔ)空間中的位置不一定連續(xù)，且各元素的存儲(chǔ)順序也是任意的。46、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)，滿足()A、p->next=NULL B、p=NULL C、p->next=hea

12、d D、p=head47、n個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有()A、n-1 B、n(n-1) C、n D、n+148、已知數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn)，為節(jié)省時(shí)間，應(yīng)采用的算法是()A、堆排序 B、直接插入排序 C、快速排序 D、直接選擇排序49、NULL是指()A、空值 B、空格 C、未知的值或無任何值 D、空字符50、算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為算法的（）A、確定性 B、易讀性 C、健壯性 D、高效性51、數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為()A、存儲(chǔ)結(jié)構(gòu) B、邏輯結(jié)構(gòu) C、順序存儲(chǔ)結(jié)構(gòu) D、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)52、下列關(guān)于棧的描述中錯(cuò)誤的是（）A、棧

13、是先進(jìn)后出的線性表 B、棧只能順序存儲(chǔ)C、棧具有記憶作用 D、對棧的插入與刪除操作中，不需要改變棧底指針53、對于長度為n的線性表，在最壞的情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是()A、冒泡排序n/2 B、冒泡排序nC、快速排序n D、快速排序n(n-1)/254、從末排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為()A、希爾排序 B、冒泡排序 C、插入排序 D、選擇排序55、對線性表進(jìn)行折半查找時(shí)，要求線性表必須()A、以順序方式存儲(chǔ) B、以鏈?zhǔn)椒绞酱鎯?chǔ)C、以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列 D、以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)

14、按關(guān)鍵字有序排列56、數(shù)據(jù)獨(dú)立性是數(shù)據(jù)庫技術(shù)的重要特點(diǎn)之一，所謂數(shù)據(jù)獨(dú)立性是指()A、數(shù)據(jù)與程序獨(dú)立存取 B、不同的數(shù)據(jù)被存放在不同的文件中C、不同的數(shù)據(jù)只能被對應(yīng)的應(yīng)用程序所使用 D、以上三種說法都不對。57、如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是()A、e3,e1,e4,e2 B、e2,e4,e3,e1 C、e3,e4,e1,e2 D、任意順序58、設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)位置的運(yùn)算稱作()A、連接 B、模式匹配 C、求子串 D、求串長59、線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址()A、必須是連續(xù)的 B、部分地址是連續(xù)的C、一定是不連續(xù)的 D

15、、連續(xù)不連續(xù)都可以60、由兩個(gè)棧共享一個(gè)存儲(chǔ)空間的好處是()A、減少存儲(chǔ)時(shí)間，降低下溢發(fā)生的機(jī)率 B、節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率C、減少存儲(chǔ)時(shí)間，降低上溢發(fā)生的機(jī)率 D、節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率61、若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則后序遍歷的結(jié)點(diǎn)訪問順序是()A、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfce62、已知棧底至棧頂依次存放元素A、B、C、D，在第5個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是()A、ABCED B、DCBEA C、DBCEA D、CDABE63、對如下二叉

16、樹進(jìn)行后序遍歷的結(jié)果為A)ABCDEF     B)DBEAFC C)ABDECF     D)DEBFCA64、對下列二叉樹FCCcEADGB進(jìn)行中序遍歷的結(jié)果是A) ACBDFEG B) ACBDFGE C) ABDCGEF D) FCADBEG65、對下列二叉樹 A B C D E F X Y Z 進(jìn)行前序遍歷的結(jié)果為A) DYBEAFCZX           B) YDEBFZXCA C

17、) ABDYECFXZ           D) ABCDEFXYZ66、對下列二叉樹進(jìn)行中序遍歷的結(jié)果為【4】 acbdfehgp 。二、填空題：1、在長度為n的有序線性表中進(jìn)行二分查找。在最壞的情況下，需要的比較次數(shù)為(log2n)。2、數(shù)據(jù)的物理結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式成為數(shù)據(jù)的(存儲(chǔ)結(jié)構(gòu))。3、數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，線性表屬于(存儲(chǔ)結(jié)構(gòu))。4、數(shù)組、堆棧、(隊(duì)列)和鏈表都是線性數(shù)據(jù)結(jié)構(gòu)。5、假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序法的時(shí)間復(fù)雜度

18、是(n(n-1)/2)。6、在一棵完全二叉樹共有500個(gè)結(jié)點(diǎn)，則在該二叉樹中有(250)個(gè)葉子結(jié)點(diǎn)。7、在樹形結(jié)構(gòu)中，根結(jié)點(diǎn)沒有(前件或前驅(qū))。8、棧的基本運(yùn)算有三種：入棧、出棧和(讀棧頂元素)。9、在完全二叉樹的順序存儲(chǔ)中，若結(jié)點(diǎn)i有左孩子，則其左孩子是結(jié)點(diǎn)(2i)。10、長度為n的順序存儲(chǔ)線性表中，當(dāng)在任何位置上插入一個(gè)元素概率都相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為(n/2)。11、用樹形結(jié)構(gòu)表示實(shí)體類型及實(shí)體間的聯(lián)系的數(shù)據(jù)模型稱為(層次模型)。12、數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的(存儲(chǔ)結(jié)構(gòu))以及對數(shù)據(jù)的操作運(yùn)算。13、設(shè)一棵二叉樹中有三個(gè)葉子結(jié)點(diǎn)，有8個(gè)度為1的結(jié)點(diǎn)，則該二叉樹總的結(jié)點(diǎn)數(shù)為(13)。14、在最壞