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

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