《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測(cè)試題帶答案 (3)

1、數(shù)據(jù)結(jié)構(gòu)模擬試題03一、單項(xiàng)選擇題（每題 2 分，共30分）1算法指的是（ ） A計(jì)算機(jī)程序 B解決問題的計(jì)算方法 C排序算法 D解決問題的有限運(yùn)算序列2線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ ） A必須是不連續(xù)的 B連續(xù)與否均可 C必須是連續(xù)的 D和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)3將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（ ） AO（1） BO（n） CO（m） DO（m+n）4由兩個(gè)棧共享一個(gè)向量空間的好處是：（ ） A減少存取時(shí)間，降低下溢發(fā)生的機(jī)率 B節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率 C減少存取時(shí)間，降低上溢發(fā)生的機(jī)率 D節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率5設(shè)數(shù)組data

2、m作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為（ ） Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m6如下陳述中正確的是（ ） A串是一種特殊的線性表 B串的長度必須大于零 C串中元素只能是字母 D空串就是空白串7若目標(biāo)串的長度為n，模式串的長度為n/3，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是（ ） AO（） BO（n） CO（n2） DO（n3）8一個(gè)非空廣義表的表頭（ ） A不可能是子表 B只能是子表 C只能是原子

3、 D可以是子表或原子9假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表 02335 對(duì)應(yīng)的稀疏矩陣是（ ） 10在一棵度為3的樹中,度為3的結(jié)點(diǎn)個(gè)數(shù)為2,度為2 的結(jié)點(diǎn)個(gè)數(shù)為1,則度為0的結(jié)點(diǎn)個(gè)數(shù)為( ) A4 B5 C6 D711在含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中,零元素的個(gè)數(shù)為( ) Ae B2e Cn2e Dn22e12假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示,則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是( ) AO(n) BO(e) CO(n+e) DO(n*e) 13用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化

4、情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ） A選擇排序 B希爾排序 C歸并排序 D快速排序14適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是（ ）A有序表 B分塊有序表 C三叉排序樹 D線性鏈表15不定長文件是指（ ）A文件的長度不固定 B記錄的長度不固定C字段的長度不固定 D關(guān)鍵字項(xiàng)的長度不固定二、填空題（每題2分，共20分）1數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無關(guān)，是獨(dú)立于計(jì)算機(jī)的。2在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾

5、結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head= 。3棧頂?shù)奈恢檬请S著 操作而變化的。4在串S=“structure”中，以t為首字符的子串有 個(gè)。5假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，其中B0存儲(chǔ)矩陣中第1個(gè)元素a1,1,則B31中存放的元素是 。6已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有 個(gè)葉子結(jié)點(diǎn)。 7已知一個(gè)圖的廣度優(yōu)先生成樹如右圖所示，則與此相 應(yīng)的廣度優(yōu)先遍歷序列為 。 8在單鏈表上難以實(shí)現(xiàn)的排序方法有 和 。 9在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為 。 10多重表文件

6、和倒排文件都?xì)w屬于 文件。三、算法簡(jiǎn)答題（每題 5 分，共20分）1畫出下列廣義表的共享結(jié)構(gòu)圖形表示 P=（z）,(x,y)）,(x,y),x),(z)）2請(qǐng)畫出與下列二叉樹對(duì)應(yīng)的森林。    3已知一個(gè)無向圖的頂點(diǎn)集為a, b, c, d, e ,其鄰接矩陣如下所示0100110010000110110110110éëêêêêêêùûúúúúúú (1)畫出該圖的圖形； （2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行

7、深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。 4已知一個(gè)散列表如下圖所示：  35 20  33 48  59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key)%m =0,1,，m1其中 h1(key)=key%11+1回答下列問題：（1）對(duì)表中關(guān)鍵字35，20，33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？（2）該散列表在等概率查找時(shí)查找成功的平均查找長度為多少？四

8、、閱讀算法（每題6分，共18分）1下列算法的功能是比較兩個(gè)鏈串的大小，其返回值為： comstr(s1,s2)= 請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?shù)膬?nèi)容。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( )return1； if( )return1； ； 2假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下： typ

9、edef struct DateType dataMaxSize； int front2,rear2； Queue2；對(duì)于i=0或1，fronti和reari分別為第i個(gè)隊(duì)列的頭指針和尾指針。請(qǐng)對(duì)以下算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。 int EnQueue (Queue2*Q,int i,DateType x) /若第 i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1；否則返回0 if(i<0|i>1)return 0； if(Q>reari=Q>front return0； Q>data =x； Q>reari= ; return1； 33已知二叉樹的存儲(chǔ)結(jié)構(gòu)為

10、二叉鏈表，閱讀下面算法。 typedef struct node DateType data； Struct node * next； ListNode； typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) LinkList s； If(T) Inorder(T>lchild)； If (!T>lchild)&&(!T>rchild) s=(ListNode*)malloc(sizeof(ListNode)； s>data=T>data； s&

11、gt;next=Leafhead； Leafhead=s； Inorder(T>rchild)； 對(duì)于如下所示的二叉樹     （1）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)；（2）說明該算法的功能。五、編寫算法（共8分）閱讀下列函數(shù)arrange()：int arrange(int a,int 1,int h,int x) /1和h分別為數(shù)據(jù)區(qū)的下界和上界 int i,j,t； i=1；j=h； while(i<j) while(i<j && aj>=x)j-； while(i<j && aj>

12、=x)i+； if(i<j) t=aj；aj=ai；ai=t； if(ai<x) return i； else return i1； （1）寫出該函數(shù)的功能； （2）寫一個(gè)調(diào)用上述函數(shù)實(shí)現(xiàn)下列功能的算法：對(duì)一整型數(shù)組bn中的元素進(jìn)行重新排列，將所有負(fù)數(shù)均調(diào)整到數(shù)組的低下標(biāo)端，將所有正數(shù)均調(diào)整到數(shù)組的高下標(biāo)端，若有零值，則置于兩者之間，并返回?cái)?shù)組中零元素的個(gè)數(shù)。  10數(shù)據(jù)結(jié)構(gòu)模擬試題03參考答案一、單項(xiàng)選擇題（每題 2 分，共30分）1D，101112131415二、填空題（每小題2分，共20分）1：存儲(chǔ)（或存儲(chǔ)結(jié)構(gòu)）2：pnextnext3：進(jìn)棧和退棧4：12

13、5：a4,86：3847：abefcdg8：快速排序、堆排序、希爾排序9：2 10：多關(guān)鍵字三、算法簡(jiǎn)答題（每題 4分，共20分）1、 2、3、（1）（2）深度優(yōu)先遍歷序列為：abdce 廣度優(yōu)先遍歷序列為：abedc4、（）對(duì)關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為、；（）平均查找長度ASL=+=32112595四、閱讀算法（每題6分，共18分）1、  S1=S1>next s2=s2>next s2(或s2!=NULL或s2&&!s1) s1(或s1!=NULL或s1&&!s2) return 02、 (i1)%2(或1i) Q>reari (Q>reari)%Maxsize3、(1)LeafheadF  H  G  D（2）中序遍歷二叉樹，按遍歷序列中葉子結(jié)點(diǎn)數(shù)據(jù)域的值構(gòu)建一個(gè)以Leafhead為頭指針的逆序單鏈表（或按二叉樹中葉子結(jié)點(diǎn)數(shù)據(jù)自右至左鏈接成一個(gè)鏈表）。五、編寫算法（共12分）（1）該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a中