西南財(cái)經(jīng)大學(xué)電子商務(wù)學(xué)院

西南財(cái)經(jīng)大學(xué)天府學(xué)院試卷(B卷)考試科目：數(shù)據(jù)構(gòu)造

_本年級

層次

教課班

：

學(xué)號：記試題號一二三分考分表閱卷人注意：1、本次考試為A卷考試，考試時(shí)間120分鐘。2、請將答案挨次寫在專用答題紙上。3、全卷共一部分，滿分為100分。

四

五

六

總分一、單項(xiàng)選擇題（共15題，每題2分，合計(jì)30分）1、在數(shù)據(jù)構(gòu)造學(xué)科中，偽代碼是（）、描繪算法且簡單理解的一種語言、能夠方便描繪算法中的分支與循環(huán)等構(gòu)造化語句、以上都正確2、若進(jìn)棧序列為1、2、3、4，進(jìn)棧過程中能夠出棧，則以下不行能的出棧序列是（）A、1、4、3、2B、2、3、4、1C、3、1、4、2D、3、4、2、13、設(shè)語句x++的時(shí)間是單位時(shí)間，則以下語句的時(shí)間復(fù)雜度為（）。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;B、O(n2)D、O(n3)A、O(1)C、O(n)4、假設(shè)一個(gè)鏈表行列的隊(duì)首和隊(duì)尾指針分別用front和rear表示，每個(gè)結(jié)點(diǎn)的構(gòu)造為：datanext當(dāng)出隊(duì)時(shí)所進(jìn)行的指針操作為（）A、front=front–>nextB、rear=rear–>nextC、front–>next=rear;rear=rear–>nextD、front=front–>next;front–>next=rear5、向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)履行（）。A、hs->next=s;B、s->next=hs;hs=s;C、s->next=hs->next;hs->next=s;D、s->next=hs;hs=hs->next;6、對于次序儲存的有序表{5，12，20，26，37，42，46，50，64}，若采納折半查找，則查找元素26的比較次數(shù)為（）。A、2B、3C、4D、57、對一組數(shù)據(jù)（86，48，26，15，23）排序，數(shù)據(jù)的擺列序次在排序過程中的變化為：8648261523154826862315232686481523264886這個(gè)排序過程采納的排序方法是（）。A、冒泡B、選擇C、迅速8、若依據(jù)查找表（23，44，36，48，52，73，64，58）成立哈希表，采納址，則哈希地點(diǎn)等于3的元素個(gè)數(shù)為（）。A、1B、2C、3

D、插入h(K)=K%7D、4

計(jì)算哈希地9、若一個(gè)元素序列基本有序，則采納（）方法較快。A、直接插入排序B、簡單項(xiàng)選擇擇排序C、堆排序D、迅速排序10、在一個(gè)長度為n的次序表中向第i個(gè)元素(0<i<n+1)以前插入一個(gè)新元素時(shí)，需要向后挪動（個(gè)元素。A、n-iB、n-i+1C、n-i-1D、i

）11、下邊對于線性表的說確的是

(

).、每個(gè)元素都有一個(gè)直接前趨和一個(gè)直接后繼、線性表中起碼要有一個(gè)元素、除第一個(gè)和最后一個(gè)元素外，其他每個(gè)元素都有一個(gè)且僅有一個(gè)直接前趨和直接后繼12、在數(shù)據(jù)構(gòu)造中，從邏輯上能夠把數(shù)據(jù)構(gòu)造分為（）。A．動向構(gòu)造和靜態(tài)構(gòu)造B.緊湊構(gòu)造和非緊湊構(gòu)造C.線性構(gòu)造和非線性構(gòu)造D.部構(gòu)造和外面構(gòu)造13、已知函數(shù)SubString(s,i,j)的功能是返回串s中從第i個(gè)字符起長度為j的子串，函數(shù)SCopy(s,t)的功能為復(fù)制串t到s。若字符串S=”SCIENCESTUDY”，則調(diào)用函數(shù)SCopy(P,Sub(S,1,7))后獲得（）。A、P=”SCIENCE”B、P=”STUDY”C、S=”SCIENCE”D、S=”STUDY”14、若將一個(gè)10×10階的對稱矩陣壓縮儲存到一個(gè)一維數(shù)組中，則該一維數(shù)組的大小應(yīng)當(dāng)是（）。A、55B、56C、45D、4615、線索二叉樹中，結(jié)點(diǎn)p沒有左子數(shù)的充要條件是（）。A、p->lc=NULLB、p->ltag=1C、p->lc=NULL且p->ltag=1D、以上都不對二、是非題（以下表達(dá)正確的寫上T，不然，寫上F。共10題，每題1分，合計(jì)10分）1、在有向圖G中，<V2,V1>和<V1,V2>是兩條不一樣的邊。（）2、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。（）3、線性表簡稱為“次序表”。（）4、線性的數(shù)據(jù)構(gòu)造能夠次序儲存，也能夠鏈?zhǔn)絻Υ?。非線性的數(shù)據(jù)構(gòu)造只好連結(jié)儲存。（）5、從單鏈表的任一結(jié)點(diǎn)出發(fā)，都能接見到全部結(jié)點(diǎn)。（）6、在有序的次序表和有序的鏈表上，均可使用折半查找來提升查找效率。（）7、假如某種排序方法是不穩(wěn)固的，那么該排序方法不擁有適用價(jià)值。（）8、滿二叉樹必定是完整二叉樹。（）9、若二叉樹的中序遍歷序列與后序遍歷序列同樣，則該二叉樹必定是任何結(jié)點(diǎn)都沒有右子樹。10、數(shù)據(jù)構(gòu)造觀點(diǎn)包含數(shù)據(jù)之間的邏輯構(gòu)造、數(shù)據(jù)在計(jì)算機(jī)中的儲存方式和數(shù)據(jù)的運(yùn)算三個(gè)方面。

（

）（）三、填空題（共10空，每空1分，合計(jì)10分）1、行列和貨倉最大的同樣點(diǎn)在于，它們都同屬于【1】;行列和棧最大的不一樣點(diǎn)在于，行列元素的刪除和插入按照【2】規(guī)則；而棧元素的刪除和插入按照后進(jìn)先出（LIFO）規(guī)則。2、假如常常對線性表進(jìn)行插入和刪除運(yùn)算，則最好采納【3】儲存構(gòu)造。3、已知二維數(shù)組A[5][3]，其每個(gè)元素占2個(gè)儲存單元，而且A[0][0]的儲存地點(diǎn)為1000。則元素A[3][2]的儲存地點(diǎn)為【4】。4、假設(shè)一個(gè)次序循環(huán)行列的儲存空間長度為QueueSize，隊(duì)首和隊(duì)尾指針分別用front和假如采納少用一個(gè)儲存空間的方式來劃分循環(huán)行列是隊(duì)空仍是隊(duì)滿，則判斷隊(duì)空的條件是判斷隊(duì)滿的條件是【6】。5、數(shù)據(jù)構(gòu)造按結(jié)點(diǎn)間的關(guān)系，可分為4中邏輯構(gòu)造，它們分別是【7】、【8】【9】和【10】。

rear表示，【5】；、四、算法填空題（每空2分，共20分）1、已知二叉樹中的結(jié)點(diǎn)種類BinTreeNode

定義為：structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};此中data為結(jié)點(diǎn)值域，left和right分別為指向左、右兒女結(jié)點(diǎn)的指針域。下邊函數(shù)的功能是返回二叉樹BT中值為X的結(jié)點(diǎn)所在的層號，請?jiān)诋嬘袡M線的地方填寫適合容。intNodeLevel(BinTreeNode*BT,ElemTypeX){intc1,c2;if(BT==NULL)return0;elseif(BT->data==X)

return1;

/*空樹的層號為/*根結(jié)點(diǎn)的層號為

0*/

1*/else{c1=NodeLevel(BT->left,X)if(c1>=1)returnc1+1;c2=【1】;if(【2】)returnelsereturn0;

【3】;/*若樹中不存在

X結(jié)點(diǎn)則返回

0*/}}2、以下算法片段是矩陣迅速轉(zhuǎn)置算法，請?jiān)趧澗€的地點(diǎn)填入適合的容。#defineARRAYSIZE1024typedefstruct{introw,col;DataTypevalue;

/*非零元素的行號和列號/*非零元素的值*/

*/}TriType;typedefstruct{triTypeitems[ARRAYSIZE+1];introws,cols;intnums;

/*非零元三元組，item[0]未用*//*稀少矩陣的行數(shù)、列數(shù)*//*稀少矩陣的非零元素個(gè)數(shù)*/}TriArray;FastTransMatrix(TriArrayTA,TriArrayTB){/*TA

為轉(zhuǎn)置前的三元組屬性表，

TB

為轉(zhuǎn)置后的三元組次序表

*/inti,j=0,k=0;intpos[ARRATSIZE+1],num[ARRATSIZE+1];if(TA.nums){for(i=1;i<=TA.cols;i++)

num[i]=0;for(i=1;i<=TA.nums;i++)

/*求

TA

中每一列非零元個(gè)數(shù)

*/【4】

;pos[1]=1;for(i=2;i<=TA.cols;i++)

/*計(jì)算第

i列第一個(gè)非零元的地點(diǎn)【5】

;for(i=1;i<=TA.nums;i++){j=TA.items[i].col;k=pos[j];TB.items[k].row=TA.items[i].col;TB.items[k].col=TA.item[i].row;TB.items[k].value=TA.items[i].value;【6】;}}TB.rows=TA.cols;TB.cols=TA.rows;}2、以下算法片段預(yù)實(shí)現(xiàn)的功能是：對有序表ST進(jìn)行折半查找，成功時(shí)返回記錄在表中的地點(diǎn)，失敗時(shí)返回0。請?jiān)趧澗€的地點(diǎn)填入適合的容。typedefstruct{keytypekey;}ElemType；typedefstruct{ElemType*elem;intlength;

/*數(shù)據(jù)元素儲存空間基址，/*表長度*/

建表時(shí)按實(shí)質(zhì)長度分派，

0號空間留空

*/}SSTable;intSearch_Bin(SSTableST,keytypekey){/*在表R中查找重點(diǎn)字k*/intlow=1,high=ST.length;while(【7】){mid=(low+high)/2;if(key=ST.elem[mid].key)returnelseif(key>ST.elem[mid].key)else【10】;

【8】【9】

;

;

/*找到待查元素*//*持續(xù)在前一半查找/*持續(xù)在后一半查找

*/*/}return0;

/*次序表中不存在待查元素

*/}五、算法應(yīng)用題（共

15分）1、模式般配的KMP算法應(yīng)用設(shè)目標(biāo)為s=”abcaabbabcabaacbacba”，模式p=”abcabaa”。(1)計(jì)算模式p的next[j]函數(shù)值。（3分）(2)不寫出KMP算法，只畫出采納next[j]函數(shù)進(jìn)行模式般配時(shí)每一趟的般配過程。（2分）2、若一棵二叉樹后序遍歷為DHEBFIGCA，中序遍歷序列為D