1A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點2.用鏈接方式存儲的隊列，在進行插入運算時().A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改4.設有一個二維數(shù)組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在5.樹最適合用來表示()。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)6.二叉樹的第k層的結(jié)點數(shù)最多為().A．2k-1B.2K+1C.2K-1D.2k-17.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標依次為()8.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為A.O（1）B.O（n）C.O（1og2n）D.O（n2）9.對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有個，10.設有6個結(jié)點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。1.通常從四個方面評價算法的質(zhì)量：________、________、________和________。2.一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為_______。3.假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，GH（I，J則樹中所含的結(jié)點數(shù)為_________個，樹的深度為__________，樹的度為________。為____________________________。5.若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有_______個指針域，其中有_______個指針域是存放了地址，有________6.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結(jié)點分別有______個和_______個。8.在一個具有n個頂點的無向完全圖中，包含有_______條邊，在一個具有n個頂點的有向完全圖中，包含有_______條邊。210.向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度__________。11.在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復雜度為_______，整個堆排序過程的時間復雜度為_______。1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next，試寫出該線性表。2.請畫出下圖的鄰接矩陣和鄰接表。3.已知一個圖的頂點集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};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時，每加入一個數(shù)據(jù)后堆的變化。{//L是不帶頭結(jié)點的單鏈表的頭指針if(L&&L->next){q=L；L=L－>next；p=L；}}{ifBT{ABC(BT->left);ABC(BT->right);}}二叉搜索樹的查找—歸算法:boolFind(BTreeNode*BST,ElemType&item)3{returnfalse;//查找失敗item=BST->data;//查找成功return___________;}elseif(item<BST->data)returnFind(______________,item);elsereturnFind(_______________,item);}統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。intCountX(LNode*HL,ElemTypex)4(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B)線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C)線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2．設哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共3．設順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為()。4．設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹5．設某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。6．設某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為。7．設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有個表頭結(jié)點。8．設一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準進行一趟快1.為了能有效地應用HASH查找技術(shù)，必須解決的兩個問題是____________________和2.下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。{}3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.快速排序的最壞時間復雜度為___________，平均時間復雜度為__________。2的結(jié)點數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_______個空指針域。56.設某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_______。7.設一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立1．設一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2．設指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A3．設一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長4．設一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應的二叉樹。5．設有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6．設有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給1．設有一組初始記錄關(guān)鍵字序列（K1，K2，…,Kn要求設計一個算法能夠在O(n)的時間復雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。2．設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈62．下面程序的時間復雜為()for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}2)3)4)3．設指針變量p指向單鏈表中結(jié)點A，若刪除單鏈表中結(jié)點A，則需要修改指針的操作序(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；(C)q=p->next；p->next=q->next；free(q)；(D)q=p->next；p->data=q->data；free(q)；4．設有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（）個輔助記錄單元。2n25．設一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結(jié)束后的結(jié)果為()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，216．設二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為。2)7．設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別8.設某強連通圖中有n個頂點，則該強連通圖中至少有條邊。9．設有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)（）1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種情況。2.設一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有___________個空指針域。3.設輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。4.設有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和75.設哈夫曼樹中共有n個結(jié)點，則該哈夫曼樹中有________個度數(shù)為1的結(jié)點。6.設有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關(guān)系為________。7.__________遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（填先序、中序或8.設查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。9.不論是順序存儲結(jié)構(gòu)的棧還是鏈式存儲結(jié)構(gòu)的棧，其入棧和出棧操作的時間復雜度均為____________。i個結(jié)點的雙親結(jié)點編號為____________，右孩子結(jié)點的編號為___________。一趟快速排序結(jié)果為_____________________的一種拓撲序列為__________________。13.下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。{inti,j;j=i=k%p;}14.下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k，請在下劃線處填上正確的語句。{}二叉樹，并畫出它的后序線索二叉樹。選用的散列函數(shù)是H（K）=Kmod7，若發(fā)生沖突采用線性探查法處理，試：（1）計算出每一個元素的散列地址并在下圖中填寫出散列表：（2）求出在查找每一個元素概率相等情況下的平均查找長度。1．設計在單鏈表中刪除值相同的多余結(jié)點的算法。2．設計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。81．設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為。2．設一棵二叉樹的深度為k，則該二叉樹中最多有（）個結(jié)點。kk-1k-13．設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為。4．在二叉排序樹中插入一個結(jié)點的時間復雜度為。2)5．設某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（）條有向邊。趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。7．設用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作。(A)必須判別棧是否為滿(B)必須判別棧是否為空(C)判別棧元素的類型(D)對棧不作任何則下列等式成立的是。10.設有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不1．設有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復雜度為________，快速排序的平均時間復雜度為_________。2．設指針變量p指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的語句序列為__________________________________________________________（設結(jié)點中的兩個指3．根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4．深度為k的完全二叉樹中最少有____________個結(jié)點。5．設初始記錄關(guān)鍵字序列為(K1，K2，…,Kn)，則用篩選法思想建堆必須從第______個元6．設哈夫曼樹中共有99個結(jié)點，則該樹中有_________個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_____個空指針域。7．設有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的98．設順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_______個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_______個元素。建成的初始堆為______________________。11．設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是____________________。12．設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個數(shù)________第i列上非013．設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為____________。14．設散列函數(shù)H(k)=kmodp，解決沖突的方法為鏈地址法字的指針，不成功時返回標志0。{inti,k;lklist*s;for(i=0;i<m;i++)___________________;for(i=0;i<n;i++){}}AGHIKJIK3、設散列表的地址范圍是[0..9]，散列函數(shù)為H（key）=（key2+2）MOD9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。1．設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。2.設計在鏈式存儲結(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。3.在鏈式存儲結(jié)構(gòu)上建立一棵二叉排序樹。2．設一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為。個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸并后的結(jié)4．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為。(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”5．設一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復雜度為。2)6．設一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，……,度數(shù)為m的結(jié)l+N2+……+Nm(B)l+N2+2N3+3N4+……+(m-1)Nm2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm7．設有序表中有1000個元素，則用二分查找查找元素X最多需要比較次。頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為。9．設輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出10設一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關(guān)鍵字45為基準而得到一趟快速排序的結(jié)果是。(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，801.設有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。2.在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是____________________。3.設有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_______個4.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。5.設一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。6.設一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為________，有__________于頂點i的________，第i列中所有非零元素個數(shù)之和9.下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。{for(i=1;i<=n-1;i++){if(r[j]>r[j+1]){temp=r[j+1];_____________;r[j]=temp;exchange=1;}}}10.下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。{{_____________________________;}}1.設某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。計算最小生成樹各邊上的權(quán)值之和。3.設一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。4.設散列表的長度為8，散列函數(shù)H(k)=kmod7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。1．設計判斷兩個二叉樹是否相同的算法。2．設計兩個有序單鏈表的合并排序算法。1．設一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度2．執(zhí)行一趟快速排序能夠得到的序列是。3．設一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件是。4．時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是。5．設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是。(A)空或只有一個結(jié)點(B)高度等于其結(jié)(C)任一結(jié)點無左孩子(D)任一結(jié)點無右6．一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是。7．設某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為。8．順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為。2)9．二路歸并排序的時間復雜度為。2)（）11.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向?qū)⒁腙犃械慕Y(jié)點X，則入隊列的操作序列為。(A)front->next=s；front=s；(B)s->next=rear；rear=s；(C)rear->next=s；rear=s；(D)s->next=front；front=s；12.設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為。13.設某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有個葉14.設二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復雜度為。2)15.設用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為。4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。()5．設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。()6．層次遍歷初始堆可以得到一個有序的序列。()7．設一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。()9．中序遍歷二叉排序樹可以得到一個有序的序列。()10.快速排序是排序算法中平均性能最好的一種排序。()1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復雜度為_________。2．設指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的新結(jié)點X，則進行插入操作3．設有向圖G的二元組形式表示為G=（D，RD4．設無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_________。6．設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。7．設二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是______________________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復雜度為___________。9．快速排序算法的空間復雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。1．設某無向圖有n個頂點，則該無向圖的鄰接表中有個表頭結(jié)點。2．設無向圖G中有n個頂點，則該無向圖的最小生成樹上有條邊。3．設一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個關(guān)鍵字45為基準而得到的一趟快速排序結(jié)果是。(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，804二叉排序樹可以得到一個從小到大的有序序列。5．設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為。6．程序段s=i=0；do{i=i+1；s=s+i；}while(7．設帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是。8．設某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有。9．設一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為。10.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為。2．當向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。()3．設某堆中有n個結(jié)點，則在該堆中插入一個新結(jié)點的時間復雜度為O(log2n)。()7．先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。()8．由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。()9．線性表中的所有元素都有一個前驅(qū)元素和后繼元素。()10.帶權(quán)無向圖的最小生成樹是唯一的。()1.設指針變量p指向雙向鏈表中的結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為_________=p；s->right=p->right；__________=s；2.設完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。3.設關(guān)鍵字序列為(Kl，K2，…,Kn)，則用篩選法建初始堆必須從第______個元素開始進4.解決散列表沖突的兩種方法是________________和__________________。5.設一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為6.高度為h的完全二叉樹中最少有________個結(jié)點，最多有________個結(jié)點。7.設有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后8.設有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后9.設一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序10.下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。{while(i<j){while(i<j&&r[j].key>x.key)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(__________________)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}}1.設計在鏈式結(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。2.設計在順序存儲結(jié)構(gòu)上實現(xiàn)求子串算法。3.設計求結(jié)點在二叉排序樹中層次的算法。2.建立一個長度為n的有序單鏈表的時間復雜度為()2)3.兩個字符串相等的充要條件是。(A)兩個字符串的長度相等(B)兩個字符串中對應位置上的字符相等4.設某散列表的長度為100，散列函數(shù)H(k)=k%P，則P通常情況下最好選擇。5.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復雜度為。6.設一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。(A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4]7.設一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為。則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為。2.設初始記錄關(guān)鍵字基本有序，則快速排序算法的時間復雜度為O(nlog2n)。()3.分塊查找的基本思想是首先在索引表中進行查找，以便確定給定的關(guān)鍵字可能存在的塊5.向二叉排序樹中插入一個結(jié)點需要比較的次數(shù)可能大于該二叉樹6.如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。()8.不論線性表采用順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，刪除值為X的結(jié)點的時間復雜度均為9.圖的深度優(yōu)先遍歷算法中需要設置一個標志數(shù)組，以便區(qū)分圖中的每個頂點是否被訪問10.稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。()1．設一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為___________________________2．下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結(jié)點，請在下劃線處填上正確的內(nèi){if(t==0){________________}3．設指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：s->next=p->next;_________________;。4．設指針變量head指向雙向鏈表中的則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設結(jié)點中的兩個指針域分別為llink和rlink）。5．設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。6．完全二叉樹中第5層上最少有__________個結(jié)點，最多有_________個結(jié)點。7．設有向圖中不存在有向邊<Vi,Vj>，則其對應的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。8．設一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇9．設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有___________條邊。10．設有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。1.設計一個在鏈式存儲結(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。2.設計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應鄰接表的算法。1．下列程序段的時間復雜度為。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；2．設順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動（）個元素。3．設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結(jié)點數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點的左子樹的結(jié)點數(shù)為。4．利用直接插入排序法的思想建立一個有序線性表的時間復雜度為。5．設指針變量p指向雙向鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后6．下列各種排序算法中平均時間復雜度為O(n2)是。7．設輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列9．設在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的為1的結(jié)點數(shù)有2個，那么度數(shù)為0的結(jié)點數(shù)有個。10.設完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。11.設順序表的長度為n，則順序查找的平均比較次數(shù)為。12.設有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24（）13.設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查14.設有向無環(huán)圖G中的有向邊集合E={<1，215.設有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為。1)s->next=___________；2)p->next=s；3)t=p->data；4)p->data=___________；5)s->data=t；2．設某棵完全二叉樹中有100個結(jié)點，則該二叉樹中有______________個葉子結(jié)點。3．設某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環(huán)隊列中最多存儲_______隊列元素。4．對一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數(shù)為__________，在整個排序過程中最多需要進行__________趟排序才可以完成。5．在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選擇_________排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇________排序。6．設一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是________________________________。7．設一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。8．設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為________________。9．設一組記錄關(guān)鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_______________________。和為_________________。1．有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。()3．子串“ABC”在主串“AABCABCD”中的位置為2。()4．若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。()6．用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊7．中序遍歷一棵二叉排序樹可以得到一個有序的序列。()10．堆是完全二叉樹，完全二叉樹不一定是堆。()1．設計計算二叉樹中所有結(jié)點值之和的算法。2．設計將所有奇數(shù)移到所有偶數(shù)之前的算法。3．設計判斷單鏈表中元素是否是遞增的算法。1．下列程序段的時間復雜度為。2)2．設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（）存儲方式3．設指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為。(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q；4．設輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為。(A)5，3，4，6，1，2(B)3，2，5，6，4，1連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]6．設一棵m叉樹中有N1個度數(shù)為1的結(jié)點，N2個度數(shù)為2的結(jié)點，……,Nm個度數(shù)為m的（）i=1i=1i=2i=27.二叉排序樹中左子樹上所有結(jié)點的值均根結(jié)點的值。8.設一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為。9.設有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH210.設某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n，則這棵二叉11.設一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過（）趟插入排序可以得到有序序列。升序的第一趟冒泡排序結(jié)束后的結(jié)果是。1.設需要對5個不同的記錄關(guān)鍵字進行排序，則至少需要比較_____________次，至多需要比較_____________次。2.快速排序算法的平均時間復雜度為____________，直接插入排序算法的平均時間復雜度為___________。3.設二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_________次。4.設在長度為20的有序表中進行二分查找，則比較一次查找成功的結(jié)點數(shù)有________個，比較兩次查找成功有結(jié)點數(shù)有_________個。5.設一棵m叉樹脂的結(jié)點數(shù)為n，用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_________個6.設指針變量p指向單鏈表中結(jié)點A，則刪除結(jié)點A的語句序列為：q=p->next；p->data=q->data；p->next=___________；feee(q)；7.數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：___________、__________和___________。8.設無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復雜度為_________；用鄰接表作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復雜度為_________。9.設散列表的長度為8，散列函數(shù)H(k)=k%7，用線性探測法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長度是________。10.設一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_____________________。11.設一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結(jié)果為______________________。<6，5>}，則該圖的一個拓撲序列為_________________________。13.下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內(nèi)容。{}14.下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，{for(i=1;i<=n;i++){}}三、算法設計題(22分)1．設計在鏈式存儲結(jié)構(gòu)上合并排序的算法。7.有向無回路8.n(n-1)/2n(n-1)9.（12，407423,55，63）11.O(log2n)O(nlog2n)2.鄰接矩陣EQ\*jc3\*hps31\o\al(\s\up5(1),5)82245（2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點2.遞歸地后序遍歷鏈式存儲的二叉樹。五、法填空（每空2分，共8分）trueBST->leftBST->right六、編寫算法（8分）{inti=0;LNode*p=HL;//i為計數(shù)器while(p!=NULL)}//while,出循環(huán)時i中的值即為x結(jié)點個數(shù)數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案二、填空題1.構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法2.stack.top++，stack.s[stack.top]=x4.O(n2)，O(nlog2n)5.N0-1，2N0+N17.(31，38，54，56，75，80，55，63)三、應用題1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.2,ASL=91*1+2*2+3*4+4*2)=25/94.樹的鏈式存儲結(jié)構(gòu)略，二叉樹略5.E={(1，3)，(1，2)，(3，5)，(5，6)1.設有一組初始記錄關(guān)鍵字序列（K1，K2，…,Kn要求設計一個算法能夠在O(n)的時間復雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。{inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}2.設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈式存儲結(jié)構(gòu)表示。voidintersection(lklist*ha,lklist*hb{lklist*p,*q,*t;}}數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案第3小題分析：首先用指針變量q指向結(jié)點A的后繼結(jié)點B，然后將結(jié)點B的值復制到結(jié)點A中，最后刪除結(jié)點B。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間二、填空題1.順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)14.return(t)，t=t->rchild第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。三、計算題NULLANULLABCDHFKJE1.設計在單鏈表中刪除值相同的多余結(jié)點的算法。{lklist*p,*q,*s;{}}2.設計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。{if(bt!=0&&flag==0)}{inti;}數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案5．C5．C二、填空題1.O(n2)，O(nlog2n)2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink6.50，51三、計算題11^AABCDEKHFGJ44^38^^2^^^2345678906571.設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){{}}2.設計在鏈式存儲結(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。{}3.在鏈式存儲結(jié)構(gòu)上建立一棵二叉排序樹。{}{inti;}數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案二、填空題2.可以隨機訪問到任一個頂點的簡單鏈表i<=k2i&&ki<=k2i+19.n-i，r[j+1]=r[j]三、應用題1.設計判斷兩個二叉樹是否相同的算法。{}2.設計兩個有序單鏈表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){}數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案二、判斷題三、填空題7.p->lchild==0&&p->rchild==01.設計在順序有序表中實現(xiàn)二分查找的算法。{{}}2.設計判斷二叉樹是否為二叉排序樹的算法。{}3.在鏈式存儲結(jié)構(gòu)上設計直接插入排序算法{lklist*s,*p,*q;intt;{}}數(shù)據(jù)結(jié)構(gòu)試卷（七）參考答案6．A7．C8．C9．B10．D二、判斷題6．對7．對8．錯9．錯10．錯三、填空題4.開放定址法，鏈地址法10.i<j&&r[i].key<x.key，r[i]=x1.設計在鏈式結(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。{lklist*p,*q,*s;intmin,t;{}}2.設計在順序存儲結(jié)構(gòu)上實現(xiàn)求子串算法。{else{for(i=start-1,}3.設計求結(jié)點在二叉排序樹中層次的算法。{if(bt!=0)level(bt->rchild,x);}}數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案二、判斷題三、填空題1.設計一個在鏈式存儲結(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。{if(bt!=0)}2.設計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應鄰接表的算法。{for(i=0;i<=n-1;i++)g2[i].for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){}}數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案二、填空題三、判斷題1．設計計算二叉樹中所有結(jié)點值之和的算法。{}2．設計將所有奇數(shù)移到所有偶數(shù)之前的算法。{while(i<j){while(i<j&&r[j]%2==0)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]%2==1)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}3．設計判斷單鏈表中元素是否是遞增的算法。{}數(shù)據(jù)結(jié)構(gòu)試卷（十）參考答案二、填空題7.線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu)三、算法設計題1.設計在鏈式存儲結(jié)構(gòu)上合并排序的算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){}{}{intj=n,i=j/2,temp=r[j-1];while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;}}點，將教學諸要素有序、優(yōu)化地安排，形成教學方案的過程。它是一系統(tǒng)，分析教學問題和需求，確立解決的程序綱要，使教學效果最優(yōu)二、教案是教師的教學設計和設想，是一種創(chuàng)造性勞動。寫一份優(yōu)秀教案是設計者教育思想、智慧、動機、經(jīng)驗、個性和教學藝術(shù)性的所謂符合科學性，就是教師要認真貫徹課標精神，按教材內(nèi)在規(guī)律，結(jié)合學生實際來確定教學目標、重點、難點。設計教學過程，避免出現(xiàn)知識性錯誤。那種遠離課標，脫離教材完整性、系統(tǒng)性，隨心所教材是死的，不能隨意更改。但教法是活的，課怎么上全憑教師的智聽取名家的指點，吸取同行經(jīng)驗，但課總還要自己親自去內(nèi)容變成胸中有案，再落到紙上，形成書面教案，繼而到課堂實際講授，關(guān)鍵在于教師要能”學百家，樹一宗”。在自己鉆研教材的基礎上，廣泛地涉獵多種教學參考資料，向有經(jīng)驗的老師請教．而不要照消化，吸收，獨立思考，然后結(jié)合個人教學體會，巧妙構(gòu)思，精心安個老師的聰明才智和創(chuàng)造力，所以老師的教案要結(jié)合本地區(qū)的特點，所謂教案的藝術(shù)性就是構(gòu)思巧妙，能讓學生在課堂上不僅能學到知識，而且得到藝術(shù)的欣賞和快樂的體驗。教案要成為一篇獨具特色”課堂教學散文”或者是課本劇。所以，開頭，經(jīng)過，結(jié)尾，要層層遞進，扣人心弦，達到立體教學效果。教師的說，談，問，講等課堂語言要字斟句酌，該說的一個字不少說，不該說的一個字也不能說，要教師在寫教案時，一定從實際出發(fā)，要充分考慮從實際需要出發(fā)，要題和看法，教師又不可能事先都估計到。在這種情況下，教學進程常思維的積極性壓下去。要根據(jù)學生的實際改變原先的教學計劃和方點，難點，疑點，和關(guān)鍵。學生能在什么地方出現(xiàn)問題，大都會出現(xiàn)什么問題，怎樣引導，要考慮幾種教學方案。出現(xiàn)打亂教案現(xiàn)象，也不要緊張。要因勢利導，耐心細致地培養(yǎng)學生的進取精神。因為事實上，一個單元或一節(jié)課的教學目標是在教學的一定過程中逐步完成學設計，并以多種媒體的表現(xiàn)方式和超文本結(jié)構(gòu)制作而成的課程軟①教學性課件的應用必須是能優(yōu)化課堂教學結(jié)構(gòu)，提高課堂教學效②可操作性課件的操作要盡量簡便﹑靈活﹑可靠，便于教師和學生③科學性課件制作要符合科學性，不要出現(xiàn)知識性的錯誤。否則用對比，前景與背景對比，線條的粗細，字符的大小，以保證學生都能充分感知對象。避免多余動作、減少每屏文字顯示數(shù)量，盡量用配音⑤藝術(shù)性一個課件的展示不但要追求良好的教學效果，而且不能太大，要適當?shù)亓粲袝r間、空間給學生思考、消化。避免因信息⑦適度使用“寸有所長，尺有所短”。要注意不同教合，優(yōu)勢互補，才能收到事半功倍的教學效果。例如：數(shù)學的方程求演示實驗更直觀更有說服力；理論問題、微觀世界的活動、宏觀世界教學案例是事件：教學案例是對教學過程中的一個實際情境的描述。它講述的是一個