设记录R1，R2，…，Rn按关键字值从小到大顺序存储在数组r[1．．n]中，在r[n+1]处设立一个监督哨，其关键字值为+∞。试写一查找给定关键字k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。

admin2017-01-04 47

问题设记录R₁，R₂，…，R_n按关键字值从小到大顺序存储在数组r[1．．n]中，在r[n+1]处设立一个监督哨，其关键字值为+∞。试写一查找给定关键字k的算法，并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。

选项

答案intSearch(rectype r[]，int n，keytype k){ ／／在n个关键字从小到大排列的顺序表中，查找关键字为k的结点 r[n+1]．key=MAXINT；／／在高端设置监视哨 int i=1： while(r[i]．key＜k)i++； if(r[n+1]．key==k)return(i％(n+1))； else return(0)； } 查找过程的判定树是单枝树。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为(n+1)／2。

解析

转载请注明原文地址:https://kaotiyun.com/show/iQRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简述魏晋玄学的产生背景及其代表人物的基本思想。(2009年统考真题)

布雷顿森林体系是如何建立的，包括哪些内容?

1920年，苏俄农民中流传着这样的说法：“土地属于我们，面包却属于你们；水属于我们，鱼却属于你们；森林属于我们，木材却属于你们”，它反映的是战时共产主义政策()。

为了防止谷贱伤农的现象，()向汉文帝提出了人粟拜爵的建议，准许富人买粟输边，按所输多少授予爵位。这一办法的实行，使农民的处境有所改善。

晚清时期清帝年号的正确排序是

设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先不知道，但是要求在任何时刻它们占用的单元数量不超过m，试写出上述栈与队列的插入算法。

假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，

Itissuggestedthatsmoking______inpublicplaces.

结肠、直肠手术前肠道准备使用的制菌药物为【】

WouldyoubelievethatthefirstoutstandingdeafteacherinAmericawasaFrenchman?HisnamewasLaurentClerc.He【C1】______a

我国人民行使国家权力的机关是()。

下列没有语病的一句是(　　)。

Accordingtotheman,heusedtobe______.

Farewell,LibrariesA)Amazon,corn’srecentannouncementthatsalesofe-booksattheonlinemegastorehadovertakensalesofha

计算机408

学硕统考专业

简述魏晋玄学的产生背景及其代表人物的基本思想。(2009年统考真题)

布雷顿森林体系是如何建立的，包括哪些内容?

1920年，苏俄农民中流传着这样的说法：“土地属于我们，面包却属于你们；水属于我们，鱼却属于你们；森林属于我们，木材却属于你们”，它反映的是战时共产主义政策()。

为了防止谷贱伤农的现象，()向汉文帝提出了人粟拜爵的建议，准许富人买粟输边，按所输多少授予爵位。这一办法的实行，使农民的处境有所改善。

晚清时期清帝年号的正确排序是

设有m个连续单元供一个栈与队列使用，且栈与队列的实际占用单元数事先不知道，但是要求在任何时刻它们占用的单元数量不超过m，试写出上述栈与队列的插入算法。

假设二叉树采用二叉链表存储结构存储，试设计一个算法，求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，

Itissuggestedthatsmoking______inpublicplaces.

结肠、直肠手术前肠道准备使用的制菌药物为【】

WouldyoubelievethatthefirstoutstandingdeafteacherinAmericawasaFrenchman?HisnamewasLaurentClerc.He【C1】______a

我国人民行使国家权力的机关是()。

下列没有语病的一句是( )。

Accordingtotheman,heusedtobe______.

Farewell,LibrariesA)Amazon,corn’srecentannouncementthatsalesofe-booksattheonlinemegastorehadovertakensalesofha

下列没有语病的一句是(　　)。