《數(shù)據(jù)結構》期末復習題

PAGEPAGE16中國石油大學（北京）遠程教育學院期末復習題一、選擇題（本大題共15小題，每小題2分，共30分）以下與數(shù)據(jù)的存儲結構無關的術語是（）A、循環(huán)隊列 B、鏈表C、哈希表 D、棧一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（）A、110 B、108C、100 D、120假設帶頭結點的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（）A、head==NULL B、head–>next==NULLC、head–>next==headD、head!=NULL若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則不可能出現(xiàn)的出棧序列是（） A、2，4，3，1，5，6 B、3，2，4，1，6，5C、4，3，2，1，5，6 D、2，3，5，1，6，4下列關鍵字序列中，構成小根堆的是（）A、{12，21，49，33，81，56，69，41}B、{81，69，56，49，41，33，21，12}C、{81，49，69，41，21，56，12，33} D、{12，21，49，33，81，41，56，69}下列數(shù)據(jù)結構中，不屬于二叉樹的是（）A、B樹 B、AVL樹C、二叉排序樹 D、哈夫曼樹用順序存儲的方法來存儲一棵二叉樹，存放在一維數(shù)組A[1..N]中，若結點A[i]有右孩子，則其右孩子是（）。A、A[2i]B、A[2i-1]C、A[2i+1]D、A[i/2]設樹T的高度為4，其中度為1、2、3、4的結點個數(shù)分別為4、2、1、1，則T中葉子數(shù)為（）A、5B、6C、7 D、8有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，則應選擇下面哪個序列輸入（）A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，53對下面有向圖給出了四種可能的拓撲序列，其中錯誤的是（）A、1，5，2，6，3，4 B、1，5，6，2，3，4C、5，1，6，3，4，2D、5，1，2，6，4，3m階B-樹中所有非終端（除根之外）結點中的關鍵字個數(shù)必須大于或等于()A、[m/2]+1B、[m/2]-1C、[m/2]D、m散列文件也稱為()A、順序文件 B、索引文件C、直接存取文件 D、間接存取文件數(shù)據(jù)結構是（）A、一種數(shù)據(jù)類型B、數(shù)據(jù)的存儲結構C、一組性質相同的數(shù)據(jù)元素的集合D、相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合從邏輯關系來看，數(shù)據(jù)元素的直接前驅為0個或1個的數(shù)據(jù)結構只能是（）A、線性結構 B、樹形結構C、線性結構和樹型結構 D、線性結構和圖狀結構設p為指向雙向循環(huán)鏈表中某個結點的指針，p所指向的結點的兩個鏈域分別用p→llink和p→rlink表示，則同樣表示p指針所指向結點的表達式是（）A、p→llink B、p→rlinkC、p→llink→llink D、p→llink→rlink若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個棧(i=1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（）A、|top[2]-top[1]|=0 B、top[1]+1=top[2]C、top[1]+top[2]=m D、top[1]=top[2]若一棵二叉樹有11個葉子結點，則該二叉樹中度為2的結點個數(shù)是（）A、10 B、11 C、12 D、不確定的樹的先根序列等同于與該樹對應的二叉樹的（）A、先序序列 B、中序序列 C、后序序列 D、層序序列下面關于哈希(Hash，雜湊)查找的說法正確的是()A、哈希函數(shù)構造的越復雜越好，因為這樣隨機性好，沖突小B、除留余數(shù)法是所有哈希函數(shù)中最好的C、不存在特別好與壞的哈希函數(shù)，要視情況而定D、若需在哈希表中刪去一個元素，解決沖突都只要簡單的將該元素刪去即可下列序列中，（）是執(zhí)行第一趟快速排序后所得的序列。A、[68，11，18，69][23，93，73]B、[68，11，69，23][18，93，73] C、[93，73][68，11，69，23，18]D、[68，11，69，23，18][93，73]下列關鍵字序列中，構成小根堆的是()A、(84，46，62，41，28，58，15，37)B、(84，62，58，46，41，37，28，15)C、(15，28，46，37，84，41，58，62)D、(15，28，46，37，84，58，62，41)ISAM文件和VASM文件屬于()A、索引非順序文件B、順序文件C、索引順序文件D、散列文件下面程序段的時間復雜度為（）for(i=0;i<m;i++)for(j=0;j<n;j++)A[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針s指向另一個單鏈表中某個結點，則在s所指結點之后插入上述鏈表應執(zhí)行的語句為（）A、q->next=s->next；s->next=p；B、s->next=p；q->next=s->next；C、p->next=s->next；s->next=q；D、s->next=q；p->next=s->next；為便于判別有向圖中是否存在回路，可借助于（）A、廣度優(yōu)先搜索算法B、最小生成樹算法C、最短路徑算法D、拓撲排序算法若以S和X分別表示進棧和退棧操作，則對初始狀態(tài)為空的?？梢赃M行的棧操作系列是（）A、SXSSXXXXB、SXXSXSSXC、SXSXXSSXD、SSSXXSXX設有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應該是()A、2B、3C、5D、6假設以數(shù)組A[m]存放循環(huán)隊列的元素。已知隊列的長度為length，指針rear指向隊尾元素的下一個存儲位置，則隊頭元素所在的存儲位置為（）。A、(rear-length+m+1)%m B、(rear-length+m)%mC、(rear-length+m-1)%m D、(rear-length)%m在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結點s的操作為（）。A、s->next=rear;rear=s;B、front=front->next;C、s->next=front;front=s;D、rear->next=s;rear=s;對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關鍵字是（）A、35和41B、23和39C、15和44D、25和51采用二叉鏈表存儲的n個結點的二叉樹，共有空指針（）個。A、n+1B、nC、n-1D、2n-1連通網的最小生成樹是其所有生成樹中（）A、頂點集最小的生成樹 B、邊集最小的生成樹C、頂點權值之和最小的生成樹 D、邊的權值之和最小的生成樹對記錄序列(314，298，508，123，486，145)依次按個位和十位進行兩趟基數(shù)排序之后所得結果為（）A、123，145，298，314，486，508B、508，314，123，145，486，298C、486，314，123，145，508，298D、298，123，508，486，145，314任何一個無向連通圖的最小生成樹()。A、一定有多棵B、可能不存在C、一棵或多棵D、只有一棵無向圖的鄰接矩陣是一個()A、對角矩陣B、上三角矩陣C、對稱矩陣D、零矩陣設無向圖G-=(V,E)和G’=(V’,E’),如G’為G的生成樹，則下列說法中不正確的是()。A、G’為G的無環(huán)子圖B、G’為G連通分量C、G’為G極小連通子圖且V’=VD、G’為G的子圖以v1為起始結點對下圖進行深度優(yōu)先遍歷，正確的遍歷序列是（）A、v1，v2，v3，v4，v5，v6，v7 B、v1，v2，v5，v4，v3，v7，v6 C、v1，v2，v3，v4，v7，v5，v6 D、v1，v2，v5，v6，v7，v3，v4下面幾個符號串編碼集合中，不是前綴編碼的是（）A、{0,10,110,1111}B、{0,1,00,11}C、{00,010,0110,1000}D、{b,c,aa,ac,aba,abb,abc}希爾排序的增量序列必須是（）。遞增的B、遞減的C、隨機的D、非遞減的采用起泡排序法對n個關鍵字進行升序排序，若要使排序過程中比較關鍵字的次數(shù)最多，則初始時的序列應滿足條件（）A、關鍵字完全無序B、關鍵字基本有序C、關鍵字從小到大排列D、關鍵字從大到小排列在下列內部排序中()是不穩(wěn)定的。A、希爾排序B、起泡排序C、直接插入排序D、歸并排序分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是()。A、（100，80，90，60，120，110，130）B、（100，120，110，130，80，60，90）C、（100，60，80，90，120，110，130）D、(100，80，60，90，120，130，110)在查找過程中，沖突指的是（）。A、兩個元素具有相同序號B、兩個元素的鍵值不同C、不同鍵值對應相同的存儲地址D、兩個元素的鍵值相同對有14個元素的有序表A[1..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[5]，A[3]，A[4]D、A[7]，A[3]，A[5]，A[4]以v1為起始結點對下圖進行廣度度優(yōu)先遍歷，正確的遍歷序列是（）A、v1，v2，v3，v4，v5，v6，v7B、v1，v2，v5，v6，v7，v3，v4C、v1，v2，v5，v6，v7，v3，v4D、v1，v4，v5，v7，v6，v2，v3二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)數(shù)據(jù)的物理結構包括的存儲和的存儲。若一個算法中的語句頻度之和為T(n)=1921n+4nlogn,則算法的時間復雜度為。下面程序段的時間復雜度是。i=1；while(i<=n)i=i*3；循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列的元素個數(shù)是。在單鏈表中設置頭結點的作用是____。線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是_。已知一無向圖G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是遍歷方法。如果排序過程不改變之間的相對次序，則稱該排序方法是穩(wěn)定的。從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需一個位置。當問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的。若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個數(shù)即為頂點vi的。一棵含999個結點的完全二叉樹的深度為。假設S和X分別表示進棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX，則由“a*b+c/d”得到“ab*cd/+”的操作序列為。.如圖所示的有向無環(huán)圖可以排出種不同的拓撲序列。從空樹起，依次插入關鍵字1l，27，35，48，52，66和73構造所得的二叉排序樹，在等概率查找的假設下，查找成功時的平均查找長度為。帶頭結點的雙循環(huán)鏈表L中只有一個元素結點的條件是。求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中的數(shù)目正相關。已知一棵完全二叉樹中共有768結點，則該樹中共有個葉子結點。實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標志數(shù)組標志已訪問的圖的結點外，還需要存放被訪問的結點以實現(xiàn)遍歷。Prim（普里姆）算法適用于求的網的最小生成樹；kruskal（克魯斯卡爾）算法適用于求的網的最小生成樹。對長度為20的有序表進行二分查找的判定樹的高度為。設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為，有_個葉子結點。高度為h的完全二叉樹中最少有個結點，最多有個結點。設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有條邊。構造n個結點的強連通圖，至少有條弧。表達式求值是應用的一個典型例子。設棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1，則棧的容量至少應該是。快速排序算法在最差的情況下其時間復雜度是。對序列{55，46，13，05，94，17，42}進行基數(shù)排序，第一趟排序后的結果是。三、應用題（本大題共5小題，每小題6分，共30分）已知二叉樹的先序遍歷序列ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。如圖請給出鄰接表、鄰接矩陣及逆鄰接表。 V1V1V3V2V4由字符集{s，t，a，e，I}及其在電文中出現(xiàn)的頻度構建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100，請根據(jù)該哈夫曼樹進行譯碼，寫出原來的電文。請畫出下圖所示的樹所對應的二叉樹，并寫出對應二叉樹的先序遍歷和中序遍歷。112345678設散列表為HT[13],散列函數(shù)為H(key)=key%13。用閉散列法解決沖突,對下列關鍵碼序列12,23,45,57,20,03,78,31,15,36造表。采用線性探查法尋找下一個空位,畫出相應的散列表,并計算等概率下搜索成功的平均搜索長度。已知帶權圖G如圖所示，畫出圖G的一棵最小生成樹。假設用于通信的電文由字符集{a,b,c,d,e,f,g,h}中的字母構成，這8個字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，請為這8個字母設計哈夫曼編碼。試用權集合{12,4,5,6,1,2}構造哈夫曼樹，并計算哈夫曼樹的帶權路徑長度。畫出與如圖所示森林對應的二叉樹。已知一個散列表如下圖所示：35203348590123456789101112其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為：hi=(h(key)+*h1(key))%m=0,1,…，m-1其中：h1(key)=key%11+1回答下列問題：（1）對表中關鍵字35，20，33和48進行查找時，所需進行的比較次數(shù)各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？請畫出與下列二叉樹對應的森林。對于給定結點的關鍵字集合K={5，7，3，1，9，6，4，8，2，10}，（1）試構造一棵二叉排序樹；（2）求等概率情況下的平均查找長度ASL。給出下圖對應的鄰接矩陣，并給出A，B，C三個頂點的出度與入度已知圖5.32如下所示，求從頂點a到其余各頂點的最短路徑。（給出求解過程）54543223356abdfce閱讀下列算法，并回答問題：（1）假設串由合法的英文字母和空格組成，并以’\0’作結束符。設串s=”??I?am?a???student”(?表示空格符)，寫出f30（s）的返回值；（2）簡述算法f30的功能。intf30(char*s){inti,n,inword;n=inword=0;for(i=0;s[i]!=’\0’;i++)if(s[i]!=’?’&&inword==0){inword=1;n++;}elseif(s[i]==’?’&&inword==1)inword=0;returnn;}閱讀下列函數(shù),并回答問題：（1）假設隊列q中的元素為(a,b,c,d,e),其中“a”為隊頭元素。寫出執(zhí)行函數(shù)調用Conv(&q)后的隊列q；（2）簡述算法Conv的功能。voidConv(Queue*Q){ StackS; InitStack(&S); while(!QueueEmpty(Q)) Push(&S,DeQueue(Q)); while(!StackEmpty(&S)) ＥnQueue(Q,Pop(&S));}閱讀下列函數(shù),并回答問題：已知整形數(shù)組L［1..8］中的元素依次為（19，18，15，17，16，13，12，10），閱讀下列函數(shù)，并寫出執(zhí)行函數(shù)調用sort(L,8)時，對L進行的頭兩趟（pass分別為0和1）處理結果。 voidsort(intR[],intn) { intpass=0,k,exchange,x; do{ k=pass%2+1; exchange=0; while(k<n) { if(R[k]>R[k+1]) { x=R[k];R[k]=R[k+1];R[k+1]=x; exchange=1; }K+=2; } pass++; }while(exchange==1||pass<=1); }keynext已知帶頭結點的單鏈表中的關鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設散列表的長度為m，散列函數(shù)為Hash(key)=key%m。鏈表的結點結構為：keynextvoidf33(LinkListL,LinkListH［］,intm){//由帶頭結點的單鏈表L生成散列表H，散列表生成之后原鏈表不再存在inti,j;LinkListp,q;for(i=0;i<m;i++)H［i］=(1);p=L->next;while(p){q=p->next;j=p->key%m;(2);H［j］=p;(3);}free(L);}下列函數(shù)的功能是，對以帶頭結點的單鏈表作為存儲結構的兩個遞增有序表（表中不存在值相同的數(shù)據(jù)元素）進行如下操作：將所有在Lb表中存在而La表中不存在的結點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入合適內容，使其成為一個完整的算法。voidunion(LinkListLa,LinkListLb) { //本算法的功能是將所有Lb表中存在而La表中不存在的結點插入到La表中 LinkListpre=La,q; LinkListpa=La->next; LinkListpb=Lb->next; free(Lb); while(pa&&pb) { if(pa->data<pb->data) {pre=pa;pa=pa->next;} elseif(pa->data>pb->data) { (1); pre=pb; pb=pb->next; (2); } else { q=pb;pb=pb->next;free(q); } } if(pb) (3); }閱讀算法f30，并回答問題：下列算法為有向圖拓撲排序,請在空缺處填入合適的內容，使其成為一個完整的算法。voidf30(hdnodesgraph[],intn){inti,j,k,top;node_pointerptr; top=-1; for(i=0;i<n;i++) if(!graph[i].count){graph[i].count=top;top=i;} for(i=0;i<n;i++) if_(1)___{fprintf(stderr,"\ngraphhasacycle\n");exit(1);} else{ j=top;_(2)__;printf("v%d,",j);for(ptr=graph[j].link;ptr;ptr=ptr->link){k=ptr->vertex;graph[k].count--;if((3)){graph[k].count=top;top=k;}}}}閱讀算法f31，并回答問題：下列算法功能為在數(shù)組a的前n(n>=1)個元素中找出第k(1<=k<=n)小的值。這里假設數(shù)組a中各元素的值都不相同。請在空缺處填入合適的內容，使其成為一個完整的算法。#defineMAXN100inta[MAXN],n,k;intf31(inta[],intn,intk){intlow,high,i,j,m,t; k--,;low=0;high=n-1; do{i=low;j=high;t=a[low]; do{while(i<j&&t<a[j])j--;if(i<j)a[i++]=a[j];while(i<j&&t>=a[i])i++if(i<j)a[j--]=a[i]; }while(i<j);a[i]=t;if(1); if(i<k)low=(2);elsehigh=(3);}while（i!=k）;return(a[k]);}閱讀算法f33，并回答問題：下