(完整word版)《數(shù)據(jù)結(jié)構(gòu)》課程期末考試試卷(A卷)DAOAN-副本

題號一題號一二三四五六總分得分評卷人(共六大題)浙江財經(jīng)學(xué)院東方學(xué)院2010?2011學(xué)年第一學(xué)期《數(shù)據(jù)結(jié)構(gòu)》課程期末考試試卷(A卷)考核方式：閉卷 考試日期：2010年月日適用專業(yè)、班級：東方電子商務(wù)專業(yè)說明：(1)請考生將答案寫在答題紙上；(2)考試時間120分鐘；一、單選題(每題1分，共15分)1、對一個算法的評價，不包括如下( )方面的內(nèi)容。A.健壯性B.可讀性C.正確性D.實用性2執(zhí)行下面程序段時，s語句的執(zhí)行次數(shù)為(D)。for(inti=l;i<=n;i++)For(intj=1;j<=i;j++)S;A.n2B.N2/2 C.n(n+1)D.n(n+1)/2面算法的時間復(fù)雜度為(B)intf(intn){if(n==0||n==l)return1.Elsereturnn*f(n-l);A.O(1)B.O(n)C.O(n2)DO(n!)4、在一個長度為n的順序存儲的線性表中，刪除第i個元素(1&i&n)時，需要從前向后依次前移(A)個元素。A.n-iB.n-i+1C.n-i-lD.i5若一個結(jié)點(diǎn)的引用為p,在p結(jié)點(diǎn)后面插入一個值為x的新結(jié)點(diǎn)的操作為(D)。A.p=newNode(x,p)B.p=newNode(x,p.next)

C.p.next=newNode(x,p)D.p.next=newNode(x,p.next)假定利用數(shù)組a順序存儲一個棧，用top表示棧頂指針，top-=-1表示棧空,并已知棧不為空，當(dāng)退棧并返回棧頂元素時所執(zhí)行的操作為 （B）。A.returna[--top]; B.returna[top--];C.returna[++top];D.returna[top++];7若讓元素1.2.3依次進(jìn)棧.則出棧次序不可能出現(xiàn)（C）的情況。A3.2.1 B.2,1,3 C.3,1,2 D.1.3,28假定一個順序隊列的隊首和隊尾指針分別為 f和r,則判斷隊空的條件為（D ）。A.f+1==rB.r+l==fC.f-==0D.f==r9在一個順序隊列中，隊首指針指向隊首元素的（A）位置。A.前一個B.后一個C.當(dāng)前D.前2個10樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（C）。A.0B.1C.-1D.211在一棵具有35個結(jié)點(diǎn)的完全二叉樹中，該樹的深度為（A）。A.6B.7C.5D.812在一棵具有n個結(jié)點(diǎn)的二叉樹的第i層上，最多具有（C）個結(jié)點(diǎn)。A.2iB.2i+1C.2i-1D.2n13n個頂點(diǎn)的連通圖至少包含有（A）條邊。A.n-lB,nC.n+114為了實現(xiàn)圖的廣度優(yōu)先搜索遍歷.其廣度優(yōu)先搜索算法使用的一個輔助數(shù)據(jù)結(jié)構(gòu)為（B）。A.棧B.隊列二叉樹D.樹15在又tn個元素進(jìn)行直接選擇排序的過程中.需要進(jìn)行 （C）趟選擇和交換。n-ln/2n-ln/2浙江財經(jīng)學(xué)院東方學(xué)院課程期末考試試卷浙江財經(jīng)學(xué)院東方學(xué)院課程期末考試試卷第第頁，共7頁二、填空題（每空1分，共15分）1算法可用文字、高級程序設(shè)計語言或類同于高級程序設(shè)計語言的偽碼 描述2.數(shù)據(jù)的物理存儲結(jié)構(gòu)分為順序和―鏈?zhǔn)蕉N。3當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時，宜采用 4一個算法的時間復(fù)雜度為（n3+n210g2n+14n）/n,其數(shù)量級表示為。5任何集合框架都包含三大塊內(nèi)容：對外的接口、 接口的實現(xiàn)和對集合運(yùn)算的算法。6設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有 條邊才能確保是一個連通圖。7List接口對Collection進(jìn)行了簡單的擴(kuò)充，它的具體實現(xiàn)類常用的有ArrayList和LinkedList8若一個過程直接地或間接地調(diào)用自己,則稱這個過程是 遞歸的過程9若某完全二叉樹的高度為h,則該完全二叉樹中至少有個結(jié)點(diǎn)10對一棵二叉搜索樹進(jìn)行前序遍歷時， 得到的結(jié)點(diǎn)序列是一個 序列。三、綜合題（每小題6分，共30分）.已知一棵二叉樹的前序遍歷的結(jié)果序列是 ABDEGCF片序遍歷的結(jié)果是DBGEACHF式畫出這棵二叉樹并寫出這棵二叉樹的后序遍歷結(jié)果。 DGEBHFCA.請寫出右圖的鄰接矩陣、鄰接表和邊集數(shù)組.設(shè)一個關(guān)鍵字序列為｛26,53,67,48,57,13,48,32,60,50｝分別寫出直接插入排序、希爾排序、冒泡排序、快速排序、選擇排序、歸并排序的前二趟的排序序列...分別用purim算法和構(gòu)造右圖的最小生成樹并寫出構(gòu)造過程.四、程序填空（每空格2分，共20分）1下面十進(jìn)制轉(zhuǎn)二進(jìn)制的算法.請在空白處填入適當(dāng)?shù)膬?nèi)容。publicclassbinary{publicstaticvoidwriteBinary(intn,Strings1){if(n<0)① thrownewIllegalArgumentException();if(n<=1){s1=1+s1;System.out.println(sl);}else{s1=② n%2+s1;③writeBinary(n/2,s1);}23下面是棧的類定義，請在空白處填入適當(dāng)?shù)膬?nèi)容publicclassStack{inttop=-1;intsize=0;Object口arr;publicStack(intcapacity){arr=new①Object[capacity];}publicvoidpush(Objecte){top++;arr[top]=②e;size++;}publicObjectpop(){Objectt=arr[top];top--；size--;returnt;}…}五、算法分析和設(shè)計題(共20分)1、指出下列算法的功能并求出其時間復(fù)雜度intCount(int[][]a,intk){intc=0;for(inti=0;i<a.length;i++)for(intj=0;j<a[i].length;j++)If(a[i][i]>=k)c++；returnc;}統(tǒng)計并返回二維數(shù)組a中大于等于k的元素的個數(shù)。時間復(fù)雜度為 O(mxn)，假定m和n分別表示二維數(shù)組a的行數(shù)和列數(shù)2指出下列算法的功能并寫出運(yùn)行結(jié)果publicclassTestPrime{publicstaticvoidmain(stringargs口) {inti,j;For(i=3;i<=30;i++){For(j=2;j<i;j++);{If(i%j==0){Bresk;}}If((j<i){Continue;

}System.out.print(i+"")}}}3編寫一個函數(shù)，要求借助一個棧把一個數(shù)組中的元素逆置PublicstaticObject口ReverseArray(Object口array)PublicstaticObject口ReverseArray(Object口array){if(array==null||array.length==0)returnarray;Stackstack=newStack(array.length);for(inti=0;i<array.length;i++)stack.push(array[i]);for(inti=0;i<array.length;i++)array[i]=stack.pop();returnarray;)4從鏈接存儲的線性表list中刪除與obj相同的所有元素

publicstaticvoiddeleteAll(linkListlist,Objectobj){ // 從參數(shù)線性表list中刪除與obj相同的所有元素Nodep=list.prior(),head=p;//listNodeq=p.next; //while(q!=head){ //if(q.element.equals(obj