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

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

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

3、和 刪除運算，則利用（A ）存儲方式最節(jié)省時間。A .順序表B.雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表A.快速排序B.堆排序9、設(shè)散列表中有0個存儲單元，（A.快速排序B.堆排序9、設(shè)散列表中有0個存儲單元，（B ）。A.小于等于0的最大奇數(shù)C.小于等于0的最大偶數(shù) 10、字符串的長度是指（C ）A.串中不同字符的個數(shù)C.串中所含字符的個數(shù)C.歸并排序D.冒泡排序散列函數(shù)儀女6丫）=key % b則口最好選擇B.小于等于m的最大素數(shù)D.小于等于0的最大合數(shù)）B.串中不同字母的個數(shù)D.串中不同數(shù)字的個數(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、二叉排序樹可以得到一個從小到大的有序序列。（B ）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷A卷）第3頁共7頁二叉排序樹：13、時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為0（皿08口）的是（A ）。2A.堆排序B.冒泡排序C.希爾排序 D.快速排序14、設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈 表仍然保持有序，則該操作的時間復(fù)雜度為（D）。A. O（logn） B. O（1） C. O（n2）D. O（n）215、設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（

5、D）個結(jié)點。A. 2k-1B. 2kC. 2k-1D. 2k-116、設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（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è)某強連通圖中有n個頂點，則該強連通圖中至少有（C ）條邊。A. n（n-1） B. n+1 C. nD. n（n+1）1：強連通圖的定義：在有向圖6中，如果對于每一對VI vj vi手丫上從到丫）和從

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

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

8、n+1)個連續(xù)的存儲單元中，則人仃與A00之間有 個數(shù)據(jù)元素。8、已知8個數(shù)據(jù)元素為(34, 76, 45, 18, 26, 54, 92, 65)按照依次插入結(jié)點的方法生成一棵二叉排序樹，則該樹的深度為。9、在一棵完全二叉樹中，若編號為i的結(jié)點有右孩子，則該右孩子結(jié)點的 編號為。10、下面程序段的時間復(fù)雜度是。i = 0;while (irchild= (2) ;(3) =q;(A卷)第6頁共7頁if(p-lchild) (4) ; if(p-rchild) (5)2、下列程序判斷字符串s是否對稱，對稱則返回1,否則返回0;如f(abba) 返回1, a62b)返回0；int f( (1) int i=0,j= (2);while (sj) (3);for(j-; ij & si=sj; (