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

1、（a卷）第 9 頁 共 9 頁韓山師范學(xué)院2012年專升本插班生考試 計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè) 數(shù)據(jù)結(jié)構(gòu) 試卷 （a卷）題號(hào)一二三四五六總分評(píng)卷人得分得分評(píng)卷人一、 單項(xiàng)選擇題（每題1.5分，共30分）題號(hào)12345678910答案題號(hào)11121314151617181920答案1、數(shù)據(jù)的不可分割的最小單位是（ c ）。a數(shù)據(jù)元素 b數(shù)據(jù)對(duì)象 c數(shù)據(jù)項(xiàng) d數(shù)據(jù)串2、一個(gè)算法應(yīng)該具有一些重要特性，下列不是算法特性的是（ d ） 。 a有窮性 b確定性 c可行性 d健壯性 e至少一個(gè)輸出 3、下面關(guān)于線性表的表述中，（ b ）是錯(cuò)誤的？ a若線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。 b若線性

2、表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。 c線性表采用鏈接存儲(chǔ)，占用的存儲(chǔ)單元不一定是連續(xù)的。 d線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。4、下列哪個(gè)不是鏈表所具有的特點(diǎn)是（ a ）。 a可隨機(jī)訪問表中元素b插入、刪除不需要移動(dòng)元素c線性鏈表必須有一個(gè)指針域d所需空間與線性長(zhǎng)度成正比解析 鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)，是用結(jié)點(diǎn)來存儲(chǔ)數(shù)據(jù)元素。線性表采用鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，不能進(jìn)行數(shù)據(jù)元素的隨機(jī)訪問，其優(yōu)點(diǎn)是插入和刪除操作不需要移動(dòng)元素。5、若線性表的長(zhǎng)度為 n，且采用順序存儲(chǔ)結(jié)構(gòu)，則等概率刪除其第 i個(gè)元素的算法的時(shí)間復(fù)雜度為（ d ）(1<=i<=n)。 a. o(i) b. o(n-

3、i) c. o(1) d. o(n)6、靜態(tài)鏈表中指針表示的是（ b ）。 a 內(nèi)存地址 b數(shù)組下標(biāo) c表頭地址 d下一元素地址7、下列關(guān)于串的敘述中正確的是 b 。a串中所含的字母?jìng)€(gè)數(shù)稱為串的長(zhǎng)度b串是一種特殊的線性表 c串中的字母不區(qū)分大小寫d由空格組成的串稱為空串8、設(shè)有一個(gè)采用壓縮存儲(chǔ)的9 階對(duì)稱矩陣a，以行序?yàn)橹鞔鎯?chǔ)，第一個(gè)元素a11的存儲(chǔ)地址為 0，每個(gè)元素占一個(gè)地址空間，則a86 的地址為（ ） 。 a. 26 b. 27 c. 36 d. 37e.46f.479、判斷一個(gè)帶表頭的循環(huán)鏈表h為空表的判定條件是（ a ）a.hnullb.h->next=nullc.h->

4、;nextnulld.h>next=h10、若一個(gè)棧的輸入序列為 1,2,3,n，輸出序列的第一個(gè)元素是 i，則第 j 個(gè)輸出元素是（ b ）。 a. 不確定的b. i-jc. j-i+1d. i-j-1 11、在一個(gè)單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若要?jiǎng)h除p所指的結(jié)點(diǎn),則執(zhí)行( b )。a. q->next=pb. q->next=p->next;c. p=q->next;d. p->next= q->next;12、廣義表a=(a,(b,c),(d,e),(f,g),則head(tail(head(tail(tail(a)式子的值為（

5、 c ）。 a. (f) b.f c. e d. (e)13、在一棵度為3的樹中,度數(shù)為3的結(jié)點(diǎn)有2個(gè),度數(shù)為2的結(jié)點(diǎn)有2個(gè)，則度為0的結(jié)點(diǎn)個(gè)數(shù)為( a ) a7 b8 c9 d1014、在下述結(jié)論中，正確的是（ c ）只有一個(gè)結(jié)點(diǎn)的二叉樹的度為 0; 二叉樹的度為 2； 二叉樹的左右子樹可任意交換; 深度為 k 的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。a b c d 15、算術(shù)表達(dá)式 a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（ a ） aabcde/+*+ b ab+cde/+* cabcde/*+ dabcde*/+ 16、一個(gè)有 n 個(gè)結(jié)點(diǎn)的圖，最多有（ a ）個(gè)連通分量。

6、an bn-1 c1 d017、若目標(biāo)串的長(zhǎng)度為n，模式串的長(zhǎng)度為n/4，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（ d ）ao（ nlogn） bo（n/4） co（n） do（n2）18、設(shè)一組初始記錄關(guān)鍵字序列(7，2，8, 6，3，10, 5)，以第一個(gè)關(guān)鍵字7為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（ b ）。a. 2，5，6，3，7, 8, 10 b. 5，2，3，6，7,10, 8c. 2，3，5，6, 7, 8，10 d. 5，2，6，3, 7， 8, 10 19、向二叉搜索樹中插入一個(gè)元素的時(shí)間復(fù)雜度是( b )。ao(n） bo(log2n) co(n*log2n)do(n+

7、log2n) e.o(n2) f.o(n3)20、一個(gè)遞歸算法必須包括（ c ）。a. 初始條件和遞歸部分 b.初始條件和迭代部分c.終止條件和遞歸部分 d.終止條件和迭代部分得分評(píng)卷人二、問答題（共10分）1、什么叫完全二叉樹（4分）， 深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。2、簡(jiǎn)述順序存儲(chǔ)隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件。（6分）得分評(píng)卷人三、填空題（每空1分，共20分）1、根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成_單鏈表_和_雙鏈表_；而又根據(jù)指針的連接方式，鏈表又可分成

8、_和_。2、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_個(gè)和_個(gè)。3、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是算法的時(shí)間復(fù)雜度和空間復(fù)雜度。4、循環(huán)隊(duì)列的引入，目的是為了克服_ _。5、串是一種特殊的線性表，其特殊性表現(xiàn)在_數(shù)據(jù)元素是一個(gè)字符_ ；串的兩種最基本的存儲(chǔ)方式是_順序存儲(chǔ)方式_、_鏈?zhǔn)酱鎯?chǔ)方式_；兩個(gè)串相等的充分必要條件是 兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置的字符相同_。6、設(shè) n 行 n 列的下三角矩陣 a 已壓縮到一維數(shù)組 b1.n*（n+1）/2中，若按行為主序存儲(chǔ)，則 aij對(duì)應(yīng)的 b 中存儲(chǔ)位置為_。7、二叉樹中某結(jié)點(diǎn)的左子樹深度減去右子樹深度稱

9、為該結(jié)點(diǎn)的_，平衡二叉樹的結(jié)點(diǎn)的可能取值是_。8、已知一個(gè)圖如右圖所示，若采用深度優(yōu)先遍歷該圖，則遍歷的序列為 abcdegf 。9、設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為n0，度數(shù)為1的結(jié)點(diǎn)數(shù)為n1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_n0-1_；若采用二叉鏈表作為該二叉樹的存儲(chǔ)結(jié)構(gòu)，則該二叉樹中共有_個(gè)空指針域。10、直接插入排序用監(jiān)視哨的作用是緩沖作用。得分評(píng)卷人四、判斷題（每小題1分，共10分）1、數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)。 （ ）2、鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。( )3、為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。( )4、若輸入序列為

10、1，2，3，4，5，6，則通過一個(gè)?？梢暂敵鲂蛄?1，5，4，6，2，3。（ ）5、完全二叉樹一定是滿二叉樹，滿二叉樹不一定是完全二叉樹。（ ）6、線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（ ）7、kmp 算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)變小。 （ ）8、若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。（ ）9、向二叉排序樹中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹的高度。（ ）10、最小生成樹的 kruskal 算法是一種貪心法（greedy）。（ ）得分評(píng)卷人五、程序填空題（每個(gè)空1分，共10分）1、下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為：請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。

11、comstr(s1,s2)=int comstr(linkstring s1,linkstring s2) /s1和s2為兩個(gè)鏈串的頭指針 while (s1&&s2) if (s1>date<s2>date) return1； if (s1>date>s2>date) return1； ； ； if ( ) return 1； if ( ) return 1； ；2、如下為二分查找的非遞歸算法，試將其填寫完整。int binsch(elemtype a , int n, keytype k)int low, high =0;_;_;while (low<=high)int mid=_；if (k=amid.key) return mid; else if (k<mid.key) _; else _; return -1; /查找失敗得分評(píng)卷人六、算法設(shè)計(jì)題（20分）1、設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)