數(shù)據(jù)結構自測題

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