數(shù)據(jù)結(jié)構(gòu)期中試卷信息112015

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)嘉興學(xué)院試卷 20122013 學(xué)年第1 學(xué)期期中考試試卷課程名稱：數(shù)據(jù)結(jié)構(gòu) 使用班級(jí)：信息11級(jí) 考試形式：開卷 試卷代碼：班級(jí)： 姓名： 學(xué)號(hào)： 題號(hào)一二三四五六七八總分得分評(píng)閱人一、單項(xiàng)選擇題(在每小題的四個(gè)備選答案中，選出一個(gè)正確答案，并將正確答案的序號(hào)填在題干的括號(hào)內(nèi)。每小題1分，共10分)1數(shù)據(jù)的邏輯結(jié)構(gòu)從形式上可用二元組（D，R）表示，其中R是（ D ） 的有限集。 A算法 B數(shù)據(jù)元素 C數(shù)據(jù)操作 D數(shù)據(jù)關(guān)系2數(shù)據(jù)結(jié)構(gòu)課程研究的內(nèi)容涉及到三個(gè)方面的內(nèi)容，它

2、們分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的（ C ）和數(shù)據(jù)的操作。 A數(shù)據(jù)元素 B邏輯結(jié)構(gòu) C存儲(chǔ)結(jié)構(gòu) D計(jì)算方法3線性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種（ A ）的存儲(chǔ)結(jié)構(gòu)。 A順序存取 B隨機(jī)存取 C索引存取 D散列存取4線性表L在（ B ） 情況下，最適合采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來實(shí)現(xiàn)算法。 A不需經(jīng)常對L進(jìn)行修改 B需經(jīng)常對L進(jìn)行刪除和插入操作 C需經(jīng)常修改L中結(jié)點(diǎn)值 DL中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜5在一個(gè)含有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，使單鏈表仍然保持有序的算法的時(shí)間復(fù)雜度是（ C ） 。O(1) B. O(log2n) C. O(n) D. O(n2)6在循環(huán)順序隊(duì)列中，假

3、設(shè)以設(shè)置一個(gè)計(jì)數(shù)變量num的方法來區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則下面不是隊(duì)列判滿或判空條件是（ A ）。 Afront=rear B. front= =rear & num=0C. front= =rear & num0 D. num= =maxSize7一個(gè)棧的入棧序列是a, b, c, d, e, 則棧的不可能的出棧序列是 （ D ）。 Aabcde Bdecba Cedcba Ddceab8在順序棧中，若棧頂指針top指向棧頂元素的下一個(gè)存儲(chǔ)單元，且順序棧的最大容量

4、是maxSize。則順序棧的判滿的條件是（ C ）。 Atop = =0 B.top= =-1 C. top = =maxSize D.top = = maxSize-19設(shè)線性表有n個(gè)元素，嚴(yán)格說來，以下操作中，（ B ）在順序表上實(shí)現(xiàn)比鏈表上實(shí)現(xiàn)比鏈表上實(shí)現(xiàn)效率更高。 輸出第i個(gè)（0in-1）數(shù)據(jù)元素的值 交換第3個(gè)數(shù)據(jù)元素與第4個(gè)數(shù)據(jù)元素的值 順序輸出這n個(gè)數(shù)據(jù)元素的值A(chǔ) B、 C、 D、10. 在一個(gè)單鏈表中的p和q兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)，假設(shè)新結(jié)點(diǎn)為s,則修改鏈的Java語句序列是（ D ）。As.setNext(p); q.setNext(s); B. p.setNext(s.

5、getNext(); s.setNext(p);C. q.setNext(s.getNext(); s.setNext(p); D. p.setNext(s); s.setNext(q);二、填空題（20分，每空1分）1算法的復(fù)雜度通常體現(xiàn)為 時(shí)間復(fù)雜度 和空間復(fù)雜度兩個(gè)指標(biāo)。2設(shè)有函數(shù)T (n)=3n2-n+4， T (n)=O ( n )。3要將一個(gè)順序表a0,a1,an-1中第i個(gè)數(shù)據(jù)元素ai(0in-1)刪除，會(huì)引起 n-1-i 個(gè)數(shù)據(jù)元素的移動(dòng)。4隊(duì)列也是一種操作受限的線性表，它與棧不同的是，隊(duì)列中所有的插入操作均限制在表的一端進(jìn)行，而所有的刪除操作都限制在表的另一端進(jìn)行，允許插入的

6、一端稱為 隊(duì)尾 ，允許刪除的一端稱為 隊(duì)首 。隊(duì)列具有 先進(jìn)先出 的特點(diǎn)。5在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：q=p.getNext(); p.setData(q.getData();p.setNext( q.getNext() );6設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出棧的序列是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是 3 。7若雙向鏈表的結(jié)點(diǎn)類描述為：public class DuLNode pvivate Object data; private DuLNode piror

7、; private DuLNode next; 則在帶頭結(jié)點(diǎn)的雙向鏈表中的p結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)s，其修改指針的java語句序列是： 1） p.getPiror().setNext(s); 2） s.setPiror(p.gettPiror(); 3） s.setNext(p); 4） p.setPiror(s); 8在不帶表頭結(jié)點(diǎn)的鏈棧中，棧頂指針top直接指向棧頂元素，如果鏈棧中結(jié)點(diǎn)的類描述為： class Node private Object data; private Node next: 則將一個(gè)新結(jié)點(diǎn)p入棧時(shí)修改鏈的兩個(gè)對應(yīng)語句是： 1） p.setNext(top); 2）

8、top=p; 9如果循環(huán)順序隊(duì)列類的描述如下： class CircleSqQueeu pvivate Object queueElem; /隊(duì)列的存儲(chǔ)空間 pvivate int front; pvivate int rear; 假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來區(qū)分隊(duì)列判滿和判空的條件，其中front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的長度是 (rear-front+queueElem.length)%queueElem.length 。10在順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)這4種存儲(chǔ)方式中，最基本、

9、最常用的兩種存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ) 和 鏈?zhǔn)酱鎯?chǔ) 。11按數(shù)據(jù)元素的邏輯關(guān)系來系，數(shù)據(jù)結(jié)構(gòu)可分為四種：線性表、集合、樹和圖。其中圖型結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“ 多對多 ”的關(guān)系 。 12. 棧元素存儲(chǔ)在數(shù)組stackElem中，假設(shè)棧頂指針top是指向棧頂元素的下一個(gè)存儲(chǔ)單元，則順序棧判空的條件是 top= =0 ；棧頂元素的訪問形式是 stackElemtop-1 。三、判斷題（共10分，2分1題，對的打“”，錯(cuò)的打“”）1. 線性表中數(shù)據(jù)元素的邏輯順序與存儲(chǔ)順序總是一致的。 （ ）2鏈?zhǔn)酱鎯?chǔ)時(shí)，存儲(chǔ)區(qū)域可以連續(xù)，也可以不連續(xù)。 （ ）3刪除順序表中第0個(gè)數(shù)據(jù)元素a0的時(shí)間復(fù)雜度是O(n)。 （

10、 ）4判斷一個(gè)鏈棧為空的條件件是表達(dá)式 top= =null的值為真。 （ ）5雙向循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。 （ ）四、應(yīng)用與計(jì)算題（共26分）求下列程序段的時(shí)間復(fù)雜度。（9分）for (i=0; in; i+) for (j=0; ji; j+) Aij=0; 時(shí)間復(fù)雜度是：O(n)a=0;b=1;for (i=0;i=n; i+) s=a+b; b=a; a=s; 時(shí)間復(fù)雜度是：O(n)a=1; m=1; while(an) m+=a; a*=3; 時(shí)間復(fù)雜度是：O(log3n)2. 設(shè)有數(shù)據(jù)的邏輯結(jié)構(gòu)的二元組定義形式為B=(D,R)，其中D=a0,a1,an-1

11、，R=| i=0,1,，n-2，請畫出此邏輯結(jié)構(gòu)對應(yīng)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的示意圖。(共6分) a0a1ai-2ai-1an-1a1a0a2an-1 3對線性表A=（11, 22, 33, 44,55），畫出下列存儲(chǔ)結(jié)構(gòu)的示意圖： （共6分）（1）帶表頭結(jié)點(diǎn)的單鏈表；（2）不帶表頭結(jié)點(diǎn)的單向循環(huán)鏈表；（3）帶表結(jié)點(diǎn)的雙向循環(huán)鏈表。112255 3344head112255 3344head 22 33 44 55 11head4. 建立鏈棧的基本思想是從空棧開始依次將入棧元素結(jié)點(diǎn)插入到棧頂。假設(shè)依次入棧的元素為23、17、28、69、11，請畫出將各元素結(jié)點(diǎn)分別入棧后的鏈棧示意圖。（5分

12、）top23 top1723 top281723 top69281723 top23 11692817根據(jù)以下各題的要求，分別寫出相應(yīng)的算法（用Java語言描述）。（共34分）編寫一個(gè)順序表類的成員函數(shù)，實(shí)現(xiàn)對順序表就地逆置的操作。（8分） 已知順序表類的描述為：class SqList private Object listElem; privat int curLen; 參考答案：（方法不唯一）public void nizhi(SqList L) Object temp; for(int i=0;icurLen/2;i+) temp=listElemi; listElemi=listEl

13、emcurLen-i-1; listElemcurLen-i-1=temp; 2編寫一個(gè)單鏈表類的成員函數(shù)，實(shí)現(xiàn)在非遞減的有序單鏈表中插入一個(gè)整數(shù)值為x的數(shù)據(jù)元素，并使單鏈表仍保持有序的操作。（8分）已知單鏈表中的結(jié)點(diǎn)類和單鏈表類分別描述如下：class Node /鏈表中的結(jié)點(diǎn)類 private Object data; private Node next;public Node(Object data) /構(gòu)造函數(shù)：構(gòu)造一個(gè)數(shù)據(jù)域值為data為結(jié)點(diǎn) this.data=data; this.next=null; clsss LinkList() /單鏈表類 private Node hea

14、d; 參考答案：（方法不唯一） public void charu(int x) Node p=head.getNext(); Node q=head; int temp; while(p!=null) temp=(Integer)p.getData().intValue(); if(tempx) q=p; p=p.getNext(); else break; Node s=new Node(x); s.setNext(p); q.setNext(s); 3編寫一個(gè)函數(shù)判斷一個(gè)字符序列是否為回文序列，所謂回文序列就是正讀與反讀都相同的字符序列，例、如：abba和abdba均是回文序列。要求只借

15、助棧來實(shí)現(xiàn)。參考答案：（方法不唯一）public Boolean isPalindSeq(String str) LinkStack s=new LinkStack; for(int i=0;istr.length();i+) s.push(str.charAt(i); for(int i=0;istr.length();i+) char c=(Character)S.pop().charValue(); if(c!=str.charAt(i) return false; Return true;4. 假設(shè)采用帶頭結(jié)點(diǎn)的循環(huán)鏈表來表示隊(duì)列，并且只設(shè)一個(gè)指向隊(duì)尾元素的指針（不設(shè)隊(duì)首指針），試編寫相應(yīng)的隊(duì)列置空、隊(duì)列判空、入隊(duì)和出隊(duì)操作的成員函數(shù)。（10分）已知用隊(duì)尾指針標(biāo)識(shí)的循環(huán)鏈隊(duì)列的類描述如下:class CircleLinkQueue private Node rear;/ 循環(huán)鏈隊(duì)列的尾指針 參考答案：（方法不唯一）隊(duì)列置空： public void clear() rear.setNext(rear);隊(duì)列判空：public Boolean isEmpty() return rear=rear.getNext();入隊(duì)操作： void offer ( Object x) Node p= new Node(x); p.setNext(