数据结构与算法实验题 条形图轮廓问题

设 h 为树的高度,也就是根到叶子的边数.
如果所有内部结点都有 2 个子结点,那么叶子数是：2^h
如果所有内部结点都有 3 个子结点,那么叶子数是：3^h
现在有 9 个叶子,也就是：2^h

平均比较次数（也就是平均查找长度）是(1+2+3+,+n)/n= (n+1)/2
答案B

第一题用python写的，第二题用c++写的。在http://pat.zju.edu.cn测试通过# 第一题
def main():
text = raw_input()
n = int(text[0:text.find(' ')])
m = int(text[text.find(' ')+1:])

root = build(n)
check(root, m)

def build(n):
raw_name = raw_input()
name = raw_name.strip()
root = {}
root['name'] = name
root['layer'] = 0
root['child'] = {}
root['sibling'] = {}

pre_node = root
for i in range(1,n):
raw_name = raw_input()
name = raw_name.strip()
cur_layer = raw_name.index(name)/2
cur_node = {}
cur_node['name'] = name
cur_node['layer'] = cur_layer
cur_node['child'] = {}
cur_node['sibling'] = {}
if cur_layer == pre_node['layer']:
pre_node['sibling'] = cur_node
elif cur_layer == pre_node['layer']+1:
pre_node['child'] = cur_node
elif cur_layer == pre_node['layer']+1:
print 'error!n'
break
elif cur_layer < pre_node['layer']:
path = getpath(root, pre_node['name'])
pre_subling = {}
for p in path:
if p['layer'] > cur_layer:
break
else:
pre_subling = p
pre_subling['sibling'] = cur_node
pre_node = cur_node

return root

def check(root, m):
#X is a child of Y
#X is the parent of Y
#X is a sibling of Y
#X is a descendant of Y
#X is an ancestor of Y
for i in range(0,m):
text = raw_input()
X = text[0:text.find(' ')]
Y = text[text.rfind(' ')+1:]
if 'child' in text:
path = getpath(root, X)
if len(path)>=2 and path[-2]['name'] == Y:
print True
else:
print False
if 'parent' in text:
path = getpath(root, Y)
if len(path)>=2 and path[-2]['name'] == X:
print True
else:
print False
if 'sibling' in text:
pathX = getpath(root, X)
pathY = getpath(root, Y)
if len(pathX)>=2 and len(pathY)>=2 and pathX[-2]['name'] == pathY[-2]['name']:
print True
else:
print False
if 'descendant' in text:
path = getpath(root, X)
for p in path:
if p['name'] == Y:
break
if p['name'] == Y:
print True
else:
print False
if 'ancestor' in text:
path = getpath(root, Y)
for p in path:
if p['name'] == X:
break
if p['name'] == X:
print True
else:
print False

def getpath(root, node_name):
path = [root]
next_node = root['child']
while True:
while next_node != {}:
path.append(next_node)
if next_node['name'] == node_name:
return path
next_node = next_node['child']

next_node = path.pop()
if path == []:
return path
else:
next_node = next_node['sibling']

if __name__ == "__main__":
main()// 第二题
#include
#include

using namespace std;

const int MAX = 224;
typedef struct
{
int index;
double no;
int range;
}ELEM;
int cmp_des( const ELEM a, const ELEM b ){
return a.no>b.no; // 降序
}
int cmp_aes( const ELEM a, const ELEM b ){
return a.index}
int main()
{
int n,m;
cin>>n>>m;

double data[5][MAX];
int paiming[5][MAX];
ELEM tmp[MAX];
int country[MAX];
int i,j;
for (i=0;i{
cin>>data[1][i]>>data[2][i]>>data[0][i];
data[3][i] = data[1][i]/data[0][i];
data[4][i] = data[2][i]/data[0][i];
}
for (i=0;icin>>country[i];

for (i=1;i<=4;i++)
{
for (j=0;j{
tmp[j].index = j;
tmp[j].no = data[i][j];
}
sort(tmp,tmp+n,cmp_des);
for (j=0;j{
if (j>0 tmp[j].no==tmp[j-1].no)
tmp[j].range = tmp[j-1].range;
else
tmp[j].range = j+1;
}
sort(tmp,tmp+n,cmp_aes);
for (j=0;j{
paiming[i][j] = tmp[j].range;
}
}

int top_12,top_34,top_1234;
for (i=0;i{
top_12 = paiming[1][country[i]]<=paiming[2][country[i]]?1:2;
top_34 = paiming[3][country[i]]<=paiming[4][country[i]]?3:4;
top_1234 = paiming[top_12][country[i]]<=paiming[top_34][country[i]]?top_12:top_34;
printf("%d:%d",(int)paiming[top_1234][country[i]],(int)top_1234);
if (iprintf(" ");
}

return 0;
}

数据结构与算法分析（电子工业出版社）不错