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

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)

2、應(yīng)該是（ ）。 A 樹 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ǔ)地址(51)×2=108 設(shè)單鏈表中指針p 指向結(jié)點(diǎn)A，若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（ ）?！窘獯稹縫->next=(p->next)->next 非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（ ）。p->next

3、=head 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（ ）；刪除開始結(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 【分析】參見。 線性表采用鏈接存儲(chǔ)時(shí)，其地

4、址（ ）。 A 必須是連續(xù)的 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的 D 連續(xù)與否均可以【解答】D 【分析】線性表的鏈接存儲(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í)，能更好地保證鏈表不斷開?！窘獯稹緽 鏈表不具有的特點(diǎn)是（ ）。 A 可隨機(jī)訪問任一元素 B 插入、刪除不需要移動(dòng)元素 C 不必事先估計(jì)存儲(chǔ)空間 D 所需空間與線性表長(zhǎng)度成正比

5、. 【解答】A 若某線性表中最常用的操作是取第i 個(gè)元素和找第i個(gè)元素的前趨，則采用（ ）存儲(chǔ)方法最節(jié)省時(shí)間。 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)行順

6、序查找，所以，雙鏈表并不能提高查找速度，因?yàn)殡p鏈表中有兩個(gè)指針域，顯然不能節(jié)約存儲(chǔ)空間，對(duì)于動(dòng)態(tài)存儲(chǔ)分配，回收存儲(chǔ)空間的速度是一樣的。由于雙鏈表具有對(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; D p->next=s; s->next=q; 【解答】B，本題答案不是非常合

7、理，應(yīng)該換順序更好！ 考試可以修改說: 已知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->next->prior=s; s->next=p->next; B p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; C s->prior=p; s->next=p->next; p->next=s; p->next->prior=

8、s; D s->prior=p; s->next=p->next; p->next->prior=s; p->next=s 【解答】D 3. 判斷題 線性表的邏輯順序和存儲(chǔ)順序總是一致的。 【解答】錯(cuò)。順序表的邏輯順序和存儲(chǔ)順序一致，鏈表的邏輯順序和存儲(chǔ)順序不一定一致。 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)。 線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 【解答】錯(cuò)。每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒有前驅(qū)，最后一個(gè)元素沒有后繼。 在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)

9、構(gòu)。 【解答】錯(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。4請(qǐng)說明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲(chǔ)結(jié)構(gòu)更好些。 若線性表的總長(zhǎng)度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 如果n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化。 描述一個(gè)城市的設(shè)計(jì)和規(guī)劃?！窘獯稹宽樞虮淼膬?yōu)點(diǎn)： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間； 可以快速地存取表中任一位置的元素（即隨機(jī)存?。ｍ樞虮淼娜秉c(diǎn)： 插入和刪除操作需移動(dòng)大量元素； 表的容量難以確定； 造成存儲(chǔ)空間的“碎片”。 單鏈表的優(yōu)點(diǎn)： 不必事先知

10、道線性表的長(zhǎng)度； 插入和刪除元素時(shí)只需修改指針，不用移動(dòng)元素。單鏈表的缺點(diǎn)： 指針的結(jié)構(gòu)性開銷； 存取表中任意元素不方便，只能進(jìn)行順序存取。 應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取結(jié)構(gòu)，單鏈表是順序存取結(jié)構(gòu)。本題很少進(jìn)行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。 應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。鏈表容易實(shí)現(xiàn)表容量的擴(kuò)充，適合表的長(zhǎng)度動(dòng)態(tài)發(fā)生變化。 應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及活動(dòng)很多，需要經(jīng)常修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。5算法設(shè)計(jì)(1) 假設(shè)在長(zhǎng)度大于1的循環(huán)鏈表中，即無頭結(jié)點(diǎn)也無頭指針，s

11、為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)s的前趨結(jié)點(diǎn)。 第 3 章特殊線性表?xiàng)！㈥?duì)列和串課后習(xí)題講解1. 填空 設(shè)有一個(gè)空棧，棧頂指針為1000H，現(xiàn)有輸入序列為1、2、3、4、5， 經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是（ ），棧頂指針為（ ）?！窘獯稹?3，1003H 棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ ）；其判定棧空的條件分別是（ ），判定棧滿的條件分別是（ ）?！窘獯稹宽樞虼鎯?chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top= -1和top=NULL，棧頂指針top等于數(shù)組的長(zhǎng)度和內(nèi)存無可用空間（ ）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

12、 (?；蛘哧?duì)列選一個(gè))【解答】棧 【分析】遞歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。 棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（ ），隊(duì)列的操作特性是（ ），棧和隊(duì)列的主要區(qū)別在于（ ）。 【解答】后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同 循環(huán)隊(duì)列的引入是為了克服（ ）。 【解答】假溢出 數(shù)組Qn用來表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素的位置，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（ ）。（rear-front+n）% n2. 選擇題 若一個(gè)棧的輸入序列是1，2，3，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是（ ）。 A 不確定 B n-i C n-i-1

13、 D n-i+1 【解答】D 【分析】此時(shí)，輸出序列一定是輸入序列的逆序。 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5、e6依次通過棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素從隊(duì)列輸出的元素的順序是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（ ）。 A 6 B 4 C 3 D 2 【解答】C 【分析】由于隊(duì)列具有先進(jìn)先出性，所以，此題中隊(duì)列形同虛設(shè)，即出棧的順序也是e2、e4、e3、e6、e5、e1。 一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（ ）。 A 54321 B 45321 C 43512 D 12345 【解答】C 【分析】

14、此題有一個(gè)技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序號(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è)沒有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。 在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（ ）結(jié)構(gòu)。 A 棧 B隊(duì)列 C 數(shù)組 D線性表 【解答】B【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。 一個(gè)隊(duì)列的入隊(duì)順序是1，2，3，4，則隊(duì)列的輸出順序是（ ）。 A 4321 B 1234

15、 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)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。 在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，則隊(duì)滿的條件是front=rear。 【解答】錯(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)別開。 空

16、串與空格串是相同的。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; x=top->data; D x=top->data; top=top->next; 【解答】D5.設(shè)S="I_ am

17、_ a_ teacther"，其長(zhǎng)度為（ ）。 【解答】156對(duì)于棧和隊(duì)列，無論它們采用順序存儲(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章 樹和二叉樹課后習(xí)題講解1. 填空題 一棵二叉樹的第i（i1）層最多有（ ）個(gè)結(jié)點(diǎn)；一棵有n（n>0）個(gè)結(jié)點(diǎn)的滿二叉樹共有（ ）個(gè)葉子結(jié)點(diǎn)和（ ）個(gè)非終端結(jié)點(diǎn)。 【解答】2i-1，(n+1)/2，(n-1)/2 【分析】設(shè)滿二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，由于滿二叉樹中不存在度為1的結(jié)點(diǎn)，所以n=n0+n2；由二叉樹的性質(zhì)n0=

18、n2+1，得n0=(n+1)/2，n2=(n-1)/2。 設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，該二叉樹的結(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)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為（ ）?！窘獯稹?0 【分析】100個(gè)結(jié)點(diǎn)的完全二叉樹中最后一個(gè)結(jié)點(diǎn)的編號(hào)為100，其雙親即最后一個(gè)分支結(jié)點(diǎn)的編號(hào)為50，也就是說，從編號(hào)51開始均為葉子。 已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)。則該樹中有（ ）個(gè)葉子結(jié)點(diǎn)。 某二叉樹的前序遍歷序列是ABC

19、DEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（ ）。【解答】CDBGFEA 【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。（10） 在有n個(gè)葉子的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為（ ），分支結(jié)點(diǎn)總數(shù)為（ ）。 【解答】n，n-1 【分析】n-1個(gè)分支結(jié)點(diǎn)是經(jīng)過n-1次合并后得到的。2. 選擇題 如果結(jié)點(diǎn)A有3個(gè)兄弟，B是A的雙親，則結(jié)點(diǎn)B的度是（ ）。 A 1 B 2 C 3 D 4 【解答】D 二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（ ）的二叉樹。 A 空或只有一個(gè)結(jié)點(diǎn) B 高度等于其結(jié)點(diǎn)數(shù) C 任一結(jié)點(diǎn)無左孩子 D 任一結(jié)點(diǎn)無右孩子 【解答】B 【分析】此

20、題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。 線索二叉樹中某結(jié)點(diǎn)R沒有左孩子的充要條件是（ ）。 A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL 【解答】C 【分析】線索二叉樹中某結(jié)點(diǎn)是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標(biāo)志是否為1。 一個(gè)高度為h的滿二叉樹共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有（ ）成立。 A n=h+m B h+m=2n C m=h-1 D n=2m-1 【解答】D 【分析】滿二叉樹中沒有度為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棵樹，樹中結(jié)點(diǎn)的個(gè)數(shù)依次為n1、n2、n3、n4，則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點(diǎn)的右子樹上有（ ）個(gè)結(jié)點(diǎn)，根結(jié)點(diǎn)的左子樹上有（ ）個(gè)結(jié)點(diǎn)。 A n1-1 B n1 C n1+n2+n3 D n2+n3+n4 （10）討論樹、森林和二叉樹的關(guān)系，目的是為了（ ）。 A 借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹的一些運(yùn)算 B 將樹、森林按二叉樹的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹的算法解決樹的有關(guān)問題 C 將樹、森林轉(zhuǎn)換成二叉樹 D 體現(xiàn)一種技巧，沒有什么實(shí)際意義3. 判斷題 在線索二叉樹中，任一結(jié)點(diǎn)均有指向其前趨和后繼的線索。 【解答】錯(cuò)。某結(jié)