一 單選1、在數據結構的討論中把數據結構從邏輯上分為（CABCD2、采用線性鏈表表示一個向量時，要求占用的空間地址（D 必須是連續 部分地址必須是連續 一定是不連續 可連續可不連3、采用順序搜索方法查找長度為n s→link= p→link=p→link= s→link=p→link= s→link=q→link= s→link=5、如果想在4092個數據中只需要選擇其中最小的5個，采用（ 起泡排 堆排 錦標賽排 快速排 求子 模式匹 串替 D串連列下標j從1到10。所有數組元素相繼存放于續的空間中，則存放該數組至少需要的字數是 8、將一個遞歸算法改為對應的非遞歸算法時，通常需要使用 隊 循環隊 D優先隊9、一個隊列的進隊列順序是1,2,3,4，則出隊列順序為 10A[0..m-1] A(-+%mB(-+%C(-+%mD(-+%11、一個數組元素a[i]與 ）的表示等價 12、若需要利用形參直接實參，則應把形參變量說明為（ ）參數 指 C 變13、下面程序段的時間復雜度為（ for(intfor(intj=0;j<n;j++) B 14、下面程序段的時間復雜度為（ n){if(n==0||n==1) return1; n*f(n-} O(n15、線性表若是采用鏈式結構時，要求內存中可用單元的地址(D)16、數據結構的定義為(D，S)，其中D是 )的集合算 B數據元 數據操 D邏輯結17、算法分析的目的是 A)分析算法的易懂性和文則執行(B)。s->link=p;p-s->link=p->link;p-s->link=p-p->link=s;s-點的直接前驅，若在*q*p*s，則應執行下列哪一個操作 q->link=s;s->link=p p->link=s->link;s->link=p; p->link=s;s->link=q; p->link=p->link-p=p->link;p->link=p->link-p->link=p- p=p->link- rear=rear- rear=rear- rear=rear->link- Ds=rear->link- rear->link->link=s- delete語句是(D)。 current->link=null 23、一個棧的入棧序列為a，b，c，則出棧序列不可能的是( Cc,a,b Da,c,b24、棧的數組表示中，top為棧頂指針，棧空的條件是 )Atop=0 Dtop=-1 都是先進后 B都是先進先C只允許在端點處插入和刪 D沒有共同26、假定一個順序的循環隊列的隊頭和隊尾指針分別為f和r,則判斷隊 f+1= r+1= f= Df=27、當利用大小為n的數組順序一個隊列時，該隊列的最大長度（B n- n- D28、當利用大小為n的數組順序一個棧時，假定用top==n表示棧空，則 ）語句修改top指針。 Btop-- 29、設鏈式棧中結點的結構為（data,link）,topx（ ） top=top->link;x=top->data; x=top;top=top->link; DataType;typedefstruct{DataTypedata[Maxsize]; front,rear;}QueueQ， Q.front== Q.front-Q.rear== Q.front+Q.rear==Maxsize; DQ.front==(Q.rear+1)% fact(int n){if(n<=0) return1; }下面正確的敘述是（ A計算fact(n)需要執行n次遞歸 Bfact(7)=5040C此遞歸算法最多只能計算到fact(8)D以上結論都不對 x if x(n-2)+x(n-}試問計算x(x(8))時需要計算（D）x 8 1833、設有廣義表D(a,b,D),其長度為（B，深度為 34、廣義表A(a),則表尾為（ (() 空 D35、下列廣義表是線性表的有（ E(a,b) E(a,L())36、遞歸表、再入表、純表、線性表之間的關系為（ 再入表>遞歸表>純表>線性 遞歸表>線性表>再入表>純 遞歸表>再入表>純表>線性 D遞歸表>再入表>線性表>純37、某二叉樹的前序和后序序列正好相反，則該二叉樹一定是（B）的二叉 空或只有一個結 B高度等于其結點 任一結點無左孩 D任一結點無右孩 An0= Bn2= Cn0= D3911，8，6，2，5路徑長度為（B）A C D40、已知一個順序的線性表，設每個結點需占m個單元，若第一個結點的地址為da1,則第I個結點的地址為（A Bda1+I*m Cda1-I*m Dda1+(I+1)*m41、34具有35個結點的完全二叉樹的深度為( C 42、對線性表進行折半搜索時，要求線性表必須（ 以方式且結點按關鍵碼有序排 以數組方式C以數組方式且結點按關鍵碼有序排 D以方式43、順序搜索算法適合于結構為（ ）的線性表 散列 順序 壓縮 D 索引44n（ O（nlogn） O（logn） n- 用（C 求關鍵路徑的方 求最短路徑的Dijkstra方 深度優先遍歷算 廣度優先遍歷算47、在10階B-樹中根結點所包含的關鍵碼個數最多為（C，最少為( 48、對包含n個元素的散列表進行搜索，平均搜索長度為（ C不直接依賴于n D上述都不對 1、數據的邏輯結構被分為集合結構、線性結構、樹形結構、圖形結構2、數據的結構被分為順序結構、結構、索引結構、散列結構四3、一種抽象數據類型包括（數據）和（操作）4pq，pq（模式匹配5 棧、隊列邏輯上都是（線性）結構7棧中存取數據的原 后進先出隊列中存取數據的原（先進先 零個或多個）字符組成的序列（長度為零的串）稱為空串 由一個或多個空格組成的串）9T=”abccdcdccbaa”,P=”cdcc”則第（6）A[0][0]的地址為（n*i+j）。（棧頂指針） (Q.rear+1)%MaxSize==q.front）13n（n-1）145（63）3樹中的結點數為（ ）個┐17、已知具有n個元素的一維數組采用順序結構，每個元素占k個單元，第一個元素的地址為LOC(a1)，那么 LOC(a1)+(i- 為0和10外，還可以最多對（ 20 ）20、由一棵二叉樹的前序序列和（中序序列）21、以折半搜索方法搜索一個線性表時，此線性表必須是（順序）的（有（6871024n=50 （３１９具有n個頂點的無向完全圖中，包含有（n(n-1)/2）條邊，在一個具有n個頂點的有向完全圖中，包含有（n(n-1) 1 位置是(1044)。30ne32、處理的三種方法，分別為(線性探測)（隨機探測（鏈地址法時間復雜度為（Ｏ（elog2e））34、快速排序在平均情況下的時間復雜度為（Ｏ（nlog2n）），在情況下（log2n）），在情況下的空間復雜度為（Ｏ（n））（４６行歸并排序的過程中，第二趟排序后的結果是［３８４６５６７９［４０８０）（４６［３８４０］４６［５６７９８０。37、一個結點的子樹的（個數）稱為該結點的度。度為（零）的結點（零的結點稱為分支結點或非終端結點。樹中各結點度的（最大值）稱為樹的度。38Ki=Kj(1<=i<=n,1<=j<=n,j<>i)RiRj(i<j),Ri仍領先于Rj，則這種排序方法是（穩定的，反之是（不40、在堆排序的過程中，對任一分支結點進行調整運算的時間復雜度為（log2n）），整個排序過程的時間復雜度為（Ｏ（nlog2n））42a,b,c（３（３（２。（４（５45、假定要對長度n=100的線性表進行散列，并采用開散列法處理，（５46、在散列中，裝載因子α又稱為裝載系數，若用m表示散列表的長度，n表示待散列的元素的個數，則α等于（n/m）。47i“1”i（出度，i“1”i（入度im/2┐，最多為（m三 判斷（╳（╳（√（╳（╳（√8（╳9（╳11hh2h-1（╳1213（√15、線性表的順序結構的特點是邏輯關系上相鄰的兩個元素在物理位置上 1819、AOE（√（╳21、二叉排序樹可以是一棵空樹 22、線性表中所有結點的類型必須相同 23n個結點的有向圖若它有n(n－1)條邊則它一定是強連通的 24、任何無環的有向圖，其結點都可以排在一個拓撲序列里。 25、隊列邏輯上是一個下端口和上端能增加又能減少的線性表 26、二叉樹是樹的一種特殊情況（ （√28鄰接表只能用于有向圖的鄰接矩陣對于有向圖和無向圖的都適用293031321（√33、快速排序是對起泡排序的一種改進。 34、直接選擇排序穩定（ 35、堆排序占用的輔助空間很大（ 37B（38、在散列法中，一個可用散列函數必須保證絕對不產生391ni個元素（1in）之前插入一個新ni1 3種 不是合理的出棧序列3、簡單（直接）{}=1{}=2{}=3{ 5124、設有序順序表為{10,20,30,40,50,60,70}，采用折半搜索時，ASLsucc=(1*1+2*2+3*4)/7=17/5n(n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少n1，2n-16hkhk1iimin,hn各層的結點個數是ki i(i+k-2)/kim(i-當(i-1)%k<>0nhn：h=logk(n*(k-1)+1)-1(n=0h=-1)7A*-B+(A+B)*D+E/(F+A*D)+A&&B||!(E C++!(A&&!((B<C)||(C>D)))||(C<8、畫出下列廣義表的圖形表示和它們 表示D(A(c),B(e),C(a,L(b,c,J1(J2(J1,a,J3(J1)),答案：廣義表（1）DDABCcLeabcd廣義表（2）J aAB AB 2CLC1b1L0^2a1C0^22B0A01C1C^1e^1d^廣義表（2） 表示為^20^2a120^2209、題目：11、將下面的森林變換成二叉樹（7ABCABCDEFGHIJKABABECFGDHIJK*+++fgh+**+++fgh+*11（5其中的一個拓撲序列為121（7885467138m=2n-1=2*8-10.230.110.050.030.290.140.070.0814、已知一棵二叉樹的前序遍歷的結果是ABECDFGHIJ,中序遍歷的結果是EBCDAFHIGJ,試畫出這棵二叉樹，并給出這棵二叉樹的后序遍歷序列。ABF GD I這棵二叉樹的后序遍歷序列為15、在結點個數為n(n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少16hAVLAVLh(空樹的高度為-1)AVLNhNh=Fh+3-1。FhAVLn3/2*log2(n+1),最小高度為「log2(n+1)┐-1。17、7-7017,094,154,170,275,503,512,553,612,677,765,897,908

18AOE求每個的最早開始時間Ve[i]和最遲開始時間Vl[i]el，確定哪些活動是關鍵活動。畫出由所有關鍵活動構成的圖哪些活動加，①③②④⑤⑥00①③②④⑤⑥00e00Ll-00808043，關鍵路徑為19第一次排序第二次排序第三次排序ASLsucc=(1+1/(1-))/2)。有：ASLsucc=1/2（1+1/（1-））≤2解得 ≤2/3，又有：=n/m=150/m225voidunknown(intw){if(w)unknown(w-1for(inti=1;i<=w;i++)cout<<w<<'';cout<<endl;}}unknown(4)(1)2233344442voidunknown(intn){cout<<n%10if(int(n/10))unknown(int(n/10)}unknown582答案：2853intunknown(intm){intvalue;if(!m value=elsevalue=unknown(m-1)+5;returnvalue;}coutunknown(3)。答案：1810因為：Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676所以：n=(676-2-所以：Loc(3,3)=5、設單鏈表結構 structListNodeintdataListNode*link下面的程序是以單鏈表為結構,實現二路歸并排序的算法,要求鏈表不另外占用空間,排序過程中不移動結點中的元素,只改各鏈結點中的指針,排序后rrQueue,其可直接使用的相關操作有置空隊列操作：makeEmptyx加入到隊列的隊尾操作：EnQueueListNode*xListNode*DlQueue1,0：intIsEmpty程序首先對待排序的單鏈表進行一次掃描,將它劃分為若干有序的子鏈表,其表頭指針存放在一個指針隊列中。當隊列不空時,從隊列中退出兩個有序子鏈表,對它們進行二路歸并,如果隊列中退出一個有序子鏈表后變成空隊列,則算法結束。這個有序在算法實現時有6(1)歸并算voidmerge(ListNode*ha,ListNode*hb,,ListNode*&hc)ListNode*pa,*pb,*pcif(ha→data<=hb→data){hc=ha;pa=ha→link;pb=hb;}else{hc=hb;pb=hb→link;pa=ha;}pc=while(pa&&pbpa→datapa→data<=( pc→link= pc=papa=} pc→link= pc=pbpb=}if(pa)pc→link=pa;elsepc→link=pb;(2)voidmergesort(ListNode*r)ListNode*s, QueueQif(!r)Q.EnQueue(rQ.EnQueue(rwhile(s)t=while(t!=0&&s→data<=t→data){s= t=link;if(t)Q.EnQueue(ss→link=Q.EnQueue(s=}}while(!Q.IsEmpty())r=Q.DlQueue(if(Q.IsEmpty())s=Q.DlQueue(Q.EnQueue(tmerge(r,Q.EnQueue(tt}}（7）voiddemo2(LinkListhead,ListNode{//head是結點的單鏈表，刪除P指向的結ListNodewhile(q&&q->next!=p)q=q->next;if(q)Error(“*pnotinhead”);}0，閱讀以下程序請回答該程序所實現的功能：temte<classtypevoidlinkedtosequent(Bintreenode<Type>*t,typea[],inti){if(t!=Null){a[]=t-linkedtosequent(t-主程序調用方式（數組8HT[13],散列函數為H(key)=key%13,對下列關鍵碼序列12,23,45,57,20,03,78,31,15,36采用線性探查法尋找下一個空位,畫出相應的散列表,并計算等概率采散列法尋找下一個空位,再散列函數為RH(key)=(7*key)%+1,尋找下一個空位的為Hi=(Hi-1+RH(key))%13,H1=H(key)。畫出相應的散列表,并計算等概率下搜索成功的平均搜索長度。H(key)=keymod13H（12）=12，0101234567891111114121ASLsuccASLunsucc利散列法造表Hi=（Hi-1 Hi012345678911111135119、閱讀下面程序，其算法的功能并求出其時間復雜度intPrime(intinti=2,x=(int)sqrt(n);}if(i>x)returnelsereturn}(2)intsum1(intn){intp=1,s=0;for(int }（1）0，程序功能是計算∑ni!， intsymmetry(DblListDL){intsym=1;DblNodep=DL->rLink,q=DL->lLink;While(p!=q&&p->lLink==q)&&sym==1 if(p->data==q->data){q=q-}elsesym=0;return11、閱讀下面程序，其算法的功#includeintBaseTrans(intN,intB){inti,result=0;Stack<int>S;return}NBB12、閱讀下面程序，其算法的功temte<classTypevoidBinaryTree<Type>::binsearchTree(BinTreeNode<Type>*t,int&bs){(t->rightchild==Null||t->data<t->rightchild->data)){binsearchTree(t- binsearchTree(t-}else 答案：該算法是判別給定的以二叉鏈表的二叉樹是否是二叉搜索樹。采用遞，結點后面，使得鏈表中所有結點保持按頻度遞減的順序排列，以使頻繁，chardata;intDoubleListNode*locate(DoubleListNode*f;char&x)DoubleListNode*p,p=f→rlink; while(p!=NULL&&p→data!=x) p=p→rlink;/*搜索*/if(p){p→freq q=p→rlink→llink q→rlink /*從鏈中while(q!=f&&q→freq<p→freq)qp→llink=p→rlink=q→rlink; q→rlink=p; /*qp*/}return}2A[n]Ann答案：#includeclassRecurveArray{int*Elements;intArraySize;intCurrentSize;RecurveArray(intMaxSize=10):ArraySize(MaxSize),Elements(newint[MaxSize]){}~RecurveArray(){delete[]Elements;}voidInputArray();intMaxkey(intn);intsum(intn);floatAverage(intvoidRecurveArray::InputArray(){cout<<”Inputthenumberof Array:\n”;for i=0;i< cin>>}intRecurveArray::Maxkey(intn){if(n==1)return inttemp=Maxkey(n-1); returnElements[n-1];elsereturntemp;}intRecurveArray::Sum(intn){if(n==1) elsereturnElements[n-1]+Sum(n-} RecurveArray::Average(intn){if(n==1)return(float)Elements[0]; return((float)Elements[n-1]+(n-1)*Average(n-}intmain(intargc,char*argv[]){intsize=1;cout<<”No.oftheElements:”;while(size<1)cin>>size;RecurveArrayra(size);Ra.InputArray();Cout<<”\nThemaxis:”<<ra.Maxkey(ra.MaxSize)<<end1;Cout<<”\nTheSumis:”<<ra.Sum(ra.MaxSize)<<end1;Cout<<”\nTheaveis:”<<ra.Average(ra.MaxSize)<<end1;Return}3n!*2nA[arraySize]n組元素中，0narraySizemaxInt，narraySizek(0kn)k!*2kmaxIntcerrexit(1)在函數的參數表設置一個型的整型變量來區別是正常返回還是某答案：#include“iostream.h”#definearraySize100#defineMaxInt0x7fffffffintcalc(intt[],intn){inti,edge=MaxInt/n/2;if for(i=1;i<n;i++){if(t[i]>ed