西南財經大學天府學院試卷(B卷)考試科目：數據構造

_本年級

層次

教課班

：

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

四

五

六

總分一、單項選擇題（共15題，每題2分，合計30分）1、在數據構造學科中，偽代碼是（）、描繪算法且簡單理解的一種語言、能夠方便描繪算法中的分支與循環等構造化語句、以上都正確2、若進棧序列為1、2、3、4，進棧過程中能夠出棧，則以下不行能的出棧序列是（）A、1、4、3、2B、2、3、4、1C、3、1、4、2D、3、4、2、13、設語句x++的時間是單位時間，則以下語句的時間復雜度為（）。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、假設一個鏈表行列的隊首和隊尾指針分別用front和rear表示，每個結點的構造為：datanext當出隊時所進行的指針操作為（）A、front=front–>nextB、rear=rear–>nextC、front–>next=rear;rear=rear–>nextD、front=front–>next;front–>next=rear5、向一個棧頂指針為hs的鏈棧中插入一個s結點時，應履行（）。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的比較次數為（）。A、2B、3C、4D、57、對一組數據（86，48，26，15，23）排序，數據的擺列序次在排序過程中的變化為：8648261523154826862315232686481523264886這個排序過程采納的排序方法是（）。A、冒泡B、選擇C、迅速8、若依據查找表（23，44，36，48，52，73，64，58）成立哈希表，采納址，則哈希地點等于3的元素個數為（）。A、1B、2C、3

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

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

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

(

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

（

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

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

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

return1;

/*空樹的層號為/*根結點的層號為

0*/

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

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

X結點則返回

0*/}}2、以下算法片段是矩陣迅速轉置算法，請在劃線的地點填入適合的容。#defineARRAYSIZE1024typedefstruct{introw,col;DataTypevalue;

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

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

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

為轉置前的三元組屬性表，

TB

為轉置后的三元組次序表

*/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

中每一列非零元個數

*/【4】

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

/*計算第

i列第一個非零元的地點【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、以下算法片段預實現的功能是：對有序表ST進行折半查找，成功時返回記錄在表中的地點，失敗時返回0。請在劃線的地點填入適合的容。typedefstruct{keytypekey;}ElemType；typedefstruct{ElemType*elem;intlength;

/*數據元素儲存空間基址，/*表長度*/

建表時按實質長度分派，

0號空間留空

*/}SSTable;intSearch_Bin(SSTableST,keytypekey){/*在表R中查找重點字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】

;

;

/*找到待查元素*//*持續在前一半查找/*持續在后一半查找

*/*/}return0;

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

*/}五、算法應用題（共

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