




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、精品文檔 數(shù)據(jù)結(jié)構(gòu)試題庫及答案 第一章概論 一、選擇題 1研究數(shù)據(jù)結(jié)構(gòu)就是研究(D A.數(shù)據(jù)的邏輯結(jié)構(gòu) C.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 2、算法分析的兩個主要方面是( A.空間復(fù)雜度和時間復(fù)雜度 C.可讀性和文檔性 具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是( A.圖B.樹 算法是(D )。 A計算機程序 D解決問題的有限運算序列 某算法的語句執(zhí)行頻度為( A. 0(n)B. O(nlog 3、 6、 7、 B. D. )。 D. )。 C. 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本操作 B.正確性和簡單性 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 廣義表 D.棧 B.解決問題的計算方法 C.排序算法 2 3n+nlog
2、2n+n +8),其時間復(fù)雜度表示( D. O(log 2n) 11、抽象數(shù)據(jù)類型的三個組成部分分別為( A.數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作 C.數(shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型 2 C. 0(n ) A ) B. C 2n) D. 數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型 1歡迎下載 二、填空題 三、綜合題 1將數(shù)量級 0,O(N),O(N 2),0(N 3),O(NLOGN),O(LOGN),O(2 )按增長率由小到大排序。 答案: O O(log 2N) O(N) O(Nlog2N) O(N 2) O(N 3) O(2 N) 一、填空題 1. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D, R)
3、,其中D是數(shù)據(jù)元素 的有限集合,R是D上的關(guān)系 有限集合。 2. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu)、數(shù)據(jù)的 存儲結(jié)構(gòu)和數(shù)據(jù)的 運算這三個方面的內(nèi)容。 順序、鏈式、索引、 3. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類,它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 ivn; i+) for (j=0; jvm; j+) Aij=0; 2.s=0; for (i=0; ivn; i+) for(j=0; jvn; j+) s+=Bij; sum=s; 3.x=0; for(i=1; ivn; i+) for (j=1; jv=n-i; j+) x+; 4.i=1; while(iv=n) i=i*3; Mn nn nn I
4、og3 n 五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu) S=( D,R), 示,并確定其是哪種邏輯結(jié)構(gòu)。 試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖 1. D=d1,d2,d3,d4R=(d1,d2),(d2,d3),(d3,d4) 2.D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 3. D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6) 第二章 線性表 一
5、、選擇題 1 、若長度為 n 的線性表采用順序存儲結(jié)構(gòu),在其第 i 個位置插入一個新元素算法的時間復(fù) 雜度( )。 2 A. O(log 2n)B.O(1)C. O(n)D.O(n 2) 2、若一個線性表中最常用的操作是取第i 個元素和找第 i 個元素的前趨元素, 則采用( ) 存儲方式最節(jié)省時間。 A. 順序表B. 單鏈表C. 雙鏈表D. 單循環(huán)鏈表 7、在雙向循環(huán)鏈表中,在p指針所指的結(jié)點后插入一個指針q所指向的新結(jié)點,修改指針的 操作是( c )。 A. p-next=q;q-prior=p;p-next-prior=q;q-next=q; B. p-next=q;p-next-prio
6、r=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; 10、 線性表是門個()的有限序列。 A. 表元素B. 字符 C. 數(shù)據(jù)元素 D. 數(shù)據(jù)項 11、 從表中任一結(jié)點出發(fā),都能掃描整個表的是()。 A. 單鏈表B. 順序表C. 循環(huán)鏈表 D. 靜態(tài)鏈表 12、 在具有n個結(jié)點的單鏈表上查找值為x的元素時,其時間復(fù)雜度為()。 2 A. O(n)B. O(1)C. O(n 2)D. O(n-1)
7、15、 在線性表的下列存儲結(jié)構(gòu)中,讀取元素花費的時間最少的是()。 A. 單鏈表 B. 雙鏈表 C. 循環(huán)鏈表D. 順序表 16、 在一個單鏈表中,若刪除p所指向結(jié)點的后續(xù)結(jié)點,則執(zhí)行()。 A. 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ù)雜度為()。 A. O(1) B. O(n) C. O(m) D. O(m+n) N D. 散列存取 18、線性表的順序存儲結(jié)構(gòu)是一種(a )存儲結(jié)構(gòu)。 A. 隨機存取
8、 B. 順序存取 C. 索引存取 19、順序表中,插入一個元素所需移動的元素平均數(shù)是()。 A. (n-1)/2B. nC. n+1D. (n+1)/2 11、不帶頭結(jié)點的單鏈表 head 為空的判定條件是( b )。 A. head=NULL B. head-next=NULL D. head!=NULL 0(1)的是()。 C. head-next=head 12、在下列對順序表進行的操作中,算法時間復(fù)雜度為 A.訪問第i個元素的前驅(qū)(1汕) B.在第i個元素之后插入一個新元素 (1 next=s-next; s-next=p ; B. s-next=p ; q-next=s-next ;
9、 C. p-next=s-next; s-next=q ; D. s-next=q ; p-next=s-next ; 15、在表長為n的順序表中,當(dāng)在任何位置刪除一個元素的概率相同時,刪除一個元素所需 移動的平均個數(shù)為(a )。 A. (n-1)/2B. n/2C. (n +1)/2D. n 二、填空題 1、設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next )。已知指針p指向單鏈表中的結(jié)點,q指向新結(jié)點, 欲將q插入到p結(jié)點之后,則需要執(zhí)行的語句: ; 。 答案:q-n ext=p-n extp-n ext=q 3、寫出帶頭結(jié)點的雙向循環(huán)鏈表L為空表的條件 。 答案:L-prior=L-n ext=
10、L 5、在一個單鏈表中刪除p所指結(jié)點的后繼結(jié)點時,應(yīng)執(zhí)行以下操作: q = p-n ext; p-n ext=_ q-n ext; 三、判斷題 3、 用循環(huán)單鏈表表示的鏈隊列中,可以不設(shè)隊頭指針,僅在隊尾設(shè)置隊尾指針。x 4、順序存儲方式只能用于存儲線性結(jié)構(gòu)。 5、 在線性表的順序存儲結(jié)構(gòu)中,邏輯上相鄰的兩個元素但是在物理位置上不一定是相鄰的。 6、鏈式存儲的線性表可以隨機存取。 四、程序分析填空題 1、函數(shù)GetElem實現(xiàn)返回單鏈表的第i個元素,請在空格處將算法補充完整。 int GetElem(LinkList L,int i,Elemtype *e) LinkList p ; int
11、j ; p=L-n ext;j=1; while(p+j; if(!p|ji) return ERROR; *e=p-data ;_ return OK; 2、函數(shù)實現(xiàn)單鏈表的插入算法,請在空格處將算法補充完整。 int List In sert(L in kList L,i nt i,ElemType e) 精品文檔 LNode *p,*s;i nt j; p=L;j=O; while(p!=NULL) j+; if(p=NULL|ji-1) return ERROR; s=(LNode *)malloc(sizeof(LNode); s-data=e; s-n ext=p-n ext ;
12、p-next=s ; return OK; /*Listl nsert*/ 3、函數(shù)ListDelete_sq 實現(xiàn)順序表刪除算法,請在空格處將算法補充完整。 int ListDelete_sq(Sqlist *L,int i) int k; if(iL-length) return ERROR; for(k=i-1;kle ngth-1;k+) L-slistk= L-slistk+1 ;_ -L-Le ngth; return OK; 4、函數(shù)實現(xiàn)單鏈表的刪除算法,請在空格處將算法補充完整。 int ListDelete(LinkList L,int i,ElemType *s) LNod
13、e *p,*q; int j; p=L;j=0; while( p-next!=NULL _)j+; if(p-n ext=NULL|ji-1) return ERROR; q=p-n ext; p-n ext=q-n ext; *s=q-data; free(q); return OK; /*listDelete*/ 5、寫出算法的功能。 int L(head) node * head; int n=0; node *p; p=head; while(p!=NULL) p=p-n ext; n+; return(n); 答案:求單鏈表head的長度 五、綜合題 1、編寫算法,實現(xiàn)帶頭結(jié)點單鏈
14、表的逆置算法。 答案: 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(Lnode *L1, Lnode *L2) Lnode *p,*q ; while(p-next!=L1)
15、 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=r; p=r; else while(!p p=p-next; r-ne
16、xt=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)),所以該算法的時間復(fù)雜度為O( N)。 5、已知head為帶頭結(jié)點的單循環(huán)鏈表的頭指
17、針,鏈表中的數(shù)據(jù)元素依次為(al , a2,a3,a4,an ) ,A為指向空的順序表的指針。閱讀以下程序段,并回答問題: (1) 寫出執(zhí)行下列程序段后的順序表A中的數(shù)據(jù)元素; (2) 簡要敘述該程序段的功能。 if(head-n ext!=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é)點位置的元素值寫入順序表 A 6、 設(shè)順序表va中的數(shù)據(jù)元數(shù)遞增有序
18、。試寫一算法,將x插入到順序表的適當(dāng)位置上,以 保持該表的有序性。 答案: void Insert_sq(Sqlist va, ElemType x) int i, j, n; n=length(va); if(x=vai) van=x; else i=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(SeqList *L) int
19、 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(!he
20、ad) return ERROR; p=head; q=p; while(!p) if(p-datax) free(p); p=head; q=p; else q-next=p-next; free(p); p=q-next; else q=p; p=p-next; 9、在帶頭結(jié)點的循環(huán)鏈表 L 中,結(jié)點的數(shù)據(jù)元素為整型,且按值遞增有序存放。給定兩個 整數(shù)a和b,且arear=Q-frontB. Q-rear=Q-front+1 C. Q-front=(Q-rear+1)%nD. Q-front=(Q-rear-1)%n 13 歡。迎下載 3、設(shè)計一個判別表達式中括號是否配對的算法,采用( A
21、. 順序表B. 鏈表C. 隊列 4、帶頭結(jié)點的單鏈表head為空的判定條件是()。 A. head=NULL C. head-next!=NULL 5、一個棧的輸入序列為: A. 1243 B. 2134 )數(shù)據(jù)結(jié)構(gòu)最佳。 D. 棧 B. head-next=NULL D. head!=NULL 1,2,3,4 ,則棧的不可能輸出的序列是( C. 1432D. 4312 rear 和 front rear 和 front 的值分別為( 和4 6、若用一個大小為 6的數(shù)組來實現(xiàn)循環(huán)隊列,且當(dāng) 中刪除一個元素,再加入兩個元素后, A. 1 和5B. 2 隊列的插入操作是在( )。 A. 隊尾B.
22、隊頭 循環(huán)隊列的隊頭和隊尾指針分別為 C. 4 和2 )。 E. 3214 的值分別為 0, 3。當(dāng)從隊列 )。 D. 5 和1 7、 8、 front C. 隊列任意位置 和 rear ,則判斷循環(huán)隊列為空的條件是( A. front=rearB. front=0 C. rear=0D. front=rear+1 一個順序棧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
23、. abc*+d- 11 、將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時,通常需要使用( A. 隊列B. 棧C. 鏈表 12、棧的插入和刪除操作在( 9、 )。 D. 隊頭元素后 )。 D. -+*abcd ) D. 來保存中間結(jié)果。 樹 指定位置 )。 A. 棧底B. 棧頂C. 任意位置 13、五節(jié)車廂以編號 1 , 2, 3, 4, 5順序進入鐵路調(diào)度站(棧) A. 3 , 4,5,1,2B. 2 , 4,1,3,5 C. 3 , 5,4,2,1D. 1 , 3,5,2,4 S (??臻g大小為n)為空的條件是( B. S-top!=0 D. S-top!=n 和rear分別為頭指針和尾指針,則插入一
24、個結(jié)點s的操作為( B. s-next=rear;rear=s D. s-next=front;front=s; 1, 2, 3, 4,則隊列的出隊序列是( B. 4 , 3, 2, 1 D. 3 , 4, 1 , 2 a,b,c,d 以后,緊接著做了兩次刪除操作,此時的隊 D. ,可以得到( )的編組。 14、判定一個順序棧 A. S-top=0 C. S-top=n 15、在一個鏈隊列中, front A. front=front-next C. rear-next=s;rear=s; 16、一個隊列的入隊序列是 A. 1 ,2,3, 4 C. 1 ,4,3, 2 17、依次在初始為空的隊
25、列中插入元素 頭元素是( )。 A. a B. b C. c 18、正常情況下,刪除非空的順序存儲結(jié)構(gòu)的堆棧的棧頂元素, A. top 不變 B. top=0 C. top=top+1 19、判斷一個循環(huán)隊列Q (空間大小為 M為空的條件是 )。 )。 )。 D. d 棧頂指針 top 的變化是( D. top=top-1 )。 )。 A. Q-front=Q-rearB. Q-rear-Q-front-1=M C. Q-front+1=Q-rear D. Q-rear+1=Q-front 精品文檔 )數(shù)據(jù)結(jié)構(gòu)最佳。 D.線性表的鏈式存儲 20、設(shè)計一個判別表達式中左右括號是否配對出現(xiàn)的算法,采用( A.線性表的順序存儲結(jié)構(gòu)B.隊列 C.棧 結(jié)構(gòu) 21、當(dāng)用大小為N的數(shù)組存儲順序循環(huán)隊列時,該隊列的最大長度為()。 A. NB. N+1C. N-1D. N-2 22、隊列的刪除操作是在()。 A.隊首B.隊尾C.隊前D.隊后 23、 若讓元素1,2,3依次進棧,則出棧次序不可能是()。 A. 3,2,1 B.2,1,3 C. 3,1,2 D.1 , 3, 2 24、循環(huán)隊列
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 物業(yè)管理新人培訓(xùn)心得體會
- 重癥監(jiān)護有創(chuàng)血壓監(jiān)測流程他
- 基層婦幼工作站出生缺陷防控管理制度與措施他
- 河道養(yǎng)護管理施工方案與技術(shù)措施
- 2025年教導(dǎo)處學(xué)生安全計劃
- 護理創(chuàng)新思維培養(yǎng)培訓(xùn)計劃
- 學(xué)校教科研評價體系心得體會
- 制造業(yè)銷售年終總結(jié)與計劃
- IT運維崗位KPI績效考核表及工作職責(zé)
- 新人教版四年級英語口語教學(xué)計劃
- 國家開放大學(xué)《藥物治療學(xué)(本)》形考作業(yè)1-4參考答案
- 基于深度學(xué)習(xí)的光學(xué)圖像海面艦船目標智能檢測與識別技術(shù)探究
- 一年級家長心理輔導(dǎo)課件
- DB50-T 1808-2025“一表通”智能報表市級業(yè)務(wù)數(shù)據(jù)規(guī)范
- 《太陽能電池片制造培訓(xùn)》課件
- 特殊飲食情況的案例討論試題及答案
- 深圳輔警考試試卷真題及答案
- 收樓驗房知識培訓(xùn)課件
- 林草行業(yè)安全生產(chǎn)
- 防中暑課件部隊
- 《洗紅領(lǐng)巾》(教案)-2024-2025學(xué)年二年級上冊勞動蘇科版
評論
0/150
提交評論