在一个含有n个元素的顺序表中查找值为x元素,对应算法的时间复杂度为()。
A、O(1)
B、
C、O(n)
D、
A、O(1)
B、
C、O(n)
D、
第4题
假设L含有n个不同的元素,其中,k为非负整数。如果已知x在表L中,且在L的每个位置的概率相等,那么用顺序搜索算法查找元素x,该算法平均情况下的比较次数是多少?从下面备选的答案中选出正确答案的标号填入括号内。()
A、
B、
C、
D、
E、
F、
第5题
假设L含有n个不同的元素,其中,k为非负整数。如果已知x在表L中,且在L的每个位置的概率相等,那么用顺序搜索算法查找元素x,该算法平均情况下的比较次数是多少?从下面备选的答案中选出正确答案的标号填入括号内。()
A、
B、
C、
D、
E、
F、
第6题
【Test-9-2】下面算法的功能是:编写一个递归算法实现在有序顺序表上的折半查找。算法的参数表中应增加两个形参 left 和 right,分别指定算法在本层执行时的查找区间的左、右端点。当查找成功时函数返回查找到的元素的存放位置;当查找不成功时函数返回-1。 请在空白处填入正确的语句。 递归算法的首部为 int binarySearch ( seqList &L, DataType x, int left, int right )。主程序的调用方式为 { int loc = binarySearch( L, x, 0, L.n-1 )。 int binarySearch(seqList &L, DataType x, int left, int right) { //在查找区间[left..right]采用折半查找算法查找与给定元素匹配的元素。 int mid = ________①_______; if(__________②_______) { mid = (left + right) / 2; if(________③_________) mid = binarySearch1(L, x, _____④_______, right); //右缩区间 else if(x < data[mid]) mid = binarySearch(L, x, left, ______⑤_______); //左缩区间 } return _______⑥_________; };
第7题
【Ex-9-3】线性表中各结点的查找概率不等,则可用如下策略提高顺序查找的效率。若找到与给定值相匹配的元素,则将该元素与其直接前驱元素(若存在)交换,使得经常被查找的元素尽量位于表的前端。下面算法的功能是:在线性表的顺序存储表示和链接存储表示的基础上实现顺序查找。请在空白处填入正确的语句。 【解答】: (1) int SeqSearch ( SeqList &L, elemType x ) { // 在顺序表 L 中从表的前端开始查找与给定值 x 匹配的元素,找到后与它前一个元素 //(若有)交换位置,再返回新的位置(注意地址从 0 开始)。 int i = 0; elemType temp; while ( __________①__________ ) i++; if ( _____②_________ ) return 0; //查找不成功 else { //查找成功 if ( i > 0 ) { temp = L.elem[i - 1]; L.elem[i - 1] = L.elem[i]; L.elem[i] = temp; } return i; } } (2) LinkNode *LinkSearch ( LinkList &L, elemType x ) { LinkNode *p = L->link, _______③_________; while ( p != NULL && p->elem != x ) { ppre = pre; _____④_____; p = p->link; } if ( p != NULL && pre != L ) { //查找成功,交换结点 p 与 pre _______⑤_______; p->link = pre; ppre->link = p; } return p; }
第8题
形参 left 和 right,分别指定算法在本层执行时的查找区间的左、右端点。当查找成功时函数返回查找到的元素的存放位置;当查找不成功时函数返回-1 typedef int ElemType; struct seqList{ ElemType data[]; //有序顺序表 int n; //表长 }; int BinarySearch(seqList *L, ElemType x, int left, int right) { int mid =_______; if(________) { mid = (left + right) / 2; if(x > L->data[mid]) mid = BinarySearch1(L, x, ________, right); else if(x < L->data[mid]) mid = BinarySearch(L, x, left, ________); } return _________; }; main() { seqList *L; int loc = BinarySearch( L, x, 0, L->n-1 ); }
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!