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

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

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

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

4、C(front-rear+m)%m D(rear-front)%m8、下面關(guān)于串的的敘述中，哪一個是不正確的？（ ）A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?、若串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ù)組的每個元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A5，8的存儲首地址為( )。A. BA+141 B. BA+180 C. BA+222 D. BA+22511、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ ）。A.13 B. 33 C. 18 D. 4012、一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（ ）。ACABDEFG BABCDEFG CDACEFBG

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

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

8、元素個數(shù)是_ 。7、棧是 的線性表，其運算遵循 的原則。8、 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。9、串是一種特殊的線性表，其特殊性表現(xiàn)在_；串的兩種最基本的存儲方式是_、_；兩個串相等的充分必要條件是_。 10、兩個字符串相等的充分必要條件是_。11、兩個字符串相等的充分必要條件是_。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é)點的二叉樹的高度為0，則高度為k的

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

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

11、max，在程序中取max為9999。在各個鏈表中，每個結(jié)點的值各不相同，但鏈表p和鏈表q可能有值相同的結(jié)點（表頭結(jié)點除外）。下面的程序?qū)㈡湵韖合并到鏈表p中，使得合并后的鏈表是按結(jié)點值遞增次序鏈接起來的帶表頭結(jié)點的環(huán)形鏈表，且鏈表中各個結(jié)點的值各不相同。請在劃線處填上適當(dāng)內(nèi)容，每個框只填一個語句或一個表達(dá)式，鏈表的結(jié)點類型如下：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)先存儲整型數(shù)組A（-3:8，3:5，-4:0，0:7）時，第一個元素的字節(jié)存儲地址是100，每個整數(shù)占4個字節(jié)，問A（0，4，-2，5）的存儲地址是什么？得 分五、算法設(shè)計題（本題共 1 小題，共 10 分）111、設(shè)有一鏈隊列的結(jié)點