数据结构与算法在一个长度为n的顺序线性表中顺序查找值为X的元素是,查找成功时的平均查找长度为A (n-1)/2B (n+

sugg9102022-10-04 11:39:541条回答

数据结构与算法
在一个长度为n的顺序线性表中顺序查找值为X的元素是,查找成功时的平均查找长度为
A (n-1)/2
B (n+1)/2
C n/2
D n

已提交,审核后显示!提交回复

共1条回复
白脸大花猫 共回答了20个问题 | 采纳率90%
平均比较次数(也就是平均查找长度)是(1+2+3+,+n)/n= (n+1)/2
答案B
1年前

相关推荐

数据结构与算法 2-3树是一种特殊的树,它满足两个条件
数据结构与算法 2-3树是一种特殊的树,它满足两个条件
2-3树是一种特殊的树,它满足两个条件
(1)每个内部结点有两个或三个子结点;(2)所有的叶结点到根的路径长度相同;
如果一棵2-3树有9个叶结点,那么它可能有_________个非叶结点.(多项)
ddnn为兽1年前1
enluan 共回答了18个问题 | 采纳率94.4%
设 h 为树的高度,也就是根到叶子的边数.
如果所有内部结点都有 2 个子结点,那么叶子数是:2^h
如果所有内部结点都有 3 个子结点,那么叶子数是:3^h
现在有 9 个叶子,也就是:2^h
数据结构与算法实验题 条形图轮廓问题
数据结构与算法实验题 条形图轮廓问题
★实验任务
在x 轴上水平放置着n 个条形图.条形图的轮廓是消去这n 个条形图的隐藏线后得到的
图形,如图所示.
每个条形图由3 元组(Li,Hi,Ri)表示.其中,Li 和Ri 分别为条形图左右竖线的x
坐标值,Hi 为条形图的高度.例如,上图的8 个条形图表示为:(1,11,5),(2,6,7),(3,13,9),
(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28).条形图的轮廓可用轮廓向
量(V1,V2,…,Vm)表示.当i 为奇数时,Vi 表示条形图轮廓中一条竖线的x 坐标值:当
i 为偶数时,Vi 表示条形图轮廓中一条横线的高度.例如,上图的条形图轮廓向量为
(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0).
现在,对于给点的n 个条形图,计算其条形图轮廓.
★数据输入
第一行一个正整数n,表示n 个条形图(1 <= n <= 4000).
接下来n 行,每行有3 个整数(Li,Hi,Ri),Li 和Ri 分别为条形图左右竖线的x 坐标
值,Hi 为条形图的高度(-3000 <= Li,Ri<= 3000, 1 <= Hi <= 1000).
★数据输出
输出计算出的条形图轮廓向量.
输入示例输出示例
8
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28


输出
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
冰下泉流1年前1
grasslandpaul 共回答了16个问题 | 采纳率93.8%
#include
#include
#include
#define LBound (-3000)
#define UBound 3000
#define Cod2Idx(x) ((x)-LBound)
#define Size Cod2Idx(UBound+1)
int main() {
int hs[Size],n;
int i,l,r,h,i0,i1;
memset(hs,0,sizeof(*hs) * Size);
scanf("%d",&n);
for (i0=UBound,i1=LBound; n>0; n--) {
scanf("%d %d %d",&l,&h,&r);
if (l < i0) i0 = l;
if (r > i1) i1 = r;
for (i=l; i
数据结构与算法的实验内容4-05. 家谱处理 输入格式说明:输入首先给出2个正整数N
数据结构与算法的实验内容

4-05. 家谱处理

输入格式说明:

输入首先给出2个正整数N(2<=N<=100)和M(<=100),其中N为家谱中名字的数量,M为家谱中陈述语句的数量,输入的每行不超过70个字符。

名字的字符串由不超过10个英文字母组成。在家谱中的第一行给出的名字前没有缩进空格。家谱中的其他名字至少缩进2个空格,即他们是家谱中最早祖先(第一行给出的名字)的后代,且如果家谱中一个名字前缩进k个空格,则下一行中名字至多缩进k+2个空格。

在一个家谱中同样的名字不会出现两次,且家谱中没有出现的名字不会出现在陈述语句中。每句陈述语句格式如下,其中X和Y为家谱中的不同名字:

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


输出格式说明:

对于测试用例中的每句陈述语句,在一行中输出True,如果陈述为真,或False,如果陈述为假。

样例输入与输出:


F. 奥运排行榜

时间限制

10 ms

内存限制

32000 kB

代码长度限制

8000 B

判题程序

Standard

每年奥运会各大媒体都会公布一个排行榜,但是细心的读者发现,不同国家的排行榜略有不同。比如中国金牌总数列第一的时候,中国媒体就公布“金牌榜”;而美国的奖牌总数第一,于是美国媒体就公布“奖牌榜”。如果人口少的国家公布一个“国民人均奖牌榜”,说不定非洲的国家会成为榜魁…… 现在就请你写一个程序,对每个前来咨询的国家按照对其最有利的方式计算它的排名。

输入格式说明:

输入的第1行给出2个正整数N和M(<=224,因为世界上共有224个国家和地区),分别是参与排名的国家和地区的总个数、以及前来咨询的国家的个数。为简单起见,我们把国家从0~N-1编号。之后有N行输入,第i行给出编号为i-1的国家的金牌数、奖牌数、国民人口数(单位为百万),数字均为[0,1000]区间内的整数,用空格分隔。最后面1行给出M个前来咨询的国家的编号,用空格分隔。

输出格式说明:

在一行里顺序输出前来咨询的国家的“排名:计算方式编号”。其排名按照对该国家最有利的方式计算;计算方式编号为:金牌榜=1,奖牌榜=2,国民人均金牌榜=3,国民人均奖牌榜=4。输出间以空格分隔,输出结尾不能有多余空格。

若某国在不同排名方式下有相同名次,则输出编号最小的计算方式。

样例输入与输出:


会开车的鸡1年前1
fzhawl 共回答了14个问题 | 采纳率100%
第一题用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;
}
求数据结构与算法工具书可以当字典查到各种常见算法的书,
iamxiaobai1年前1
saisai315 共回答了17个问题 | 采纳率88.2%
数据结构与算法分析(电子工业出版社)不错

大家在问