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

1、 2021年數(shù)據(jù)構造期末考試題及答案一、選擇題(共計50分，每題2分，共25題)1在數(shù)據(jù)構造中，從邏輯上可以把數(shù)據(jù)構造分為 C 。A動態(tài)構造和靜態(tài)構造 B緊湊構造和非緊湊構造C線性構造和非線性構造 D內部構造和外部構造2數(shù)據(jù)構造在計算機內存中的表示是指A。A數(shù)據(jù)的存儲構造B數(shù)據(jù)構造C數(shù)據(jù)的邏輯構造 D數(shù)據(jù)元素之間的關系3在數(shù)據(jù)構造中，及所使用的計算機無關的是數(shù)據(jù)的 A 構造。A邏輯B存儲C邏輯和存儲D物理4在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲 C 。A數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類型C數(shù)據(jù)元素之間的關系D數(shù)據(jù)的存儲方法5在決定選取何種存儲構造時，一般不考慮 A 。A各結點的值

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

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

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。

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

6、23某二叉樹結點的中序序列為ABCDEFG，后序序列為BDCAFGE，那么其左子樹中結點數(shù)目為：CA3B2 C4D5二、填空題。共計20分，共10題，每空1分1數(shù)據(jù)邏輯構造包括線性構造 、樹形構造和圖狀構造三種類型，樹形構造和圖狀構造合稱 非線性構造 。2數(shù)據(jù)的邏輯構造分為集合 、線性構造 、樹形構造和圖狀構造4種。3線性構造中元素之間存在 一對一 關系，樹形構造中元素之間存在 一對多 關系，圖形構造中元素之間存在多對多關系。4數(shù)據(jù)構造的根本存儲方法是 順序、鏈式、 索引和 散列存儲 。5子串 str 在主串 datastructure 中的位置是 5。6深度為5的二叉樹至多有31 個結點。7

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