數(shù)據(jù)結(jié)構(gòu)復習題

考試題型一、選擇題(每小題2分，共30分)二、程序填空題(本大題共20空，每空1分，共20分)三、問答題(本大題共3小題，共35分)四、算法設(shè)計題(共15分)數(shù)據(jù)結(jié)構(gòu)復習題一、選擇題.下面程序段的時間復雜度是()。count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;A.O(log2n) B.O(n) C.O(nlog2n) D.0(n2).順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由()表示。A.線性結(jié)構(gòu) B.非線性結(jié)構(gòu) C.存儲位置 D.指針.順序表中第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是()。A.110 B.108 C.100 D.1201、與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的()。A.存儲結(jié)構(gòu) B.存儲實現(xiàn)C.邏輯結(jié)構(gòu) D.運算實現(xiàn).試分析下面程序段的時間復雜度()。x=90;y=100;while(y>0)if(x>100){x=x-10;y-;}elsex++;A.0(1) B.0(n2) C.O(log3n)D.0().順序表中第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是()。A.110 B.108 C.100 D.120.鏈接存儲的存儲結(jié)構(gòu)所占存儲空間()。A.分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針B.只有一部分，存放結(jié)點值C.只有一部分，存儲表示結(jié)點間關(guān)系的指針D.分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù).創(chuàng)建一個包括n個結(jié)點的有序單鏈表的時間復雜度是( )。A.0(1) B.0(n) C.0(n2) D.O(nlog2n).向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數(shù)為()。A.8 B.63.5 C.63 D.7.在單鋅表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句應為（）。A.s->next=p+l;p->next=s; B.（*p）.next=s;（*s）.next=（+p）.next;C.s->next=p->next;p->next=s->next; D.s->next=p->next;p->next=s;.在一個以L為頭指針的單循環(huán)鏈表中，p指針指向鏈尾的條件是（）。A.p->next==L B.p->next==NULLC.p->next->next==L D.p->data=-1.若已知一個棧的人棧序列是1,2,3, 其輸出序列為pi,pz,P3,…，Pn，若Pi=n，則pi為（）。A.i B.n-i C.n-i+1 D.不確定。.已知循環(huán)隊列存儲在一維數(shù)組A[0..nT]中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第1個進入隊列的元素存儲在A[（）]處,則初始時front和rear的值分別是（）。A.0,0 B.0,n-l C.n-1,0 D.n-l,n-l.已知字符串S為"abaabaabacacaabaabcc"，模式串t為"abaabc"，采用KMP算法進行匹配，第一次出現(xiàn)“失配"（s[i] 時，i=j=5,則下次開始匹配時，i和j的值分別是（）。A.i=l,j=0 B.i=5,j=0 C.i=5,j=2 D.i=6,j=2.已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉子結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多是（）。A.39 B.52 C.Ill D.119.若一組記錄的排序碼為{46,79,56,38,40,84},則利用堆排序的方法建立的初始堆為（）。A.79,46,56,38,40,84 B.84,79,56,38,40,46C.84,79,56,46,40,38 D.84,56,79,40,46,38.下列選項給出的是從根分別到大兩個葉子結(jié)點路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是（）。A.24,10,5和24,10,7 B.24,10,5和24,12,7C.24J0,10和24,14/I D.24J0,5和24,14,6.在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（）。p->next->prior=p->prior;p->prior->next=p->nex（;p->next=p->next->next;p->next->prior=p;p->prior->next=p;p->prior=p->prior->prior;p->prior=p->next->next;p->next=p->prior->prior;.若已知一個棧的入枝序列是1,2,3,…，n,其輸出序列為pl,p2,p3,…，pn,若pl=n,貝ijpi為（）oA.i B.n-i C.n-i+1 D.不確定19.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5和e6依次進入棧S,一個元素出棧后即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和el,則棧S的容最至少應該是（）。A.2 B.3 C.4 D.620.若??個枝以向量存儲，初始棧頂指針top設(shè)為n+1,則元素x進棧的正確操作是（）<>A.top++;V[top]=x; B.V[top]=x;top++;C.top—;V[top]=x; D.V[top]=x;top-;21.最大容量為n的循環(huán)隊列，隊尾指針是rear,隊頭是front,則隊空的條件是()。A.(rear+1)%n==front B.rear==frontC.rcar+l==front D.(rcar-l)%n==front.對右圖圖1所示的圖進行拓撲排序，可以得到不同的拓撲序列個數(shù)是()。A.4 B.3 C.2 D.1 圖1.對于有n個頂點、e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷，其算法的時間復雜度是()。A.O(n) B.O(e) C.O(n+e) D.O(nxe).折半查找有序表{4,6,10,12,20,30,50,70,88,100}。若查找表中元素58,則它將依次與表中()比較大小，查找結(jié)果是失敗。A.20,70,30,50 B.30,88,70,50 C.20,50 D.30,88,50.若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B[l..(n(n+l))/2]中，則在B中確定aij(i<j)的位置k的關(guān)系為()。A.i*(i-l)/2+jB.j*(j-l)/2+iC.i*(i+l)/2+jD.j*(j+l)/2+i.一個具有1025個結(jié)點的二叉樹的高h為()。A.11 B.10 C.11至1025之間D.10至1024之間.深度為h的滿m叉樹的第k層有()個結(jié)點。(l=<k=<h)A.mk-1 B.mk-1 C.mh-1 D.mh-1.設(shè)哈夫曼樹中有50個葉結(jié)點，則該哈夫曼樹中有( )個結(jié)點。A.99 B.100C.101 D.102.下面()算法適合構(gòu)造一個稀疏圖G的最小生成樹。A.Prim算法B.Kruskal算法C.Floyd算法D.Dijkstra算法.用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常借助()來實現(xiàn)算法。A.棧 B.隊列 C.樹 D.圖.折半查找有序表(4,6,10,12,20,30,50,70,88,100)?若查找表中元素58,則它將依次與表中()比較大小，查找結(jié)果是失敗。A.20,70,30,50 B.30,88,70,50C.20,50 D.30,88.50.下列關(guān)鍵字序列中，()是堆。A.16,72,31,23,94,53 B.94,23,31,72,16,S3C.16,53,23,94,31,72 D.16,23,53,31,94,72.下述幾種排序方法中，()是穩(wěn)定的排序方法。A.希爾排序B.快速排序 C.歸并排序D.堆排序二、程序填空題.已知單鏈表的存儲結(jié)構(gòu)為typcdefstructLNode 〃定義單鏈表結(jié)點類型{ElemTypedata;〃數(shù)據(jù)域structLNodc*ncxt; 〃指向后繼結(jié)點}LinkNode將以下程序補充完整，實現(xiàn)用尾插法建立單鏈表。voidCrcatcListR(LinkNodc*&L,ElcmTypca[],intn){LinkNode*s,*r; 〃i?為尾指針inti;L=(LinkNode*)malloc(sizeof(LinkNode));for(i=0;i<n;i++){s=(LinkNode*)malloc(sizeof(LinkNode));s->data=a[il;).設(shè)有一個不帶表頭結(jié)點的單鏈表L,設(shè)計兩個遞歸算法，del(L,x)刪除單鏈表L中第一個值為x的結(jié)點，delall(L,x)刪除單鏈表L中所有值為x的結(jié)點。voiddel(LinkNode*&L,ElemTypex)(LinkNode*t;if(L==NULL);if(L->data==x)(t=;.free(t);J))voiddelall(LinkNode*&L,ElemTypex)(LinkNode*t;if(L==NULL)return;while()(t=L;L=L->next;).假設(shè)以I和()分別表示進棧和出棧操作，棧的初態(tài)和終棧均為空，進棧和出棧的操作序列可表示為僅由I和0組成的序列。(1)下面所示的序列中哪些是合法的：A.IOIIOIOOB.1(X)10110C.III0I010D.111(X)100(2)通過對(1)的分析，設(shè)計一個算法判定所給的操作序列是否合法。若合法返回真;否則返回假。(假設(shè)被判定的操作序列已存入一維數(shù)組中)。booljudge(charstr[],,intn){inti=0;ElemTypex;LinkStNode*ls;boolflag=;InitStack(ls);while(i<n&&flag){ if(str[i]==,I')〃進棧elseif(str[i]=='')〃出棧{if(StackEmpty(ls))flag=false;〃?？諘relse;)elseflag=;〃其他值無效i++;)if(!StackEmpty(ls))flag=;DestroyStack(ls);return;)三、問答題.已知模式串t="abcaabbabcab”寫出用KMP法求得的每個字符對應的next和ncxtval函數(shù)值。.已知圖2所示的無向網(wǎng)，請給出：(1)鄰接表(2)最小生成樹。圖2.設(shè)散列表的地址范圍為0~17,散列函數(shù)為：H(key)=key%16o用線性探測法處理沖突，輸入關(guān)鍵字序列：(10,24,32,17,31,30,46,47,40,63,49),構(gòu)造散列表，試回答下列問題：(1)畫出散列表的示意圖.(2)查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字進行比較？(3)若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字進行比較？(4)假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。.已知一棵二叉樹的中序序列為cbedahgijf,后序序列為cedbhjigfa,給出該二叉樹樹形表示。.設(shè)一組關(guān)鍵字為(7,15,20,31,48,53,64,76,82,99),Hash函數(shù)H(key)=key%l1,Hash表表長m=ll,用線性探測法解決沖突，試構(gòu)造Hash表，并計算查找成功和不成功情況下的平均查找長度。.已知一個圖的頂點集V和邊集E分別為：V={1,234,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)26(5,6)18,(6,7)25};說明：邊集合中(1,2)3中1,2代表頂點，3為改邊上的權(quán)值畫出該圖并用克魯斯卡爾算法得到最小生成樹，試寫出最小生成樹的邊的生成順序過程。.將整數(shù)序列(4,5,7,2,1,3,6)中的元素依次插入到一棵空的二叉排序樹中，試構(gòu)造相應的二叉排序樹，要求用圖形給出構(gòu)造過程。四、算法設(shè)計題.當取di=n/2,&+1=[4/2]時,希爾排序算法如何實現(xiàn)？請完成函數(shù)voidShellSort(RecTypeR[],intn)o.假設(shè)圖G采用鄰接表存儲，設(shè)廿一一個算法void