數(shù)據(jù)結構復習題.doc

一、判斷題1、 線性表的邏輯順序與存儲順序總是一致的。2、 順序存儲的線性表可以按序號隨機存取。3、線性表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動。4、線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有同樣的特性，因此是屬于同一數(shù)據(jù)對象。5、在線性表的順序存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。6、在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理位置上不一定緊鄰。7、線性表的鏈接存儲結構優(yōu)于順序存儲結構。8、在線性表的順序存儲結構中，插入和刪除時，移動元素的個數(shù)與該元素的位置有關。9、若采用三元組壓縮技術存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置運算。10、線性表的鏈接存儲結構是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。11、在鏈表中，要取得某個元素，只要知道指向該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。12、二叉樹是樹的特殊形式。T13、由樹轉換成二叉樹，其根結點右子樹總是空的。F14、先根遍歷一顆樹和前序遍歷與該樹對應的二叉樹，其結果不同。F15、后根遍歷一顆樹和中序遍歷與該樹對應的二叉樹，其結果不同。T16、前根遍歷森林和前序遍歷與該森林對應的二叉樹，其結果不同。17、后根遍歷森林和中序遍歷與該森林對應的二叉樹，其結果不同。18、不使用遞歸也可實現(xiàn)二叉樹的前序、中序和后序遍歷。T19、若一個結點是某二叉樹子樹的中序遍歷序列中的最后一個結點，則它必是該子樹的前序遍歷序列中的最后一個結點。F20、若一個結點是某二叉樹子樹的中序遍歷序列中的第一個結點，則它必是該子樹的后序遍歷序列中的第一個結點。F21、不用遞歸也可實現(xiàn)二叉樹的前序、中序和后序遍歷。T22、在具有n個結點的二叉樹的標準表示形式中，共有n個空指針。23、滿二叉樹一定是完全二叉樹。T24、在Huffman編碼中，出現(xiàn)頻率相同的字符編碼長度也一定相同。F25、Huffman樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根最近。T26、由前序序列和后序序列能唯一確定一棵二叉樹。F27、由前序序列和中序序列能唯一確定一棵二叉樹。T28、由中序序列和后序序列不能唯一確定一棵二叉樹。F29、完全二叉樹可采用順序存儲結構實現(xiàn)存儲，非完全二叉樹則不能。T二、選擇題1、用鏈表表示線性表的優(yōu)點是 （ ）。 A 便于隨機存取 B 花費的存儲空間較順序存儲少 C 便于插入和刪除 D 數(shù)據(jù)元素的物理順序與邏輯順序相同2、稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）。 A 二維數(shù)組和三維數(shù)組 B 三元組和散列 C 三元組和十字鏈表 D 散列和十字鏈表3、線性表若采用鏈接存儲結構時，要求內存中可用存儲單元的地址（ ）。 A 必須是連續(xù)的 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的 D 連續(xù)不連續(xù)都可以4、串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 A 可以順序存儲 B 數(shù)據(jù)元素是一個字符 C 可以鏈接存儲 D 數(shù)據(jù)元素可以是多個字符5、對順序存儲的線性表，設其長度是n，在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的（ ）個元素。 A n/2 B (n+1)/2 C (n-1)/2 D n6、在數(shù)據(jù)結構中，從邏輯上把數(shù)據(jù)結構分為（ ）。 A 動態(tài)結構和靜態(tài)結構 B 緊湊結構和非緊湊結構 C 線性結構和非線性結構 D 內部結構和外部結構7、設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為（ ）。 A 連接 B 模式匹配 C 求子串 D 求串長8、棧結構通常采用的兩種存儲結構是（ A ）。 A、 順序存儲結構和鏈表存儲結構 B、 散列方式和索引方式 C、 鏈表存儲結構和數(shù)組 D、 線性存儲結構和非線性存儲結構9、數(shù)組通常具有的兩個基本操作是（ ） A、 建立和刪除 B、 索引和修改 C、 查找和修改 D、 查找和索引10、棧和隊列的共同點是 （ ）。 A、 都是先進后出 B、 都是先進先出 C、 只允許在端點處插入和刪除元素 D、 沒有共同點三、程序填空題四、回答下列問題1、 設有五個結點，結點關鍵字值分別為A、B、C、D、E，權值分別是4、3、3、2、1，畫出對應的Huffman（哈夫曼）樹。2、寫出下圖所示二叉樹按前序、中序、后序和層次遍歷得到的結點序列。3、已知稀疏矩陣A如下，寫出對應的三元組表示： A: 。4、給出下列上三角矩陣的壓縮存儲地址表示a00 a01 a 0 n-1 c a11 a 1 n-1 . c c a n-1 n-15、給出下圖的前根、后根遍歷結點序列6、給出下圖中各頂點的度（分入度和出度）7、給出下圖的鄰接矩陣8、已知下圖，給出按prim算法得出的最小生成樹五、編寫下列函數(shù)（第一題5分，第二題10分，共15分）1、已知單鏈表H，寫一個算法將其倒置。2、一棵n個結點的完全二叉樹以向量作為存儲結構，試設計非遞歸算法對該完全二叉樹進行前序遍歷。3、已知不帶頭結點的單鏈表H，寫一個算法求其表長。4、給定一棵二叉樹，其根指針為root，試寫出求二叉樹結點的數(shù)目的算法。5、假使A、B是兩個按結點值從小到大排列的線性鏈表，編寫一個將這兩個有序的線性鏈表歸并為一個按結點值從小到大排列的線性鏈表java的函數(shù)。先根次序：訪問根結點，遍歷左子樹，遍歷右子樹。（根左右）中根次序：