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

1、3、D )。C.廣義表4、(5、6、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是(A.圖B.樹(shù)計(jì)算機(jī)中的算法指的是解決某一個(gè)冋題的有限運(yùn)算序列，它必須具備輸入、輸出、 B )等5個(gè)特性。A.可執(zhí)行性、可移植性和可擴(kuò)充性C.確定性、有窮性和穩(wěn)定性 下面程序段的時(shí)間復(fù)雜度是for(i=0;i<m;i+) for(j=0;j <n ;j+) aij=i*j;A. O(m2)B. O(n2)算法是(D )oA.計(jì)算機(jī)程序C.排序算法D.棧C. 0(m* n)B.7、9、的B.D.可執(zhí)行性、有窮性和確定性 易讀性、穩(wěn)定性和確定性D. 0(m+n)某算法的語(yǔ)句執(zhí)行頻度為(A. O( n)B. O( nlog下面程

2、序段的時(shí)間復(fù)雜度為(i=1;while(i<=n) i=i*3;A. O(n)B. O(3n)C. O(log 3n)解決問(wèn)題的計(jì)算方法D.解決冋題的有限運(yùn)算序列3n+nlog2n+n2+8),其時(shí)間復(fù)雜度表示( C )。D. O(log 2n)22n)C. O(n )C )。D. 0(n 3數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的數(shù)據(jù)元素以及它們之間B )和運(yùn)算等的學(xué)科。A.結(jié)構(gòu)B.關(guān)系下面程序段的時(shí)間復(fù)雜度是(i=s=0;while(s< n)i+;s+=i;A. O(n)B. O(n 2)11、抽象數(shù)據(jù)類(lèi)型的三個(gè)組成部分分別為A.數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作 數(shù)據(jù)

3、項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類(lèi)型D.10、C.運(yùn)算 C)D.算法C. O( Vn)A ) oB.數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)C.數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型D. O(n 3)12、 通常從正確性、易讀性、健壯性、高效性等4個(gè)方面評(píng)價(jià)算法的質(zhì)量，以下解釋錯(cuò) 誤的是(A )oA. 正確性算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定的功能B. 易讀性算法應(yīng)易于閱讀和理解，以便調(diào)試、修改和擴(kuò)充C. 健壯性當(dāng)環(huán)境發(fā)生變化時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生不需要的運(yùn)行結(jié)果D. 高效性即達(dá)到所需要的時(shí)間性能13、下列程序段的時(shí)間復(fù)雜度為( B )ox=n;y=O;while(x>=(y+1)*(y+1) y=y+i;A.

4、O(n)B. 0(, n)C. 0(1) D. O(n2)二、填空題1、 程序段 “ i=1;while(i<=n) i=i*2;”的時(shí)間復(fù)雜度為 O(log 2n)2、數(shù)據(jù)結(jié)構(gòu)的四種基本類(lèi)型中,樹(shù)形結(jié)構(gòu)的元素是一對(duì)多關(guān)系。三、綜合題1、將數(shù)量級(jí) 0(1),0(N),0(N ),0(N 3),O(NLOGN),O(LOGN),O(2)按增長(zhǎng)率由小到大排序。 答案： 0(1) < 0(log 2N) < 0(N) < 0(Nlog 2N) < 0(N 2) < 0(N 3) < 0(2 )第二章線性表、選擇題1、若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第

5、i個(gè)位置插入一個(gè)新元素算法的時(shí) 間復(fù)雜度(C )A. O(log 2n)(1)若一個(gè)線性表中最常用的操作是取第A )存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表 B. 單鏈表 具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是(DA.圖B.樹(shù)C.2、(3、C. 0( n)(n 2)i個(gè)元素和找第i個(gè)元素的前趨元素，則采用C.雙鏈表D.單循環(huán)鏈表0廣義表D.棧D. i4、在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素之前插入一個(gè)新元素時(shí)，需向后移動(dòng)(B) 個(gè)元素。A. n-iB. n-i+1C. n-i-10B. p->n ext=NULLD.p=head5、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足(A )A. p->n ext=h

6、eadC. p=NULL6、鏈表不具有的特點(diǎn)是(元素B.插入刪除不需要移動(dòng)元素D.所需空間與線性表長(zhǎng)度成正比A. 可隨機(jī)訪問(wèn)任一C.不必事先估計(jì)存儲(chǔ)空間7、 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)指針q所指向的新結(jié)點(diǎn)，修改指 針的操作是(C )。A. p->n ext=q;q->prior=p;p->n ext->prior=q ;q->n ext=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=

7、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ǔ)地址（C ）。A. 必須是連續(xù)的 B. 必須是不連續(xù)的C. 連續(xù)與否均可 D. 和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)9、 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，需要向前移動(dòng)（A ）個(gè)元素。A. n-iB. n-i+1C. n-i-1D. i+110、線性表是n個(gè)（C ）的有限序列。A. 表元素B. 字符C. 數(shù)據(jù)元素D. 數(shù)據(jù)項(xiàng)11、 從表中任一結(jié)

8、點(diǎn)出發(fā)，都能掃描整個(gè)表的是（C ）。A. 單鏈表 B. 順序表 C. 循環(huán)鏈表D. 靜態(tài)鏈表12、 在具有n個(gè)結(jié)點(diǎn)的單鏈表上查找值為x的元素時(shí)，其時(shí)間復(fù)雜度為（ A ）。A. O（n）B. O（1）C. O（n2）D. O（n-1）13、線性表L=（a1,a2,an），下列說(shuō)法正確的是（ D ）。A. 每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B. 線性表中至少要有一個(gè)元素C. 表中諸元素的排列順序必須是由小到大或由大到小D. 除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都由一個(gè)且僅有一個(gè)直接前驅(qū)和直 接后繼14、 一個(gè)順序表的第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度為 2，則第 6個(gè)元素的 存儲(chǔ)地址

9、是（ B ）。A. 98B. 100C. 102D. 10615、 在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)的時(shí)間最少的是（D ）。A. 單鏈表 B. 雙鏈表 C. 循環(huán)鏈表D. 順序表16、 在一個(gè)單鏈表中，若刪除p所指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（A ）。A. 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ù)雜度為（C ）（A. O（1）B.

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

11、C. head->next=head（循環(huán)鏈表判定條件）D. head!=NULL12、 在下列對(duì)順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為0（1）的是（A ）。A.訪問(wèn)第i個(gè)元素的前驅(qū)（1<i n ）B. 在第i個(gè)元素之后插入一個(gè)新元素（1 i n）C. 刪除第i個(gè)元素（1 i n）D.對(duì)順序表中元素進(jìn)行排序13、 已知指針p和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。假設(shè)指針s指向另 一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語(yǔ)句為（A ）。A. q->next=s->next； s->next=p ；B. s->next=p ； q-&

12、gt;next=s->next ；C. p->next=s->next； s->next=q ；D. s->next=q ； p->next=s->next ；14、在以下的敘述中，正確的是（ C ）。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的順序表中，當(dāng)在任何位置刪除一個(gè)元素的概率相同時(shí)，刪除一個(gè)元素 所需移動(dòng)的平均個(gè)數(shù)為（A ）。A. （n-1）/2B. n/2C. （

13、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í)行（C ）0A. s->n ext=p->n ext; p->n ext=s;B. p->n ext=s->n ext;s->n ext=p;C. q->n ext=s;s->n ext=p;D. p->n ext=s;s->n ext=q;17、在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)刪除x的后繼的語(yǔ)句是（B ）oA. p=p->n ext;B. p->n ext=p->n ext- >n e

14、xt;C. p->n ext=p;D. p=p->n ext- >n ext;18、在頭指針為head且表長(zhǎng)大于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p->next->next=head ，貝U（ D ）。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í)行的語(yǔ)句： q->next=p->next ; p->n ext = q _。二、填空題答案：q->next=p-&

15、gt;nextp->next=q2、線性表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，其所含元素的個(gè)數(shù)稱(chēng)為線性表的 長(zhǎng)度。答案：線性結(jié)構(gòu)長(zhǎng)度3、寫(xiě)出帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表 L為空表的條件 。答案：L->prior=L->next=L4、帶頭結(jié)點(diǎn)的單鏈表head為空的條件是。答案：head->next=NULL5、在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作:q = p->n ext;p->n ext= _q->n ext_;三、判斷題1單鏈表不是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。對(duì)2在具有頭結(jié)點(diǎn)的單鏈表中，頭指針指向鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。錯(cuò)3、用循環(huán)單鏈表表示的鏈隊(duì)列中，可以不

16、設(shè)隊(duì)頭指針，僅在隊(duì)尾設(shè)置隊(duì)尾指針。對(duì)4、順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。錯(cuò)5、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素但是在物理位置上不一定是相 鄰的。錯(cuò)6、鏈?zhǔn)酱鎯?chǔ)的線性表可以隨機(jī)存取。 錯(cuò)四、程序分析填空題1函數(shù)GetElem實(shí)現(xiàn)返回單鏈表的第i個(gè)元素，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int GetElem(LinkList L,int i,Elemtype *e)LinkList p ； int j ； p=L->n ext;j=1;while(p&&j<i)(1) ;+i;if(!p|j>i) return ERROR;*e=；return OK;答

17、案：(1) p=p->next (2)p->data2、函數(shù)實(shí)現(xiàn)單鏈表的插入算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。int List In sert(L in kList L,i nt i,ElemType e)LNode *p,*s;i nt j;p=L;j=0;while(p!=NULL)&&(j<i-1)p=p-> next;j+;if(p=NULL|j>i-1) return ERROR;s=(LNode *)malloc(sizeof(LNode);s->data=e;(1;(2;return OK;/s=q->data;free(q

18、);return OK;/*listDelete*/答案：(1)p->next!=NULL (2)p->next=q->next5、寫(xiě)出算法的功能。int L(head)node * head;int n=0;node *p;p=head;while(p!=NULL) p=p->n ext;n+;return( n);答案：求單鏈表head的長(zhǎng)度Listl nsert*/答案：(1) s->next=p->next (2)p->next=s3、函數(shù)ListDelete_sq實(shí)現(xiàn)順序表刪除算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整 int ListDelete_sq

19、(Sqlist *L,i nt i)int k;if(i<1|i>L->length) return ERROR;for(k=i-1;k<L->le ngth-1;k+)L->slistk=(1);(2) ；return 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( (j<i-1)p=p->n ext;j

20、+;if(p->next=NULL|j>i-1) return ERROR;q=p->n ext;(2) ;五、綜合題1、編寫(xiě)算法，實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表的逆置算法。 答案： void invent(Lnode *head)Lnode *p,*q,*r;if(!head->next) return ERROR;p=head->next; q=p->next; p->next =NULL; while(q) r=q->next; q->next=p; head->next=q; p=q;q=r; 試編寫(xiě)一個(gè)算法，將一個(gè)順序表逆置，并使用最少

21、的輔助存儲(chǔ)空間實(shí)現(xiàn)。 答案： typedef struct ElemType *elem;int length; Sqlist;Invert_list(Sqlist *L)/* 將順序表進(jìn)行逆置 */ int i; ElemType t; for(i=0;i<(L->length-1)/2;i+) t=L->elemi;L->elem i= L->elem L->length-i-1; L->elem L->length -i-1=t;/*for*/ /*invert_list*/2、 有兩個(gè)循環(huán)鏈表，鏈頭指針?lè)謩e為L(zhǎng)1和L2,要求寫(xiě)出算法將L2

22、鏈表鏈到L1鏈表 之后，且連接后仍保持循環(huán)鏈表形式。答案： void merge(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-

23、>next; p->next=NULL;while(q)r=q; q=q->next;if(r->data<=p->data)r->next=p; head->next=r; p=r; elsewhile(!p && r->data>p->data)s=p; p=p->next; r->next=p; s->next=r;p=head->next; 4、編寫(xiě)算法 , 將一個(gè)頭指針為 head 不帶頭結(jié)點(diǎn)的單鏈表改造為一個(gè)單向循環(huán)鏈表，并 分析算法的時(shí)間復(fù)雜度。答案：void linklis

24、t_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))，所以該算法的時(shí)間復(fù)雜度為 O(N)。5、已知head為帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針，鏈表中的數(shù)據(jù)元素依次為( al, a2,a3,a4,an ) ,A為指向空的順序表的指針。閱讀以下程序段，并回答問(wèn)題：(1) 寫(xiě)出執(zhí)行下列程序段后的順序表 A中的數(shù)據(jù)元素；(2) 簡(jiǎn)要敘述該

25、程序段的功能。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)位置的元素值寫(xiě)入順序表 A6、設(shè)順序表va中的數(shù)據(jù)元數(shù)遞增有序。試寫(xiě)一算法，將x插入到順序表的適當(dāng)位置上, 以保持該表的有序性。答案：void Insert_sq(Sqlist va, ElemTyp

26、e x)int i, j, n;n=length(va); if(x>=van-1) van=x;elsei=0; while(x>vai) i+; for(j=n-1;j>=I;j-) vaj+1=vaj;vai=x; n+;試編寫(xiě)一個(gè)算法，在一個(gè)遞增有序排列的單鏈表中插入一個(gè)新結(jié)點(diǎn)x，并保持有序。struct Linknodeint data ;struct Linknode *next ;typedef struct Linknode *Link;Link insert(Link head)int i,e,j ;Link pointer,s;printf("n

27、please input the elem of you want insert:"); scanf("%d",&e);pointer= head;while (pointer->next && e>=pointer->next->data)/*在鏈表中確定插入的位置*/pointer=pointer->next;if (!pointer->next) s=(Link)malloc(sizeof(struct Linknode); s->data=e; s->next=NULL; pointe

28、r->next=s;else s=(Link)malloc(sizeof(struct Linknode); s->data=e;/*為插入的結(jié)點(diǎn)建立鏈接關(guān)系 */s->next=pointer->next;pointer->next=s;/*if*/ return head;/*LinkList_insert*/7、假設(shè)線性表采用順序存儲(chǔ)結(jié)構(gòu)，表中元素值為整型。閱讀算法f2 ，設(shè)順序表L=(3,7,3,2,1,1,8,7,3),寫(xiě)出執(zhí)行算法f2后的線性表L的數(shù)據(jù)元素，并描述該算法的功能。void f2(SeqList *L)int i,j,k;k=0;for(i

29、=0;i<L->length;i+)for(j=0;j<k && L->datai!=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)。試寫(xiě)一算法，刪除表中所有大于x且小于y的元素(若表中存在這樣的元素)同時(shí)釋放被刪除結(jié)點(diǎn)空間< 答案：void Delete_list(Lnode *head, ElemType x, ElemType y)L

30、node *p, *q;if(!head) return ERROR;p=head; q=p;while(!p)if(p->data>x) && (p->data<y)i+;if(p=head)head=p->next; free(p);p=head; q=p; else q->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，且a<b，編寫(xiě)算法刪除鏈表L中元素值大于a

31、且小于b的所有結(jié)點(diǎn)。void Delete_list(Lnode *head, ElemType a, ElemType b) Lnode *p, *q;if(!head->next) return ERROR;p=head->next; q=p; while(p->next!=head) if(p->data>x) && (p->data<y)i+;if(p=head)head=p->next; free(p); p=head; q=p; elseq->next=p->next; free(p); p=q->n

32、ext; else q=p; p=p->next; 試編寫(xiě)一個(gè)算法，將兩個(gè)元素值遞減排列的順序表合并為一個(gè)非遞增的順序表。typedef struct ElemType *elem;int length;Sqlist;Merge_list(Sqlist *A, Sqlist *B, Sqlist *C) int j=0, k=0, i=0; C->length= A->length+ B->length; while(i<A->length&&j<B->length) if(A->elemi>B->elemj)

33、C->elemk= A->elemi; i+; k+; else C->elemk= B->elemj; j+; k+; while(i< A->length) C->elemk= A->elemi; i+; k+; while(j< B->length) C->elemk= B->elemj; j+; k+;第三章 棧和隊(duì)列、選擇題1、 一個(gè)棧的輸入序列為：a, b, c, d, e,則棧的不可能輸出的序列是(C )。A. a,b,c,d,eB. d,e,c,b,aC. d,c,e,a,bD. e,d,c,b,a2、判斷

34、一個(gè)循環(huán)隊(duì)列Q (最多n個(gè)元素)為滿的條件是( C )。A. Q->rear=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ì)的算法,采用(D )數(shù)據(jù)結(jié)構(gòu)最佳。A. 順序表B. 鏈表C. 隊(duì)列D. 棧4、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(B )。A. head=NULLB. head->next=NULLC. head->next!=NULLD. head!=NULL5、 一個(gè)棧的

35、輸入序列為：1,2,3,4 ,則棧的不可能輸出的序列是( D )。A. 1243 B. 2134 C. 1432D. 4312 E. 32146、 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)rear和front的值分別為0, 3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為(B )。A. 1 和5B. 2和4C. 4和2D. 5和17、隊(duì)列的插入操作是在(A )。A. 隊(duì)尾B. 隊(duì)頭 C. 隊(duì)列任意位置D. 隊(duì)頭元素后8循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則判斷循環(huán)隊(duì)列為空的條件是 ( A )。A. front=rearB. front=0C. re

36、ar=0D. front=rear+19、一個(gè)順序棧S,其棧頂指針為top，則將元素e入棧的操作是( A )。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á)式是( B )。A. abcd+-B. abc+*d- C. abc*+d- D. -+*abcd11、 將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí),通常需要使用(B )來(lái)保存中間結(jié)果。A. 隊(duì)列B. 棧 C. 鏈表D. 樹(shù)12、 棧的插入和刪除操作在(B )。A. 棧底B. 棧頂C.

37、 任意位置D. 指定位置13、 五節(jié)車(chē)廂以編號(hào) 1 , 2, 3, 4, 5順序進(jìn)入鐵路調(diào)度站(棧),可以得到(C )的 編組。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 )。A. S->top=0B. S->top!=0C. S->top=n D. S->top!=n15、 在一個(gè)鏈隊(duì)列中，front和rear分別為頭指針和尾指針，則插入一個(gè)結(jié)點(diǎn)s的操作為 ( C )。A. front=front->nextB. s->ne

38、xt=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 )。A. 1 ， 2， 3， 4B. 4 ， 3， 2，1C. 1 ， 4， 3， 2D. 3 ， 4， 1，217、依次在初始為空的隊(duì)列中插入元素a,b,c,d 以后，緊接著做了兩次刪除操作，此時(shí)的隊(duì)頭元素是( C )。A. aB. bC. cD. d18、正常情況下，刪除非空的順序存儲(chǔ)結(jié)構(gòu)的堆棧的棧頂元素，棧頂指針top 的變化是( D )。A. top 不變 B. top=0 C

39、. top=top+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)用大小為h的數(shù)組存儲(chǔ)順序循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為(C )。A. NB. N+1C. N-1D. N-2【

40、解析：隊(duì)列的頭指針指向的是第一個(gè)元素的前一個(gè)結(jié)點(diǎn)， 而不是指向第一個(gè)元素， 一次隊(duì)列的頭指針要占用一個(gè)結(jié)點(diǎn)長(zhǎng)度?！?2、 隊(duì)列的刪除操作是在(A )。A. 隊(duì)首B. 隊(duì)尾C. 隊(duì)前D. 隊(duì)后23、 若讓元素 1 ， 2， 3依次進(jìn)棧，則出棧次序不可能是(C )。A. 3 ， 2， 1B. 2 ， 1 ， 3 C. 3 ， 1 ， 2D. 1 ， 3， 224、 循環(huán)隊(duì)列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針?lè)謩e是front和rear，則 當(dāng)前隊(duì)列中的元素個(gè)數(shù)是( A )。A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-f

41、ront25、 在解決計(jì)算機(jī)主機(jī)和打印機(jī)之間速度不匹配問(wèn)題時(shí)，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)， 主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)， 而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印。 該緩 沖區(qū)應(yīng)該是一個(gè)( B )結(jié)構(gòu)。A. 堆棧B. 隊(duì)列C. 數(shù)組D. 線性表【解析：先進(jìn)入緩沖區(qū)的文件先被打印，選擇先進(jìn)先出的結(jié)構(gòu)，即隊(duì)列?！?6、棧和隊(duì)列都是( C )。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)【解析：棧是只允許在棧頂進(jìn)行插入和刪除操作的線性表，隊(duì)列是只允許在隊(duì)頭進(jìn) 行刪除，在隊(duì)尾進(jìn)行刪除操作的線性表】27、在一個(gè)鏈隊(duì)列中，假定front和rea

42、r分別為隊(duì)頭指針和隊(duì)尾指針，刪除一個(gè)結(jié)點(diǎn)的 操作是( A )。A. front=front->n extC. rear- >n ext=fr ont28、隊(duì)和棧的主要區(qū)別是(D )A.邏輯結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)數(shù)不同B. rear= rear- >n extD. front->n ext=rearB. 存儲(chǔ)結(jié)構(gòu)不同D.限定插入和刪除的位置不同二、填空題1設(shè)棧S和隊(duì)列C的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過(guò)棧S, 個(gè)元素出 棧后即進(jìn)入隊(duì)列Q若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1 ，則棧的容量至少應(yīng)該 答案：32、一個(gè)循環(huán)隊(duì)列Q

43、的存儲(chǔ)空間大小為M,其隊(duì)頭和隊(duì)尾指針?lè)謩e為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)過(guò)一系列的入隊(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ì)列都是受限的線性結(jié)構(gòu)。對(duì)2、在單鏈表中，要訪問(wèn)某個(gè)結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的地址即可；因此，單鏈表是一種 隨機(jī)存取結(jié)構(gòu)。錯(cuò)3、 以鏈表作為棧

44、的存儲(chǔ)結(jié)構(gòu)，出棧操作必須判別?？盏那闆r。對(duì)四、程序分析填空題1、已知棧的基本操作函數(shù)：intlnitStack(SqStack *S); 連接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ù)元素是一個(gè)字符D.數(shù)據(jù)元素任意4、設(shè)串長(zhǎng)為n,模式串長(zhǎng)為m則KMP算法所需的附加空間為(A )。A. O(m)B. 0(n)C. O(m* n) D. 0( nlog2m)5、空串和空格串(B )。

45、A. 相同B.不相同 C.可能相同D.無(wú)法確定6、與線性表相比，串的插入和刪除操作的特點(diǎn)是( A )。A.通常以串整體作為操作對(duì)象B.需要更多的輔助空間C. 算法的時(shí)間復(fù)雜度較高D.涉及移動(dòng)的元素更多7、設(shè)SUBSTR(S,i,k)是求S中從第i個(gè)字符開(kāi)始的連續(xù)k個(gè)字符組成的子串的操作，則對(duì) 于S=' Beijing&Nanjing '，SUBSTR(S,4,5)=( B )。A. ijing 'B. jing& ' C. ingNa'D. ing&N'、判斷題對(duì)對(duì)對(duì))1、造成簡(jiǎn)單模式匹配算法BF算法執(zhí)行效率低的原因是有回

46、溯存在)2、KM算法的最大特點(diǎn)是指示主串的指針不需要回溯。)3、完全二叉樹(shù)某結(jié)點(diǎn)有右子樹(shù)，則必然有左子樹(shù)。三、填空題1、 求子串在主串中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為 。答案：模式匹配2、設(shè) s=' I J AMT L TEACHER,其長(zhǎng)度是 。答案：143、兩個(gè)串相等的充分必要條件是兩個(gè)串的長(zhǎng)度相等且 答案：對(duì)應(yīng)位置的字符也相同 四、程序填空題1、函數(shù)kmp實(shí)現(xiàn)串的模式匹配，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整<int kmp(sqstri ng *s,sqstri ng *t,i nt start,i nt n ext) int i=start-1,j=0;while(i<s->

47、le n&&j<t->le n) if(j=-1|s->datai=t->dataj) i+；j+；else j= _ n extj _jif(j>=t->le n) return( i-t->le nelsereturn(-1);2、函數(shù)實(shí)現(xiàn)串的模式匹配算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整 int in dex_bf(sqstri ng*s,sqstri ng *t,i nt start)int i=start-1,j=0;while(i<s->le n&&j<t->le n)if(s->dat

48、ai=t->dataj)i+；j+；elsei= i-j+1;j=0; if(j>=t->le n)return i-t->le n+1;elsereturn -1;/*listDelete*/3、寫(xiě)出下面算法的功能。in t fun ctio n(SqStri ng *s1,SqStri ng *s2)int i;for(i=0;i<s1->le ngth&&i<s1->le ngth;i+) if(s->datai!=s2->datai) return s1->datai-s2->datai;retur

49、n s1->le ngth-s2->le ngth;答案：.串比較算法4、寫(xiě)出算法的功能。int fun( sqstri ng *s,sqstri ng *t,i nt start)int i=start-1,j=0;while(i<s->le n&&j<t->le n)if(s->datai=t->dataj) i+;j+;else i=i-j+1;j=0;if(j>=t->le n)return i-t->le n+1;else return -1;答案：串的模式匹配算法第五章數(shù)組和廣義表一、選擇題1、設(shè)廣義

50、表L=（a，b, c），則L的長(zhǎng)度和深度分別為（C）A. 1 和 1B. 1 和 3C.1和2D. 2 和32、廣義表（a）,a）的表尾是（B）°A. aB. (a)C.()D. (a)3、稀疏矩陣的常見(jiàn)壓縮存儲(chǔ)方法有(C )兩種A.二維數(shù)組和三維數(shù)組C.三元組和十字鏈表4、一個(gè)非空廣義表的表頭(A.不可能是子表C.只能是原子B. 三元組和散列表D. 散列表和十字鏈表D )。B. 只能是子表D. 可以是子表或原子5、數(shù)組A0.5,0.6的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為A ）。D. 1210A ）。D. 8的內(nèi)存單元中，則元素A55的地址是(A.1175B.118

51、0 C.12056、廣義表 G=(a,b(c,d,(e,f),g)的長(zhǎng)度是A. 3B. 4C. 7 7、采用稀疏矩陣的三元組表形式進(jìn)行壓縮存儲(chǔ)，若要完成對(duì)三元組表進(jìn)行轉(zhuǎn)置，只要 將行和列對(duì)換，這種說(shuō)法(B )。A.正確 B.錯(cuò)誤 C.無(wú)法確定D.以上均不對(duì)& 廣義表(a,b,c)的表尾是(B )。A. b,cB. (b,c)C. cD. (c)9、 常對(duì)數(shù)組進(jìn)行兩種基本操作是(C )0A.建立和刪除B.索引和修改C. 查找和修改D.查找與索引10、對(duì)一些特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了( D )oA.表達(dá)變得簡(jiǎn)單B.對(duì)矩陣元素的存取變得簡(jiǎn)單C. 去掉矩陣中的多余元素D.減少不必要的

52、存儲(chǔ)空間的開(kāi)銷(xiāo)11、 設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元 素，其存儲(chǔ)地址為1，每元素占1個(gè)地址空間，則a85的地址為(B )oA. 13B. 33 C. 18D. 4012、設(shè)矩陣A是一個(gè)對(duì)稱(chēng)矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一維數(shù)組 B1,n(n-1)/2中，對(duì)下三角部分中任一元素ai,j(i>=j)，在一維數(shù)組B的下標(biāo)位置k的 值是(A ) oA. 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. bD

53、. (a)14、稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即( C )oA.二維數(shù)組和三維數(shù)組B.三元組和散列4X 5的稀疏矩陣是C.三元組和十字鏈表D.散列和十字鏈表15、假設(shè)以三元組表表示稀疏矩陣，則與如圖所示三元組表對(duì)應(yīng)的(注：矩陣的行列下標(biāo)均從1開(kāi)始)(B )。0806008060A70000f70003A.B.0000050400504000000012-814s'2r i7253f 31- 53340 8 0 6 0小00003C.70000504000 8 0 6 0小7000 0D.50 4 0 300 0 0 016、以下有關(guān)廣義表的表述中，正確的是( A ) A.由0個(gè)或多

54、個(gè)原子或子表構(gòu)成的有限序列B. 至少有一個(gè)元素是子表C. 不能遞歸定義D. 不能為空表操作的結(jié)果是17、對(duì)廣義表 L=(a,b),(c,d),(e,f)執(zhí)行head(tail(head(tail(L)(D )。A.的B. eC. (e)D. (e,f)、判斷題(錯(cuò))1、廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度。(錯(cuò))2、一個(gè)稀疏矩陣采用三元組表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互 換，并把miftnu的值進(jìn)行互換，則完成了矩陣轉(zhuǎn)置。(對(duì))3、稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。錯(cuò))4、廣義表的長(zhǎng)度是指廣義表中括號(hào)嵌套的層數(shù)。(對(duì))5、廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)，其元素可以是單原子也可以是子

55、表。三、填空題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)橹鲀煞N不同的存儲(chǔ)方式。4、 稀疏矩陣的壓縮存儲(chǔ)方式有：_三元組表 和_十字鏈表法_。四、綜合題1、現(xiàn)有一個(gè)稀疏矩陣，請(qǐng)給出它的三元組表。答案：第六章樹(shù)一、選擇題1、二叉樹(shù)的深度為k,則二叉樹(shù)最多有(C )個(gè)結(jié)點(diǎn)。A. 2kB. 2k-1C. 2 k-1D. 2k-12、用順序存儲(chǔ)的方法，將完全二叉樹(shù)中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維 數(shù)組 R1.N 中，若結(jié)點(diǎn) Ri 有右孩子，則其右孩子是（ B ）。A. R2i-1 B. R2i+1 C. R2i D. R2/i3、 設(shè)a,b為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前面的條件是（B ）。A. a在b的右方B. a在b的左方C. a是b的祖先D. a 是b的子孫4、 設(shè)一棵二叉樹(shù)的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹(shù)先序遍歷 序列為（ D ）。A. a