數(shù)據(jù)結(jié)構(gòu)自測題

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請聯(lián)系刪除，謝謝！一．緒論1.1單項(xiàng)選擇題①②DR是D①②。。①②①②1.2填空題（將正確的答案填在相應(yīng)的空中）、和為。。。,_。,,_,。1。。。{}。第二章基礎(chǔ)知識一、選擇題1、線性表是_______。A.一個有限序列，可以為空C.一個無限序列，可以為空一個有限序列，不能為空D.一個無限序列，不能為空2、在一個長度為n的順序存儲的線性表中，向第i1i）位置插入一個新元素時，需要從后向前依次后移______個元素。A.n-iB.n-i+1C.n-i-1D.i3、在一個長度為n的線性表中，刪除值為x的元素時需要比較元素和移動元素的總次數(shù)為_______。A.(n+1)/2B.n/2C.nD.n+14、在一個順序表的表尾插入一個元素的時間復(fù)雜性的量級為_______。A.O(n)B.O(1)C.O(n)D.O(logn)225、設(shè)單鏈表中指針p指向結(jié)點(diǎn)a，若要刪除aii2改指針的操作為____________。A.p->next=p->next->next;C.p=p->next->next;B.p=p->next;D.next=p;6、設(shè)單鏈表中指針p指向結(jié)點(diǎn)a，指針f指向?qū)⒁迦氲男陆Y(jié)點(diǎn)x，問：i（1）當(dāng)x插在鏈表中兩個數(shù)據(jù)元素a和a之間時，只要先修改______后修改ii+1______即可。A.p->next=fC.p->next=f->nextE.f->next=NULLB.p->next=p->next->nextD.f->next=p->nextF.f->next=p（2）在鏈表中最后一個結(jié)點(diǎn)a______后修改______即n可。A.f->next=pC.p->next=fE.f=NULLB.f->next=p->nextD.p->next=f->next7、在一個單鏈表中，若要在p所指向的結(jié)點(diǎn)之前插入一個新結(jié)點(diǎn)，則此算法的時間復(fù)雜度為________。A.O(n)B.O(n/2)C.O(1)D.O(n)8、不帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件為_________。A.L==NULLC.L->next==LB.L->next==NULLD.L!=NULL9、帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件為_________。A.L==NULLC.L->next==LB.L->next==NULLD.L!=NULL10、指針p指向雙向鏈表中的結(jié)點(diǎn)a，為a的前驅(qū)結(jié)點(diǎn)，指針f指向?qū)⒁錫ii1i入的新結(jié)點(diǎn)x。x插在a和a之間，此時需要修改指針的操作依次為i1i_________________。A.p->prior->next=fC.f->next=pB.p->prior=fD.f->prior=p->priorp所指的結(jié)點(diǎn)之后插入一個q指針?biāo)赶虻慕Y(jié)點(diǎn)，則需要對q->next賦值為______。A.p->priorB.p->nextC.p->next->nextC.p->prior->prior二、填空題：1、線性表的兩種存儲結(jié)構(gòu)分別為__________和_______________。2_______經(jīng)常需要對線性表進(jìn)行查找運(yùn)算，則最好采用________存儲結(jié)構(gòu)。3、訪問一個線性表中具有給定值元素的時間復(fù)雜度為__________。34、對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為______，在表尾插入元素的時間復(fù)雜度為___________。5、單鏈表是____________的鏈接存儲表示。6p所指向的結(jié)點(diǎn)的后面插入一個指針q所指向的結(jié)點(diǎn)時，首先把_______的值賦給q->next，然后把__________的值賦給p->next。7p所指結(jié)點(diǎn)之前插入一個s（1）s->next=______________;（2）p->next=s;（3）t=p->data;（4）p->data=______________;（5）s->data=______________;8、假定指向單鏈表中第一個結(jié)點(diǎn)的表頭指針為，則向該單鏈表的表頭插入指針p所指向的新結(jié)點(diǎn)時，首先執(zhí)行____________賦值操作，然后執(zhí)行________________賦值操作。9p_____________的值賦給p->next指針域。10、在一個單鏈表中刪除指針p所指結(jié)點(diǎn)時，應(yīng)執(zhí)行以下操作：q=p->next;p->data=p->next->data;p->next=___________;free(q);________來確定它，即通過頭指針或尾指針可以訪問到該鏈表中的每個結(jié)點(diǎn)。12p復(fù)雜性的量級為___________________。三、簡答題1、對于線性表的兩種存儲結(jié)構(gòu)，如果線性表的總數(shù)基本穩(wěn)定，并且很少進(jìn)行插儲結(jié)構(gòu)？試說明理由。2、有哪些鏈表可僅由一個尾指針來唯一確定，即從尾指針出發(fā)能訪問到鏈表上任何一個結(jié)點(diǎn)？3、在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪除？若可以，其時間復(fù)雜度各為多少？4四、算法閱讀題讀下面的程序段，畫出執(zhí)行過程的示意圖及所完成的功能。1.#defineN6voidmain(){SqListL;intA[N];inti,j,m,elem;InitList_Sq(L);//初始化順序表for(j=0;j<N;j++)scanf("%d",&A[j]);for(m=0;m<N;m++)ListInsert_Sq(L,m+1,A[m]);PrintList(L);//輸出函數(shù)，順序輸出表中元素}2.intA(LinkListL){/*L是無表頭結(jié)點(diǎn)的單鏈表*/if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}return1;}3.voidBB(LNode*s,LNode*q){p=s;while(p->next!=q)p=p->next;p->next=s;}voidAA(LNode*pa,LNode*pb){/*pa和pb分別指向單循環(huán)鏈表中兩個節(jié)點(diǎn)*/5BB(pa,pb);BB(pb,pa);}五、算法設(shè)計(jì)題1、分別編寫在順序表和帶頭結(jié)點(diǎn)的單鏈表上統(tǒng)計(jì)出值為x的元素個數(shù)的算法，統(tǒng)計(jì)結(jié)果由函數(shù)值返回。2An將x插入到線性表的適當(dāng)位置，以保持線性表的有序性。3、已知兩個單鏈表A和，指向頭結(jié)點(diǎn)的指針分別為La和，試編寫一個算法從單鏈表A中刪除自第i個元素起的共length表B的第j個元素之前。4B和CA作如下運(yùn)算：刪去那些既在表B中出現(xiàn)又在表C中出現(xiàn)的元素。試分別以兩種存儲結(jié)構(gòu)（一種順序的，一種鏈?zhǔn)降模┚帉憣?shí)現(xiàn)上述運(yùn)算的算法。5、已知線性表的元素是無序的，且以帶頭結(jié)點(diǎn)的單鏈表作為存儲結(jié)構(gòu)。試編寫一個刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素）的算法。6、有兩個循環(huán)不帶頭結(jié)點(diǎn)的單鏈表如圖所示，編寫一個算法將鏈表1連接到鏈表2之后，并仍然保持循環(huán)鏈表形式。67、假設(shè)有一個單向循環(huán)鏈表，其結(jié)點(diǎn)含有三個域：，data和next，其中data為數(shù)據(jù)域；next為指針域，它指向后繼結(jié)點(diǎn)；pre為指針域，它的值為空指針（8、編寫算法實(shí)現(xiàn)順序表的就地逆置，即利用原順序表的存儲單元把數(shù)據(jù)元素序列如（a,a,...,aa,a,...,a）。12nnn119、假設(shè)在長度大于1的循環(huán)單鏈表中，既無頭結(jié)點(diǎn)也無頭指針，p為指向該鏈表中某個結(jié)點(diǎn)的指針，編寫一個算法刪除該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。10、設(shè)頭指針為，編寫算法實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表head的就地逆置，即利用原帶頭結(jié)點(diǎn)單鏈表head的結(jié)點(diǎn)空間把數(shù)據(jù)元素序列（a,a,...,a）逆置為01n1（a,...,a,an110數(shù)據(jù)元素x素的遞增有序。12、設(shè)head為單鏈表的頭指針，并設(shè)單鏈表帶有頭結(jié)點(diǎn)，編寫算法將單鏈表中的數(shù)據(jù)元素按照元素值遞增有序的順序就地排序。13、編寫不帶頭結(jié)點(diǎn)單鏈表的初始化操作、插入操作和刪除操作。一、選擇題1、棧的插入和刪除操作在（A、棧頂B、棧底2123，np1p2p3pn,那么p1=n；pi為（Ａ、iＢ、n-i3、假設(shè)以I和O分別表示入棧和出棧操作，棧的初態(tài)和終態(tài)均為空，入棧）進(jìn)行。C、任意位置D、指定位置Ｃ、n－i＋1Ｄ、不確定和出棧的操作序列可表示為僅由I和OＡ、IOIIOIOO4、遞歸函數(shù)可以調(diào)用自身（Ａ、至多1次Ｂ、任意次數(shù)Ｂ、IOOIOIIOCIIIOIOIOＣ、0次DOIIOIOIO）次。2次二、填空題1、線性表、棧和隊(duì)列都是（）結(jié)構(gòu)，可以在線性表的（）位置插入7和刪除元素；對于棧只能在（）插入和刪除元素；對于隊(duì)列只能在（）插入元素和在（）刪除元素。2應(yīng)先判別棧是否為（m時，作進(jìn)棧運(yùn)算時發(fā)生上溢，則說明棧的可用最大容量為（3、設(shè)有一個空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push，push，pop，push，pop，push，push后，輸出序列是（4、無論對于順序存儲還是鏈?zhǔn)酱鎯Φ臈：完?duì)列來說，進(jìn)行插入或刪除操作的時間復(fù)雜度均相同為（5、有一個循環(huán)隊(duì)列，分配到的存儲空間大小為n，則其隊(duì)滿條件是（三、應(yīng)用題１、若依次讀入數(shù)據(jù)元素序列{a,b,c,d}進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出各種可能的出棧元素序列。2、以下代碼段執(zhí)行什么操作？StackS1，tmp；ElemtypeX；?While(！StackEmpty(S1)){Pop(S1,X)；Push(tmp，X)；}While(!StackEmpty(tmp)){Pop(tmp,X)；Push(S1，X)；}四、算法設(shè)計(jì)題1、有兩個棧s1和s2共享存儲空間c[m]（下標(biāo)為0,...,m-1c[0]c[m-1]s1和s2的進(jìn)棧Push(i,x)Pop(i,x)和設(shè)置?？誗etnull(i)的函數(shù)，其中i=1,2。注意：僅當(dāng)整個空間c占滿時才產(chǎn)生上溢。2、假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧3種類型的括弧，編寫一個判別表達(dá)式中括弧是否正確配對的函數(shù)。以字符“#”作為算術(shù)表達(dá)式的結(jié)束符。3、回文是指正讀和反讀均相同的字符序列，如“”和“abdba”均是回文，但“”不是回文。試寫一個算法判定給定的字符串是否回文，該字符串是從84、如果用一個循環(huán)數(shù)組q[num]表示隊(duì)列時，該隊(duì)列只有一個頭指針front指向隊(duì)首元素，不設(shè)隊(duì)尾rear，而設(shè)置計(jì)數(shù)器count用以記錄隊(duì)列中結(jié)點(diǎn)的個數(shù)。編寫實(shí)現(xiàn)隊(duì)列的5EmptyqGetHead，OutQueue。提示]算法的思想：依照題意，可以得出以下條件：隊(duì)列為空：count==0;隊(duì)列為滿：count==num;(front+count)%num;出隊(duì)時新的隊(duì)列首元素的位置：(front+1)%num;5、在一個循環(huán)隊(duì)列中，設(shè)計(jì)一個標(biāo)志flag用于標(biāo)識是否為