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

1、a.圖b.樹c.廣義表4、計算機中的算法指的是解決某一個問題的有限運算序列,(b )等5個特性。a.可執(zhí)行性、可移植性和可擴充性b.可執(zhí)行性、有窮性和確定性第一一、選擇題1、研究數(shù)據(jù)結(jié)構(gòu)就是研究(d )。a.數(shù)據(jù)的邏輯結(jié)構(gòu)c.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)操作2、算法分析的兩個主要方面是(a )a.空間復(fù)雜度和時間復(fù)雜度檔性 d.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是(d )章概論b.數(shù)據(jù)的存儲結(jié)構(gòu)d.數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本b.正確性和簡單性c.可讀性和文d. 棧它必須具備輸入、輸出、c.確定性、有窮性和穩(wěn)定性d. 易讀性、穩(wěn)定性和確定性5、下面程序段的時間復(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.計算機程序b.解決問題的計算方法c.排序算法d.解決問題的有限運算序列7、某算法的語句執(zhí)行頻度為(3n+nlog2n+n2+8),其時間復(fù)雜度表示(c )。a. o(n)b. o(nlog2n)c. o(n 2)d. o(log 2n)8、下面程序段的時間復(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ù)值計算的程序設(shè)計問題中計算

3、機的數(shù)據(jù)元素以及它們之問的(b )和運算等的學(xué)科。a.結(jié)構(gòu)b.關(guān)系c.運算d.算法10、下面程序段的時間復(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、鏈表不具有的特點是()。a.可隨機訪問任一元素b.插入刪除不需要移動元素c.不必事先估計存儲空間d.所需空間與線性表長度成正比7、在雙向循環(huán)鏈表中，在p指針所指的結(jié)點后插入一個指針q所指向的新結(jié)點，修改 指針的操作是(

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、線性表采用鏈式存儲時，結(jié)點的存儲地址（）0a.必須是連續(xù)的b.必須是不連續(xù)的c.連續(xù)與否均可d.和頭結(jié)點的存儲地址相連續(xù)9、在一個長度為n的順序表中刪除第i個元素，需要向前移動（）個元素。a. n-ib.

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

6、4、一個順序表的第一個元素的存儲地址是 90,每個元素的長度為2,則第6個元素 的存儲地址是（）。a. 98b. 100c. 102 d. 10615、在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費的時間最少的是（）。a. 單鏈表b.雙鏈表 c.循環(huán)鏈表 d.順序表16、在一個單鏈表中，若刪除p所指向結(jié)點的后續(xù)結(jié)點，則執(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、將長度為n的單鏈表連接在長度為m勺單鏈表之后的算法的時間復(fù)雜度為（）0a. o（1）b. o（n）c. o

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

8、結(jié)點的12、在下列對順序表進行的操作中，算法時間復(fù)雜度為o（1）的是（）。a.訪問第i個元素的前驅(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.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)b.線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況c.線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況d.線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)15、在表長為n的順序表中

9、，當(dāng)在任何位置刪除一個元素的概率相同時，刪除一個元 素所需移動的平均個數(shù)為()。a. (n-1)/2b. n/2c. (n+1)/2d. n16、在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插 入一個結(jié)點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é)點，實現(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且表長大于1的單循環(huán)鏈表中，指針 p指向表中某個結(jié)點，若 p-next-next=head，貝u ()。a. p指向頭結(jié)點 b. p指向尾結(jié)點c. p的直接后繼是頭結(jié)點d. p的直接后繼是尾結(jié)點二、填空題1、設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next )。已知指針p指向單鏈表中的結(jié)點，q指向新 結(jié)點，欲將q插入到p結(jié)點之后，則需要執(zhí)行的語 句：; 。答案：q-next=p-next p-next=q2、線性表的邏輯結(jié)構(gòu)是,其所含元素的個數(shù)稱為線性表的 。答案：線性結(jié)構(gòu)長度3、寫出帶頭結(jié)點的雙向循環(huán)鏈表 l為空表的條件。答案：l-prior=l

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

12、元素，請在空格處將算法補充完整。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ù)實現(xiàn)單鏈表的插入算法，請在空格處將算法補充完整。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實現(xiàn)順序表

14、刪除算法，請在空格處將算法補充完整 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ù)實現(xiàn)單鏈表的刪除算法，請在空格處將算法補充完整。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的長度五、綜合題1、編寫算法，實現(xiàn)帶頭結(jié)點單鏈表的逆置算法。答案：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、有兩個循環(huán)鏈表，鏈頭指針分別為l1和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è)一個帶頭結(jié)點的單向鏈表的頭指針為head,設(shè)計算法，將鏈表的記錄，按照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、編寫算法，將一個頭指針為head不帶頭結(jié)點的單鏈表改造為一個單向循環(huán)鏈表， 并分析算法的時間復(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è)單鏈表的長度(數(shù)據(jù)結(jié)點數(shù))為n,則該算法的時間主要花費在查找鏈表最后一個結(jié)點上(算法中的while循環(huán))，所以

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

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è)線性表采用順序存儲結(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、已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一算法， 刪除表中所有大于x且小于y的元素(若表中存在這樣的元素)同時釋放被刪除結(jié)點 空間。答案：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é)點的循環(huán)鏈表l中，結(jié)點的數(shù)據(jù)元素為整型，且按值遞增有序存放。給 定兩個整數(shù)a和b,且2rear=q-frontb. q-rear=q-front+1c. q-front=（q-rear+1）%nd. q-front=（q-rear-1）%n3、設(shè)計一個判別表達式中括號是否配對的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。a.順序表

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

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

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

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

26、+1d. top=top-119、判斷一個循環(huán)隊列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è)計一個判別表達式中左右括號是否配對出現(xiàn)的算法，采用（ c ）數(shù)據(jù)結(jié)構(gòu)最 佳。a.線性表的順序存儲結(jié)構(gòu)b.隊列 c.棧d.線性表的鏈式存儲結(jié)構(gòu) 21、當(dāng)用大小為n勺數(shù)組存儲順序循環(huán)隊列時，該隊列的最大長度為（ c ）。a. nb. n+1c. n-1d. n-222、隊列的刪除操作是在（a ）。a.隊首b.隊尾c.隊前d.隊后23、若讓元素1, 2,

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

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

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

30、性結(jié)構(gòu)。2、在單鏈表中，要訪問某個結(jié)點，只要知道該結(jié)點的地址即可；因此，單鏈表是一 種隨機存取結(jié)構(gòu)。3、以鏈表作為棧的存儲結(jié)構(gòu)，出棧操作必須判別?？盏那闆r。四、程序分析填空題1、已知棧的基本操作函數(shù)：int initstack(sqstack *s); /構(gòu)造空棧int stackempty(sqstack *s);/判斷?？読nt push(sqstack *s,elemtype e);/入棧int pop(sqstack *s,elemtype *e);/出棧函數(shù)conversion實現(xiàn)十進制數(shù)轉(zhuǎn)換為八進制數(shù)，請將函數(shù)補充完整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)隊列非空，隊頭元素出隊列且返回其值，否則返回空元素。3、閱讀算法f2,并回答下列問題：(1)設(shè)隊列q= (1,

32、 3, 5, 2, 4, 6)。寫出執(zhí)行算法f2后的隊列q;(2)簡述算法f2的功能。void f2(queue *q) datatype e;if (!queueempty(q) e=dequeue(q);f2(q);enqueue(q,e);(2)將隊列倒置答案：(1) 6,4,2,5,3,1五、綜合題1、假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，但不設(shè)頭指針，請寫出相應(yīng)的入隊列算法(用函數(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是一個非空隊列，s是一個空棧。編寫算法，僅用隊列和棧的adt函數(shù)和少 量工作變量，將隊列q的所有元素逆置。棧的adt函數(shù)有：void makeempty(sqstack s); 置空棧void push(sqstack s,elemtype e); 元素e入棧elemtype pop(sqstack s);出棧，返回棧頂元素int isempty(sqstack s);判斷棧空隊列的adt函數(shù)有：void enqueue(queue

34、 q,elemtype e); 元素e入隊elemtype dequeue(queue q); 出隊，返回隊頭元素int isempty(queue q); 判斷隊空 答案：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、對于一個棧，給出輸入項

35、a,b,c,d,如果輸入項序列為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è)有兩個用s1和s2,求用s2fts1中首次出現(xiàn)位置的運算稱作(c )。a.連接b.求子用c.模式匹配d.判斷子用2、已知用s= aaab,則next數(shù)組值為(a )。a.0123b.1123c.1231d.12113、用與普通的線性表相比較，它的特殊性體現(xiàn)在( c )。a.順序的存儲結(jié)構(gòu)b.鏈式存儲結(jié)構(gòu)c.數(shù)據(jù)元素

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

37、ing& c. ingnad.ing&n二、判斷題(x ) 1、造成簡單模式匹配算法bf算法執(zhí)行效率低的原因是有回溯存在。(v ) 2、km算法的最大特點是指示主審的指針不需要回溯(v ) 3、完全二叉樹某結(jié)點有右子樹，則必然有左子樹。模式匹西己三、填空題1、求子用在主審中首次出現(xiàn)的位置的運算稱為一2、設(shè)$= iamt ateacher,其長度是 _14.3、兩個用相等的充分必要條件是兩個用的長度相等且對應(yīng)位置字符相r 。 四、程序填空題 1、函數(shù)km成現(xiàn)用的模式匹配，請在空格處將算法補充完整。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ù)實現(xiàn)用的模式匹配算法，請在空格處將算法補充完整。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的長度和深度分別為(c )。a. 1 和1b. 1 和3c. 1 和2 d. 2 和32、廣義表(a),a)的表尾是(b )。a. ab. (a)c. ()d. (a)3、稀疏矩陣的常見壓縮存儲方法有(c )兩種。a.二維數(shù)組和三維數(shù)組b.三元組和散列表c.三元組和十字鏈表 d.散列表和十字鏈表 4、一個非空廣義表的表頭(d )。a.不可能是

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

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

43、下標位置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、稀疏矩陣一般的壓縮存儲方法有兩種，即( c )。a.二維數(shù)組和三維數(shù)組b.三元組和散列c.三元組和十字鏈表 d.散列和十字鏈表4x5的稀疏矩陣15、假設(shè)以三元組表表示稀疏矩陣，則與如圖所示三元組表對應(yīng)的是(注：矩陣的行列下標均從1開始)a.，0-8060c.00003700005040008060、7000000000150400，b.0-8067000-50400000

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

45、置。(v ) 3、稀疏矩陣壓縮存儲后，必會失去隨機存取功能。(x ) 4、廣義表的長度是指廣義表中括號嵌套的層數(shù)。(v ) 5、廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)，其元素可以是單原子也可以是子表。三、填空題1、已知二維數(shù)組amn采用行序為主方式存儲，每個元素占k個存儲單元，并且第 一個元素的存儲地址是loc(a00),則aij 的地址是 loc(a00)+(i*n+j)*k 。2、廣義表運算式 head(tail(a,b,c),(x,y,z)的結(jié)果是：(x,y,z)。3、二維數(shù)組，可以按照 列序為主和行序為豐 兩種不同的存儲方式。4、稀疏矩陣的壓縮存儲方式有：三元組 和 十字鏈表。四、綜合題1、現(xiàn)有

46、一個稀疏矩陣，請給出它的三元組表。0 31010000 2100-201答案：ijv12313121132233143-2第六章樹 一、選擇題 1、二叉樹的深度為k,則二叉樹最多有（c ）個結(jié)點。a. 2kb. 2 k-1 c. 2 k-1d. 2k-12、用順序存儲的方法，將完全二叉樹中所有結(jié)點按層逐個從左到右的順序存放在一 維數(shù)組r1.n中，若結(jié)點ri有右孩子，則其右孩子是（b ）。a. r2i-1b. r2i+1c. r2id. r2/i3、設(shè)a,b為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，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é)點總數(shù)為（a ）。a. 31b. 32 c. 33d. 166、由二叉樹的前序和后序遍歷序列（ b ）惟一確定這棵二叉樹。a.能b.不能7、某二叉樹的中序序列為abcdefg后序序列為bdcafge則其左子樹中結(jié)點數(shù)目為 （c ）。a. 3b. 2c. 4 d. 58、若以4,5,6,7,8作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長度為（ c ）。a. 67b. 68c. 69d. 709、將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1,則編號為49的結(jié)點的左孩子編號為（a ）。a. 98b. 99c. 50 d. 4810、表達式a*（b+c）-d的后綴表達式是（b ）。a. abcd+-b. abc+*d- c. abc*+d- d. -+*abcd11、對某二叉樹進行先序遍歷的結(jié)果為 abdefc中序遍歷的結(jié)果為dbfeac則后序遍 歷的結(jié)果是（b ）。a. dbfeac b. dfebca c. bdfeca d. bdefac 12、樹最適合用來表示（c ）。a.有序數(shù)據(jù)