2013韓山師范學(xué)院專升本插班生考試數(shù)據(jù)結(jié)構(gòu)課程試卷

1、A卷）第1頁(yè)共7頁(yè)韓山師范學(xué)院2013年專升本插班生考試試卷計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)試卷（A卷）題號(hào)12345678910答案題號(hào)11121314151617181920答案1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（A ）兩大類。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)于算法說(shuō)法錯(cuò)誤的是（D ）A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個(gè)都是錯(cuò)誤的3、棧和隊(duì)列的共同特點(diǎn)是（A ）。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒

2、有共同點(diǎn)4、以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（D ） ?A.廣義表B.二叉樹C.A.廣義表B.二叉樹C.稀疏矩陣D.串A卷）第2頁(yè)共7頁(yè)5、下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ B ）A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。6、靜態(tài)鏈表中指針表示的是（B ）。A.內(nèi)存地址B.數(shù)組下標(biāo)C.表頭地址 D.下一元素地址/所謂靜態(tài)鏈表就是沒有指針的，用下標(biāo)模仿這個(gè)指針的功能的 7、若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入

3、和 刪除運(yùn)算，則利用（A ）存儲(chǔ)方式最節(jié)省時(shí)間。A .順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表A.快速排序B.堆排序9、設(shè)散列表中有0個(gè)存儲(chǔ)單元，（A.快速排序B.堆排序9、設(shè)散列表中有0個(gè)存儲(chǔ)單元，（B ）。A.小于等于0的最大奇數(shù)C.小于等于0的最大偶數(shù) 10、字符串的長(zhǎng)度是指（C ）A.串中不同字符的個(gè)數(shù)C.串中所含字符的個(gè)數(shù)C.歸并排序D.冒泡排序散列函數(shù)儀女6丫）=key % b則口最好選擇B.小于等于m的最大素?cái)?shù)D.小于等于0的最大合數(shù)）B.串中不同字母的個(gè)數(shù)D.串中不同數(shù)字的個(gè)數(shù) 11、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為(D )。A.

4、top=top+1;B. top=top-1;C. top-next=top;D. top=top-next;12、二叉排序樹可以得到一個(gè)從小到大的有序序列。（B ）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷A卷）第3頁(yè)共7頁(yè)二叉排序樹：13、時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為0（皿08口）的是（A ）。2A.堆排序B.冒泡排序C.希爾排序 D.快速排序14、設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈 表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（D）。A. O（logn） B. O（1） C. O（n2）D. O（n）215、設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（

5、D）個(gè)結(jié)點(diǎn)。A. 2k-1B. 2kC. 2k-1D. 2k-116、設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（C）條有向邊。A. nB. n-1 C. mD. m-117、已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（D ）A. -A+B*C/DE B. -A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE18、設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（C ）條邊。A. n（n-1） B. n+1 C. nD. n（n+1）1：強(qiáng)連通圖的定義：在有向圖6中，如果對(duì)于每一對(duì)VI vj vi手丫上從到丫）和從

6、丫）到丫諸口存在路徑，貝U郁 是強(qiáng)連通圖。2：分析：可知當(dāng)9個(gè)節(jié)點(diǎn)的圖構(gòu)成一個(gè)環(huán)，任意兩點(diǎn)之間存在著回路，于是最小的邊數(shù)為最大邊數(shù)為n（n-1）;19、設(shè)一組初始記錄關(guān)鍵字序列（5, 2, 6, 3, 8）,以第一個(gè)記錄關(guān)鍵字5 為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（C ）。A. 2，3，5，8，6B. 3，2，5，8，6C. 3 2, 5, 6, 8D. 2, 3, 6, 5, 820、設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有（B ）條邊。A卷)第4頁(yè)共7頁(yè)D. n2A. n-1 B. n(n-1)/2 D. n2得分 評(píng)卷人 二、填空題(每空2分，共20分)1、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是時(shí)間

7、復(fù)雜度和空間復(fù)雜度2、已知如下程序段FOR i:= n DOWNTO 1 DO語(yǔ)句 1BEGINx:=x+1;語(yǔ)句 2FOR j:=n DOWNTO i DO 語(yǔ)句 3y：=y+1;語(yǔ)句 4END;語(yǔ)句3執(zhí)行的頻度為 。3、解決散列表沖突的兩種方法是 開放地址法和鏈地址法4、判斷一個(gè)無(wú)向圖是一棵樹的條件是有n個(gè)頂點(diǎn)，n-1條邊的無(wú)向連通圖5、設(shè)一棵二叉樹的前序序列為人8則有 5 _種不同的二叉樹可以得到 這種序列。6、設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為 空的條件為。7、設(shè)有一個(gè)口階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?(包括對(duì)角線上元素)存放在n(

8、n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則人仃與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;(A卷)第6頁(yè)共7頁(yè)if(p-lchild) (4) ; if(p-rchild) (5)2、下列程序判斷字符串s是否對(duì)稱，對(duì)稱則返回1,否則返回0;如f(abba) 返回1, a62b)返回0；int f( (1) int i=0,j= (2);while (sj) (3);for(j-; ij & si=sj; (