《數(shù)據(jù)結(jié)構(gòu)》期末復習題

浙江廣播電視大學《數(shù)據(jù)結(jié)構(gòu)》期末復習題2005年12月一、單選題1．某程序的時間復雜度為（3n+nlog2n+n2+8）,其數(shù)量級表示為（）。A．O（n）B．O（nlog2n）C．O（n2）D．O（log2n）2．隊列的插入操作是在（）進行。A．隊首B．隊尾C．隊前D．對后3．二叉樹上葉結(jié)點數(shù)等于（）。A．分支結(jié)點數(shù)加1B．單分支結(jié)點數(shù)加1C．雙分支結(jié)點數(shù)加1D．雙分支結(jié)點數(shù)減14．每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做（）排序A．插入B．交換C．選擇D．歸并5．在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。A．2B．1C．3D．46．隊列的刪除操作是在（）進行。A．隊首B．隊尾C．隊前D．對后7．當利用大小為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？?，則退棧時，用（）語句修改top指針。A．top++;B．top=0;C．top--;D．top=N;8．由權(quán)值分別為3,6,7,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。A．51B．23C．53D．749．在一棵二叉樹中，第4層上的結(jié)點數(shù)最多為（）。A．31B．8C．15D．1610．向堆中插入一個元素的時間復雜度為（）。A．O(log2n)B．O(n)C．O(1)D．16O(nlog2n)11．在一個長度為n的順序存儲的線性表中，向第i個元素（1≤i≤n+1）之前插入一個新元素時，需要從后向前依次后移（）個元素。A．n-iB．n-i+1C．n-i-1D．i12．在線性表的散列存儲中，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則裝填因子等于（）。A．n/mB．m/nC．n/(n+m)D．m/(n+m)13．從一棵B_樹刪除元素的過程中，若最終引起樹根結(jié)點的合并，則新樹高度是（）。A．原樹高度加1B．原樹高度減1C．原樹高度D．不確定14．在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點都具有相同的（）。A．行號B．列號C．元素值D．地址15．在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要（）條邊。A．nB．2nC．n-1D．n+116．某程序的時間復雜度為（10n+nlog2n+n2）,其數(shù)量級表示為（）。A．O（n）B．O（nlog2n）C．O（n2）D．O（log2n）17．在一個長度為n的順序存儲的線性表中，向第i個元素（1≤i≤n+1）之前插入一個新元素時，需要從后向前依次后移（）個元素。A．n-iB．n-i+1C．n-i-1D．i18．在一棵二叉搜索樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定（）該結(jié)點的值。A．小于B．大于C．不小于D．大于等于19．對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為（）。A．n-1B．nC．n+1D．2n20．某程序的時間復雜度為（3n+100×log2n+nlog2n）,其數(shù)量級表示為（）。A．O（n）B．O（nlog2n）C．O（100）D．O（log2n）21．在一個單鏈表中,若q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點,若在q與p之間插入一個s所指的結(jié)點,則執(zhí)行()。A．s→link=p→link;p→link=s;B．p→link=s;s→link=q;C．p→link=s→link;s→link=p;D．q→link=s;s→link=p;22．根據(jù)n個元素建立一棵二叉搜索樹時，其時間復雜度大致為（）。A．O(n)B．O(log2n)C．O(n2)D．O(nlog2n)二、填空題1．一個算法應(yīng)具備的5個特性為、、、、。2．在采用獨立結(jié)點構(gòu)成的雙向鏈表中，設(shè)p和q分別是具有Dnode*類型的指針變量。若雙向鏈表中p結(jié)點之后插入一個q結(jié)點，其操作步驟為：；；；；3．表示圖的三種存儲結(jié)構(gòu)為、和。4．假定一棵二叉樹廣義表表示為a(b(c,d)，e(,f))，則對它進行的先序遍歷結(jié)果為____________，中序遍歷結(jié)果為____________，后序遍歷結(jié)果為____________，按層遍歷結(jié)果為____________。5．當從一個小根堆中刪除一個元素時，需要把________元素填補到________位置，然后再按條件把它逐層________調(diào)整。6．二叉搜索樹的中序遍歷得到的結(jié)點序列為________。7．數(shù)據(jù)的存儲結(jié)構(gòu)被分為____________、___________、____________和____________四種。8．若對一棵二叉樹的結(jié)點編號從0開始順序編碼，按順序存儲，把編號為0的結(jié)點存儲到a[0]中，其余類推，則a[i]元素的左孩子元素為________，右孩子元素為________，雙親元素(i>0)為________。9．從一個棧刪除元素時，首先取出，然后再前移一位。10．后綴表達式“210+5*6–9/”的值為。11．假定一棵樹的廣義表表示為A(B(C(D,E),F,G(H,I,J)),K)，則度為3、2、1、0的結(jié)點數(shù)分別為______、______、______和______個。12．在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。13．在索引表中，若一個索引項對應(yīng)主表中的一條記錄，則稱此索引為________索引，若對應(yīng)主表中的若干條記錄，則稱此索引為________索引。14．對于二分查找所對應(yīng)的判定樹，它既是一棵_____，又是一棵__________。15．對于雙目操作符，其重載函數(shù)帶有__________個參數(shù)，其中至少有一個為____________的類型。16．從一維數(shù)組a[n]中順序查找出一個最大值元素的時間復雜度為________，輸出一個二維數(shù)組b[m][n]中所有元素值的時間復雜度為________。17．在歸并排序中，進行每趟歸并的時間復雜度為________，整個排序過程的時間復雜度為________，空間復雜度為________。18．在一棵m階B_樹上，每個非樹根結(jié)點的關(guān)鍵字數(shù)目最少為________個，最多為________個，其子樹數(shù)目最少為________，最多為________。19．當從一個小根堆中刪除一個元素時，需要把________元素填補到________位置，然后再按條件把它逐層________調(diào)整。20．快速排序在平均情況下的時間復雜度為________，在最壞情況下的時間復雜度為________。21．從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結(jié)點的值，則表明_______，若元素的值小于根結(jié)點的值，則繼續(xù)向________查找，若元素的大于根結(jié)點的值，則繼續(xù)向________查找。22．在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則應(yīng)執(zhí)行語句：。23．若對一棵二叉樹的結(jié)點編號從0開始順序編碼，按順序存儲，把編號為0的結(jié)點存儲到a[0]中，其余類推，則a[i]元素的左孩子元素為________，右孩子元素為________，雙親元素(i>0)為________。24．在循環(huán)單鏈表中，最后一個結(jié)點的指針域指向________結(jié)點。25．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則結(jié)點D的雙親結(jié)點為________，孩子結(jié)點為___________。26．后綴表達式“216+5–6–9*”的值為。27．在一棵高度為5的理想平衡樹中，最多含有________個結(jié)點，最少含有________個結(jié)點。28．二叉搜索樹的中序遍歷得到的結(jié)點序列為________。29．在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為________________和____________________。30．假定一個線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個字母進行劃分，使得同一個字母被劃分在一個子表中，則得到的a,b,c三個子表的長度分別為________、________和________。三、運算題1．已知一個中綴算術(shù)表達式為：3+4*(25-(6/15))-8@，寫出對應(yīng)的后綴算術(shù)表達式。2．對以下圖，試給出一種拓撲序列，若在它的鄰接表存儲結(jié)構(gòu)中，每個頂點鄰接表中的邊結(jié)點都是按照終點序號從大到小鏈接的，則按此給出唯一一種拓撲序列。002531469873.空堆開始依次向堆中插入線性表（64,52,12,48,45,26）中的每個元素，請以線性表的形式給出每插入一個元素后堆的狀態(tài)。（為小根堆）４．在一份電文中共使用五種字符：A，G，F(xiàn)，U，Y，Z，它們的出現(xiàn)頻率依次為12,9,18,7,14，11，求出每個字符的哈夫曼編碼。5．假定一個待散列存儲的線性表為(37,65,25,73,42,91,45,36,18,75)，散列地址空間為HT[12]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長度。6．對于下圖，若按照克魯斯卡爾算法產(chǎn)生最小生成樹，寫出得到的各條邊的次序。312314312314255106420255106420198933198933753175311334151334157．有七個帶權(quán)結(jié)點，其權(quán)值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹，并計算出帶權(quán)路徑長度WPL。

8。已知一組記錄的排序碼為（46，79，56，38，40，80,95，24），寫出對其進行快速排序的每一次劃分結(jié)果。9．已知一個中綴算術(shù)表達式為：25-（6/15）+（15/8）@，寫出對應(yīng)的后綴算術(shù)表達式。10．在一份電文中共使用五種字符：A，G，F(xiàn)，U，Y，Z，它們的出現(xiàn)頻率依次為4,9,8,17,14，11，求出每個字符的哈夫曼編碼。11．一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）=key%13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。四、閱讀算法，回答問題1．intAA(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p->data==x)n++;p=p->next;}returnn;}對于結(jié)點類型為LNode的單鏈表，以上算法的功能為：2．intBB(ElemTypeA[],intn,KeyTypeK){for(inti=0;i<n;i++)if(A[i].key==K)break;if(i<n)returni;elsereturn–1;}該算法的功能是：3．voidCC(Stack&S){Pop(S);Push(S,50);Push(S,45);Peek(S);}假定調(diào)用算法時棧S中已有2個元素（23，16）的棧，其中23時棧底，調(diào)用后得到的棧內(nèi)容為（從棧底開始排列）：4．voidDD(ElemTypeA[],intn){ElemTypex;inti,j,flag;for(i=1;i<n-1;i++){flag=0;for(j=n-1;j>=i;j__)if(A[j].stn<A[j-1].stn){x=A[j];A[j]=A[j-1];A[j-1]=x;flag=1;}if(flag==0)return;}}該算法的功能是什么，一般稱為什么算法？5．voidEE(LNode*HL,constElemType&item){LNode*newptr=newLnode;newptr->data=item;LNode*p=HL;while(p->next!=HL)p=p->next;newptr->next=HL;p->next=newptr;}對于結(jié)點類型為LNode的單鏈表，以上算法的功能為：6．voidFF(List&L){inti=0;while(i<L.size){intj=i+1;while(j<L.size){if(L.list[j]==L.list){for(intk=j+1;k<L.size;k++)L.list[k-1]=L.list[k];L.size--;}elsej++;}i++;}}以上算法的功能為：7．voidGG(BTreeNode*&BST){ElemTypea[6]={45，23，78，35，77，25}；BST=NULL；for(inti=0,i<6;i++)Insert(BST,a[i]);}調(diào)用該算法后，生成的二叉搜索數(shù)的中序序列為：8．voidHH(){ElemTypeA[]={1,3,5,7,9,2,4,6,8,10},B[10];TwoMerge(A,B,0,4,9);for(inti=0;i<10;i++)cout<<B[i]<<”“;cout<<endl;}調(diào)用該算法后，輸出結(jié)果為：9．voidII(LNode*&HL){LNode*p=HL;HL=NULL;while(p!=NULL){LNode*q=p;p=p->next;q->next=HL;HL=q;}}對于結(jié)點類型為Lnode的單鏈表，以上算法的功能為：10．voidJJ(List&La){InitList(La);inta[]={78,26,56,27,34,42};for(i=0;i<3;i++)InsertFront(La,a[i]);for(i=3;i<6;i++)InsertRear(La,a[i]);TraverseList(La);}該算法執(zhí)行后得到的線性表La為：11．voidKK(BTreeNode*BT){if(BT!=NULL){cout<<BT->data;if(BT->left!=NULL||BT->right!=NULL){cout<<’(’;KK(BT->left);if(BT->right!=NULL)cout<<’,’;KK(BT->right);cout<<’)’;}}}以上算法的功能為：12．voidLL(GLNode*GL){intmax=0;while(GL!=NULL){if(GL->tag==true){intdep=LL(GL->sublist);if(dep>max)max=dep;}GL=GL->next;}returnmax+1;}以上算法的功能為：13．voidCC(Stack&S){Pop(S);Push(S,50);Push(S,45);Peek(S);}假定調(diào)用算法時棧S中已有2個元素（23，16）的棧，其中23時棧底，調(diào)用后得到的棧內(nèi)容為（從棧底開始排列）：14．寫出以下函數(shù)的功能。boolAA(BtreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;else{if(item==BST→data){item=BST→dta;returntrue;}elseif(item<BST→data)returnfind(BST→left,item);elseretrunfind(BST→right,item);}}五、編寫算法1．編寫一個算法，返回搜索樹中的關(guān)鍵字最小的元素值。2．編寫一個非遞歸算法，在稀疏有序索引表中二分查找出給定值K所對應(yīng)的索引項，即索引值剛好大于等于K的索引項，返回該索引項的start域的值，若查找失敗則返回-1。3．編寫對二叉樹進行中序遍歷的非遞歸算法。4．編寫從類型為List的線性表L中刪除其值等于給定值x的第一個元素的算法，假定該線性表不為空。要求若刪除成功返回true，否則返回false。boolDelete(List&L,ElemTypex){5．寫出向以BST為樹根指針的二叉搜索樹上插入值為item的結(jié)點的遞歸算法。voidInsert(ABTListBST,constElemType&item){參考答案一、單選題1．C2．B3．C4．A5．A6．A7．A8．A9．B10．A11．C12．A13．B14．A15．C16．C17．C18．B19．A20．B21．D22．D二、填空題1．有窮性、確定性、可行性、輸入、輸出2．q->right=p->right;if(p->right)p->right->left=q;q->left=p;p->right=q;3．鄰接距陣、鄰接表、邊集數(shù)組4．a(chǎn)bcdefcbdaefcdbfeaabecdf5．堆尾、堆頂、向下6．有序序列7．順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)8．2i+1、2i+2、9．棧頂元素、棧頂指針10．611．2、2、0、712．n(n-1)/2、n(n-1)13．稠密、稀疏14．二叉搜索樹、理想平衡樹15．2、用戶定義16．O(n)、O(m*n)17．O(n)、O(nlog2n)、O(n)18．、m-1、、m19．堆尾、堆頂、向下20．O(nlog2n)、O(n2)21．查找成功、左子樹、右子樹22．p->next=HL;HL=p;23．2i+1、2i+2、24．表頭25．B、EFG26．6327．31、1628．有序序列29．HL→next=NULL、HL=HL→next30．3、3、2三、運算題1．后綴算術(shù)表達式：3425615/－*＋8－@2．拓撲序列為（64）（52，64）（12，64，52）（12，48，52，64）（12，45，52，64，48）（12，45，26，64，48，52）4．A：111G：011F：10U：010Y：00Z：110（或0、1相反）5．012345678910117373652537189145364275∧∧∧∧∧平均查找長度ASL=(7*1+2*2+3*1)/10=1.46．（3，4）5，（0，1）8，（4，5）9，（4，7）10，（2，4）14，（1，3）15，（4，6）317.帶權(quán)路徑長度WPL=131。哈夫曼樹為：50502129101114155678328．[382440]46[56809579]24[3840]46[56809579]24384046[56809579]2438404656[809579]243840465679[8095]24384046567980959．后綴算術(shù)表達式：25615/-158/+@10．帶權(quán)路徑長度WPL=158。哈夫曼樹為：262663143717201291148A：000G：100F：001U：11Y：01Z：101（或0和1相反）11．0123456789101112012345678910111278150357452031233612查找成功的平均查找長度：ASLSUCC=14/10=1.4四、閱讀算法，回答問題1．統(tǒng)計單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)。2．在具有n個元素的順序表A中，順序查找關(guān)鍵字為K的元素。3．棧內(nèi)容為（從棧底開始排列）：23，50，45。4．對數(shù)組A中的n個元素進行排序，稱為起泡算法。5．向單鏈表的末尾添加一個元素。6．刪除線性表中所有重復的元素。7．2325354577788．123456789109．將一個單