數(shù)據(jù)結(jié)構(gòu)填空題大全

1、數(shù)據(jù)結(jié)構(gòu)填空題大全二、填空題(每題6分，共24分)1 .數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的聯(lián)系。當結(jié)點之間存在M對N(M:N)的聯(lián)系時，稱這種結(jié)構(gòu)為圖或者是圖的結(jié)構(gòu)2 .隊列的插入操作是在隊列的尾進行，刪除操作是在隊列的t進行。3 .當用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則表示棧滿的條件是top=0(要超出才為滿)。4 .對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為0(1)、在表尾插入元素的時間復雜度為0。5 .設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標i從0到7,列下標j從0到3,則二維數(shù)組W的數(shù)據(jù)元素共占用128個字節(jié)。W中第6行的元素和

2、第4列的元素共占用上個字節(jié)。若按行順序存放二維數(shù)組W,其起始地址為100,則二維數(shù)組元素W6,3的起始地址為108q6 .廣義表A=(a,(a,b),(a,b),c),則它的深度為J,它的長度為小_。7 .二叉樹是指度為2的有序樹。一棵結(jié)點數(shù)為N的二叉樹，其所有結(jié)點的度的總和是n-1o8 .對一棵二叉搜索樹進行中序遍歷時，得到的結(jié)點序列是一個有序序列有序列表。對一棵由算術(shù)表達式組成的二叉語法樹進行后序遍歷得到的結(jié)點序列是該算術(shù)表達式的后綴表達式后綴表達式(或列波蘭式)。9 .對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為2n個,其中點的有向完全圖中，包含有n(n-1)條邊。9.假

3、定一個線性表為(12,23,74,55,63,40),若按Key%4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為(12,40)、_()、_(_74)和(23,55,63)。10 .向一棵B樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度增加1。11 .在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復雜度為O(log2n),整個堆排序過程的時間復雜度為O(nlog2n)_。12 .在快速排序、堆排序、歸并排序中，歸并排序是穩(wěn)定的。二、填空題(每空1分，共32分)1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合、線性、稱和圖四種。2、一種抽象數(shù)據(jù)類型包括數(shù)據(jù)描述和操作聲明兩個

4、部分。3、在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為ao.next,則該線性表為(38,56,25,60,42,74)。4、在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為HLnext=NULL和HL=HL-next;。5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的前一個位置,該循環(huán)隊列的最大長度為n-1。6、當堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用S.stackS.top表示:當堆棧采用鏈接存儲結(jié)構(gòu)時，棧頂元素的值可用HS-data表示。7、一棵高度為5的二叉樹中最少含有5個結(jié)點，最多含有31個結(jié)點；8、在圖的鄰接表中，

5、每個結(jié)點被稱為邊結(jié)點,通常它包含三個域：一是鄰接點域；二是權(quán)域;三是鏈域。9、在一個索引文件的索引表中，每個索引項包含對應(yīng)記錄的索引值域和一開始位置域兩項數(shù)據(jù)。10、假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J),則樹中所含的結(jié)點數(shù)為10個，樹的深度為3，樹的度為3,結(jié)點H的雙親結(jié)點為b，孩子結(jié)點為i和J。11、在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復雜度為_O(log2n)_,整個堆排序過程的時間復雜度為O(nlog2n)_o12、在m階的B樹插入元素的過程中，每向一個結(jié)點插入一個索引項(葉子結(jié)點中的索引項為關(guān)鍵字和空指針)后，若該結(jié)點的索引項數(shù)等于M個，則必須

6、把它分裂為M-1個結(jié)點。第二部分非選擇題(共70分)二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。16 .數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(或存儲結(jié)構(gòu))無關(guān),是獨立于計算機的。17 .在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head=p>next>next。18 .棧頂?shù)奈恢檬请S著講棧和遐棧操作而變化的。19 .在串S="structure”中，以t為首字符的子串有12個。20 .假設(shè)一個9階的上三角矩陣

7、A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B0存儲矩陣中第1個元素a1,1，則B31中存放的元素是生。21 .已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有J84個葉子結(jié)點。22 .已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相應(yīng)的廣度優(yōu)先遍歷序列為。23 .在單鏈表上難以實現(xiàn)的排序方法有快速排序和堆排序，希爾排序。24 .在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為2。25 .多重表文件和倒排文件都歸屬于多關(guān)鍵字文件。1.設(shè)順序循環(huán)隊列Q0:m-1的隊頭指針和隊尾指針分別為F和R,其中隊頭指針F指向當前隊頭元素的前一個位置，隊尾指針R

8、指向當前隊尾元素所在的位置，則出隊列的語句為F=(F+1)%m；。2 .設(shè)線性表中有n個數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復雜度為O(n),在鏈式存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復雜度為O(n)。3 .設(shè)一棵二叉樹中有n個結(jié)點，則當用二叉鏈表作為其存儲結(jié)構(gòu)時，該二叉鏈表中共有2n個指針域，n+1個空指針域。4 .設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點B,則在結(jié)點A的后面插入結(jié)點B的操作序列為s->next=p->next;s->next=s。5 .設(shè)無向圖G中有n個頂點和e條邊，則其對應(yīng)的鄰接表中有n個表頭結(jié)點和2e個表結(jié)點。6 .設(shè)無向圖

9、G中有n個頂點e條邊，所有頂點的度數(shù)之和為m,則e和m有_m=2e關(guān)系。7 .設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC,則該二叉樹的后序遍歷序列為_cba。8 .設(shè)一棵完全二叉樹中有21個結(jié)點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點的編號是4,編號為8的左孩子結(jié)點的編號是16。9 .下列程序段的功能實現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。intindex(chars,chart)(i=j=0；while(i<strlen(s)&&j<strlen(t)if(si=tj)i=i+l;j=j+l;elsei=

10、_i-j+1;j=0;if(j=strlen(t)return(i-strlen(t);elsereturn(-1);10 .設(shè)一個連通圖G中有n個頂點e條邊，則其最小生成樹上有n-1條邊。二、填空題(24分)1. 為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是才勾造一個好的HASH函數(shù)和確定解決沖突的方法。2. 下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。typedefstructints100;inttop;sqstack;voidpush(sqstack&stack,intx)if(stack.top=m-1)printf("overflow&

11、quot;);1. elsestack.top+;stack.sstack.top=x;3 .中序遍歷二叉排序樹所得到的序列是有序序列(填有序或無序)。4 .快速排序的最壞時間復雜度為O(n2),平均時間復雜度為O(nlog2n)。5 .設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為N1,則該二叉樹中度數(shù)為2的結(jié)點數(shù)為No-1；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_2No+N1個空指針域。2. 6.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=_d/2_。7 .設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用

12、篩選法建立的初始堆為(31,38,54,56,75,80,55,63)。Vi-3-2-4v2-1-3v3-二1一428 .設(shè)某無向圖G的鄰接表為v4->1->3，則從頂點V1開始的深度優(yōu)先遍歷序列為(1,3,4,2);廣度優(yōu)先遍歷序列為(1,3,2,4)。填空殖(48分，其中最后兩小題各6分)1 .數(shù)據(jù)的物理結(jié)本主要包括順序存儲結(jié)構(gòu)和頂車式存儲結(jié)構(gòu)兩種情況。2 .設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為9;若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有501個空指針域。3 .設(shè)輸入序列為1、2、3,則經(jīng)過棧的作用后可以得到5種不同的輸出序列。4 .設(shè)有向圖G用鄰接矩陣A

13、nn作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點i的出度,第i列上所有元素之和等于頂點i的入度。5 .設(shè)哈夫曼樹中共有n個結(jié)點，則該哈夫曼樹中有_0_個度數(shù)為1的結(jié)點。6 .設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d,則e和d的關(guān)系為e=d。7 .中序遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列(填先序、中序或后序)。8 .設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較7次就可以斷定數(shù)據(jù)元素X是否在查找表中。9 .不論是順序存儲結(jié)構(gòu)的棧還是鏈式存儲結(jié)構(gòu)的棧，其入棧和出棧操作的時間復雜度均為0(1)。10 .設(shè)有n個結(jié)點的完全二叉樹

14、，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為i/2,右孩子結(jié)點的編號為2+。11 .設(shè)一組初始記錄關(guān)鍵字為(72,73,71,23,94,16,5),則以記錄關(guān)鍵字72為基準的一趟快速排序結(jié)果為(5,16,71,23,72,94,73。12 .設(shè)有向圖G中有向邊的集合E=<1,2>,<2,3>,<1,4>,<4,2>,<4,3>,則該圖的一種拓撲序列為(1,4,3,2)。13 .下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。structrecordintkey;intothe

15、rs;inthashsqsearch(structrecordhashtable,intk)inti,j;j=i=k%p;while(hashtablej.key!=k&&hashtablej.flag!=0)j=(_j+1)%m;if(i=j)return(-1);if(hashtablej.key=k)return(j);elsereturn(-1);14 .下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k,請在下劃線處填上正確的語句。typedefstructnodeintkey;structnode*lchild;structnode*rchild;bitree;bitree*b

16、stsearch(bitree*t,intk)if(t=0)return(0);elsewhile(t!=0)if(t->key=k)return(t)elseif(t->key>k)t=t->lchild;else_t=t->rchild;二、填空題(42分)1 .設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復雜度為_O(n2)，快速排序的平均時間復雜度為O(nlog2n)。2 .設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點X,則刪除結(jié)點X需要執(zhí)行的語句序列為p>llink->rlink=p->rlink;p->rlink->llink=

17、p->rlink(設(shè)結(jié)點中的兩個指針域分別為llink和rlink)。3 .根據(jù)初始關(guān)鍵字序列(19,22,01,38,10)建立的二叉排序樹的高度為3_。4 .深度為k的完全二叉樹中最少有2k-1個結(jié)點。5 .設(shè)初始記錄關(guān)鍵字序列為(K1,K2,，Kn),則用篩選法思想建堆必須從第_n/2個元素開始進行篩選。6 .設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有50個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_51一個空指針域。7 .設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲m-1個隊列元素；當前實際存儲_(R-F+M)%M個隊列元素(設(shè)頭指針F指向當前隊頭元素的前一

18、個位置，尾指針指向當前隊尾元素的位置)。8 .設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_n+1-i個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_n-i_個元素。9 .設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則以20為中軸的一趟快速排序結(jié)果為(19,18,16,20,30,22)。10 .設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為(16,18,19,20,32,22)。11 .設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是Ai

19、j=1。12 .設(shè)無向圖對應(yīng)的鄰接矩陣為A,則A中第i上非0元素的個數(shù)一等于_第i列上非0元素的個數(shù)(填等于，大于或小于)。13 .設(shè)前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后序遍歷該二叉樹白序列為BDCA。14 .設(shè)散列函數(shù)H(k)=kmodp,解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標志0。typedefstructnodeintkey;structnode*next;Iklist;voidcreatelkhash(lklist*hashtab

20、le)inti,k;lklist*s;for(i=0;i<m;i+)hashtablei=0;for(i=0;i<n;i+)s=(lklist*)malloc(sizeof(lklist);s->key=ai;k=ai%p;s->next=hashtablek;hashtablek=s;二、填空題(共30分)1 .設(shè)有一個順序共享棧S0:n-1,其中第一個棧項指針topi的初值為-1,第二個棧頂指針top2的初值為n,則判斷共享棧滿的條件是top1+1=top2。2 .在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是可以隨機訪問到任一個頂點的簡單鏈表。3 .設(shè)有一個n階

21、的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對角線上元素)存放在n(n+1)個連續(xù)的存儲單元中，則Aij與A00之間有i(i+1)/2+j-1個數(shù)據(jù)元素。4 .棧的插入和刪除只能在棧的棧頂進行，后進棧白元素必定先出棧，所以又把棧稱為FILO表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為FIFO表。5 .設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF,則該二叉樹的前序遍歷序列為ABDECF,中序遍歷序列為DBEAFC,后序遍歷序列為DEBFCA。6 .設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為8,有64個葉子結(jié)點。

22、7 .設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的出度,第i列中所有非零元素個數(shù)之和等于頂點i的入度。8 .設(shè)一組初始記錄關(guān)鍵字序列(k1,k2,kn)是堆，則對i=1,2,，n/2而言滿足的條件為ki<=k&&&k:<=k2i+1。9 .下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。voidbubble(intrn)for(i=1;i<=n-1;i+)for(exchange=0,j=0;j<n-i;j+)if(rj>rj+1)temp=rj+1;rj+1=rj;rj=temp;

23、exchange=1;if(exchange=0)return;10 .下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。structrecordintkey;intothers;intbisearch(structrecordr,intk)intlow=0,mid,high=n-1;while(low<=high)mid=(low+high)/2;if(rmid.key=k)return(mid+1);elseif(_rmid.key>k)high=mid-1;elselow=mid+1;return(0);三、填空題(30分)1 .for(i=1,t=1,s=0;

24、i<=n;i+)t=t*i;s=s+t;的時間復雜度為O(n)。2 .設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入白新結(jié)點X,則進行插入操作的語句序列為s->next=p->next;p->next=s(設(shè)結(jié)點的指針域為next)。3 .設(shè)有向圖G的二元組形式表示為G=(D,R),D=1,2,3,4,5,R=r,r=<1,2>,<2,4>,<4,5>,<1,3>,<3,2>,<3,5>,則給出該圖的一種拓撲排序序列(1,3,2,4,5)。4 .設(shè)無向圖G中有n個頂點，則該無向圖中每個頂點的度

25、數(shù)最多是_n-1。5 .設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50,度數(shù)為1的結(jié)點數(shù)為30,則該二叉樹中總共有129個結(jié)點數(shù)。6 .設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為F=R。7 .設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild,則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是p->lchild=0&&p->rchild=0。8 .簡單選擇排序和直接插入排序算法的平均時間復雜度為O(n2)。9 .快速排序算法的空間復雜度平均情況下為O(nlog2n),最壞的情況下為_O(n)。10 .散列表中解決沖突的兩種方法是開放定址法和鏈地

26、址法。三、填空題(30分)1. 設(shè)指針變量p指向雙向鏈表中的結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點X的操作序列為_s->left=p=p;s->right=p->right;p->right=s;p->right->left=s;(設(shè)結(jié)點中的兩個指針域分別為left和right)。2. 設(shè)完全有向圖中有n個頂點，則該完全有向圖中共有_n(n-1)條有向條；設(shè)完全無向圖中有n個頂點，則該完全無向圖中共有n(n-1)/2條無向邊。3. 設(shè)關(guān)鍵字序列為(Kl,K2,，Kn),則用篩選法建初始堆必須從第n/2個元素開始進行篩選。4. 解決散列

27、表沖突的兩種方法是開放定址法和鏈地址法。5. 設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有_14個。6. 高度為h的完全二叉樹中最少有2h-1個結(jié)點，最多有_2h-1個結(jié)點。7. 設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟直接插入排序結(jié)束后的結(jié)果的是(12,24,35,27,18,26)。8. 設(shè)有一組初始關(guān)鍵字序列為(24,35,12,27,18,26),則第3趟簡單選擇排序結(jié)束后的結(jié)果的是(12,18,24,27,35,26)。9. 設(shè)一棵二叉樹的前序序列為ABC,則有5種不同的二叉樹可以得到這種序列。10. 下面

28、程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。structrecordintkey;datatypeothers;voidquickpass(structrecordr,ints,intt,int&i)intj=t;structrecordx=rs;i=s;while(i<j)while(i<j&&rj.key>x.key)j=j-1;if(i<j)ri=rj;i=i+1;while(i<j&&ri.key<x.key)i=i+1;if(i<j)rj=ri;j=j-1;ri=x;三、填空題(30分)

29、1 .設(shè)一組初始記錄關(guān)鍵字序列為(49,38,65,97,76,13,27,50),則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為(49,13,27,50,76,38,65,97)。2 .下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結(jié)點，請在下劃線處填上正確的內(nèi)容。typedefstructnodeintdata;structnode*lchild;structnode*rchild;bitree;voidbstinsert(bitree*&t,intk)if(t=0)t=(bitree)malloc(sizeof(bitree):t->data=k;t->lchild=t

30、->rchild=0;elseif(t->data>k)bstinsert(t->lchild,k);elsebstinsert(t->rchild,k);3 .設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：s->next=p->next;p->next=s;。4 .設(shè)指針變量head指向雙向鏈表中的頭結(jié)點，指針變量p指向雙向鏈表中的第一個結(jié)點，則指針變量p和指針變量head之間的關(guān)系是p=head->rlink和head=p->llink(設(shè)結(jié)點中的兩個指針域分別為lli

31、nk和rlink)。5 .設(shè)某棵二叉樹的中序遍歷序列為ABCD,后序遍歷序列為BADC,則其前序遍歷序列為CABD。6 .完全二叉樹中第5層上最少有1個結(jié)點，最多有16個結(jié)點。7 .設(shè)有向圖中不存在有向邊<Vi,Vj>,則其對應(yīng)的鄰接矩陣A中的數(shù)組元素Aij的值等于0O8 .設(shè)一組初始記錄關(guān)鍵字序列為(49,38,65,97,76,13,27,50),則第4趟直接選擇排序結(jié)束后的結(jié)果為(13,27,38,50,76,49,65,97)。9 .設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有n-1條邊。10 .設(shè)有一組初始記錄關(guān)鍵字序列為(50,16,23,68,94,70,73

32、),則將它們調(diào)整成初始堆只需把16與50相互交換即可。二、填空題(30分)1.設(shè)指針p指向單鏈表中結(jié)點A,指針s指向被插入的結(jié)點X,則在結(jié)點A的前面插入結(jié)點X時的操作序列為：1)s->next=p->next;2)p->next=s;3)t=p->data;4)p->data=s->data;5)s->data=t;2 .設(shè)某棵完全二叉樹中有100個結(jié)點，則該二叉樹中有50個葉子結(jié)點。3 .設(shè)某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環(huán)隊列中最多存儲m-1隊列元素。4 .對一組初始關(guān)鍵

33、字序列(40,50,95,20,15,70,60,45,10)進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數(shù)為6,在整個排序過程中最多需要進行8趟排序才可以完成。5 .在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇快速排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇堆排序。6 .設(shè)一組初始記錄關(guān)鍵字序列為(20,12,42,31,18,14,28),則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是19/7。7 .設(shè)一棵二叉樹的中序遍歷序列為BDCA,后序遍歷序列為DBAC,則這棵二叉樹的前序序歹U為CBDA。8 .設(shè)用于通信的電文僅由8個字母組成，字母在電文中

34、出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10,根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為69 .設(shè)一組記錄關(guān)鍵字序列為(80,70,33,65,24,56,48),則用篩選法建成的初始堆為_(24,65,33,80,70,56,48),10 .設(shè)無向圖G(如右圖所示)，則其最小生成樹上所有邊的權(quán)值之和為8。二、填空題(48分，其中最后兩小題各6分)1.設(shè)需要對5個不同的記錄關(guān)鍵字進行排序，則至少需要比較4次，至多需要比較10次。2 .快速排序算法的平均時間復雜度為O(nlog2n),直接插入排序算法的平均時間復雜度為O(n2)。3 .設(shè)二叉排序樹的高度為h,則在該樹中查

35、找關(guān)鍵字key最多需要比較n次。4 .設(shè)在長度為20的有序表中進行二分查找，則比較一次查找成功的結(jié)點數(shù)有1個,比較兩次查找成功有結(jié)點數(shù)有2個。5 .設(shè)一棵m叉樹脂的結(jié)點數(shù)為n,用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_n(m-1)+1個空指針域。6 .設(shè)指針變量p指向單鏈表中結(jié)點A,則刪除結(jié)點A的語句序列為：q=p->next;p->data=q->data;p->next=q->next;feee(q);7 .數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：_線性2構(gòu)、_樹型Z構(gòu)_和_圖型2構(gòu)_。8 .設(shè)無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度

36、優(yōu)先遍歷時的時間復雜度為一O(n2)；用鄰接表作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復雜度為O(n+e)。9 .設(shè)散列表的長度為8,散列函數(shù)H(k)=k%7,用線性探測法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8,15,16,22,30,32)構(gòu)造出的散列表的平均查找長度是_8/3。10 .設(shè)一組初始關(guān)鍵字序列為(38,65,97,76,13,27,10),則第3趟冒泡排序結(jié)束后的結(jié)果為(38,13,27,10,65,76,97)。11 .設(shè)一組初始關(guān)鍵字序列為(38,65,97,76,13,27,10),則第3趟簡單選擇排序后的結(jié)果為_(10,13,27,76,65,97,38)。1. 12.設(shè)有向圖G中的有向邊的集合E=<1,2>,<2,3>,<1,4>,<4,5>,<5,3>,<4,6>,<6,5>,則該圖的一個拓撲序列為124653。13 .下面程序