【文章內(nèi)容簡介】  head(tail (((a，b)，(c，d))))。⑥ 畫出下列廣義表的圖形表示:  D(A()，B(e)，C(a，L(b，c，d)))；
 M1(a，((b，c，d)，e))。4. 算法設(shè)計(jì)題(1) 設(shè)有三對角矩陣Ann，將其三條對角線上的元素逐行地存儲到向量B\[0..3n3\]中，使得B\[k\]=aij，求: ① 用i，j 表示k的下標(biāo)變換公式。② 用 k 表示 i，j 的下標(biāo)變換公式。 (2) 當(dāng)三角矩陣采用題(1)所述的壓縮存儲時，寫一算法求三對角矩陣在這種壓縮存儲表示下的轉(zhuǎn)置矩陣。(3) 當(dāng)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)時，試寫出矩陣相加的算法，其結(jié)果存放在三元組表C中。第6章 數(shù)組和廣義表 C++中數(shù)組的定義及抽象數(shù)據(jù)類型表示 C++中數(shù)組的定義 數(shù)組的抽象數(shù)據(jù)類型表示 數(shù)組的順序存儲結(jié)構(gòu) 矩陣的壓縮存儲 特殊矩陣的壓縮存儲1. 對稱矩陣的壓縮存儲2. 三角矩陣的壓縮存儲3. 對角矩陣的壓縮存儲圖67 對角矩陣 稀疏矩陣的壓縮存儲1. 三元組順序表2. 十字鏈表 廣義表的概念圖69 廣義表的圖形表示 廣義表的存儲結(jié)構(gòu)表示圖610 廣義表的存儲結(jié)構(gòu)示例 廣義表的運(yùn)算1. 廣義表結(jié)點(diǎn)類的存取成員函數(shù)2. 求廣義表的深度depth(LS)3. 廣義表的復(fù)制算法4. 廣義表的刪除算法圖611 廣義表的刪除示例5. 從字符串s建立廣義表的鏈表表示ls圖612 從字符串建立的廣義鏈表小結(jié)習(xí)題1. 判斷題(1) 數(shù)組是同類型值的集合。( )(2) 數(shù)組是一組相繼的內(nèi)存單元。( )(3) 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，既不是線性的，也不是樹形的。( )(4) 插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。( )(5) 使用三元組表表示稀疏矩陣的元素，有時并不能節(jié)省存儲空間。( )(6) 廣義表是由零或多個單元素或子表所組成的有序列，所以廣義表可能為空表。( )(7) 線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是單元素，則廣義表便成為線性表。( )(8) 線性表的邏輯順序與物理順序總是一致的。( )(9) 線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎尽? )(10) 每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算: 插入、刪除和搜索。( )2. 單選題(1) 設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯?，a11為第一個元素，其存儲地址為1，每個元素占1個地址空間，則a85的地址為( )。 A) 13 B) 33C) 18D) 40 (2) 一個nn的對稱矩陣，如果以行或列為主序存入內(nèi)存，則其容量為( )。 A) n2 B) n2/2 C) n(n+1)/2 D) (n+1)(n+1)/2 E) (n1)n/2 F) n(n1) (3) 二維數(shù)組a的每個元素是由6個字符組成的串，行下標(biāo)i的范圍從0～8，列下標(biāo)j的范圍是從1～10。從供選擇的答案中選出正確答案填入下列關(guān)于數(shù)據(jù)存儲敘述中的( )內(nèi)。① 存放a至少需要( )字節(jié)。 A) 90 B) 180 C) 240 D) 270 E) 540 ② a的第8列和第5行共占( )字節(jié)。 A) 108 B) 114 C) 54 D) 60 E) 150 ③ 若a按行存放，元素a\[8，5\]的起始地址與當(dāng)a按列存放的元素( )的起始地址一致。 A) a\[8，5\] B) a\[3，10\] C) a\[5，8\] D) a\[0，9\] (4) 已知廣義表LS=(a，(b，c，d)，e)，運(yùn)用head和tail函數(shù)取出LS中單元素b的運(yùn)算是( )。 A) head(head(LS)) B) tail(head(LS)) C) head(head(tail(LS))) D) head(tail(LS)) (5) 已知廣義表A=((a，b，c)，(d，e，f))，從A中取出單元素e的運(yùn)算是( )。 A) tail(head(A)) B) head(tail(A)) C) head(tail(tail(head(A)))) D) head(tail(head(tail(A))))3. 綜合題(1) 畫出下列廣義表的圖形表示和它們的存儲表示: ① D(A(c)， B(e)， C(a， L(b， c， d)))② J1(J2(J1， a， J3(J1))， J3(J1)) (2) 利用廣義表的head和tail操作寫出函數(shù)表達(dá)式，把以下各題中的單元素banana從廣義表中分離出來: ① L1(apple， pear， banana， orange)② L2((apple， pear)， (banana， orange))③ L3(((apple)， (pear)， (banana)， (orange)))④ L4((((apple)))， ((pear))， (banana)， orange)⑤ L5((((apple)， pear)， banana)， orange)⑥ L6(apple， (pear， (banana)， orange)) (3) 廣義表具有可共享性，因此在遍歷一個廣義表時必須為每一個結(jié)點(diǎn)增加一個標(biāo)志域mark，以記錄該結(jié)點(diǎn)是否訪問過。一旦某一個共享的子表結(jié)點(diǎn)被作了訪問標(biāo)志，以后就不再訪問它。① 試定義該廣義表的類結(jié)構(gòu)。② 采用遞歸的算法對一個非遞歸的廣義表進(jìn)行遍歷。③ 試使用一個棧，實(shí)現(xiàn)一個非遞歸算法，對一個非遞歸廣義表進(jìn)行遍歷。(4) 編寫函數(shù)，對一個下三角矩陣和一個上三角矩陣進(jìn)行乘法運(yùn)算(兩個矩陣都是按行的方式存儲在一個一維數(shù)組中)，所得到的結(jié)果用一個二維數(shù)組來描述。函數(shù)的時間復(fù)雜性是多少？(5) 假設(shè)有一個1010的對稱矩陣A\[10\]\[10\]，采用按行壓縮存儲的方式存放于一個一維數(shù)組B\[\]中，則數(shù)組B\[\]的容量應(yīng)有多大？若設(shè)A\[0\]\[0\]為第一個元素，存放于B\[0\]， 并且矩陣A\[\]\[\]的每一個數(shù)組元素在數(shù)組B\[\]中占一個數(shù)組元素的位置，則A\[8\]\[5\] 在數(shù)組B\[\]中的位置是多少？(6) 畫圖及計(jì)算題① 給定一奇數(shù)n，構(gòu)造一個n階魔陣。n階魔陣是一個n階方陣，其元素由自然數(shù)1，2，3，…，n組成。魔陣的每行元素之和，每列元素之和以及主、副對角線之和均相等。即對于給定的奇數(shù)n以及i=1，2，…，n，魔陣A滿足條件:∑n[]k=1aik=∑n[]k=1aki=∑n[]k=1akk=∑n[]k=1ak,nk+1 ② 設(shè)有一每行每列都有8個正方格的棋盤。試用8個棋子分布到格子上，要求滿足以下條件:  任意兩個棋子不在同一行和同一列； 任意兩個棋子不在同一斜線上。問有多少種擺法。③ 設(shè)B(nm)是一個二維對稱數(shù)組，為節(jié)省存儲單元，只將上三角的元素存于內(nèi)存中，試推導(dǎo)元素B{i，j}(0≤i≤n，0≤j≤m)的位置的公式。④ 求三維數(shù)組按行優(yōu)先順序存儲的地址公式。⑤ 求下列廣義表運(yùn)算的結(jié)果 head((p，h，w))； tail((b，k，p，h))； head(tail (((a，b)，(c，d))))。⑥ 畫出下列廣義表的圖形表示:  D(A()，B(e)，C(a，L(b，c，d)))； M1(a，((b，c，d)，e))。4. 算法設(shè)計(jì)題(1) 設(shè)有三對角矩陣Ann，將其三條對角線上的元素逐行地存儲到向量B\[0..3n3\]中，使得B\[k\]=aij，求: ① 用i，j 表示k的下標(biāo)變換公式。② 用 k 表示 i，j 的下標(biāo)變換公式。 (2) 當(dāng)三角矩陣采用題(1)所述的壓縮存儲時，寫一算法求三對角矩陣在這種壓縮存儲表示下的轉(zhuǎn)置矩陣。(3) 當(dāng)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)時，試寫出矩陣相加的算法，其結(jié)果存放在三元組表C中。第7章 樹 樹的基本概念 樹的定義圖71 樹的示例圖72 非樹結(jié)構(gòu)的示例 樹的表示形式圖73 樹的其他表示形式 樹的常用術(shù)語 樹的基本操作 一個樹的接口 樹的基本算法 二叉樹 二叉樹的定義圖74 二叉樹示意圖圖75 二叉樹的五種基本形態(tài)圖76 滿二叉樹圖77 完全二叉樹和非完全二叉樹 二叉樹的性質(zhì)圖78 完全二叉樹中結(jié)點(diǎn)i和i+1的左、右孩子 二叉樹的接口 二叉樹的存儲結(jié)構(gòu)1. 順序存儲結(jié)構(gòu)圖79 帶有結(jié)點(diǎn)編號的完全二叉樹圖710 二叉樹的順序存儲結(jié)構(gòu)圖711 添上虛結(jié)點(diǎn)后的完全二叉樹2. 鏈?zhǔn)酱鎯Y(jié)構(gòu)圖712 二叉樹的結(jié)點(diǎn)及其存儲結(jié)構(gòu)圖713 二叉樹的二叉鏈表及三叉鏈表存儲結(jié)構(gòu)圖 二叉樹的遍歷1. 前序遍歷二叉樹(DLR)2. 中序遍歷二叉樹(LDR)
3. 后序遍歷二叉樹(LRD)4. 二叉樹的層次遍歷 二叉樹遍歷的應(yīng)用圖714 表達(dá)式(a+b*(cd)e/f)的二叉樹 線索二叉樹 線索二叉樹的類定義圖715 中序線索二叉樹及其存儲結(jié)構(gòu)圖716 后序后繼線索二叉樹(虛線表示線索) 中序線索二叉樹1. 建立中序線索二叉樹2. 中序線索化二叉樹中的部分成員函數(shù)的實(shí)現(xiàn)3. 在中序線索樹二叉樹上插入結(jié)點(diǎn) 樹、森林和二叉樹的關(guān)系 樹的存儲結(jié)構(gòu)1. 雙親表示法圖717 樹的雙親表示法示例2. 孩子表示法圖718 圖717(a)中樹的另外兩種表示法3. 孩子兄弟表示法圖719 圖717中樹的孩子兄弟鏈表 森林與二叉樹的轉(zhuǎn)換1. 樹、森林轉(zhuǎn)換成二叉樹圖720 樹與二叉樹之間的關(guān)系圖721 森林與二叉樹的關(guān)系圖722 圖721(a)的森林轉(zhuǎn)換為二叉樹的過程2. 二叉樹轉(zhuǎn)換成樹、森林圖723 圖721(c)的二叉樹轉(zhuǎn)換為森林 樹和森林的遍歷1. 前序遍歷森林2. 后序遍歷森林圖724 森林和對應(yīng)的二叉樹 霍夫曼樹及其應(yīng)用 霍夫曼樹的定義圖725 具有不同帶權(quán)路徑長度的二叉樹 霍夫曼樹的構(gòu)造圖726 一棵霍夫曼樹的構(gòu)造過程 霍夫曼樹在編碼問題中的應(yīng)用圖727 前174。綴編碼示例小結(jié)習(xí)題1. 判斷題(1) 二叉樹是樹的特殊形式。( )(2) 由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的。( )
(3) 前序遍歷樹和前序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同。( )(4) 后序遍歷樹和中序遍歷與該樹對應(yīng)的二叉樹，其結(jié)果不同。( )(5) 前序遍歷森林和前序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同。( )(6) 后序遍歷森林和中序遍歷與該森林對應(yīng)的二叉樹，其結(jié)果不同。( )(7) 在二叉樹中插入結(jié)點(diǎn)后，該二叉樹就不是二叉樹。( )(8) 霍夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。( )(9) 用一維數(shù)組存放二叉樹時，總是以前序遍歷存儲結(jié)點(diǎn)。( )2. 選擇題(1) 有一棵二叉樹，如圖728所示該二叉樹是( )。圖728 A) 二叉平衡樹B) 二叉排序樹 C) 堆的形狀 (2) 線索化二叉樹中某結(jié)點(diǎn)沒有孩子的充要條件是( )。 A) =NULL B) =1 C) =0 (3) 如果結(jié)點(diǎn)A有3個兄弟，而且B是A的雙親，則B的度是( )。 A) 4 B) 5 C) 1 (4) 樹B的層號表示1a，2b，3d，3e，2c 對應(yīng)于下面的( )。 A) 1a\[2b\[3d，3e\]，2c\] B) a\[b\[d\]，e\]，c\] C) a\[b，d\[e，c\]\] D) a\[b\[d，e\]，c\] (5) 某二叉樹T有n個結(jié)點(diǎn)，設(shè)按某種順序?qū)中的每個結(jié)點(diǎn)進(jìn)行編號，編號值為1，2，…,n。且有如下性質(zhì): T中任意結(jié)點(diǎn)V，其編號等于左子樹上的最小編號減1，而V的右子樹的結(jié)點(diǎn)中，其最小編號等于V左子樹上結(jié)點(diǎn)的最大編號加1，這是按( )編號的。 A) 中序遍歷序列B) 前序遍歷序列C) 后序遍歷序列(6) 設(shè)F是一個森林；B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點(diǎn)，B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有( )個。 A) n1 B) n C) n+1 D) n+2 (7) 前序遍歷的順序是( )。 A) 根結(jié)點(diǎn)，左子樹，右子樹 B) 左子樹，根結(jié)點(diǎn)，右子樹 C) 右子樹，根結(jié)點(diǎn)，左子樹 D) 左子樹，右子樹，根結(jié)點(diǎn) (8) 中序遍歷的順序是( )。 A) 根結(jié)點(diǎn)，左子樹，右子樹 B) 左子樹，根結(jié)點(diǎn)，右子樹 C) 右子樹，根結(jié)點(diǎn)，左子樹 D) 左子樹，右子樹，根結(jié)點(diǎn) (9) 后序遍歷的順序是( )。 A) 根結(jié)點(diǎn)，左子樹，右子樹 B) 左子樹，根結(jié)點(diǎn)，右子樹 C) 右子樹，