2017年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案A

1、 2017年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案一、選擇題(共計(jì)50分，每題2分，共25題)1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 C 。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)2數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指A。A數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu) D數(shù)據(jù)元素之間的關(guān)系3在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的 A 結(jié)構(gòu)。A邏輯B存儲(chǔ)C邏輯和存儲(chǔ)D物理4在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ) C 。A數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類型C數(shù)據(jù)元素之間的關(guān)系D數(shù)據(jù)的存儲(chǔ)方法5在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮 A 。A各結(jié)點(diǎn)的值

2、如何B結(jié)點(diǎn)個(gè)數(shù)的多少C對(duì)數(shù)據(jù)有哪些運(yùn)算D所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6以下說(shuō)法正確的是D 。A數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位B數(shù)據(jù)元素是數(shù)據(jù)的最小單位C數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7在以下的敘述中，正確的是 B 。A線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進(jìn)先出D隊(duì)列的操作方式是先進(jìn)后出8通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B 。A數(shù)據(jù)元素具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要

3、相等9鏈表不具備的特點(diǎn)是A 。A可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B插入刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與其長(zhǎng)度成正比10若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用D存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B給出表頭指針的單循環(huán)鏈表C雙鏈表 D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表11需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是 B 。A單鏈表 B靜態(tài)鏈表C線性鏈表 D順序存儲(chǔ)結(jié)構(gòu)12非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足C 。Apnext NULLBp NULLCpnext head Dp head13在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的

4、操作是 D 。Appriorprior=sBppriornext=sCspriornext sDspriorprior s14棧和隊(duì)列的共同點(diǎn)是C 。A都是先進(jìn)后出 B都是先進(jìn)先出C只允許在端點(diǎn)處插入和刪除元素 D沒(méi)有共同點(diǎn)15一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C 。AedcbaBdecbaCdceabDabcde16一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是B 。A4，3，2，1 B1，2，3，4C1，4，3，2 D3，2，4，117在循環(huán)隊(duì)列中，若front與rear 分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是 C。Afrontre

5、ar1 Brearfront1 Cfrontrear Dfront018若串Ssoftware，其子串的數(shù)目是 B 。A8 B37 C36D919串的長(zhǎng)度是指B 。A串中所含不同字母的個(gè)數(shù) B串中所含字符的個(gè)數(shù)C串中所含不同字符的個(gè)數(shù) D串中所含非空格字符的個(gè)數(shù)20串是一種特殊的線性表，其特殊性體現(xiàn)在B 。A可以順序存儲(chǔ)B數(shù)據(jù)元素是一個(gè)字符C可以鏈?zhǔn)酱鎯?chǔ)D數(shù)據(jù)元素可以是多個(gè)字符21若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)是B 。A9 B11 C15D不能確定22具有10個(gè)葉子結(jié)點(diǎn)的二叉樹中有 B 個(gè)度為2的結(jié)點(diǎn)。A8 B9 C10 D1123某二叉樹結(jié)點(diǎn)的中序

6、序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為：CA3B2 C4D5二、填空題。（共計(jì)20分，共10題，每空1分）1數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu) 、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱 非線性結(jié)構(gòu) 。2數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合 、線性結(jié)構(gòu) 、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。3線性結(jié)構(gòu)中元素之間存在 一對(duì)一 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 一對(duì)多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。4數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是 順序、鏈?zhǔn)健?索引和 散列存儲(chǔ) 。5子串 ”str” 在主串 ”datastructure” 中的位置是 5。6深度為5的二叉樹至多有31 個(gè)結(jié)點(diǎn)。7若某二叉樹有

7、20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)個(gè)數(shù)為 69 。8具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_45_。 9索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集，它由若干索引項(xiàng)組成，索引項(xiàng)的結(jié)構(gòu)為關(guān)鍵字 和 關(guān)鍵字對(duì)應(yīng)記錄的地址 。10在一棵m階B樹中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有 m棵子樹，最少有 m/2 棵子樹。三、判斷題（共10分，共10題，每題一分）。1在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮各結(jié)點(diǎn)的值如何。（）2抽象數(shù)據(jù)類型（ADT）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個(gè)ADT的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。（ ）3抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān)。（ ）4順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。（ ）5線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。（ ）6雙向鏈表可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)。（）7在單鏈表中，給定任一結(jié)點(diǎn)的地址p，則可用下述語(yǔ)句將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p的后面 ：pnext； （ ）8隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種先