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