資源簡介

1.初識數(shù)據(jù)結構
【要點提示】
1.瑞士計算機科學家沃斯指出“___________________”,形象地闡明了計算機程序設計的本質是______________________的設計。
2.數(shù)據(jù)結構的概念：
(1)數(shù)據(jù)元素：數(shù)據(jù)的______單位，可由若干數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的______數(shù)據(jù)表示單位。
(2)數(shù)據(jù)類型：具有__________的計算機數(shù)據(jù)的集合及在這個數(shù)據(jù)集合上的一組操作。數(shù)據(jù)類型可分為__________和__________。
(3)數(shù)據(jù)結構：數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的__________。主要包含數(shù)據(jù)的__________、數(shù)據(jù)的__________和數(shù)據(jù)的________。
3.常見的數(shù)據(jù)結構
(1)數(shù)組：表示一批數(shù)據(jù)，不僅可以描述數(shù)據(jù)本身，還可以描述數(shù)據(jù)所處的位置或數(shù)據(jù)之間的前后順序關系。可以迅速地通過______精確訪問序列中的某個數(shù)據(jù)元素，又可以通過下標按順序______序列中的每個元素。
(2)鏈表：表示一批數(shù)據(jù)，這類數(shù)據(jù)之間具有明確的相互鏈接的___________，但對數(shù)據(jù)對象本身的___________不作要求。常用的鏈表有單向鏈表、雙向鏈表、循環(huán)鏈表。
(3)隊列：數(shù)據(jù)具有“____________”且中間__________的組織和操作的性質。在數(shù)據(jù)序列的頭部（稱為隊首）進行數(shù)據(jù)的讀取（即出隊），在數(shù)據(jù)序列的尾部（稱為隊尾）進行數(shù)據(jù)的插入（即入隊）。
(4)棧：數(shù)據(jù)具有“___________”且所有操作只能在一端（稱為棧頂）進行的性質。僅可在一端進行數(shù)據(jù)的讀取(稱為出棧)和插入（稱為入棧）操作。
(5)樹：數(shù)據(jù)元素前面只有一個元素，后面可以有______________元素相鄰，所有元素之間的關系特征像一棵倒放的樹。
4.對于同一問題，若依據(jù)不同的數(shù)據(jù)結構來設計算法，則算法的處理效率、程序的實現(xiàn)效率也會_______。
限時訓練
1.以下關于數(shù)據(jù)結構的描述，不正確的是( )
A.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間的邏輯排列和對應關系
B.數(shù)據(jù)的存儲結構包括數(shù)據(jù)元素的存儲及數(shù)據(jù)元素之間關系的存儲
C.數(shù)據(jù)的運算是指對數(shù)據(jù)施加的操作，包括刪除、查找、插入數(shù)據(jù)等
D.數(shù)據(jù)結構設計時不需要考慮編程實現(xiàn)和數(shù)據(jù)處理的效率
2.數(shù)據(jù)元素及其關系在計算機存儲器內(nèi)的表示，也稱為數(shù)據(jù)的( )
A.線性結構 B.物理結構 C.邏輯結構 D.空間結構
3.下列數(shù)據(jù)結構中屬于線性數(shù)據(jù)結構的是( )
①數(shù)組 ②棧 ③隊列 ④鏈表 ⑤樹
A.①②③④⑤ B.①②③④ C.①②④⑤ D.①②③⑤
4.用一帶蓋的玻璃筒來放取乒乓球，放、取球只能在帶蓋的一端進行（另一端為封閉狀態(tài))，且筒的直徑只允許一個乒乓球進出。若放入球的編號序列為1、2、3、4，則取出球的編號序列不可能的是( )
A.1、2、3、4 B.2、3、4、1 C.4、2、3、1 D.3、2、1、4
5.關于數(shù)據(jù)項與數(shù)據(jù)元素的描述，下面說法不正確的是( )
A.數(shù)據(jù)元素可由若干數(shù)據(jù)項組成
B.同一數(shù)據(jù)元素中各數(shù)據(jù)項的數(shù)據(jù)類型必須相同
C.數(shù)據(jù)項是數(shù)據(jù)的最小單位，通常用來描述實體的某種屬性
D.數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體來處理
6.諸葛亮家族的部分家譜如圖所示。和家譜圖結構相似的數(shù)據(jù)結構是( )
A.鏈表
B.隊列
C.樹
D.棧
7.在日常幻燈片（如PowerPoint演示文稿）的放映中，可以通過超鏈接的方式進行幻燈片之間的任意跳轉。與這種頁面之間相互鏈接的表現(xiàn)形式相似的數(shù)據(jù)結構是( )
A.樹 B.鏈表 C.隊列 D.棧
8.數(shù)據(jù)結構中棧和隊列的共同特點是( )
A.都是先進后出 B.都是先進先出
C.只允許在端點處插入和刪除數(shù)據(jù) D.沒有共同點
9.小陳同學高一結束后需要換寢室，他將全部物品打包成6個箱子并編號疊放在一起（如圖1-10所示）。為了搬運物品方便，他借了一輛手推車，該手推車一次最多能疊放3個箱子（如圖1-11所示）箱子從上往下依次疊放在小推車上（假定每次只放一個箱子），小推車每次可以疊放1、2或3個箱子，小推車上的箱子也是從上往下依次拿取（假定每次只取一個箱子），搬運后的箱子仍引舊疊放在一起。
(1)在搬運中，與手推車上箱子疊放和拿取的過程相似的數(shù)據(jù)結構是___棧_______
(2)若搬運完畢后箱子的疊放順序是2、1、3、4、6、5（從下往上），則每趟手推車至多需要搬運的箱子數(shù)是___2_____個。
(3)在每趟搬運時手推車上的箱子必須全部搬離的情況下：
請寫出至少2個搬運完畢后箱子可能的疊放（從下往上）順序：_123456___、_321654___
請寫出至少1個搬運完畢后不可能的箱子疊放（從下往上）順序：___342165_________
10.線性表是由零個或多個數(shù)據(jù)元素組成的有限序列，數(shù)據(jù)元素之間的關系是一對一的關系。線性表是一種基本的、常見的數(shù)據(jù)結構，可以根據(jù)需要向線性表中添加元素或者刪除元素。數(shù)組、隊列、棧、鏈表都是線性表的特殊形式。
小林使用數(shù)組、鏈表、隊列和棧這四種數(shù)據(jù)結構，分別實現(xiàn)線性表中數(shù)據(jù)元素的刪除操作，以探究這幾種數(shù)據(jù)結構在數(shù)據(jù)刪除操作中的特點。現(xiàn)假設有10個數(shù)據(jù)元素的線性表（數(shù)據(jù)不重復)，以刪除數(shù)據(jù)元素“4”為例進行分析(10個數(shù)據(jù)元素的順序表如圖所示)，數(shù)據(jù)刪除后其余數(shù)據(jù)元素的相對位置保持不變。
補充完整以下分析過程：
(1)數(shù)組存儲：
如圖所示，從a[0]開始找到數(shù)組元素“4”需要查找3次，刪除“4”后，其后續(xù)數(shù)組元素需要往前移動___7____次；此時數(shù)組元素a[2]的值為__1_____, a[9]的值為____5___
(2)單鏈表存儲：
如圖1-14所示，從第1個節(jié)點的數(shù)據(jù)元素“2”開始找到數(shù)據(jù)元素“4”（出隊元素依次在隊尾入隊）需要查找___3___次，刪除該節(jié)點（如圖1-15所示），其后續(xù)節(jié)點需要移動___0___
次；此時鏈表中數(shù)據(jù)元素的個數(shù)為__9____個。
(3)隊列存儲：
如圖1-16所示，從隊首查找需要出隊3次找到數(shù)據(jù)元素“4”（出隊元素依次在隊尾入隊），刪除該元素后，為了保持原隊列其他數(shù)據(jù)元素的次序不變，還需出隊__7__次，入隊_7___次；此時隊列中數(shù)據(jù)元素的個數(shù)為_9___個。
(4)棧存儲：
如圖1-17所示，從棧頂查找需要出棧_3___次找到數(shù)據(jù)元素“4”，刪除該元素后，為了保持原棧內(nèi)其他數(shù)據(jù)元素的次序不變，還需入棧__2__次；此時棧頂指向的數(shù)據(jù)元素為__2_____
11.有如下圖所示的單向鏈表：
從頭指針head指向的節(jié)點開始查找數(shù)據(jù)元素“5”，并刪除該節(jié)點，下列說法正確的是（ ）
A.共需查找3次
B.刪除數(shù)據(jù)元素“5”的節(jié)點，后續(xù)節(jié)點需要移動3次
C.頭指針head將指向數(shù)據(jù)元素“7”的節(jié)點
D.此時鏈表中數(shù)據(jù)元素的個數(shù)為6個
12.數(shù)組b中存儲的數(shù)據(jù)情況如下圖所示：
b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] b[9]
20 12 8 6 9 5 10 7 18 11
要在數(shù)組元素b[2]后面插入數(shù)據(jù)“17”，則數(shù)組元素需要往后移動的次數(shù)為( )
A.0 B.3 C.4 D.7
13.隊列Q1的存儲情況如下圖所示：
要查找并得到數(shù)據(jù)元素“3”，則需要隊列Q1中的元素出隊次數(shù)為( )
A.1 B.3 C.4 D.6
14.設棧S和隊列Q的初始狀態(tài)為空，元素w1、w2、w3、w4、w5依次通過棧S,一個元素出棧后即進入隊列Q,下列不可能是出隊序列的是( )
A.w5、w4、w3、w2、w1 B.w3、w2、w1、w4、w5
C.w4、w2、w1、w3、w5 D.w1、w2、w3、w4、w5
15.下列對數(shù)據(jù)結構的描述正確的是( )
A.邏輯結構相鄰的兩個數(shù)據(jù)元素，其存儲位置也一定相鄰
B.對于同一個問題，只能使用一種數(shù)據(jù)結構來設計算法并解決
C.選擇的數(shù)據(jù)結構不同，算法的處理效率、程序的運行效率也不同
D.對同一操作（如刪除、插入數(shù)據(jù)），不同的數(shù)據(jù)結構實現(xiàn)的方法相同
16.關于數(shù)組和鏈表，以下描述不正確的是( )
A.數(shù)組通過下標訪問或遍歷序列中的數(shù)據(jù)元素
B.常見的鏈表有單向鏈表、雙向鏈表和循環(huán)鏈表
C.一般情況下，數(shù)組元素的插入和刪除效率比鏈表要低
D.一般情況下，數(shù)組元素的查找效率比鏈表要低
17.下列關于數(shù)據(jù)結構的描述，正確的是（ ）
A.數(shù)據(jù)的物理結構是指數(shù)據(jù)元素之間的邏輯排列和對應關系
B.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素及其關系在計算機存儲器內(nèi)的表示
C.數(shù)據(jù)的運算是指對數(shù)據(jù)施加的操作，但僅包括插入和刪除數(shù)據(jù)
D.數(shù)據(jù)結構設計的目的是使數(shù)據(jù)元素間的相互關系能準確地反映現(xiàn)實問題中的事物邏輯

展開更多......

收起↑