數(shù)據(jù)結(jié)構(gòu)(C++版)課后作業(yè)1-6章帶答案

1、.第 1 章緒 論課后習(xí)題講解1. 填空(1)從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（）、（ ）、（ ）和（ ）。(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有（）和（ ）兩種基本方法，不論哪種存儲(chǔ)結(jié)構(gòu)，都要存儲(chǔ)兩方面的內(nèi)容：（ ）和（ ）。(3)算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為（）。2.選擇題 順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的。 A 線性結(jié)構(gòu) B 非線性結(jié)構(gòu)C 存儲(chǔ)位置D 指針 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（）。 A

2、樹(shù) B 圖 C 線性表 D 集合3.判斷題(1) 每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本操作：插入、刪除和查找。第 2 章線性表課后習(xí)題講解1. 填空 順序表中第一個(gè)元素的存儲(chǔ)地址是100 ，每個(gè)元素的長(zhǎng)度為2，則第 5 個(gè)元素的存儲(chǔ)地址是（）。第 5個(gè)元素的存儲(chǔ)地址= 第1個(gè)元素的存儲(chǔ)地址(5 1) 2=108 設(shè)單鏈表中指針p 指向結(jié)點(diǎn) A，若要?jiǎng)h除 A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（ ）。【解答】 p-next=(p-next)-next 非空的單循環(huán)鏈表由頭指針head 指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（）。 p-next=head 在由尾指針 rear 指示的單循環(huán)鏈

3、表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（）；刪除開(kāi)始結(jié)點(diǎn)的操作序列為（）。 【解答】 s-next =rear-next; rear-next =s; rear =s; q=rear-next-next;rear-next-next=q-next; delete q;2. 選擇題 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)， 線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)。A 隨機(jī)存取B 順序存取C 索引存取D 散列存取【解答】 A，B 【分析】參見(jiàn) 2.2.1 。 線性表采用鏈接存儲(chǔ)時(shí)，其地址（）。A 必須是連續(xù)的B 部分地址必須是連續(xù)的C 一定是不連續(xù)的 D 連續(xù)與否均可以【解答】 D 【分析】

4、線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。 單循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。A 不再需要頭指針了B 從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表；C 已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨；D 在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈1 / 6.表不斷開(kāi)?！窘獯稹?B 鏈表不具有的特點(diǎn)是（）。 A 可隨機(jī)訪問(wèn)任一元素B 插入、刪除不需要移動(dòng)元素C 不必事先估計(jì)存儲(chǔ)空間 D 所需空間與線性表長(zhǎng)度成正比. 【解答】 A 若某線性表中最常用的操作是取第i 個(gè)元素和找第 i個(gè)元素的前趨， 則采用（ ）存儲(chǔ)方法最節(jié)省時(shí)間。

5、 A順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表【解答】 A 【分析】線性表中最常用的操作是取第i 個(gè)元素，所以，應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即順序表，同時(shí)在順序表中查找第i個(gè)元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第i個(gè)元素的前趨也不方便，雙鏈表雖然能快速查找第i個(gè)元素的前趨，但不能實(shí)現(xiàn)隨機(jī)存取。 使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以（）。 A 提高查找速度 B 更方便數(shù)據(jù)的插入和刪除C 節(jié)約存儲(chǔ)空間 D 很快回收存儲(chǔ)空間【解答】 B 【分析】在鏈表中一般只能進(jìn)行順序查找，所以，雙鏈表并不能提高查找速度，因?yàn)殡p鏈表中有兩個(gè)指針域，顯然不能節(jié)約存儲(chǔ)空間，對(duì)于動(dòng)態(tài)存儲(chǔ)分配，回收存儲(chǔ)空

6、間的速度是一樣的。由于雙鏈表具有對(duì)稱性，所以，其插入和刪除操作更加方便。 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是 p所指結(jié)點(diǎn)的直接前驅(qū)，若在q 和p之間插入 s所指結(jié)點(diǎn)，則執(zhí)行（）操作。A s-next=p-next; p-next=s; B q-next=s; s-next=p; C p-next=s-next; s-next=p; Dp-next=s; s-next=q;【解答】 B，本題答案不是非常合理，應(yīng)該換順序更好！考試可以修改說(shuō): 已知 q所指結(jié)點(diǎn) , 在 q后面插入一個(gè)節(jié)點(diǎn)。 在循環(huán)雙鏈表的p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn)的操作是（）。 A p-next=s; s-prior=p;p-nex

7、t-prior=s; s-next=p-next; B p-next=s; p-next-prior=s; s-prior=p; s-next=p-next; Cs-prior=p; s-next=p-next; p-next=s; p-next-prior=s; D s-prior=p; s-next=p-next;p-next-prior=s; p-next=s【解答】 D3. 判斷題 線性表的邏輯順序和存儲(chǔ)順序總是一致的?！窘獯稹垮e(cuò)。順序表的邏輯順序和存儲(chǔ)順序一致，鏈表的邏輯順序和存儲(chǔ)順序不一定一致。 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)。 線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接

8、前驅(qū)和一個(gè)直接后繼。【解答】錯(cuò)。每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒(méi)有前驅(qū)，最后一個(gè)元素沒(méi)有后繼。 在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)。【解答】錯(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指針開(kāi)始查找，所以單鏈表是順序存取結(jié)構(gòu)。4請(qǐng)說(shuō)明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲(chǔ)結(jié)構(gòu)更好些。 若線性表的總長(zhǎng)度基本穩(wěn)定， 且很少進(jìn)行插入和刪除操作， 但要求以最快的速度存取線性表中的元素。 如果 n 個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化。 描述一個(gè)城市的設(shè)計(jì)和規(guī)劃?！窘獯稹宽樞虮淼膬?yōu)點(diǎn)：無(wú)需為表示表中元

9、素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；可以快速地存取表中任一位置的元素（即隨機(jī)存?。?。順序表的缺點(diǎn)：插入和刪除操作需移動(dòng)大量元素；表的容量難以確定； 造成存儲(chǔ)空間的 “碎片 ”。 單鏈表的優(yōu)點(diǎn)：不必事先知道線性表的長(zhǎng)度；插入和刪除元素時(shí)只需修改指針，不用移動(dòng)元素。單鏈表的缺點(diǎn)：指針的結(jié)構(gòu)性開(kāi)銷；存取表中任意元素不方便，只能進(jìn)行順序存取。 應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取結(jié)構(gòu)，單鏈表是順序存取2 / 6. 構(gòu)。本 很少 行插入和 除操作， 所以空 化不大， 且需要快速存取， 所以 用 序存 構(gòu)。 用 接存 構(gòu)。 表容易 表容量的 充，適合表的 度 生 化。 用 接存 構(gòu)。 因 一個(gè)城市的

10、 和 劃涉及活 很多， 需要 常修改、 充和 除各種信息，才能適 不斷 展的需要。而 序表的插入、 除的效率低，故不合適。5算法 (1) 假 在 度大于 1 的循 表中，即無(wú) 點(diǎn)也無(wú) 指 ， s 指向 表中某個(gè) 點(diǎn)的指 ， 寫算法 除 點(diǎn) s的前 點(diǎn)。第 3 章特殊線性表 棧、隊(duì)列和串課后習(xí)題講解1. 填空 有一個(gè)空 ， 指 1000H ， 有 入序列 1、 2、3 、4、 5， 經(jīng)過(guò) push ， push ， pop ，push ，pop ，push ，push 后， 出序列是（）， 指 （）?！窘獯稹?23 ， 1003H 通常采用的兩種存 構(gòu)是（）；其判定 空的條件分 是（），判定 的

11、條件分 是（）?！窘獯稹?序存 構(gòu)和 接存 構(gòu)（或 序 和 ）， 指 top= -1 和 top=NULL ， 指 top等于數(shù) 的 度和內(nèi)存無(wú)可用空 （）可作 函數(shù) 用的一種數(shù)據(jù) 構(gòu)。( 或者 列 一個(gè))【解答】 【分析】 函數(shù)的 用和返回正好符合后 先出性。 和 列是兩種特殊的 性表， 的操作特性是（）， 列的操作特性是（）， 和 列的主要區(qū) 在于（）。【解答】后 先出，先 先出， 插入和 除操作限定的位置不同循 列的引入是 了克服（）。 【解答】假溢出數(shù) Qn 用來(lái)表示一個(gè)循 列， front 為隊(duì)頭元素的前一個(gè)位置，rear 尾元素的位置， 算 列中元素個(gè)數(shù)的公式 （）。（ rear-

12、front+n ） % n2.選擇題若一個(gè) 的 入序列是 1，2 ，3，n， 出序列的第一個(gè)元素是n， 第 i個(gè) 出元素是（）。 A 不確定 B n-i C n-i-1D n-i+1【解答】 D 【分析】此 ， 出序列一定是 入序列的逆序。 設(shè)棧 S和 列 Q的初始狀 空，元素e1 、e2 、e3 、e4 、e5 、e6 依次通 S，一個(gè)元素出 后即 入 列 Q，若 6個(gè)元素從 列 出的元素的 序是 e2 、e4、 e3、 e6、e5 、e1， S的容量至少 是（）。A 6B 4C 3D 2【解答】 C 【分析】由于 列具有先 先出性，所以，此 中 列形同虛 ，即出 的 序也是e2、 e4、e

13、3、e6 、e5 、e1 。 一個(gè) 的入 序列是1，2，3，4，5， 的不可能的 出序列是（）。A 54321 B 45321 C 43512 D12345 【解答】 C 【分析】 此 有一個(gè)技巧：在 出序列中任意元素后面不能出 比 元素小并且是升序3 / 6.（指的是元素的序號(hào)）的兩個(gè)元素。 設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳A 順序表B 棧C 隊(duì)列D 鏈表【解答】 B 【分析】每個(gè)右括號(hào)與它前面的最后一個(gè)沒(méi)有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。 在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（ ）結(jié)構(gòu)。A 棧 B隊(duì)列

14、C 數(shù)組D線性表【解答】 B【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。 一個(gè)隊(duì)列的入隊(duì)順序是1， 2，3，4 ，則隊(duì)列的輸出順序是（）。A 4321 B 1234 C 1432 D 3241【解答】 B 【分析】隊(duì)列的入隊(duì)順序和出隊(duì)順序總是一致的。 棧和隊(duì)列的主要區(qū)別在于（）。A 它們的邏輯結(jié)構(gòu)不一樣B 它們的存儲(chǔ)結(jié)構(gòu)不一樣C 所包含的運(yùn)算不一樣D 插入、刪除運(yùn)算的限定不一樣【解答】 D 設(shè)有兩個(gè)串 p和q ，求 q在 p中首次出現(xiàn)的位置的運(yùn)算稱作（）。A 連接 B 模式匹配C 求子串D 求串長(zhǎng)3. 判斷題 棧可以作為實(shí)現(xiàn)過(guò)程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。 在循環(huán)隊(duì)列中，front 指

15、向隊(duì)頭元素的前一個(gè)位置，rear 指向隊(duì)尾元素的位置， 則隊(duì)滿的條件是front=re ar 。【解答】錯(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)別開(kāi)。 空串與空格串是相同的。1在一個(gè)具有 n個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top 作為棧頂指針，當(dāng)出棧時(shí)， top 的變化為（）。A 不變B top=0;C top=top-1;D top=top+1;【解答】 C3從棧頂指針為 top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（）。A x=top;top=top-next; B x=top-data; C top=top-next;

16、 x=top-data;D x=top-data; top=top-next;【解答】 D5.設(shè) S=I_ am_ a_ teacther，其長(zhǎng)度為（）?！窘獯稹?156對(duì)于棧和隊(duì)列， 無(wú)論它們采用順序存儲(chǔ)結(jié)構(gòu)還是鏈接存儲(chǔ)結(jié)構(gòu)，進(jìn)行插入和刪除操作的時(shí)間復(fù)雜度都是（ ）?！窘獯稹?(1)8簡(jiǎn)述 隊(duì)列和棧這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)。第 5 章 樹(shù)和二叉樹(shù)課后習(xí)題講解1. 填空題4 / 6. 一棵二叉樹(shù)的第 i（i 1）層最多有（ ）個(gè)結(jié)點(diǎn)；一棵有 n（ n0 ）個(gè)結(jié)點(diǎn)的滿二叉樹(shù)共有（）個(gè)葉子結(jié)點(diǎn)和（ ）個(gè)非終端結(jié)點(diǎn)。【解答】 2 i-1，(n+1)/2 ，(n-1)/2 【分析】設(shè)滿二叉樹(shù)中葉

17、子結(jié)點(diǎn)的個(gè)數(shù)為n0 ，度為 2 的結(jié)點(diǎn)個(gè)數(shù)為 n2 ，由于滿二叉樹(shù)中不存在度為 1的結(jié)點(diǎn)，所以 n=n0+n2 ；由二叉樹(shù)的性質(zhì) n0=n2+1 ，得 n0=(n+1)/2，n2=(n-1)/2 。 設(shè)高度為 h的二叉樹(shù)上只有度為0和度為 2的結(jié)點(diǎn)，該二叉樹(shù)的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值是（），最小值是（ ）。 【解答】 2h -1 ，2h-1 【分析】最小結(jié)點(diǎn)個(gè)數(shù)的情況是第 1層有 1個(gè)結(jié)點(diǎn)，其他層上都只有 2個(gè)結(jié)點(diǎn)。 具有 100 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為（）?！窘獯稹?50 【分析】 100 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中最后一個(gè)結(jié)點(diǎn)的編號(hào)為100 ，其雙親即最后一個(gè)分支結(jié)點(diǎn)的編號(hào)為 50，也就

18、是說(shuō)，從編號(hào)51 開(kāi)始均為葉子。 已知一棵度為 3的樹(shù)有 2個(gè)度為 1的結(jié)點(diǎn)， 3個(gè)度為 2的結(jié)點(diǎn)， 4 個(gè)度為 3的結(jié)點(diǎn)。則該樹(shù)中有（）個(gè)葉子結(jié)點(diǎn)。 某二叉樹(shù)的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（）。【解答】 CDBGFEA 【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹(shù)構(gòu)造出來(lái)。（10） 在有 n個(gè)葉子的哈夫曼樹(shù)中，葉子結(jié)點(diǎn)總數(shù)為（），分支結(jié)點(diǎn)總數(shù)為（）?！窘獯稹?n， n-1 【分析】 n-1 個(gè)分支結(jié)點(diǎn)是經(jīng)過(guò)n-1 次合并后得到的。2. 選擇題 如果結(jié)點(diǎn) A有3 個(gè)兄弟， B是A的雙親，則結(jié)點(diǎn) B的度是（ ）。 A 1 B 2 C 3 D

19、4 【解答】 D 二叉樹(shù)的前序序列和后序序列正好相反，則該二叉樹(shù)一定是 （ ）的二叉樹(shù)。A 空或只有一個(gè)結(jié)點(diǎn)B 高度等于其結(jié)點(diǎn)數(shù)C 任一結(jié)點(diǎn)無(wú)左孩子D 任一結(jié)點(diǎn)無(wú)右孩子【解答】 B 【分析】此題注意是序列正好相反，則左斜樹(shù)和右斜樹(shù)均滿足條件。 線索二叉樹(shù)中某結(jié)點(diǎn)R沒(méi)有左孩子的充要條件是（）。 A R.lchild=NULL B R.ltag=0 C R.ltag=1 DR.rchild=NULL【解答】 C 【分析】線索二叉樹(shù)中某結(jié)點(diǎn)是否有左孩子，不能通過(guò)左指針域是否為空來(lái)判斷，而要判斷左標(biāo)志是否為 1。 一個(gè)高度為 h的滿二叉樹(shù)共有n 個(gè)結(jié)點(diǎn)，其中有 m個(gè)葉子結(jié)點(diǎn)，則有（）成立。A n=h+

20、m B h+m=2n Cm=h-1 D n=2m-1【解答】 D 【分析】滿二叉樹(shù)中沒(méi)有度為1 的結(jié)點(diǎn)，所以有m個(gè)葉子結(jié)點(diǎn)，則度為2的結(jié)點(diǎn)個(gè)數(shù)為 m-1( 比如葉子為 8, 則依次往上是 4,2,1 個(gè)節(jié)點(diǎn) ,等比數(shù)列個(gè)數(shù)為m-1.)。 設(shè)森林中有 4棵樹(shù)，樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)依次為n1 、n2 、n3 、n4 ，則把森林轉(zhuǎn)換成二叉樹(shù)后，其根結(jié)點(diǎn)的右子樹(shù)上有（）個(gè)結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹(shù)上有（）個(gè)結(jié)點(diǎn)。A n1-1 B n1 C n1+n2+n3 D n2+n3+n4（10）討論樹(shù)、森林和二叉樹(shù)的關(guān)系，目的是為了（）。A 借助二叉樹(shù)上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹(shù)的一些5 / 6.運(yùn)算B 將樹(shù)、森林按二叉樹(shù)的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹(shù)的算法解決樹(shù)的有關(guān)問(wèn)題C 將樹(shù)、森林轉(zhuǎn)換成二叉樹(shù)D 體現(xiàn)一種技巧，沒(méi)有什么實(shí)際意義3. 判斷題 在線索二叉樹(shù) 中，任一結(jié)點(diǎn)