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

實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(第四版)課后習(xí)題實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(第四版)課后習(xí)題實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(第四版)課后習(xí)題資料僅供參考文件編號：2022年4月實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(第四版)課后習(xí)題版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：判斷題（第一章緒論）1.數(shù)據(jù)元素是數(shù)據(jù)的最小單元。答案：錯誤一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的基本運算集構(gòu)成的整體。答案：錯誤數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)元素之間的邏輯關(guān)系和邏輯結(jié)構(gòu)在計算機(jī)存儲器內(nèi)的映像。答案：正確數(shù)據(jù)的邏輯結(jié)構(gòu)是描述元素之間的邏輯關(guān)系，它是依賴于計算機(jī)的。答案：錯誤5.用語句頻度來表示算法的時間復(fù)雜度的最大好處是可以獨立于計算機(jī)的軟硬件，分析算法的時間答案：正確（第二章線性表）6.取順序存儲線性表的第i個元素的時間同i的大小有關(guān)。答案：錯誤7.線性表鏈?zhǔn)酱鎯Φ奶攸c是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。答案：正確8.線性鏈表的每一個節(jié)點都恰好包含一個指針域。答案：錯誤9.順序存儲方式的優(yōu)點的存儲密度大，插入和刪除效率不如練市存儲方式好。答案：正確10.插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。答案：錯誤（第三章棧）11.棧是一種對進(jìn)棧和出棧作了限制的線性表。答案：錯誤12.在C（或C++）語言中設(shè)順序棧的長度為MAXLEN，則top=MAXLEN表示棧滿。答案：錯誤13.鏈棧與順序棧相比，其特點之一是通常不會出現(xiàn)滿棧的情況。答案：正確14.空棧就是所有元素都為0上的棧。答案：錯誤15.將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。答案：正確（第四章隊列）16.隊列式限制在兩端進(jìn)行操作的線性表。答案：正確17.判斷順序隊列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一結(jié)點。答案：錯誤18.在循環(huán)鏈列隊中無溢出現(xiàn)像。答案：錯誤19.在循環(huán)隊列中，若尾指針rear大于頭指針front，則元素個數(shù)為rear-front。答案：正確20.順序隊列和循環(huán)隊列關(guān)于隊滿和隊空的判斷條件是一樣的。答案：錯誤（第五章串）21.串是n個字母的有限序列。答案：錯誤22.串的堆分配存儲是一種動態(tài)存儲結(jié)構(gòu)。答案：正確23.串的長度是指串中不同字符的個數(shù)。答案：錯誤24.如貴一個串中所有的字母均在另一個串中出現(xiàn)，則說明前者是后者的子串。答案：錯誤25.在鏈串中為了提高存儲密度，應(yīng)該增大結(jié)點的大小。答案：正確（第六章對維數(shù)組和廣義表）n維的多維數(shù)組可以視為n-1維數(shù)組元素組成的線性結(jié)構(gòu)。答案：正確27.上三角矩陣對主角線以上（不包括對主角線中的元素），均為常數(shù)C。答案：錯誤28.數(shù)組的三元組表存儲時對稀疏矩陣的壓縮存儲。答案：正確29.廣義表Ls=（a0，a1，......an-1），則an-1是其表尾。答案：錯誤30.廣義表（（a,b），a,b）的表頭和表尾是相等的。答案：錯誤（第七章樹和二叉樹）31.在完全二叉樹中，若一個結(jié)點沒有左孩子，則它必然是葉子節(jié)點。答案：正確32.含多于兩棵樹的森林轉(zhuǎn)換到二叉樹，其根節(jié)點一定無右子樹。答案：錯誤33.二叉樹的前序遍歷中，任意一個節(jié)點均處于其子女節(jié)點的前面。答案：正確34.在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。答案：錯誤35.在哈夫曼編碼中，當(dāng)兩個字符出現(xiàn)的頻率相同的，其他編碼也相同，對于這種情況應(yīng)該做特殊處理。答案：錯誤（第八章圖）36.在無相圖中，（v1,v2）與（v2,v1）是兩條不同的邊。答案：錯誤37.圖可以沒有邊，但不能沒有頂點。答案：正確38.若一個無向圖以頂點v1為起點，進(jìn)行深度優(yōu)先遍歷，所得的遍歷序列唯一，則可以唯一確定該圖。答案：錯誤39.用鄰接矩陣法存儲一個圖時，所占用的存儲空間大小與圖中的頂點個數(shù)無關(guān)，而只與圖的邊數(shù)有關(guān)。答案：錯誤40.存儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的上三角（或下三角）部分就可以了。答案：正確（第九章查找）41.在有序的順序表和有序的鏈表上，均可以采用二分查找法來提高查找速度。答案：錯誤42.在二叉排序樹中，根節(jié)點的這都小于孩子節(jié)點的值。答案：錯誤43.選擇好的哈希函數(shù)就可以避免沖突的發(fā)生。答案：錯誤44.散列存儲法的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)存儲地址。答案：正確45.在二叉排序樹上刪除一個節(jié)點時，不必移動其他節(jié)點，只要將該節(jié)點的父節(jié)點的相應(yīng)指針域置空即可。答案：錯誤（第十章排序）46.如果某種排序算法不穩(wěn)定，則該排序方法就沒有使用價值。答案：錯誤47.希爾排序是不穩(wěn)定的排序。答案：正確48.對排序所需的時間與待排序的記錄個數(shù)無關(guān)。答案：錯誤49.快速排序在任何情況下都比其他排序方法速度快。答案：錯誤50.采用歸并排序可以實現(xiàn)外排序。答案：錯誤二、填空題（第一章緒論）數(shù)據(jù)結(jié)果是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的___數(shù)據(jù)元素___，以及它們之間關(guān)系和運算的學(xué)科。數(shù)據(jù)有邏輯結(jié)構(gòu)和__存儲結(jié)構(gòu)__兩種結(jié)構(gòu)。數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外的還包括線性結(jié)構(gòu)，樹形結(jié)構(gòu)和__圖形結(jié)構(gòu)__。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是線性結(jié)構(gòu)和__非線性結(jié)構(gòu)__。圖形結(jié)構(gòu)和__樹形結(jié)構(gòu)__合稱為非線性結(jié)構(gòu)。在樹形結(jié)構(gòu)中，除了樹根節(jié)點以外，其余每個節(jié)點都只有__1__個前驅(qū)結(jié)點。在圖形結(jié)構(gòu)中，每一個節(jié)點的前驅(qū)節(jié)點上數(shù)和后繼節(jié)點數(shù)可以__互換__。數(shù)據(jù)的存儲結(jié)構(gòu)，又叫做數(shù)據(jù)的__物理結(jié)構(gòu)__。數(shù)據(jù)的存儲結(jié)構(gòu)形式，包括順序存儲，鏈?zhǔn)酱鎯λ饕鎯蚠_散列存儲__。樹形結(jié)構(gòu)中的元素之間存在__1對多__的關(guān)系。圖形結(jié)構(gòu)的元素之間存在__多對多__的關(guān)系。數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)和__算法__三方面的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)被定義為(D,R),D是數(shù)據(jù)的有限集合，R是D上的__邏輯關(guān)系__的有限集合算法是對特定問題__解決步驟__的描述。算法效率的度量可以分為事先估算和__事后統(tǒng)計__。一個算法的時間復(fù)雜度是算法__數(shù)據(jù)規(guī)模__的函數(shù)。算法的空間復(fù)雜度是指該算法所耗費的__存儲空間__，他是該算法求解問題規(guī)模n的函數(shù)。若一個算法中，還有10萬條基本語句，但有問題的規(guī)模無關(guān)，則該算法的時間復(fù)雜度為__O(1)__。若一個算法中的語句頻度之和為T(n)=6n+3nlog2n，則算法的時間復(fù)雜度為__O(n)__。若一個算法中的語句頻度之和為T(n)=3n+nlog2n+n2，則算法的時間復(fù)雜度為__O(n^2)__。（第二章線性表）1.在線性表中，數(shù)據(jù)的長度定義為__表長__。2.順序表中邏輯上相鄰的元素在物理位置上__一定__相鄰。3.順序表相對于鏈表的優(yōu)點是__密度大__和隨機(jī)存取。4.某線性表采用順序存儲結(jié)構(gòu)，每個元素占據(jù)4個存儲單元，首地址為100則下標(biāo)為11的(第12個元素)存儲地址為__144__。5.當(dāng)線性表中的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取現(xiàn)象表中的元素時，應(yīng)采用__順序__存儲結(jié)構(gòu)。6.順序表中訪問任意一個結(jié)點的時間復(fù)雜度均為__O(1)__。7.在一個長度為n的順序表中刪除第i個元素要移動__n-i__個元素。8.在一個長度為n的順序表中，如果要在第二個元素前插入一個元素要后移__n-i+1__個元素。9.線性表L=(a1,a2,......,an)用數(shù)組表示假定刪除表中任意元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是__n/2__。10.在線性表的鏈?zhǔn)酱鎯χ性刂g的邏輯關(guān)系是通過__指針__決定的。11.在雙向鏈表中每個節(jié)點都有兩個指針域他們一個指向其__前驅(qū)__結(jié)點，另一個指向其后繼結(jié)點。12.線性表的元素總數(shù)不確定，且經(jīng)常需要進(jìn)行插入和刪除操作，應(yīng)采用__鏈?zhǔn)絖_存儲結(jié)構(gòu)。13.在單向鏈表中，需要知道__表頭指針__才能遍歷整個鏈表。14.在單向鏈表中，要在已知的節(jié)點*p之前插入一個新節(jié)點，需找到*p的直接前驅(qū)結(jié)點的地址，其查找的時間復(fù)雜度為__O(n)__。15.單向循環(huán)鏈表的最大優(yōu)點是__從任意節(jié)點出發(fā)__可以訪問到鏈表中每一個元素。16.在雙向鏈表中要刪除已知節(jié)點*p，其實間復(fù)雜度為__O(n)__。17.帶頭節(jié)點的雙循環(huán)鏈表L中判斷只有一個元素節(jié)點的條件是__L->next->next==L(L->front->front==L)__。18.對于雙向鏈表，在兩個節(jié)點之間插入一個新節(jié)點需要修改的指針共__4__個。19.雙向鏈表中，設(shè)p是指向其中待刪除的節(jié)點，則需要執(zhí)行的操作命令序列為：p->front->rear=p->rear；__p->rear->front=p->front__。20.在如下所示的鏈表中，若在指針p所在的結(jié)點之后插入數(shù)據(jù)與值為a和b的兩個節(jié)點,則可用語句__S->next->next=p->next__來實現(xiàn)該操作。（第三章棧）棧的特點是__先進(jìn)后出__。在棧結(jié)構(gòu)中，允許插入，刪除的一端稱為__棧頂__。在順序棧中，在棧頂指針top=-1時表示__棧為空__。4.順序棧s存儲在數(shù)組s->data[0..maxlen-1]中，進(jìn)棧操作時首先需要執(zhí)行的語句有：s->top=__s->top+1__。5.鏈棧LS為空的條件是__LS==NULL__。6.已知順序棧s在對s進(jìn)行棧操作之前，首先要判斷__棧滿否__。7.若內(nèi)存空間充足，__鏈__?？梢圆欢x棧滿運算。8.同一棧的各元素類型__一致__。9.在有n個元素的鏈棧中，進(jìn)棧操作的時間復(fù)雜度為__O(1)__。10.由于鏈棧的操作只在鏈表的頭部進(jìn)行，所以沒有必要設(shè)置__頭__節(jié)點。11.從一個棧刪除元素時，首先取出__棧頂元素__，然后在移動棧頂指針。12.像一個棧頂指針為top的鏈棧插入一個新的節(jié)點*p時，應(yīng)執(zhí)行__p->next=top__和top=p的操作。13.若進(jìn)棧的次序是A、B、C、D、E執(zhí)行三次出棧操作后棧頂元素為__B__。14.四個元素按A、B、C、D順序進(jìn)s棧執(zhí)行兩次pop(S、X)后X的值是__C__。15.設(shè)有一個順序空棧，現(xiàn)有輸入序列號ABCDE，經(jīng)過push、push、pop、push、pop、push、push、pop操作之后輸出序列式是__BCE__。16.對一個初始值為空棧s執(zhí)行操作push(s,5)、push(s,2)、push(s,4)、push(s,x)、readTop(s,x)后，x的值應(yīng)是__2__。17.設(shè)I表示入棧操作，O表示出棧操作，若元素入棧順序為1,2,3,4為了得到1,3,4,2出棧順序，則相應(yīng)的I和O的操作串為__IOIIOIOO__。18.已知表達(dá)式，求它后綴表達(dá)式是__棧__的典型應(yīng)用。+B/C-D*E的后綴表達(dá)式是__ABC/+DE*-__。20.已知一個棧的進(jìn)棧序列是1,2,3,4,，......，n，其輸出序列是p1，p2，p3，......，pn。若p1=n，則pi的值是__n+i-1__。第四章隊列第四章填空1.在隊列中存取數(shù)據(jù)應(yīng)遵循的原則是先進(jìn)先出。2.在隊列中允許插入的一段稱之為隊尾。3.在隊列中允許刪除的一端，稱之為對頭。4.隊列在進(jìn)行出隊操作時，首先要判斷隊列是否為空。5.順序隊列在進(jìn)行入隊操作時，首先要判斷隊列是否為滿。6.順序隊列初始化后，front=rear＝-17.鏈隊列LQ為空時，LQ-＞front-＞next=NULL8.讀隊首元素的操作不改變隊列元素的個數(shù)。9.在一個鏈隊列中，若隊首指針為front,隊尾指針為rear，則判斷該隊列只有一個結(jié)點的條件為front==real（front-＞next==NULL）10.設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊操作的時間復(fù)雜度為O(n)11.設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)尾指針，則出隊操作的時間復(fù)雜度為O(n)12.隊列Q，經(jīng)過InitQueue(Q)XXXXXX運算后的值是013.隊列Q，經(jīng)過InitQueue(Q)XXXXXX運算后，x的值是a14.解決順序隊列“假溢出”的方法是采用循環(huán)隊15.循環(huán)隊列q的對手指針為，隊尾指針為，則隊空的條件為==16.設(shè)循環(huán)隊列的容量為40（序號為0~39）現(xiàn)經(jīng)過一系列的入隊和出隊運算后，front=11，rear=19，則循環(huán)隊列中還有8個元素17.設(shè)循環(huán)隊列的頭指針front指向隊首元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，則隊滿標(biāo)志為rear-front==MAXLEN18.從循環(huán)隊列中刪除一個元素時，其操作是front++19.在循環(huán)隊列中，隊首指針指向隊首元素的前一個位置20.刪除雙向?qū)α斜碇?p的前驅(qū)結(jié)點（存在）應(yīng)執(zhí)行的語句序列是xxxxxxx第五章1.由零個或多個字符組成的有限序列稱為字符串。2.空格穿時有空格組成的串。3.字符串存儲方式除了順序存儲，鏈接存儲，還有堆存儲。4.穿衣順序存儲非緊湊格式的缺點是密度小5.串順序存儲緊湊格式的缺點是對串的字符處理困難。6.串的鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱為鏈串。7.串鏈接存儲的優(yōu)點是插入，刪除方便，缺點是存儲，檢索效率低。8.在c或c++語言中以字符（這個答案很奇怪）表示串值的終結(jié)9.兩個串相等的充分必要條件是兩個串長度相等，且對應(yīng)位置的字符相同10.設(shè)S=“mymusic”則LenStr（S）=811.兩個字符串分別為XXXXX12.求子串的結(jié)果是13.在串的運算中XXXXXX，返回值為July14.在串的運算中XXXXXX，返回值為-115.設(shè)有兩個串P和Q，求Q在P中首次出現(xiàn)的位置運算稱作16.在子串的定位運算中，被匹配的主串稱為目標(biāo)串，子串稱為模式17.模式匹配成功的起始位置稱為有效位移18.設(shè)XXXXX19.設(shè)Xxxx20.若n為主串長度，m為子串長度，且n＞＞m，則簡單模式匹配算法最好情況下的時間復(fù)雜度為0（n*m）第六章1.多維數(shù)組的順序存儲方式有按行優(yōu)先順序存儲和列優(yōu)先兩種。2.在n維數(shù)組中的每一個元素最多可以有n個直接前驅(qū)3.在多維數(shù)組中，數(shù)據(jù)元素的存放地址可以直接通過地址計算公式算出，所以多維數(shù)組是一種順序存取結(jié)構(gòu)4.數(shù)組元素a[0..2][0..3]的實際地址是2000，元素長度是4，則LOC[1,2]=2285.輸入二維數(shù)組A[n][m]中所有元素值的時間復(fù)雜度為0（n*m）階對稱矩陣，如果只存儲下三角元素，只需要n*(n+1)/2個存儲單元階下三角矩陣，因為對角線的上方是一個常數(shù)，需要n*(n+1)/2+1個存儲單元8.非零元素的個數(shù)遠(yuǎn)小于矩陣元素總數(shù)的矩陣為稀疏矩陣9.稀疏矩陣矩陣的三元組有三列１０．稀疏矩陣中有ｎ個非