第1頁共1頁在您完成作業過程中，如有疑難，請登錄學院網站“輔導答疑”欄目，與老師進行交流討論！《數據結構》作業一、選擇題1．線性表的順序存儲結構是一種的存儲結構，線性表的鏈式存儲結構是一種的存儲結構。隨機存儲；b.順序存儲；c.索引存取；d.HASH存取2．一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是。a.edcba;b.decba;c.dceab;d.abcde3．一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是。a.4,3,2,1;b.1,2,3,4;c.1,4,3,2;d.3,2,4,14．在一個單鏈表中，已知p結點是q結點的直接前驅結點，若在p和q之間插入結點s，則執行的操作是。s->nxet=p->next;p->next=s;p->next=s->next;s->next=p;q->next=s; s->next=p;p->next=s; s->next=q;5．設有兩個串p,q，求q在p中首次出現的位置的運算稱作。a.聯接b.模式匹配c.求子串d.求串長6．二維數組M的成員是6個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要個字節。90b.180c.240d.5407．在線索二叉樹中，結點p沒有左子樹的充要條件是。p->lch==NULLp->ltag==1p->ltag==1且p->lch=NULL以上都不對8．在棧操作中，輸入序列為（A，B，C，D），不可能得到的輸出序列為：______A、（A，B，C，D）B、（D，C，B，A）C、（A，C，D，B）D、（C，A，B，D）9．已知某二叉樹的后序序列是dabec，中序序列是debac，則它的先序序列是。A、acbedB、decabC、deabcD、cedba10．設矩陣A是一個對稱矩陣，為了節省存儲空間，將其下三角部分（見下圖）按行序存放在一維數組B[1..n(n-1)/2]中，對任一上三角部分元素，在一維數組B的存放位置是。A、B、C、D、11．圖G中有n個頂點，n-1條邊，那么圖G一定是一棵樹嗎？。一定是B、一定不是C、不一定12．用某種排序方法對關鍵字序列{25，84，21，47，15，27，68，35，20}進行排序時，元素序列的變化情況如下： ①{25，84，21，47，15，27，68，35，20} ②{20，15，21，25，47，27，68，35，84} ③{15，20，21，25，35，27，47，68，84} ④{15，20，21，25，27，35，47，68，84} 則所采用的排序方法是。快速排序B、希爾排序C、歸并排序D、選擇排序13．表達式a*(b+c)-d的后綴表示式是。 a.abcd-*+; b.abc+*d-; c.abc*+d-; d.-*a+bcd;14．在雙向循環鏈表中的結點P之后插入結點S的操作是。a.p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;b.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;c.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;d.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;15．如下圖所示循環隊列，其中的數據元素個數是00Q.rearQ.front…m-11…(Q.rear-Q.front+m)%mQ.rear-Q.frontQ.rear-Q.front+1(Q.rear-Q.front)%m16．串是一種特殊的線性表，其特殊性體現在。可以順序存儲數據元素是一個字符可以鏈接存儲數據元素可以是多個字符17．數組A中，每個元素A[i][j]的長度是3個字節，行下標i從1到8，列下標j從1到10，從首地址SA開始連續存放在存儲器內，存放該數組的單元數是。8010024027018．已知某二叉樹的先序遍歷序列是abdgcefh，中序遍歷序列是dgbaechf，則其后序遍歷的結點訪問順序序列是。bdgcefhagdbecfhabdgaechfgdbehfca19．線索二叉樹是一種結構。邏輯邏輯和存儲物理線性20．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的倍。1/212321．采用分塊查找時，若線性表中共有625個元素，查找每個元素的概率相同，假設采用順序查找來確定元素所在的塊時，則每塊應分為個元素的塊時，查找效率最佳。1025662522．一個棧的輸入序列是12345，則棧的不可能輸出序列是。5432145321435121234523．完全二叉樹一定是滿二叉樹嗎？。一定是不是不一定24．線性表采用鏈式存儲結構時其地址。必須是連續的部分地址必須是連續的一定是不連續的連續不連續都可以25．具有線性結構的數據結構是。樹圖廣義表棧26．下圖為順序隊列的初始情況，設a,b,c相繼出隊列，e,f相繼入隊列，則指針Q.front和Q.rear分別為。Q.rear=4Q.rear=454d3c2Q.front=0bQ.front=01a0 2,53,53,64,6二、填空題1．設n行n列的下三角陣A已經壓縮存儲到一維數組S[0..]中，若按行序為主序存儲，則A[i][j]對應的在S中的存儲位置是。2．廣義表（（a），（（b），c），（（（d））））的長度是，深度是。3．深度為k的完全二叉樹至少有個結點，至多有個結點，若按自上而下，從左到右的次序給結點編號（從1開始），則編號最小的葉子結點的編號是。4．根據有向圖的寬度優先遍歷算法，對下圖2所示有向圖從頂點v1出發進行搜索，所得到的頂點遍歷序列是。0V12213NULL34NULL13NULL1V2NULL2V33V4NULL4V5 圖25．有一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當二分查找值為82的元素時，需要經過次比較就找到。6．_____________是數據的最小單位。7．在雙向鏈表中，每個結點有兩個指針域，一個是指向_____________,另一個指向_________。8．設棧ST用順序存儲結構表示，則棧ST為空的條件是____________________。9．兩個串相等的充分必要條件是_____________________和對應位置上的字符相等。10．對于深度為h的二叉樹至多有___________個結點。11．將一個A的對稱矩陣壓縮存儲到一個一維數組中，該數組的長度至少為__________。三、算法應用題1．數據集{4，5，6，7，10，12，18}為結點權值構造Huffman樹，請給出構造所得的Huffman樹，并求其帶權路徑長度。2．假設一棵二叉樹的先序序列是EBADCFHGIKJ，中序序列是ABCDEFGHIJK。請畫出該二叉樹。3．已知一顆二叉排序樹如下圖所示，若依次刪除93、19、87、48結點，試分別畫出每刪除一個結點后得到的二叉排序樹。4．已知關鍵字序列{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函數：H(key)=key%13，和開放地址法的線性探測再散列方法解決沖突，已知其裝填因子，試對該關鍵字序列構造哈希表，并求其查找成功時的平均查找長度。5．畫出和下列已知序列對應的森林F:森林的先序遍歷序列是：ABCDEFGHIJKL；森林的中序遍歷序列是：CBEFDGAJIKLH。6．假設用于通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。請給這8個字母設計哈夫曼編碼。62462463551V1V2V3V4V5V665①給出其鄰接矩陣，并按Prim算法求其最小生成樹；②給出其鄰接表，并按Kruskal算法求其最小生成樹。8．我們已經知道對長度為n的記錄序列進行快速排序時，所需進行的比較次數依賴于這n個元素的初始排列。試問：n=7時在最好情況下需進行多少次比較?請說明理由。對n=7給出一個最好情況的初始排列實例。9．下列算法為斐波那契查找算法：intFibSearch(SqListr,KeyTypek){ j=1;while(fib(j)<n+1)j=j+1;mid=n-fib(j-1)+1;//若fib(j)=n+1,則mid=fib(j-1)f1=fib(j-2);f2=fib(j-3);found=false;while((mid!=0)&&(!found))switch{ case(k==r[mid].key):found=true;break; case(k<r[mid].key): if(!f2)mid=0; else{mid=mid-f2;t=f1-f2;f1=f2;f2=t;} break; case(k>r[mid].key):if(f1==1)mid=0;else{mid=mid+f2;f1=f1-f2;f2=f2-f1;} break;} iffoundreturnmid; elsereturn0; }//FibSearch 其中fib(i)為斐波那契序列。試畫出對長度為20的有序表進行斐波那契查找的判定樹，并求其等概率時查找成功的平均查找長度。10．對下圖所示的AOE網絡，計算各活動的最早開始時間e(i)和最遲開始時間l(i)，各事件的最早發生時間ve(i)和vl(i)；并列出各條關鍵路徑。aa9=4a8=7a7=9a5=1a4=1a3=5a2=4a1=6V11V21V31V41V51V61V71V81V91a6=2a10=2a11=4四、算法設計題1．設線性表，試寫一按下列規則和并為線性表的算法，即使得當時；或者當時。線性表和均以單鏈表作存儲結構，且表利用表和表中的結點空間構成。注意：單鏈表的長度值和均未顯示存儲。2．試完成二叉樹按層次（同一層自左至右）遍歷的算法。3．試完成求無向圖的連同分量個數的算法。4．試寫一算法將兩個遞增有序的帶頭結點的單鏈表合并為一個非遞增有序的