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

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

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

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

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

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

6、序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點數(shù)目為：CA3B2 C4D5二、填空題。（共計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)中元素之間存在 一對一 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 一對多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。4數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是 順序、鏈式、 索引和 散列存儲 。5子串 ”str” 在主串 ”datastructure” 中的位置是 5。6深度為5的二叉樹至多有31 個結(jié)點。7若某二叉樹有

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