《數(shù)據(jù)結(jié)構(gòu)》（戴敏）期末復(fù)習(xí)題庫(kù)

1、第一章 緒論一、選擇題1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 以及它們之間的 和運(yùn)算等的學(xué)科。(易) A、數(shù)據(jù)元素 B、計(jì)算方法 C、邏輯存儲(chǔ)D、數(shù)據(jù)映象 A、結(jié)構(gòu) B、關(guān)系 C、運(yùn)算 D、算法2、數(shù)據(jù)結(jié)構(gòu)被形式地定義為(K,R),其中K是 的有限集，R是K上的 有限集。(易) A、算法 B、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯結(jié)構(gòu) A、操作 B、映象C、存儲(chǔ)D、關(guān)系3、在數(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、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4、算法分析的目的是 ，算法分析的兩個(gè)主要方面是 。(中) A、找出數(shù)據(jù)

2、結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出的關(guān)系 C、分析算法的效率以求改進(jìn)D、分析算法的易懂性和文檔性 A、空間復(fù)雜度和時(shí)間復(fù)雜度B、正確性和簡(jiǎn)單性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性5、計(jì)算機(jī)算法指的是 ，它必須具備輸入、輸出和 等5個(gè)特性。(易) A、計(jì)算方法B、排序方法 C、解決問題的有限運(yùn)算序列D、調(diào)度方法 A、可執(zhí)行性、可移植性和可擴(kuò)充性 B、可行性、確定性和有窮性C、確定性、有窮性和穩(wěn)定性D、易讀性、穩(wěn)定性和安全性答案：1、A，B 2、D，B 3、C 4、C，A 5、C，B二、名詞解釋：(易)1、數(shù)據(jù) 2、數(shù)據(jù)元素 3、數(shù)據(jù)對(duì)象 4、數(shù)據(jù)結(jié)構(gòu) 5、數(shù)據(jù)類型 6、算法答案：1、

3、數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中被計(jì)算機(jī)程序處理的符號(hào)的總稱。2、數(shù)據(jù)元素?cái)?shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常做為一個(gè)整體進(jìn)行考慮和處理。3、數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合。4、數(shù)據(jù)結(jié)構(gòu)：相互具有一種或多種關(guān)系的數(shù)據(jù)元素的集合。5、數(shù)據(jù)類型：是具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及在這個(gè)數(shù)據(jù)上的一組運(yùn)算，是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的概念。6、算法：對(duì)特定問題求解步驟的一種描述，是有限指令的集合。三、填空題1、下面程序段的時(shí)間復(fù)雜度是_。(易)for (i=0;i<n;i+)for (j=0;j<m;j+)aij=0;2、下面程序段的時(shí)間復(fù)雜度是_。(中)i=

4、s=0while(s<n) i+; /* i=i+1 */ s+=i;/* s=s+i */3、下面程序段的時(shí)間復(fù)雜度是_。(易)s=0;for (i=0;i<n;i+)for (j=0;j<n;j+)s+=bij;sum=s;4、下面程序段的時(shí)間復(fù)雜度是_。(難)i=1;wile (i<=n)i=i*3;5、數(shù)據(jù)元素可以由若干_組成，_是數(shù)據(jù)的基本單位，_是數(shù)據(jù)的最小單位。(易)6、數(shù)據(jù)結(jié)構(gòu)分為兩部分，即_結(jié)構(gòu)和_結(jié)構(gòu)。(易)7、數(shù)據(jù)的存儲(chǔ)方式分為_存儲(chǔ)和_存儲(chǔ)。(易)8、順序存儲(chǔ)是一種_的存儲(chǔ)方式，是用一組_的存儲(chǔ)空間存儲(chǔ)數(shù)據(jù)，而鏈?zhǔn)酱鎯?chǔ)是用一組_的存儲(chǔ)空間存儲(chǔ)數(shù)據(jù)

5、。(易)答案：1、O(m*n) 2、O() 3、O() 4、O(lon) 5、數(shù)據(jù)項(xiàng) 數(shù)據(jù)元素 數(shù)據(jù)項(xiàng) 6、邏輯 物理 7、順序 鏈?zhǔn)?8、隨機(jī)存取 連續(xù) 任意四、簡(jiǎn)答題：1、什么是算法，其基本性質(zhì)是什么？(易)2、算法的要求是什么？(中)3、結(jié)構(gòu)共分幾類？其各自的性質(zhì)是什么？(易)答案：1、算法是對(duì)特定問題求解步驟的一種描述，是有限指令的集合。其基本性質(zhì)如下：1)有窮性：算法對(duì)任意合法的輸入均能在有限時(shí)間、有限步驟后完成。2)確定性：算法的每一步驟的含義都是唯一、確定的，對(duì)于相同的輸入均能得到相同的輸出。3)可行性：算法的每一個(gè)步驟和指令都應(yīng)在已實(shí)現(xiàn)的算法的基礎(chǔ)上完成。4)輸入：任一個(gè)算法必

6、須有0個(gè)或多個(gè)輸入。5)輸出：任一個(gè)算法必須有1個(gè)或多個(gè)輸出。2、算法的要求是：1)正確性：算法能正確描述待求解問題的需求，沒有邏輯錯(cuò)誤，據(jù)此算法書寫的程序，對(duì)于任何合法的輸入，都有得到正確的、說明需求的結(jié)果。2)可讀性：算法應(yīng)簡(jiǎn)潔、明晰，易于閱讀和理解，便于算法的移植和交流，有利于增加算法的生命力。3)健壯性：當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法要能作出適當(dāng)?shù)奶幚恚粫?huì)產(chǎn)生難以預(yù)料的結(jié)果。4)高效率性：一般來說，對(duì)同一問題的多種算法，首先選擇執(zhí)行時(shí)間相對(duì)較短、存儲(chǔ)空間相對(duì)較少的算法，然后考慮易于實(shí)現(xiàn)的算法。3、結(jié)構(gòu)共分為四類，分別為：1)集合：所有元素除共在同一集合外，沒有其他關(guān)系。2)線性結(jié)構(gòu)：元素間

7、是一對(duì)一的關(guān)系。3)樹型結(jié)構(gòu)：元素間是一對(duì)多的關(guān)系。4)圖型結(jié)構(gòu)：元素間是多對(duì)多的關(guān)系。五、算法設(shè)計(jì)題：1、試寫一算法，求隨機(jī)輸入的三個(gè)整數(shù)的最大值。(中)2、隨機(jī)從鍵盤上輸入三個(gè)整數(shù)求其平均值輸出。(易)答案：1、int max(int x,int y,int z) int t;t=x>y?x:y;t=t>z?t:z;return t;2、main() int a,b,c; float sum=0,ave; scanf(“%d%d%d”,&a,&b,&c); sum=a+b+c; ave=sum/3;printf(“%.2fn”,ave);第二章 線性結(jié)構(gòu)

8、一、 判斷題1、線性表的邏輯順序與存儲(chǔ)順序總是一致的。(易)2、順序存儲(chǔ)的線性表可以按序號(hào)隨機(jī)存取。(易)3、順序表的插入和刪除一個(gè)數(shù)據(jù)元素，每次操作平均只有近一半的元素需要移動(dòng)。(易)4、線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對(duì)象。(易)5、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。(易)6、在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。(易)7、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。(易)8、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。(易)9、線性表的鏈?zhǔn)酱?/p>

9、儲(chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中數(shù)據(jù)元素的。(易)10、在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。(易)11、線性表中，每一個(gè)元素均存在前驅(qū)。(易)12、線性表中，每一個(gè)元素均存在后繼。(易)13、線性表中，存在唯一一個(gè)被稱為第一元素的元素。(易)14、線性表中，存在唯一一個(gè)被稱為最后一個(gè)元素的元素。(易)15、線性結(jié)構(gòu)是一種一對(duì)一的結(jié)構(gòu)。(易)答案：1-5 ×× 6-10 ×× 11-15 ××二、 選擇題：1、線性表是( ) 。(易)A、一個(gè)有限序列，可以為空； B、一個(gè)有限

10、序列，不能為空； C、一個(gè)無限序列，可以為空； D、一個(gè)無序序列，不能為空。 2、對(duì)順序存儲(chǔ)的線性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除操作都是等概率的。插入一個(gè)元素時(shí)平均要移動(dòng)表中的（ ）個(gè)元素。(易) A、n/2 B、(n+1)/2 C、(n 1)/2 D、n3、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址( ) 。(易)A、必須是連續(xù)的； B、部分地址必須是連續(xù)的； C、一定是不連續(xù)的； D、連續(xù)與否均可以。4、用鏈表表示線性表的優(yōu)點(diǎn)是 （ ）。(易)A、便于隨機(jī)存取B、花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少C、便于插入和刪除D、數(shù)據(jù)元素的物理順序與邏輯順序相同5、 某鏈表中最常用的操作是在最后一個(gè)元素之后插入一

11、個(gè)元素和刪除最后一個(gè)元素，則采用( )存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(易)A、單鏈表B、雙鏈表C、單循環(huán)鏈表D、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表6、 循環(huán)鏈表的主要優(yōu)點(diǎn)是( ) 。(易)A、不再需要頭指針了B、已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨C、在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開D、從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表7、 下面關(guān)于線性表的敘述錯(cuò)誤的是( )。(易) A、線性表采用順序存儲(chǔ)，必須占用一片地址連續(xù)的單元；B、線性表采用順序存儲(chǔ)，不便于進(jìn)行插入和刪除操作；C、線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片地址連續(xù)的單元；D、線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作；8、 單鏈表中，增

12、加一個(gè)頭結(jié)點(diǎn)的目的是為了（）。(易)A、使單鏈表至少有一個(gè)結(jié)點(diǎn) B、標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C、方便運(yùn)算的實(shí)現(xiàn) D、說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)9、 若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(易)A、單鏈表 B、僅有頭指針的單循環(huán)鏈表 C、雙鏈表 D、僅有尾指針的單循環(huán)鏈表10、 若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(易)A、單鏈表 B、順序表 C、雙鏈表 D、單循環(huán)鏈表11、 一個(gè)向量(一種順序表)第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素

13、的地址是_。(易)A、110 B、108 C、100 D、12012、 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_。(易)A、head = = NULL; B、head->next = = NULL;C、head->next = = head; D、head! = NULL;13、 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_。(易)A、head = = NULL; B、head->next = = NULL;C、head->next = = head; D、head! = NULL;14、 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行_。(

14、易)A、s->next=p; p->next=s; B、s->next=p->next; p->next=s;C、s->next=p->next; p=s; D、p->next=s; s->next=p; 15、 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行_。(易)A、s->next=p->next; p->next=s; B、p->next=s->next; s->next=p;C、q->next=s; s->next=p; D、p->nex

15、t=s; s->next=q;16、 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_個(gè)結(jié)點(diǎn)。(易)A、n; B、n/2; C、(n-1)/2; D、(n+1)/2;17、 給定有n個(gè)結(jié)點(diǎn)的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度_。(易)A、 O(1); B、 O(n); C、 O(n); D、 O(nlogn);18、順序存儲(chǔ)結(jié)構(gòu)是一種_ _的存儲(chǔ)結(jié)構(gòu)。(易)A、隨機(jī)存取 B、索引存取 C、順序存取 D、散列存取19、在以下的敘述中，正確的是_ _。(易)A、線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B、線性表的順序存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況C

16、、線性表的鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況D、線性表的鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)20、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足_。(易)A、 p->next= =NULL B、 p= =NULLC、 p->next= =head D、 p= =head 21、在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行_。(易)A、p->next= p->next->next； B、 p= p->next; p->next= p->next->next；C、p->next= p->next; D、p= p->

17、;next->next；答案：1-5 AADCD 6-10 DBCDB 11-15 BABBC 16-20 DCACC 21 A三、 填空題1 在一個(gè)長(zhǎng)度為n的向量中的第i個(gè)元素(1in)之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。(易)2、 在一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素(1in)時(shí)，需向前移動(dòng)_個(gè)元素。(易)3、在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)由指針s所指結(jié)點(diǎn)，可執(zhí)行以下操作：(易)s->next=_(1)_;p->next=s;t=p->data;p->data=_(2)_;s->data=_(3)_;4、在線性表L=(a1,a2,an)中，L稱

18、為線性表的_，n稱為線性表的_。(易)5、在線性表中有(ai,aj)，稱ai為aj的_，稱aj為ai的_。(易)6、在順序表中，若第一個(gè)元素所在的地址為L(zhǎng)oc(a1)，每個(gè)元素在內(nèi)存中占有L個(gè)存儲(chǔ)單元，則元素ai在內(nèi)存中的地址Loc(ai)=_。(易)7、順序表是一種_存取的存儲(chǔ)結(jié)構(gòu)，其元素的邏輯位置與物理位置一一對(duì)應(yīng)。(易)8、系統(tǒng)在內(nèi)存中為順序表提供一組_的存儲(chǔ)空間，為單鏈表提供一組_的存儲(chǔ)空間。(易)9、在單鏈表中，一個(gè)結(jié)點(diǎn)包含兩部分內(nèi)容，分別為_和_。(易)10、在單鏈表中，若指針p已指向最后一個(gè)結(jié)點(diǎn)，則p應(yīng)滿足的條件是_。(易)11、在單鏈表中，若結(jié)點(diǎn)p是結(jié)點(diǎn)q的前驅(qū)，應(yīng)滿足的條件是

19、_。(易)12、在單鏈表中，申請(qǐng)一個(gè)結(jié)點(diǎn)空間的命令是_，釋放一個(gè)空間的命令是_。(易)13、在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)為_，指向_ _；另一個(gè)為_，指向_ _ _。(易)14、在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s->next=_ _和p->next=_的操作。(易)15、在雙向鏈表中，若結(jié)點(diǎn)p是結(jié)點(diǎn)q的前驅(qū)，現(xiàn)要?jiǎng)h除結(jié)點(diǎn)q，需要完成的操作是_；_；(易)16、在雙向鏈表中，若在結(jié)點(diǎn)p之前插入一個(gè)新結(jié)點(diǎn)s，需要完成的操作有_；_；_；_；(易)答案：1、n-i+1 2、n-i 3、(1) p->next (2) s->data (3)

20、t4、名字 長(zhǎng)度 5、直接前驅(qū)元素 直接后繼元素6、Loc(ai)=Loc(a1)+(i-1)*L 7、隨機(jī) 8、連續(xù) 任意 9、指針域 數(shù)據(jù)域10、p.next=null 11、p.next=q 12、malloc() free() 13、前驅(qū)指針域 prior 后繼指針域 next 14、p.next s 15、p.next=q.next; q.next.prior=q.prior;16、s.prior=p.prior; s.next=p; p.prior.next=s; p.prior=s;四、算法設(shè)計(jì)題：1、在一順序表L的第i個(gè)元素前，插入一新元素x。(中)2、現(xiàn)有一順序表L，其值非遞

21、增有序排列，現(xiàn)插入一新元素x，要求插入后，L仍保持非遞增有序排列，試寫其算法。(中)3、在帶頭結(jié)點(diǎn)的單鏈表H中的p結(jié)點(diǎn)前插入一個(gè)新元素x。(中)4、已知單鏈表LA、LA中的元素按值非遞減有序排列，現(xiàn)將LA、LB歸并成一個(gè)新表LC，并要求LC中的元素亦非遞減有序排列。(中)五、編程題：1、百錢百雞問題。(中)2、獵人與狗的問題：一隊(duì)獵人一隊(duì)狗，兩隊(duì)并成一隊(duì)走，數(shù)頭一共三百六，數(shù)腳一共八百九，問多少獵人多少狗。(中)四、五題答案：四、算法題：1、int Insert_Sq(SqList L,int i,elemtp x) if(i<1 | i>L.len+1) return 0;if(

22、L.len=maxsize) return -1;for(j=L.len;j>=i;j-) L.elemj+1=L.elemj;L.elemi=x;L.len+;return 1; 2、int Insert(SqList L,elemtp x)if(L.len=maxsize) return -1; for(p=&L.elemL.len-1;*p<=x;p-) *(p+1)=*p; *(p+1)=x; return 1; 3、int Insert_L(LNode *H,LNode *p,elemtp x) s=(LNode *) malloc(sizeof(LNode);s

23、.data=x;q=H;while(q.next!=p) q=q.next;s.next=p;q.next=s;return 1;4、void Merge_L(LNode La,LNode Lb,LNode Lc) pa=La.next;pb=Lb.next;Lc=pc=La;while(pa && pb)if(pa.data<=pb.data) pc.next=pa;pc=pa;pa=pa.next; else pc.next=pb;pc=pb;pb=pb.next; pc.next=pa?pa:pb;free(Lb);五、編程題：1、main()int x,y,z;

24、for(x=1;x<20;x+) for(y=1;y<33;y+) z=100-x-y; if(100=5*x+3*y+z/3.0) printf(“%d,%d,%dn”,x,y,z); 2、main() int x,y;for(x=1;x<360;x+) y=360-x; if(2*x+4*y=890) printf(“%d,%d n”,x,y); 第三章棧和隊(duì)列一、判斷題：1、棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)(易)2、棧和隊(duì)列是兩種重要的線性結(jié)構(gòu)。(易)3、帶頭結(jié)點(diǎn)的單鏈表形式的隊(duì)列，頭指針F指向隊(duì)列的頭結(jié)點(diǎn)，尾指針R指向隊(duì)列的最后一個(gè)結(jié)點(diǎn)(易)4、在對(duì)不帶頭結(jié)點(diǎn)的鏈隊(duì)列

25、作出隊(duì)操作時(shí)，不會(huì)改變頭指針的值。(易)答案：1-4 ××二、選擇題：1、一個(gè)棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是_。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為_。 A、 i B、 n=i C、 n-i+1 D、 不確定3、棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是_。A、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B、散列方式和索引方式C、鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D、線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)4、 判定一個(gè)順序棧ST（最多元素為m0）為空的條件是_。A、t

26、op !=0 B、top= =0 C、top !=m0 D、top= =m0-15、 判定一個(gè)順序棧ST（最多元素為m0）為棧滿的條件是_。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-16、 隊(duì)列操作的原則是( ) A、 先進(jìn)先出 B、 后進(jìn)先出 C、 只能進(jìn)行插入 D、 只能進(jìn)行刪除7、 向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行_ _。(不帶空的頭結(jié)點(diǎn)) (易)A、HSnext=s;B、snext= HSnext; HSnext=s;C、snext= HS; HS=s;D、snext= HS; HS= HSnext;8、從一個(gè)棧頂指針為HS

27、的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行_ _。(不帶空的頭結(jié)點(diǎn)) (中)A、x=HS; HS= HSnext; B、x=HSdata;C、HS= HSnext; x=HSdata; D、x=HSdata; HS= HSnext;9、 一個(gè)隊(duì)列的數(shù)據(jù)入列序列是1，2，3，4，則隊(duì)列的出隊(duì)時(shí)輸出序列是_ 。(易) A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，110、判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m）為空的條件是_。(中)A、rear - front= =m B、rear-front-1= =mC、front= = rear D、front= = re

28、ar+111、 判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m, m= =Maxsize-1）為滿隊(duì)列的條件是_。(易)A、(rear- front)+ Maxsize)% Maxsize = =mB、rear-front-1= =m C、front= =rear D、front= = rear+112、 循環(huán)隊(duì)列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_。(中)A、 (rear-front+m)%m B、 rear-front+1C、 rear-front-1 D、 rear-front13、 棧和隊(duì)列的共同點(diǎn)是_。A、 都是先進(jìn)后出 B、 都是

29、先進(jìn)先出C、 只允許在端點(diǎn)處插入和刪除元素 D、 沒有共同點(diǎn)14、棧操作的原則是( ) (易)A、 先進(jìn)先出 B、 后進(jìn)先出 C、 只能進(jìn)行插入 D、 只能進(jìn)行刪除15、在順序棧中，判斷棧s為空的條件是( ) (中)A、t.base = NULL B、st.top = st.stacksizeC、st.top-st.base>= st.stacksize D、st.top = st.base16、在順序棧中，判斷棧s滿的條件是( ) (易)A、 st.base = NULL B、 st.top = st.stacksizeC、 st.top-st.base>= st.stacksi

30、ze D、 st.top = st.base答案：1-5 CCABD 6-10 ACBCC 11-15 AACBD 16 C三、填空題：1、棧和隊(duì)列都是_結(jié)構(gòu)，對(duì)于棧只能在_插入和刪除元素；對(duì)于隊(duì)列只能在_插入元素和_刪除元素。(易)2、向一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素（1in+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。(易)3、向一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1in）時(shí)，需向前移動(dòng)_個(gè)元素。(易)4、向棧中壓入元素的操作是_。(易)5、對(duì)棧進(jìn)行退棧時(shí)的操作是_。(易)6、在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_。(易)7、從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是_。(易)8、在具有

31、n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有_個(gè)元素。(易)9、一個(gè)棧的輸入序列是12345，則棧的輸出序列43512是_。(易)10、一個(gè)棧的輸入序列是12345，則棧的輸出序列12345是_。(易)11、隊(duì)列的基本性質(zhì)是_；棧的基本性質(zhì)是_。(易)12、在一個(gè)鏈棧中，若棧頂指針等于NULL則為_，在一個(gè)鏈隊(duì)中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為_或該隊(duì)列_。(易)13、向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)新結(jié)點(diǎn)*P，應(yīng)執(zhí)行 和 操作。(易)14、棧的順序存儲(chǔ)結(jié)構(gòu)即順序棧，是利用 來依次存放自棧底至棧頂?shù)臄?shù)據(jù)元素；當(dāng)棧為非空時(shí)，棧頂指針top始終指向 。15、從數(shù)據(jù)結(jié)構(gòu)的角度看，棧和隊(duì)列是

32、兩類線性表。(易)答案：1. 線性、棧頂、隊(duì)尾、隊(duì)首 2. n-i+1 3. n-i4.先移動(dòng)棧頂指針，后存入元素 5. 先取出元素，后移動(dòng)棧頂指針6.前一個(gè)位置 7. 先移動(dòng)隊(duì)首元素，后取出元素8. n-1 9. 不可能的 10. 可能的 11、FIFO LIFO12、棧空 空隊(duì) 只有一個(gè)元素 13、p->next=top top=p14、一組地址連續(xù)的存儲(chǔ)單元 棧頂元素的下一位置 15、受限的線性表四、算法題：1、輸入一個(gè)任意的非負(fù)十進(jìn)制整數(shù),輸出與其等值的八進(jìn)值數(shù)。(中)答案：void conversion() InitStack(s);scanf(“%d”,&N);whi

33、le(N)push(s,N%d); N=n/8;while(!empty(s) pop(s,e); printf(“%dn”,e);五、編程題：1、從鍵盤上輸入一個(gè)大寫字母，要求改用小寫字母輸出。（中）2、輸入一個(gè)圓的半徑，求其周長(zhǎng)及面積并輸出。答案：1、main()char c; scanf(“%c”,&c); c=c+32; printf(“%cn”,c); 2、#definet PI 3.14 main() float r,s,c;scanf(“%f”,&r);s=PI*r*r;c=2*PI*r;printf(“s=%.2f,c=%.2fn”,s,c);第四章 串和廣義表

34、一、判斷題：1、空串是由空白字符組成的串(易)2、串的定長(zhǎng)順序結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，按照預(yù)定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)。(易)3、串的堆分配存儲(chǔ)表示是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配得到的。(易)4、如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，那么則說明前者是后者的子串。(易)5、串是由有限個(gè)字符構(gòu)成的連續(xù)序列，串長(zhǎng)度為串中字符的個(gè)數(shù)，子串是主串中字符構(gòu)成的有限序列。(易)6、廣義表的表頭一定是列表。(易)7、廣義表的表尾一定是列表。(易)8、空串的長(zhǎng)度為零。(易)9、廣義表的元素即可以是原

35、子，也可以是子表。(易)10、廣義表中的子表與串中的子串的含義一樣。(易)11、廣義表A=()，為空表，其長(zhǎng)度為0。(易)12、由于廣義表的元素可以是列表，所以可以將廣義表轉(zhuǎn)化為一個(gè)樹型結(jié)構(gòu)答案：1-5 ××× 6-10 ×× 11-12 二、選擇題：1、以下敘述中正確的是 。(易)A、串是一種特殊的線性表B、串的長(zhǎng)度必須大于零C、串中無素只能是字母D、空串就是空白串2、空串與空格串是相同的，這種說法_。(易)A、 正確 B、 不正確3、串是一中特殊的線性表，其特殊性體現(xiàn)在_。(易)A、 可以順序存儲(chǔ) B、 數(shù)據(jù)元素是一個(gè)字符C、 可以鏈接存儲(chǔ)

36、 D、 數(shù)據(jù)元素可以是多個(gè)字符4、設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作_。(易)A、連接 B、模式匹配 C、求子串 D、求串長(zhǎng)5、設(shè)串s1=ABCDEFG，s2=PQRST，函數(shù)con (x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con (subs (s1,2,len (s2), subs (s1,len (s2),2)的結(jié)果串是_。(中)A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF6、設(shè)串的長(zhǎng)度為n，則它的子串個(gè)數(shù)為 。(易)A、nB、n(n+1)C、n(n+

37、1)/2 D、n(n+1)/2+17、下列那些為空串（ ）(易)A、S=“ ” B、S=“” C、S=“” D、S=“”8、S1=“ABCD”，S2=“CD”則S2在S3中的位置是（ ）(易)A、1 B、2 C、3 D、49、串是一種特殊的線性表，其特殊性體現(xiàn)在( )。(易)A、可以順序存儲(chǔ) B、 數(shù)據(jù)元素是一個(gè)字符C、可以鏈接存儲(chǔ) D、 數(shù)據(jù)元素可以是多個(gè)字符10、串是( )。(易)A、少于一個(gè)字母的序列 B、 任意個(gè)字母的序列C、不少于一個(gè)字符的序列 D、 有限個(gè)字符的序列11、 串的長(zhǎng)度是( )。(易)A、串中不同字母的個(gè)數(shù) B、 串中不同字符的個(gè)數(shù) C、串中所含的字符的個(gè)數(shù) D、 串中

38、所含字符的個(gè)數(shù)，且大于012、若某串的長(zhǎng)度小于一個(gè)常數(shù)，則采用( )存儲(chǔ)方式最為節(jié)省空間。(易)A、鏈?zhǔn)?B、 堆結(jié)構(gòu) C、 順序表答案：1-5 ABBBD 6-10 CBCBD 11-12 CC三、填空題：1、串的兩種最基本的存儲(chǔ)方式是_。(易)2、兩個(gè)串相等的充分必要條件是_。(易)3、空串是_，其長(zhǎng)度等于_。(易)4、空格串是_，其長(zhǎng)度等于_。(易)5、設(shè)s=IAMATEACHER,其長(zhǎng)度是_。(易)6、串s=abcdef,s1=cde，s1在s中的位置為_。(易)7、廣義表A=(a,(b,c d)；其表頭為_，表尾為_。(中)8、廣義表A=(a,A)；其表頭為_，表尾為_。(易)9、串

39、是每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成的（ ）。(易)答案：1順序存儲(chǔ)方式和鏈接存儲(chǔ)方式2兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置的字符相同3零個(gè)字符的串、零4由一個(gè)或多個(gè)空格字符組成的串、其包含的空格個(gè)數(shù)5146、3 7、a (b,c,d) 8、a (A) 9、線性表四、簡(jiǎn)答題：1、請(qǐng)寫出下列廣義表的表長(zhǎng)、表頭、表尾。(易)(1) A=( ) (2) B=(e) (3) C=(a,b,(c,d,e) (4) D=(a,D)答案：(1) 表長(zhǎng)為0，表頭為( )，表尾為（） (2) 表長(zhǎng)為1，表頭為e，表尾為（） (3) 表長(zhǎng)為3，表頭為a，表尾為（b,(c,d,e)） (4) 表長(zhǎng)為2，表頭為a，表尾為（D）五、編程題

40、：1編寫一個(gè)程序，要求有鍵盤輸入三個(gè)數(shù)，計(jì)算以這三個(gè)數(shù)為邊長(zhǎng)的三角形的面積(假定輸入的邊長(zhǎng)是有效的)。（中）2. 有一函數(shù)，其函數(shù)關(guān)系如下，試編程求對(duì)應(yīng)于每一自變量的函數(shù)值。（中） 1 (x<0) y = 0 (x=0) -1 (x>0)答案：1、#include “math.h” main() float a,b,c,p,s;scanf(“%f%f%f”,&a,&b,&c);p=(a+b+c)/2;s=sqrt(p*(p-a)*(p-b)*(p-c);printf(“%.2fn”,s);2、main() int x,y;scanf(“%d”,&x)

41、;if(x<0) y=1;if(x=0) y=0;if(x>0) y=-1;prinft(“%dn”,y);第五章數(shù)組一、名詞解釋：1、壓縮存儲(chǔ)(易)2、特殊矩陣(易)3、稀疏矩陣(易)答案：1、壓縮存儲(chǔ)：為多個(gè)值相同的元分配一個(gè)存儲(chǔ)空間，對(duì)零元不分配存儲(chǔ)空間。2、特殊矩陣：值相同的元素或者是零元素分布的有規(guī)律則稱為特殊矩陣。3、稀疏矩陣：在一個(gè)m*n的矩陣中，有t個(gè)非0元，其稀疏因子為t/(m*n)，如果稀疏因子小于0.05就稱為稀疏矩陣。二、選擇題：1、設(shè)數(shù)組a76的基地址為1024,每個(gè)元素占2個(gè)存儲(chǔ)單元,若以行序?yàn)橹餍蝽樞虼鎯?chǔ),則元素a24的存儲(chǔ)地址是_。(中)A、1058

42、 B、1056 C、1098 D、答案A,B,C都不對(duì)2、 二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A47的起始地址為_。(中)A、 SA+141 B、 SA+180 C、 SA+222 D、 SA+2253、二維數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是_。(中)A、 80 B、 100 C、240 D、 2704、 二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址S

43、A開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A74的起始地址為_。(中)A、 SA+141 B、 SA+144 C、 SA+222 D、 SA+225答案：1-4 BBCC三、填空題：1、 已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A00)，則Aij的地址是_。(中)2、 二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A00的存儲(chǔ)地址是200，則A612的地址是_。(中)3、 二維數(shù)組A1020510采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A105的存儲(chǔ)地址是1000，則A189的地址是_。(中)4、

44、現(xiàn)有一個(gè)n階的對(duì)稱矩陣ann，現(xiàn)將其壓縮存儲(chǔ)在一個(gè)一維數(shù)組sm中，則m=_，若以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)，則元素aij(i>=j)在s中的下標(biāo)k=_。(中)5、在一個(gè)m*n的矩陣中，若a00是第一個(gè)元素，則aij是第_個(gè)元素。(中)答案：1、LOC (A00)+(n*i+j)*k 2.、326 3、12084、n(n+1)/2 i(i-1)/2+j-1 5、i*n+j四、編程題：1、編寫一程序，求1+2+3+4+100的值（中）2、菱形的輸出(前5行) （中）答案：1、main()int i,sum=0; for(i=1;i<=100;i+) sum+=i; printf(“sum=%d

45、n”,sum); 2、main()int i,j; for(i=1;i<=3;i+) for(j=1;j<=3-i;j+) printf(“ “); for(j=1;j<=2*i-1;j+) printf(“*”); printf(“n”); for(i=1;i<=2;i+) for(j=1;j<=i;j+) printf(“ “); for(j=1;j<=5-2*i;j+) printf(“*”); printf(“n”); 第六章 樹一、選擇題：1、由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹是一種特殊的樹，這種說法_。(易)A、 正確 B、 錯(cuò)誤2、假

46、定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。 (易)A、15 B、16 C、17 D、473、按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹有_種。(易)A、3 B、 4 C、 5 D、 64、按照二叉樹的定義，具有3個(gè)不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹有_種。(易)A、5 B、 6 C、 30 D、 325、深度為5的二叉樹至多有_個(gè)結(jié)點(diǎn)。(易)A、16 B、32 C、31 D、106、設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為_ _。(易)A、 2h B、 2h-1 C、 2h+1 D、 h+17、 對(duì)一個(gè)滿二叉樹，m個(gè)樹

47、葉，n個(gè)結(jié)點(diǎn)，深度為h，則_ 。(易)A、 n=h+m B、 h+m=2n C、 m=h-1 D、 n=2 h-18、 任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序_。(易)A、不發(fā)生改變 B、發(fā)生改變 C、不能確定 D、以上都不對(duì)9、 如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序?yàn)開。(易) A、 uwvts B、 vwuts C、 wuvts D、 wutsv10、 二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說法_。(易) A、 正確 B、 錯(cuò)誤11、 某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的

48、結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是_。(易)A、 bdgcefha B、 gdbecfha C、 bdgaechf D、 gdbehfca12、 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊_。(易)A、 只有右子樹上的所有結(jié)點(diǎn) B、 只有右子樹上的部分結(jié)點(diǎn)C、 只有左子樹上的部分結(jié)點(diǎn) D、 只有左子樹上的所有結(jié)點(diǎn)13、 如圖6、1所示二叉樹的中序遍歷序列是_。(易)A、 abcdgef B、 dfebagc C、 dbaefcg D、 defbagcgcefdbaagedbchf圖6.2 圖6、1 14、 一棵二叉樹如圖6、2所示，其中序遍歷的序列為_ _(易)A、 abdgcefh B、 dgbaechf C、 gdbehfca D、 abcdefgh15、設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件是 。(易)A、a在b的右方B、a在b的左方 C、a是b的祖先D、a是b的子孫16、 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是_。 (易)A、 acbed B、 decab C、 deabc D、 cedba17、 實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞