數據結構c語言版章節練習題(16章)(專業版)

　　

【正文】 C1 , int amp。 // 求當前項 a = b。}return max。 if ( HL == NULL || xHLdata ) { // 空表 或 x小于表頭結點，newptrnext = HL。 cp = HL 。 j=i1 。 // 線性表長度減1return x。三、應用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。19．假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，則對它進行的先序遍歷結果為____________，中序遍歷結果為____________，后序遍歷結果為____________，按層遍歷結果為____________。3．在一棵三叉樹中，度為3的結點數有2個，度為2的結點數有1個，度為1的結點數為2個，那么度為0的結點數有________個。 Q) { InitQueue(Q)。 A、f+1==r B、r+1==f C、f==0 D、f==r8．假定一個鏈隊的隊首和隊尾指針分別為front和rear，則判斷隊空的條件是 。(1)從線性表中刪除具有最小值的元素并由函數返回，空出的位置由最后一個元素填補，若線性表為空則顯示出錯信息并退出運行。 i++) InsertFront(La,a[i])。 qnext = q。 A、qnext = pnext 。j++) p*=j。 } A、 O(1) B、 O(n) C、 O(n2) D、 O(n!)二、填空題、_________、__________和__________四種。 A、 *(a+i) B、 a+i C、 *a+i D、 amp。 A、 n2 B、 n2/2 C、 n(n+1) D、 n(n+1)/2。 while(++i=n) { int p=1。 D、pnext = HLnext。 C、p = qnext 。 int a[]={48,26,57,34,62,79}。 Insert(La,a[5]/2)。 A、前一個 B、后一個 C、當前 D、后面5．當利用大小為N的一維數組順序存儲一個循環隊列時，該隊列的最大長度為 。13．從一個棧頂指針為HS的非空鏈棧中刪除結點并不需要返回棧頂結點的值和回收結點時，應執行________操作。，利用一個數組來存儲非零元素，該數組的長度應________對應三元組線性表的長度。16．若對一棵二叉樹從0開始進行結點編號，并按此編號把它順序存儲到一維數組a中，即編號為0的結點存儲到a[0]中，其余類推，則a[i]元素的左孩子元素為________，右孩子元素為________，雙親元素(i0)為________。4．在一個堆的順序存儲中，若一個元素的下標為i，則它的左孩子元素的下標為______，右孩子元素的下標為________。 k = i。 } if ( == MaxSize ) { // 判斷線性表滿 printf(List overflow!\n)。exit(1)。 // 申請一個新結點 if ( newptr == NULL ) { // 分配失敗cerr Memory allocation failare!endl。LNode * p = HLnext。else for ( int i = 3 。 cout 無右孩子！endl。amp。 // 返回所求的第n項} 遞歸算法的時間復雜度為 O(2n)，空間復雜度為 O(n)；非遞歸算法的時間復雜度為 O(n)，空間復雜度為 O(1)。 while ( p != NULL ) { if ( pdata == x ) n++。 } // 查找插入位置 LNode * cp = HLnext。 // cp指向的結點即為第i個結點 else { // 繼續向后尋找ap = cp。 // 元素插入 ++。exit(1)。4. 有七個帶權結點，其權值分別為3,7,8,2,6,10,14，試以它們為葉子結點構造一棵哈夫曼樹，并計算出帶權路徑長度WPL。2．編寫一算法，求出一棵二叉樹中所有結點數和葉子結點數，假定分別用變參C1和C2統計所有結點數和葉子結點數，初值均為0。6．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則度為0的結點數分別為______、_____、______和______個。 i4。3．向一個順序棧插入一個元素時，首先把待插入元素________到這個位置上然后，使________后移一個位置。(4)從線性表中刪除具有給定值x的所有元素。 for(i=0。3．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為_____，在表尾插入元素的時間復雜度為_____。 q = p。第二章 線性表一、單選題1．在一個長度為n的順序存儲線性表中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需要從后向前依次后移 個元素。 im。 i++) for(int j=1。[n]中順序查找出一個最大值元素的時間復雜度為________，輸出一個二維數組b[m][n]中所有元素值的時間復雜度為________。 HL = p。 pnext = qnext。10．在以HL為表頭指針的帶表頭結點的單鏈表和循環單鏈表中，鏈表為空的條件分別為_____和______。 i++) InsertRear(La,a[i])。 A、棧頂 B、棧底 C、任意位置 D、指定位置2．當利用大小為N的一維數組順序存儲一個棧時，假定用top==0表示棧空，則向這個棧插入一個元素時，需要執行 語句修改top指針。10．向一個順序隊列插入元素時，需要首先向________插入新元素，然后再移動________。 A、 行號 B、 列號 C、 元素值 D、 地址二、填空題，每個非零元素所對應的三元組包括該元素的________、________和________三項。13．一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)))，它含有雙親結點______個，單分支結點______個，葉子結點______個。 A、 24 B、 48 C、 72 D、 53二、填空題 1. 在一棵二叉搜索樹中，每個分支結點的左子樹上所有結點的值一定________該結點的值，右子樹上所有結點的值一定________該結點的值。