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

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