PAGEPAGE1計算機應用專業（普專）《數據結構》模擬試卷模擬試卷一單選題（每題2分，共20分）以下數據結構中哪一個是線性結構？()A.有向圖B.隊列C.線索二叉樹D.B樹在一個單鏈表HL中，若要在當前由指針p指向的結點后面插入一個由q指向的結點，則執行如下()語句序列。A.p=q;p->next=q;B.p->next=q;q->next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;以下哪一個不是隊列的基本運算？（）A.在隊列第i個元素之后插入一個元素B.從隊頭刪除一個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值字符A、B、C依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成()個不同的字符串？A.14B.5C.6D.8由權值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權路徑長度為()。EAGCBDF圖1A．11EAGCBDF圖1以下6-8題基于圖1。該二叉樹結點的前序遍歷的序列為()。E、G、F、A、C、D、BE、A、G、C、F、B、DE、A、C、B、D、G、FE、G、A、C、D、F、B該二叉樹結點的中序遍歷的序列為()。A.A、B、C、D、E、G、FB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FB、D、C、A、F、G、E該二叉樹的按層遍歷的序列為()。A．E、G、F、A、C、D、BB.E、A、C、B、D、G、FC.E、A、G、C、F、B、DD.E、G、A、C、D、F、B下面關于圖的存儲的敘述中正確的是()。A．用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關B．用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數和結點個數都有關C.用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結點個數和邊數都有關D．用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關設有關鍵碼序列(q，g，m，z，a，n，p，x，h)，下面哪一個序列是從上述序列出發建堆的結果?()A.a，g，h，m，n，p，q，x，zB.a，g，m，h，q，n，p，x，zC.g，m，q，a，n，p，x，h，zD.h，g，m，p，a，n，q，x，z填空題（每空1分，共26分）數據的物理結構被分為_________、________、__________和___________四種。對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。向一個由HS指向的鏈棧中插入一個結點時p時，需要執行的操作是________________;刪除一個結點時，需要執行的操作是______________________________（假設棧不空而且無需回收被刪除結點）。對于一棵具有n個結點的二叉樹，一個結點的編號為i(1≤i≤n)，若它有左孩子則左孩子結點的編號為________，若它有右孩子，則右孩子結點的編號為________，若它有雙親，則雙親結點的編號為________。當向一個大根堆插入一個具有最大值的元素時，需要逐層_________調整，直到被調整到____________位置為止。以二分查找方法從長度為10的有序表中查找一個元素時，平均查找長度為________。表示圖的三種常用的存儲結構為_____________、____________和_______________。對于線性表（70，34，55，23，65，41，20）進行散列存儲時，若選用H（K）=K%7作為散列函數，則散列地址為0的元素有________個，散列地址為6的有_______個。在歸并排序中，進行每趟歸并的時間復雜度為______，整個排序過程的時間復雜度為____________，空間復雜度為___________。在一棵m階B_樹上，每個非樹根結點的關鍵字數目最少為________個，最多為________個，其子樹數目最少為________，最多為________。運算題（每題6分，共24分）圖2寫出下列中綴表達式的后綴形式：圖23X/(Y-2)+12+X*(Y+3)試對圖2中的二叉樹畫出其：順序存儲表示的示意圖；二叉鏈表存儲表示的示意圖。判斷以下序列是否是小根堆?如果不是,將它調整為小根堆。（1）{12,24,33,65,33,56,48,92,86,70}（2）{05,23,20,28,40,38,29,61,35,76,47,100}已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};按照普里姆算法從頂點1出發得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。閱讀算法（每題7分，共14分）voidAE(Stack&S){ InitStack(S); Push(S,3); Push(S,4); intx=Pop(S)+2*Pop(S); Push(S,x); inti,a[5]={1,5,8,12,15}; for(i=0;i<5;i++)Push(S,2*a[i]); while(!StackEmpty(S))cout<<Pop(S)<<'';}該算法被調用后得到的輸出結果為：voidABC(BTNode*BT,int&c1,int&c2){ if(BT!=NULL){ABC(BT->left,c1,c2);c1++;if(BT->left==NULL&&BT->right==NULL)c2++;ABC(BT->right,c1,c2); }//if}該函數執行的功能是什么？算法填空（共8分）向單鏈表的末尾添加一個元素的算法。VoidInsertRear(LNode*&HL,constElemType&item){LNode*newptr;newptr=newLNode;If(______________________){cerr<<"Memoryallocationfailare!"<<endl;exit(1);}________________________=item;newptr->next=NULL;if(HL==NULL)HL=__________________________;else{LNode*P=HL;While(P->next!=NULL)____________________;p->next=newptr;}}編寫算法（共8分）編寫從類型為List的線性表L中將第i個元素刪除的算法，（假定不需要對i的值進行有效性檢查,也不用判別L是否為空表。）voidDelete(List&L,inti)模擬試卷一參考答案單選題（每題2分，共20分）1.B2.D3.A4.B5.B6.C7.A8.C9.B10.B填空題（每空1分，共26分）順序鏈表索引散列O(n)O(1)圖3p->next=HS;HS=pHS=HS->next圖32i2i+1i/2（或i/2）向上根2.9鄰接矩陣鄰接表邊集數組14O(n)O(nlog2n)O(n)m/2-1m-1m/2m運算題（每題6分，共24分）(1)3X*Y2-/1+2XY3+*+（1）（3分）01234567891011121314…18…3112345678…9（2）見圖3所示：(1)不是小根堆。調整為：{12,65,33,70,24,56,48,92,86,33}(2)是小根堆。普里姆算法從頂點1出發得到最小生成樹為：(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)20閱讀算法（每題7分，共14分）30241610210該函數的功能是：統計出BT所指向的二叉樹的結點總數和葉子總數算法填空（共8分，每一空2分）newptr==NULLnewptr->=datanewptrp=p->next編寫算法（8分）voidDelete(List&L,inti){for(intj=i-1;j<L.size-1;j++)L.list[j]=L.list[j+1];//第i個元素的下標為i-1 L.size--;}模擬試卷二單選題（每題2分，共20分）在一個帶有附加表頭結點的單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執行()。A.HL=p;p->next=HL;B.p->next=HL->next;HL->next=p;C.p->next=HL;p=HL;D.p->next=HL;HL=p;若順序存儲的循環隊列的QueueMaxSize=n,則該隊列最多可存儲（）個元素.A.nB.n-1C.n+1D.不確定下述哪一條是順序存儲方式的優點？（）A．存儲密度大B.插入和刪除運算方便C.獲取符合某種條件的元素方便D.查找運算速度快設有一個二維數組A[m][n]，假設A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每個元素占一個空間，問A[2][3](10)存放在什么位置？(腳注(10)表示用10進制表示,m>3)A．658B．648C．633D．653下列關于二叉樹遍歷的敘述中，正確的是()。A.若一個樹葉是某二叉樹的中序遍歷的最后一個結點，則它必是該二叉樹的前序遍歷最后一個結點B．若一個點是某二叉樹的前序遍歷最后一個結點，則它必是該二叉樹的中序遍歷的最后一個結點C．若一個結點是某二叉樹的中序遍歷的最后一個結點，則它必是該二叉樹的前序最后一個結點D．若一個樹葉是某二叉樹的前序最后一個結點，則它必是該二叉樹的中序遍歷最后一個結點k層二叉樹的結點總數最多為().A．2k-1B.2K+1C.2K-1D.2k-1對線性表進行二分法查找，其前提條件是().線性表以鏈接方式存儲，并且按關鍵碼值排好序線性表以順序方式存儲，并且按關鍵碼值的檢索頻率排好序線性表以順序方式存儲，并且按關鍵碼值排好序線性表以鏈接方式存儲，并且按關鍵碼值的檢索頻率排好序對n個記錄進行堆排序，所需要的輔助存儲空間為A.O（1og2n）B.O（n）C.O（1）D.O（n2）對于線性表（7，34，77，25，64，49，20，14）進行散列存儲時，若選用H（K）=K%7作為散列函數，則散列地址為0的元素有（）個，A．1B．2C．3D．4下列關于數據結構的敘述中，正確的是().數組是不同類型值的集合遞歸算法的程序結構比迭代算法的程序結構更為精煉樹是一種線性結構用一維數組存儲一棵完全二叉樹是有效的存儲方法填空題（每空1分，共26分）數據的邏輯結構被分為_________、________、__________和___________四種。一個算法的時間復雜度為(3n3+2000nlog2n+90)/n2，其數量級表示為________。對于一個長度為n的單鏈存儲的隊列，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。假定一棵樹的廣義表表示為A（D（E，G），H（I，J）），則樹中所含的結點數為__________個，樹的深度為___________，樹的度為_________。后綴算式79230+-42/*的值為__________。中綴算式（3+X*Y）-2Y/3對應的后綴算式為_______________________________。在一棵高度為5的理想平衡樹中，最少含有_______個結點，最多含有_______個結點。在樹中，一個結點的直接后繼結點稱為該結點的________。一個結點的直接前趨結點稱為該結點的________。在一個具有10個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。假定一個線性表為(12,17,74,5,63,49,82,36)，若按Key%4條件進行劃分，使得同一余數的元素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。對一棵B_樹進行刪除元素的過程中，若最終引起樹根結點的合并時，會使新樹的高度比原樹的高度___________。在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為________，整個堆排序過程的時間復雜度為________。在線性表的散列存儲中，裝填因子又稱為裝填系數，若用m表示散列表的長度，n表示待散列存儲的元素的個數，則等于________。運算題（每題6分，共24分）在如下數組A中鏈接存儲了一個線性表，表頭指針存放在A[0].next，試寫出該線性表。A01234567data605078903440next4052713已知一棵二叉樹的前序遍歷的結果是ABKCDFGHIJ,中序遍歷的結果是KBCDAFHIGJ,試畫出這棵二叉樹。已知一個圖的頂點集V為：V={1,2,3,4,5,6,7};其共有10條邊。該圖用如下邊集數組存儲：起點1225522613終點6454767775權1122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權值。畫出向小根堆中加入數據4,2,5,8,3,6,10,1時，每加入一個數據后堆的變化。閱讀算法（每題7分，共14分）在下面的每個程序段中，假定線性表La的類型為List，元素類型ElemType為int，并假定每個程序段是連續執行的。試寫出每個程序段執行后所得到的線性表La。InitList(La);Inta[]={100,26,57,34,79};For(i=0;i<5;i++)Insert(La,a[i]);TraverseList(La);DeleteFront(La);InsertRear(La,DeleteFront(La));TraverseList(La);ClearList(La);For(i=0;i<5;i++)InsertFront(La,a[i]);TraverseList(La);現面算法的功能是什么？voidABC(BTNode*BT){ifBT{cout<<BT->data<<'';ABC(BT->left);ABC(BT->right);}}算法填空（共8分）二分查找的遞歸算法。IntBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK) {if___________________{intmid=(low+high)/2;if(_____________________)returnmid;//查找成功，返回元素的下標elseif(K<A[mid].key)returnBinsch(A,low,mid-1,K);//在左子表上繼續查找elsereturn_____________________________；//在右子表上繼續查找}else________________；//查找失敗，返回-1}編寫算法（共8分）HL為單鏈表的表頭指針，試寫出在該單鏈表中查找具有給定的元素item的算法。boolFind(LNode*HL,ElemType&item)模擬試卷二參考答案單選題（每題2分，共20分）1.B2.B3.A4.C5.D6.A7.C8.C9.D10.D填空題（每空1分，共26分）集合結構線性結構樹結構圖結構O(n)O(1)O(1)732943XY*+2Y*3/-1631孩子（或子）結點雙親（或父）結點45n(n-1)（12，36）（17,5,49）（74，82）（63）減少1（或減少）O(log2n)O(nlog2n)n/m運算題（每題6分，共24分）線性表為：（90，40，78，50，34，60）當前序序列為ABKCDFGHIJ，中序序列為KBCDAFHIGJ時，逐步形成二叉樹的過程如下圖4所示：AAAAAAAAFBBFFBFBBFFBGKCGKCHIGJCDKFHIGJGKCGKCHIGJCDKFHIGJHDJHIJDHDJHIJDIKBCD圖4IKBCD用克魯斯卡爾算法得到的最小生成樹為：(1,6)1,(2,4)1,(2,5)2,(5,7)2,(2,6)3,(3,5)7見圖5。222442224445552444455524442238838812221222253553352535533510643104864848106431048648486688圖5閱讀算法（每題7分，共14分）(1)La=(26,34,57,79,100)(2)La=(57,79,100,34)(3)La=(79,34,57,26,100)前序遍歷鏈式存儲的二叉樹。算法填空（每空2分，共8分）(low<=high)K==A[mid].keyBinsch(A,mid+1,hight,K)return-1編寫算法（8分）boolFind(LNode*HL,ElemType&item){LNode*p=HL;whilepif(p->data==item){returntrue;}elsep=p->next;returnfalse;}模擬試卷三單選題（每題2分，共20分）對一個算法的評價，不包括如下（）方面的內容。A．健壯性和可讀性B．并行性C．正確性D．時空復雜度在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，則執行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;對線性表，在下列哪種情況下應當采用鏈表表示？()A.經常需要隨機地存取元素B.經常需要進行插入和刪除操作C.表中元素需要占據一片連續的存儲空間D.表中元素的個數不變一個棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是()A.231 B.321C.312 D.123AOV網是一種（）。A．有向圖B．無向圖C．無向無環圖D．有向無環圖采用開放定址法處理散列表的沖突時，其平均查找長度（）。A．低于鏈接法處理沖突B.高于鏈接法處理沖突C．與鏈接法處理沖突相同D．高于二分查找若需要利用形參直接訪問實參時，應將形參變量說明為（）參數。A．值B．函數C．指針D．引用在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同的（）。A．行號B．列號C．元素值D．非零元素個數快速排序在最壞情況下的時間復雜度為（）。A．O(log2n)B．O(nlog2n)C．0(n)D．0(n2)從二叉搜索樹中查找一個元素時，其時間復雜度大致為()。A.O(n)B.O(1)C.O(log2n)D.O(n2)運算題（每題6分，共24分）數據結構是指數據及其相互之間的______________。當結點之間存在M對N（M：N）的聯系時，稱這種結構為_____________________。隊列的插入操作是在隊列的_________進行，刪除操作是在隊列的__________進行。當用長度為N的數組順序存儲一個棧時，假定用top==N表示?？?，則表示棧滿的條件是_____________________。對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。設W為一個二維數組，其每個數據元素占用4個字節，行下標i從0到7，列下標j從0到3，則二維數組W的數據元素共占用＿_____＿個字節。W中第6行的元素和第4列的元素共占用＿_______＿個字節。若按行順序存放二維數組W，其起始地址為100，則二維數組元素W[6，3]的起始地址為＿________＿。廣義表A=(a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。二叉樹是指度為2的____________________樹。一棵結點數為N的二叉樹，其所有結點的度的總和是_____________。對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個______________。對一棵由算術表達式組成的二叉語法樹進行后序遍歷得到的結點序列是該算術表達式的__________________。對于一棵具有n個結點的二叉樹，用二叉鏈表存儲時，其指針總數為_____________個，其中_______________個用于指向孩子，_________________個指針是空閑的。若對一棵完全二叉樹從0開始進行結點的編號，并按此編號把它順序存儲到一維數組A中，即編號為0的結點存儲到A[0]中。其余類推，則A[i]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。當待排序的記錄數較大，排序碼較隨機且對穩定性不作要求時，宜采用_______________排序；當待排序的記錄數較大，存儲空間允許且要求排序是穩定時，宜采用________________________排序。運算題（每題6分，共24分）已知一個65稀疏矩陣如右所示，試：寫出它的三元組線性表；給出三元組線性表的順序存儲表示。設有一個輸入數據的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個輸入各個數據而生成的二叉搜索樹。對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，試寫出：(1)從頂點①出發進行深度優先搜索所得到的深度優先生成樹；(2)從頂點②出發進行廣度優先搜索所得到的廣度優先生成樹；已知一個圖的頂點集V和邊集E分別為：圖6V={1,2,3,4圖6E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進行排序，試給出得到的拓樸排序的序列。閱讀算法（每題7分，共14分）intPrime(intn){inti=1;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;}指出該算法的功能；該算法的時間復雜度是多少？寫出下述算法的功能：voidAJ(adjlistGL,inti,intn){ QueueQ; InitQueue(Q); cout<<i<<''; visited[i]=true; QInsert(Q,i);while(!QueueEmpty(Q)){ intk=QDelete(Q); edgenode*p=GL[k]; while(p!=NULL) { intj=p->adjvex; if(!visited[j]){ cout<<j<<''; visited[j]=true; QInsert(Q,j); } p=p->next; } }}算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0;inthigh=n-1;while(low<=high){intmid=_______________________________；if(K==A[mid].key)returnmid;//查找成功，返回元素的下標 elseif(K<[mid].key)______________________________________;//在左子表上繼續查找 else__________________________________;//在右子表上繼續查找}return-1;//查找失敗，返回-1}編寫算法（共8分）HL是單鏈表的頭指針，試寫出刪除頭結點的算法。ElemTypeDeleFront(LNode*&HL)模擬試卷三參考答案單選題（每題2分，共20分）1.B2.A3.B4.C5.D6.B7.D8.A9.D10.C填空題（每空1分，共26分）聯系圖（或圖結構）尾首top==0O（1）O（n）128441083365565515132-145-2515637圖7有序序列后綴表達式（或逆波蘭式）2nn-1n+12i+12i+2(i-1)/2開放定址法鏈接法快速歸并運算題（每題6分，共24分）（1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)（2）三元組線性表的順序存儲表示如圖7示。圖8如圖8圖8DFS：BFS：拓樸排序為：4365721閱讀算法（每題7分，共14分）(1)判斷n是否是素數（或質數）（2）O（）功能為：從初始點vi出發廣度優先搜索由鄰接表GL所表示的圖。算法填空（8分）(low+high)/2high=mid-1low=mid+1編寫算法（8分）ElemTypeDeleFront(LNode*&HL){if(HL==NULL){ cerr<<"空表"<<endl;exit(1);}LNode*p=HL;HL=HL->next;ElemTypetemp=p->data;deletep;returntemp;}模擬試卷四單選題（每題2分，共20分）以下數據結構中哪一個是線性結構？()A.有向圖B.棧C.二叉樹D.B樹若某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用()存儲方式最節省時間。A.單鏈表 B.雙鏈表C.帶頭結點的雙循環鏈表 D.單循環鏈表以下哪一個不是隊列的基本運算？（）A.在隊列第i個元素之后插入一個元素B.從隊頭刪除一個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值字符A、B、C、D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成()個不同的字符串？A.15B.14C.16D.21由權值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權路徑長度為()。A．11B.37C.19D.53以下6-8題基于下面的敘述：若某二叉樹結點的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。則該二叉樹結點的前序遍歷的序列為().A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B該二叉樹有（）個葉子。A．3B.2C.5D.4該二叉樹的按層遍歷的序列為()A．E、G、F、A、C、D、BB.E、A、C、B、D、G、FC.E、A、G、C、F、B、DD.E、G、A、C、D、F、B下面的二叉樹中，()不是完全二叉樹。設有關鍵碼序列(q，g，m，z，a)，下面哪一個序列是從上述序列出發建的小根堆的結果?()A.a，g，m，q，zB.a，g，m，z,qC.g，m，q，a，zD.g，m，a，q，z填空題（每空1分，共26分）數據結構是指數據及其相互之間的______________。當結點之間存在1對N（1：N）的聯系時，稱這種結構為_____________________。一個廣義表中的元素分為________元素和________元素兩類。對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。向一個由HS指向的鏈棧中插入一個結點時p時，需要執行的操作是_________________;刪除一個結點時，需要執行的操作是___________________________（假設棧不空而且無需回收被刪除結點）。棧又稱為_______________表，隊列又稱為___________表。在稀疏矩陣所對應的三元組線性表中，每個三元組元素按_________為主序、_________為輔序的次序排列。若一棵二叉樹中只有葉子結點和左、右子樹皆非空的結點，設葉結點的個數為K，則左、右子樹皆非空的結點個數是________。以折半（或二分）查找方法從長度為8的有序表中查找一個元素時，平均查找長度為________。表示圖的三種常用的存儲結構為_____________、____________和_______________。對于線性表（78，4，56，30，65）進行散列存儲時，若選用H（K）=K%5作為散列函數，則散列地址為0的元素有________個，散列地址為4的有_______個。在歸并排序中，進行每趟歸并的時間復雜度為______，整個排序過程的時間復雜度為____________，空間復雜度為___________。在n個帶權葉子結點構造出的所有二叉樹中，帶權路徑長度最小的二叉樹稱為________。WPL稱為_____________________。在索引表中，若一個索引項對應主表的一個記錄，則此索引為__________索引，若對應主表的若干條記錄，則稱此索引為________索引。運算題（每題6分，共24分）寫出下列中綴表達式的后綴形式：3X/(Y-2H)+12+X*(Y+3)假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結果。先序：中序：后序：按層：abcde已知一個無向圖的頂點集為{a,b,c,d,e},其鄰接矩陣如下所示(1)畫出該圖的圖形；（2）根據鄰接矩陣從頂點a出發進行深度優先遍歷和廣度優先遍歷，寫出相應的遍歷序列。已知一個圖的頂點集V和邊集E分別為：V={0,1,2,3,4,5,6,7};E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20};按照普里姆算法從頂點0出發得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。閱讀算法（每題7分，共14分）voidAE(Stack&S){ InitStack(S); Push(S,3); Push(S,4); intx=Pop(S)+2*Pop(S); Push(S,x); inti,a[5]={2,5,8,22,15}; for(i=0;i<5;i++)Push(S,a[i]); while(!StackEmpty(S))cout<<Pop(S)<<'';}該算法被調用后得到的輸出結果為：intakm(unsignedm,unsignedn){ if(m==0)returnn+1; elseif(n==0)returnakm(m-1,1); elsereturnakm(m-1,akm(m,n-1)); }該函數執行的功能是什么？算法填空（共8分）二叉搜索樹的查找——非遞歸算法boolFind(BTreeNode*BST,ElemType&item){while(BST(!=NULL){if(item==______________){item=BST->data;//查找成功returntrue;}elseif(item<BST->data)BST=BST->_____________;elseBST=BST->_____________;}//whilereturn_____________;//查找失敗}編寫算法（共8分）用遞歸的算法編寫出對存入在a[n+1]數組中的n個有序元素進行二分（又稱折半）查找（假定a[0]單元不用）的程序。inthalfsearch(SSTable*a,KeyTypek,intlow,inthigh)模擬試卷四參考答案單選題（每題2分，共20分）1.B2.C3.A4.B5.B6.C7.A8.C9.C10.B填空題（每空1分，共26分）聯系樹（或樹結構）單（子）表O(n)O(1)p->next=HS;HS=pHS=HS->next先進后出先進先出行列k-12.625鄰接矩陣鄰接表邊集數組21O(n)O(nlog2n)O(n)哈夫曼樹帶權路徑長度稠密稀疏運算題（每題6分，共24分）(1)3X*Y2H*-/1+（2）2XY3+*+先序：a,b,c,d,e,f中序：c,b,a,e,d,f后序：c,b,e,f,d,a圖9按層：a,b,d,c,e,f圖9（1）該圖的圖形如圖9示：（2）深度優先遍歷序列為：abdce廣度優先遍歷序列為：abedc普里姆：(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,(6,4)4,(5,7)20閱讀算法（每題7分，共14分）152285210該函數的功能是：求：算法填空（共8分，每一空2分）BST->dataleftrightfalse編寫算法（8分）遞歸算法：inthalfsearch(SSTable*a,KeyTypek,intlow,inthigh){if(low>high)return0;else{intmid=(low+high)/2ifEQ(k,a[mid].key)returnmid;elseifLT(k,a[mid].key)returnhalfsearch(a,k,low,mid-1);elsereturnhalfsearch(a,k,mid+1,high);}}模擬試卷五單選題（每題2分，共20分）棧和隊列的共同特點是()。A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點用鏈接方式存儲的隊列，在進行插入運算時().A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改以下數據結構中哪一個是非線性結構？()A.隊列B.棧C.線性表D.二叉樹設有一個二維數組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。A．688B．678C．692D．696樹最適合用來表示()。A.有序數據元素B.無序數據元素C.元素之間具有分支層次關系的數據D.元素之間無聯系的數據二叉樹的第k層的結點數最多為().A．2k-1B.2K+1C.2K-1D.2k-1若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二分查找，則查找A［3］的比較序列的下標依次為()A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，3對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為A.O（1）B.O（n）C.O（1og2n）D.O（n2）對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數，則散列地址為1的元素有（）個，A．1B．2C．3D．4設有6個結點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。A.5B.6C.7D.8填空題（每空1分，共26分）通常從四個方面評價算法的質量：_________、_________、_________和_________。一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數量級表示為________。假定一棵樹的廣義表表示為A（C，D（E，F，G），H（I，J）），則樹中所含的結點數為__________個，樹的深度為___________，樹的度為_________。后綴算式923+-102/-的值為__________。中綴算式（3+4X）-2Y/3對應的后綴算式為_______________________________。若用鏈表存儲一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，n個結點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有_______個和________個。AOV網是一種___________________的圖。在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。假定一個線性表為(12,23,74,55,63,40)，若按Key%4條件進行劃分，使得同一余數的元素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度___________。在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為________，整個堆排序過程的時間復雜度為________。在快速排序、堆排序、歸并排序中，_________排序是穩定的。運算題（每題6分，共24