瓊州學(xué)院生物科學(xué)與技術(shù)學(xué)院

1、.班級(jí) 姓名 學(xué)號(hào)密 封 裝 訂 線 電子信息工程 學(xué)院 11 級(jí) 數(shù)字媒體 專業(yè)數(shù)據(jù)結(jié)構(gòu)試卷2012 2013 學(xué)年度第 2 學(xué)期期末考試 （ A ）卷注意事項(xiàng)： 1、考前請(qǐng)將密封線內(nèi)填寫(xiě)清楚 2、所有答案請(qǐng)直接答在試卷上（或答題紙上） 3、考試形式：閉 卷 4、本試卷共 5 大題，滿分100分?？荚嚂r(shí)間 120 分鐘5、評(píng)分一律加分，不寫(xiě)減分題號(hào)一二三四五總分評(píng)卷人復(fù)查人得分 得 分一、單項(xiàng)選擇題（本題共 15 小題，每小題 2 分，共 30 分）1、算法的時(shí)間復(fù)雜度取決于（ ）。A問(wèn)題的規(guī)模 B待處理數(shù)據(jù)的初態(tài) CA和BD都不是2、下面的敘述不正確的是（ ）。A線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第

2、i個(gè)元素的時(shí)間同i的值成正比B線性表采用鏈?zhǔn)酱鎯?chǔ)比采用順序存儲(chǔ)浪費(fèi)更多的空間C線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i 的值成正比D線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)3、(1) 靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元素的時(shí)間與i無(wú)關(guān)。(2) 靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。(3) 靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)。以上說(shuō)法錯(cuò)誤的是（ ）。A（1），（2） B（1） C（1），（2），（3） D（2）4、若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)

3、間復(fù)雜度為（ ）(1<=i<=n+1)。AO(0) BO(1) CO(n) DO(n2) 5、用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)( )。A僅修改隊(duì)頭指針 B. 僅修改隊(duì)尾指針 C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭、隊(duì)尾指針都可能要修改6、遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D. 線性表7、假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素，其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。A(rear-front+m)%m Brear-front+1

4、C(front-rear+m)%m D(rear-front)%m8、下面關(guān)于串的的敘述中，哪一個(gè)是不正確的？（ ）A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)9、若串S1=ABCDEFG，S2=9898，S3=#，S4=012345，執(zhí)行Concat(Replace(S1, Substring(S1, length(S2), length(S3), S3), Substring(S4, Index(S2, 8), length(S2)其結(jié)果為（ ）。AABC#G0123 BABCD#2345 CABC#G2345 DAB

5、C#G123410、設(shè)有數(shù)組Ai, j，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)，元素A5，8的存儲(chǔ)首地址為( )。A. BA+141 B. BA+180 C. BA+222 D. BA+22511、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。A.13 B. 33 C. 18 D. 4012、一棵二叉樹(shù)的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（ ）。ACABDEFG BABCDEFG CDACEFBG

6、DBADCFEG13、二叉樹(shù)的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷：HFIEJKG。該二叉樹(shù)根的右子樹(shù)的根是（）。A、 E B、 F C、 G D、 H14、某二叉樹(shù)T有n個(gè)結(jié)點(diǎn)，設(shè)按某種順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)為1，2，n，且有如下性質(zhì)：T中任一結(jié)點(diǎn)V，其編號(hào)等于左子樹(shù)上的最小編號(hào)減1，而V的右子樹(shù)的結(jié)點(diǎn)中，其最小編號(hào)等于V左子樹(shù)上結(jié)點(diǎn)的最大編號(hào)加1。這時(shí)是按（ ）編號(hào)的。A.中序遍歷序列 B.前序遍歷序列 C.后序遍歷序列 D.層次順序 15、一個(gè)有向無(wú)環(huán)圖的拓?fù)渑判蛐蛄校?）是唯一的。A一定 B不一定得 分二、填空題（每小題 2 分，共 30 分）1、抽

7、象數(shù)據(jù)類型的定義僅取決于它的一組_ ，而與 _無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_ 不變，都不影響其外部使用。2、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是 。3、設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data, next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn)，若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語(yǔ)句：_；_；4、在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。5、在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_。6、循環(huán)隊(duì)列用數(shù)組A0m-1存放其元素值，已知其頭尾指針?lè)謩e是front和rear ，則當(dāng)前隊(duì)列的

8、元素個(gè)數(shù)是_ 。7、棧是 的線性表，其運(yùn)算遵循 的原則。8、 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。9、串是一種特殊的線性表，其特殊性表現(xiàn)在_；串的兩種最基本的存儲(chǔ)方式是_、_；兩個(gè)串相等的充分必要條件是_。 10、兩個(gè)字符串相等的充分必要條件是_。11、兩個(gè)字符串相等的充分必要條件是_。12、已知U=xyxyxyxxyxy；T=xxy； StrAssign（S，U）； StrAssign（V，Substring（S，Index（S，T），StrLength（T）+1）； StrAssign（M，ww）求Replace（S，V，M）= _。13、設(shè)只含根結(jié)點(diǎn)的二叉樹(shù)的高度為0，則高度為k的

9、二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為_(kāi)，最小結(jié)點(diǎn)數(shù)為_(kāi)。14、高度為K的完全二叉樹(shù)至少有_個(gè)葉子結(jié)點(diǎn)。15、一個(gè)有2001個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為_(kāi)。得 分三、判斷題（正確打，錯(cuò)誤打×，本題共10 小題，每題 2 分，共20 分） 1、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。( )2、順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。（）3、線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。( )4、即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（ ）5、有n個(gè)數(shù)順序（依次）進(jìn)棧，出棧序列有Cn種，Cn=1/(n+1)*(

10、2n)! / (n!)*(n!)。（ ）6、設(shè)模式串的長(zhǎng)度為m，目標(biāo)串的長(zhǎng)度為n，當(dāng)nm且處理只匹配一次的模式時(shí)，樸素的匹配（即子串定位函數(shù)）算法所花的時(shí)間代價(jià)可能會(huì)更為節(jié)省。（ ）7、從邏輯結(jié)構(gòu)上看，n維數(shù)組的每個(gè)元素均屬于n個(gè)向量。（ ）8、稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（ ）9、樹(shù)形結(jié)構(gòu)中元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。10、必須把一般樹(shù)轉(zhuǎn)換成二叉樹(shù)后才能進(jìn)行存儲(chǔ)。得 分四、應(yīng)用題（本題共 2 小題，每題 5 分，共,10 分。）1、假設(shè)鏈表p和鏈表q中的結(jié)點(diǎn)值都是整數(shù)，且按結(jié)點(diǎn)值的遞增次序鏈接起來(lái)的帶表頭結(jié)點(diǎn)的環(huán)形鏈表。各鏈表的表頭結(jié)點(diǎn)的值為max,且鏈表中其他結(jié)點(diǎn)的值都小于

11、max，在程序中取max為9999。在各個(gè)鏈表中，每個(gè)結(jié)點(diǎn)的值各不相同，但鏈表p和鏈表q可能有值相同的結(jié)點(diǎn)（表頭結(jié)點(diǎn)除外）。下面的程序?qū)㈡湵韖合并到鏈表p中，使得合并后的鏈表是按結(jié)點(diǎn)值遞增次序鏈接起來(lái)的帶表頭結(jié)點(diǎn)的環(huán)形鏈表，且鏈表中各個(gè)結(jié)點(diǎn)的值各不相同。請(qǐng)?jiān)趧澗€處填上適當(dāng)內(nèi)容，每個(gè)框只填一個(gè)語(yǔ)句或一個(gè)表達(dá)式，鏈表的結(jié)點(diǎn)類型如下：struct node int data; struct node *link; LNode, LinkList;const max=9999;void merge( LinkList p, LinkList q ) LinkList r, s; r=p;while (

12、A)_ while ( r->link->data<q->link->data ) (B)_; if ( r->link->data>q->link->data ) s= (C)_ ; (D)_ =s->link; s->link= (E)_ ; (F)_ _=s; (G) _; else (H)_ _; s:=q.link; (I)_ _; free(s); free(q);2、假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整型數(shù)組A（-3:8，3:5，-4:0，0:7）時(shí)，第一個(gè)元素的字節(jié)存儲(chǔ)地址是100，每個(gè)整數(shù)占4個(gè)字節(jié)，問(wèn)A（0，4，-2，5）的存儲(chǔ)地址是什么？得 分五、算法設(shè)計(jì)題（本題共 1 小題，共 10 分）111、設(shè)有一鏈隊(duì)列的結(jié)點(diǎn)