请写一非递归算法，对于任意给定的k值，该算法在长度为&ensp;n、且元素按..._考试资料网

网站首页考试题库模拟考场智能家居网课试题

普通考研

题库首页每日一练章节练习

问答题 请写一非递归算法，对于任意给定的k值，该算法在长度为 n、且元素按值严格递增排列的顺序表A[1..n]中采用折半查找法查找值不大于k的最大元素，若表中存在这样的元素，则算法返回该元素在表中的位置，否则，算法返回信息0。（假设表中元素分别为一个正整数）
例如，对于顺序表A[1..10]=(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)，
当k=8时，满足条件的元素为8，返回位置4；
当k=13时，满足条件的元素为12，返回位置6；
当k=1时，无满足条件的元素，返回信息0。

参考答案：

您可能感兴趣的试卷

你可能感兴趣的试题

1.问答题请根据堆积（Heap）的定义，以二叉树的形式画出序列（26，5，77，1，61，11，59，15，48，19）对应的（大顶）堆积。

参考答案：

2.问答题 请画出如图所示的连通图的最小生成树。

参考答案：

3.问答题 下列算法的功能是在由list所指的非空线性链表的第i个结点（假设链表中存在第i个结点，且i≥1）后面插入一个由p指的结点。
请在算法的空白处（横线上方）填上必要的内容，使算法完整。

参考答案：

①j<i
②p->link=q->link;

4.问答题数据文件的基本操作有插入、删除、修改和查找等，请问：其中最基本的操作是哪一个？为什么？

参考答案：数据文件最基本的操作是查找，插入、删除和修改等操作都是建立在查找操作之上的，因为在进行这些操作之前都需要先通过查找操作来...

点击查看完整答案

5.问答题拓扑排序的主要功能是什么？对于一个存在拓扑序列的有向图，通过拓扑排序得到的拓扑序列是否惟一？

参考答案：拓扑排序的主要功能是检测一个有向图中是否存在回路。对于一个存在拓扑序列的有向图，通过拓扑排序得到的拓扑序列不一定惟一。

6.问答题有人说：“在一棵二叉树中，对于除叶结点外的任意结点，如果其值大于它的左孩子结点（若存在）的值，并且小于或等于它的右孩子结点（若存在）的值，则该二叉树一定是二叉排序树”，该说法正确吗？若你认为不正确，请举一例说明。

参考答案：此说法不正确。二叉排序树的定义是一个递归定义，要求其左、右子树都是二叉排序树，因此，该说法不符合定义。以下图...

点击查看完整答案

7.问答题若5个元素的进栈序列是a、b、c、d、e，利用堆栈操作能否得到出栈序列b、c、a、e、d和d、b、a、c、e？对于不能得到的出栈序列，请说明理由。

参考答案：能够得到出栈序列b、c、a、e、d，但不能得到出栈序列d、b、a、c、e。因为若出栈序列以元素d开始，则说明在d之前的进...

点击查看完整答案

8.单项选择题下面给出的四种排序法中，排序过程中元素之间的比较次数与排序法无关的是（）。

A.选择排序法
B.插入排序法
C.快速排序法
D.堆积排序法

点击查看答案

9.单项选择题与直接插入排序法比较，折半插入排序法减少了排序过程中的（）。

A.排序总的趟数
B.元素的移动次数
C.元素之间的比较次数
D.使用的辅助空间的数量

点击查看答案

10.单项选择题散列技术中的散列冲突是指（）。

A.两个元素具有相同的序号
B.两个元素的键值不同，而其他属性相同
C.元素过多
D.不同键值的元素对应着相同的存储地址

点击查看答案