太原理工大學數據結構試題庫及答案

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

2、2n+n +8),其時間復雜度表示( D. O(log 2n) 11、抽象數據類型的三個組成部分分別為（ A.數據對象、數據關系和基本操作 C.數據項、數據元素和數據類型 2 C. 0(n ) A ) B. C 2n) D. 數據元素、邏輯結構和存儲結構 數據元素、數據結構和數據類型 1歡迎下載 二、填空題 三、綜合題 1將數量級 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. 數據結構被形式地定義為（D, R）

3、，其中D是數據元素 的有限集合,R是D上的關系 有限集合。 2. 數據結構包括數據的 邏輯結構、數據的 存儲結構和數據的 運算這三個方面的內容。 順序、鏈式、索引、 3. 數據結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構。 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 五、設有數據邏輯結構 S=( D,R)， 示，并確定其是哪種邏輯結構。 試按各小題所給條件畫出這些邏輯結構的圖 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 的線性表采用順序存儲結構，在其第 i 個位置插入一個新元素算法的時間復 雜度（ ）。 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指針所指的結點后插入一個指針q所指向的新結點，修改指針的 操作是（ 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. 數據元素 D. 數據項 11、 從表中任一結點出發(fā)，都能掃描整個表的是（）。 A. 單鏈表B. 順序表C. 循環(huán)鏈表 D. 靜態(tài)鏈表 12、 在具有n個結點的單鏈表上查找值為x的元素時，其時間復雜度為（）。 2 A. O（n）B. O（1）C. O（n 2）D. O（n-1）

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

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

10、L 5、在一個單鏈表中刪除p所指結點的后繼結點時，應執(zhí)行以下操作： q = p-n ext; p-n ext=_ q-n ext; 三、判斷題 3、 用循環(huán)單鏈表表示的鏈隊列中，可以不設隊頭指針，僅在隊尾設置隊尾指針。x 4、順序存儲方式只能用于存儲線性結構。 5、 在線性表的順序存儲結構中，邏輯上相鄰的兩個元素但是在物理位置上不一定是相鄰的。 6、鏈式存儲的線性表可以隨機存取。 四、程序分析填空題 1、函數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、函數實現(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、函數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、函數實現(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)帶頭結點單鏈

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、 設一個帶頭結點的單向鏈表的頭指針為head，設計算法，將鏈表的記錄，按照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 不帶頭結點的單鏈表改造為一個單向循環(huán)鏈表，并分析 算法的時間復雜度。 答案： void linklist_c(Lnode *head) Lnode *p; p=head; if(!p) return ERROR; while(p-next!=NULL) p=p-next; p-next=head; 設單鏈表的長度(數據結點數)為 N,則該算法的時間主要花費在查找鏈表最后一個結點上 (算法中的 while 循環(huán))，所以該算法的時間復雜度為O( N)。 5、已知head為帶頭結點的單循環(huán)鏈表的頭指

17、針，鏈表中的數據元素依次為(al , a2,a3,a4,an ) ,A為指向空的順序表的指針。閱讀以下程序段，并回答問題： (1) 寫出執(zhí)行下列程序段后的順序表A中的數據元素； (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)單鏈表中偶數結點位置的元素值寫入順序表 A 6、 設順序表va中的數據元數遞增有序

18、。試寫一算法，將x插入到順序表的適當位置上，以 保持該表的有序性。 答案： 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、假設線性表采用順序存儲結構，表中元素值為整型。閱讀算法f2 ,設順序表 L=(3,7,3,2,1,1,8,7,3),寫出執(zhí)行算法f2后的線性表L的數據元素，并描述該算法的功能。 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) 刪除順序表中重復的元素 8、已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結構。試寫一算法，刪除表 中所有大于 x 且小于 y 的元素(若表中存在這樣的元素)同時釋放被刪除結點空間。 答案： 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、在帶頭結點的循環(huán)鏈表 L 中，結點的數據元素為整型，且按值遞增有序存放。給定兩個 整數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、設計一個判別表達式中括號是否配對的算法，采用（ A

21、. 順序表B. 鏈表C. 隊列 4、帶頭結點的單鏈表head為空的判定條件是（）。 A. head=NULL C. head-next!=NULL 5、一個棧的輸入序列為： A. 1243 B. 2134 ）數據結構最佳。 D. 棧 B. head-next=NULL D. head!=NULL 1,2,3,4 ，則棧的不可能輸出的序列是（ C. 1432D. 4312 rear 和 front rear 和 front 的值分別為（ 和4 6、若用一個大小為 6的數組來實現(xiàn)循環(huán)隊列，且當 中刪除一個元素，再加入兩個元素后， A. 1 和5B. 2 隊列的插入操作是在（ ）。 A. 隊尾B.

22、隊頭 循環(huán)隊列的隊頭和隊尾指針分別為 C. 4 和2 ）。 E. 3214 的值分別為 0， 3。當從隊列 ）。 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 、將遞歸算法轉換成對應的非遞歸算法時，通常需要使用（ A. 隊列B. 棧C. 鏈表 12、棧的插入和刪除操作在（ 9、 ）。 D. 隊頭元素后 ）。 D. -+*abcd ） D. 來保存中間結果。 樹 指定位置 ）。 A. 棧底B. 棧頂C. 任意位置 13、五節(jié)車廂以編號 1 ， 2， 3， 4， 5順序進入鐵路調度站（棧） 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、個結點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、正常情況下，刪除非空的順序存儲結構的堆棧的棧頂元素， 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 精品文檔 ）數據結構最佳。 D.線性表的鏈式存儲 20、設計一個判別表達式中左右括號是否配對出現(xiàn)的算法，采用（ A.線性表的順序存儲結構B.隊列 C.棧 結構 21、當用大小為N的數組存儲順序循環(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)隊列