當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

【最详细】数据结构（C语言版第2版）第七章课后习题答案严蔚敏等编著

發布時間：2024/2/28 编程问答 25 豆豆

生活随笔收集整理的這篇文章主要介紹了【最详细】数据结构（C语言版第2版）第七章课后习题答案严蔚敏等编著小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

所有章節答案合集——>傳送門

1．選擇題

（ 1）對 n 個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為（）。
A． (n-1)/2
B ． n/2
C． (n+1)/2
D ． n
答案： C
解釋：總查找次數 N=1+2+3+ , +n=n(n+1)/2 ，則平均查找長度為 N/n=(n+1)/2 。

（ 2）適用于折半查找的表的存儲方式及元素排列要求為（）。
A．鏈接方式存儲，元素無序
B．鏈接方式存儲，元素有序
C．順序方式存儲，元素無序
D ．順序方式存儲，元素有序
答案： D
解釋：折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。

（ 3）如果要求一個線性表既能較快的查找，又能適應動態變化的要求，最好采用 ( )查找法。
A ．順序查找 B．折半查找
C．分塊查找 D．哈希查找
答案： C
解釋：分塊查找的優點是：在表中插入和刪除數據元素時，只要找到該元素對應的塊，就可以在該塊內進行插入和刪除運算。由于塊內是無序的，故插入和刪除比較容易，無需進行大量移動。如果線性表既要快速查找又經常動態變化，則可采用分塊查找。

（ 4）折半查找有序表（ 4， 6， 10， 12， 20 ， 30 ， 50 ， 70 ， 88 ， 100 ）。若查找表中元素
58，則它將依次與表中（）比較大小，查找結果是失敗。
A． 20 ， 70， 30， 50
B ． 30， 88， 70 ， 50
C． 20 ， 50
D． 30 ， 88， 50
答案： A
解釋：表中共 10 個元素，第一次取 (1+10)/2 =5 ，與第五個元素 20 比較， 58 大于 20，再取 (6+10)/2 =8，與第八個元素 70 比較，依次類推再與 30 、 50 比較，最終查找失敗。

（ 5）對 22 個記錄的有序表作折半查找，當查找失敗時，至少需要比較（）次關鍵字。
A． 3
B． 4
C ． 5
D． 6
答案： B
解釋： 22 個記錄的有序表，其折半查找的判定樹深度為 log 222 + 1=5 ，且該判定樹不是滿二叉樹，即查找失敗時至多比較 5 次，至少比較 4 次。

（ 6）折半搜索與二叉排序樹的時間性能（）。
A．相同
B．完全不同
C．有時不相同
D．數量級都是 O(log 2n)
答案： C

（ 7）分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是（）。
A．（ 100 ， 80， 90 ， 60， 120 ， 110 ， 130 ）
B．（ 100 ， 120 ， 110 ， 130 ， 80， 60 ， 90）
C．（ 100 ， 60， 80 ， 90， 120 ， 110 ， 130 ）
D． (100 ， 80 ， 60， 90 ， 120 ， 130 ， 110)
答案： C
解釋： A 、 B、 C、 D 四個選項構造二叉排序樹都以 100 為根，易知 A 、 B、 D 三個序列中第一個比 100 小的關鍵字為 80，即 100 的左孩子為 80 ，而 C 選項中 100 的左孩子為 60，故選 C。

（ 8）在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為 A ，并已知A 的左孩子的平衡因子為 0 右孩子的平衡因子為 1，則應作（）型調整以使其平衡。
A ． LL
B ． LR
C． RL
D ． RR
答案： C

（ 9）下列關于 m 階 B- 樹的說法錯誤的是（）。
A ．根結點至多有 m 棵子樹
B ．所有葉子都在同一層次上
C．非葉結點至少有 m/2 (m 為偶數 )或 m/2+1 （ m 為奇數）棵子樹
D ．根結點中的數據是有序的
答案： D

（ 10）下面關于 B- 和 B+ 樹的敘述中，不正確的是（）。
A． B- 樹和 B+ 樹都是平衡的多叉樹
B． B- 樹和 B+ 樹都可用于文件的索引結構
C． B- 樹和 B+ 樹都能有效地支持順序檢索
D． B- 樹和 B+ 樹都能有效地支持隨機檢索
答案： C

（ 11） m 階 B- 樹是一棵（）。
A． m 叉排序樹
B ． m 叉平衡排序樹
C． m-1 叉平衡排序樹
D． m+1 叉平衡排序樹
答案： B

（ 12）下面關于哈希查找的說法，正確的是（）。
A．哈希函數構造的越復雜越好，因為這樣隨機性好，沖突小
B．除留余數法是所有哈希函數中最好的
C．不存在特別好與壞的哈希函數，要視情況而定
D．哈希表的平均查找長度有時也和記錄總數有關
答案： C

（ 13）下面關于哈希查找的說法，不正確的是（）。
A ．采用鏈地址法處理沖突時，查找一個元素的時間是相同的
B ．采用鏈地址法處理沖突時，若插入規定總是在鏈首，則插入任一個元素的時間是相同
的
C．用鏈地址法處理沖突，不會引起二次聚集現象
D ．用鏈地址法處理沖突，適合表長不確定的情況
答案： A
解釋：在同義詞構成的單鏈表中，查找該單鏈表表中不同元素，所消耗的時間不同。

（ 14）設哈希表長為 14，哈希函數是 H(key)=key%11 ，表中已有數據的關鍵字為 15，38，61， 84 共四個，現要將關鍵字為 49 的元素加到表中，用二次探測法解決沖突，則放入的位置是（）。
A ． 8
B ． 3
C． 5
D． 9
答案： D
解釋：關鍵字 15 放入位置 4，關鍵字 38 放入位置 5，關鍵字 61 放入位置 6，關鍵字 84放入位置 7，再添加關鍵字 49，計算得到地址為 5，沖突，用二次探測法解決沖突得到新地址為 6，仍沖突，再用用二次探測法解決沖突，得到新地址為 4，仍沖突，再用用二次探測法解決沖突，得到新地址為 9，不沖突，即將關鍵字 49 放入位置 9。

（ 15）采用線性探測法處理沖突，可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的關鍵字 ( )。
A．不一定都是同義詞
B．一定都是同義詞
C．一定都不是同義詞
D ．都相同
答案： A
解釋：所探測的這些關鍵字可能是在處理其它關鍵字沖突過程中放入該位置的。

2．應用題

（ 1）假定對有序表：（ 3， 4，5， 7， 24 ， 30， 42，54 ，63， 72， 87， 95）進行折半查找，
試回答下列問題：
①畫出描述折半查找過程的判定樹；
②若查找元素 54，需依次與哪些元素比較？
③若查找元素 90，需依次與哪些元素比較？
④假定每個元素的查找概率相等，求查找成功時的平均查找長度。
答案：
① 先畫出判定樹如下（注： mid=(1+12)/2 =6）：

② 查找元素 54，需依次與 30, 63, 42, 54 元素比較；
③ 查找元素 90，需依次與 30, 63,87, 95 元素比較；
④ 求 ASL 之前，需要統計每個元素的查找次數。判定樹的前 3 層共查找 1＋ 2×2＋ 4×3=17 次；
但最后一層未滿，不能用 8× 4，只能用 5× 4=20 次，
所以 ASL ＝ 1/12 （ 17＋ 20 ）＝ 37/12 ≈ 3.08

（ 2）在一棵空的二叉排序樹中依次插入關鍵字序列為 12， 7， 17， 11， 16， 2， 13， 9，
21， 4，請畫出所得到的二叉排序樹。
答案：

驗算方法：用中序遍歷應得到排序結果： 2,4,7,9,11,12,13,16,17,21

（ 3）已知如下所示長度為 12 的表：（ Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec ）
①試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。
②若對表中元素先進行排序構成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。
③按表中元素順序構造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。

（ 4）對圖 7.31 所示的 3 階 B- 樹，依次執行下列操作，畫出各步操作的結果。
①插入90 ② 插入25 ③ 插入45 ④刪除60

答案：

（ 5）設哈希表的地址范圍為 0～ 17 ，哈希函數為： H （ key ） =key%16 。用線性探測法處理沖突，輸入關鍵字序列：（ 10 ， 24 ， 32， 17 ， 31 ， 30， 46 ， 47 ， 40， 63 ， 49），構造哈希表，試回答下列問題：
①畫出哈希表的示意圖；
②若查找關鍵字 63 ，需要依次與哪些關鍵字進行比較？
③若查找關鍵字 60 ，需要依次與哪些關鍵字比較？
④假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。
答案：
① 畫表如下

② 查找 63, 首先要與 H(63)=63%16=15 號單元內容比較，即 63 與 31 比較 , 不匹配 ;
然后順移，與 46,47,32,17,63 相比，一共比較了 6 次！
③ 查找 60, 首先要與 H(60)=60%16=12 號單元內容比較，但因為 12 號單元為空（應當有空標記），所以應當只比較這一次即可。
④ 對于黑色數據元素，各比較 1 次；共 6 次；對紅色元素則各不相同，要統計移位的位數。 “ 63 ”需要 6 次，“ 49”需要 3 次，“ 40”需要 2 次，“ 46 ”需要 3 次，“ 47 ”需要 3 次，
所以 ASL=1/11 （ 6＋ 2＋ 3×3+6 ）＝ 23/11

（ 6）設有一組關鍵字（ 9， 01 ， 23， 14， 55， 20， 84， 27 ），采用哈希函數： H（ key ）
=key %7 ，表長為 10 ，用開放地址法的二次探測法處理沖突。要求：對該關鍵字序列構造哈
希表，并計算查找成功的平均查找長度。
答案：
平均查找長度： ASLsucc =（1+1+1+2+3+4+1+2 ） /8=15/8
以關鍵字 27 為例： H（ 27 ） =27%7=6（沖突） H 1=（ 6+1 ） %10=7（沖突）H2=（ 6+2 2） %10=0（沖突） H 3=（ 6+3 3） %10=5 所以比較了 4 次。

（ 7）設哈希函數 H（ K） =3 K mod 11 ，哈希地址空間為 0～ 10 ，對關鍵字序列（ 32 ，13，49 ，24 ， 38， 21， 4， 12 ），按下述兩種解決沖突的方法構造哈希表，并分別求出等概率下查找成功時和查找失敗時的平均查找長度 ASLsucc 和 ASLunsucc 。
①線性探測法；
②鏈地址法。

答案：
ASLsucc = （ 1+1+1+2+1+2+1+2 ） /8=11/8
ASLunsucc =（1+2+1+8+7+6+5+4+3+2+1 ） /11=40/11

②

ASLsucc = （ 15+23 ） /8=11/8
ASLunsucc=（1+2+1+2+3+1+3+1+3+1+1 ） /11=19/11

3．算法設計題

（ 1）試寫出折半查找的遞歸算法。
[算法描述 ]

int BinSrch （ rectype r[ ] ， int k ， low ， high ） // 在長為 n 的有序表中查找關鍵字 k，若查找成功，返回 k 所在位置，查找失敗返回 0。 {if （ low ≤ high ） //low 和 high 分別是有序表的下界和上界{mid= （ low+high ） /2 ；if （ r[mid].key==k ） return （ mid ）；else if （ r[mid].key>k ） return （ BinSrch （ r,k ， mid+1 ， high ）） ; else return （ BinSrch （ r,k ， low ， mid-1 ）） ; } else return （ 0）； // 查找失敗。 }// 算法結束

（ 2）試寫一個判別給定二叉樹是否為二叉排序樹的算法。
[題目分析 ] 根據二叉排序樹中序遍歷所得結點值為增序的性質，在遍歷中將當前遍歷結點與其前驅結點值比較，即可得出結論，為此設全局指針變量 pre （初值為 null ）和全局變量 flag ，初值為 true 。若非二叉排序樹，則置 flag 為 false 。
[ 算法描述 ]

#define true 1 #define false 0 typedef struct node {datatype data; struct node *lchild,*rchild;} *BTree; void JudgeBST （ BTree T,int flag ） // 判斷二叉樹是否是二叉排序樹，本算法結束后，在調用程序中由 flag 得出結論。 { if （ T!=null && flag ）{ Judgebst （ T->lchild,flag ）； // 中序遍歷左子樹if （ pre==null ） pre=T ； // 中序遍歷的第一個結點不必判斷else if （ pre->data<T->data ） pre=T ； // 前驅指針指向當前結點else{flag=flase ； } // 不是完全二叉樹Judgebst （ T->rchild,flag ）； // 中序遍歷右子樹 }//JudgeBST 算法結束

（ 3）已知二叉排序樹采用二叉鏈表存儲結構，根結點的指針為 T ，鏈結點的結構為（ lchild,data,rchild ），其中 lchild ， rchild 分別指向該結點左、右孩子的指針， data 域存放結
點的數據信息。請寫出遞歸算法，從小到大輸出二叉排序樹中所有數據值 >=x 的結點的數據。
要求先找到第一個滿足條件的結點后，再依次輸出其他滿足條件的結點。
[ 題目分析 ] 本題算法之一是如上題一樣，中序遍歷二叉樹，在“訪問根結點”處判斷結
點值是否≥ x，如是則輸出，并記住第一個≥ x 值結點的指針。這里給出另一個算法，利用二叉排序樹的性質，如果根結點的值 >=x, 則除左分枝中可能有 <x 的結點外都應輸出。所以從根結點開始查找，找到結點值 <x 的結點后，將其與雙親斷開輸出整棵二叉排序樹。如果根結點的值 <x, 則沿右子樹查找第一個≥ x 的結點，找到后，與上面同樣處理。

void Print （ BSTree t ）// 中序輸出以 t 為根的二叉排序樹的結點{ if （ t ） {Print （ t->lchild ）；Cout<<t-data ；Print （ t->rchild ）；} } void PrintAllx(BSTree bst ， datatype x ）// 在二叉排序樹 bst 中，查找值≥ x 的結點并輸出 {p=bst ；if （ p）{ while （ p && p->data<x ） p=p->rchild ； // 沿右分枝找第一個值≥ x 的結點bst=p; //bst 所指結點是值≥ x 的結點的樹的根if （ p）{f=p; p=p->lchild ； // 找第一個值 <x 的結點while （ p && p->data ≥ x） // 沿左分枝向下，找第一個值 <x 的結點{f=p ； p=p->lchild ； } //f 是 p 的雙親結點的指針，指向第一個值≥ x 的結點if (p) f->lchild=null; // 雙親與找到的第一個值 <x 的結點斷開Print(bst) ； // 輸出以 bst 為根的子樹}// while}// 內層 if （ p）}// 第一層 if （ p）}

（ 4）已知二叉樹 T 的結點形式為（ lling,data,count,rlink ），在樹中查找值為 X 的結點，若找到，則記數（ count ）加 1，否則，作為一個新結點插入樹中，插入后仍為二叉排序樹，寫出其非遞歸算法
[算法描述 ]

void SearchBST(BiTree &T,int target){ BiTree s,q,f;// 以數據值 target, 新建結點 s s=new BiTNode; s->data.x=target; s->data.count=0; s->lchild=s->rchild=NULL; if(!T){ T=s; return ; } //如果該樹為空則跳出該函數f=NULL; q=T; while (q){ if (q->data.x==target){ q->data.count++; return ; } // 如果找到該值則計數加一f=q; if (q->data.x>target) // 如果查找值比目標值大，則為該樹左孩子q=q->lchild; else // 否則為右孩子q=q->rchild; }// 將新結點插入樹中if(f->data.x>target) f->lchild=s; else f->rchild=s; }

（ 5）假設一棵平衡二叉樹的每個結點都表明了平衡因子 b，試設計一個算法，求平衡二叉樹的高度。
[ 題目分析 ] 因為二叉樹各結點已標明了平衡因子 b，故從根結點開始記樹的層次。根結點的層次為 1，每下一層，層次加 1，直到層數最大的葉子結點，這就是平衡二叉樹的高度。當結點的平衡因子 b 為 0 時，任選左右一分枝向下查找，若 b 不為 0，則沿左（當 b=1 時）或右（當 b=-1 時）向下查找。
[ 算法描述 ]

int Height （ BSTree t ）// 求平衡二叉樹 t 的高度 {level=0 ； p=t ；while （ p）{level++ ； // 樹的高度增 1 if （ p->bf<0 ） p=p->rchild ； //bf=-1 沿右分枝向下//bf 是平衡因子，是二叉樹 t 結點的一個域，因篇幅所限，沒有寫出其存儲定義else p=p->lchild ； //bf>=0 沿左分枝向下}// whilereturn （ level ）； // 平衡二叉樹的高度 } // 算法結束

（ 6）分別寫出在散列表中插入和刪除關鍵字為 K 的一個記錄的算法，設散列函數為 H，解決沖突的方法為鏈地址法。
[算法描述 ]

bool insert(){ int data; cin>>data; int ant=hash(data); LinkList p=HT[ant]; // 初始化散列表while (p->next){ if(p->next->data==data) return false; p=p->next; } //找到插入位置LinkList s; s=new LNode; s->data=data; s->next=p->next; p->next=s; //插入該結點return true; } bool deletes(){ int data; cin>>data; int ant=hash(data); LinkList p=HT[ant]; // 初始化散列表while (p->next){ if(p->next->data==data){ LinkList s=p->next; p->next=s->next; delete s; //刪除該結點return true; } // 找到刪除位置p=p->next ； // 遍歷下一個結點} return false; }