太原理工大學(xué)數(shù)據(jù)結(jié)構(gòu)試題庫(kù)及答案

1、精品文檔 數(shù)據(jù)結(jié)構(gòu)試題庫(kù)及答案 第一章概論 一、選擇題 1研究數(shù)據(jù)結(jié)構(gòu)就是研究（D A.數(shù)據(jù)的邏輯結(jié)構(gòu) C.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) 2、算法分析的兩個(gè)主要方面是（ A.空間復(fù)雜度和時(shí)間復(fù)雜度 C.可讀性和文檔性 具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ A.圖B.樹 算法是（D ）。 A計(jì)算機(jī)程序 D解決問題的有限運(yùn)算序列 某算法的語(yǔ)句執(zhí)行頻度為（ A. 0（n）B. O（nlog 3、 6、 7、 B. D. )。 D. )。 C. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其基本操作 B.正確性和簡(jiǎn)單性 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 廣義表 D.棧 B.解決問題的計(jì)算方法 C.排序算法 2 3n+nlog

2、2n+n +8),其時(shí)間復(fù)雜度表示( D. O(log 2n) 11、抽象數(shù)據(jù)類型的三個(gè)組成部分分別為（ A.數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系和基本操作 C.數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型 2 C. 0(n ) A ) B. C 2n) D. 數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型 1歡迎下載 二、填空題 三、綜合題 1將數(shù)量級(jí) 0,O(N),O(N 2),0(N 3),O(NLOGN),O(LOGN),O(2 )按增長(zhǎng)率由小到大排序。 答案： 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ù)的 存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的 運(yùn)算這三個(gè)方面的內(nèi)容。 順序、鏈?zhǔn)?、索引?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 、若長(zhǎng)度為 n 的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第 i 個(gè)位置插入一個(gè)新元素算法的時(shí)間復(fù) 雜度（ ）。 2 A. O（log 2n）B.O（1）C. O（n）D.O（n 2） 2、若一個(gè)線性表中最常用的操作是取第i 個(gè)元素和找第 i 個(gè)元素的前趨元素， 則采用（ ） 存儲(chǔ)方式最節(jié)省時(shí)間。 A. 順序表B. 單鏈表C. 雙鏈表D. 單循環(huán)鏈表 7、在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)指針q所指向的新結(jié)點(diǎn)，修改指針的 操作是（ 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、 線性表是門個(gè)（）的有限序列。 A. 表元素B. 字符 C. 數(shù)據(jù)元素 D. 數(shù)據(jù)項(xiàng) 11、 從表中任一結(jié)點(diǎn)出發(fā)，都能掃描整個(gè)表的是（）。 A. 單鏈表B. 順序表C. 循環(huán)鏈表 D. 靜態(tài)鏈表 12、 在具有n個(gè)結(jié)點(diǎn)的單鏈表上查找值為x的元素時(shí)，其時(shí)間復(fù)雜度為（）。 2 A. O（n）B. O（1）C. O（n 2）D. O（n-1）

7、15、 在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)的時(shí)間最少的是（）。 A. 單鏈表 B. 雙鏈表 C. 循環(huán)鏈表D. 順序表 16、 在一個(gè)單鏈表中，若刪除p所指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(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、將長(zhǎng)度為n的單鏈表連接在長(zhǎng)度為 m的單鏈表之后的算法的時(shí)間復(fù)雜度為（）。 A. O(1) B. O(n) C. O(m) D. O(m+n) N D. 散列存取 18、線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（a ）存儲(chǔ)結(jié)構(gòu)。 A. 隨機(jī)存取

8、 B. 順序存取 C. 索引存取 19、順序表中，插入一個(gè)元素所需移動(dòng)的元素平均數(shù)是（）。 A. （n-1）/2B. nC. n+1D. （n+1）/2 11、不帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是（ b ）。 A. head=NULL B. head-next=NULL D. head!=NULL 0（1）的是（）。 C. head-next=head 12、在下列對(duì)順序表進(jìn)行的操作中，算法時(shí)間復(fù)雜度為 A.訪問第i個(gè)元素的前驅(qū)(1汕) B.在第i個(gè)元素之后插入一個(gè)新元素 (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、在表長(zhǎng)為n的順序表中，當(dāng)在任何位置刪除一個(gè)元素的概率相同時(shí)，刪除一個(gè)元素所需 移動(dòng)的平均個(gè)數(shù)為(a )。 A. (n-1)/2B. n/2C. (n +1)/2D. n 二、填空題 1、設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next )。已知指針p指向單鏈表中的結(jié)點(diǎn)，q指向新結(jié)點(diǎn)， 欲將q插入到p結(jié)點(diǎn)之后，則需要執(zhí)行的語(yǔ)句： ； 。 答案：q-n ext=p-n extp-n ext=q 3、寫出帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空表的條件 。 答案：L-prior=L-n ext=

10、L 5、在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作： q = p-n ext; p-n ext=_ q-n ext; 三、判斷題 3、 用循環(huán)單鏈表表示的鏈隊(duì)列中，可以不設(shè)隊(duì)頭指針，僅在隊(duì)尾設(shè)置隊(duì)尾指針。x 4、順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。 5、 在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素但是在物理位置上不一定是相鄰的。 6、鏈?zhǔn)酱鎯?chǔ)的線性表可以隨機(jī)存取。 四、程序分析填空題 1、函數(shù)GetElem實(shí)現(xiàn)返回單鏈表的第i個(gè)元素，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。 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ù)實(shí)現(xiàn)單鏈表的插入算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。 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 實(shí)現(xiàn)順序表刪除算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。 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ù)實(shí)現(xiàn)單鏈表的刪除算法，請(qǐng)?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。 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的長(zhǎng)度 五、綜合題 1、編寫算法，實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈

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、 有兩個(gè)循環(huán)鏈表，鏈頭指針分別為L(zhǎng)1和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è)一個(gè)帶頭結(jié)點(diǎn)的單向鏈表的頭指針為head，設(shè)計(jì)算法，將鏈表的記錄，按照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、編寫算法 , 將一個(gè)頭指針為 head 不帶頭結(jié)點(diǎn)的單鏈表改造為一個(gè)單向循環(huán)鏈表，并分析 算法的時(shí)間復(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è)單鏈表的長(zhǎng)度(數(shù)據(jù)結(jié)點(diǎn)數(shù))為 N,則該算法的時(shí)間主要花費(fèi)在查找鏈表最后一個(gè)結(jié)點(diǎn)上 (算法中的 while 循環(huán))，所以該算法的時(shí)間復(fù)雜度為O( N)。 5、已知head為帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指

17、針，鏈表中的數(shù)據(jù)元素依次為(al , a2,a3,a4,an ) ,A為指向空的順序表的指針。閱讀以下程序段，并回答問題： (1) 寫出執(zhí)行下列程序段后的順序表A中的數(shù)據(jù)元素； (2) 簡(jiǎn)要敘述該程序段的功能。 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é)點(diǎn)位置的元素值寫入順序表 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è)線性表采用順序存儲(chǔ)結(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、已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一算法，刪除表 中所有大于 x 且小于 y 的元素(若表中存在這樣的元素)同時(shí)釋放被刪除結(jié)點(diǎn)空間。 答案： 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é)點(diǎn)的循環(huán)鏈表 L 中，結(jié)點(diǎn)的數(shù)據(jù)元素為整型，且按值遞增有序存放。給定兩個(gè) 整數(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è)計(jì)一個(gè)判別表達(dá)式中括號(hào)是否配對(duì)的算法，采用（ A

21、. 順序表B. 鏈表C. 隊(duì)列 4、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。 A. head=NULL C. head-next!=NULL 5、一個(gè)棧的輸入序列為： 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、若用一個(gè)大小為 6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng) 中刪除一個(gè)元素，再加入兩個(gè)元素后， A. 1 和5B. 2 隊(duì)列的插入操作是在（ ）。 A. 隊(duì)尾B.

22、隊(duì)頭 循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為 C. 4 和2 ）。 E. 3214 的值分別為 0， 3。當(dāng)從隊(duì)列 ）。 D. 5 和1 7、 8、 front C. 隊(duì)列任意位置 和 rear ，則判斷循環(huán)隊(duì)列為空的條件是（ A. front=rearB. front=0 C. rear=0D. front=rear+1 一個(gè)順序棧S,其棧頂指針為top，則將元素e入棧的操作是（ A. *S-top=e;S-top+;B. S-top+;*S-top=e; C. *S-top=eD. S-top=e; 10、表達(dá)式 a*（b+c）-d 的后綴表達(dá)式是（ ）。 A. abcd+-B. abc+*d-C

23、. abc*+d- 11 、將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（ A. 隊(duì)列B. 棧C. 鏈表 12、棧的插入和刪除操作在（ 9、 ）。 D. 隊(duì)頭元素后 ）。 D. -+*abcd ） D. 來(lái)保存中間結(jié)果。 樹 指定位置 ）。 A. 棧底B. 棧頂C. 任意位置 13、五節(jié)車廂以編號(hào) 1 ， 2， 3， 4， 5順序進(jìn)入鐵路調(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、個(gè)結(jié)點(diǎn)s的操作為（ B. s-next=rear;rear=s D. s-next=front;front=s; 1， 2， 3， 4，則隊(duì)列的出隊(duì)序列是（ B. 4 ， 3， 2， 1 D. 3 ， 4， 1 ， 2 a,b,c,d 以后，緊接著做了兩次刪除操作，此時(shí)的隊(duì) D. ，可以得到（ ）的編組。 14、判定一個(gè)順序棧 A. S-top=0 C. S-top=n 15、在一個(gè)鏈隊(duì)列中， front A. front=front-next C. rear-next=s;rear=s; 16、一個(gè)隊(duì)列的入隊(duì)序列是 A. 1 ，2，3， 4 C. 1 ，4，3， 2 17、依次在初始為空的隊(duì)

25、列中插入元素 頭元素是（ ）。 A. a B. b C. c 18、正常情況下，刪除非空的順序存儲(chǔ)結(jié)構(gòu)的堆棧的棧頂元素， A. top 不變 B. top=0 C. top=top+1 19、判斷一個(gè)循環(huán)隊(duì)列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.線性表的鏈?zhǔn)酱鎯?chǔ) 20、設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（ A.線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列 C.棧 結(jié)構(gòu) 21、當(dāng)用大小為N的數(shù)組存儲(chǔ)順序循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為（）。 A. NB. N+1C. N-1D. N-2 22、隊(duì)列的刪除操作是在（）。 A.隊(duì)首B.隊(duì)尾C.隊(duì)前D.隊(duì)后 23、 若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能是（）。 A. 3，2，1 B.2，1，3 C. 3，1，2 D.1 ， 3， 2 24、循環(huán)隊(duì)列