復習題1[共12頁]

一、選擇題 1-1 下列關于數據和邏輯結構的敘述中，哪一個是不正確的（ ）。 A ) 數據的邏輯結構是數據間關系的描述 B) 數據的邏輯結構抽象反映數據元素間的邏輯關系 C) 數據的邏輯結構具體反映數據在計算機中的存儲方式 D) 數據的邏輯結構分為線性結構和非線性結構 C1-2 以下關于數據的存儲結構的敘述中哪一條是正確的（ ）。 A) 數據的存儲結構是數據間關系的抽象描述 B) 數據的存儲結構是邏輯結構在計算機存儲器中的實現 C) 數據的存儲結構分為線性結構和非線性結構 D) 數據的存儲結構對數據運算的具體實現沒有影響 B 二、簡答題 1-1 數據結構的存儲方式有哪幾種？ 1-2 算法的時間復雜度僅與問題的規(guī)模相關嗎 ? 1-1 數據結構的存儲方式有哪幾種？ 【解析】 常用的存儲表示方法有四種 : 1 、順序存儲方法：它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構，通常借助程序語言的數組描述。 2 、鏈接存儲方法：它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針字段表示。由此得到的存儲表示稱為鏈式存儲結構 , 通常借助于程序語言的指針類型描述。 3 、索引存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。組成索引表的索引項由結點的關鍵字和地址組成。若每個結點在索引表中都有一個索引項，則該索引表稱之為稠密索引（ Dense Index ）。若一組結點在索引表中只對應一個索引項，則該索引表稱為稀疏索引。 4 、散列存儲方法：就是根據結點的關鍵字直接計算出該結點的存儲地址。 1-2 算法的時間復雜度僅與問題的規(guī)模相關嗎 ? 【解析】 算法的時間復雜度不僅與問題的規(guī)模相關，還與輸入實例中的初始狀態(tài)有關。但在最壞的情況下，其時間復雜度就是只與求解問題的規(guī)模相關的。我們在討論時間復雜度時，一般就是以最壞情況下的時間復雜度為準的。 三、應用題: 分析以下程序段的時間復雜度。 int i ， j ， k ； for （ i=0 ； i n ； i+ / for （ j=0 ； j n ； j+ / cij=0 ； / for （ k=0 ； k n ； k+ / cij=cij+aik+bkj ； / 【解析】 語句的循環(huán)控制變量 i 要增加到 n ，測試到 i=n 成立才會終止，故它的頻度為 n+1 ； 語句作為語句循環(huán)體內的語句應該執(zhí)行 n 次，但語句本身要執(zhí)行 n+1 次，故語句的頻度是 n （ n+1 ）； 同理可得語句、和的頻度分別是 n 2 ， n 2 （ n+1 ）和 n 3 。該程序段所有語句的頻度之和為： T （ n ） =2n3 +3n 2 +2n+1 其復雜度為 O （ n 3 ）。 一、簡答1 何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜? 2 在順序表中插入和刪除一個結點需平均移動多少個結點?具體的移動次數取決于哪兩個因素? 3 為什么在單循環(huán)鏈表中設置尾指針比設置頭指針更好? 4 在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點*p從相應的鏈表中刪去?若可以，其時間復雜度各為多少? 5 下述算法的功能是什么?LinkList Demo(LinkList L) / L 是無頭結點單鏈表 ListNode *Q,*P; if(L&&L->next) Q=L;L=L->next;P=L; while (P->next) P=P->next; P->next=Q; Q->next=NULL; return L; / Demo 6、試描述頭指針、頭結點、開始結點的區(qū)別、并說明頭指針和頭結點的作用。二、下列函數的功能是，對以帶頭結點的單鏈表作為存儲結構的兩個遞增有序表（表中不存在值相同的數據元素）進行如下操作：將所有在Lb表中存在而La表中不存在的結點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入合適內容，使其成為一個完整的算法。void union (LinkList La, LinkList Lb)/*本算法的功能是將所有Lb表中存在而La表中不存在的結點插入到La表中*/ LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pb)if (pa -> data <pb -> data) pre = pa; pa = pa -> next;else if (pa -> data > pb ->data) (1) ;pre = pb;pb = pb -> next; (2) ;else q = pb; pb = pb -> next; free (q);if (pb) (3) ;（1）pre->next=pb;（2）pre->next=pa;（3）pre->next=pb;三、已知一個線性表有n（n30）個元素，其中每個元素的數據占8個字節(jié)。假設一個指針的大小為4個字節(jié)。如果采用有30個元素的數組存儲，那么當數組中有效元素個數n滿足什么條件時，數組的存儲效率比不帶頭結點的單鏈表更高。數組總的空間240個字節(jié)，數組的效率為8n/240；鏈表的總空間為12n，效率為8n/12n。故可得：n20四、畫出執(zhí)行下列各語句后各指針及鏈表的示意圖。L=(LinkList)malloc(sizeof(Lnode);P=L;for(i=1;i<=4;i+) p->next=(LinkList) malloc(sizeof(Lnode); p=p->next;P->data=i*2-1;P->next=NULL;for(i=4;i>=1;i-) InsertList (L,i+1,i*2);for(i=1;i<=3;i+) DeleteList (L,i);2、順序隊列一般應該組織成為循環(huán)隊列的形式，而且一般隊列頭或為隊列尾其中之一虛指一位，滿隊列時實際上數組中還有一個空閑位置。請分析這樣設置的理由。有利于判斷隊列是空還是滿。因為隊列有n+2種狀態(tài)：空，1個元素， 2個元素，, n個元素，滿。但實際上rear只有n種可能的取值，故必須尋求其他途徑解決隊空和隊滿。當然也有其他方法。3、隊列可以用循環(huán)單鏈表來實現，故可以只設置一個頭指針或者只設置一個尾指針。請分析對于循環(huán)單鏈表實現的隊列，用那種方案更合適。設置尾指針。因為是循環(huán)單鏈表，設置尾指針，可以在O(1)的時間內找到頭；如果只設置頭指針，要在O(n)時間內找到尾。設置尾指針，入隊和出隊的時間復雜度均為O(1)，設置頭指針，出隊O(1)，入隊O(n)。一、單項選擇題1、由于二叉樹中每個結點的度最大為2，所以二叉樹是一種特殊的樹，這種說法 （A）正確 （B）錯誤2、某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是 (A)空或只有一個結點 (B) 完全二叉樹(C)二叉排序樹 (D) 高度等于其節(jié)點數3、深度為5的二叉樹至多有 多少個結點(A)16 (B)32 (C)31 (D)104、根據使用頻率為5個字符設計的哈夫曼編碼不可能是（A）111，110，10，01，00（B）000，001，010，011，1（C）100，11，10，1，0 （D）001，000，01，11，10二、填空題1、樹和二叉樹的主要差別是 ， 。2、深度為k的完全二叉樹至少有 個結點，至多有 個結點。 3、一棵二叉樹的第i(i1)層最多有 個結點；一棵有n（n>0）個結點的滿二叉樹共有 個葉子結點和 個非葉子結點。1、 （1）每個結點最多有兩棵子樹； （2）子樹有左右之分2、2k-1,2k-1,3、2i-1, 2 log2n ， n- 2 log2n 1、一棵度為2的樹與一棵二叉樹有何區(qū)別？2、具有三個結點的樹和具有三個結點的二叉樹它們的所有不同形態(tài)有哪些？3、請說明一棵二叉樹進行先序、中序和后序遍歷，其葉結點的次序是否會發(fā)生變化？為什么？1、解答：度為2的樹結點有兩個分支，沒有左右之分；一棵二叉樹的結點也可有兩個分支，但有左右之分，且左右不能交換。3.解答：二叉樹中葉結點必在某結點的左或右子樹中，三種遍歷方法對左右子樹的遍歷都是按先左后右的原則進行。所以在三種遍歷序列中葉結點的相對次序是不會發(fā)生變化的。4、假設一棵二叉樹的結點數為33個，則它的最小高度為（ ），最大高度為（ ）。5、一個高度為h的滿m叉樹，第k層最多有（ ）個結點，整棵樹最多有（ ）個結點。4、最小高度為：6，最大高度為：335、第k層最多有 mk-1,整棵樹最多有(mk-1)/(m- 1)6、一個二叉樹的對稱序列和后序序列分別是DCBAEFG和DCBGFEA，請給出該二叉樹的前序序列。 6、ABCDEFG7 有7個帶權結點，其權值分別為4，7，8，2，5，16，30，以它們?yōu)槿~子結點構造一顆哈夫曼樹（要求按每個結點的左子樹根結點的權值小于或等于右子樹根結點的權值的次序構造），并計算出其帶權路徑長度WPL。可得帶權路徑長度：WPL=(2+4)5+(5+7+8)4+162+301=1721、一個n個頂點的無向圖最多有 條邊。(A)n (B)n(n-1) (C)n(n-1)/2 (D)2n2、（A）1/2 （B）1 （C）2 （D）43.兩種遍歷算法。1、設線性表（a1，a2，a500）元素的值由小到大排列，對一個給定的k值用折半法查找線性表，在查找不成功的情況下至多需比較 次 1. log2n+12 試述順序查找法、折半查找法和分塊查找法對被查找的表中元素的要求。對長度為n的表來說，三種查找法在查找成功時的查找長度各是多少？查找要求:順序查找法：表中元素可以任意存放,(n+1)/2 折半查找法：有序存放 log2(n+1)-1分塊查找法：分塊有序(n/s+s)/2+1,b為塊數，s為塊中記錄數1.數據的基本單位是（C）A.數據項 B.數據類型 C.數據元素 D.數據變量2.下列程序的時間復雜度為（C）i=0；s=0；while（s<n） i+；s=s+i； A.O（ ） B.O（ ） C.O（n） D.O（n2）3.若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則最節(jié)省運算時間的存儲方式是（D）A.單鏈表 B.僅有頭指針的單循環(huán)鏈表C.雙鏈表 D.僅有尾指針的單循環(huán)鏈表4.從一個長度為n的順序表中刪除第i個元素（1in）時，需向前移動的元素的個數是（A）A.n-i B.n-i+1C.n-i-1 D.i5.順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數組，則元素e進棧操作的主要語句為（C）A.s.elemtop=e； B.s.elemtop+1=e； s.top=s.top+1； s.top=s.top+1；C.s.top=s.top+1； D.s.top=s.top+1； s.elemtop+1=e； s.elemtop=e；6.循環(huán)隊列sq中，用數組elem025存放數據元素，sq.front指示隊頭元素的前一個位置，sq.rear指示隊尾元素的當前位置，設當前sq.front為20，sq.rear為12，則當前隊列中的元素個數為（D）A.8 B.16 C.17 D.188.含有10個結點的二叉樹中，度為0的結點數為4，則度為2的結點數為（A） A.3 B.4C.5 D.610.有n個結點的有向完全圖的弧數是（C）A.n2 B.2nC.n(n-1) D.2n(n+1)11.設圖的鄰接鏈表如題12圖所示，則該圖的邊的數目是（B） A.4 B.5 C.10 D.2012.已知一個有序表為（13，18，24，35，47，50，62，83，90，115，134），當二分檢索值為90的元素時，檢索成功需比較的次數是（B）A.1 B.2C.3 D.413.排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（）A.選擇排序 B.快速排序C.冒泡排序 D.插入排序14數據結構是（D）A一種數據類型B數據的存儲結構C一組性質相同的數據元素的集合D相互之間存在一種或多種特定關系的數據元素的集合15算法分析的目的是（B）A辨別數據結構的合理性B評價算法的效率C研究算法中輸入與輸出的關系D鑒別算法的可讀性16在線性表的下列運算中，不改變數據元素之間結構關系的運算是（D）A插入 B刪除C排序 D定位17若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則可能出現的出棧序列為（B）A3，2，6，1，4，5 B3，4，2，1，6，5C1，2，5，3，4，6 D5，6，4，2，3，118二維數組A89按行優(yōu)先順序存儲，若數組元素A23的存儲地址為1087，A47的存儲地址為1153，則數組元素A67的存儲地址為（A）A1207 B1209C1211 D121319在按層次遍歷二叉樹的算法中，需要借助的輔助數據結構是（A）A隊列 B棧C線性表 D有序表20在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關系（B）A不一定相同 B都相同C都不相同 D互為逆序1稱算法的時間復雜度為O(f(n)，其含義是指算法的執(zhí)行時間和_ f(n)_的數量級相同。2假設為循環(huán)隊列分配的向量空間為Q20，若隊列的長度和隊頭指針值分別為13和17，則當前尾指針的值為_10_。3一棵含999個結點的完全二叉樹的深度為_。4含n個頂點的無向連通圖中至少含有_條邊。6在數據結構中，數據的邏輯結構分為集合、_、樹形結構和圖狀結構等四類。7. 順序表的存儲密度為_，而鏈表的存儲密度為_。是指一個結點中數據域所占的存儲單元和整個結點所占的存儲單元之比8. 對于棧只能在_插入和刪除元素。9. 在循環(huán)隊列中，存儲空間為0n-1,設隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么隊滿標志為front=(rear+1)%n，隊空標志為_。10. 三個結點可構成_種不同形態(tài)的二叉樹。1.若對具有n個元素的有序的順序表和無序的順序表分別進行順序查找，試在下述兩種情況下分別討論兩者在等概率時的平均查找長度：(1)查找不成功，即表中無關鍵字等于給定值K的記錄；(2)查找成功，即表中有關鍵字等于給定值K的記錄。答：查找不成功時，需進行n+1次比較才能確定查找失敗。因此平均查找長度為n+1，這時有序表和無序表是一樣的。查找成功時，平均查找長度為(n+1)/2,有序表和無序表也是一樣的。因為順序查找與表的初始序列狀態(tài)無關。2給出樹如下圖所示，請寫出先序遍歷和中序遍歷的節(jié)點次序。3一棵度為2的有序樹與一棵二叉樹有何區(qū)別?答：一棵度為二的有序樹與一棵二叉樹的區(qū)別在于:有序樹的結點次序是相對于另一結點而言的，如果有序樹中的子樹只有一個孩子時，這個孩子結點就無須區(qū)分其左右次序，而二叉樹無論其孩子數是否為2，均需確定其左右次序，也就是說二叉樹的結點次序不是相對于另一結點而言而是確定的。4設將整數1，2，3，4依次進棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題：(1)若入、出棧次序為Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),則出棧的數字序列為何(這里Push(i)表示i進棧，Pop( )表示出棧)?(2)能否得到出棧序列1423和1432?并說明為什么不能得到或者如何得到。答：(1)出棧序列為：1324 (2)不能得到1423序列。因為要得到14的出棧序列，則應做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。這樣，3在棧頂，2在棧底，所以不能得到23的出棧序列。能得到1432的出棧序列。具體操作為：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。1指出下述程序段的功能是什么?void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i< n; i+) Push(S, arri); /Demo1程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂的元素放到棧底，棧底的元素放到棧頂。此棧中元素個數限制在64個以內。2.已知二叉樹的先序序列和中序序列分別為HDACBGFE和ADCBHFEG,畫出該二叉樹.3.以二叉鏈表為存儲結構， 寫一算法交換各結點的左右子樹。 答：要交換各結點的左右子樹，最方便的辦法是用后序遍歷算法，每訪問一個結點時把兩棵子樹的指針進行交換，最后一次訪問是交換根結點的子樹。void ChangeBinTree(BinTree *T) /交換子樹if(*T) /這里以指針為參數使得交換在實參的結點上進行后序遍歷BinTree temp;ChangeBinTree(&(*T)->lchild);ChangeBinTree(&(*T)->rchild);temp=(*T)->lchild;(*T)->lchild=(*T)->rchild;(*T)->rchild=temp;信道容量1. 假設用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構成，這8個字母在電文中出現的概率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10.為這8個字母設計哈夫曼編碼。 (1)哈夫曼編碼 根據上圖可得編碼表：a:1001b:01c:10111d:1010e:11f:10110g:00h:10002.給出下圖的從結點a開始的遍歷次序，1）深度優(yōu)先；2）廣度優(yōu)先。