數(shù)據(jù)結(jié)構與算法作業(yè).doc

數(shù)據(jù)結(jié)構與算法作業(yè)說明：1、題號形式: 每題都以【sn，cha，sec】開頭，sn表明本題的題目序號，每道題都有唯一的序號；cha表示內(nèi)容所在的章；sec表示內(nèi)容所在的節(jié)。如 【17，2，1】表示序號17的題來自第2章第1節(jié)。2、題型： 1)填空題:1-802)分析計算作圖題：序號1-30題（選自數(shù)據(jù)結(jié)構題集嚴蔚敏等編）3、內(nèi)容取舍：根據(jù)本學期上課課件中的內(nèi)容，未上課章節(jié)的練習可舍棄。4、必做題或選做題：第四章和第五章不考，所以可以選做。1) 填空題：序號1-80題【1，1，2】線性結(jié)構中元素之間存在一對一關系，樹形結(jié)構中元素之間存在關系，圖形結(jié)構中元素之間存在關系?！?，1，2】為了最快地存取數(shù)據(jù)元素，物理結(jié)構宜采用 結(jié)構?！?，1，2】數(shù)據(jù)結(jié)構的三要素是 ， ， ?！?，1，2】數(shù)據(jù)的邏輯結(jié)構可形式地用一個二元組B(K，R)來表示，其中K是 _，R是 _?！?，1，2】存儲結(jié)構可根據(jù)數(shù)據(jù)元素在機器中的位置是否一定連續(xù)分為 _， _。【6，1，4】度量算法效率可通過 _來進行。【7，1，4】算法的五個重要特性是確定性、輸入和輸出?！?，1，4】設n為正整數(shù)，則下面程序段的時間復雜度是 _。i=1；k=0；while(in)k=k+10*i；i+；【9，1，4】設n 為正整數(shù)，下面程序段中前置以記號的語句的頻度是 。 for (i=0; in; i+) for (j=0; jn; j+) if (i+j=n-1) aij=0; 【10，1，4】設n 為正整數(shù)，試確定下列各程序段中前置以記號的語句的頻度: (1) i=1; k=0; while (i=n-1) i+; k+=10 * i; / 語句的頻度是_。 (2) k=0; for (i=1;i=n;i+) for (j=i; jnext=_ _;和p-next=_ _的操作?！?9，2，3】在一個單鏈表中的指針p所指結(jié)點之前插入一個由指針s所指結(jié)點，可執(zhí)行以下操作序列：s-next= _;p-next=s;t=p-data;p-data=_ _;s-data=t;【20，2，3】在一個單鏈表中刪除p所指結(jié)點時，應執(zhí)行以下操作： q= p-next; p-data= p-next-data; p-next= _ ; free(q);【21，2，3】在單鏈表中，刪除指針P所指結(jié)點的后繼結(jié)點的語句是 _?！?2，2，3】帶頭結(jié)點的單循環(huán)鏈表Head的判空條件是_； 不帶頭結(jié)點的單循環(huán)鏈表的判空條件是_?！?3，2，3】刪除帶頭結(jié)點的單循環(huán)鏈表Head的第一個結(jié)點的操作是_；刪除不帶頭結(jié)點的單循環(huán)鏈表的第一個結(jié)點的操作是_?！?4，2，3】已知L是帶表頭結(jié)點的非空單鏈表, 且P結(jié)點既然不首元結(jié)點,也不是尾元結(jié)點,試從下列提供的答案中選擇合適的語句序列。a. 刪除P結(jié)點的直接前驅(qū)結(jié)點的語句序列是_。b. 刪除結(jié)點P的語句序列是_。c. 刪除尾元結(jié)點的語句序列是_。(1) P = P-next;(2) P-next = P;(3) P-next = P-next -next;(4) P = P-next -next;(5) while (P != NULL) P = P-next;(6) while (Q-next != NULL)P = Q; Q = Q-next;(7) while (P-next != Q) P = P-next;(8) while (P-next-next != Q) P = P-next;(9) while (P-next-next != NULL) P = P-next;(10) Q = P;(11) Q = P-next;(12) P = L;(13) L = L-next;(14) free (Q);【25，3，1】棧操作的原則是 ?！?6，3，1】對一個棧，給定輸入的順序是A、B、C，則全部不可能的輸出序列有 ?！?7，3，1】數(shù)據(jù)A、B、C、D依次進棧后，再從棧中取一數(shù)據(jù)，則它是 。則本棧得到DCBA的輸出序列，其理由是 ?！?8，3，1】.在棧頂指針為HS的鏈棧中，判定?？盏臈l件是?！?9，3，1】將遞歸算法改寫成等價的非遞歸算法，通常應該設置 的數(shù)據(jù)結(jié)構【30，3，2】下列程序把十進制數(shù)轉(zhuǎn)換為十六進制數(shù)，請?zhí)顚懞线m的語句成分。（每空2分）void conversion10_16() InitStack(&s); scanf(“%d”,&N); while(N) _ _ ; N = N/16; while(!StackEmpty(s) _ ; if(e=9)printf(“%d”,e); else printf(“%c”,e-10+A); /* conversion */【31，3，4】若一個棧的輸入序列為1,2,3,n，輸出序列的第一個元素為n，則第i個輸出元素是 ?！?2，3，4】若用一個大小為6個元素的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear=0和front=3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是 和 。【33，3，4】已知一個棧的輸入序列為1，2，3，n,輸出序列為a1,a2,a3,an，那么a2=n的輸出序列共有 種?！?4，3，4】堆棧和隊列都是線性表, 堆棧是_的線性表, 而隊列是_的線性表?！?5，3，4】從循環(huán)隊列中刪除一個元素時，其操作是?！?6，3，4】若用一個大小為6個元素的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear=0和front=3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是 和 ?！?7，3，4】下面是關于循環(huán)隊列的操作，請在劃線空白處填寫合適語句成分。Status EnQueue(SqQueue &Q, QelemType e) if( ) retrun ERROR; Q.base(Q.rear+1) % MAXSIZE = e; Q.rear = ; return OK; / EnQueue 【38，4，1-選】空串是 ，其長度為 ?！?9，4，1-選】設串s1=”teachers and “,s2=”students”,則StrLength(s2)= ；Concat(s1,s2)= ?！?0，4，1-選】設s = I AM A TEACHER，其長度是?！?1，4，1-選】兩個串相等的充分必要條件是。【42，4，2-選】串的兩種最基本的存儲方式是。【43，4，3-選】令有串u=”aabcaab”和v=”abcaabcaabcaaba”,(1) 求Index(v,u,5)的值：Index(v,u,5)= ; (2分)(2) 求出u作為模式串時在KMP算法中的nextj值。(2分)j1234567uaabcaabnextj【44，5，1-選】二維數(shù)組A1020采用列序為主方式存儲，每個元素占一個存儲單元，并且A00的存儲地址是200，則A610的地址是?！?5，5，1-選】設每個元素需要8個字節(jié)，順序存儲100個元素,若首地址是2500，那么第50個元素的地址是_?！?6，5，2-選】已知二維數(shù)組Amn采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC(A00)，則Aij的地址是【47，5，2-選】C語言采用行優(yōu)先方式存放數(shù)組元素，數(shù)組下標從0開始。設維數(shù)為（5,6,7）的數(shù)組A5x6x7的起始存儲地址為Loc000=1000，每個數(shù)組元素占用4個字節(jié)。則元素A444所在的地址Loc444= _?！?8，5，2-選】按行優(yōu)先次序列出三維數(shù)組A232的所有12個元素在內(nèi)存中的存儲次序，它們依次是： A000 A A A A A A A A A A A121【49，5，3-選】對一個10階對稱矩陣A，采用壓縮存儲方式（以行序為主序，且A00的地址為1）,則A85的地址是 ?！?0，5，3-選】對一個10階三對角矩陣A，采用壓縮存儲方式（以行序為主序，且A00的地址為1，每個元素占4個字節(jié)）,則A65的地址是 。【51，5，3-選】對一個對稱矩陣A（aij=aji,0=i,j=j）對應S中的下標是 ；一維數(shù)組S的大小M至少為 ?！?2，6，1】已知一棵樹邊的集合是,。那么根結(jié)點是 ，結(jié)點b的雙親是 ，結(jié)點a的子孫有 ，樹的深度是 ，樹的度是 ，結(jié)點g在樹的第 層。【53，6，2】通常使用來表示二叉樹結(jié)構?！?4，6，2】從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結(jié)構，將樹轉(zhuǎn)化為二叉樹的基本的目的是?！?5，6，2】在圖1至圖5中, _是樹，_是二叉樹，_是完全二叉樹，_是滿二叉樹。 圖1 圖2 圖3 圖4 圖5【56，6，3】在圖4中，結(jié)點H在這棵樹的前序、中序和后序遍歷次序中分別是_、第_和第_個結(jié)點?！?7，6，2】滿三叉樹的第i層的結(jié)點個數(shù)為 ，深度為h時該樹中共有 結(jié)點?！?8，6，2】在圖4中，A是_結(jié)點，D是_結(jié)點，B是E的_，B是G的_，D是E的_。這棵樹的度是_，深度是_。【59，6，2】程序填空：下列算法是求以二叉鏈表存儲的二叉樹中的最小值，設數(shù)據(jù)域的類型為int。void minnode(BiTree T, int *min) if(T!=NULL) if( ) *min = T-data; minnode(T-lchild,min); ; 【60，6，2】已知一棵完全二叉樹有56個葉子結(jié)點，從上到下、從左到右對它的結(jié)點進行編號，根結(jié)點為1號。則該完全二叉樹總共結(jié)點有_個；有_層；第91號結(jié)點的雙親結(jié)點是_號；第63號結(jié)點的左孩子結(jié)點是_號。（每空2分）【61，6，2】下列表示的圖中，共有_個是樹；有_個是二叉樹；有_個是完全二叉樹?！?2，6，3】下列二叉樹的中序遍歷序列是_;后序遍歷序列是_。 【63，6，3】一棵二叉樹的中序遍歷序列是DBNGOAEC,后序遍歷序列是DNOGBECA，則其先序遍歷的序列中的第一個元素是_ _，第五個元素是_ _，最后一個元素是_【64，6，3】下列二叉樹的先序遍歷序列的第5個結(jié)點是_；第8個結(jié)點是_；后序遍歷序列的第2個結(jié)點是_；第6個結(jié)點是_。(每空 2 分)【65，6，3】如果某二叉樹的后序遍歷序列是ABCDEFGHI，中序遍歷序列是ACBIDFEHG，則其先序遍歷序列的第一個字母是 ，最后一個字母是 ?！?6，6，3】程序填空：設算法DFS(Mgraph *G, int i)是無向圖G從i頂點開始的深度優(yōu)先遍歷算法。下列算法是判斷無向圖G是否是連通的。int isconnect(Mgraph *G) int i,k=0; for(i=0; ivexnum; i+) visitedi = 0; for(i=0; ivexnum; i+) if(!visitedi) ； DFS(G, i); if(k=1) ； else return 0;【67，7，2】圖有 和 等存儲結(jié)構?！?8，7，2】設無權圖G的鄰接矩陣為A，若（vi,vj）屬于圖G的邊集合，則對應元素Aij等于 ，22、設無向圖G的鄰接矩陣為A，若Aij等于0，則Aji等于 。【69，7，2】若一個圖用鄰接矩陣表示，則計算第i個結(jié)點的入度的方法是 ?！?0，7，2】若一個圖用鄰接矩陣表示，則刪除從第i個頂點出發(fā)的所有邊的方法是 ?！?1，7，4】n個頂點的連通圖至少有 條邊?！?2，7，4】設一個圖G=V,A,V=a,b,c,d,e,f,A=,。那么頂點e的入度是 ；出度是 ；通過頂點f的簡單回路有 條；就連通性而言，該圖是 圖；它的強連通分量有 個；其生成樹可能的最大深度是?！?3，7，5】下面有向圖共有_個頂點；從v3到v2的最短簡單路徑之一是_；v1的出度是_；包含所有頂點的簡單路徑之一是_?！?4，9，2】n個結(jié)點的二叉排序樹的最大深度是 ，最小深度為 【75，9，3】設HASH表的大小為 n (n=7), HASH函數(shù)為 h(x)=x % n, 如果用線性探測法 F(i)=i解決沖突，請在下面HASH表中依次插入關鍵字5, 18, 21, 14, 25, 4以后，關鍵字4、5和25所在地址的下標分別是 、 和 ，插入上述6個元素的平均比較次數(shù)是 。下標：0 1 2 3 4 5 6 【76，10，1】排序過程一般需經(jīng)過兩個基本操作，它們是 和 ?！?7，10，2】結(jié)點的關鍵字序列是（F,B,J,G,E,A,I,D,C,H），對它按字母的字典序進行排列。如果采用Shell排序方法，那么步長取5時，第一次掃描結(jié)果的前5個字母分別是 ?！?8，10，2】在對一組關鍵字是（54,38,96,45,15,72,60,23,83）的記錄進行直接插入排序時，當把第七個記錄（關鍵字是60）插入到有序表時，為尋找插入位置需比較 次?！?9，10，3】在利用快速排序方法對一組關鍵字是（54,38,96,45,15,72,60,23,83）的記錄進行排序時，需要遞歸調(diào)用partition函數(shù)，遞歸的最大深度（設第一次調(diào)用深度為1）為 ，共需5次遞歸調(diào)用，其中第二次遞歸調(diào)用是對關鍵字是 的一組記錄進行的?！?0，10，4】插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序、和基數(shù)排序方法中，不穩(wěn)定的排序方法有 。2) 分析計算作圖題：序號1-30（選自數(shù)據(jù)結(jié)構題集嚴蔚敏等編）【1， 1，4】（選自數(shù)據(jù)結(jié)構題集1.8，選做題）設n為正整數(shù)，試確定下列各段程序中前置以記號的語句的頻度(語句的頻度指的是該語句重復執(zhí)行的次數(shù))。(1) i=1；k=0;while (i0) if(x100) x-=10; y-; else x+;【2， 1，4】（選自數(shù)據(jù)結(jié)構題集1.9，選做題） 假設n為2的乘冪，并且n2，試求下列算法的時間復雜度及變量count的值（以n函數(shù)形式表示） int Time (int n)count =0;x=2;while(x next S ；（2）P next P next next；（3）P next S next；（4）S next P next；（5）S next L；（6）S next NULL；（7）Q P；（8）while （P next ！ Q）P P next；（9）while （P next ！ NULL） P P next；（10）P Q；（11）P L；（12）L S；（13）L P；【4， 2，2】（選自數(shù)據(jù)結(jié)構題集2.10，選做題）指出以下算法中的錯誤和低效（即費時）之處，并將它改寫為一個既正確又高效的算法。 Status DeleteK（SqList &a，int i，int k）/本過程從順序存儲結(jié)構的線性表a中刪除第i個元素起的k個元素 if（i 1 | k a.length）return INFEASIBLE；/ 參數(shù)不合法 else for（count 1；count i +1；j ）a.elemj1 a.elemj；a. length ； return OK； / DeleteK【5， 3，1】（選自數(shù)據(jù)結(jié)構題集3.4，必做題） 簡述以下算法的功能（棧的元素類型 SElemType為int）（1）Status algo1（Stack S） int i，n，A255； n 0； while （！StackEmpty（S） n +；Pop（S，An）； for（i 1；i n；i +）Push（S，Ai）； （2）Status algo2（Stack S，int e） Stack T；int d； InitStack（T）； while（！StackEmpty（S） Pop（S，d）； if（d！e）Push（T，d）； while（！StackEmpty（T） Pop（T，d）； Push（S，d）； 【6， 3，1】（選自數(shù)據(jù)結(jié)構題集3.15，選做題）假設以順序存儲結(jié)構實現(xiàn)一個雙向棧，即在一堆數(shù)組的存儲空間中存在著兩個棧，它們的棧底分別設在數(shù)組的兩個端點。試編寫實現(xiàn)這個雙向棧tws的三個操作：初始化inistack（tws）、入棧push（tws，i，x）和出棧pop（tws，i）的算法，其中i為0或1，用以分別指示設在數(shù)組兩端的兩個棧，并討論按過程（正/誤狀態(tài)變量可設為變參）或函數(shù)設計這些操作算法各有什么優(yōu)缺點。【7， 3，4】（選自數(shù)據(jù)結(jié)構題集3.13，必做題）簡述以下算法的功能（棧和隊列的元素類型均為int）void algo3(Queue &Q)Stack S; int d; InitStack (S);while (!QueueEmpty (Q) DeQueue (Q, d); Push (S,d);while (!StackEmpty (S) Pop (S, d); EnQueue(Q, d);【8， 3，2】（選自數(shù)據(jù)結(jié)構題集3.19，選做題）假設一個算術表達式中可以包含三種括號：圓括號“（”和“）”，方括號“”和“”和花括號“”和“”，且這三種括號可以按任意的次序嵌套使用（如：()）。編寫判別給定表達式所含括號是否正確配對出現(xiàn)的算法（已知表達式已存入數(shù)據(jù)元素為字符的順序表中）。【9， 4，1】（選自數(shù)據(jù)結(jié)構題集4.3，必做題）設s =I AM A STUDENT,t =GOOD,q =WORKER。求：StrLength(s), StrLength(t), SubString(s,8,7), SubString(t,2,1),Index(s, A), Index(s, t), Replace(s, STUDENT,q ),Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)【10， 5，1】（選自數(shù)據(jù)結(jié)構題集5.1，必做題）假設有兩維數(shù)組A6x8，每個元素用相鄰的6個字節(jié)存儲，存儲按字節(jié)編址。已知A的起始地址為1000，計算：(1) 數(shù)組A的存儲量；(2) 數(shù)組A的最后一個元素a57的第一個字節(jié)的地址；(3) 按行存儲時，元素a14的第一個字節(jié)的地址；(4) 按列存儲時，元素a47的第一個字節(jié)的地址；【11， 6，1】（選自數(shù)據(jù)結(jié)構題集6.1，必做題）已知一棵樹邊的集合為，請畫出這棵樹，并回答下列問題：（1）哪個是根結(jié)點？（2）哪些是葉子結(jié)點？（3）哪個是結(jié)點G的雙親？（4）哪些是結(jié)點G的祖先？（5）哪些是結(jié)點G的孩子？（6）哪些是結(jié)點E的子孫？（7）哪些是結(jié)點E的兄弟？哪些是結(jié)點F的兄弟？（8）結(jié)點B和N的層次號分別是什么？（9）樹的深度是多少？（10）以結(jié)點C為根的子樹的深度是多少？【12， 6，1】（選自數(shù)據(jù)結(jié)構題集6.4，選做題）一棵深度為H的滿k叉樹有如下性質(zhì)第H層上的結(jié)點都是葉子節(jié)點，其余各層上每個結(jié)點都有k棵非空子樹。如果按層次順序從1開始對全部結(jié)點編號，問：（1）各層的結(jié)點數(shù)目是多少？（2）編號為p的父結(jié)點（若存在）的編號是多少？（3）編號為p的結(jié)點的第i個兒子結(jié)點（若存在）的編號是多少？（4）編號為p的結(jié)點有右兄弟的條件是什么？其右兄弟的編號是多少？【13， 6，2】（選自數(shù)據(jù)結(jié)構題集6.5，選做題）已知一棵度為k的樹中有n1個度為1 的結(jié)點，n2個度為2 的結(jié)點，nk個度為k的結(jié)點，問該樹中有多少個葉子結(jié)點？【14， 6，3】（選自數(shù)據(jù)結(jié)構題集6.13，必做題）假設n和m為二叉樹中的兩結(jié)點，用“1”、“0”、“”（分別表示肯定、恰恰相反或者不一定）填寫下表：已知 問答:前序遍歷時n在m前？中序遍歷時n在m前？后序遍歷時n在m前？n在m左方n在m右方n是m祖先n是m子孫注：如果（1）離a和b最近的共同祖先p存在，且（2）a在p的左子樹中，b在p的右子樹中，則稱a在b的左方（即b在a的右方）【15， 6，3】（選自數(shù)據(jù)結(jié)構題集6.14，選做題）找出所有滿足下列條件的二叉樹：（a）它們在先序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同；（b）它們在后序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同；（c）它們在先序遍歷和后序遍歷時，得到的結(jié)點訪問序列相同；【16， 6，4】（選自數(shù)據(jù)結(jié)構題集6.19，必做題）分別畫出和下列樹對應的各二叉樹：【17， 6，3】（選自數(shù)據(jù)結(jié)構題集6.23，選做題）畫出和下列已知序列對應的樹T樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG?！?8， 6，5】（選自數(shù)據(jù)結(jié)構題集6.26，必做題）假設用于通信的電文僅有8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10.試為這8個字母設計哈夫曼編碼。使用07的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點?！?9， 6，2】（選自數(shù)據(jù)結(jié)構題集6.29，必做題）假設一棵二叉樹的層序序列為ABCDEFGHIJ和中序序列為DBGEHJACIF。請畫出該樹?！?0， 7，2】（選自數(shù)據(jù)結(jié)構題集7.1，必做題）已知如右圖所示的有向圖，請給出該圖的（1） 每個頂點的入/出度； （2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表；（5） 強連通分量?！?1， 7，3】（選自數(shù)據(jù)結(jié)構題集7.4，選做題）試對教科書7.1節(jié)中圖7.3（a）所示的無向圖(如下圖)，畫出其廣度優(yōu)先生成森林。【22， 7，4】（選自數(shù)據(jù)結(jié)構題集7.5，選做題）已知以二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090