數(shù)據(jù)結(jié)構(gòu) 考試 填空選擇簡答

1、.一、選擇題1在數(shù)據(jù)結(jié)構(gòu)中，不可分割的最小數(shù)據(jù)單位是（A）A數(shù)據(jù)項B數(shù)據(jù)元素；C數(shù)據(jù)對象D.數(shù)據(jù)類型2.算法指的（D）A計算機程序 B解決問題的計算方法；C排序算法；D解決問題的有限運算序列3一個隊列的入列序列是1、2、3、4，則隊列的輸出序列是（ B ）A4，3，2，1 B1，2，3，4C1，4，3，2 D3，2，4，14某二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則前序序列遍歷為 ( D ) A. ACBEDB. DECAB C. DEABC D. CEDBA5 設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（D）條邊。A n-1 B.n(n+1)/2 C.n2 Dn(n-1)/2

2、1.串是一種特殊的線性表，其特殊性體現(xiàn)在（D ）A、可以順序存儲 B、數(shù)據(jù)元素是一個字符C、可以鏈接存儲 D、數(shù)據(jù)元素可以是多個字符2.不帶頭結(jié)點的單鏈表head為空的判定條件是（A ）A.head=NULL B.head-next=NULLC.head-next=head D.head！=NULL3.一個向量第一個元素的存儲地址是100 ,每個元素的長度為2，則第5個元素的地址是（B ）A.110 B.108 C.100 D.1204、一個隊列的入列序列是1、2、3、4，則隊列的輸出序列是（B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 5、線性表若采

3、用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（C ）A.必須是連續(xù) B.部分地址必須是連續(xù)的C.一定是不連續(xù)的 D.連續(xù)或不連續(xù)都可以6、在以下的敘述中，正確的是（B ）A、線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B、二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C、棧的操作方式是先進先出D、隊列的操作方式是先進后出7、串是一種特殊的線性表，其特殊性體現(xiàn)在（D ）A、可以順序存儲 B、數(shù)據(jù)元素是一個字符C、可以鏈接存儲 D、數(shù)據(jù)元素可以是多個字符8、若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種觀點（A ）A正確 B、錯誤1. 抽象數(shù)據(jù)類型概念與C語

4、言中數(shù)據(jù)類型概念的最大區(qū)別在于（D）A前者比后者復(fù)雜得多；B前者包含后者；C前者包含一組數(shù)據(jù)關(guān)系，而后者沒有；D前者包含一組操作，而后者沒有2. 在數(shù)據(jù)結(jié)構(gòu)中，不可分割的最小數(shù)據(jù)單位是（A）A數(shù)據(jù)項 B數(shù)據(jù)元素；C數(shù)據(jù)對象D數(shù)據(jù)類型3. 字符串S1、S2聯(lián)接成新串T，其中LS1、LS2和LT分別表示S1、S2和T的長度。根據(jù)S1和S2長度的不同，新串T值的產(chǎn)生一般要可慮到3種情況，請在以下選項中選出不屬于考慮范圍的情況：（C）A. LS1LS2LT；B. LS1LS2LT；C. LS2LT；D. LS1LT4. 在鏈式棧的操作中，關(guān)于出棧與取棧頂元素的描述，正確的是（E）A. 兩者均為讀出棧頂

5、元素的值；B. 兩者均使棧頂元素出棧；C. 前者使棧頂元素出棧，而后者為讀出棧頂元素的值；D. 后者使棧頂元素出棧，而前者為讀出棧頂元素的值；E. 前者使棧頂元素出棧，并釋放內(nèi)存空間，而后者為讀出棧頂元素的值一，填序號已知是帶表頭結(jié)點的非空單鏈表，且結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從下列提供的答案中選擇全程的語句序列。1.刪除結(jié)點的直接后繼結(jié)點的語句序列是11,3,142.刪除結(jié)點的直接前驅(qū)結(jié)點的語句序列是10,12,8,11,3,143. 刪除結(jié)點的語句序列是10,12,7,3,144刪除首元結(jié)點的語句序列是12,11,3,145. 刪除尾元結(jié)點的語句序列是12,9,11,3,14（）

6、；（）；（）；（）；（）（?。?；（）（?。唬ǎǎ。?；（）（！）；（）（?。唬ǎ?；（）；（）；（）；（）（）；二簡答題1簡述下列術(shù)語數(shù)據(jù):即對客觀事物的符號表示。在計算機科學(xué)中，指輸入到計算機中并被計算機處理的符號的總稱數(shù)據(jù)元素:數(shù)據(jù)的基本單位。可由若干數(shù)據(jù)項組成，常把數(shù)據(jù)元素作為一個整體考慮。數(shù)據(jù)對象:性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。數(shù)據(jù)結(jié)構(gòu):是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。作為一門學(xué)科，它是研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等。數(shù)據(jù)邏輯結(jié)構(gòu):是指在數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)學(xué)模型。數(shù)據(jù)存儲結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)在計算機中

7、的表示或映象。包含數(shù)據(jù)元素及其關(guān)系的表示。數(shù)據(jù)類型:一個值的集合和定義在這個值集上的一組操作的總稱。抽象數(shù)據(jù)類型:是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。包括數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作算法:是對特定問題求解步驟的一種描述，是指令的有限序列。2. 簡述線性表的定義及其特點答：即多個數(shù)據(jù)元素的有限序列。特點： 存在惟一一個被稱作“第一個”的數(shù)據(jù)元素存在惟一一個被稱作“最后一個”的數(shù)據(jù)元素集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)（除第一個之外）集合中的每個數(shù)據(jù)元素均只有一個后繼（除最后一個之外）3. 簡述順序表與單鏈表的定義，并指出它們各自的存儲結(jié)構(gòu)、表特點、存取方式。答：用一組地址連續(xù)的存儲單元

8、依次存儲線性表的數(shù)據(jù)元素，象這種順序存儲結(jié)構(gòu)的線性表叫做順序表。用一組地址任意的存儲單元存儲線性表的數(shù)據(jù)元素，數(shù)據(jù)元素除了存儲其本身的信息之外，還存儲一個指示其直接后繼的信息，n個數(shù)據(jù)元素結(jié)點鏈接成的鏈式存儲結(jié)構(gòu)的線性表，就是鏈表。每個結(jié)點只包含一個指針域的鏈表叫做單鏈表4. 簡述棧與隊列的定義，并指出它們各自的特點。答：棧是限定僅在表尾進行插入或刪除操作的線性表。特點：后進先出(LIFO) 隊列是只允許在表的一端進行插入，而在另一端刪除元素的線性表。特點：先進先出（FIFO）3 填空題1、在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū) 結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；葉子結(jié)點沒有后繼 結(jié)點，其余

9、每項個結(jié)點的后續(xù)結(jié)點可以多個。2、在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以相等 相同。3在線性結(jié)構(gòu)中，第一個結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有 個前驅(qū)結(jié)點；最后一個結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點有且只有 個后續(xù)結(jié)點。4，在順序表中插入或刪除一個元素，需平均移動（表中一半）元素，具體移動的元素個數(shù)與（表長和該元素在表中的位置）有關(guān)。5，在單鏈表中，除了首元素結(jié)點外，任一結(jié)點的存儲位置由（其直接前驅(qū)結(jié)點的鏈域的值）來指示。6，在單鏈表中，設(shè)置頭結(jié)點的作用是（對首元結(jié)點的操作和對其他結(jié)點的操作保持一致，不用特殊）。7、單鏈表是線性表的鏈接存儲表示。8、兩個串相等的充分必要條件是兩個串的

10、值相等。9、空串是零個字符的串，其長度等于零。10、一維數(shù)組的邏輯結(jié)構(gòu)是 ，存儲結(jié)構(gòu)是順序存儲；對二維或多維數(shù)組，分為按 列序為主序和行序為主序兩種不同的存儲方式。11棧和隊列都是線性結(jié)構(gòu)，對于棧只能在棧頂插入和刪除元素，對于隊列只能在隊尾插入元素和隊頭刪除元素。12棧是限定僅在表尾進行插入或刪除操作的線性表，其進棧和出棧特點為先進后出；隊列是只允許在表的一端進行插入，而在另一端除元素的線性表，其進隊和出隊特點為先進先出。13，算法有5個重要特性，分別是：（有窮性）、（確定性）、（可行性）、（輸入）、（輸出）。14，一個“好”的算法，通常從5個方面來衡量，它們是（正確性）、（可讀性）、（健壯性

11、）（效率高）、（存儲空間?。?5，順序表中邏輯上相鄰元素的物理位置（必定）（填寫“必定”或“不一定”）緊鄰；單鏈表中邏輯上相鄰元素的物理位置（不一定）（填寫“必定”或“不一定”）緊鄰。16線性結(jié)構(gòu)中元素之間存在 一個對一個關(guān)系，樹形結(jié)構(gòu)中元素之間存在一個對多個 關(guān)系，圖形結(jié)構(gòu)中元素之間存在多個對多個關(guān)系。17廣義表（a），（b），c），(d)）的表頭是（a），表尾是（b），c），(d)）。18 有一棵樹如右圖所示，這棵樹的根結(jié)點是K1；結(jié)點K3的子女是K5，K6；結(jié)點K3的父結(jié)點是K1。19 根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特點，數(shù)據(jù)結(jié)構(gòu)可分為4種基本類型，它們分別是：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)（或網(wǎng)狀結(jié)構(gòu)）。20. 用一維數(shù)組保存一組類型相同的數(shù)據(jù)元素，設(shè)數(shù)組開始存放位置LOC(0)=a,且每個數(shù)據(jù)元素占用w個存儲單元,那么LOC(i)=Loc（0）+（i-1）*w 。已知廣義表B（e）,則GetHead(B)=e，GetTail(B)=1。五，判斷題1. 線性表的每個數(shù)據(jù)元素都有一個前驅(qū)和一個后繼。X 2廣度優(yōu)先搜索和深度優(yōu)先搜索是圖的兩種遍歷方法。 3廣義表（ ）和