數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上習(xí)題1一、選擇題1數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（ ）及它們之間的相互聯(lián)系。A存儲結(jié)構(gòu)和邏輯結(jié)構(gòu) B存儲和抽象 C聯(lián)系和抽象 D聯(lián)系與邏輯2從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)3數(shù)據(jù)處理的基本單位是（ ）。A數(shù)據(jù)元素B數(shù)據(jù)項 C數(shù)據(jù)類型 D數(shù)據(jù)變量 4數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)中元素對應(yīng)關(guān)系為（ ）。A一對一 B一對多C多對多 D無關(guān)系5數(shù)據(jù)結(jié)構(gòu)中樹形結(jié)構(gòu)中元素對應(yīng)關(guān)系為（ ）。A一對一 B一對多 C多對多 D無關(guān)系6數(shù)據(jù)結(jié)構(gòu)中圖形結(jié)構(gòu)中元素對應(yīng)關(guān)系為（ ）。A一對一 B一對多 C多對多

2、D無關(guān)系7數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱為（ ）。A存儲結(jié)構(gòu) B邏輯結(jié)構(gòu) C順序存儲結(jié)構(gòu) D鏈?zhǔn)酱鎯Y(jié)構(gòu)8非線性結(jié)構(gòu)中的每個結(jié)點（ ）。A無直接前趨結(jié)點 B無直接后繼結(jié)點C只有一個直接前趨結(jié)點和一個直接后繼結(jié)點D可能有多個直接前趨結(jié)點和多個直接后繼結(jié)點9鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間（ ）。A分兩部分，一部分存放結(jié)點的值，另一部分存放表示結(jié)點間關(guān)系的指針B只有一部分，存放結(jié)點的值C只有一部分，存儲表示結(jié)點間關(guān)系的指針D分兩部分，一部分存放結(jié)點的值，另一部分存放結(jié)點所占單元素10算法分析的兩個主要方面是（ ）。A正確性和簡單性 B可讀性和文檔性 C數(shù)據(jù)復(fù)雜性和

3、程序復(fù)雜性 D時間復(fù)雜度和空間復(fù)雜度11算法的計算量大小稱為算法的（ ）。A現(xiàn)實性 B難度 C時間復(fù)雜性 D效率12數(shù)據(jù)的基本單位是（ ）。A數(shù)據(jù)結(jié)構(gòu) B數(shù)據(jù)元素 C數(shù)據(jù)項 D文件13每個結(jié)點只含有一個數(shù)據(jù)元素，所有存儲結(jié)點相繼存放在一個連續(xù)的存儲區(qū)里，這種存儲結(jié)構(gòu)稱為（ ）結(jié)構(gòu)。A順序存儲 B鏈?zhǔn)酱鎯?C索引存儲 D散列存儲14每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（ ）存儲方式。A順序 B鏈?zhǔn)?C索引 D散列15以下任何兩個結(jié)點之間都沒有邏輯關(guān)系的是（ ）。A圖形結(jié)構(gòu) B線性結(jié)構(gòu) C樹形結(jié)構(gòu) D集合16在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是（ ）。A物理結(jié)構(gòu) B存

4、儲結(jié)構(gòu) C邏輯結(jié)構(gòu) D邏輯和存儲結(jié)構(gòu)17下列四種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（ ）。A集合 B線性結(jié)構(gòu) C樹形結(jié)構(gòu) D圖形結(jié)構(gòu)18與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（ ）。A邏輯結(jié)構(gòu) B存儲結(jié)構(gòu) C邏輯實現(xiàn) D存儲實現(xiàn)19每一個存儲結(jié)點只含有一個數(shù)據(jù)元素，存儲結(jié)點存放在連續(xù)的存儲空間，另外有一組指明結(jié)點存儲位置的表，該存儲方式是（ ）存儲方式。A順序 B鏈?zhǔn)?C索引 D散列20算法能正確的實現(xiàn)預(yù)定功能的特性稱為算法的（ ）。A正確性 B易讀性 C健壯性 D高效性21算法在發(fā)生非法操作時可以做出處理的特性稱為算法的（ ）。A正確性 B易讀性 C健壯性 D高效性2

5、2下列時間復(fù)雜度中最壞的是（ ）。AO(1) BO(n) CO(log2n) DO(n2)23在下面的程序段中，對x的賦值語句的頻度為（ ）。 for( i=1;i<n;i+) for(j=1;j<n;j+) x+;AO(2n) BO(n) CO(n2) DO(log2n) 二、填空題1常見的數(shù)據(jù)結(jié)構(gòu)有集合、線性結(jié)構(gòu)、 結(jié)構(gòu)、 結(jié)構(gòu)。2算法的5個重要特性是有窮性、 、可行性、輸入、 。3評價算法的優(yōu)劣通常主要考慮算法的 和 這兩方面。4線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 關(guān)系。5數(shù)據(jù)的存儲結(jié)構(gòu)又叫 。6數(shù)據(jù)結(jié)構(gòu)被定義為(D，R)，其中

6、D是數(shù)據(jù)的有限集合，R是D上的 的有限集合。7算法的空間復(fù)雜度是指該算法所耗費的 ，它是該算法求解問題規(guī)模n的函數(shù)。8算法是一個 的集合，算法效率的度量可以分為 和 。9若一個算法中的語句頻度之和為T(n)=7n+4n2，則算法的時間復(fù)雜度為 。10設(shè)有一組數(shù)據(jù)元素需存儲，為了方便查找某元素，數(shù)據(jù)宜采用 存儲結(jié)構(gòu)；為了方便插入與刪除某元素，數(shù)據(jù)宜采用 存儲結(jié)構(gòu)。三、判斷題1數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。（ ）2一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上一個基本運算集構(gòu)成的整體。（ ）3數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ ）4數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是相同的。（ ）5程序和算法

7、原則上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時可以通用。 （ ）6從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。 （ ）7數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映像。（ ）習(xí)題2一、選擇題1下面關(guān)于線性表的敘述中，錯誤的是（ ）。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。2在有n個結(jié)點的順序表上做插入、刪除結(jié)點運算的時間復(fù)雜度為（ ）。AO(1) BO(n)CO(n2)DO(log2n)3兩個指針P和Q，分別指向單鏈表的兩個元素，P所指元素是Q所指元

8、素前驅(qū)的條件是（ ）。AP->next = Q->next BP->next = Q CQ->next = PDP = Q4在單鏈表中，增加頭結(jié)點的目的是（ ）。A使單鏈表至少有一個結(jié)點 B標(biāo)志表中首結(jié)點的位置C方便運算的實現(xiàn) D說明該單鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)5在順序表中，只要知道（ ），就可以求出任意一個結(jié)點的存儲地址。A基地址 B結(jié)點大小 C向量大小 D基地址和結(jié)點大小6鏈表不具備的特點是（ ）。A隨機(jī)訪問 B不必事先估計存儲空間C插入刪除時不需移動元素 D所需空間與線性表成正比7在（ ）的運算中，使用順序表比鏈表好。A插入 B根據(jù)序號查找 C刪除 D根據(jù)元素查

9、找8在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是（ ）。Ap->next=s;s->next=p->next; Bs->next=p->next;p->next=s;Cp->next=s;p->next=s->next; Dp->next=s->next;p->next=s;9用鏈表表示線性表的優(yōu)點是（ ）。A便于進(jìn)行插入和刪除操作 B便于隨機(jī)存取C占用的存儲空間較順序表少 D元素的物理順序與與邏輯順序一致10在一個長度為n的順序表中，若要刪除第i（1in）個元素，則需向前移動（ ）個元素。An-i+1 Bn

10、-i-1 Cn-i Di11在一個長度為n的順序表中，若要在第i（1in）個元素前插入一個元素時，則需向后移動（ ）個元素。An-i+1 Bn-i-1 Cn-i Di12設(shè)p為指向單循環(huán)鏈表上某結(jié)點的指針，則*p的直接前驅(qū)（ ）。A找不到 B查找時間復(fù)雜度為O(1)C查找時間復(fù)雜度為O(n)D查找結(jié)點的次數(shù)約為n13等概率情況下，在有n個結(jié)點的順序表上做插入結(jié)點運算，需平均移動結(jié)點的數(shù)目為（ ）。AnB(n-1)/2 Cn/2 D(n+1)/214以下鏈表結(jié)構(gòu)中，從當(dāng)前結(jié)點出發(fā)能夠訪問到任意結(jié)點的是（ ）。A單向鏈表和雙向鏈表 B循環(huán)鏈表和單向鏈表C循環(huán)鏈表和雙向鏈表 D單向鏈表、雙向鏈表和循

11、環(huán)鏈表15對具有n個結(jié)點的線性表進(jìn)行插入或刪除操作，所需的算法時間復(fù)雜度為（ ）。AO(n2) BO(nlog2n) CO(log2n) DO(n)二、填空題1線性表L=(a1,a2,an)采用順序存儲，假定刪除表中任意元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是 。2順序表相對于鏈表的優(yōu)點是： 和隨機(jī)存?。绘湵硐鄬τ陧樞虮淼膬?yōu)點是： 方便。3在單鏈表中要在已知結(jié)點*P之前插入一個新結(jié)點，需找到*P的直接前趨結(jié)點的地址，其查找的時間復(fù)雜度為 。4在長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移 個元素。 5鏈表相對于順序表的優(yōu)點是插入、刪除方便；缺點是存儲密度 。6鏈?zhǔn)?/p>

12、存儲的特點是利用 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。7在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向其 結(jié)點，另一個指向其 結(jié)點。8在一個雙鏈表中，設(shè)指針p是指向該表中待刪除的結(jié)點，則需要執(zhí)行的操作為： 。9若對一個線性表經(jīng)常進(jìn)行查找操作，而很少進(jìn)行插入和刪除操作時，則采用 存儲結(jié)構(gòu)為宜，相反，若經(jīng)常進(jìn)行的是插入和刪除操作時，則采用 存儲結(jié)構(gòu)為宜。三、判斷題1線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。（ ）2鏈表的每個結(jié)點都恰好包含一個指針域。（ ）3在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。（ ）4順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。（ ）5線性鏈表的刪除算

13、法簡單，因為當(dāng)刪除鏈中某個結(jié)點后，計算機(jī)會自動地將后續(xù)的各個單元向前移動。6順序表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。（ ）7線性表鏈?zhǔn)酱鎯Φ奶攸c是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。 （ ）8線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 （ ）9順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 （ ）10插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。 （ ）習(xí)題3一、選擇題1對于棧操作數(shù)據(jù)的原則是（ ）。A先進(jìn)先出 B后進(jìn)先出 C后進(jìn)后出 D不分順序2有6個元素按6,5,4,3,2,1 的順序進(jìn)棧，問下列（ ）

14、不是合法的出棧序列？ A5 4 3 6 1 2 B4 5 3 1 2 6C3 4 6 5 2 1 D2 3 4 1 5 6 3插入和刪除只能在一端進(jìn)行的線性表，稱為（ ）。 A隊列 B循環(huán)隊列 C棧 D循環(huán)棧 4輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為（ ）。 Apush,pop,push,pop,push,pop Bpush,push,push,pop,pop,popCpush,push,pop,pop,push,pop Dpush,pop,push,push,pop,pop5設(shè)有編號為1,2,3,4的四輛列車，順序進(jìn)入一個棧結(jié)構(gòu)的站臺，下列不可能的出站順序為（ ）。A1234 B

15、1243 C1324 D14236如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（ ）。A必須判別棧是否滿 B必須判別棧是否空C必須判別棧元素類型 D隊?？刹蛔鋈魏闻袆e7順序棧存儲空間的實現(xiàn)使用（ ）存儲棧元素。 A鏈表 B數(shù)組 C循環(huán)鏈表 D變量8在C語言中，一個順序棧一旦被聲明，其占用空間的大小（ ）。A已固定 B不固定 C可以改變 D動態(tài)變化9從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪除的結(jié)點，應(yīng)執(zhí)行下列（ ）命令。 Ax=top;top=top->next; Btop=top->next;x=top->data; Cx=top->data; Dx=to

16、p->data;top=top->next;104個元素按A,B,C,D順序進(jìn)S棧，執(zhí)行兩次Pop(S,x)運算后，棧頂元素的值是（ ）。 AA BB CC DD11在一個棧頂指針為HS的鏈棧中，將一個S指針?biāo)傅慕Y(jié)點入棧，應(yīng)執(zhí)行下列（ ）命令。AHS->next=S; BS->next=HS->next;HS->next=S;CS->next=HS->next;HS=S; DS->next=HS;HS=HS->next;12向順序棧中壓入元素時，（ ）。A先存入元素，后移動棧頂指針B先移動棧頂指針，后存入元素C誰先誰后無關(guān)緊要 D同

17、時進(jìn)行13一個棧的入棧次序ABCDE，則棧的不可能的輸出序列是（ ）。AEDCBA BDECBACDCEABDABCDE14設(shè)有一個順序棧S，元素A,B,C,D,E,F,依次進(jìn)棧，如果6個元素出棧的順序是B,D,C,F,E,A，則棧的容量至少應(yīng)是（ ）。 A3 B4 C5 D6二、填空題 1對于棧只能在 位置插入和刪除元素。2在順序棧中，當(dāng)棧頂指針top=-1時，表示 。3在有n個元素的棧中，進(jìn)棧操作的時間復(fù)雜度為 。4在棧中，出棧操作的時間復(fù)雜度為： 。5在一個鏈棧中，若棧頂指針等于NULL，則表示 。6向一個棧頂指針為top的鏈棧插入一個新結(jié)點*p時，應(yīng)執(zhí)行 和 操作。7已知順序棧S，在對

18、S進(jìn)行進(jìn)棧操作之前首先要判斷 。8已知順序棧S，在對S進(jìn)行出棧操作之前首先要判斷 。94個元素按A,B,C,D順序進(jìn)S棧，執(zhí)行兩次Pop（S，x）運算后，x的值是 。10當(dāng)棧中元素為M時，做進(jìn)棧操作時發(fā)生上溢，則說明棧的最大容量為 。11一個棧的輸入序列是：1,2,3則不可能的棧輸出序列是 。12若進(jìn)棧的次序是A,B,C,D,E，執(zhí)行3次出棧操作以后，棧頂元素為 。三、判斷題1棧是運算受限制的線性表。 （ ）2在?？盏那闆r下，不能做出棧操作，否則產(chǎn)生下溢出。 （ ）3棧一定是順序存儲的線性結(jié)構(gòu)。 （ ）4棧的特點是“后進(jìn)先出”。 （ ）5空棧就是所有元素都為0的棧。 （ ）6在C語言中設(shè)順序棧

19、的長度為MAXLEN，則top=MAXLEN時表示隊滿。 （ ）7鏈棧與順序棧相比，其特點之一是通常不會出現(xiàn)棧滿的情況。 （ ）8一個棧的輸入序列為：A,B,C,D，可以得到輸出序列：C,A,B,D。 （ ）9遞歸定義就是循環(huán)定義。 （ ）10將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。 （ ）四、應(yīng)用題 1寫出下列程序段的運行結(jié)果（棧中的元素類型是char）：main()SeqStack S;char x, y;InitStack(&S);x = 'C'y = 'K'Push(&S, x);Push(&S, 'A');P

20、ush(&S, y);Pop(&S, &x);Push(&S, 'T');Push(&S, x);Pop(&S, &x);Push(&S, 'S');while (!EmptyStack(&S)Pop(&S, &y);printf("%c", y);printf("%cn", x);2將一個非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)的算法實現(xiàn)。3設(shè)計一個算法判別算術(shù)表達(dá)式中的圓括號是否配對正確。習(xí)題4一、選擇題1對于隊列操作數(shù)據(jù)的原則是（ ）。A先進(jìn)

21、先出B后進(jìn)先出C先進(jìn)后出D不分順序2隊列是限定在（ ）進(jìn)行操作的線性表。A中間B隊首C隊尾D端點3隊列中的元素個數(shù)是（ ）。A不變的B可變的C任意的D04同一隊列內(nèi)各元素的類型（ ）。A必須一致B不能一致 C可以不一致D不限制5隊列是一個（ ）線性表結(jié)構(gòu)。A不加限制的 B推廣了的 C加了限制的 D非6當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最后一個元素的下標(biāo)為（ ）。An-2 Bn-1Cn Dn+17最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（ ）。A(rear+1) % n=front Brear=front Crear+1=front D(rear

22、-1) % n=front8最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊滿的條件是（ ）。A(rear+1) % n=front Brear=front Crear+1=front D(rear-l) % n=front9循環(huán)隊列占用的空間（ ）。A必須連續(xù)B不必連續(xù) C不能連續(xù) D可以不連續(xù)10存放循環(huán)隊列元素的數(shù)組data有10個元素，則data數(shù)組的下標(biāo)范圍是（ ）。A010 B09C19 D11011若進(jìn)隊的序列為：A，B，C，D，則出隊的序列是（ ）。AB，C，D，A BA，C，B，D CA，B，C，D DC，B，D，A124個元素按：A，B，C，D順序連續(xù)進(jìn)隊

23、Q，則隊尾元素是（ ）。AA BB CC DD13循環(huán)隊列SQ隊滿的條件是（ ）。ASQ->rear=SQ->front B(SQ->rear+1)% MAXLEN =SQ->frontCSQ->rear=0 DSQ->front=014設(shè)鏈棧中結(jié)點的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。若想在鏈棧的棧頂插入一個由指針s所指的結(jié)點，則應(yīng)執(zhí)行下列（ ）操作。As->next=top->next；top->next=s；Btop->next=s； Cs->next=top；top=top->next；D

24、s->next=top；top=s；15若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為（ ）。A5和1 B4和2 C2和4 D1和516棧和隊列的共同點是（ ）。A都是先進(jìn)先出 B都是先進(jìn)后出 C只允許在端點處插入和刪除元素 D沒有共同點17棧和隊都是（ ）。A順序存儲的線性結(jié)構(gòu) B鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)C限制存取點的線性結(jié)構(gòu) D限制存取點的非線性結(jié)構(gòu)二、填空題 1循環(huán)隊列的引入，目的是為了克服 現(xiàn)象。 2在隊列中存取數(shù)據(jù)應(yīng)遵循的原則是 。3 是被限定為只能在表的一端進(jìn)行插入運算，在

25、表的另一端進(jìn)行刪除運算的線性表。4在隊列中，允許插入的一端稱為 。5在隊列中，允許刪除的一端稱為 。6隊列在進(jìn)行出隊操作時，首先要判斷隊列是否為 。7順序隊列在進(jìn)行入隊操作時，首先要判斷隊列是否為 。8順序隊列初始化后，front=rear= 。9循環(huán)隊列的隊首指針為front，隊尾指針為rear，則隊空的條件為 。10鏈隊列LQ為空時，LQ->front->next= 。11在一個鏈隊列中，若隊首指針與隊尾指針的值相同，則表示該隊列為 。12設(shè)循環(huán)隊列的頭指針front指向隊首元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，則隊滿標(biāo)志為 。三、判斷

26、題1隊列是限制在兩端進(jìn)行操作的線性表。 （ ）2判斷順序隊列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個結(jié)點。 （ ）3在鏈隊列上進(jìn)行出隊操作時，會改變front指針的值。 （ ）4在循環(huán)隊列中，若尾指針rear大于頭指針front，其元素個數(shù)為rear-front。 （ ）5在單向循環(huán)鏈表中，若頭指針為h，那么p所指結(jié)點為尾結(jié)點的條件是p=h。6鏈隊列在一定范圍內(nèi)不會出現(xiàn)隊滿的情況。（ ）7在循環(huán)鏈隊列中無溢出現(xiàn)象。 （ ）8棧和隊列都是順序存儲的線性結(jié)構(gòu)。（ ）9在隊列中允許刪除的一端稱為隊尾。（ ）10順序隊和循環(huán)隊關(guān)于隊滿和隊空的判斷條件是一樣的。（ ）四、應(yīng)用題 1請簡述線性表、棧、隊列有

27、什么異同？2寫出下列程序段的運行結(jié)果（隊列中的元素類型是char）main()SeqQueue Q;char x, y;x = 'E'y = 'C'InitQueue(&Q);EnQueue(&Q, 'H');EnQueue(&Q, 'R');EnQueue(&Q, y);DeQueue(&Q, &x);EnQueue(&Q, x);DeQueue(&Q, &x);EnQueue(&Q, 'A');while (!EmptyQueue(

28、&Q)DeQueue(&Q, &y);printf("%c", y);printf("%cn", x);3假定用一個循環(huán)單鏈表表示一個循環(huán)隊列，該隊列只設(shè)一個隊尾指針rear，試填空完成向循環(huán)隊列中插入一個元素為x的結(jié)點的函數(shù)。typedef struct queuenodeint data;struct queuenode *next;qu;InQueue(qu *rear, int x)qu *head, *s;s = （1）;s->data = （2）;if (rear = NULL) rear = s; rear-&

29、gt;next=( 3); elsehead = （4）; rear->next = （5）;rear = s;（6） = head;4一個用單鏈表組成的循環(huán)隊列，只設(shè)一個尾指針rear，不設(shè)頭指針，請編寫如下算法：（1）向循環(huán)隊列中插入一個元素為x的結(jié)點；（2）從循環(huán)隊列中刪除一個結(jié)點。習(xí)題5一、選擇題1以下說法正確的是（ ）。A串是一種特殊的線性表B串的長度必須大于零 C串中的元素只能是字母D空串就是空白串2設(shè)有一個字符串S="Welcome to Shenyang!"，問該串的長度為（ ）。A18 B19 C20 D213設(shè)有一個字符串S="abcde

30、fgh"，問該串的最大子串個數(shù)為（ ）。A8 B36 C37 D94兩個字符串相等的條件是（ ）。A兩串的長度相等B兩串包含的字符相同 C兩串的長度相等，并且兩串包含的字符相同 D兩串的長度相等，并且對應(yīng)位置上的字符相同5某串的長度小于一個常數(shù)，則采用（ ）存儲方式最節(jié)省空間。A鏈?zhǔn)?B順序 C堆結(jié)構(gòu) D無法確定6以下論述正確的是（ ）。A空串與空格串是相同的B"tel"是"Teleptone"的子串C空串是零個字符的串D空串的長度等于17以下論斷正確的是（ ）。A“”是空串，“ ”是空格串B"BEIJING"是"

31、BEI JING"的子串C"something"<"Somethig"D"BIT"="BITE"8設(shè)有兩個串S1和S2，則StrCompare(S1,S2)運算稱做（ ）。A. 串連接 B模式匹配C. 求子串 D串比較9串的模式匹配是指（ ）。A判斷兩個串是否相等B對兩個串比較大小C找某字符在主串中第一次出現(xiàn)的位置D找某子串在主串中第一次出現(xiàn)的第一個字符位置10若SubString(Sub,S,pos,len)表示用Sub返回串S的第pos個字符起長度為len的子串的操作，則對于S="Da

32、ta Structure"，SubString(Sub,S,6,3)的結(jié)果為（ ）。A"ta Str" B"Str" C" tru" D以上均不正確11若StrIndex(S,T)表示求T在S中的位置的操作，則對于S="Beijing and Nanjing"，T="jing"，StrIndex(S,T)的結(jié)果為（ ）。A2 B3 C4 D1612S="morning"，執(zhí)行求子串函數(shù)SubStr(S,2,2)后的結(jié)果為（ ）。 A"mo" B&

33、quot;or" C"in" D"ng"13S1="Good"，S2="Morning"，執(zhí)行串連接函數(shù)ConcatStr(S1,S2)后的結(jié)果為（ ）。A"GoodMorning"B"Good Morning"C"GOODMORNING" D"GOOD MORNING"14S1="good"，S2="morning"，執(zhí)行函數(shù)SubStr(S2,4,LenStr(S1)后的結(jié)果為（ ）

34、。A"good" B"ning" C"go" D"morn"15設(shè)串S1="ABCDEFG"，S2="PQRST" ,則ConcatStr(SubStr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)的結(jié)果串為（ ）。ABCDEF BBCDEFG CBCPQRST DBCDEFEF16廣義表是線性表的推廣，它們之間的區(qū)別在于（ ）。A能否使用子表 B能否使用原子項C是否能為空 D表的長度17廣義表(a,b),c,d)的表尾是（ ）。Aa Bb

35、C(a,b) D(c,d)18廣義表(a,b,c,d,e)的表尾是（ ）。A(b,c,d,e) B() C(a,b,c,d,e) D(e)二、填空題 1字符串按存儲方式可以分為：順序存儲、鏈接存儲和 。2在C語言中，以字符 表示串值的終結(jié)。3空格串的長度等于 。4在空串和空格串中，長度不為0的是 。5兩個串相等是指兩個串長度相等，且對應(yīng)位置的 。6設(shè)S=“My mather”，則LenStr(s)= 。7兩個字符串分別為：S1="Today is"，S2="24 July,2011",ConcatStr(S1,S2)的結(jié)果是： 。8串順序存儲非緊湊格式的

36、缺點是 。9串順序存儲緊湊格式的缺點是對串的字符處理 。10串鏈接存儲的優(yōu)點是 ，缺點是 。11假設(shè)有兩個字符串S1和S2，其中S1="abcdxyz"，S2="rest"，那么如果進(jìn)行了下面的運算StrCat(SubString(Sub, S1,3,2), SubString(Sub, S1, StrLength(S2),3)，其結(jié)果為 。 12廣義表(a),(b),(c,d,e)的表頭是_，表尾是 _。三、判斷題 1串是n個字母的有限序列（n0 ）。 （ ） 2空串與由空格組成的串沒有區(qū)別。 （ ） 3空串是任意串的子串。 （ ）4在順序存儲結(jié)構(gòu)中，

37、串的插入算法是非常方便的。 （ ）5數(shù)組的順序存儲結(jié)構(gòu)有兩種：按行序存儲與按列序存儲。 （ ）6串的數(shù)據(jù)元素是一個字符。 （ ）7串的長度是指串中不同字符的個數(shù)。 （ ）8如果兩個串含有相同的字符，則說明它們相等 （ ）9如果一個串中所有的字母均在另一個串中出現(xiàn)，則說明前者是后者的子串。 （ ）10串的堆分配存儲是一種動態(tài)存儲結(jié)構(gòu)。 （ ）11“DT”是“DATA”的子串。 （ ）12串中任意個字符組成的子序列稱為該串的子串 （ ）13子串的定位運算稱為模式匹配。 （ ）14在鏈串中為了提高存儲密度，應(yīng)該增大結(jié)點的大小。 （ ）15廣義表不能遞歸。 （ ）16廣義表組成的元素可以是不同形式的元

38、素。 （ ）四、應(yīng)用題1下面程序是把兩個串r1和r2首尾相連的程序，即：r1=r1+r2，試完成程序填空。typedef Struct char vecMAXLEN; /*定義合并后串的最大長度*/ int len; /*len為串的長度*/St;void ConcatStr(Str *r1, Str *r2) /*字符串連接函數(shù)*/int i; cout << r1->vec << r2->vec;if (r1->len + r2->len> （1）) cout << "兩個串太長，溢出！"elsefor

39、(i = 0; i< （2）; i+) /*把r2連接到r1*/r1->vec（3） = r2->veci;r1->vecr1->len + i = （4）; /*添上字符串結(jié)束標(biāo)記*/r1->len = （5）; /*修改新串長度*/2設(shè)x和y兩個串均采用順序存儲方式，下面的程序是比較x 和y兩個串是否相等的函數(shù)，試完成程序填空。#define MAXLEN 100typedef structchar vecMAXLEN;int len; str;int same(str *x,str *y)int i = 0, tag = 1;if (x->len

40、 （1） y->len) return (0);elsewhile (i<x->len （2） tag) if (x->veci （3） y->veci) （4）; （5）; return (tag);3簡述廣義表具有哪些性質(zhì)？4編寫算法，求串S中所含不同字符的總數(shù)和每種字符的個數(shù)。5有兩個串S1和S2，設(shè)計一個算法，求一個串T，使其中的字符是S1和S2中的公共字符。習(xí)題6一、選擇題1假設(shè)在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為（ ）個。A15 B16 C17 D472在一棵二叉樹上第3層上的結(jié)點數(shù)最多為（ ）。A2 B4 C6 D

41、83用順序存儲的方法將完全二叉樹中所有結(jié)點逐層存放在數(shù)組a1an中，結(jié)點ai若有左孩子，其左孩子的編號為結(jié)點（ ）。Aa2i+1 Ba2i-1 Cai/2 Da2i4已知一棵完全二叉樹的結(jié)點總數(shù)為9個，則最后一層的結(jié)點數(shù)為（ ）。A1 B2 C3 D45具有35個結(jié)點的完全二叉樹的深度為（ ）。A 5 B 6 C 7 D 86二叉樹的先序遍歷序列為ABC的不同二叉樹有（ ）種形態(tài)。A 3 B 4 C 5 D 67設(shè)有一棵二叉樹，其先序遍歷序列是：ABCDEFG，中序遍歷序列是：CBAEDFG，則該二叉樹的后序遍歷序列是（ ）。ACBDFGEA BCBDGFEA CCBEFGDA DCBEGFD

42、A8某二又樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則先序遍歷序列為（ ）。AACBED BDECAB CDEABC DCEDBA9在完全二叉樹中，如果一個結(jié)點是葉子結(jié)點，則它沒有（ ）。A左孩子結(jié)點 B右孩子結(jié)點 C左、右孩子結(jié)點 D左、右孩子結(jié)點和兄弟結(jié)點10在下列存儲形式中，哪一種不是樹的存儲形式（ ）。A雙親表示法 B孩子鏈表表示法 C孩子兄弟鏈表表示法D順序存儲表示法11樹最適合用來表示（ ）。A有序數(shù)據(jù)元素B元素之間具有分支層次關(guān)系的數(shù)據(jù)C無序數(shù)據(jù)元素D元素之間無聯(lián)系的數(shù)據(jù)12在下圖所示的四棵二叉樹中，不屬于完全二叉樹的是（ ）。13在一棵度為3的樹中，度為3的結(jié)點數(shù)

43、為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，那么度為0的結(jié)點數(shù)有（ ）個。A4 B5 C6 D714任何一棵二叉樹的葉子結(jié)點在先序、中序、后序遍歷序列中的相對次序（ ）。A不發(fā)生改變 B發(fā)生改變 C不能確定 D以上都不對15A、B為一棵二叉樹上的兩個葉子結(jié)點，在中序遍歷時，A在B前的條件是（ ）。AA在B的右方 BA是B的祖先 CA在B的左方 DA是B的子孫二、填空題 1樹中結(jié)點的最大層次稱為樹的_。2假定一棵樹的廣義表表示法為A(B(E),C(F(H,I,J),G),D)，則該樹的度為_，樹的深度為_，終端結(jié)點的個數(shù)為_，單分支結(jié)點的個數(shù)為_，雙分支的結(jié)點個數(shù)為_，三分支的結(jié)點個數(shù)為

44、_，C結(jié)點的雙親結(jié)點為_，其孩子結(jié)點為_和_結(jié)點。3對于一個具有n個結(jié)點的二叉樹，當(dāng)它為一棵_二叉樹時，具有最小高度，即為_，當(dāng)它為一棵單支樹時具有_高度，即為_。4一棵深度為k的滿二叉樹的結(jié)點總數(shù)為_，一棵深度為k的完全二叉樹的結(jié)點總數(shù)的最小值為_，最大值為_。5對于二叉樹來說，第i層上最多有_個結(jié)點。6由三個結(jié)點構(gòu)成的二叉樹，共有_種不同的結(jié)構(gòu)。7由一棵二叉樹的先序序列和_序列可唯一確定這棵二叉樹。8設(shè)F是森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點，B中右指針域為空的結(jié)點有_。9先序序列和中序序列相同的二叉樹為_。10設(shè)一棵二叉樹共有50個葉子結(jié)點（終端結(jié)點），則有_度為2的結(jié)點。11哈夫曼樹是指_的二叉樹。12由帶權(quán)為3，6，2，5的4個葉子結(jié)點構(gòu)成的一棵哈夫曼樹，則帶權(quán)路徑長度為_。三、判斷題1在任意一棵二叉