2014年韓山師范學(xué)院本科插班生《數(shù)據(jù)結(jié)構(gòu)》試卷.doc

（A卷）第 7 頁 共 7 頁2014年韓山師范學(xué)院本科插班生數(shù)據(jù)結(jié)構(gòu)試卷計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè) 數(shù)據(jù)結(jié)構(gòu) 試卷 （A卷）一、 單項(xiàng)選擇題（每題2分，共40分）1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。A動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C線性結(jié)構(gòu)、非線性結(jié)構(gòu)D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2、下面關(guān)于算法說法錯(cuò)誤的是（）A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B為解決某問題的算法同為該問題編寫的程序含義是相同的C算法的可行性是指指令不能有二義性D以上幾個(gè)都是錯(cuò)誤的3、棧和隊(duì)列的共同特點(diǎn)是()。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點(diǎn)4、以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（）？A廣義表B.二叉樹C.稀疏矩陣D.串5、下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（）A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。6、靜態(tài)鏈表中指針表示的是（）。A內(nèi)存地址B數(shù)組下標(biāo)C表頭地址D下一元素地址7、若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A順序表B雙鏈表C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D單循環(huán)鏈表8、下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（）。A快速排序B.堆排序C.歸并排序D.冒泡排序9、設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key%p，則p最好選擇（）。A.小于等于m的最大奇數(shù)B.小于等于m的最大素?cái)?shù)C.小于等于m的最大偶數(shù)D.小于等于m的最大合數(shù)10、字符串的長度是指（）。A.串中不同字符的個(gè)數(shù)B.串中不同字母的個(gè)數(shù)C.串中所含字符的個(gè)數(shù)D.串中不同數(shù)字的個(gè)數(shù)11、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（）。A.top=top+1;B.top=top-1;C.top-next=top;D.top=top-next;12、二叉排序樹可以得到一個(gè)從小到大的有序序列。()A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷13、時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。A.堆排序B.冒泡排序C.希爾排序D.快速排序14、設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（）。A.O(log2n)B.O(1)C.O(n2)D.O(n)15、設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（）個(gè)結(jié)點(diǎn)。A.2k-1B.2kC.2k-1D.2k-116、設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（）條有向邊。A.nB.n-1C.mD.m-117、已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()A-A+B*C/DEB.-A+B*CD/EC-+*ABC/DED.-+A*BC/DE18、設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（）條邊。A.n(n-1)B.n+1C.nD.n(n+1)19、設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，820、設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。An-1Bn(n-1)/2Cn(n+1)/2Dn*n二、填空題（每空2分，共20分）1、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是 。2、已知如下程序段FOR i:= n DOWNTO 1 DO -語句1BEGIN x:=x+1； -語句2FOR j:=n DOWNTO i DO -語句3 y:=y+1; -語句4END；語句3執(zhí)行的頻度為 。3、解決散列表沖突的兩種方法是 。4、判斷一個(gè)無向圖是一棵樹的條件是 。5、設(shè)一棵二叉樹的前序序列為ABC，則有 種不同的二叉樹可以得到這種序列。6、設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為 。7、設(shè)有一個(gè)n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽?duì)角線上元素）存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則Aij與 A00之間有 個(gè)數(shù)據(jù)元素。8、已知8 個(gè)數(shù)據(jù)元素為（34，76，45，18，26，54，92，65）按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，則該樹的深度為_ _。9、在一棵完全二叉樹中，若編號(hào)為 i的結(jié)點(diǎn)有右孩子，則該右孩子結(jié)點(diǎn)的編號(hào)為_ _。10、下面程序段的時(shí)間復(fù)雜度是 。 i 0；while（irchild= (2) ; (3) =q;if(p-lchild) (4) ; if(p-rchild) (5) ;2、下列程序判斷字符串s 是否對(duì)稱，對(duì)稱則返回1，否則返回0；如 f(abba)返回1，f(abab)返回0； int f( (1) ) int i=0,j=（2）; while (sj) (3)_; for(j-; ij & si=sj;（4） ,j-); re