數(shù)據(jù)結(jié)構(gòu)練習題

1、數(shù)據(jù)結(jié)構(gòu)練習題一、單項選擇題1、 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？（C）A. 隊列B. 棧 C. 二叉樹D. 線性表線性結(jié)構(gòu)：向量列表 堆棧 隊列非線性結(jié)構(gòu)：樹形 圖形2、 棧中元素的進出原則是（B ）A. 先進先出B.后進先出C.棧空則進D.棧滿則出3、 隊列中元素的進出原則是（A ）A. 先進先出B.后進先出C.隊空則進D.隊滿則出4、從邏輯上可以把數(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.初等結(jié)構(gòu)、構(gòu)造性結(jié)構(gòu)5、 在一顆二叉樹上第三層的節(jié)點數(shù)最多為（B ）。A.2B.4C.6D.86、由權(quán)值分別為11， 8， 6， 2， 5的葉

2、子結(jié)點生成一顆哈夫曼樹，它的帶權(quán)路徑長度為（A ）。A.71B.23C.48D.537、串是一種特殊的線性表，其特殊性體現(xiàn)在（B ）。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈式存儲D.數(shù)據(jù)元素可以是多個字符8、 （ B? ）遍歷方法在遍歷它的左子樹和右子樹后再遍歷它自身。A.先序遍歷 B. 后序遍歷C. 中序遍歷D. 層次遍歷9、 判斷一個循環(huán)隊列（ m0 為最大隊列長度（ 以元素為單位） ， front 和 rear 分別為隊列的隊頭指針和隊尾指針 , 則為滿隊列的條件是（ C ） 。A front= rearB front!= rearC front=（ rear+1） % m 0

3、 D front!=（ rear+1） % m 010、設(shè)有6 個結(jié)點的無向圖，該圖至少應(yīng)有（ A ） 條邊才能確保是一個連通圖。A.5B.6C.7D.811、 下列說法正確的是（A）A.數(shù)據(jù)是數(shù)據(jù)元素的基本單位B.數(shù)據(jù)元素是數(shù)據(jù)項中不可分割的最小標識單位C.數(shù)據(jù)可由若干個數(shù)據(jù)元素構(gòu)成D.數(shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成12、在以下的敘述中，正確的是（B）A.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進先出D.隊列的操作方式是先進后出13、與單鏈表相比，雙鏈表的優(yōu)點之一是（D）。A.插入、刪除操作更簡單B .可以進行隨機訪問C可以省略表頭指針或表

4、尾指針D.順序訪問相鄰結(jié)點更靈活第6頁，共5頁14、下面關(guān)于線性表的敘述中，錯誤的是哪一個 ？（B ）A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B.線性表采用順序存儲，便于進行插入和刪除操作。C.線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D.線性表采用鏈式存儲，便于進行插入和刪除操作。A.順序存儲占用連續(xù)空間，就像數(shù)組一樣。B.順序存儲的時候，插入和刪除需要移動插入和刪除點后面的數(shù)據(jù)。不方便。C.鏈接存儲不需連續(xù)空間，就像 LinkedList的實現(xiàn)一樣，一個結(jié)點的next指針指向下一個元素的位置D.鏈接存儲時，插入和刪除只需要修改指針的指向結(jié)點即可。15、在循環(huán)隊列中，若fron

5、t與rear分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條 件是（C）。A. front = = rear + 1C. front = = rearD16、對于循環(huán)隊列（D ）。A.無法判斷隊列是否為空C.隊列不可能滿D17、用的長度是指（B ）。A.用中所含不同字母的個數(shù)C申中所含不同字符的個數(shù)18、深度為5的二叉樹至多有（A. 16 B . 32B . rear = = front + 1.front = = 0B.無法判斷隊列是否為滿.以上說法都不對B .用中所含字符的個數(shù)D .用中所含非空格字符的個數(shù)C ）個結(jié)點。C . 31 C. 1019、在下述論述中，正確的是（D ）只有

6、一個結(jié)點的二叉樹的度為0;二叉樹的度為2;二叉樹的左右子樹可任意交換；深度為 K的順序二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A.B. C . D .20、采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（ A ） oA.先序遍歷B .中序遍歷C .后序遍歷D .按層遍歷這是因為圖的深度優(yōu)先遍歷算法先訪問所在結(jié)點，再訪問它的鄰接點。與二叉樹的先序遍歷先訪問子樹的根結(jié)點，再訪問它的孩子結(jié)點（鄰接點）類似。圖的廣度優(yōu)先遍歷算法類似于二叉樹的按層次遍歷。二、判斷題1、順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（f ）2、線性表采用鏈式存儲結(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以

7、是不連續(xù)的。（ f ）3、對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（f ）4、順序存儲方式只能用于存儲線性結(jié)構(gòu)。（f ）5、鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序表中效率高。（t ）6、雙向鏈表可隨機訪問任一結(jié)點。（f ）7、在哈夫曼樹中，權(quán)值最小的結(jié)點離根結(jié)點最近。（f ）8、強連通圖的各頂點間均可達。（t ）9、用是一種特殊的線性表，其特殊性體現(xiàn)在可以順序存儲。（f ）10、對于任意一個圖，從它的某個結(jié)點進行一次深度或廣度優(yōu)先遍歷可以訪問到該圖的每個頂點。（f ）11、StringBuilder 是非線程安全，StringBuffer 是線程安全的。

8、（t ）12、鏈式存儲結(jié)構(gòu)是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，借助元素（ 指針？ ?）在存儲器中的相對位置來表示數(shù)據(jù)元素之間邏輯關(guān)系。（f?）13、入棧和出棧操作只能在棧頂進行。（f ）14、用不是線性表。（f ）15、深度為5的二叉樹至少有5個結(jié)點。（t ）16、子用“str ”在主審" datastructure ”中的位置是5 （索引從1開始）。（t ）17、順序存儲結(jié)構(gòu)是通過指針（結(jié)點物理上相鄰）表示元素之間的關(guān)系的；鏈式存儲結(jié)構(gòu)是通過 （結(jié)點指針）下標表示元素之間的關(guān)系的。（f ）18、具有10個頂點的無向圖，邊的總數(shù)最多為 45。（ t ）19、數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合

9、、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。 （t ）20、數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，數(shù)據(jù)項是組成數(shù)據(jù)元素的基本單位。（t ）21、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯的角度來觀察數(shù)據(jù)，分析數(shù)據(jù)，與數(shù)據(jù)的存儲位置無關(guān)。（t ）22、單鏈接表可以按雙向遍歷線性表中的每一個數(shù)據(jù)元素。（）23、鏈表中刪除和插入操作比順序表快，但是元素的訪問速度比順序表要慢。（ t ）24、棧的主要特點是“先進先出”，隊列的主要特點是“后進先出”。（f ）25、前序遍歷是首先遍歷根結(jié)點的左子樹，再遍歷根結(jié)點的右子樹，最后訪問根結(jié)點。f26、用鏈表表示線性表的優(yōu)點是便于插入和刪除。（t ）27、入棧和出棧操作只能在棧頂進行。（f）28、

10、用不是線性表。（f）29、雙鏈接表可以按雙向遍歷線性表中的每一個數(shù)據(jù)元素。（）30、一個算法有至少一個或多個輸出。（t ）31、二叉樹的數(shù)據(jù)結(jié)構(gòu)描述了數(shù)據(jù)之間網(wǎng)狀關(guān)系。（t ）32、String是不可變字符串，StringBuffer 是可變字符串。（t ）三、填空題1、數(shù)據(jù)的存儲方式分為_軀序_存儲和_狙接_存儲。2、在一個長度為n的順序表中刪除第i個元素（1 & i季元素序號從1開始）時，則需向前移動_n-1 個元素。3、隊列的操作性質(zhì)是 先進先出；棧的操作性質(zhì)是后進先出 。4、設(shè) s='+ ama student 其長度是 _14。5、一個有7個頂點的無向圖最多有_21條

11、邊。公式：n（n-1）/26、圖的深度優(yōu)先搜索遍歷算法是一種遞歸算法，所以需要使用棧和遞歸算法 。7、數(shù)據(jù)的邏輯結(jié)構(gòu)共分為四類，分別為：集合、線性結(jié)構(gòu)、 樹形結(jié)構(gòu) 、 圖形結(jié)構(gòu)。8、一種順序表第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是08。9、在單鏈表中，一個結(jié)點包含兩部分內(nèi)容，分別為結(jié)點數(shù)據(jù)本身和指針。10、用 s= "cabcdefcde，si= "cde”,貝 s.indexOf（s1）的值為 4。11、圖的遍歷有廣度優(yōu)先遍歷和 深度優(yōu)先遍歷 兩種方法。12、對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小至少為n*n。13、若已知一個棧的入棧序列是 1, 2, 3,，n,其輸出序列為p1, p2, p3,，pn,若p1=n,則pi 為 n-i+1 o14、假設(shè) S= "abcaabcaaa