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

admin2019-01-30 25

问题顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( (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://kaotiyun.com/show/KdRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列不属于延安整风运动的文件是()。

提出天人关系应当“交相胜，还相用”的观点是()。

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争，这一古老文件是（）。

电子计算机的发展经过了：①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。

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

三国时期，魏、蜀、吴三国灭亡的历史顺序是()。

系统阐明社会主义初级阶段理论是在()。

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

当溶液中Bi3+、Pb2+浓度均为10-2mol/L时，可以选择滴定Bi3+。（已知：lgKBiY=27.94，lgKPbY=18.04）。（）

要使word能使用自动更正经常输错的单词，应使用______功能。

依据《社会生活环境噪声排放标准》，某商场拟建在城市快速路附近，则该商场执行的昼夜噪声排放限值分别是()。

()是指计入资产负债表内的业务所形成的敞口头寸，等于表内的即期资产减去即期负债。

我国《公司法》将公司分为有限责任公司和()。

商业银行因支付清算和业务合作等需要，存在同业及其他金融机构的款项叫作()。

安排怀孕七个月以上的女职工延长工作时间和从事夜班劳动的，按每侵害一名女职工予以()元以内标准的处罚。

在正弦交流电路中，电感元件的瞬时值伏安关系可表达为()。

以占有作为生效要件的法律行为包括()。