《數(shù)據(jù)結構》模擬試題綜合測試題帶答案 (3)

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

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

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

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適于對動態(tài)查找表進行高效率查找的組織結構是（ ）A有序表 B分塊有序表 C三叉排序樹 D線性鏈表15不定長文件是指（ ）A文件的長度不固定 B記錄的長度不固定C字段的長度不固定 D關鍵字項的長度不固定二、填空題（每題2分，共20分）1數(shù)據(jù)的邏輯結構是從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無關，是獨立于計算機的。2在一個帶頭結點的單循環(huán)鏈表中，p指向尾

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

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

7、深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍歷序列。 4已知一個散列表如下圖所示：  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）對表中關鍵字35，20，33和48進行查找時，所需進行的比較次數(shù)各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？四

8、、閱讀算法（每題6分，共18分）1下列算法的功能是比較兩個鏈串的大小，其返回值為： comstr(s1,s2)= 請在空白處填入適當?shù)膬?nèi)容。int comstr(LinkString s1,LinkString s2) /s1和s2為兩個鏈串的頭指針 while(s1&&s2) if(s1>date<s2>date)return1； if(s1>date>s2>date)return1； ； ； if( )return1； if( )return1； ； 2假設兩個隊列共享一個循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下： typ

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

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)； 對于如下所示的二叉樹     （1）畫出執(zhí)行上述算法后所建立的結構；（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）寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法：對一整型數(shù)組bn中的元素進行重新排列，將所有負數(shù)均調(diào)整到數(shù)組的低下標端，將所有正數(shù)均調(diào)整到數(shù)組的高下標端，若有零值，則置于兩者之間，并返回數(shù)組中零元素的個數(shù)。  10數(shù)據(jù)結構模擬試題03參考答案一、單項選擇題（每題 2 分，共30分）1D，101112131415二、填空題（每小題2分，共20分）1：存儲（或存儲結構）2：pnextnext3：進棧和退棧4：12

13、5：a4,86：3847：abefcdg8：快速排序、堆排序、希爾排序9：2 10：多關鍵字三、算法簡答題（每題 4分，共20分）1、 2、3、（1）（2）深度優(yōu)先遍歷序列為：abdce 廣度優(yōu)先遍歷序列為：abedc4、（）對關鍵字35、20、33和48進行查找的比較次數(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）中序遍歷二叉樹，按遍歷序列中葉子結點數(shù)據(jù)域的值構建一個以Leafhead為頭指針的逆序單鏈表（或按二叉樹中葉子結點數(shù)據(jù)自右至左鏈接成一個鏈表）。五、編寫算法（共12分）（1）該函數(shù)的功能是：調(diào)整整數(shù)數(shù)組a中