2012《數(shù)據(jù)結(jié)構(gòu)》期末試卷(a卷)

《2012《數(shù)據(jù)結(jié)構(gòu)》期末試卷(a卷)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、2012A卷【字號：大中小】2011－2012年春季學(xué)期計算機科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程專業(yè)《數(shù)據(jù)結(jié)構(gòu)》期末試卷（A卷）卷面總分：100分???????答題時間：120分鐘?專業(yè)???????年級????班級?????姓名?????????學(xué)號?????????題號一二三四五六七八九十總分得分???????????一、????????????單項選擇題（本大題共15小題，每小題1分，共15分?答案寫在答題卡上）答題卡?題號123456789101112131415???答案???????????????1.??設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程

2、序片段的時間復(fù)雜度是(???)。?????????????x=2;?????????????while(x0）。??????????A．表元素?????????????B．?dāng)?shù)據(jù)元素????C．字符???????????????D．?dāng)?shù)據(jù)項????????3.?對于順序存儲的線性表

3、，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為(???)。???A.O(n)?O(n)?????????B.O(n)?O(1)????C.O(1)?O(n)??????D.O(1)O(1)4.???設(shè)棧的輸入序列是1，2，3，4,則(???)不可能是其出棧序列。A.1，2，4，3???????B.2，1，3，4???C.1，4，3，2??????D.4，3，1，2???????5.???設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是b,d,c,f,e,a,g，則棧S的容量至

4、少是(???)。A.4????????????????????B.3??????????????C.2?????????????????D.16.為解決計算機主機與打印機之間速度不匹配問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是(???)。A.棧?????????????????B.隊列?????????C.樹????????????????D.串7.???串是一種特殊的線性表，下面哪個敘述體現(xiàn)了這種特殊性(???)。A.可以順序存儲????????????????

5、????????B.數(shù)據(jù)元素是一個字符?C.數(shù)據(jù)元素可以是多個字符???????D.可以鏈接存儲8.已知一棵完全二叉樹的第6層（設(shè)根是第1層）有8個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多是(???)。A.119???????????B.111?????????C.52????????D.399.一個具有1025個結(jié)點的二叉樹的高h為(???)。A．10至1024之間???B．11至1025之間???????????C.10???????D.1110.??設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點

6、的右子樹上的結(jié)點個數(shù)是(???)。A．M1+M2???????????B．M2+M3????????CM3???????????D.M1?11.?設(shè)無向圖的頂點個數(shù)為n，則該圖最多有(???)條邊。?????????????A．n-1?????????????B．n2?????C．n(n+1)/2??????D．n(n-1)/212.若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為(???)。A.(n-1)/2?????????B.n/2??????C.n????????????????D.

7、(n+1)/213.分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是(???)。A.(100,80,90,60,120,110,130)???B.(100,120,110,130,80,60,90)?????????????C.(100,60,80,90,120,110,130)???D.(100,80,60,90,120,130,110)??14.一組記錄的關(guān)鍵字為{46、79、56、38、40、84},則利用快速排序的方法,以第一個記錄為樞軸得到的一次劃分結(jié)果是(???)A.38、40、46、56、79、84???????B.4

8、0、38、46、79、56、84?????????????C.40、38、46、56、79、84??????