數(shù)據(jù)結(jié)構(gòu)習(xí)題集(包含全部答案)

1、精品文檔數(shù)據(jù)結(jié)構(gòu)習(xí)題集（自編）第一章緒論一、選擇題1數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中的操作對(duì)象以及它們之間的（）和運(yùn)算的學(xué)科。a結(jié)構(gòu)b關(guān)系c運(yùn)算d算法2在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。a動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)b緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)c線性結(jié)構(gòu)和非線性結(jié)構(gòu)d邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)3線性表的邏輯順序和存儲(chǔ)順序總是一致的，這種說法（）。a正確b不正確c無法確定d以上答案都不對(duì)4算法分析的目的是（）。a找出算法的合理性b研究算法的輸人與輸出關(guān)系c分析算法的有效性以求改進(jìn)d分析算法的易懂性5.算法的時(shí)間復(fù)雜度取決于（）a問題的規(guī)模b待處理數(shù)據(jù)的初態(tài)c.a和b6一個(gè)算法應(yīng)該是（）。a程序b

2、問題求解步驟的描述c要滿足五個(gè)基本特性da和c.7.下面關(guān)于算法說法錯(cuò)誤的是（）a算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)b.為解決某問題的算法與為該問題編寫的程序含義是相同的c.算法的可行性是指指令不能有二義性d.以上幾個(gè)都是錯(cuò)誤的8以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（）。a循環(huán)隊(duì)列b.鏈表c.哈希表d.棧9在下面的程序段中，對(duì)x的賦值語句的頻度為（）for（i=0;in;i+）for(j=0;jn;j+)x=x+1;a2nbncn2dlogn210以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)a樹b字符串c隊(duì)列d棧11.下列數(shù)據(jù)中，（）是線性數(shù)據(jù)結(jié)構(gòu)。a哈夫曼樹b.有向無環(huán)圖c.二叉排序樹d.棧12以下屬于邏輯結(jié)

3、構(gòu)的是（）。a順序表b.哈希表c.有序表d.單鏈表二、填空題1、_是信息的載體，是對(duì)客觀事物的符號(hào)表示，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)、加工和處理，_是對(duì)能夠有效的輸人到計(jì)算機(jī)中并且能夠被計(jì)算機(jī)處理的符號(hào)的總稱。（數(shù)據(jù)、數(shù)據(jù)）2、數(shù)據(jù)元素是數(shù)據(jù)的_，有些情況下也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。（基本單位）3、_是數(shù)據(jù)不可分割的最小單元，是具有獨(dú)立含義的最小標(biāo)識(shí)單位。.精品文檔例如構(gòu)成一個(gè)數(shù)據(jù)元素的字段、域、屬性等都可稱之為_。（數(shù)據(jù)項(xiàng)、數(shù)據(jù)項(xiàng)）（4、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)之間的_。邏輯結(jié)構(gòu)是從_上描述數(shù)據(jù)，它與具體存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的_。（邏輯關(guān)系、邏

4、輯關(guān)系、數(shù)學(xué)模型）5、數(shù)據(jù)的_指數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示。_是邏輯結(jié)構(gòu)在計(jì)算機(jī)里的實(shí)現(xiàn)，也稱之為映像。存儲(chǔ)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)）6、數(shù)據(jù)邏輯結(jié)構(gòu)可以分為四種基本的類型，_結(jié)構(gòu)中的元素除了僅僅只是同屬于一個(gè)_，不存在什么關(guān)系。（集合、集合）7、數(shù)據(jù)邏輯結(jié)構(gòu)的四種基本類型中，_中的元素是一種一對(duì)一的關(guān)系，這種結(jié)構(gòu)的特征是：若結(jié)構(gòu)是非空集，則有且只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最多只能有一個(gè)直接前驅(qū)和一個(gè)直接后繼。（線性結(jié)構(gòu)）8、數(shù)據(jù)邏輯結(jié)構(gòu)的四種基本類型中，_中的元素是一種一對(duì)多的關(guān)系。（樹形結(jié)構(gòu)）9、圖型結(jié)構(gòu)或圖狀結(jié)構(gòu)是一種_的關(guān)系。在這種邏輯結(jié)構(gòu)中，所有結(jié)點(diǎn)均可以有多個(gè)前驅(qū)

5、和多個(gè)后繼。（多對(duì)多）10、有時(shí)也可將樹型結(jié)構(gòu)、集合和圖型結(jié)構(gòu)稱為_，這樣數(shù)據(jù)的邏輯結(jié)構(gòu)就可以分為_和_兩大類。（非線性結(jié)構(gòu)、線性結(jié)構(gòu)、非線性機(jī)構(gòu)）11、_方式是指邏輯上相鄰的結(jié)點(diǎn)被存儲(chǔ)到物理上也相鄰的存儲(chǔ)單元中。這種存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)結(jié)點(diǎn)的數(shù)值，不存儲(chǔ)結(jié)點(diǎn)之間的關(guān)系，結(jié)點(diǎn)之間的關(guān)系是通過存儲(chǔ)單元的相鄰關(guān)系隱含的表示出來的。（順序存儲(chǔ)）12、_方式是種存儲(chǔ)方法，不要求邏輯上相鄰的結(jié)點(diǎn)在物理上也相鄰，即數(shù)據(jù)元素可以存儲(chǔ)在任意的位置上。（鏈?zhǔn)酱鎯?chǔ)）13、_方式是利用結(jié)點(diǎn)關(guān)鍵字的值直接計(jì)算出該結(jié)點(diǎn)存儲(chǔ)單元地址，然后將結(jié)點(diǎn)按某種方式存人該地址的一種方法。（散列存儲(chǔ)或哈希存儲(chǔ)）14、所謂算法（algorit

6、hm）是對(duì)特定問題求解步驟的一種描述，它是指令的其中每個(gè)指令表示一個(gè)或多個(gè)操作。算法的五個(gè)重要特性是_、_、_、_和_。（有限序列、有窮性、確定性、可行性、輸入、輸出）15、算法的_性是指算法必須能夠在執(zhí)行有限個(gè)步驟之后結(jié)束，并且每個(gè)步驟都必須在有窮的時(shí)間內(nèi)完成。（有窮性）16、算法的_性是指算法中的每一個(gè)步驟必須是有明確定義的，不允許有模棱兩可的解釋，也不允許有多義性。并且，在任何條件下，算法只能有惟一的一條執(zhí)行路徑，即只要輸人是相同的就只能得到_的輸出結(jié)果。（確定性、相同）17、算法的_性又稱為算法的能行性，是指算法中描述的操作是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。（可行性）18、

7、判斷一個(gè)算法的好壞主要以下幾個(gè)標(biāo)準(zhǔn)：_、_、_、_。（正確性、可讀性、健壯性、時(shí)間效率和空間效率）19、算法分析是對(duì)一種算法所消耗的計(jì)算機(jī)資源的估算，其中包括計(jì)算機(jī)_的長短和_的大小。（運(yùn)行時(shí)間、所占據(jù)空間）20、空間復(fù)雜度（spacecomplexity）也是度量一個(gè)算法好壞的標(biāo)準(zhǔn)，它所描述的是算法在運(yùn)行過程中所占用_的大小。（存儲(chǔ)空間）.精品文檔三、判斷題1順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（）2數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）3算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。()4健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()5數(shù)據(jù)的邏輯結(jié)構(gòu)是指各元素之間的邏輯關(guān)系，是根據(jù)用戶

8、需要而建立的。6數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映像分別稱為存儲(chǔ)結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。（）7數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中實(shí)際的存儲(chǔ)形式。（）8具有存取任一元素的時(shí)間相等這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)稱為隨機(jī)存取結(jié)構(gòu)。9算法實(shí)際上就是程序，程序也一定是算法。()10.在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。()11.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。()12.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。()13.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)。()14.判斷一個(gè)算法的好壞主要以下幾個(gè)標(biāo)準(zhǔn)：正確性、有窮

9、性、健壯性和可行性。()15算法的時(shí)間復(fù)雜度t（n）=o(f(n)表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率與函數(shù)f(n)的增長率相同。（）四、綜合題1用大o形式表示下面算法的時(shí)間復(fù)雜度：for（i=0；im；i十十）for（j=0；jn；j）aij=i*j；2寫出下面算法的時(shí)間復(fù)雜度：i0；s=0；while(sn）i+;s+=i;3寫出以下算法的時(shí)間復(fù)雜度：for（i0;im;i）for（j0;jt;j）cij=0；for（i=0；im；i）for（j=o;jt;j+）for（k=0；kn；k）cijaik*bkj;4寫出下面算法的時(shí)間復(fù)雜度：i=1;while（in）i=i*3;5求下

10、面函數(shù)中各條語句的頻度和算法的時(shí)間復(fù)雜度：.精品文檔prime（intn）inti2；while(ni）！=0isqrt(n)i+;if（isqrt(n)printf（”disaprimenumber.n”，n）；elseprintf（”disnotaprimenumber.n”，n）；1.該算法的時(shí)間復(fù)雜度為：o(mn)。2.該算法的時(shí)間復(fù)雜度為：o(n)3.該算法的時(shí)間復(fù)雜度為：o(mnt)。4.該算法的時(shí)間復(fù)雜度為：log(n)。35.該算法的時(shí)間復(fù)雜度為：o(n)。6將下列函數(shù)，按它們?cè)趎時(shí)的無窮大階數(shù)，從小到大排序。n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2

11、+logn,(3/2)n,n!,n2+logn從小到大排列為：logn,n1/2+logn,n,nlogn,n2+logn，n3,n-n3+7n5,2n/2,(3/2)n,n!,.精品文檔第二章線性表一、選擇題1在一個(gè)長度為n的順序表中刪除第i個(gè)元素（0inext=p-next-nextbp-next=p-nextcp=p-next-nextdp=p-next;p-next=p-next-next14在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)，若在q和p之間插入s所指的結(jié)點(diǎn)，則執(zhí)行（）操作。.精品文檔as-next=p-next;p-next=s;bq-next=s;s-next=p;c

12、p-next=s-next;s-next=p;dp-next=s;s-next=q;15在單鏈表中附加頭結(jié)點(diǎn)的目的是為了（）。a保證單鏈表中至少有一個(gè)節(jié)點(diǎn)b標(biāo)識(shí)單鏈表中首結(jié)點(diǎn)的位置c方便運(yùn)算的實(shí)現(xiàn)d說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)16循環(huán)單鏈表的主要優(yōu)點(diǎn)是（）。a不再需要頭指針了b從表中任意一個(gè)結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表c已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的前驅(qū)d在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開17非空的循環(huán)單鏈表l的尾結(jié)點(diǎn)p滿足（）。ap-next=nullbp=nullcp-next=ldp=l18在雙向循環(huán)鏈表中,在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q所指向的新結(jié)點(diǎn),其修改指針

13、的操作是()。注:雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(prior,data,next)。供選擇的答案：ap-prior=q；q-next=p；p-prior-next=q；q-prior=q；bp-prior=q；p-prior-next=q;q-next=p；q-prior=p-prior；cq-next=p；q-prior=p-prior；p-prior-next=q;p-prior=q;dq-prior=p-prior；q-next=p；p-prior=q；p-prior=q；19在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（）。ap-prior-next=p-next;p-next-prior

14、=p-prior;bp-prior=p-prior-prior;p-prior-next=p;(刪p的前趨)cp-next-prior=p;p-next=p-next-next;dp-next=p-prior-prior;p-prior=p-next-next;二、填空題1線性表（linearlist）是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表中的元素（存在著_的相互關(guān)系。一對(duì)一）2線性表中有且僅有一個(gè)開始結(jié)點(diǎn)，表中有且僅有一個(gè)終端結(jié)點(diǎn)，除開始結(jié)點(diǎn)外，其他每個(gè)元素有且僅有一個(gè)_，除終端結(jié)點(diǎn)外，其他每個(gè)元素有且僅有一個(gè)_。3線性表是n（n=0）個(gè)數(shù)據(jù)元素的_。其中n為數(shù)據(jù)元素的個(gè)數(shù)，定義為線性表的_

15、。當(dāng)n為零時(shí)的表稱為_。4所謂順序表（sequentiallist）是線性表的_，它是將線性表中的結(jié)點(diǎn)按其_依次存放在內(nèi)存中一組連續(xù)的存儲(chǔ)單元中，使線性表中相鄰的結(jié)點(diǎn)存放在_的存儲(chǔ)單元中。5單鏈表不要求邏輯上相鄰的存儲(chǔ)單元在物理上也一定要相鄰。它是分配一些_的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素，這些存儲(chǔ)單元可以分散在內(nèi)存中的_的位置上，它們?cè)谖锢砩峡梢允且黄B續(xù)的存儲(chǔ)單元，也可以是_的。因此在表示線性表這種數(shù)據(jù)結(jié)構(gòu)時(shí)，必須在存儲(chǔ)線性表元素的同時(shí)，也存儲(chǔ)線性表的。.精品文檔6線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每一個(gè)結(jié)點(diǎn)（node）需要包括兩個(gè)部分：一部分用來存放元素的數(shù)據(jù)信息，稱為結(jié)點(diǎn)的_；另一部分用來存放元

16、素的指向直接后繼元素的指針(即直接后繼元素的地址信息)，稱為_或_。7線性鏈表的邏輯關(guān)系是通過每個(gè)結(jié)點(diǎn)指針域中的指針來表示的。其邏輯順序和物理存儲(chǔ)順序不再一致，而是一種_存儲(chǔ)結(jié)構(gòu)，又稱為_。8如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中的頭結(jié)點(diǎn)的地址值，這樣就構(gòu)成了_。9為了能夠快速地查找到線性表元素的直接前驅(qū)，可在每一個(gè)元素的結(jié)點(diǎn)中再增加一個(gè)指向其前驅(qū)的指針域，這樣就構(gòu)成了_。10雙向鏈表某結(jié)點(diǎn)的指針p，它所指向結(jié)點(diǎn)的后繼的前驅(qū)與前驅(qū)的后繼都是p_。11在單鏈表中，刪除指針p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是_。12在雙循環(huán)鏈表中，刪除指針p所指結(jié)點(diǎn)的語句序列是p-prior-nextp-next

17、及_。13單鏈表是_的鏈接存儲(chǔ)表示。14可以使用_表示樹形結(jié)構(gòu)。15向一個(gè)長度為n的向量的第i個(gè)元素(lin+1）之前插人一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。16刪除一個(gè)長度為n的向量的第i個(gè)元素（lin）時(shí)，需向前移動(dòng)_個(gè)元素。17在單鏈表中，在指針p所指結(jié)點(diǎn)的后面插人一個(gè)結(jié)點(diǎn)s的語句序列是_。18在雙循環(huán)鏈表中，在指針p所指結(jié)點(diǎn)前插人指針s所指的結(jié)點(diǎn)，需執(zhí)行語句_。19取出廣義表a（x，（a，b，c，d）中原子c的函數(shù)是_。20在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插人一個(gè)新結(jié)點(diǎn)并使之仍然有序的時(shí)間復(fù)雜度為_。21寫出帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表l為空表的條件_。22線性表、棧和隊(duì)列都是_結(jié)構(gòu)。23向棧中

18、插人元素的操作是先移動(dòng)棧_針，再存人元素。1.一對(duì)一2.直接前驅(qū)、直接后繼3.有限序列、長度、空表4.順序存儲(chǔ)結(jié)構(gòu)、邏輯順序、地址相鄰5.任意、任意、不連續(xù)、邏輯關(guān)系6.數(shù)據(jù)域、指針域、鏈域7.非順序、非順序映像8.循環(huán)鏈表9.雙向鏈表10.所指向的結(jié)點(diǎn)本身11.p-next=p-next-next12.p-next-prior=p-prior13.線性表.精品文檔14.雙鏈表15.n-i+116.n-i17.s-next=p-next;p-next=s18.p-prior-next=s;s-prior=p-prior;s-next=p;p-prior=s;19.head(tail(tail(

19、head(tail(head(a)20.o(n)21.(l=l-next)&(l=l-prior)22.線性23.頂三、判斷題1線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。()2在具有頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針指向鏈表中的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。()3順序存儲(chǔ)的線性表不可以隨機(jī)存取。()4單鏈表不是一種隨機(jī)存取結(jié)構(gòu)。（）5順序存儲(chǔ)結(jié)構(gòu)線性表的插入和刪除運(yùn)算所移動(dòng)元素的個(gè)數(shù)與該元素的位置無關(guān)。()6順序存儲(chǔ)結(jié)構(gòu)是動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是靜態(tài)存儲(chǔ)結(jié)構(gòu)。()7線性表的長度是線性表所占用的存儲(chǔ)空間的大小。()8雙循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。()9線性表的惟一存儲(chǔ)

20、形式是鏈表。()1.錯(cuò)誤：鏈表存儲(chǔ)中，結(jié)點(diǎn)之間可以連續(xù)也可以不連續(xù)，但結(jié)點(diǎn)內(nèi)部是連續(xù)的。2.錯(cuò)誤：頭指針指向頭結(jié)點(diǎn)而不是數(shù)據(jù)結(jié)點(diǎn)。3.錯(cuò)誤：順序存儲(chǔ)的線性表可以隨機(jī)存取。4.正確。5.錯(cuò)誤。6.錯(cuò)誤：順序存儲(chǔ)結(jié)構(gòu)是靜態(tài)存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。7.錯(cuò)誤：先行表的長度是線性表中結(jié)點(diǎn)的個(gè)數(shù)。8.錯(cuò)誤：注意最后一個(gè)結(jié)點(diǎn)。9.錯(cuò)誤：也可以有順序存儲(chǔ)的形式。.精品文檔第三章棧和隊(duì)列一、選擇題l一個(gè)棧的序列是：a，b，c，d，e，則棧的不可能輸出的序列是（）。aa，b，c，d，ebd，e，c，b，acd，c，e，a，bde，d，c，b，a2若一個(gè)棧的輸人序列是1，2，3，n，輸出序列的第一個(gè)元

21、素是n，則第k個(gè)輸出元素是（）。akbn-k-1cn-k+1d不確定3判定一個(gè)棧s（最多有n個(gè)元素）為空的條件是（）。as-top！0bs-top=0cs-top!=nds-top=n4判定一個(gè)棧s（最多有n個(gè)元素）為滿的條件是（）。as-top!=0bs-top=0cs-top!=nds-top=n5向一個(gè)棧頂指針為top的不帶頭結(jié)點(diǎn)的鏈棧中插人一個(gè)*s結(jié)點(diǎn)的時(shí)候，應(yīng)當(dāng)執(zhí)行語句（）。atop-next=s；bs-next=top；top=s；cs-nexttop-next；top-nexts；ds-nexttop；tops-next；6向一個(gè)帶頭結(jié)點(diǎn)、棧頂指針為top的鏈棧中插人一個(gè)*s結(jié)點(diǎn)

22、的時(shí)候，應(yīng)當(dāng)執(zhí)行語句（）。atop-next=s；bs-next=top；top=s；cs-next=top-next；top-next=s；ds-next=top；top=s-next；7判定一個(gè)隊(duì)列q（最多有n個(gè)元素）為空的條件是（）。aq-rear-q-front=nbq-rear-q-front+1=ncq-rear=q-frontdq-rear+1=q-front8判定一個(gè)隊(duì)列q（最多有n個(gè)元素）為滿的條件是（）。aq-rear-q-front=nbq-rear-q-front+1=ncq-rear=q-frontdq-rear+1=q-front9判定一個(gè)循環(huán)隊(duì)列q（最多有n個(gè)元素

23、）為空的條件是（）。aq-rear=q-frontbq-rear=q-frontlcq-front=(q-rear+1)ndq-front=(q-rear-1)n10判定一個(gè)循環(huán)隊(duì)列q（最多有n個(gè)元素）為滿的條件是（）。aq-rear=q-frontbq-rear=q-frontlcq-front=(q-rear+1)ndq-front=(q-rear-1)n11在一個(gè)鏈隊(duì)列中，假定front和rear分別為頭指針和尾指針，則插入一個(gè)結(jié)點(diǎn)*s的操作是（）。afrontfront-nextbs-next=rear；rear=screar-next=s；rear=sds-next=front；fr

24、onts12在一個(gè)鏈隊(duì)列中，假定front和rear分別為頭指針和尾指針，刪除一個(gè)結(jié)點(diǎn)的操作是（）。afront=front-nextbrear=rear-nextcrear-next=frontdfront-nextrear13棧與隊(duì)列都是（）。a鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)b鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)c限制存取點(diǎn)的線性結(jié)構(gòu)d限制存取點(diǎn)的非線性結(jié)構(gòu)14若進(jìn)棧序列為l，2，3，4，則（）不可能是一個(gè)出棧序列。a3，2，4，1bl，2，3，4c4，2，3，1d4，3，2，l.精品文檔15在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫人該緩沖區(qū)，而打印機(jī)則從該緩沖

25、區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。a堆棧b隊(duì)列c數(shù)組d線性表1.c2.c3.b4.d5.b6.c7.c8.a9.a10.c11.c12.a13.c14.c15.b二、填空回1棧（stack）是限定在_一端進(jìn)行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為_，而另一端稱為_。不含元素的棧稱為_。2在棧的運(yùn)算中，棧的插人操作稱為_或_，棧的刪除操作稱為_或_。3根據(jù)棧的定義，每一次進(jìn)棧的元素都在原_之上，并成為新的_；每一次出棧的元素總是當(dāng)前的_，因此最后進(jìn)棧的元素總是_，所以棧也稱為_線性表，簡稱為_表。4棧是一種操作受到限制的線性表，是一種特殊的線性表，因此棧也有_和

26、_兩種存儲(chǔ)結(jié)構(gòu)，分別稱為_和_5當(dāng)棧滿的時(shí)候，再進(jìn)行人棧操作就會(huì)產(chǎn)生_，這種情況的溢出稱為_；當(dāng)?？盏臅r(shí)候，如果再進(jìn)行出棧操作，也會(huì)_，這種情況下的溢出稱為_。6棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為_，是一種_。7人們?nèi)粘Ｓ?jì)算用到的表達(dá)式都被稱為_，這是由于這種算術(shù)表達(dá)式的運(yùn)算符被置于兩個(gè)操作數(shù)中間。8計(jì)算機(jī)中通常使用_，這是一種將運(yùn)算符置于兩個(gè)操作數(shù)后面的算術(shù)表達(dá)式。這種表達(dá)式是由波蘭科學(xué)家謝維奇提出的，因此又稱為_9隊(duì)列（queue）也是一種_，但它與棧不同，隊(duì)列中所有的插人均限定在表的一端進(jìn)行，而所有的刪除則限定在表的另一端進(jìn)行。允許插人的一端稱為_，允許刪除的一端稱為_。10隊(duì)列的特點(diǎn)是_，因此隊(duì)列

27、又被稱為_的線性表，或稱為_表。11隊(duì)列的_又稱為_，是用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的元素。12由于隊(duì)列中的元素經(jīng)常變化，對(duì)于隊(duì)列的刪除和插人分別在隊(duì)頭和隊(duì)尾進(jìn)行，因此需要設(shè)置兩個(gè)指針分別指向_和_，這兩個(gè)指針又稱為_和_。13循環(huán)順序隊(duì)列（circularsequencequeue）經(jīng)常簡稱為_，它是將存儲(chǔ)順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的一個(gè)環(huán)，即將隊(duì)首和隊(duì)尾元素連接起來形成一個(gè)環(huán)形表。首尾相連的狀態(tài)是通過數(shù)學(xué)上的_來實(shí)現(xiàn)的。14在算法或程序中，當(dāng)一個(gè)函數(shù)直接調(diào)用自己或通過一系列語句間接調(diào)用自己的時(shí)候，則稱這個(gè)函數(shù)為，也稱為_。函數(shù)直接調(diào)用自己，則稱為_；當(dāng)一個(gè)函數(shù)通過另一個(gè)

28、函數(shù)來調(diào)用自己則稱為_。15在循環(huán)隊(duì)列中規(guī)定：當(dāng)q-rear=q-front的時(shí)候循環(huán)隊(duì)列為_，.精品文檔當(dāng)（q-rear+1）maxsizefront的時(shí)候循環(huán)隊(duì)列為_。16用鏈表方式表示的隊(duì)列稱為_。17已知棧的輸人序列為1，2，3，n，輸出序列為a1，a2，an，符合a2=n的輸出序列共有_。18一個(gè)棧的輸人序列是12345，則棧的輸出序列為43512是_（填是否可能）。19一個(gè)棧的輸人序列是12345，則棧的輸出序列為12345是_（填是否可能）。20設(shè)sq1maxsize為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂元素的位置，則作入棧操作的條件是_。21設(shè)sq1maxsize為一個(gè)順序存儲(chǔ)

29、的棧，變量top指示棧頂元素的位置，如果把棧頂元素彈出并送到x中，則需執(zhí)行語句_。22棧的特性是_。23對(duì)棧進(jìn)行退棧時(shí)的操作是先取出元素，后移動(dòng)_。24設(shè)s1max為一個(gè)順序存儲(chǔ)的棧，變量top指示棧頂位置，棧為滿的條件是_。25設(shè)鏈棧的棧頂指針為top，則棧非空的條件是_。26已知循環(huán)隊(duì)列用數(shù)組data1.n存儲(chǔ)元素值，用f，r分別作為頭尾指針，則當(dāng)前元素個(gè)數(shù)為_。27在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_位置。（前一個(gè)或后一個(gè)）28隊(duì)列中允許進(jìn)行刪除的一端稱為_。29鏈隊(duì)列實(shí)際上是一個(gè)同時(shí)帶有頭指針和尾指針的單鏈表（1n），尾指針指向該單鏈表的第_個(gè)元素。30設(shè)雙向鏈表鏈列為lq，lq

30、的頭指針為lq.front，尾指針為lq.rear，則隊(duì)列為空的條件是_。31從循環(huán)隊(duì)列中刪除一個(gè)元素，其操作是先取出一個(gè)元素，后移動(dòng)_32隊(duì)列中允許進(jìn)行插入的一端稱為_。1.表尾、棧頂、棧底、空棧2.進(jìn)棧、入棧、退棧、出棧3.棧頂元素、棧頂元素、棧頂元素、最先出棧、后進(jìn)先出、lifo4.順序、鏈?zhǔn)?、順序棧、鏈?.溢出、上溢、溢出、下溢6.鏈棧、特殊的單鏈表7.中綴表達(dá)式8.后綴表達(dá)式、波蘭式9.特殊的線性表、隊(duì)尾、隊(duì)頭10.先進(jìn)先出、先進(jìn)先出、fifo11.順序存儲(chǔ)結(jié)構(gòu)、順序隊(duì)列12.隊(duì)頭元素、隊(duì)尾元素、隊(duì)頭指針、隊(duì)尾指針13.循環(huán)隊(duì)列、取模運(yùn)算14.遞歸函數(shù)、自調(diào)用函數(shù)、直接遞歸調(diào)用、間

31、接遞歸調(diào)用15.空、滿16.鏈隊(duì)列.精品文檔17.n-118.不可能的19.可能的20.top!=maxsize21.x=sqtop;top=top-122.先進(jìn)后出23.棧頂指針24.top=max25.top!=nil26.(n+r-f)modn27.前一個(gè)28.隊(duì)首29.n30.lq-front=lq-rear31.棧頂指針32.隊(duì)尾三、判斷題1棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。（）2不同的入棧和出棧組合可能得到相同輸出序列。（）3消除遞歸一定要用棧。（）4循環(huán)隊(duì)列是順序存儲(chǔ)結(jié)構(gòu)。（）5循環(huán)隊(duì)列不會(huì)產(chǎn)生溢出。（）6循環(huán)隊(duì)列滿的時(shí)候rear=front。（）7在對(duì)鏈隊(duì)列（帶頭結(jié)點(diǎn)）做出隊(duì)操

32、作時(shí)不會(huì)改變front指針的值。（）1.正確。2.錯(cuò)誤：不同的入棧和出棧組合得到不同輸出序列。3.錯(cuò)誤：某些情況如尾遞歸可以轉(zhuǎn)換為遞推的形式。4.正確。5.錯(cuò)誤：循環(huán)隊(duì)列不會(huì)產(chǎn)生假溢出。6.錯(cuò)誤。7.正確。四、綜合題1設(shè)有4個(gè)元素a、b、c和d進(jìn)棧，給出它們所有可能的出棧秩序?？赡艿某鰲Ｐ蛄校海ü?4個(gè)）abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba不可能的出棧序列：（共10個(gè)）adbcbdaccabdcadbcdabdabcdacbdbacdbcadcab.精品文檔習(xí)題四一、選擇項(xiàng)l空串與空格串（）。a相同b不相同c可能相同d

33、無法確定2設(shè)有兩個(gè)申s1與s2，求串s2在s1中首次出現(xiàn)位置的運(yùn)算稱作（）。a連接b求子串c模式匹配d判子串3串與普通的線性表相比較，它的特殊性體現(xiàn)在（）。a順序的存儲(chǔ)結(jié)構(gòu)b鏈接的存儲(chǔ)結(jié)構(gòu)c數(shù)據(jù)元素是一個(gè)字符d數(shù)據(jù)元素可以任意4設(shè)有串s=computer，則其子串的數(shù)目是（）。a36b37c8d91.b2.c3.c4.b二、境空題1串是由零個(gè)或多個(gè)字符組成的_。通常記作：s“c1，c2，cn”(n=0)，其中，s稱為_；串中的ci（1=i=n）可以是字母、數(shù)字字格或其他字符。用雙引號(hào)括起來的部分是_即串s的內(nèi)容。2串中字符的個(gè)數(shù)稱為串的_。3不含有任何字符的串稱為_，它的長度為_。4由一個(gè)或多

34、個(gè)空格構(gòu)成的串稱為_，它的長度為_。5串中任意多個(gè)連續(xù)字符組成的子序列稱為該串的_；包含_的串稱為主串。6字符在序列中的序號(hào)稱為該字符在串中的_。7兩個(gè)字符串相等是指兩個(gè)字符串的，也就是說這兩個(gè)字符串不僅_，而且對(duì)應(yīng)位置上的字符也。8兩個(gè)串的比較實(shí)際上是_的比較。兩個(gè)串從第一個(gè)位置上的字符開始進(jìn)行比較，當(dāng)?shù)谝淮纬霈F(xiàn)_大的串為大，若比較過程中出現(xiàn)一個(gè)字符串結(jié)束的情況，則另一個(gè)串為_。9串的_就是把串所包含的字符序列，依次存人連續(xù)的存儲(chǔ)單元中去。10有些計(jì)算機(jī)系統(tǒng)中為了充分利用存儲(chǔ)空間，允許一個(gè)存儲(chǔ)單元可以存放多個(gè)字符，串的這種存儲(chǔ)方式是一種_。11串的_是以存儲(chǔ)單元為存儲(chǔ)單位，一個(gè)存儲(chǔ)單元中只存

35、放_(tái)。在這種情況下，即使一個(gè)存儲(chǔ)單元能存放多個(gè)字符，這時(shí)候也只存放_(tái)。12串在非緊縮方式下，串長度的存儲(chǔ)是隱式的，_即串的長度。13一些計(jì)算機(jī)是以字節(jié)為存取單位，恰好一個(gè)字符占用一個(gè)字節(jié)，自然形成了每個(gè)存儲(chǔ)單元存放_(tái)的分配方式，這種方式就是一種_。這種方式一般不需要存放_(tái)的存儲(chǔ)單元，而需要以程序中各變量值所、的字符為結(jié)束符。.精品文檔14串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是將存儲(chǔ)區(qū)域分成一系列大小相同的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有兩個(gè)城：_域和_域。其中_域用于存放數(shù)據(jù)，_域用于存放下一個(gè)結(jié)點(diǎn)的指針。15子串定位strindex(s，t)，也稱為_，是返回串t在s主串中的位置。1.有限序列、串名、串值2.長度3.空串、零4

36、.空格串、空格的個(gè)數(shù)5.子串、子串6.位置7.值相等、長度相等、相等8.ascii碼、ascii碼、較大者9.順序存儲(chǔ)結(jié)構(gòu)10.緊縮式存儲(chǔ)方式11.非緊縮存儲(chǔ)方式、一個(gè)字符、一個(gè)字符12.串所占用的存儲(chǔ)單元的個(gè)數(shù)13.一個(gè)字符、單字節(jié)存儲(chǔ)方式、串長、不包含14.數(shù)據(jù)、指針、數(shù)據(jù)、指針15.模式匹配三、判斷回1子串是主串中字符構(gòu)成的有限序列。（）2kmp算法的最大特點(diǎn)是指示主串的指針不需要回溯。（3串中的元素只能是字符。（）4串中的元素只可能是字母。（）5串是一種特殊的線性表。（）6串中可以包含有空白字符。（）7串的長度不能為零。（）8兩個(gè)串相等必有串長度相同。（）9兩個(gè)串相等則各位置上字符必須

37、對(duì)應(yīng)相等。（）.精品文檔習(xí)題五一、選擇題l數(shù)組常用的兩種基本操作是（）。a建立與查找b刪除與查找c插人與索引d查找與修改2對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，常用的兩種方法是（）。a二元組和散列表b三元組表和十字鏈表c三角矩陣和對(duì)角矩陣d對(duì)角矩陣和十字鏈表3采用稀疏矩陣的三元組表形式進(jìn)行壓縮存儲(chǔ)，若要完對(duì)三元組表進(jìn)行成轉(zhuǎn)置，只要將行和列對(duì)換，這種說法（）。a正確b錯(cuò)誤c無法確定d以上均不對(duì)4一個(gè)廣義表的表頭總是一個(gè)廣義表，這種說法（）。a正確b錯(cuò)誤c無法確定d以上均不對(duì)5一個(gè)廣義表的表尾總是一個(gè)廣義表，這種說法（）。a正確b錯(cuò)誤c無法確定d以上均不對(duì)6廣義表(a)的表頭是（）。（a）bac（a）d（a）7

38、廣義表（a）的表尾是（）。（a）bac（a）d（a）8廣義表（a），a）的表頭是（）。（a）bac（a）d（a）9廣義表（a），a）的表尾是（）。（a（a()bac）d（a）10廣義表（a，b，c）的表頭是（）。aab（a）ca，bd（b，c）11廣義表（a，b，c）的表尾是（）。ab，cb（b，c）cab，cd（a，b，c）12廣義表a滿足head（）=tail（），則a為（）。（a）b（）c（），（）d（），（），（）1.d2.b3.b4.b5.a6.c7.a8.c9.c10.a11.b12.b二、填空題1數(shù)組（array）是n（n1）個(gè)_的有序組合，數(shù)組中的數(shù)據(jù)是按順序存儲(chǔ)在一塊_的存儲(chǔ)

39、單元中。2數(shù)組中的每一個(gè)數(shù)據(jù)通常稱為_，_用下標(biāo)區(qū)分，其中下標(biāo)的個(gè)數(shù)由數(shù)組的_決定。3由于計(jì)算機(jī)內(nèi)存中的存儲(chǔ)單元是一個(gè)一維的存儲(chǔ)結(jié)構(gòu)，因此對(duì)于多維數(shù)組要想按順序存儲(chǔ)到計(jì)算機(jī)存儲(chǔ)單元中就必須有一個(gè)排列順序問題。對(duì)于二維數(shù)組，有兩種排列形式：一種是_；另一種是_。4對(duì)于需要壓縮存儲(chǔ)的矩陣可以分為_和_。對(duì)那些具有.精品文檔相同值元素或零元素在矩陣中分布具有一定規(guī)律的矩陣，我們稱之為_；而對(duì)于那些零元素?cái)?shù)目遠(yuǎn)遠(yuǎn)多于非零元素?cái)?shù)目，并且非零元素的分布沒有規(guī)律的矩陣稱為_。5在一個(gè)n階方陣a中，若元素滿足性質(zhì)：aa（0=i，j=0）個(gè)元素的序列。記作：a（a1，a2，an），其中，a是廣義表的_，n是它的

40、_，當(dāng)n=0的時(shí)候稱為_。9在一個(gè)非空的廣義表中，其元素a可以是某一確定類型的單個(gè)元素，稱i為_，也可以又是一個(gè)廣義表，稱為_。10廣義表的定義是一種遞歸的定義，廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。當(dāng)廣義表非空的時(shí)候，稱第一個(gè)元素a為廣義表a的_，稱其余元素組成1的表（a2，a3，an）是a的_。11廣義表的深度一般定義為廣義表元素_，或者說是廣義表_。利用遞歸的定義，廣義表的深度就是所有子表中_。1.相同類型數(shù)據(jù)、地址連續(xù)2.數(shù)組元素、數(shù)組元素、維數(shù)3.以行序?yàn)橹?、以列序?yàn)橹?.特殊矩陣、稀疏矩陣、特殊矩陣、稀疏矩陣5.對(duì)稱矩陣6.三元組順序表、三元組7.矩陣轉(zhuǎn)置8.名稱、長度、空表9.原子、子表10.表頭、表尾11.最大的層數(shù)、括號(hào)的重?cái)?shù)、最大深度加