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

1、緒論1.1單項選擇題數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中,數(shù)據(jù)元素的、數(shù)據(jù)信息在計算機中的以及一組相關(guān)的運算等的課程。A.操作對象B 計算方法C .邏輯結(jié)構(gòu)D .數(shù)據(jù)映象A.存儲結(jié)構(gòu)B.關(guān)系C.運算D.算法2,數(shù)據(jù)結(jié)構(gòu)DS(Data Struct)可以被形式地定義為DS= (D, R),其中D是的有限集合，R是D上的的有限集合。A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.數(shù)據(jù)對象A.操作B.映象C.存儲D.關(guān)系在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分 。動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)算法分析的目的是，算法分析的兩個主要方面是A.找出數(shù)據(jù)結(jié)

2、構(gòu)的合理性C.分析算法的效率以求改進A.空間復雜性和時間復雜性C.可讀性和文檔性研究算法中的輸入和輸出的關(guān)系D.分析算法的易懂性和文檔性B.正確性和簡明性D. 數(shù)據(jù)復雜性和程序復雜性計算機算法指的是，它必具備輸入、輸出和等五個特性B.排序方法D.調(diào)度方法B. 可行性、確定性和有窮性D.易讀性、穩(wěn)定性和安全性A. 計算方法解決問題的有限運算序列A.可行性、可移植性和可擴充性C.確定性、有窮性和穩(wěn)定性1.2填空題(將正確的答案填在相應的空中)數(shù)據(jù)邏輯結(jié)構(gòu)包括、和三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為。在線性結(jié)構(gòu)中，第一個結(jié)點 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 個前驅(qū)結(jié)點；最后一個結(jié)點 后續(xù)結(jié)點，其余每個

3、結(jié)點有且只有個后續(xù)結(jié)點。在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 結(jié)點，其余每個結(jié)點有且只有 個直接前驅(qū)結(jié)點，葉子結(jié)點沒有 結(jié)點，其余每個結(jié)點的直接后續(xù)結(jié)點可。在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可。線性結(jié)構(gòu)中元素之間存在 關(guān)系，樹形結(jié)構(gòu)中元素之間存在 關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。算法的五個重要特性是, ,。分析下面算法(程序段)，該算法的時間復雜度是。for (i=0;in;i+)for (j=0;jn; j+)Aij=0;分析下面算法(程序段)，該算法的時間復雜度是_for (i=0;in;i+)for (j=0; ji; j+) Aij=0;分析下面算法(程序段)，該算法的時間復雜度是

4、_s=0;for (i=0;in;i+)for (j=0;jn;j+)for (k=0;kn;k+) s=s+Bijk;sum=s;分析下面算法(程序段)，該算法的時間復雜度是i=s=0;while (sn) i+;s+=i;/s=s+i分析下面算法(程序段)，該算法的時間復雜度是 i=1;while (i=n)i=i*2;第二章基礎(chǔ)知識一、選擇題1、 線性表是。A.一個有限序列，可以為空B.一個有限序列，不能為空C. 一個無限序列，可以為空D.一個無限序列，不能為空2、在一個長度為n的順序存儲的線性表中，向第i個元素QJ i next=p-next-next;B. p=p-next;C. p

5、=p-next-next;D. next=p;6、設(shè)單鏈表中指針p指向結(jié)點斗，指針f指向?qū)⒁迦氲男陆Y(jié)點x,問: 當x插在鏈表中兩個數(shù)據(jù)元素a和a.之間時，只要先修改 后修改 即可。A. p-next=fB.p-next=p-next-nextC. p-next=f-nextD. f-next=p-nextE. f-next=NULLF. f-next=p 在鏈表中最后一個結(jié)點an之后插入時，只要先修改后修改 即可。A. f-next=pB. f-next=p-nextC. p-next=fD. p-next=f-nextE. f=NULL7、在一個單鏈表中，若要在p所指向的結(jié)點之前插入一個新

6、結(jié)點，則此算法的 時間復雜度為。A. O(n)B. O(n/2)C. O(1)D. O(打)8、 不帶頭結(jié)點的單鏈表L為空的判定條件為。A. L=NULLB.L-next=NULLC. L-next=LD. L!=NULL9、 帶頭結(jié)點的單鏈表L為空的判定條件為。A. L=NULLB.L-next=NULLC. L-next=LD. L!=NULL 10、指針p指向雙向鏈表中的結(jié)點a，a為a的前驅(qū)結(jié)點，指針f指向?qū)⒁錳 i 1 i入的新結(jié)點x。x插在aii和斗之間，此時需要修改指針的操作依次為A. p-prior-next=fB. p-prior=fC. f-next=pD. f-prior

7、=p-prior11、在一個帶頭結(jié)點的雙向循環(huán)鏈表中，若要在指針p所指的結(jié)點之后插入一個 q指針所指向的結(jié)點，則需要對q-next賦值為。A. p-priorB. p-nextC. p-next-nextC. p-prior-prior二、填空題：1、 線性表的兩種存儲結(jié)構(gòu)分別為 和。2、 若經(jīng)常需要對線性表進行插入和刪除運算，則最好采用 存儲結(jié)構(gòu)，若經(jīng)常需要對線性表進行查找運算，則最好采用 存儲結(jié)構(gòu)。3、 訪問一個線性表中具有給定值元素的時間復雜度為。4、對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為，在表尾插入元素的時間復雜度為。5、 單鏈表是 的鏈接存儲表示。6、在一個

8、單鏈表中指針p所指向的結(jié)點的后面插入一個指針q所指向的結(jié)點時，首先把的值賦給q-next，然后把的值賦給p-next。7、在一個單鏈表中的p所指結(jié)點之前插入一個s所指結(jié)點時，可執(zhí)行如下操作:（1）s-next=;（2）p-next=s;（3）t=p-data;（4）p-data=;（5） s-data=;8、假定指向單鏈表中第一個結(jié)點的表頭指針為head，則向該單鏈表的表頭插入指針p所指向的新結(jié)點時，首先執(zhí)行 賦值操作，然后執(zhí)行賦值操作。9、在一個單鏈表中刪除指針p所指向結(jié)點的后繼結(jié)點時，需要把的值賦給p-next指針域。10、在一個單鏈表中刪除指針p所指結(jié)點時，應執(zhí)行以下操作：q=p-nex

9、t;p-data=p-next-data;p-next=;free（q）;11、 在 鏈表中，既可以通過設(shè)定一個頭指針也可以通過設(shè)定一個尾指針 來確定它，即通過頭指針或尾指針可以訪問到該鏈表中的每個結(jié)點。12、在一個雙向循環(huán)鏈表中指針p所指向的結(jié)點之前插入一個新結(jié)點時，其時間 復雜性的量級為。三、簡答題1、對于線性表的兩種存儲結(jié)構(gòu)，如果線性表的總數(shù)基本穩(wěn)定，并且很少進行插 入和刪除操作，但是要求以最快的速度存取線性表中的元素，則應該選用哪種存 儲結(jié)構(gòu)？試說明理由。2、有哪些鏈表可僅由一個尾指針來唯一確定，即從尾指針出發(fā)能訪問到鏈表上 任何一個結(jié)點？3、在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指

10、針p指向某結(jié)點，不知道頭 指針，能否將結(jié)點*?從相應的鏈表中刪除？若可以，其時間復雜度各為多少？四、算法閱讀題讀下面的程序段，畫出執(zhí)行過程的示意圖及所完成的功能。1.# define N 6void main ()SqList L ;int A N ;int i ,j,m, elem ;InitList_Sq(L); 初始化順序表for (j=0; jN; j+)scanf(%d,&A j );for ( m=0; mnext)Q=L; L=L-next; P=L;while (P-next) P=P-next;P-next=Q; Q-next=NULL;return 1;3.void BB(

11、LNode *s, LNode *q) p=s;while (p-next !=q ) p=p-next;p-next=s;void AA(LNode *pa, LNode *pb)/*pa和pb分別指向單循環(huán)鏈表中兩個節(jié)點*/BB(pa,pb);BB(pb,pa);五、算法設(shè)計題1、分別編寫在順序表和帶頭結(jié)點的單鏈表上統(tǒng)計出值為x的元素個數(shù)的算法， 統(tǒng)計結(jié)果由函數(shù)值返回。2、設(shè)線性表存放于順序表A中，其中有n個元素，且遞減有序，請設(shè)計一算法， 將x插入到線性表的適當位置，以保持線性表的有序性。3、已知兩個單鏈表A和B，指向頭結(jié)點的指針分別為La和Lb，試編寫一個算 法從單鏈表A中刪除自第i個

12、元素起的共length個元素，然后將它們插入到單鏈 表B的第j個元素之前。4、已知A，B和C為三個元素值遞增有序的單鏈表，現(xiàn)要求對表A作如下運算: 刪去那些既在表B中出現(xiàn)又在表C中出現(xiàn)的元素。試分別以兩種存儲結(jié)構(gòu)（一 種順序的，一種鏈式的）編寫實現(xiàn)上述運算的算法。5、已知線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。試編寫 一個刪除表中所有值大于 mink 且小于 maxk 的元素（若表中存在這樣的元素） 的算法。6、有兩個循環(huán)不帶頭結(jié)點的單鏈表如圖所示，編寫一個算法將鏈表1連接到鏈 表2之后，并仍然保持循環(huán)鏈表形式。7、假設(shè)有一個單向循環(huán)鏈表，其結(jié)點含有三個域：pre, data和

13、next，其中data 為數(shù)據(jù)域；next為指針域，它指向后繼結(jié)點；pre為指針域，它的值為空指針（NULL）。試編寫算法將此表改為雙向循環(huán)鏈表。8、編寫算法實現(xiàn)順序表的就地逆置，即利用原順序表的存儲單元把數(shù)據(jù)元素序 歹列 如（a , a ,., a），逆置為（ a , a ,., a ） 。12 幾n n 一119、假設(shè)在長度大于1的循環(huán)單鏈表中，既無頭結(jié)點也無頭指針，p為指向該鏈 表中某個結(jié)點的指針，編寫一個算法刪除該結(jié)點的前趨結(jié)點。10、設(shè)頭指針為head，編寫算法實現(xiàn)帶頭結(jié)點單鏈表head的就地逆置，即利用原帶頭結(jié)點單鏈表head的結(jié)點空間把數(shù)據(jù)元素序列（a , a ,., a ）逆置

14、為 0 1n一1（a，,a , a ）。11、設(shè)頭指針為head，并設(shè)帶頭結(jié)點單鏈表中的數(shù)據(jù)元素遞增有序，編寫算法將 數(shù)據(jù)元素x插入到帶頭結(jié)點單鏈表的適當位置上，要求插入后保持單鏈表數(shù)據(jù)元 素的遞增有序。12、設(shè)head為單鏈表的頭指針，并設(shè)單鏈表帶有頭結(jié)點，編寫算法將單鏈表中 的數(shù)據(jù)元素按照元素值遞增有序的順序就地排序。13、編寫不帶頭結(jié)點單鏈表的初始化操作、插入操作和刪除操作。第三章基礎(chǔ)知識一、選擇題1、棧的插入和刪除操作在（）進行。A、棧頂B、棧底C、任意位置D、指定位置2、若已知一個棧的入棧序列是1，2, 3,，n，其輸出序列為pl，p2, p3,， pn,那么 p1=n； pi 為（

15、 ）。A、iB、n-iC、n-i + 1D、不確定3、假設(shè)以I和O分別表示入棧和出棧操作，棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列。下列序列（）是合法的。A、IOIIOIOO B、IOOIOIIO C、IIIOIOIOD、OIIOIOIO4、 遞歸函數(shù)可以調(diào)用自身（）次。A、至多1次 B、任意次數(shù)C、0次D、至多2次二、填空題1、線性表、棧和隊列都是（）結(jié)構(gòu)，可以在線性表的（）位置插入 和刪除元素；對于棧只能在（）插入和刪除元素；對于隊列只能在（）插 入元素和在（）刪除元素。2、對于一個順序棧作進棧運算時，應先判別棧是否為（），作退棧運算時， 應先判別棧是否為（）

16、，當棧中元素為m時，作進棧運算時發(fā)生上溢，則說明 棧的可用最大容量為（）。3、設(shè)有一個空棧，現(xiàn)有輸入序列1， 2， 3， 4， 5，經(jīng)過push，push，pop，push，pop，push，push 后，輸出序列是（）。4、無論對于順序存儲還是鏈式存儲的棧和隊列來說，進行插入或刪除操作 的時間復雜度均相同為（）。5、 有一個循環(huán)隊列，分配到的存儲空間大小為n，則其隊滿條件是（），隊列為空的條件是（）。三、應用題1、若依次讀入數(shù)據(jù)元素序列a,b,c,d進棧，進棧過程中允許出棧，試寫出 各種可能的出棧元素序列。2、以下代碼段執(zhí)行什么操作？Stack S1 ， tmp；Elemtype X ；Wh

17、ile（! StackEmpty（Sl）Pop（S1,X）；Push（tmp，X）；While（!StackEmpty（tmp）Pop（tmp,X）；Push（S1，X）；四、算法設(shè)計題1、有兩個棧si和s2共享存儲空間cm（下標為0,.,m-1），其中一個棧底設(shè)在 c0處，另一個棧底設(shè)在cm-1處，分別編寫si和s2的進棧 Push（i,x）、出棧 Pop（i,x） 和設(shè)置?？誗etnull（i）的函數(shù)，其中i=1,2。注意：僅當整個空間c占滿時才產(chǎn)生 上溢。2、假設(shè)一個算術(shù)表達式中包含圓括弧、方括弧和花括弧3種類型的括弧，編寫 一個判別表達式中括弧是否正確配對的函數(shù)。以字符“ #”作為算術(shù)

18、表達式的結(jié) 束符。3、回文是指正讀和反讀均相同的字符序列，如“abba”和“abdba”均是回文， 但“good”不是回文。試寫一個算法判定給定的字符串是否回文，該字符串是從 鍵盤讀入的（提示：將一半字符入棧）。4、如果用一個循環(huán)數(shù)組 qnum表示隊列時，該隊列只有一個頭指針 front指向 隊首元素，不設(shè)隊尾rear，而設(shè)置計數(shù)器count用以記錄隊列中結(jié)點的個數(shù)。編寫實現(xiàn)隊歹列的 5 個基本運算的算法：InitQueue，Emptyq，GetHead，EnQueue， OutQueue。提示算法的思想：依照題意，可以得出以下條件：隊列為空：count=0;隊歹歹為滿：count=num;隊列尾元素的下一位置（即新入隊元素位置）：（front+count）%num;出隊時新的隊列首元素的位置：（front+1）%num;5、在一個循環(huán)隊列中，設(shè)計一個標志flag用于標識是否為空