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

1、緒論1.1單項(xiàng)選擇題數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中,數(shù)據(jù)元素的、數(shù)據(jù)信息在計(jì)算機(jī)中的以及一組相關(guān)的運(yùn)算等的課程。A.操作對(duì)象B 計(jì)算方法C .邏輯結(jié)構(gòu)D .數(shù)據(jù)映象A.存儲(chǔ)結(jié)構(gòu)B.關(guān)系C.運(yùn)算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ù)對(duì)象A.操作B.映象C.存儲(chǔ)D.關(guān)系在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分 。動(dòng)態(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)算法分析的目的是，算法分析的兩個(gè)主要方面是A.找出數(shù)據(jù)結(jié)

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

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

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

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

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

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

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

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

10、針p指向某結(jié)點(diǎn)，不知道頭 指針，能否將結(jié)點(diǎn)*?從相應(yīng)的鏈表中刪除？若可以，其時(shí)間復(fù)雜度各為多少？四、算法閱讀題讀下面的程序段，畫出執(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)鏈表中兩個(gè)節(jié)點(diǎn)*/BB(pa,pb);BB(pb,pa);五、算法設(shè)計(jì)題1、分別編寫在順序表和帶頭結(jié)點(diǎn)的單鏈表上統(tǒng)計(jì)出值為x的元素個(gè)數(shù)的算法， 統(tǒng)計(jì)結(jié)果由函數(shù)值返回。2、設(shè)線性表存放于順序表A中，其中有n個(gè)元素，且遞減有序，請(qǐng)?jiān)O(shè)計(jì)一算法， 將x插入到線性表的適當(dāng)位置，以保持線性表的有序性。3、已知兩個(gè)單鏈表A和B，指向頭結(jié)點(diǎn)的指針分別為L(zhǎng)a和Lb，試編寫一個(gè)算 法從單鏈表A中刪除自第i個(gè)

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

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

14、為 0 1n一1（a，,a , a ）。11、設(shè)頭指針為head，并設(shè)帶頭結(jié)點(diǎn)單鏈表中的數(shù)據(jù)元素遞增有序，編寫算法將 數(shù)據(jù)元素x插入到帶頭結(jié)點(diǎn)單鏈表的適當(dāng)位置上，要求插入后保持單鏈表數(shù)據(jù)元 素的遞增有序。12、設(shè)head為單鏈表的頭指針，并設(shè)單鏈表帶有頭結(jié)點(diǎn)，編寫算法將單鏈表中 的數(shù)據(jù)元素按照元素值遞增有序的順序就地排序。13、編寫不帶頭結(jié)點(diǎn)單鏈表的初始化操作、插入操作和刪除操作。第三章基礎(chǔ)知識(shí)一、選擇題1、棧的插入和刪除操作在（）進(jìn)行。A、棧頂B、棧底C、任意位置D、指定位置2、若已知一個(gè)棧的入棧序列是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、線性表、棧和隊(duì)列都是（）結(jié)構(gòu)，可以在線性表的（）位置插入 和刪除元素；對(duì)于棧只能在（）插入和刪除元素；對(duì)于隊(duì)列只能在（）插 入元素和在（）刪除元素。2、對(duì)于一個(gè)順序棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為（），作退棧運(yùn)算時(shí)， 應(yīng)先判別棧是否為（）

16、，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明 棧的可用最大容量為（）。3、設(shè)有一個(gè)空棧，現(xiàn)有輸入序列1， 2， 3， 4， 5，經(jīng)過push，push，pop，push，pop，push，push 后，輸出序列是（）。4、無論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來說，進(jìn)行插入或刪除操作 的時(shí)間復(fù)雜度均相同為（）。5、 有一個(gè)循環(huán)隊(duì)列，分配到的存儲(chǔ)空間大小為n，則其隊(duì)滿條件是（），隊(duì)列為空的條件是（）。三、應(yīng)用題1、若依次讀入數(shù)據(jù)元素序列a,b,c,d進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出 各種可能的出棧元素序列。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è)計(jì)題1、有兩個(gè)棧si和s2共享存儲(chǔ)空間cm（下標(biāo)為0,.,m-1），其中一個(gè)棧底設(shè)在 c0處，另一個(gè)棧底設(shè)在cm-1處，分別編寫si和s2的進(jìn)棧 Push（i,x）、出棧 Pop（i,x） 和設(shè)置棧空Setnull（i）的函數(shù)，其中i=1,2。注意：僅當(dāng)整個(gè)空間c占滿時(shí)才產(chǎn)生 上溢。2、假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧3種類型的括弧，編寫 一個(gè)判別表達(dá)式中括弧是否正確配對(duì)的函數(shù)。以字符“ #”作為算術(shù)

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