數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題.doc

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