數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:

一、選擇題1．以下數(shù)據(jù)結(jié)構(gòu)中，（D）是線性結(jié)構(gòu)。A．圖B.二叉樹C.樹D.串2．線性表是具有n個（C）的有限序列。A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項E．信息項3．線性表采用鏈接存儲時，其地址（D）。A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.一定是不連續(xù)的 D.連續(xù)與否均可以4．一個隊列的入隊順序是1，2，3，4，則隊列的輸出順序是（B）。A.4321 B.1234 C.1432 D.32415．假設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為（A）。A．(rear-front+m)%m B．rear-front+1C．(front-rear+m)%m D．(rear-front)%m6．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（D）倍。A．1/2B．1C．4D．27．串的長度是指（B）A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)8．設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（C）。A．求子串 B．聯(lián)接 C．匹配 D．求串長9．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中，計算機的操作對象以及它們之間的（B）和操作等的學(xué)科。A．結(jié)構(gòu)B．關(guān)系C．邏輯存儲D．算法10．設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是（B）。A．211．（D）是C語言中“abcd321ABCD”的子串。A．a(chǎn)bcdB．321ABC.“abcABC”D．“21AB”子串的定義是什么串中任意個連續(xù)的字符組成的子序列成為該串的子串。12．二分查找要求被查找的表是（C）A．鍵值有序的鏈接表B．鏈接表但鍵值不一定有序C．鍵值有序的順序表D．順序表但鍵值不一定有序13．?dāng)?shù)據(jù)結(jié)構(gòu)的形式定義為(D,S)，其中D是（B）的有限集。A.算法 B.數(shù)據(jù)元素 C.數(shù)據(jù)操作 D.邏輯結(jié)構(gòu)14．一個算法指的是（B）。A．程序B．問題求解步驟的描述C．要滿足五個基本特性D．A和C15．具有10個葉結(jié)點的二叉樹中有（B）個度為2的結(jié)點。A．8B．9C．10D．ll16．以下數(shù)據(jù)結(jié)構(gòu)中，（D）是線性結(jié)構(gòu)。A．圖B.二叉樹C.樹D.串17．?dāng)?shù)據(jù)結(jié)構(gòu)的形式定義為(D,S)，其中D是（B）的有限集。A.算法 B.數(shù)據(jù)元素 C.數(shù)據(jù)操作 D.邏輯結(jié)構(gòu)18．一個算法指的是（B）。A．程序B．問題求解步驟的描述C．要滿足五個基本特性D．A和CA．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。19．在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（D）倍。A．1/2B．1C．4D．220．串是任意有限個（C）。A．符號構(gòu)成的序列B．符號構(gòu)成的集合C.字符構(gòu)成的序列D．字符構(gòu)成的集合21．二分查找要求被查找的表是（C）A．鍵值有序的鏈接表B．鏈接表但鍵值不一定有序C．鍵值有序的順序表D．順序表但鍵值不一定有序22.在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：（B）。A．=s;=;B．=;=s;C．=s;=;D．p.>next=;=s;23.一個棧的輸入序列為1，2，3，4，下面哪一個序列不可能是這個棧的輸出序列(C).A、1，3，2，4B、2，3，4，1C、4，3，1，2D、3，4，2，124.折半查找要求查找表中各元素的關(guān)鍵字值必須是（A）排列。Ａ、

遞增或遞減Ｂ、遞增Ｃ、遞減Ｄ、無序25.在已知待排序文件已基本有序的前提下，效率最高的排序方法是（A）A、直接插入排序B、直接選擇排序C、快速排序D、歸并排序26．?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的（B）和操作等的學(xué)科。A．結(jié)構(gòu) B．關(guān)系 C．邏輯存儲D．算法27．下面（C）不是算法所必須具備的特性。 A．有窮性 B．確切性 C．高效性 D．可行性28．已知一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用4個存儲單元，第9個元素的地址為144，則第一個元素的地址是（A）。A．108 B．180 C．176 D．11229．一個棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（C）。A．54321 B．45321 C．43512 D．1234530．假設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為（A）。A．(rear-front+m)%m B．rear-front+1C．(front-rear+m)%mD．(rear-front)%m31．設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（B）。A．連接 B．模式匹配 C．求子串 D．求串長32．串的長度是指（B）A．串中所含不同字母的個數(shù) B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù) D．串中所含非空格字符的個數(shù)33．一棵二叉樹前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷結(jié)果為（A）。A．CBEFDA B．FEDCBA C．CBEDFA D．不定34．在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為（）A．2k-1 B．2k C．2k-1 D．log2k+1CA．2k-1B．2k-1-1C．2k-1D．2k解析：一棵高為k的完全二叉樹，當(dāng)?shù)趉層只有最左邊一個結(jié)點時具有最少的結(jié)點。根據(jù)二叉樹的性質(zhì)，第1層到第k-1層共有結(jié)點2k-1-1個，因此它至少有2k-1-1+1=2k-1個結(jié)點。35．當(dāng)采用分快查找時，數(shù)據(jù)的組織方式為(B)A．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最小）的數(shù)據(jù)組成索引塊D.數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同36．下面關(guān)于線性表的敘述中，錯誤的是（B）。A．線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B．線性表采用順序存儲，便于進行插入和刪除操作。C．線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D．線性表采用鏈接存儲，便于插入和刪除操作。二、判斷題（正確的打“√”，錯誤的打“Х”）1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。(√)2．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。(Х)數(shù)據(jù)項3．隊列邏輯上是一個下端口和上端口能增加又能減少的線性表。（Х）頭只減少，尾只增加4．每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作：插入、刪除和查找。(Х)5．線性表的邏輯順序和存儲順序總是一致的。(Х)6．?dāng)?shù)據(jù)元素可由若干個數(shù)據(jù)項組成。(√)7．線性表的特點是每個元素都有一個前驅(qū)和一個后繼。(Х)8．若輸入序列為1,2,3,4,5,6,則通過一個?？梢暂敵鲂蛄?,2,5,6,4,1。(√)9．空串與空格串是相同的。(Х)10．基于某種邏輯結(jié)構(gòu)之上的運算，其實現(xiàn)是唯一的。(Х)11．評價一個算法時間性能的主要標(biāo)準(zhǔn)是算法的時間復(fù)雜度。(√)12．鏈表中的頭結(jié)點僅起到標(biāo)識的作用。(Х)13．順序存儲的線性表可以隨機存取。(√)14．順序存儲的線性表可以隨機存取。(√)15．單鏈表表示法的基本思想是用指針表示結(jié)點間的邏輯關(guān)系。(√)16．棧與隊列是一種操作受限的線性表。（√）17.數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。(√)18．單鏈表表示法的基本思想是用指針表示結(jié)點間的邏輯關(guān)系。(√)19．棧與隊列是一種操作受限的線性表。（√）20.通常從正確性、易讀性、健壯性、高效性等四個方面評價算法(包括程序)的質(zhì)量。(√)21．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。(Х)數(shù)據(jù)項22．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(√)23．線性表的邏輯順序和存儲順序總是一致的。(Х)24．棧和隊列都是限制存取點的線性結(jié)構(gòu)。（√）25．在二叉樹的先序遍歷序列中，任意一個結(jié)點均處在其子女的前面。(√)26．串是一種數(shù)據(jù)對象和操作都特殊的線性表。（√）27．空串與空格串是相同的。(Х)28．一個有向圖的鄰接表和逆鄰接表中的結(jié)點個數(shù)一定相等。(√)29.線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。(Х)30.順序存儲的線性表可以隨機存取。(√)31.在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的直接前驅(qū)結(jié)點。(Х)32.鏈棧與順序棧相比，有一個比較明顯的優(yōu)點即通常不會出現(xiàn)棧滿的情況。（√）33.設(shè)有一個空棧，現(xiàn)有輸入序列為A、B、C、D、E，經(jīng)過PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作后，輸出序列是B、C。（Х）ADE棧：先進后出34.循環(huán)隊列的隊滿條件為sq.(rear+1)%maxsize==。（√）35.由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹。（Х)36．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。(√)37．順序存儲的線性表可以隨機存取。(√)38．由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹。（Х）39．對鏈表進行插入和刪除操作時，不必移動結(jié)點。(√)40．棧和隊列的共同特點是只允許在端點處插入和刪除。（√）41．在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的直接前驅(qū)結(jié)點。(Х)42．設(shè)有一個空棧，現(xiàn)有輸入序列為A、B、C、D、E，經(jīng)過PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作后，輸出序列是B、C。（Х）43．有向圖用鄰接矩陣表示后，頂點i的入度等于鄰接矩陣中第i列的元素個數(shù)。(√)44．鏈棧與順序棧相比，有一個比較明顯的優(yōu)點即通常不會出現(xiàn)棧滿的情況。（√）45．通常從正確性、易讀性、健壯性、高效性等四個方面評價算法(包括程序)的質(zhì)量。(√)46．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。(Х)數(shù)據(jù)項47．單鏈表表示法的基本思想是用指針表示結(jié)點間的邏輯關(guān)系。(√)48．棧與隊列是一種操作受限的線性表。（√）49．隊列邏輯上是一個下端口和上端口能增加又能減少的線性表。（Х）50．有向圖用鄰接矩陣表示后，頂點i的入度等于鄰接矩陣中第i列的元素個數(shù)。(√)51．鏈棧與順序棧相比，有一個比較明顯的優(yōu)點即通常不會出現(xiàn)棧滿的情況。（√）52.邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。(√)53．健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。(√)54．對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（×）55．順序存儲方式只能用于存儲線性結(jié)構(gòu)。（Х）56．循環(huán)鏈表不是線性表。（Х）57．線性表中每個元素都有一個直接前驅(qū)和一個直接后繼。（Х）58．二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。（√）59．線性表中存在沒有前驅(qū)或后繼的元素。(√)60.基于某種邏輯結(jié)構(gòu)之上的運算，其實現(xiàn)是唯一的。(Х)61．線性表的邏輯順序和存儲順序總是一致的。(Х)62.棧與隊列是一種特殊操作的線性表。(√)63．串是一種數(shù)據(jù)對象和操作都特殊的線性表。（√）64.由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。(√)65．一個有向圖的鄰接表和逆鄰接表中的結(jié)點個數(shù)一定相等。(√)66．冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)。(Х)選擇排序67．對線性表進行折半查找時，要求線性表必須以鏈?zhǔn)椒绞酱鎯?，且結(jié)點按關(guān)鍵字有序排列。(√)68．通常從正確性、易讀性、健壯性、高效性等四個方面評價算法(包括程序)的質(zhì)量。(√)69．對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（×）70．長度為1的串等價于一個字符型常量。(×)71．二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。（√）三、填空題1．鏈棧中，在作進棧運算時不必判別棧是否（空）；在作退棧運算時應(yīng)先判別棧是否（滿）。2．二叉樹由(根結(jié)點)、(左子樹)和(右子樹)三個基本單元組成。3.數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是空間復(fù)雜度、時間復(fù)雜度。4.在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是：_p->next!=NULL。5.在一個長度為n的順序表的第i（1≤i≤n+1）個元素之前插入一個元素，需向后移動n-i+1個元素，刪除第i（1≤i≤n）個元素時，需向前移動n-i個元素。6.設(shè)有一個空棧（每個元素占2個字節(jié)），棧頂指針為1000H，現(xiàn)有輸入序列為1、2、3、4、5，經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是__145，棧頂指針為__5。7．根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有（集合結(jié)構(gòu)）、（線性結(jié)構(gòu)）（樹狀結(jié)構(gòu)）、（網(wǎng)絡(luò)結(jié)構(gòu)）四類基本邏輯結(jié)構(gòu)，它們反映了四類基本的數(shù)據(jù)組織形式。8.串是一種特殊的線性表，其特殊性體現(xiàn)在_數(shù)據(jù)元素是一個字符。9.兩個串相等的充分必要條件是__兩個串的長度相等、_對應(yīng)位置的字符相同。10.一棵二叉樹的第i（i≥1）層最多有__2i-1個結(jié)點；一棵有n（n>0）個結(jié)點的滿二叉樹共有__2/n個葉子結(jié)點和__2/n個非終端結(jié)點。11．一棵有n個結(jié)點的滿二叉樹有（0）個度為1的結(jié)點、有（(n-1)/2）個分支（非終端）結(jié)點和（(n+1)/2）個葉子，該滿二叉樹的深度為（log2n+1）。12.圖的存儲結(jié)構(gòu)主要有兩種，分別是鄰接矩陣和鄰接表13.算法具有的5個特性是:(確定性)、(可行性)、(有窮性)、輸入和輸出。14.順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為(n)次；當(dāng)使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為(n+1)。15.top=0表示?？?，此時作退棧運算，則產(chǎn)生“(下溢)”；top=sqstack_maxsize-1表示棧滿，此時作進棧運算，則產(chǎn)生“(上溢)”。16.線性結(jié)構(gòu)的基本特征是：若至少含有一個結(jié)點，則除起始結(jié)點沒有直接(前驅(qū))外，其他結(jié)點有且僅有一個直接(前驅(qū))；除終端結(jié)點沒有直接(后繼)外，其它結(jié)點有且僅有一個直接(后繼)。17．在樹形結(jié)構(gòu)中，樹根結(jié)點沒有（前驅(qū)）結(jié)點，其余每個結(jié)點有且只有（1）個前驅(qū)結(jié)點；葉子結(jié)點沒有（后繼）結(jié)點，其余每個結(jié)點的后繼結(jié)點可以有（任意多）個。18.根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有集合、(線性)、(樹狀)、(網(wǎng)絡(luò))四類基本邏輯結(jié)構(gòu)，它們反映了四類基本的數(shù)據(jù)組織形式。19.組成串的數(shù)據(jù)元素只能是(單個字符)，空串是（空格），其長度等于（空格個數(shù)）。20.具有n個結(jié)點的二叉樹的中,一共有2n個指針域,其中只有(n-1)個用來指向結(jié)點的左右孩子，其余的（n+1）個指針域為NULL。21．根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有（集合結(jié)構(gòu)）、（線性結(jié)構(gòu)）（樹狀結(jié)構(gòu)）、（網(wǎng)絡(luò)結(jié)構(gòu)）四類基本邏輯結(jié)構(gòu)，它們反映了四類基本的數(shù)據(jù)組織形式。22．在樹形結(jié)構(gòu)中，樹根結(jié)點沒有（前驅(qū)）結(jié)點，其余每個結(jié)點有且只有（1）個前驅(qū)結(jié)點；葉子結(jié)點沒有（后繼）結(jié)點，其余每個結(jié)點的后繼結(jié)點可以有（任意多）個。23．二叉排序樹是一種特殊的、增加了限制條件的二叉樹，其限制條件是任一結(jié)點的鍵值（大）于其左孩子（及其子孫）的鍵值且（小）于其右孩子（及其子孫）的鍵值。24．鏈棧中，在作進棧運算時不必判別棧是否（空）；在作退棧運算時應(yīng)先判別棧是否（滿）。25．一棵有n個結(jié)點的滿二叉樹有（0）個度為1的結(jié)點、有（(n-1)/2）個分支（非終端）結(jié)點和（(n+1)/2）個葉子，該滿二叉樹的深度為（log2n+1）。26．二叉樹由(根結(jié)點)、(左子樹)和(右子樹)三個基本單元組成。27．棧中存取數(shù)據(jù)的原則是（先進后出），隊列中存取數(shù)據(jù)的原則是（先進先出）。28．組成串的數(shù)據(jù)元素只能是(單個字符)，空串是（空格），其長度等于（空格個數(shù)）。29．?dāng)?shù)據(jù)結(jié)構(gòu)是討論數(shù)據(jù)元素關(guān)系的集合，描述數(shù)據(jù)間1：1關(guān)系的是線性結(jié)構(gòu)、描述1：m關(guān)系的是樹狀結(jié)構(gòu)、描述m：n關(guān)系的是圖結(jié)構(gòu)。30．我們將數(shù)據(jù)結(jié)構(gòu)在計算機中的表示形式稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲結(jié)構(gòu)，則數(shù)據(jù)結(jié)構(gòu)在計算機中主要有兩種不同的存儲結(jié)構(gòu)，順序表邏輯上相鄰的元素的物理位置必定相鄰，單鏈表中邏輯上相鄰的元素的物理位置則不一定相鄰。31．具有先進先出操作特征的數(shù)據(jù)結(jié)構(gòu)是隊列、具有先進后出的操作特征的數(shù)據(jù)結(jié)構(gòu)是棧。32．棧中存取數(shù)據(jù)的原則是（先進后出），隊列中存取數(shù)據(jù)的原則是（先進先出）。33．組成串的數(shù)據(jù)元素只能是(單個字符)，空串是（空格），其長度等于（空格個數(shù)）。34．二叉排序樹是一種特殊的、增加了限制條件的二叉樹，其限制條件是任一結(jié)點的鍵值（大）于其左孩子（及其子孫）的鍵值且（小）于其右孩子（及其子孫）的鍵值。35．根據(jù)二叉樹的特征，我們可以知道，一顆深度為k的滿二叉樹的節(jié)點個數(shù)有2k-1。36．我們在討論圖的存儲結(jié)構(gòu)時主要使用了鄰接矩陣和鄰接表兩種。37．在討論查找表時，我們主要討論了兩種查找表