试题详情
- 简答题已知下列各种初始状态(长度为n)的元素,试问当利用直接插入排序进行排序时,至少需要进行多少次比较(要求排序后的记录由小到大顺序排列)? ⑴关键码从小到大有序(key1< key2< …< keyn)。 ⑵关键码从大到小有序(key1> key2 >…> keyn)。 ⑶奇数关键码顺序有序,偶数关键码顺序有序(key1< key3< …,key2key4…)。 ⑷前半部分元素按关键码顺序有序,后半部分元素按关键码顺序有序,即:(key1< key2< …< keym,keym+1< keym+2 <…)
- 依题意,最好情况下的比较次数即为最少比较次数。
⑴插入第i(2≤i≤n)个元素的比较次数为1,因此总的比较次数为:1+1+……+1=n-1
⑵插入第i(2≤i≤n)个元素的比较次数为i,因此总的比较次数为:2+3+……+n=(n-1)(n+2)/2
⑶比较次数最少的情况是所有记录关键码按升序排列,总的比较次数为:n-1
⑷在后半部分元素的关键码均大于前半部分元素的关键码时需要的比较次数最少,总的比较次数为:n-1 关注下方微信公众号,在线模考后查看
热门试题
- 对于给定结点的关键字集合K={5,7,3
- 将一棵树转换成二叉树后,根结点没有左子树
- 串s是s本身的真子串。
- 设一棵哈夫曼树共有14个非叶结点,则该树
- 简述数据结构中讨论的三种经典结构的逻辑特
- 基于关键字比较大小的排序算法中,()排序
- 双向链表
- 稀疏矩阵的三元组有()列。
- 请画出下图的邻接矩阵。
- 广义表(f ,h
- 折半搜索只适合用于()。
- 若把整个广义表也看为一个表结点,则该结点
- 在单链表中设置头结点的作用是()。
- 数据结构里,栈的特性是后进先出(Last
- 算法的设计要求包含的选项是()。
- 设计一个判别表达式中左右括号是否配对的算
- 在执行某个排序算法过程中,出现了排序码朝
- 三叉链表比二叉链表多一个指向()的指针域
- 简述二叉树的常用操作及各操作的含义。
- 排序方法中,从无序序列中选择关键字最小的