數據結構與算法離線作業答案(已修改)

　

【正文】 浙江大學遠程教育學院《數據結構與算法》課程離線作業姓名：陳翠學 號：713009014001年級：2013秋學習中心：金華學習中心—————————————————————————————一、填空題：（【序號，章，節】。）【1，1，2】線性結構中元素之間存在一對一關系，樹形結構中元素之間存在　　 一對多　　關系，圖形結構中元素之間存在　　多對多　　關系。【2，1，2】為了最快地存取數據元素，物理結構宜采用 順序存儲 結構。【3，1，2】存儲結構可根據數據元素在機器中的位置是否一定連續分為 順序存儲結構___， 鏈式存儲結構___。【4，1，3】度量算法效率可通過 時間復雜度___來進行。【5，1，3】設n 為正整數，下面程序段中前置以記號@的語句的頻度是 n(n+1)/2 。 for (i=0。 in。 i++){ for (j=0。 jn。 j++) if (i+j==n1)@ a[i][j]=0。 }【6，1，3】設n 為正整數，試確定下列各程序段中前置以記號@的語句的頻度: (1) i=1。 k=0。 while (i=n1){ i++。 @ k+=10 * i。 // 語句的頻度是_________n1_______________。 } (2) k=0。 for (i=1。 i=n。 i++){ for (j=i。 j=n。 j++) @ k++。 // 語句的頻度是_________n(n+1)/2________________。 }【7，3，2】線性表(a1，a2，…，an)有兩種存儲結構： 順序存儲結構和鏈式存儲結構，請就這兩種存儲結構完成下列填充： ___順序_ 存儲密度較大；___順序____存儲利用率較高；___順序____可以隨機存取；__鏈式_____不可以隨機存取；__鏈式____插入和刪除操作比較方便。【8，3，2】從一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動 ni 個元素。【9，3，2】帶頭結點的單鏈表Head為空的條件是___ Headnext=NULL _ ______。【10，3，2】在一個單鏈表中p所指結點(p所指不是最后結點)之后插入一個由指針s所指結點，應執行snext=__ pnext ___。和pnext=___ s_ _____的操作。【11，3，2】在一個單鏈表中刪除p所指結點時，應執行以下操作： q= pnext。 pdata= pnextdata。 pnext= pnextnext _ 。 free(q)。【12，3，2】帶頭結點的單循環鏈表Head的判空條件是_ Headnext == Head ____； 不帶頭結點的單循環鏈表的判空條件是_ Head == NULL ____。【13，3，2】已知L是帶表頭結點的非空單鏈表, 且P結點既然不首元結點,也不是尾元結點,試從下列提供的答案中選擇合適的語句序列。a. 刪除P結點的直接前驅結點的語句序列是__10 12 8 11 4 14___。b. 刪除結點P的語句序列是__10 12 7 3 14______。c. 刪除尾元結點的語句序列是____9 11 3 14_____。(1) P = Pnext。(2) Pnext = P。(3) Pnext = Pnext next。(4) P = Pnext next。(5) while (P != NULL) P = Pnext。(6) while (Qnext != NULL){P = Q。 Q = Qnext}。(7) while (Pnext != Q) P = Pnext。(8) while (Pnextnext != Q) P = Pnext。(9) while (Pnextnext != NULL) P = Pnext。(10) Q = P。(11) Q = Pnext。(12) P = L。(13) L = Lnext。(14) free (Q)。【14，3，3】對一個棧，給定輸入的順序是A、B、C，則全部不可能的輸出序列有 不可能得到的輸出序列有CAB 。【15，3，3】.在棧頂指針為HS的鏈棧中，判定棧空的條件是　headnext==NULL　。【16，3，3】下列程序把十進制數轉換為十六進制數，請填寫合適的語句成分。void conversion10_16(){ InitStack(amp。s)。 scanf(“%d”,amp。N)。 while(N){① ________Push(s, N%16)______ 。 N = N/16。 } while(!StackEmpty(s)){② _______ Pop(s, e)_ _______ 。 if(e=9)printf(“%d”,e)。 else printf(“%c”,e10+’A’)。 }} /* conversion */【17，3，4】若用一個大小為6個元素的數組來實現循環隊列，且當前rear=0和front=3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是 2 和 4 。【18，3，4】堆棧和隊列都是線性表, 堆棧是______后進先出_______的線性表, 而隊列是____先進先出_______的線性表。【19，3，4】若用一個大小為6個元素的數組來實現循環隊列，且當前rear=0和front=3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是 2 和 4 。【20，4，2】已知一棵樹邊的集合是{a,d,d,c,d,j,e,a,f,g,d,b,g,h,g,i,e,f}。那么根結點是 e ，結點b的雙親是 d ，結點a的子孫有 bcdj ，樹的深度是 4 ，樹的度是 3 ，結點g在樹的第 3 層。【21，4，3】從概念上講，樹與二叉樹是二種不同的數據結構，將樹轉化為二叉樹的基本的目的是　樹可采用二叉樹的存儲結構并利用二叉樹的已有算法解決樹的有關問題　　。【22，4，3】滿三叉樹的第i層的結點個數為 3i1 ，深度為h時該樹中共有 3 1h 結點。【23，4，3】已知一棵完全二叉樹有56個葉子結點，從上到下、從左到右對它的結點進行編號，根結點為1號。則該完全二叉樹總共結點有___111_____個；有__7__層；第91號結點的雙親結點是___45__號；第63號結點的左孩子結點是____32_____號。【24，4，3】下列表示的圖中，共有___5____個是樹；有___3____個是二叉樹；有__2____個是完全二叉樹。【25，4，4】n個結點的二叉排序樹的最大深度是 n ，最小深度為 [log2n]+1 。【26，4，3】如果某二叉樹的后序遍歷序列是ABCDEFGHI，中序遍歷序列是ACBIDFEHG，則其先序遍歷序列的第一個字母是 I ，最后一個字母是 G 。【27，4，3】下列二叉樹的中序遍歷序列是_DBNGOAEC__。后序遍歷序列是_____DNIGBECA________。 【28，5，4】設HASH表的大小為 n (n=10), HASH函