數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(第四版)課后習(xí)題

判斷題（第一章緒論）1.數(shù)據(jù)元素是數(shù)據(jù)的最小單元。答案：錯(cuò)誤一個(gè)數(shù)據(jù)結(jié)構(gòu)是由一個(gè)邏輯結(jié)構(gòu)和這個(gè)邏輯結(jié)構(gòu)上的基本運(yùn)算集構(gòu)成的整體。答案：錯(cuò)誤數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素之間的邏輯關(guān)系和邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的映像。答案：正確數(shù)據(jù)的邏輯結(jié)構(gòu)是描述元素之間的邏輯關(guān)系，它是依賴于計(jì)算機(jī)的。答案：錯(cuò)誤5.用語句頻度來表示算法的時(shí)間復(fù)雜度的最大好處是可以獨(dú)立于計(jì)算機(jī)的軟硬件，分析算法的時(shí)間答案：正確（第二章線性表）6.取順序存儲(chǔ)線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)。答案：錯(cuò)誤7.線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。答案：正確8.線性鏈表的每一個(gè)節(jié)點(diǎn)都恰好包含一個(gè)指針域。答案：錯(cuò)誤9.順序存儲(chǔ)方式的優(yōu)點(diǎn)的存儲(chǔ)密度大，插入和刪除效率不如練市存儲(chǔ)方式好。答案：正確10.插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。答案：錯(cuò)誤（第三章棧）11.棧是一種對(duì)進(jìn)棧和出棧作了限制的線性表。答案：錯(cuò)誤12.在C（或C++）語言中設(shè)順序棧的長(zhǎng)度為MAXLEN，則top=MAXLEN表示棧滿。答案：錯(cuò)誤13.鏈棧與順序棧相比，其特點(diǎn)之一是通常不會(huì)出現(xiàn)滿棧的情況。答案：正確14.空棧就是所有元素都為0上的棧。答案：錯(cuò)誤15.將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。答案：正確（第四章隊(duì)列）16.隊(duì)列式限制在兩端進(jìn)行操作的線性表。答案：正確17.判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一結(jié)點(diǎn)。答案：錯(cuò)誤18.在循環(huán)鏈列隊(duì)中無溢出現(xiàn)像。答案：錯(cuò)誤19.在循環(huán)隊(duì)列中，若尾指針rear大于頭指針front，則元素個(gè)數(shù)為rear-front。答案：正確20.順序隊(duì)列和循環(huán)隊(duì)列關(guān)于隊(duì)滿和隊(duì)空的判斷條件是一樣的。答案：錯(cuò)誤（第五章串）21.串是n個(gè)字母的有限序列。答案：錯(cuò)誤22.串的堆分配存儲(chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。答案：正確23.串的長(zhǎng)度是指串中不同字符的個(gè)數(shù)。答案：錯(cuò)誤24.如貴一個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn)，則說明前者是后者的子串。答案：錯(cuò)誤25.在鏈串中為了提高存儲(chǔ)密度，應(yīng)該增大結(jié)點(diǎn)的大小。答案：正確（第六章對(duì)維數(shù)組和廣義表）n維的多維數(shù)組可以視為n-1維數(shù)組元素組成的線性結(jié)構(gòu)。答案：正確27.上三角矩陣對(duì)主角線以上（不包括對(duì)主角線中的元素），均為常數(shù)C。答案：錯(cuò)誤28.數(shù)組的三元組表存儲(chǔ)時(shí)對(duì)稀疏矩陣的壓縮存儲(chǔ)。答案：正確29.廣義表Ls=（a0，a1，......an-1），則an-1是其表尾。答案：錯(cuò)誤30.廣義表（（a,b），a,b）的表頭和表尾是相等的。答案：錯(cuò)誤（第七章樹和二叉樹）31.在完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必然是葉子節(jié)點(diǎn)。答案：正確32.含多于兩棵樹的森林轉(zhuǎn)換到二叉樹，其根節(jié)點(diǎn)一定無右子樹。答案：錯(cuò)誤33.二叉樹的前序遍歷中，任意一個(gè)節(jié)點(diǎn)均處于其子女節(jié)點(diǎn)的前面。答案：正確34.在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。答案：錯(cuò)誤35.在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同的，其他編碼也相同，對(duì)于這種情況應(yīng)該做特殊處理。答案：錯(cuò)誤（第八章圖）36.在無相圖中，（v1,v2）與（v2,v1）是兩條不同的邊。答案：錯(cuò)誤37.圖可以沒有邊，但不能沒有頂點(diǎn)。答案：正確38.若一個(gè)無向圖以頂點(diǎn)v1為起點(diǎn)，進(jìn)行深度優(yōu)先遍歷，所得的遍歷序列唯一，則可以唯一確定該圖。答案：錯(cuò)誤5.順序隊(duì)列在進(jìn)行入隊(duì)操作時(shí)，首先要判斷隊(duì)列是否為滿。6.順序隊(duì)列初始化后，front=rear＝-17.鏈隊(duì)列LQ為空時(shí)，LQ-＞front-＞next=NULL8.讀隊(duì)首元素的操作不改變隊(duì)列元素的個(gè)數(shù)。9.在一個(gè)鏈隊(duì)列中，若隊(duì)首指針為front,隊(duì)尾指針為rear，則判斷該隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件為front==real（front-＞next==NULL）10.設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為O(n)11.設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)尾指針，則出隊(duì)操作的時(shí)間復(fù)雜度為O(n)12.隊(duì)列Q，經(jīng)過InitQueue(Q)XXXXXX運(yùn)算后的值是013.隊(duì)列Q，經(jīng)過InitQueue(Q)XXXXXX運(yùn)算后，x的值是a14.解決順序隊(duì)列“假溢出”的方法是采用循環(huán)隊(duì)15.循環(huán)隊(duì)列q的對(duì)手指針為Q.front，隊(duì)尾指針為Q.rear，則隊(duì)空的條件為Q.rear==Q.front16.設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)為0~39）現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后，front=11，rear=19，則循環(huán)隊(duì)列中還有8個(gè)元素17.設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)首元素，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN，則隊(duì)滿標(biāo)志為rear-front==MAXLEN18.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是front++19.在循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置20.刪除雙向?qū)α斜碇?p的前驅(qū)結(jié)點(diǎn)（存在）應(yīng)執(zhí)行的語句序列是xxxxxxx第五章1.由零個(gè)或多個(gè)字符組成的有限序列稱為字符串。2.空格穿時(shí)有空格組成的串。3.字符串存儲(chǔ)方式除了順序存儲(chǔ)，鏈接存儲(chǔ)，還有堆存儲(chǔ)。4.穿衣順序存儲(chǔ)非緊湊格式的缺點(diǎn)是密度小5.串順序存儲(chǔ)緊湊格式的缺點(diǎn)是對(duì)串的字符處理困難。6.串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱為鏈串。7.串鏈接存儲(chǔ)的優(yōu)點(diǎn)是插入，刪除方便，缺點(diǎn)是存儲(chǔ)，檢索效率低。8.在c或c++語言中以字符（這個(gè)答案很奇怪）表示串值的終結(jié)9.兩個(gè)串相等的充分必要條件是兩個(gè)串長(zhǎng)度相等，且對(duì)應(yīng)位置的字符相同10.設(shè)S=“mymusic”則LenStr（S）=811.兩個(gè)字符串分別為XXXXX12.求子串的結(jié)果是13.在串的運(yùn)算中XXXXXX，返回值為July14.在串的運(yùn)算中XXXXXX，返回值為-115.設(shè)有兩個(gè)串P和Q，求Q在P中首次出現(xiàn)的位置運(yùn)算稱作16.在子串的定位運(yùn)算中，被匹配的主串稱為目標(biāo)串，子串稱為模式17.模式匹配成功的起始位置稱為有效位移18.設(shè)XXXXX19.設(shè)Xxxx20.若n為主串長(zhǎng)度，m為子串長(zhǎng)度，且n＞＞m，則簡(jiǎn)單模式匹配算法最好情況下的時(shí)間復(fù)雜度為0（n*m）第六章1.多維數(shù)組的順序存儲(chǔ)方式有按行優(yōu)先順序存儲(chǔ)和列優(yōu)先兩種。2.在n維數(shù)組中的每一個(gè)元素最多可以有n個(gè)直接前驅(qū)3.在多維數(shù)組中，數(shù)據(jù)元素的存放地址可以直接通過地址計(jì)算公式算出，所以多維數(shù)組是一種順序存取結(jié)構(gòu)4.數(shù)組元素a[0..2][0..3]的實(shí)際地址是2000，元素長(zhǎng)度是4，則LOC[1,2]=2285.輸入二維數(shù)組A[n][m]中所有元素值的時(shí)間復(fù)雜度為0（n*m）6.n階對(duì)稱矩陣，如果只存儲(chǔ)下三角元素，只需要n*(n+1)/2個(gè)存儲(chǔ)單元7.n階下三角矩陣，因?yàn)閷?duì)角線的上方是一個(gè)常數(shù)，需要n*(n+1)/2+1個(gè)存儲(chǔ)單元8.非零元素的個(gè)數(shù)遠(yuǎn)小于矩陣元素總數(shù)的矩陣為稀疏矩陣9.稀疏矩陣矩陣的三元組有三列１０．稀疏矩陣中有ｎ個(gè)非零元素，則三元組有ｎ＋１１１.稀疏矩陣的三元組中的一列存儲(chǔ)的是數(shù)組中非零元素所在的行１２．稀疏矩陣a，如圖，其非零元素存于三元表中三元組415，按列優(yōu)先順序存儲(chǔ)在三元表中的第５項(xiàng)１３.稀疏矩陣的壓縮存儲(chǔ)方法通常有三元組表和十字鏈表兩種１４.任何一個(gè)非空廣義表的表尾，必定是表元素１５．廣義表Ｌ的表尾【１６－２０題在書上看吧】ＱＡＱ第七章1.三個(gè)節(jié)點(diǎn)可以組成五種不同形態(tài)的樹。2.在樹中，一個(gè)結(jié)點(diǎn)所擁有的子樹數(shù)，稱之為該結(jié)點(diǎn)的度。3.度為零的結(jié)點(diǎn)稱之為葉結(jié)點(diǎn)。4.樹中節(jié)點(diǎn)的最大層次稱之為樹的深度5.對(duì)于二叉樹來說，第二層上至多有6.深度為h的二叉樹至多有7.有20個(gè)節(jié)點(diǎn)的完全二叉樹，編號(hào)為10的節(jié)點(diǎn)的父節(jié)點(diǎn)的編號(hào)是58.將一棵完全二叉樹按層次編號(hào)，對(duì)于任意一個(gè)編號(hào)為i的結(jié)點(diǎn)，其右孩子結(jié)點(diǎn)編號(hào)為2i+19.已知完全二叉樹的第8層有8個(gè)節(jié)點(diǎn)，則其葉節(jié)點(diǎn)數(shù)是三10.采用二叉鏈表存儲(chǔ)的n個(gè)節(jié)點(diǎn)的二叉樹，共有空指針n+1個(gè)11.如圖12.如圖13.A.B為一棵樹二叉數(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是A在B的左子樹上14.設(shè)一棵二叉樹節(jié)點(diǎn)的先序遍歷序列為abcdefgh，中序遍歷序列為dbeaf