數(shù)據(jù)結(jié)構(gòu)與算法分析模擬試卷

1則執(zhí)行如下()語句序列。A.p=q;p->next=q;B.p->next=q;q->nextC.p->next=q->next;p=q;D.q->next=p->next;p3.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？()A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值A(chǔ).145.由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。6.該二叉樹結(jié)點(diǎn)的前序遍歷的序列為()。7.該二叉樹結(jié)點(diǎn)的中序遍歷的序列為()。EEAGAGFFCCBBDD28.該二叉樹的按層遍歷的序列為(9.下面關(guān)于圖的存儲(chǔ)的敘述中正確的是()。C.用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)2.對(duì)于一個(gè)長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為，在表尾插入元素的時(shí)間復(fù)雜度為。5.當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí)，需要逐層調(diào)整，直到被調(diào)整到位置為止。作為散列函數(shù)，則散列地址為0的元素有個(gè)，散列地址為6的有個(gè)。9.在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為，整個(gè)排序過程的時(shí)間復(fù)雜度為 ,空間復(fù)雜度為。10.在一棵m階B_樹上，每個(gè)非樹根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為個(gè)，最多為 (1)順序存儲(chǔ)表示的示意圖；(2)二叉鏈表存儲(chǔ)表示的示意圖。3.判斷以下序列是否是小根堆?如果不是,將它調(diào)整為小根堆。4.已知一個(gè)圖的頂點(diǎn)集V和邊集3E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹，試寫條邊。intx=Pop(S)+2*Pop(S);inti,a[5]={1,5,8,12,15};for(i=0;i<5;i++)Push(while(!StackEmpty(S))cout<<Pop(S)<<'}該算法被調(diào)用后得到的輸出結(jié)果為：2.voidABC(BTNif(BT->left==NULL&&BT->right==NULL)c2++;}//if}向單鏈表的末尾添加一個(gè)元素的算法。VoidInsertRear(LNode*&HL,constElemType&it{If(______________________){cerr<<"Memoryallocationfailare} if(HL==NULL)HL=4;____________________p->next=newptr;}編寫從類型為List的線性表L中將第i個(gè)元素刪除的算法假定不需要對(duì)i的值進(jìn)行voidDelete(List&L,3.p->next=HS;HS=pH4.2i2i+1□i/2□（或i/2）□m/2□-1m-1□m/2□m2.（1）123456789（2）見圖3所示：(2)是小根堆。4.普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹為：(1,2)3,(1,3)5,(1,4)8,2.該函數(shù)的功能是：統(tǒng)計(jì)出BT所指向的二叉樹newptr==NULLnewptr->=datanewptrp=p->ne{for(intj=i-1;j<L.size-1;j++)L.list[j]=L.list[j+1];5}1.在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HA.HL=p;p->next=HL;B.p->next=HL->next;HL->nextC.p->next=HL;p=HL;D.p->next=A.nB.C.n+13.下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？()4.設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在5.下列關(guān)于二叉樹遍歷的敘述中，正確的是()A.若一個(gè)樹葉是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷C．若一個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最D．若一個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后6.k層二叉樹的結(jié)點(diǎn)總數(shù)最多為().k-1B.2K+1C.2K-1D7.對(duì)線性表進(jìn)行二分法查找，其前提條件是().A.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序B.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序D.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序A.O（1og2n）B.O（n）10.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是(A.數(shù)組是不同類型值的集合B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉6D.用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法表尾插入元素的時(shí)間復(fù)雜度為。4.假定一棵樹的廣義表表示為A（D（E，GH（I，J則樹中所含的結(jié)點(diǎn)數(shù)為_- 應(yīng)的后綴算式為。6.在一棵高度為5的理想平衡樹中，最少含有個(gè)結(jié)點(diǎn)，最多含有有向完全圖中，包含有條邊。的元素成為一個(gè)子表，則得到的四個(gè)子表分別為、 10.對(duì)一棵B_樹進(jìn)行刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并時(shí)示待散列存儲(chǔ)的元素的個(gè)數(shù)，則□等于。4052713試畫出這棵二叉樹。權(quán)權(quán)122552261364547677751122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫出每個(gè)程序段執(zhí)行后所得到的線性表Inta[]={100,26,57,7InsertRear(La,DeleteFron{ifBT{cout<<BT->data<<'';}二分查找的遞歸算法。IntBinsch(ElemTypeA[],intlow,inthigh,Key{if___________________{if()returnmid;//查找成功，返回元素的下標(biāo)elseif(K<A[mid].key)returnBinsch(A,low,mid-1,K);//在左子表上繼elsereturn；/}else；}HL為單鏈表的表頭指針，試寫出在該單鏈表中查找具有給定的元素item的算法。boolFind(LNode*HL,ElemType&item)二、填空題（每空1分，共268：（AABBFFAAABBFFAKCGKCGKDJKDJ3.用克魯斯卡爾算法得到的最小生成樹為：(1,6)1,(2,4)1,(2,5)AFBF II4444222422//822221//82.前序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。五、算法填空（每空2分，共8分）(low<=high)K==A[mid].keyBinsch(A,mid+1,hight,K)retuboolFind(LNode*HL,ElemType&item){if(p->data==item){9}}（）2.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行A.p->next=HL->next;HL->next=p;B.p->next=HL;HLC.p->next=HL;p=HL;D.HL=p;p-3.對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變6.采用開放定址法處理散列表的沖突時(shí)，其8.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的()。10.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為(的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為。2.隊(duì)列的插入操作是在隊(duì)列的進(jìn)行，刪除操作是在隊(duì)列的進(jìn)行。4.對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為，在表尾插入元素的時(shí)間復(fù)雜度為。5.設(shè)W為一個(gè)二維數(shù)組，其每個(gè)第4列的元素共占用＿＿個(gè)字節(jié)。若按行順序存放二維數(shù)組W，其起始地址＿＿二叉樹是指度為2的樹。一棵結(jié)點(diǎn)數(shù)為N的點(diǎn)的度的總和是算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的 。其中個(gè)用于指向孩子，個(gè)指針是空閑的。若對(duì)一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A[0]中。其余類推，則A[i]元素的左孩子元素為 兩種。 排序。三、三、已知一個(gè)6□5稀疏矩陣如右所示，試：（1）寫出它的三元組線性表；（2）給出三元組線性表的順序存儲(chǔ)表示。空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫出：(1)從頂點(diǎn)□出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；(2)從頂點(diǎn)□出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；E={<2,1>,<3,2>,<3,6>,<4,3>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。1.intPrime(intn){inti=1;intx=(int)sqrt(n);if(n%i==0)break;}(1)指出該算法的功能；2.寫出下述算法的功能：voidAJ(adjlistGL,inti,intn){intk=QDelete(Q);{intj=p->adjvex;{}p=p->next;}}如下為二分查找的非遞歸算法，試將其填寫完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){inthigh=n-1;{intmid=if(K==A[mid].key)returnmid;//查找成功，返回元素的下標(biāo)elseif(K<[mid].key); ;}return-1;//查找失敗，返}HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。1.（1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)（2）三元組線性表的順序存儲(chǔ)表示如圖7示。2.如圖8所示。65515132455156373.DFS：□□□□□BFS：□□□□□ 2.功能為：從初始點(diǎn)vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。(low+high)/2high=mid-1{if(HL==NULL){}ElemTypetemp=p-}用()存儲(chǔ)方式最節(jié)省時(shí)間。A.單鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表3.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？()A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元A.15B.145.由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為6.則該二叉樹結(jié)點(diǎn)的前序遍歷的序列為().9.下面的二叉樹中，()不是完全二叉樹。的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為。2.一個(gè)廣義表中的元素分為元素和元素兩類。3.對(duì)于一個(gè)長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為，在表尾插入元素的時(shí)間復(fù)雜度為。 5.棧又稱為表，隊(duì)列又稱為表。為輔序的次序排列。8.以折半（或二分）查找方法從長度為8的有序表中查找一個(gè)元素時(shí)，平均查找長度為 。函數(shù)，則散列地址為0的元素有個(gè)，散列地址為4的有個(gè)。11.在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為，整個(gè)排序過程的時(shí)間復(fù)雜度為 ,空間復(fù)雜度為。應(yīng)主表的若干條記錄，則稱此索引為索引。層遍歷的結(jié)果。先序：中序：后序：按層：3.已知一個(gè)無向圖的頂點(diǎn)集為{a,b,c,d,e},其鄰接矩陣如下所示abcde(1)畫出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先列。E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3按照普里姆算法從頂點(diǎn)0出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。intx=Pop(S)+2*Pop(S);inti,a[5]={2,5,8,22,15};for(i=0;i<5;i++)Puswhile(!StackEmpty(S))cout<<Pop(S)<<'}該算法被調(diào)用后得到的輸出結(jié)果為：if(m==0)returnn+1;elseif(n==0)returnakm(m-1,1);elsereturnakm(m-1,akm(m,n-1));}boolFind(BTreeNode*BST,ElemType&item)if(item==______________){elseif(item<BST->data)BST=BST->elseBST=BST->return}（假定a[0]單元不用）的程序。inthalfsearch(SSTable*a,KeyTypek,intlow,inthigh)4.p->next=HS;HS=pHS=HS->2.先序：a,b,c,d,e,f中序：c,b,a,e,d,f按層：3.（1）該圖的圖形如圖9示：（2）深度優(yōu)先遍歷序列為：abdce4.普里姆：(0,3)2,(0,2)5,(0,1)8,(1,5)6,(4.該函數(shù)的功能是：五、算法填空（共8分，每一空2分）BST->dataleftrightinthalfsearch(SSTable*a,KeyTypek,intlow,inthigh)ifEQ(k,a[mid].key)returnmid;elseifLT(k,a[mid].key)returnhalfsearch(a,k,low,mid-1);elsereturnhalfsearch(a,k,mid}2.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)().4.設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位表示。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)6.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為(k-1B.2K+1C.2K-1D分查找，則查找A［3］的比較序列的下標(biāo)依次為(A.O（1）B.O（n）（）10.設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有()指針域是存放了地址，有個(gè)指針是空指針。分別有個(gè)和個(gè)。7.AOV網(wǎng)是一種 10.向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度 。 。 排序是穩(wěn)定的。3572041E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)184.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時(shí)，每加入一個(gè)數(shù)據(jù)后S1：while(p－>next)}}請(qǐng)回答下列問題：（1）說明語句S1的功能；（2）說明語句組S2的功能；（3）設(shè)鏈表表示的線性表為（a1,a2,…,an）,寫出算法執(zhí)行后的返回值所表示的表。{ifBT{cout<<BT->data<<'';}該算法的功能是：boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)if(item==BST->data){returnelseif(item<BST->data)returnFind(elsereturnFind(}//if}intCountX(LNode*HL,Elem3.用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,4422244222222454548545//\/\/2//\/\/1.（1）查詢鏈表的尾結(jié)點(diǎn)（2）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)（3）返回的線性表為（a2,a3,…,an,a2.遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。五、算法填空（每空2分，共8分）trueBST->leftBST->riintCountX(LNode*HL,Elem{inti=0;LNode*p=HL;//i為計(jì)數(shù)器p=p->next;A）O(n)B）O(n2)C）O(n*i)D）O(n+i)2．設(shè)一個(gè)棧的入棧序列是ABCD，則借助于一個(gè)棧所得到的出棧序列不可能是()。C）ACDBA）單鏈表C）單向循環(huán)鏈表()。A）'BBABABA'B）'BBAAC）'BBAAA'D）'BBABABBA'A）O(n)B）O(n2)C）O(n3)D）O(nlo的地址是(A）8B）9A）O(n)B）O(n2)C）O(nlog2n)D6．隊(duì)列的插入操作在(10．在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有(個(gè)頂點(diǎn)的有向完全圖中，包含有()條弧。法稱為()排序。三、判斷改錯(cuò)題（判斷正誤，將正確的劃上“√”,錯(cuò)誤的劃上“×”,每小題1分，共10)達(dá)式(A-B)*C+D將不會(huì)發(fā)生發(fā)生上溢現(xiàn)象。(結(jié)點(diǎn)之前插入元素x的語句序列。變化情況。度WPL的值。處理沖突，試構(gòu)造哈希表。下面程序的功能是二叉樹的中序遍歷的非遞歸算法，其中二叉樹的結(jié)點(diǎn)結(jié)構(gòu)為充完整。if(!T)returnNULL;while(T->lchild){}}voidBiTree<Type>::Inorder(BiTreeNode<Type>*T,void(*if(t->rchild)elseif(!StackEmpty(S))t=下面程序的功能是用線性探測(cè)再散列處理沖突（即Hi=(H(key)+i)%m哈希函數(shù)為typedefenum{SUCCESS,UNSUCCESS,OVERFLOW}Status;typedefstruct{StatusSerchHashTable(Hinti=0,k=;//i為沖突的次數(shù),k為哈希函數(shù)的值while(i<m&&H.elem[k].key!=NULLKEY&&p->elem.key!=e.ke p=(p+i)%m;elseif(p->elem.key!=e.key)return;H.elem[p].elem=}//if39分）閱讀下面算法，試回答：（1）根據(jù)鄰接表畫出對(duì)應(yīng)的圖；voidAdjGraph<Type>::T(AdjGraph<Type>g;inti){p=g[i].link;p=p->next;序排序，試編寫此算法。算法申明如下：voidLinkList<Type>::Simpl用MidOrder(T->rchild,visvoidBiTree<Type>::PreOrder(BiTreeNode<Type>*T,void(MidOrder(T->lchild,ViMidOrder(T->rchild,Vi}//if_三、判斷改錯(cuò)題（判斷正誤，將正確的劃上“√”,錯(cuò)誤的劃上“×”,每小題1分，共10p->prior->next=s;p->prior=s;WPL=20*2+15*2+14*2+7*3+3*4+4*4NULL++iUNSUCCESSe（2）參考答案：V1V2V4V3（3）參考答案：從頂點(diǎn)Vi出發(fā)進(jìn)行深度優(yōu)先搜索圖。voidLinkList<Type>::Simplp=la->next;if(minp->data>q↑.datap->data=minp->data;}//ifp=p->next;}//ifvoidBiTree<Type>::MidOrder(BiTreeNode<Type>*T,void(MidOrder(T->lchild,ViA）O（n）B）O（()。A）s->next=p->next;p->next=s;B）q->next=s;s->next=p;C）p->next=s-next;s->next=p;D）p->next=s;s-neA）3C）7D）8A）O(n)B）O(n2)C）O(n3)D）O(nloA）順序表C）順序表且是按值遞增或遞減次序排列D）不受上述的任何限制為散列函數(shù)，則與元素18沖突的元素有()個(gè)。A）0C）2D）3值傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。5．在有n個(gè)結(jié)點(diǎn)的單鏈表la中，刪除指定結(jié)點(diǎn)p的操作delete(la,p)的時(shí)間復(fù)雜度為()。8．對(duì)于一個(gè)具有9個(gè)結(jié)點(diǎn)的二叉樹的最小深度為()，最大深度為()排序。三、判斷改錯(cuò)題（判斷正誤，將正確的劃上“√”,錯(cuò)誤的劃上“×”,每小題1分，共105．串的長度是指串中不同字符的個(gè)數(shù)。)7．結(jié)點(diǎn)數(shù)為n的完全二叉樹的深度為log2n+1。9．在順序表中取出第i個(gè)元素所花費(fèi)時(shí)間與i成正比。()基準(zhǔn)，將所有記錄分為兩組，此記錄就排在這兩組的中間，這也是此記錄的最終位置。試給出語句序列。下面程序的功能是二叉樹的層次遍歷的非遞歸算法，其中二叉樹的結(jié)點(diǎn)結(jié)構(gòu)為試將程序補(bǔ)充完整。voidBiTree<Type>::levelorder(BiTreeNode<Type>*T,void(*while(! EnQueue(Q,p->lchild);visit(p->lchild-}EnQueue(Q,p->rchild);visit(p->rchild-}下面程序的功能是用鏈地址法處理沖突，哈希函數(shù)為typedefenum{SUCCESS,UNSUCCESS}Status;typedefstructNode{typedefstruct{StatusSerchHashTablintk=e.key%m;Node<Type>*pre=NULLwhile(p&&p->elem.key!=e.kepre->next=;q->next=NULL;}intMGraph<Type>::cid(MGraph<Type>g){//g是有向圖的鄰接數(shù)組存儲(chǔ)結(jié)構(gòu)inti,j,c=0;while(g.arcs[i,j]==0&&i<g.vexnum)i序排序，試編寫此算法。算法申明如下：voidLinkList<Type>::StraitInsertSort(用PreOrder(T->rchild,VisvoidBiTree<Type>::PreOrder(B