數(shù)據(jù)結(jié)構(gòu)試題集(包含答案_完整版)

1、A.圖B.樹C.廣義表4、計(jì)算機(jī)中的算法指的是解決某一個(gè)問題的有限運(yùn)算序列,(B )等5個(gè)特性。A.可執(zhí)行性、可移植性和可擴(kuò)充性B.可執(zhí)行性、有窮性和確定性第一一、選擇題1、研究數(shù)據(jù)結(jié)構(gòu)就是研究(D )。A.數(shù)據(jù)的邏輯結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)操作2、算法分析的兩個(gè)主要方面是(A )A.空間復(fù)雜度和時(shí)間復(fù)雜度檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是(D )章概論B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)D.數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其基本B.正確性和簡(jiǎn)單性C.可讀性和文D. 棧它必須具備輸入、輸出、C.確定性、有窮性和穩(wěn)定性D. 易讀性、穩(wěn)定性和確定性5、下面程序段的時(shí)間復(fù)雜度是(C )。f

2、or(i=0;im;i+)for(j=0;jn;j+)aij=i*j；A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)6、算法是(D )。A.計(jì)算機(jī)程序B.解決問題的計(jì)算方法C.排序算法D.解決問題的有限運(yùn)算序列7、某算法的語句執(zhí)行頻度為(3n+nlog2n+n2+8),其時(shí)間復(fù)雜度表示(C )。A. O(n)B. O(nlog2n)C. O(n 2)D. O(log 2n)8、下面程序段的時(shí)間復(fù)雜度為(C )。i=1;while(i=n)i=i*3;A. O(n)B. O(3n)C. O(log 3n)D. O(n 3)9、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算

3、機(jī)的數(shù)據(jù)元素以及它們之問的(B )和運(yùn)算等的學(xué)科。A.結(jié)構(gòu)B.關(guān)系C.運(yùn)算D.算法10、下面程序段的時(shí)間復(fù)雜度是(A )c i=s=0;while(s=(y+1)*(y+1)y=y+i;A. O(n)B. O(. n)C. O(1) D. O(n2)二、填空題1、程序段“ i=1;while(inext=headB. p-next=NULLC. p=NULLD. p=head6、鏈表不具有的特點(diǎn)是()。A.可隨機(jī)訪問任一元素B.插入刪除不需要移動(dòng)元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性表長(zhǎng)度成正比7、在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)指針q所指向的新結(jié)點(diǎn)，修改 指針的操作是(

4、)。A. p-next=q;q-prior=p;p-next-prior=q;q-next=q;B. p-next=q;p-next-prior=q;q-prior=p;q-next=p-next;C. q-prior=p;q-next=p-next;p-next-prior=q;p-next=q;D. q-next=p-next;q-prior=p;p-next=q;p-next=q;8、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）0A.必須是連續(xù)的B.必須是不連續(xù)的C.連續(xù)與否均可D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)9、在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，需要向前移動(dòng)（）個(gè)元素。A. n-iB.

5、n-i+1C. n-i-1D. i+110、線性表是n個(gè)（）的有限序列。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)11、從表中任一結(jié)點(diǎn)出發(fā)，都能掃描整個(gè)表的是（）。A.單鏈表B.順序表C.循環(huán)鏈表D. 靜態(tài)鏈表12、在具有n個(gè)結(jié)點(diǎn)的單鏈表上查找值為x的元素時(shí)，其時(shí)間復(fù)雜度為（）。A. O（n）B. O（1）C. O（n2）D. O（n-1）13、線性表L=（a1,a2,an）,下列說法正確的是（）。A.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B.線性表中至少要有一個(gè)元素C.表中諸元素的排列順序必須是由小到大或由大到小D.除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都由一個(gè)且僅有一個(gè)直接前驅(qū)和 直接后繼1

6、4、一個(gè)順序表的第一個(gè)元素的存儲(chǔ)地址是 90,每個(gè)元素的長(zhǎng)度為2,則第6個(gè)元素 的存儲(chǔ)地址是（）。A. 98B. 100C. 102 D. 10615、在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)的時(shí)間最少的是（）。A. 單鏈表B.雙鏈表 C.循環(huán)鏈表 D.順序表16、在一個(gè)單鏈表中，若刪除p所指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（）0A. p-next=p-next-next;B. p=p-next;p-next=p-next-next;C. p =p-next;D. p=p-next-next;17、將長(zhǎng)度為n的單鏈表連接在長(zhǎng)度為m勺單鏈表之后的算法的時(shí)間復(fù)雜度為（）0A. O（1）B. O（n）C. O

7、（m） D. O（m+n）18、線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B.順序存取 C.索引存取 D.散列存取19、順序表中，插入一個(gè)元素所需移動(dòng)的元素平均數(shù)是（）。A. （n-1）/2 B. nC. n+1D. （n+1）/210、循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。A.不再需要頭指針B.已知某結(jié)點(diǎn)位置后能容易找到其直接前驅(qū)C.在進(jìn)行插入、刪除運(yùn)算時(shí)能保證鏈表不斷開D.在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表11、不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（A ）。A. head=NULLB. head-next=NULLC. head-next=headD. head!=NULL答案B是帶頭

8、結(jié)點(diǎn)的12、在下列對(duì)順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為O（1）的是（）。A.訪問第i個(gè)元素的前驅(qū)(1iEn)(1 i next=s-next ； s-next=p ；B. s-next=p ； q-next=s-next ；C. p-next=s-next ； s-next=q ；D. s-next=q ； p-next=s-next ；14、在以下的敘述中，正確的是()。A.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B.線性表的順序存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況C.線性表的鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況D.線性表的鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)15、在表長(zhǎng)為n的順序表中

9、，當(dāng)在任何位置刪除一個(gè)元素的概率相同時(shí)，刪除一個(gè)元 素所需移動(dòng)的平均個(gè)數(shù)為()。A. (n-1)/2B. n/2C. (n+1)/2D. n16、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插 入一個(gè)結(jié)點(diǎn)s,則執(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-next=s;s-next=q;17、在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)刪除x的后繼的語句是()0A. p=p-next;B.p-next=p-next-next;C. p-next=p;D

10、.p=p-next-next;18、在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針 p指向表中某個(gè)結(jié)點(diǎn)，若 p-next-next=head，貝U ()。A. p指向頭結(jié)點(diǎn) B. p指向尾結(jié)點(diǎn)C. p的直接后繼是頭結(jié)點(diǎn)D. p的直接后繼是尾結(jié)點(diǎn)二、填空題1、設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next )。已知指針p指向單鏈表中的結(jié)點(diǎn)，q指向新 結(jié)點(diǎn)，欲將q插入到p結(jié)點(diǎn)之后，則需要執(zhí)行的語 句：; 。答案：q-next=p-next p-next=q2、線性表的邏輯結(jié)構(gòu)是,其所含元素的個(gè)數(shù)稱為線性表的 。答案：線性結(jié)構(gòu)長(zhǎng)度3、寫出帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表 L為空表的條件。答案：L-prior=L

11、-next=L4、帶頭結(jié)點(diǎn)的單鏈表head為空的條件是。答案：head-next=NULL5、在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q = p-next;p-next= _q-next ;三、判斷題1、單鏈表不是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。2、在具有頭結(jié)點(diǎn)的單鏈表中，頭指針指向鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。3、用循環(huán)單鏈表表示的鏈隊(duì)列中，可以不設(shè)隊(duì)頭指針，僅在隊(duì)尾設(shè)置隊(duì)尾指針。4、順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。5、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素但是在物理位置上不一定是相鄰的。6、鏈?zhǔn)酱鎯?chǔ)的線性表可以隨機(jī)存取。X四、程序分析填空題1、函數(shù)GetElem實(shí)現(xiàn)返回單鏈表的第i個(gè)

12、元素，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int GetElem(LinkList L,int i,Elemtype *e)LinkList p ; int j ；p=L-next;j=1;while(p&ji) return ERROR;*e=(2)_；return OK;答案：(1)p=p-next (2)p-data2、函數(shù)實(shí)現(xiàn)單鏈表的插入算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int ListInsert(LinkList L,int i,ElemType e)LNode *p,*s;int j;p=L;j=0;while(p!=NULL)&(jnext;j+;if(p=NULL|ji-1) retur

13、n ERROR;s=(LNode *)malloc(sizeof(LNode);s-data=e;；return OK; /s=q-data;free(q);return OK;/*listDelete*/答案：(1)p-next!=NULL (2)p-next=q-next5、寫出算法的功能。int L(head) node * head;int n=0;node *p;p=head; while(p!=NULL) p=p-next;n+; return(n);ListInsert*/ 答案：(1)s-next=p-next (2)p-next=s3、函數(shù)ListDelete_sq實(shí)現(xiàn)順序表

14、刪除算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整 int ListDelete_sq(Sqlist *L,int i)int k;if(iL-length) return ERROR;for(k=i-1;klength-1;k+)L-slistk= (1);(2)1return OK;答案：(1) L-slistk+1(2) -L-Length4、函數(shù)實(shí)現(xiàn)單鏈表的刪除算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int ListDelete(LinkList L,int i,ElemType *s)LNode *p,*q;int j;p=L;j=0;while( (1)&(jnext;j+;if(p-next=NULL|

15、ji-1) return ERROR;q=p-next;(2);答案：求單鏈表head的長(zhǎng)度五、綜合題1、編寫算法，實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表的逆置算法。答案：void invent(Lnode *head)Lnode *p,*q;if(!head-next) return ERROR;p=head-next; q=p-next; p-next =NULL;while(q)p=q; q=q-next; p-next=head-next; head-next=p;2、有兩個(gè)循環(huán)鏈表，鏈頭指針分別為L(zhǎng)1和L2,要求寫出算法將L2鏈表鏈到L1鏈表 之后，且連接后仍保持循環(huán)鏈表形式。答案：void merge

16、(Lnode *L1, Lnode *L2)Lnode *p,*q ;while(p-next!=L1)p=p-next;while(q-next!=L2)q=q-next;q-next=L1; p-next =L2;3、設(shè)一個(gè)帶頭結(jié)點(diǎn)的單向鏈表的頭指針為head,設(shè)計(jì)算法，將鏈表的記錄，按照data域的值遞增排序。答案：void assending(Lnode *head)Lnode *p,*q , *r, *s;p=head-next; q=p-next; p-next=NULL;while(q)r=q; q=q-next;if(r-datadata)r-next=p; head-next

17、=r; p=r; elsewhile(!p & r-datap-data)s=p; p=p-next; r-next=p; s-next=r;p=head-next; 4、編寫算法，將一個(gè)頭指針為head不帶頭結(jié)點(diǎn)的單鏈表改造為一個(gè)單向循環(huán)鏈表， 并分析算法的時(shí)間復(fù)雜度。答案：void linklist_c(Lnode *head)Lnode *p; p=head;if(!p) return ERROR;while(p-next!=NULL)p=p-next;p-next=head;設(shè)單鏈表的長(zhǎng)度(數(shù)據(jù)結(jié)點(diǎn)數(shù))為N,則該算法的時(shí)間主要花費(fèi)在查找鏈表最后一個(gè)結(jié)點(diǎn)上(算法中的while循環(huán))，所以

18、該算法的時(shí)間復(fù)雜度為 O (N)。5、已知head為帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針，鏈表中的數(shù)據(jù)元素依次為( al, a2,a3,a4,an ) ,A為指向空的順序表的指針。閱讀以下程序段，并回答問題：(1)寫出執(zhí)行下列程序段后的順序表 A中的數(shù)據(jù)元素；(2)簡(jiǎn)要敘述該程序段的功能。if(head-next!=head)p=head-next;A-length=0;while(p-next!=head)p=p-next;A-dataA-length +=p-data;if(p-next!=head)p=p-next; 答案：(1) (a2,a4,，)(2) 將循環(huán)單鏈表中偶數(shù)結(jié)點(diǎn)位置的元素值寫入

19、順序表A6、設(shè)順序表va中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將 x插入到順序表的適當(dāng)位置 上，以保持該表的有序性。答案：void Insert_sq(Sqlist va口，ElemType x)int i, j, n;n=length(va);if(x=vai)van=x;elsei=0;while(xvai) i+;for(j=n-1;j=I;j-)vaj+1=vaj;vai=x; n+;7、假設(shè)線性表采用順序存儲(chǔ)結(jié)構(gòu)，表中元素值為整型。閱讀算法 f2 ,設(shè)順序表 L=(3,7,3,2,1,1,8,7,3), 寫出執(zhí)行算法f2后的線性表L的數(shù)據(jù)元素，并描述該算法的 功能。void f2(Seq

20、List *L)int i,j,k；k=0;for(i=0;ilength;i+)for(j=0;jdatai!=L-dataj;j+);if(j=k)if(k!=i)L-datak=L-datai;k+;L-length=k;答案：(3,7,2,1,8)刪除順序表中重復(fù)的元素8、已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一算法， 刪除表中所有大于x且小于y的元素(若表中存在這樣的元素)同時(shí)釋放被刪除結(jié)點(diǎn) 空間。答案：void Delete_list(Lnode *head, ElemType x, ElemType y)Lnode *p, *q;if(!head) ret

21、urn ERROR;p=head; q=p;while(!p)if(p-datax) & (p-datanext; free(p);p=head; q=p; elseq-next=p-next; free(p);p=q-next; elseq=p; p=p-next; 9、在帶頭結(jié)點(diǎn)的循環(huán)鏈表L中，結(jié)點(diǎn)的數(shù)據(jù)元素為整型，且按值遞增有序存放。給 定兩個(gè)整數(shù)a和b,且2rear=Q-frontB. Q-rear=Q-front+1C. Q-front=（Q-rear+1）%nD. Q-front=（Q-rear-1）%n3、設(shè)計(jì)一個(gè)判別表達(dá)式中括號(hào)是否配對(duì)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A.順序表

22、B. 鏈表C.隊(duì)列D.棧4、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。A. head=NULLB. head-next=NULLC. head-next!=NULLD. head!=NULL5、一個(gè)棧的輸入序列為：1,2,3,4 ,則棧的不可能輸出的序列是（）。A. 1243 B. 2134 C. 1432D. 4312 E.32146、若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)rear和front的值分別為0, 3。當(dāng) 從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（）。A. 1 和5B. 2 和4C. 4 和2D. 5 和17、隊(duì)列的插入操作是在（）。A.隊(duì)尾B

23、.隊(duì)頭C.隊(duì)列任意位置D.隊(duì)頭元素后 8、循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear ,則判斷循環(huán)隊(duì)列為空的條件是（）。A. front=rearB. front=0C. rear=0D. front=rear+19、一個(gè)順序棧S,其棧頂指針為top ,則將元素e入棧的操作是（）。A. *S-top=e;S-top+;B. S-top+;*S-top=e;C. *S-top=eD. S-top=e;10、表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）。A. abcd+-B. abc+*d- C. abc*+d- D. -+*abcd11、將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（）

24、來保存中間結(jié)果。A.隊(duì)列B.棧C.鏈表D.樹12、棧的插入和刪除操作在（）。A. 棧底B.棧頂C.任意位置D.指定位置13、五節(jié)車廂以編號(hào)1, 2, 3, 4, 5順序進(jìn)入鐵路調(diào)度站（棧），可以得到（）的編組。A. 3 ,4,5, 1, 2B. 2,4,1,3, 5C. 3 ,5,4, 2, 1D. 1 ,3,5,2, 414、判定一個(gè)順序棧S （?？臻g大小為n）為空的條件是（）。A. S-top=0B. S-top!=0C. S-top=nD. S-top!=n15、在一個(gè)鏈隊(duì)列中，front和rear分別為頭指針和尾指針，則插入一個(gè)結(jié)點(diǎn)s的操作 為（）。A. front=front-nex

25、tB. s-next=rear;rear=sC. rear-next=s;rear=s;D. s-next=front;front=s;16、一個(gè)隊(duì)列的入隊(duì)序列是1, 2, 3, 4,則隊(duì)列的出隊(duì)序列是（）。A.1 , 2, 3, 4B. 4 , 3, 2, 1C.1 , 4, 3, 2D. 3 , 4, 1, 217、依次在初始為空的隊(duì)列中插入元素 a,b,c,d以后，緊接著做了兩次刪除操作，止匕 時(shí)的隊(duì)頭元素是（）。A. aB. bC. cD. d18、正常情況下，刪除非空的順序存儲(chǔ)結(jié)構(gòu)的堆棧的棧頂元素，棧頂指針top的變化是（）。A. top 不變 B. top=0 C. top=top

26、+1D. top=top-119、判斷一個(gè)循環(huán)隊(duì)列Q （空間大小為M為空的條件是（A ）。A. Q-front=Q-rearB. Q-rear-Q-front-1=MC. Q-front+1=Q-rearD. Q-rear+1=Q-front20、設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（ C ）數(shù)據(jù)結(jié)構(gòu)最 佳。A.線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列 C.棧D.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 21、當(dāng)用大小為N勺數(shù)組存儲(chǔ)順序循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為（ C ）。A. NB. N+1C. N-1D. N-222、隊(duì)列的刪除操作是在（A ）。A.隊(duì)首B.隊(duì)尾C.隊(duì)前D.隊(duì)后23、若讓元素1, 2,

27、 3依次進(jìn)棧，則出棧次序不可能是（C ）。A. 3 , 2, 1B. 2,1,3 C. 3,1,2 D. 1 , 3, 224、循環(huán)隊(duì)列用數(shù)組A0 , m-1存放其元素值，已知其頭尾指針分別是front和rear , 則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（A ）。B. rear-front+1D. rear-frontA. (rear-front+m)%mC. rear-front-125、在解決計(jì)算機(jī)主機(jī)和打印機(jī)之間速度不匹配問題時(shí)，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū), 該緩沖區(qū)應(yīng)該是一個(gè)（B ）結(jié)構(gòu)。A.堆棧B.隊(duì)列26、棧和隊(duì)列都是（C ）。A.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C.限制

28、存取點(diǎn)的線性結(jié)構(gòu)而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印C.數(shù)組D.線性表B.鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)27、在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，刪除一個(gè)結(jié)點(diǎn) 的操作是（A ）。A. front=front-nextC. rear-next=front28、隊(duì)和棧的主要區(qū)別是（D ）A.邏輯結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)數(shù)不同B. rear= rear-nextD. front-next=rearB.存儲(chǔ)結(jié)構(gòu)不同D.限定插入和刪除的位置不同、填空題1、設(shè)棧竹口隊(duì)列Q勺初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S, 一個(gè)元素 出棧后即進(jìn)

29、入隊(duì)列Q,若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1 ,則棧的容量至少 應(yīng)該是 0答案：32、一個(gè)循環(huán)隊(duì)列Q勺存儲(chǔ)空間大小為M,其隊(duì)頭和隊(duì)尾指針分別為front和rear ,則循 環(huán)隊(duì)列中元素的個(gè)數(shù)為：。答案：(rear-front+M)%M3、在具有n個(gè)元素的循環(huán)隊(duì)列中，隊(duì)滿時(shí)具有 個(gè)元素。答案：n-14、設(shè)循環(huán)隊(duì)列的容量為70,現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)操作后，front為20, rear為 11,則隊(duì)列中元素的個(gè)數(shù)為。答案：615、已知循環(huán)隊(duì)列的存儲(chǔ)空間大小為20,且當(dāng)前隊(duì)列的頭指針和尾指針的值分別為 8和 3,且該隊(duì)列的當(dāng)前的長(zhǎng)度為 15。三、判斷題1、棧和隊(duì)列都是受限的線

30、性結(jié)構(gòu)。2、在單鏈表中，要訪問某個(gè)結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的地址即可；因此，單鏈表是一 種隨機(jī)存取結(jié)構(gòu)。3、以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，出棧操作必須判別棧空的情況。四、程序分析填空題1、已知棧的基本操作函數(shù)：int InitStack(SqStack *S); /構(gòu)造空棧int StackEmpty(SqStack *S);/判斷棧空int Push(SqStack *S,ElemType e);/入棧int Pop(SqStack *S,ElemType *e);/出棧函數(shù)conversion實(shí)現(xiàn)十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)，請(qǐng)將函數(shù)補(bǔ)充完整void conversion()InitStack(S);sc

31、anf( d ,&N);while(N)(1);N=N/8;while( (2)Pop(S,&e);printf(d ,e);/conversion答案：(1) Push(S,N%8)(2) !StackEmpty(S)2、寫出算法的功能。int function(SqQueue *Q,ElemType *e)if(Q-front=Q-rear)return ERROR;*e=Q-baseQ-front;Q-front=(Q-front+1)%MAXSIZE;return OK;若循環(huán)隊(duì)列非空，隊(duì)頭元素出隊(duì)列且返回其值，否則返回空元素。3、閱讀算法f2,并回答下列問題：(1)設(shè)隊(duì)列Q= (1,

32、 3, 5, 2, 4, 6)。寫出執(zhí)行算法f2后的隊(duì)列Q;(2)簡(jiǎn)述算法f2的功能。void f2(Queue *Q) DataType e;if (!QueueEmpty(Q) e=DeQueue(Q);f2(Q);EnQueue(Q,e);(2)將隊(duì)列倒置答案：(1) 6,4,2,5,3,1五、綜合題1、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，請(qǐng)寫出相應(yīng)的入隊(duì)列算法(用函數(shù)實(shí)現(xiàn))答案：void EnQueue(Lnode *rear, ElemType e) Lnode *new;New=(Lnode *)malloc(sizeof(Lnode);I

33、f(!new) return ERROR;new-data=e; new-next=rear-next;rear-next=new; rear =new;2、已知Q是一個(gè)非空隊(duì)列，S是一個(gè)空棧。編寫算法，僅用隊(duì)列和棧的ADT函數(shù)和少 量工作變量，將隊(duì)列Q的所有元素逆置。棧的ADT函數(shù)有：void makeEmpty(SqStack s); 置空棧void push(SqStack s,ElemType e); 元素e入棧ElemType pop(SqStack s);出棧，返回棧頂元素int isEmpty(SqStack s);判斷?？贞?duì)列的ADT函數(shù)有：void enQueue(Queue

34、 q,ElemType e); 元素e入隊(duì)ElemType deQueue(Queue q); 出隊(duì)，返回隊(duì)頭元素int isEmpty(Queue q); 判斷隊(duì)空 答案：void QueueInvent(Queue q) ElemType x;makeEmpty(SqStack s);while(!isEmpty(Queue q)x=deQueue(Queue q);push(SqStack s, ElemTypex); while(!isEmpty(SqStack s)x=pop(SqStack s);enQueue(Queue q, ElemType x);3、對(duì)于一個(gè)棧，給出輸入項(xiàng)

35、A,B,C,D,如果輸入項(xiàng)序列為A,B,C,D,試給出全部可能 的輸出序列。4,1,4,1,2,1,1答案：出棧的可能序列：ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA BDCACBDA CBAD CD3A DCBA第四章申 、選擇題1、設(shè)有兩個(gè)用S1和S2,求用S2ftS1中首次出現(xiàn)位置的運(yùn)算稱作(C )。A.連接B.求子用C.模式匹配D.判斷子用2、已知用S= aaab,則next數(shù)組值為(A )。A.0123B.1123C.1231D.12113、用與普通的線性表相比較，它的特殊性體現(xiàn)在( C )。A.順序的存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.數(shù)據(jù)元素

36、是一個(gè)字符D.數(shù)據(jù)元素任意4、設(shè)用長(zhǎng)為n,模式用長(zhǎng)為m,則KMPT法所需的附加空間為(A )。A. O(m) B. O(n)C. O(m*n) D. O(nlog 2m)5、空用和空格用(B )。A. 相同 B.不相同C.可能相同D. 無法確止6、與線性表相比，用的插入和刪除操作的特點(diǎn)是( B )。A.通常以用整體作為操彳對(duì)象B.需要更多的輔助空間C.算法的時(shí)間復(fù)雜度較高D.涉及移動(dòng)的元素更多7、設(shè)SUBSTR(S,i,k)是求S中從第i個(gè)字符開始的連續(xù)k個(gè)字符組成的子用的操作，則對(duì)于S= Beijing&Nanjing , SUBSTR(S,4,5)= ( B )。A. ijing B. j

37、ing& C. ingNaD.ing&N二、判斷題(X ) 1、造成簡(jiǎn)單模式匹配算法BF算法執(zhí)行效率低的原因是有回溯存在。(V ) 2、KM算法的最大特點(diǎn)是指示主審的指針不需要回溯(V ) 3、完全二叉樹某結(jié)點(diǎn)有右子樹，則必然有左子樹。模式匹西己三、填空題1、求子用在主審中首次出現(xiàn)的位置的運(yùn)算稱為一2、設(shè)$= IAMT ATEACHER,其長(zhǎng)度是 _14.3、兩個(gè)用相等的充分必要條件是兩個(gè)用的長(zhǎng)度相等且對(duì)應(yīng)位置字符相R 。 四、程序填空題 1、函數(shù)km成現(xiàn)用的模式匹配，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int kmp(sqstring *s,sqstring *t,int start,int next

38、兒 int i=start-1,j=0;while(ilen&jlen)if(j=-1|s-datai=t-dataj) i+；j+；else j= nextj ;if(j=t-len) return( i=t-len+1 );else return(-1);2、函數(shù)實(shí)現(xiàn)用的模式匹配算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int index_bf(sqstring*s,sqstring *t,int start)int i=start-1,j=0;while(ilen&jlen)if(s-datai=t-dataj) i+;j+;else i= i-j+1;j=0;if(j=t-len) return

39、 i-t-len+1 ;else return -1;/*listDelete*/3、寫出下面算法的功能。int function(SqString *s1,SqString *s2) int i;for(i=0;ilength&ilength;i+)if(s-datai!=s2-datai)return s1-datai-s2-datai;return s1-length-s2-length;答案：.用比較算法4、寫出算法的功能。int fun(sqstring *s,sqstring *t,int start) int i=start-1,j=0;while(ilen&jlen) if(s

40、-datai=t-dataj)i+;j+;elsei=i-j+1;j=0;if(j=t-len)return i-t-len+1;elsereturn -1; 答案：用的模式匹配算法 第五章數(shù)組和廣義表 一、選擇題1、設(shè)廣義表L=(a , b, c),則L的長(zhǎng)度和深度分別為(C )。A. 1 和1B. 1 和3C. 1 和2 D. 2 和32、廣義表(a),a)的表尾是(B )。A. aB. (a)C. ()D. (a)3、稀疏矩陣的常見壓縮存儲(chǔ)方法有(C )兩種。A.二維數(shù)組和三維數(shù)組B.三元組和散列表C.三元組和十字鏈表 D.散列表和十字鏈表 4、一個(gè)非空廣義表的表頭(D )。A.不可能是

41、子表B.只能是子表C.只能是原子 D.可以是子表或原子 5、數(shù)組A0.5,0.6 的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為 1000的內(nèi)存單元中，則元素 A55的地址是(A )。A.1175B.1180C.1205D.12106、廣義表 G=(a,b(c,d,(e,f),g)的長(zhǎng)度是(A )。A. 3B. 4C. 7 D. 87、采用稀疏矩陣的三元組表形式進(jìn)行壓縮存儲(chǔ)，若要完成對(duì)三元組表進(jìn)行轉(zhuǎn)置，只 要將行和列對(duì)換，這種說法(B )。A.正確B.錯(cuò)誤C.無法確定D.以上均不對(duì) 8、廣義表(a,b,c)的表尾是(B )。A. b,cB. (b,c)C. cD. (c)9、常對(duì)數(shù)組進(jìn)

42、行兩種基本操作是(C )0A.建立和刪除B.索引和修改C.查找和修改D.查找與索引 10、對(duì)一些特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了( D )。A.表達(dá)變得簡(jiǎn)單B.對(duì)矩陣元素的存取變得簡(jiǎn)單C.去掉矩陣中的多余元素D.減少不必要的存儲(chǔ)空間的開銷11、設(shè)有一個(gè)10階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè) 元素，其存儲(chǔ)地址為1,每元素占1個(gè)地址空間，則a85的地址為(B )。A. 13B. 33 C. 18D. 40 12、設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一維數(shù)組B1,n(n-1)/2中，對(duì)下三角部分中任一元素ai,j(i=j),在一維數(shù)組B的

43、下標(biāo)位置k的值是(B )A. i(i-1)/2+j-1B. i(i-1)/2+jC.i(i+1)/2+j-1D. i(i+1)/2+j13、廣義表A=(a),a)的表頭是(B )A. aB. (a)C. b D. (a)14、稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即( C )。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表 D.散列和十字鏈表4X5的稀疏矩陣15、假設(shè)以三元組表表示稀疏矩陣，則與如圖所示三元組表對(duì)應(yīng)的是(注：矩陣的行列下標(biāo)均從1開始)A.，0-8060C.00003700005040008060、7000000000150400，B.0-8067000-50400000

44、0、300,0-8060、70000-50403、0000012-814621725 133 1-5334B.至少有一個(gè)元素是子D.不能為空表16、以下有關(guān)廣義表的表述中，正確的是( A )A.由0個(gè)或多個(gè)原子或子表構(gòu)成的有限序列表C.不能遞歸定義17、對(duì)廣義表 L=(a,b),(c,d),(e,f)執(zhí)行 head(tail(head(tail(L)操作的結(jié)果是(D )。A.的B. eC. (e)D. (e,f )二、判斷題(x ) 1、廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度。(X) 2、一個(gè)稀疏矩陣采用三元組表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把miftnu的值進(jìn)行互換，則完成了矩陣轉(zhuǎn)

45、置。(V ) 3、稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。(X ) 4、廣義表的長(zhǎng)度是指廣義表中括號(hào)嵌套的層數(shù)。(V ) 5、廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)，其元素可以是單原子也可以是子表。三、填空題1、已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第 一個(gè)元素的存儲(chǔ)地址是LOC(A00),則Aij 的地址是 Loc(A00)+(i*N+j)*k 。2、廣義表運(yùn)算式 HEAD(TAIL(a,b,c),(x,y,z)的結(jié)果是：(x,y,z)。3、二維數(shù)組，可以按照 列序?yàn)橹骱托行驗(yàn)樨S 兩種不同的存儲(chǔ)方式。4、稀疏矩陣的壓縮存儲(chǔ)方式有：三元組 和 十字鏈表。四、綜合題1、現(xiàn)有

46、一個(gè)稀疏矩陣，請(qǐng)給出它的三元組表。0 31010000 2100-201答案：ijv12313121132233143-2第六章樹 一、選擇題 1、二叉樹的深度為k,則二叉樹最多有（C ）個(gè)結(jié)點(diǎn)。A. 2kB. 2 k-1 C. 2 k-1D. 2k-12、用順序存儲(chǔ)的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一 維數(shù)組R1.N中，若結(jié)點(diǎn)Ri有右孩子，則其右孩子是（B ）。A. R2i-1B. R2i+1C. R2iD. R2/i3、設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前面的條件是（B ）。A. a在b的右方B. a在b的左方C. a是b的祖先D. a是b的子孫

47、 4、設(shè)一棵二叉樹的中序遍歷序列：badce,后序遍歷序列：bdeca,則二叉樹先序遍歷序列為（D ）。A. adbceB. decab C. debacD. abcde5、在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（A ）。A. 31B. 32 C. 33D. 166、由二叉樹的前序和后序遍歷序列（ B ）惟一確定這棵二叉樹。A.能B.不能7、某二叉樹的中序序列為ABCDEFG后序序列為BDCAFGE則其左子樹中結(jié)點(diǎn)數(shù)目為 （C ）。A. 3B. 2C. 4 D. 58、若以4,5,6,7,8作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長(zhǎng)度為（ C ）。A. 67B. 68C. 69D. 709、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（A ）。A. 98B. 99C. 50 D. 4810、表達(dá)式a*（b+c）-d的后綴表達(dá)式是（B ）。A. abcd+-B. abc+*d- C. abc*+d- D. -+*abcd11、對(duì)某二叉樹進(jìn)行先序遍歷的結(jié)果為 ABDEFC中序遍歷的結(jié)果為DBFEAC則后序遍 歷的結(jié)果是（B ）。A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、樹最適合用來表示（C ）。A.有序數(shù)據(jù)