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

1、第一章 緒論一、選擇題1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的 以及它們之間的 和運(yùn)算等的學(xué)科。(易) A、數(shù)據(jù)元素 B、計算方法 C、邏輯存儲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、存儲D、關(guān)系3、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成_。(易)A、動態(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、算法分析的目的是 ，算法分析的兩個主要方面是 。(中) A、找出數(shù)據(jù)

2、結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出的關(guān)系 C、分析算法的效率以求改進(jìn)D、分析算法的易懂性和文檔性 A、空間復(fù)雜度和時間復(fù)雜度B、正確性和簡單性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性5、計算機(jī)算法指的是 ，它必須具備輸入、輸出和 等5個特性。(易) A、計算方法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ù)對象 4、數(shù)據(jù)結(jié)構(gòu) 5、數(shù)據(jù)類型 6、算法答案：1、

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

4、s=0while(s<n) i+; /* i=i+1 */ s+=i;/* s=s+i */3、下面程序段的時間復(fù)雜度是_。(易)s=0;for (i=0;i<n;i+)for (j=0;j<n;j+)s+=bij;sum=s;4、下面程序段的時間復(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ù)的存儲方式分為_存儲和_存儲。(易)8、順序存儲是一種_的存儲方式，是用一組_的存儲空間存儲數(shù)據(jù)，而鏈?zhǔn)酱鎯κ怯靡唤M_的存儲空間存儲數(shù)據(jù)

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

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

7、是一對一的關(guān)系。3)樹型結(jié)構(gòu)：元素間是一對多的關(guān)系。4)圖型結(jié)構(gòu)：元素間是多對多的關(guān)系。五、算法設(shè)計題：1、試寫一算法，求隨機(jī)輸入的三個整數(shù)的最大值。(中)2、隨機(jī)從鍵盤上輸入三個整數(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、線性表的邏輯順序與存儲順序總是一致的。(易)2、順序存儲的線性表可以按序號隨機(jī)存取。(易)3、順序表的插入和刪除一個數(shù)據(jù)元素，每次操作平均只有近一半的元素需要移動。(易)4、線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對象。(易)5、在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。(易)6、在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。(易)7、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。(易)8、在線性表的順序存儲結(jié)構(gòu)中，插入和刪除時，移動元素的個數(shù)與該元素的位置有關(guān)。(易)9、線性表的鏈?zhǔn)酱?/p>

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

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

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

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

13、的地址是_。(易)A、110 B、108 C、100 D、12012、 不帶頭結(jié)點的單鏈表head為空的判定條件是_。(易)A、head = = NULL; B、head->next = = NULL;C、head->next = = head; D、head! = NULL;13、 帶頭結(jié)點的單鏈表head為空的判定條件是_。(易)A、head = = NULL; B、head->next = = NULL;C、head->next = = head; D、head! = NULL;14、 在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(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、 在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(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、 從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較_個結(jié)點。(易)A、n; B、n/2; C、(n-1)/2; D、(n+1)/2;17、 給定有n個結(jié)點的向量，建立一個有序單鏈表的時間復(fù)雜度_。(易)A、 O(1); B、 O(n); C、 O(n); D、 O(nlogn);18、順序存儲結(jié)構(gòu)是一種_ _的存儲結(jié)構(gòu)。(易)A、隨機(jī)存取 B、索引存取 C、順序存取 D、散列存取19、在以下的敘述中，正確的是_ _。(易)A、線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B、線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況C

16、、線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況D、線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)20、非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足_。(易)A、 p->next= =NULL B、 p= =NULLC、 p->next= =head D、 p= =head 21、在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(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 在一個長度為n的向量中的第i個元素(1in)之前插入一個元素時，需向后移動_個元素。(易)2、 在一個長度為n的向量中刪除第i個元素(1in)時，需向前移動_個元素。(易)3、在一個單鏈表中p所指結(jié)點之前插入一個由指針s所指結(jié)點，可執(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、在順序表中，若第一個元素所在的地址為Loc(a1)，每個元素在內(nèi)存中占有L個存儲單元，則元素ai在內(nèi)存中的地址Loc(ai)=_。(易)7、順序表是一種_存取的存儲結(jié)構(gòu)，其元素的邏輯位置與物理位置一一對應(yīng)。(易)8、系統(tǒng)在內(nèi)存中為順序表提供一組_的存儲空間，為單鏈表提供一組_的存儲空間。(易)9、在單鏈表中，一個結(jié)點包含兩部分內(nèi)容，分別為_和_。(易)10、在單鏈表中，若指針p已指向最后一個結(jié)點，則p應(yīng)滿足的條件是_。(易)11、在單鏈表中，若結(jié)點p是結(jié)點q的前驅(qū)，應(yīng)滿足的條件是

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

20、t4、名字 長度 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è)計題：1、在一順序表L的第i個元素前，插入一新元素x。(中)2、現(xiàn)有一順序表L，其值非遞

21、增有序排列，現(xiàn)插入一新元素x，要求插入后，L仍保持非遞增有序排列，試寫其算法。(中)3、在帶頭結(jié)點的單鏈表H中的p結(jié)點前插入一個新元素x。(中)4、已知單鏈表LA、LA中的元素按值非遞減有序排列，現(xiàn)將LA、LB歸并成一個新表LC，并要求LC中的元素亦非遞減有序排列。(中)五、編程題：1、百錢百雞問題。(中)2、獵人與狗的問題：一隊獵人一隊狗，兩隊并成一隊走，數(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); 第三章棧和隊列一、判斷題：1、棧和隊列都是限制存取點的線性結(jié)構(gòu)(易)2、棧和隊列是兩種重要的線性結(jié)構(gòu)。(易)3、帶頭結(jié)點的單鏈表形式的隊列，頭指針F指向隊列的頭結(jié)點，尾指針R指向隊列的最后一個結(jié)點(易)4、在對不帶頭結(jié)點的鏈隊列

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

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

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

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

29、先進(jìn)先出C、 只允許在端點處插入和刪除元素 D、 沒有共同點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、棧和隊列都是_結(jié)構(gòu)，對于棧只能在_插入和刪除元素；對于隊列只能在_插入元素和_刪除元素。(易)2、向一個長度為n的順序表的第i個元素（1in+1）之前插入一個元素時，需向后移動_個元素。(易)3、向一個長度為n的順序表中刪除第i個元素（1in）時，需向前移動_個元素。(易)4、向棧中壓入元素的操作是_。(易)5、對棧進(jìn)行退棧時的操作是_。(易)6、在一個循環(huán)隊列中，隊首指針指向隊首元素的_。(易)7、從循環(huán)隊列中刪除一個元素時，其操作是_。(易)8、在具有

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

32、兩類線性表。(易)答案：1. 線性、棧頂、隊尾、隊首 2. n-i+1 3. n-i4.先移動棧頂指針，后存入元素 5. 先取出元素，后移動棧頂指針6.前一個位置 7. 先移動隊首元素，后取出元素8. n-1 9. 不可能的 10. 可能的 11、FIFO LIFO12、?？?空隊 只有一個元素 13、p->next=top top=p14、一組地址連續(xù)的存儲單元 棧頂元素的下一位置 15、受限的線性表四、算法題：1、輸入一個任意的非負(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、從鍵盤上輸入一個大寫字母，要求改用小寫字母輸出。（中）2、輸入一個圓的半徑，求其周長及面積并輸出。答案：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、串的定長順序結(jié)構(gòu)是用一組地址連續(xù)的存儲單元存儲串值的字符序列，按照預(yù)定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)。(易)3、串的堆分配存儲表示是用一組地址連續(xù)的存儲單元存儲串值的字符序列，但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配得到的。(易)4、如果一個串中的所有字符均在另一串中出現(xiàn)，那么則說明前者是后者的子串。(易)5、串是由有限個字符構(gòu)成的連續(xù)序列，串長度為串中字符的個數(shù)，子串是主串中字符構(gòu)成的有限序列。(易)6、廣義表的表頭一定是列表。(易)7、廣義表的表尾一定是列表。(易)8、空串的長度為零。(易)9、廣義表的元素即可以是原

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

36、 D、 數(shù)據(jù)元素可以是多個字符4、設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作_。(易)A、連接 B、模式匹配 C、求子串 D、求串長5、設(shè)串s1=ABCDEFG，s2=PQRST，函數(shù)con (x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con (subs (s1,2,len (s2), subs (s1,len (s2),2)的結(jié)果串是_。(中)A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF6、設(shè)串的長度為n，則它的子串個數(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、可以順序存儲 B、 數(shù)據(jù)元素是一個字符C、可以鏈接存儲 D、 數(shù)據(jù)元素可以是多個字符10、串是( )。(易)A、少于一個字母的序列 B、 任意個字母的序列C、不少于一個字符的序列 D、 有限個字符的序列11、 串的長度是( )。(易)A、串中不同字母的個數(shù) B、 串中不同字符的個數(shù) C、串中所含的字符的個數(shù) D、 串中

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

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

40、：1編寫一個程序，要求有鍵盤輸入三個數(shù)，計算以這三個數(shù)為邊長的三角形的面積(假定輸入的邊長是有效的)。（中）2. 有一函數(shù)，其函數(shù)關(guān)系如下，試編程求對應(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、壓縮存儲(易)2、特殊矩陣(易)3、稀疏矩陣(易)答案：1、壓縮存儲：為多個值相同的元分配一個存儲空間，對零元不分配存儲空間。2、特殊矩陣：值相同的元素或者是零元素分布的有規(guī)律則稱為特殊矩陣。3、稀疏矩陣：在一個m*n的矩陣中，有t個非0元，其稀疏因子為t/(m*n)，如果稀疏因子小于0.05就稱為稀疏矩陣。二、選擇題：1、設(shè)數(shù)組a76的基地址為1024,每個元素占2個存儲單元,若以行序為主序順序存儲,則元素a24的存儲地址是_。(中)A、1058

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

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

44、現(xiàn)有一個n階的對稱矩陣ann，現(xiàn)將其壓縮存儲在一個一維數(shù)組sm中，則m=_，若以行序為主序進(jìn)行存儲，則元素aij(i>=j)在s中的下標(biāo)k=_。(中)5、在一個m*n的矩陣中，若a00是第一個元素，則aij是第_個元素。(中)答案：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、由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹，這種說法_。(易)A、 正確 B、 錯誤2、假

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

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

48、結(jié)點訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是_。(易)A、 bdgcefha B、 gdbecfha C、 bdgaechf D、 gdbehfca12、 在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊_。(易)A、 只有右子樹上的所有結(jié)點 B、 只有右子樹上的部分結(jié)點C、 只有左子樹上的部分結(jié)點 D、 只有左子樹上的所有結(jié)點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為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，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、 實現(xiàn)任意二叉樹的后序遍歷的非遞