顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定Ⅳ为线性表中结点数，且每次查找都是成功的。 (2)

admin2019-01-30 19

问题顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定Ⅳ为线性表中结点数，且每次查找都是成功的。
(2)

选项 A、N+1
B、2log₂N
C、log₂N
D、N／2

答案C

解析此题考查的知识点是各类查找算法的比较次数计算。顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1)／2，即查找成功时的平均比较次数约为表长的一半。
二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为[log₂n]+1。这样，折半查找成功时，关键字比较次数最多不超过[log₂n]+1。所以，(1)应选择D，(2)应选C。

转载请注明原文地址:https://jikaoti.com/ti/MsfjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定Ⅳ为线性表中结点数，且每次查找都是成功的。 (2)

计算机408

学硕统考专业

北宋时期，由于原有的市坊制度被打破，因此北宋政府控制商人和商业主要通过()。

战国初期，上党地区在下列哪一个国家的控制范围之内?()

下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

“二战”后，为了同苏联争夺更广阔的亚洲、非洲和拉丁美洲地区，建立美国控制下的冷战联盟体系，杜鲁门政府向亚非拉地区推行的经济与技术援助计划是()

下列选项中，控制了西域政权的是()。

下列明末清初来华传教士，按时间顺序排列，正确的是（）。

系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。

1839年将细胞学说从植物界扩展到动物界，形成了适用于整个生物界的细胞学说的是()。

文件系统的主要目的是()。

如果互联的局域网高层分别采用TCP／IP协议与SPX／IPX协议，那么我们可以选择的多个网络互联设备应该是()。

以下哪一症状不是胃寒证所见

下列哪些药物含有儿茶酚的结构（　　）。

下列项目中，属于所有者权益的会计科目是()。

甲、乙、丙三人投资设立一家有限合伙企业，甲为普通合伙人，乙和丙为有限合伙人，下列财产中，可以作为乙的出资方式的有()。

下列可以被核准注册为商标的有()

陶行知最早创办的学校是()。

计算机中的堆栈，通常是指(　　　)一部分，但遵循先进后出的规则。

数据模型按不同的应用层次分为三种类型，它们是【】数据模型、逻辑数据模型和物理数据模型。

Isyourfamilyinterestedinbuyingadog?Adogcanbeahappy【B1】______toyourfamily,butifyouchoosethewrongkindofdog

NowHiring:Green-CollarWorkers[A]Ifyou’relookingforagood,safejob,itmakessensethesedaystogogreen.TheObamaAdm

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (1) )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( (2) )。在此假定Ⅳ为线性表中结点数，且每次查找都是成功的。 (2)

计算机408

学硕统考专业

北宋时期，由于原有的市坊制度被打破，因此北宋政府控制商人和商业主要通过()。

战国初期，上党地区在下列哪一个国家的控制范围之内?()

下列长征事件的正确顺序是()。①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥

“二战”后，为了同苏联争夺更广阔的亚洲、非洲和拉丁美洲地区，建立美国控制下的冷战联盟体系，杜鲁门政府向亚非拉地区推行的经济与技术援助计划是()

下列选项中，控制了西域政权的是()。

下列明末清初来华传教士，按时间顺序排列，正确的是（）。

系统地阐明道家思想的著作《淮南鸿烈》，也叫《淮南子》，是汉武帝时()集宾客写成的。《淮南子》问世时，黄老思想在政治上已不占支配地位了。

1839年将细胞学说从植物界扩展到动物界，形成了适用于整个生物界的细胞学说的是()。

文件系统的主要目的是()。

如果互联的局域网高层分别采用TCP／IP协议与SPX／IPX协议，那么我们可以选择的多个网络互联设备应该是()。

以下哪一症状不是胃寒证所见

下列哪些药物含有儿茶酚的结构（ ）。

下列项目中，属于所有者权益的会计科目是()。

甲、乙、丙三人投资设立一家有限合伙企业，甲为普通合伙人，乙和丙为有限合伙人，下列财产中，可以作为乙的出资方式的有()。

下列可以被核准注册为商标的有()

陶行知最早创办的学校是()。

计算机中的堆栈，通常是指( )一部分，但遵循先进后出的规则。

数据模型按不同的应用层次分为三种类型，它们是【】数据模型、逻辑数据模型和物理数据模型。

Isyourfamilyinterestedinbuyingadog?Adogcanbeahappy【B1】______toyourfamily,butifyouchoosethewrongkindofdog

NowHiring:Green-CollarWorkers[A]Ifyou’relookingforagood,safejob,itmakessensethesedaystogogreen.TheObamaAdm

下列哪些药物含有儿茶酚的结构（　　）。

计算机中的堆栈，通常是指(　　　)一部分，但遵循先进后出的规则。