第九章查詢（參***）
9.1 int seqsearch( rectype r, keytype k)
// 監視哨設在n個元素的公升序順序表低下標端，順序查詢關鍵字為k的資料
// 元素。若存在，則返回其在順序表中的位置，否則，返回0
r[0].key=k; i=n;
while (r[i].key>k) i--;
if (i>0 && r[i].key==k) return(i);
else return(0)
} // 演算法結束
查詢過程的判定樹是單支樹。
查詢成功的平均查詢長度為
asl=∑pici =1/n*∑i = 1/2*(n+1)
查詢不成功的平均查詢長度為 asl=1/(n+1)(∑i+(n+1))=(n+2)/2.
9.2typedef struct lnode
seqlist;
typedef struct snode
snode;
void locate(seqlist l,keytype x)
// 在鍊錶中查詢給定值為x的結點，並保持訪問頻繁的結點在前
//呼叫本函式前，各結點的訪問頻率域（freq）值均為0。
else // 演算法結束
void locate(snode l,int n;keytype x)
// 在具有n個元素順序儲存的線性表l中查詢給定值為x的結點，並保持
// 訪問頻繁的結點在前。呼叫本函式前，各結點的訪問頻率域值為0。
else
} // 演算法結束
9.3 注：判定樹中的編號為元素在有序表中的序號
9.4 int binsearch(rectype s,int low,int high, keytype k)
// 有序的順序表s,其元素的低端和高階下標分別為low和 high.
// 本演算法遞迴地折半查詢關鍵字為k的資料元素，若存在，則返回其在有序
// 順序表中的位置，否則，返回0。
else return(0);
} // 演算法結束
9.5 int level(bstnode *bst, keytype k)
// 在二叉排序樹bst中，求關鍵字k所在結點的層次
// 沿右子樹
else // 沿左子樹
if (p->key==k) return (++num); // 查詢成功
else return(0); // 查詢失敗
} // 演算法結束
其遞迴演算法如下：
int level(bstnode *bst, keytype k，int num)
// 在二叉排序樹中，求關鍵字k所在結點的層次的遞迴演算法，呼叫時num=0
// 演算法結束
9.6 bstnode *ancestor(bstnode *bst)
// bst是非空二叉排序樹根結點的指標。
// a和b是bst樹上的兩個不同結點，本演算法求a和b的最近公共祖先。
// 設a和b的關鍵字分別為a和b，不失一般性，設a
else if (p->key==b)
else if (p-key>a && p->key else if (p->key>b) return(ancestor(p->lchild)); // 沿左子樹
else return(ancestor(p->rchild)); // 沿右子樹
} // 演算法結束
9.7 int bstree(bstnode *bst, bstnode *pre)
// bst是二叉樹根結點的指標,pre總指向當前訪問結點的前驅，呼叫本函式
// 時為null。本演算法判斷bst是否是二叉排序樹。設一全程變數flag,初始值
// 為1，呼叫本函式後，若仍為1，是二叉排序樹，否則，不是二叉排序樹。
else pre=p;
bstree(bst->rchild,pre);
}}9.8（1）
asl=(1*1+2*2+3*3+3*4+2*5+1*6)/12=42/12
(2)lr(一)rl（二） r
r(三)（四）
asl=(1*1+2*2+4*3+4*4+1*5)/12=38/12
9.9 l
l r
lr l
(ll型) (lr型) (rl型)
rr (rr 型)
9.10
（1）插入關鍵字b後，b-樹的結點無變化
（2）插入關鍵字l後，結點e 和g產生**
（3）插入關鍵字p後，結點h產生**
（4）插入關鍵字q後，結點不變
（5）插入關鍵字r後，三個層次結點產生**，使b-樹增高
9.11 hegtype hashdelete(hashtable ht,hegtype k)
//ht是拉鍊法解決衝突的雜湊表，本演算法刪除關鍵字
//為k的指定結點，若刪除成功，返回k；否則
//返回null
else
《資料結構》第九章集合
第九章集合 一 選擇題 1.若查詢每個記錄的概率均等，則在具有n個記錄的連續順序檔案中採用順序查詢法查詢乙個記錄，其平均查詢長度asl為 北京航空航天大學 2000 一 8 2分 a n 1 2 b.n 2 c.n 1 2 d.n 2.對n個元素的表做順序查詢時，若查詢每個元素的概率相同，則平均查詢...
資料結構作業系統第九章答案
判別給定二叉樹t是否為二叉排序樹。若是，則返回true，否則false 二叉樹的型別bitree定義如下 typedef struct elemtype typedef struct bitnode bitnode,bitree status isbstree bitree t 判別給定二叉樹t是否...
第九章習題
第九章一般均衡和福利經濟學 一 選擇題 1 當最初的變化影響廣泛分散到很多市場，每個市場只受到輕微的影響時，d a.要求用一般均衡分析 b.一般均衡分析很可能推出錯誤的結論 c.區域性均衡分析很可能推出錯誤的結論 d.區域性均衡分析將提供合理可靠的 2 被西方經濟學界推崇為 福利經濟學之父 的是 b...