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

浙江財經(jīng)學(xué)院東方學(xué)院課程期末考試試卷第2頁，共6頁專業(yè)、班級：學(xué)號：姓名：密封線浙江財經(jīng)學(xué)院東方學(xué)院2010～2011學(xué)年第一學(xué)期專業(yè)、班級：學(xué)號：姓名：密封線《數(shù)據(jù)結(jié)構(gòu)》課程期末考試試卷（A卷）考核方式：閉卷考試日期：2010年月日適用專業(yè)、班級：東方電子商務(wù)專業(yè)題號一二三四五六總分得分評卷人（共六大題）說明：請考生將答案寫在答題紙上；考試時間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／2C．n(n+1)D.n(n+1)/23..下面算法的時間復(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é)點的引用為p，在p結(jié)點后面插入一個值為x的新結(jié)點的操作為(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)6假定利用數(shù)組a順序存儲一個棧，用top表示棧頂指針，top-=-1表示?？?，并已知棧不為空，當(dāng)退棧并返回棧頂元素時所執(zhí)行的操作為(B)。A.returna[--top];B.returna[top--];C.rcturna[++top];D.returna[top++];7若讓元素1．2.3依次進棧．則出棧次序不可能出現(xiàn)(C)的情況。A3.2.1B.2,1,3C.3,1,2D.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é)點的度等于所有結(jié)點數(shù)加(C)。A．0B．1C．-1D．211在一棵具有35個結(jié)點的完全二叉樹中，該樹的深度為(A)。A．6B．7C．5D．812在一棵具有n個結(jié)點的二叉樹的第i層上，最多具有(C)個結(jié)點。A．2iB．2i+1C．2i-1D．2n13n個頂點的連通圖至少包含有(A)條邊。A．n-lB．nC．n+114為了實現(xiàn)圖的廣度優(yōu)先搜索遍歷．其廣度優(yōu)先搜索算法使用的一個輔助數(shù)據(jù)結(jié)構(gòu)為(B)。A．棧B．隊列二叉樹D．樹15在對n個元素進行直接選擇排序的過程中．需要進行(C)趟選擇和交換。AnB．n+lC．n-lD．n/2二、填空題（每空1分，共15分）1算法可用文字、高級程序設(shè)計語言或類同于高級程序設(shè)計語言的偽碼______描述2．?dāng)?shù)據(jù)的物理存儲結(jié)構(gòu)分為順序和____鏈?zhǔn)絖______二種。3當(dāng)待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_______________排序4一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n，其數(shù)量級表示為_____。5任何集合框架都包含三大塊內(nèi)容：對外的接口、_____接口的實現(xiàn)和對集合運算的算法。6設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有______條邊才能確保是一個連通圖。7List接口對Collection進行了簡單的擴充，它的具體實現(xiàn)類常用的有ArrayList和_____LinkedList8若一個過程直接地或間接地調(diào)用自己,則稱這個過程是_____遞歸的過程9若某完全二叉樹的高度為h，則該完全二叉樹中至少有______個結(jié)點10對一棵二叉搜索樹進行前序遍歷時，得到的結(jié)點序列是一個__________序列。三、綜合題（每小題6分，共30分）已知一棵二叉樹的前序遍歷的結(jié)果序列是ABDEGCFH，中序遍歷的結(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下面十進制轉(zhuǎn)二進制的算法.請在空白處填入適當(dāng)?shù)膬?nèi)容。publicclassbinary{publicstaticvoidwriteBinary(intn,Strings1){ if(n<0) ①thrownewIllegalArgumentException(); if(n<=1){ s1=1+s1; System.out.println(s1); } 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(m×n)，假定m和n分別表示二維數(shù)組a的行數(shù)和列數(shù)2指出下列算法的功能并寫出運行結(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;//list的表頭指針賦給p，并保存到headNodeq=p.next;//使q指向第1個元素結(jié)點,p為q的前驅(qū)while(q!=head){//從頭到尾依次掃描每個結(jié)點