精华内容
下载资源
问答
  • 举例子计算log29=y 2的0次方和N作比较,1<9 2的1次方和N作比较,2<9 2的2次方和N作比较,4<9 2的3次方和N作比较,8<9 2的4次方和N作比较,16>9 那么相当于y=log...

    解题思路

    由于log2N=y 相当于 “2的y次方=n”
    因此:本题等价于:
    举例子计算log29=y
    2的0次方和N作比较,1<9
    2的1次方和N作比较,2<9
    2的2次方和N作比较,4<9
    2的3次方和N作比较,8<9
    2的4次方和N作比较,16>9
    那么相当于y=log29的范围在(3,4),那么则取3(不大于 log2N 的最大整数)

    java代码

    package homework1_1;
    
    /**
     * @description: ${description}
     * @create: 2019-02-03
     **/
    public class W1_1_14 {
        //方法1
        public static int lg1(int n){
            //logxN=logeN/logex,
            //log2x=loge x/loge2
            double a=Math.log(n)/Math.log(2);
            return (int)Math.floor(a);
        }
        //方法2
        public static int lg2(int n){
            int i=1;
            int result=1;
            int count=0;
            while(result<n){
                for(int j=0;j<n;j++){
                    result=result*2;
                    count++;
                    if(result>n){
                        count--;
                        break;
                    }
                }
            }
            return count;
        }
        //方法3
        public static int lg3(int n) {
            int i = 2;
            int j = 0;
            while (true) {
                i *= 2;
                j++;
                if (i >= n) {
                    return j;
                }
            }
        }
        //测试
        public static void main(String[] args) {
            for(int i=1;i<20;i++){
                int lg1 = lg1(i);
                int lg2 = lg2(i);
                int lg3 = lg3(i);
                System.out.print("N:"+i+" log2N为 ");
                System.out.print(lg1+"\t");
                System.out.print(lg2+"\t");
                System.out.print(lg3+"\t");
                System.out.println();
            }
        }
    }
    

    结果

    在这里插入图片描述

    展开全文
  • 由于二分查找每次查询都是从数组中间切开查询,所以每次查询,剩余的查询数为上一次的一半...=1,我们计算时间复杂度是按照最坏的情况进行计算,也就是是查到剩余最后一个数才查到我们想要的数据,也就是 N/(2^K)=1 ...

    由于二分查找每次查询都是从数组中间切开查询,所以每次查询,剩余的查询数为上一次的一半,从下表可以清晰的看出查询次数与剩余元素数量对应关系

    表-查询次数及剩余数
    第几次查询    剩余待查询元素数量

    从上表可以看出N/(2^K)肯定是大于等于1,也就是N/(2^K)>=1,我们计算时间复杂度是按照最坏的情况进行计算,也就是是查到剩余最后一个数才查到我们想要的数据,也就是
    N/(2^K)=1
    =>N=2^K
    =>K=log2N
    所以二分查找的时间复杂度为O(log2N) 可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O()=O(logn)
    ————————————————

    展开全文
  • 计算时间复杂度时,o(log2(2n))与o(log2(n))相同吗, 区别在于n前多个系数,
  • 计算log(N!)

    千次阅读 2017-04-22 13:36:49
    poj1423是一道计算阶乘位数的题,假设我们要求10!的位数,我们知道log10(10!)的值向下取整就是10!的位数,这里我们用stirling公式: lnN!=NlnN-N+0.5ln(2N*pi)

    poj1423是一道计算阶乘位数的题,假设我们要求10!的位数,我们知道log10(10!)的值向下取整就是10!的位数,这里我们用stirling公式:

    lnN!=NlnN-N+0.5ln(2N*pi)

    展开全文
  • 数据结构计算

    2020-08-07 13:20:51
    【解答】 log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n! 2、对下列用二元组表示的数据结构 , 试分别画出对应的逻辑结构图, 并指出属于何种结构。 ⑴ A=(D,R), 其中 D={a1, a2, a3, a4...

    1、将下列函数按它们在 n 时的无穷大阶数,从小到大排列。
    n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!,
    n2+log2n
    【解答】 log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5,
    2n/2, (3/2)n, n!

    2、对下列用二元组表示的数据结构 , 试分别画出对应的逻辑结构图,

    并指出属于何种结构。
    ⑴ A=(D,R), 其中 D={a1, a2, a3, a4} ,R={ }
    ⑵ B=(D,R), 其中 D={a, b, c, d, e, f} ,R={,}
    ⑶ C=( D ,R),其中 D={a,b,c,d,e,f} ,R={,}
    ⑷ D=(D,R), 其中 D={1, 2, 3, 4, 5, 6} ,
    R={(1, 2) ,(1, 4) ,(2, 3) ,(2, 4) ,(3, 4) ,(3, 5) ,(3, 6) ,
    (4, 6)}
    【解答】⑴ 属于集合,其逻辑结构图如图 1-4(a) 所示;⑵ 属于线
    性结构,其逻辑结构图如图 1-4(b) 所示;
    ⑶ 属于树结构,其逻辑结构图如图 1-4© 所示;⑷ 属于图结构,
    其逻辑结构图如图 1-4(d) 所示。

    3、证明:对任一满二叉树,其分枝数 B=2(n0-1) 。(其中,n0 为终
    端结点数)
    【解答】因为在满二叉树中没有度为 1 的结点,所以有:
    n=n0+n2
    设 B为树中分枝数,则
    n=B+1
    所以
    B=n0 +n2-1
    再由二叉树性质:
    n0=n2+1
    代入上式有:
    B=n0+n0-1-1=2(n0-1)

    4、证明:已知一棵二叉树的前序序列和中序序列,则可唯一确定该
    二叉树。
    【解答】证明采用归纳法。
    设二叉树的前序遍历序列为 a1a2a3, an,中序遍历序列为 b1b2b3,
    bn。
    当 n=1 时,前序遍历序列为 a1,中序遍历序列为 b1,二叉树只有一
    个根结点,所以, a1= b1,可以唯一
    确定该二叉树;
    假设当 n<=k时,前序遍历序列 a1a2a3, ak 和中序遍历序列 b1b2b3,
    bk 可唯一确定该二叉树,下面证
    明当 n=k+1 时,前序遍历序列 a1a2a3, akak+1 和中序遍历序列
    b1b2b3, bk bk+1 可唯一确定一棵二叉树。
    在前序遍历序列中第一个访问的一定是根结点, 即二叉树的根结点是
    a1,在中序遍历序列中查找值为 a1的结点,
    假设为 bi ,则 a1=bi 且 b1b2, bi-1 是对根结点 a1 的左子树进行中序遍历的结果,前序遍历序列a2a3, ai 是对根结点 a1 的左子树进行前序遍历的结果,
    由归纳假设,前序遍历序列 a2a3, ai 和中序遍历序列 b1b2, bi-1 唯一确定了根结点的左子树, 同样可证前序遍历序列 ai+1ai+2 , ak+1 和中序遍历序列bi+1bi+2 , bk+1 唯一确定了根结点的右子树。

    5、已知一棵度为 m的树中有: n1 个度为 1 的结点,n2 个度为 2 的结
    点,, , nm个度为 m的结点,问该树中共有多少个叶子结点?
    【解答】设该树的总结点数为 n,则
    n=n0+n1+n2+,+nm
    又:
    n=分枝数+1=0×n0+1×n1+2×n2+, +m×nm+1
    由上述两式可得:
    n0= n2+2n3+,+(m -1)nm+1

    6、对给定的一组权值 W=(5,2,9,11,8,3,7),试构造相应
    的哈夫曼树,并计算它的带权路径长度。
    【解答】构造的哈夫曼树如图 5-13 所示。
    zzzz
    树的带权路径长度为:
    WPL=2 ×4+3×4+5×3+7×3+8×3+9×2+11×2
    =120

    7、已知某字符串 S中共有 8 种字符,各种字符分别出现 2 次、1 次、
    4 次、5 次、7 次、3 次、4 次和 9 次,对该字符串用 [0 ,1] 进行前缀编码,问该字符串的编码至少有多少位。
    【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码
    树如图 5-14 所示。其带权路径长度
    =2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98,所以,该字符 z

    8、已知散列函数 H(k)=k mod 12 ,键值序列为 (25, 37, 52, 43, 84,
    99, 120, 15, 26, 11, 70, 82) ,采用拉链法处理冲突,试构造开散列表,并计算查找成功的平均查找长度。
    【解答】 H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3,
    H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10
    构造的开散列表如下:
    平均查找长度 ASL=(8×1+4×2)/12=16/12

    9、已知关键码序列为( Jan, Feb, Mar, Apr, May, Jun, Jul, Aug,

    Sep, Oct, Nov, Dec ),散列表的地址空间
    为 0~16,设散列函数为 H(x)= ,其中 i 为关键码中第一个字母在字
    母表中的序号,采用线性探测
    法和链地址法处理冲突, 试分别构造散列表, 并求等概率情况下查找
    成功的平均查找长度。
    【 解 答 】 H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6,
    H(Apr)=1/2=0
    H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0
    H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2
    采用线性探测法处理冲突,得到的闭散列表如下:
    平均查找长度 =(1+1+1+1+2+4+5+2+3+5+6+1)/12=32/12
    采用链地址法处理冲突,得到的开散列表如下:
    平均查找长度 =(1×7+2×4+3×1)/12=18/12 Image

    10、试推导含有 12 个结点的平衡二叉树的最大深度, 并画出以棵这样

    的树。
    【解答】令 Fk 表示含有最少结点的深度为 k 的平衡二叉树的结点树
    目,则:
    F1=1,F2=2,, , Fn= Fn-2+Fn-1+1。含有 12 个结点的平衡二叉树
    的最大深度为 5,例如:

    11、如果只想得到一个序列中第 k 个最小元素之前的部分排序序列,

    最好采用什么排序方法?为什么?对于序列{57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7} ,得到其第 4 个最小元素之前的部分序列 {6,7,9,11} ,使用所选择的排序算法时,要执行多少次比较?
    【解答】采用堆排序最合适, 依题意可知只需取得第 k 个最小元素之
    前的排序序列时,堆排序的时间复杂
    度Ο(n+klog2n) ,若 k≤nlog2n ,则得到的时间复杂性是 Ο(n) 。
    对于上述序列得到其前 4 个最小元素, 使用堆排序实现时, 执行的比
    较次数如下:
    初始建堆:比较 20 次,得到 6;
    第一次调整:比较 5 次,得到 7;
    第二次调整:比较 4 次,得到 9;
    第三次调整:比较 5 次,得到 11。

    12、. 写出计算单链表 head(head 为单链表的表头)中数据域 data 值为 m的结点个数的算法。

    int count (Node *head)
    // 计算单链表 head 中数据域 data 值为 m的结点个数
    { Node *p=head->next;
    int n=0;
    while (p!=NULL)
    {if (p->data==m)
    n++;
    p=p->next;
    }
    return n;
    }// count

    13、 已知非空单链表 head,试设计一个算法,交换 p 所指结点与其后继结点在链表中的位置。

    解答:
    int revers(listnode *head, listnode p)
    /
    交换 p 所指结点与其后继结点在链表中的位置 */
    { if (p->next==NULL) return 0 ;
    listnode *q=head;
    while (q->next!=p) q=q->next;
    {r=p->next ;q->next=r;
    p->next =r->next ; r->next=p;
    return 1;
    }// revers

    14、 线性表用带头结点的单向链表示,试写出删除表中所有 data 域为零的元素的算法。

    解答:
    解: int DeleteItem(Node * head)
    { Node *p=head;
    // 声明指针 p,并令其指向链表头结点
    while (p->next!=NULL)
    {if(p->nex->data==0)
    p->next=p->next->next.
    else p=p->next; // 指针下移
    }
    }

    15、试设计一算法,计算带头结点的单链表 head(head 指向表头 ) 的结点个数。

    解答:
    int Length( )
    // 计算带表头结点的单链表 head 的长度
    {Node *p=head->next;
    int count=0;
    while (p!=NULL)
    {p=p->next; count ++;}
    return count;
    }

    16、试设计一算法,计算带头结点的单链表 head(head 指向表头 ) 的结点个数。

    解答:
    int Length( )
    // 计算带表头结点的单链表 head 的长度
    {Node *p=head->next;
    int count=0;
    while (p!=NULL)
    {p=p->next; count ++;}
    return count;
    }

    17、判断单链表 head(head 指向表头 ) 是否是递增的。

    解答:【编者注: 链表无头结点】
    int order(Node *head)
    {Node *p=head;
    while(p->next!=NULL)
    if(p->datanext->data)
    p=p->next;
    else
    break;
    if(p->next==NULL)
    return 1;
    else
    return 0;
    }

    18、设计一个算法,在一个单链表 head 中找出值最小的元素。

    解答:【编者注: 链表无头结点】

    int Min(Node * head )
    // 在单链表 head 中找出值最小的元素
    { Node *p=head;
    int min=p->data;
    while (p->next!=NULL)
    { if(p->next->data<min) min=p->next->data;
    p=p->next;
    }
    return min;
    }

    19、设有两个单链表 L 和 L1, 其结点结构为 (data,next), 试编写算法判断链表 L1 中的各元素是否都是单链表

    L 中的元素。
    解答:
    int SubLnk(Node *L, Node *L1)
    {Node *p1=L1;
    while(p1!=NULL)
    {Node *p=L;
    while((p!=NULL)&&(p1->data!=p->data))
    p=p->next;
    if (p==NULL) return 0; // 【编者注: L1 中元素未在 L 中】
    else p1=p1->next;
    }
    return 1;
    }

    20、设有一个正整数序列组成带头结点的单链表 head,试编写算法确定在序列中比正整数 x 大的数有几个。

    (8 分)
    解答:
    int count (Node * head ,int x )
    ∥在带头结点的单链表 head 中,确定序列中比正整数 x 大的数有几个
    {
    Node *p=head->next;
    int count=0;
    while (p!=NULL)
    { if (p->data>x) count ++;
    p=p->next;
    }
    return count;
    } ∥算法 count 结束

    21、对于一个队列,如果输入项序列由 1,2,3,4 所组成,试给出全部可能的输出序列。
    答: 1,2,3,4

    22、将算术表达式 a+b*(c+d/e )转为后缀表达式。
    答: B .abcde/+*+

    23、将表达式 ((a+b)-c*(d+e)-f)(g+h) 改写成后缀表达式。
    答:后缀表达式为: ab+cde+
    -f-gh+*

    24、将算术表达式 a*(b+c)-d 转为后缀表达式。
    答: abc+*d-

    25、 写出中缀表达式 A-(B+C/D)*E 的后缀形式。
    答:中缀表达式 A-(B+C/D)E 的后缀形式是: ABCD/+E-。

    26、 设一棵二叉树以二叉链表为存储结构,设计一个算法交换二叉树中每个结点的左子女和右子女。 (12 分)
    解答:
    void exchange(BinTreeNode * t)
    {if (t!=NULL)
    BinTreeNode * temp;
    if((t->lchild!=NULL)||(t->rchild!=NULL))
    {temp= t->lchild;
    t->lchild= t->rchild;
    t->rchild= temp;
    exchange(t->lchild);
    exchange(t->rchild);
    }
    }

    27、 设一棵二叉树以二叉链表为存储结构,试设计一个算法计算二叉树中叶子结点的个数。
    (12 分)
    解答: void countleaf(BinTreeNode * t,int &count)
    { if(t!=NULL)
    {if((t->lchild= =NULL)&&(t->rchild= =NULL))
    count++; (2 分)
    countleaf(t->lchild,count);
    countleaf(t->rchild ,count);
    }
    }

    28、设一棵二叉树以二叉链表为存储结构,试写一算法求该二叉树上度为 2 的结点个数。
    (12 分)
    解答:
    void count2(bitreptr t ,int count)
    {if (t!=NULL)
    {if ((t->lchild != NULL) && (t->rchild != NULL))
    count++;
    count2(t->lchild,count) ;
    count2(t->rchild,count) ;
    }
    }// count2

    29、 设一棵二叉树以二叉链表为存储结构,试写一算法求该二叉树中最大值(元) 。(12 分)
    解答:
    void maxnode(bitreptr t ,int max)
    {if(t!=NULL) (2 分)
    {if(t-> data>max) max=t->data; (4 分)
    max= maxnode(t->lchild,max) ;(2 分)
    max= maxnode(t->rchild,max) ;(2 分)
    }
    return max; (2 分)
    }// maxnode

    30、组记录的关键字为 (52, 56, 26, 12, 69, 85, 33, 48, 70) ,给出快速排序的过程。
    解答: 【编者: 本书对快速排序与其它书不一样】
    解: 52, 56, 26, 12, 69, 85, 33, 48, 70 错误
    第一趟排序 33, 48, 26, 12, 52, 85, 69, 56, 70
    第二趟排序 26, 12, 33, 48, 52, 69, 56, 70, 85
    第三趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85
    第四趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85
    第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85

    31、对半查找是否适合于以链接结构组织的表?
    答:对半查找不适合于以链接结构组织的表。 。
    30. 请指出中序遍历二叉查找树的结点可以得到什么样的结点序列。
    答:中序遍历二叉查找树的结点就可以得到从小到大排序的结点序列。

    32、已知待排记录的关键字序列为 {25, 96,11,63,57,78,44} ,请回答下列问题:
    (1)画出堆排序的初始堆(大根堆) ;
    (2)画出第二次重建堆之后的堆。
    在这里插入图片描述
    33、.要在[ 0…n-l]的向量空间中建立两个栈 stackl和stack2,请回答:
    (1)应该如何设计这两个栈才能充分利用整个向量空间?
    (2)若stackl的栈顶指针为 topl,stack2的栈顶指针为 top2,如果需要充分利用整个向量空间,则:
    栈stackl空的条件是: ___________;
    栈stack2空的条件是: ___________;
    栈stackl和栈 stack2满的条件是: ___________。
    在这里插入图片描述

    34、27.已知广义表如下:
    A=(B,y)
    B=(x ,L)
    L=(a,b)
    要求:
    第 12 页
    (1)写出下列操作的结果
    tail(A)=_.
    head(B)=

    (2)请画出广义表 A对应的图形表示。
    在这里插入图片描述

    35、已知二叉树如下:
    在这里插入图片描述
    请画出该二叉树对应的森林。
    在这里插入图片描述
    36、.请回答下列问题:
    (1)英文缩写 DAG 的中文含义是什么?
    (2)请给出下面 DAG 图的全部拓扑排序。
    在这里插入图片描述

    37、已知线性表 (a1,a2,a3…,an)按顺序存放在数组 a中,每个元素均为整数,下列程序的功能是将所有小于 0的元素移
    到全部大于等于 0的元素之前。例如,有 7个整数的原始序列为 (x,x,-x,-x,x,x,-x) ,变换后数组中保存的序列是
    (-x,-x,-x,x,x,x,x) 。请在程序处填入合适的内容,使其成为完整的算法。
    f30(int a[], int n)
    { int k,m,temp;
    m= (1) ;
    while (a[m]<0 &&m<n)
    m= (2) ;
    k=m;
    while (k<n)
    { while(a [k]>=0&&k<n)
    k= (3) ;
    if(k<n)
    { temp=a[k];
    a[k]=a[m];
    a[m]= (4) ;
    m= (5) ;
    }
    }
    }
    在这里插入图片描述
    (1)
    (2)
    (3)
    (4)
    (5)
    38、

    39、阅读下列程序,并回答问题:

    #include<stdio.h>
    substr(chart,chars,int pos,int len)
    { while (len>0&&*s )
    { t=(s+pos-l);
    第 14 页
    t++;s++;len–;
    }
    t=’\0’;
    }
    char f31(chars)
    { char t[100];
    if (strlen(s)=1)
    return s;
    substr(t,s,1,1);
    substr(s,s,2,strlen(s)-1);
    f31(s);
    return strcat(s,t);
    }
    main( )
    { char str[100]= ‘‘String’’;
    printf(’’%s\n’’,f31(str));
    }
    (1)请写出执行该程序后的输出结果;
    (2)简述函数 f31的功能。
    在这里插入图片描述
    40、下面程序实现插入排序算法。
    typedef struct{
    int key;
    Info otherinfo;
    }SeqList;
    void InsertSort(SeqList R[] ,int n)
    {/
    待排序列保存在 R[ 1…n]中 */
    SeqList x;
    int i,j,k,lo,hi,mi;
    for (i=2 ;i<=n ;i++)
    {
    (1) ;
    lo=1 ;
    第 15 页
    hi=i-l;
    while (lo<=hi)
    {
    mi=(lo+hi)/2;
    if ( (2) ) break;
    if (R[mi].key>x.key) hi=mi-l;
    else lo=mi+l;
    }
    if (mi=lo) k=i - mi;
    else k=i - mi-1;
    for (j=0 ;j<k ;j++)
    (3) ;
    R[i-j ]=x;
    }
    }
    在空白处填写适当的内容,使该程序功能完整。

    答 :
    在这里插入图片描述

    41、已知二叉树的定义如下:
    typedef struct node{
    int data;
    struct node *lchild, *rchild;
    }*Bitptr ;
    编写递归算法求二叉树的高度。函数原型为: int f34(Bitptr t);
    在这里插入图片描述
    42、29稀疏矩阵 A 如下,写出矩阵 A 的三元组表及矩阵 A 的转置矩阵的三元组表。
    答 :在这里插入图片描述
    在这里插入图片描述

    43、一棵二叉树的前根遍历序列为 ABCDEFG ,中根遍历序列为 CBDAEGF ,试构造出该二叉树。
    在这里插入图片描述

    44、31.下述矩阵表示一个无向连通网,试画出它所表示的连通网及该连通网的最小生成树。
    在这里插入图片描述
    答 :
    在这里插入图片描述

    45、32给定表( 80, 90,50,70,75,60,40,100),试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排
    序树,画出插入完成后的二叉排序树。
    答:
    在这里插入图片描述

    46、试写出一组键值( 46,58,15, 45,90,18,10,62)应用直接插入排序算法从小到大排序后各趟的结果。
    在这里插入图片描述

    47、试写出一组键值( 46,58,15, 45,90,18,10,62)应用直接插入排序算法从小到大排序后各趟的结果。
    在这里插入图片描述

    48、试分别写出二叉树的先根遍历和中根遍历的递归算法
    在这里插入图片描述

    49、试编写以单链表为存储结构实现直接选择排序的算法。
    在这里插入图片描述

    50、在栈的输入端元素的输入顺序为 1,2,3,4,5,6,进栈过程中可以退栈,则退栈时能否排成序列 3,2,5,6,
    4,1 和 1,5,4, 6,2,3,若能,写出进栈、退栈过程,若不能,简述理由。 (用 push(x)表示 x 进栈, pop(x)
    表示 x 退栈)
    在这里插入图片描述
    51、已知一棵二叉树的中根遍历序列为 CBEDFAGH ,后根遍历序列为 CEFDBHGA ,画出该二叉树。
    在这里插入图片描述

    52、给定表( 15,11,8,20, 14,13),试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树,画
    出插入完成后的二叉排序树,并判断该二叉排序树是否为平衡二叉排序树,若为非平衡二叉排序树,将它调整为
    平衡二叉排序树。
    在这里插入图片描述
    在这里插入图片描述

    53、如题 32 图所示无向图, (1)写出其邻接矩阵; (2)写出三种以顶点 A 为起点的深度优先搜索顶点序列。

    在这里插入图片描述

    在这里插入图片描述

    54、、用冒泡排序法对数据序列( 49, 38,65,97,76,134,27,49)进行排序,写出排序过程。并说明冒泡排序是否为稳定排序
    在这里插入图片描述
    55、编写计算二叉树中叶子结点数目的算法。
    在这里插入图片描述

    56、开散列表的类型定义如下:

    typedef struct tagnode
    {keytype key;
    struct tagnode*next;
    }*pointer,node;
    typedef pointer openhash[ n];
    试写出开散列表上的查找算法。
    在这里插入图片描述

    57、
    在这里插入图片描述

    在这里插入图片描述

    58、
    在这里插入图片描述
    答 :
    在这里插入图片描述

    59、
    在这里插入图片描述
    答:领接矩阵
    在这里插入图片描述

    60、
    在这里插入图片描述
    答 :
    在这里插入图片描述

    61、
    在这里插入图片描述
    答 :
    在这里插入图片描述

    62、在这里插入图片描述
    答 :
    在这里插入图片描述

    63、
    在这里插入图片描述
    答:在这里插入图片描述

    64、设某文件有 14个记录,其关键字分别为{25,75,125,93,241,203,19,198,121,173,218,80,214,329} 。桶的容量 M=3,此时采用除留余数法构造散列函数,且散列函数为 h(k)=k%5, 画出该散列文件的结构图,并说明如何对其进行删除
    或插入、检索等操作。
    答案:由于散列函数 h(k)=k%5, 从而可得按散列函数方法组织的文件结构如下 ( 可选桶数为
    (14/3 )×(1+10%)=5);
    当需对该散列文件中的记录进行检索时,可首先根据给定记录的关键字值,用散列函数求出其对应的散列地址,此地址即为桶的编号,然后按照散列表中第 i 项给出的地址把该桶中的所有记录读入内存,并对这些记录进行顺序检索。若找到说明检索成功,否则,若该桶不满或其指针域为空,说明检索失败。此时若其指针域不空,则该指针把第一个溢出桶的记录读入内存,继续检索
    直到检索成功或失败时为止。当要对散列文件中的记录进行删除操作时,同样可首先利用散列函数求出该记录所在的存储桶并
    把它读入内存,接着把该记录与最后一个记录对调,然后把该桶重新写回到外存储器的原来的位置。当从最后一个桶中删除最后一个记录时,可将此空桶释放回系统,以节省存储空间。当要对散列文件中的记录进行更新或修改时,可首先检索该记录所在的存储桶,并把该桶记录读入内存,接着检索该记录,并修改,然后把修改过的桶重新写回到原来的位置即可。

    65、写出二分查找的递归算法。
    答案: int binlist (datatype a [n];int s,t;datatype x)/*n 为元素个数, s,t 分别为查找区
    间的上、下界 /
    { if(S>t) return(0);/
    查找失败 /
    else { mid=(s+t)/2;
    switch(mid)of
    { x<a [mid]:return (binlist(a,s,mid-1,x));/
    在低端区间上递归 /
    x==a[mid]:return (mid);/
    查找成功 /
    x>a[mid]:return(binlist(a,mid+1,t,x));/
    在高端区间上递归 */
    }
    }
    }

    66、对于如下一个有序的关键字序列 {5,9,12,18,23,31,37,46,59,66,71,78,85}, 现在要求用二
    分法进行查找值为 18的关键字,则经过几次比较之后能查找成功 ?
    答案:根据二分查找的过程,我们可以得到如下的比较结果:
    第一次比较:[ 5,9,12,18,23,31,37,46,59,66,71,78,85,]

    第二次比较:[ 5,9,12,18,23,31],37,46,59,66,71,78,85

    第三次比较: 5,9,12[18,23,31],37,46,59,66,71,78,85

    第四次比较: 5,9,12[18]23,31,37,46,59,66,71,78,85

    则从上面的比较过程我们可以看出:经过四次比较之后,就可以查找到值为 18的关键字。

    67、在一棵二叉树中,度为 0的结点个数与度为 2的结点个数和度数之间有什么关系 ?在一棵完全二叉树中,如果共有 200个结点,则能判断出叶结点的个数吗 ?如果能,请指出会有多少个叶结点,多少个度为2的结点 ?多少个度为 1的结点?如果有 201个结点呢?

    答案:在一棵二叉树中,度数为 0的结点 ( 叶结点 )的个数总是比度为 2的结点的个数多 1。根据完
    全二叉树的定义:若一棵二叉树至多只有最下面的两层上结点的度数可以小于 2,并且最下一层上的结点都集中在该层最左边的若干位置上,
    则我们可以得出这样一个结论:在一棵完全二叉树上,或者没有度为 1的结点。则根据以上分析,我们可以这样计算此题:设度数为 2的结点有 n个,则必有 n+1个度为 0的结点,即度数为 2和度数为 0的结点数之和为 2n+1(是奇数 ) ,
    于是得出,如果一棵完全二叉树的结点总数为奇数,则此树中必然不存在度为 1的结点,若完全二叉树中结点总数为偶数,则必然有 1个度为 1的结点存在,于是若完全二叉树中有 200个结点,就必有 100个对结点,99个度数为 2的结点, 12个度数为 1的结点,如果二叉树中有 201个结点,则必有 101个叶结点, 100个度数为 2的结点,没有度数为 1的结点。

    68、以下运算实现在循环队上取队头,请在 ___处用适当的语句予以填充。
    int GetHead(CycqueueTp sq,DataType *x)
    { if(sq.rear==___return(0);
    else { *x=sq.data [___];
    return(1);
    }
    }
    答案: sq.front (sq.front+1)% maxsize

    69、以下运算实现在链栈上的初始化,请在 ___处用适当的语句予以填充。
    void InitStack (LStackTp *ls){;___}
    答案: ls=NULL

    70、以下算法在开散列表 HP中查找键值等于 K的结点,成功时返回指向该点的指针,不成功时返
    回空指针。请分析程序,并在 ___上填充合适的语句。
    pointer research-openhash(keytype K,openhash HP)
    { i=H(K);/* 计算K的散列地址 /
    p=HP[i ];/i 的同义词子表表头指针传给 p/
    while(___)p=p->next;/
    未达到表尾且未找到时,继续扫描 */
    ______;
    }
    答案: (p!=NULL)&&(p->key!=K) return§

    71、写出向某个有序文件中插入一个记录的程序。
    答案:所谓有序文件是指文件的记录按关键字由小到大 (或由大到小 )顺序存放。为方便起见,可
    设文件的每一个记录是一个整数,文件上数据是按由小到大顺序存放。设插入数据是命令行的第
    3个参数,且设为 d。若原文件中没有数据,则 d写入文件;若有数据,则找到第 1个比d大的数据
    i ,先写入 d,再将 i 和其后各数据写回文件中,可通过调用 fseek 函数来实现插入。相应程序为:
    #include <stdio.h>
    #include <stdlib.h>
    #include <io.h>
    #include <fcntl.h>
    #define LEN sizeof(int)
    void main(int argi,char * * argc)
    { int fp,i,d;
    if (argi<3)
    { printf( ″filename int n″)
    exit(0);
    }
    d=atoi (argc [2]);
    fp=open(argc [1],O_CREAT |O_RDWR |O_BINARY,s-IREAD |S_IWRITE);
    while(1)
    { if ( read(fp,&I,LEN) !=LEN)
    {write (fp,&d,LEN)😕* 文件结束, d添加到文件尾端 /
    break; }
    if (i>=d)/
    文件中读出数据 i ,若i>=d,则先存 d*/
    { do
    { fseek(fp,-1Llen,SEEK_CUR);/ 文件指针后退 1个记录 */
    write(fp,&d,LEN);/*d 写到文件中 /
    d=i;/
    原i 作d,以便处理其他数据 /
    }while (read(fp,&i,LEN)==LEN);
    write(fp,&d,LEN);/
    继续读数据,并判别文件是否结束 */
    break;
    }
    }
    close (fp);
    }/main/

    72、对题 26 图中所给的二叉排序树 T回答下列问题。
    (1) 给出能生成 r 的 2 种关键字插入序列;
    (2) 给出 r 的前序遍历序列。
    在这里插入图片描述

    在这里插入图片描述

    73、对题 27 图所示的无向带权图 G,回答下列问题。
    (1) 给出图 G的邻接矩阵;
    (2) 给出图 G的一棵最小生成树。
    在这里插入图片描述
    答 :

    在这里插入图片描述
    在这里插入图片描述

    74、现有 5 个权值分别是 20、31、 16、7 和 l5 的叶结点,用它们构造一棵哈夫曼树,画出该树。
    在这里插入图片描述

    75、对于给定的一组关键字序列 {26 ,l8 ,60,65,45,13,32} ,写出使用直接选择排序方法将其排成升序序列的过程。
    在这里插入图片描述

    76、设非空双向循环链表 L 的头指针为 head,表结点类型为 DLNode,定义如下。
    在这里插入图片描述

    初始时, L 中所有结点的 prior 域均为空 (NULL),next 域和 data 域中已经正确赋
    值。如题 30 图 a 所示
    在这里插入图片描述

    函数 f30 完成的功能是:将 L 中各结点的 prior 域正确赋值,使 L 成为双向循环链表。如题 30 图 b 所示。
    在这里插入图片描述

    将空白处应填写的内容答在答题卡上。
    在这里插入图片描述

    在这里插入图片描述

    77、已知二叉树的二叉链表类型定义如下,阅读程序,并回答问题。

    在这里插入图片描述

    若二叉树如下所示,写出调用 f31(T) 的输出结果
    在这里插入图片描述

    在这里插入图片描述

    78、阅读下列程序,写出 f32 的输出结果。
    在这里插入图片描述

    在这里插入图片描述

    79、阅读程序,回答下列问题。
    在这里插入图片描述

    在这里插入图片描述

    80、已知单链表类型定义如下:
    在这里插入图片描述
    单链表 L 中结点数不少于 2。设计算法判断 L 中存储的全部 n 个数据是否是斐波那契序列的前 n 项。如果是,则
    函数返回 1,否则返回 0。函数原型如下
    在这里插入图片描述

    在这里插入图片描述

    81、已知 n 阶对称矩阵 A的元素为 a i,j (0≤i ,j ≤n 一 1),采用“按行优先”将下三角部分
    的元素 ( 含主对角线 ) 保存在一维数组 sa 中,且约定元素 a 0,0 保存在 sa[0] 中,元素 a i,j ( ≤i ,
    j ≤n-1) 保存在 sa[k] 中,请给出由下标 i ,j 计算下标 k 的计算公式。
    在这里插入图片描述

    82、己知二又树 T 如题 27 图所示。
    在这里插入图片描述

    请问答下列问题:
    (1) 画出该二叉树对应的森林。
    (2) 写出对森林进行前序遍历的遍历序列 i
    答 :
    在这里插入图片描述

    83、题 28 图所示为一棵含 2 个关键字的 3 阶 B树 T。现将关键字序列 {40 ,60,70,20,10}依次插入到 T 中,画出每插入一个关键字后得到的树型。
    在这里插入图片描述

    答 :
    在这里插入图片描述

    84、给定无向带权连通图 G如题 29 图所示,从顶点 v 0 开始,使用普里姆 (Prim) 算法,求 G的最小生成树 T。请回答下列问题。在这里插入图片描述

    (1) 画出最小生成树 T。
    (2) 计算 T中各边权值之和。
    在这里插入图片描述

    85、请写出下列程序段的输出结果。
    在这里插入图片描述

    在这里插入图片描述

    答:
    在这里插入图片描述

    86、己知存储稀疏矩阵三元组表的类型定义如下:
    在这里插入图片描述
    在这里插入图片描述
    答:
    在这里插入图片描述

    87、已知二叉树的二叉链表类型定义如下:
    在这里插入图片描述

    答:
    在这里插入图片描述

    88、函数 f33 的参数 t 指向题 33 图所示的二叉排序树的根,阅读程序,回答下列问题。
    在这里插入图片描述

    1. 若连续 3 次调用函数 f33 ,参数 K的值依次取 10、25、10,写出每次调用后函数的输
      出结果;
      (2) 说明函数 f33 的功能。
      在这里插入图片描述

    89、已知顺序表 SeqList 定义如下:
    typedef struct{
    KeyType key ;
    InfoType otherinf0 ;
    }RecType :
    typedef RecType SeqList[MAXSIZE+1] ;
    编写函数,用冒泡排序法将 n个元素的待排序列 R按关键字降序排序。函数原型为:
    int f34(SeqList R ,int n)
    在这里插入图片描述

    90、
    在这里插入图片描述

    在这里插入图片描述

    91、
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    92、
    在这里插入图片描述
    在这里插入图片描述

    93、
    在这里插入图片描述

    在这里插入图片描述

    94、
    在这里插入图片描述

    答 :
    在这里插入图片描述
    95、
    在这里插入图片描述

    在这里插入图片描述

    答 :
    在这里插入图片描述

    96、
    在这里插入图片描述

    在这里插入图片描述
    答 :
    在这里插入图片描述

    97、
    在这里插入图片描述

    在这里插入图片描述

    98、在这里插入图片描述
    答 :
    在这里插入图片描述
    99、
    在这里插入图片描述
    100、
    在这里插入图片描述
    101、
    在这里插入图片描述
    102、
    在这里插入图片描述
    103、
    在这里插入图片描述

    104、
    在这里插入图片描述

    105、
    在这里插入图片描述
    106、
    在这里插入图片描述

    107、
    在这里插入图片描述

    108、
    在这里插入图片描述
    109、
    在这里插入图片描述

    110、
    在这里插入图片描述
    111、
    在这里插入图片描述
    112、
    在这里插入图片描述

    113、
    在这里插入图片描述
    114、
    在这里插入图片描述
    115、
    在这里插入图片描述
    116、
    在这里插入图片描述
    117、
    在这里插入图片描述

    118、
    在这里插入图片描述

    119、
    在这里插入图片描述
    在这里插入图片描述

    120、
    在这里插入图片描述
    121、
    在这里插入图片描述

    122、
    在这里插入图片描述
    123、
    在这里插入图片描述
    124、
    在这里插入图片描述
    125、
    在这里插入图片描述
    126、
    在这里插入图片描述
    127、
    在这里插入图片描述
    128、
    在这里插入图片描述
    129、
    在这里插入图片描述

    130、
    在这里插入图片描述

    131、
    在这里插入图片描述
    132、
    在这里插入图片描述

    133、
    在这里插入图片描述

    134、
    在这里插入图片描述
    135、
    在这里插入图片描述

    136、已知某二叉树如下图所示,试给出其二叉链表及顺序存储结构表示。
    在这里插入图片描述

    答 :
    在这里插入图片描述
    在这里插入图片描述

    137、在这里插入图片描述
    答 :
    在这里插入图片描述

    138、已知某二叉排序树 10 个结点的值依次为 1~10,其结构如图所示,试标出该二叉树各结点所对应的具体值。
    在这里插入图片描述

    答 :
    在这里插入图片描述

    139、已知一组键值序列( 28,47,35,42,53,60,34,22),试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。
    在这里插入图片描述

    140、.已知一组键值序列( 3,6, 8,9,2,7,4,3),试采用快速排序法对该组序列作升序排序,并给出每一趟的排序结果。
    在这里插入图片描述

    141、设某单链表中,存在多个结点其数据值均为 D,试编写一算法统计该类结点的个数。
    在这里插入图片描述

    142、35叉树存储结构采用二叉链表表示,试编写一算法,计算一棵二叉树的所有结点数。
    在这里插入图片描述

    143、假设二叉树的 RNL遍历算法定义如下:
    若二叉树非空,则依次执行如下操作:
    (1) 遍历右子树;
    (2) 访问根节点;
    (3) 遍历左子树。
    已知一棵二叉树如图所示,请给出其 RNL遍历的结果序列。

    答 :
    该树的 RNL遍历结果序列为: GCFABD

    144、已知一个无向图 G=(V,E),其中 V={A,B,C,D,E,F},邻接矩阵表示如下所示。
    请回答下列问题:
    (1) 请画出对应的图 G。
    (2) 画出图 G的邻接表存储结构。

    答:
    在这里插入图片描述

    145、已知一组待排记录的关键字序列为 (16, 12,18,60,15,36,14,18,25,85) ,用堆排序方法建小根堆,请给出初始建堆后的序列。


    初始堆序列是 (12 ,15,14,18,16,36,18,60,25,85)

    146、已知一棵二叉排序树如图所示。

    请回答下列问题:
    (1) 画出插入元素 23 后的树结构;
    (2) 请画出在原图中删除元素 57 后的树结构
    在这里插入图片描述
    答:
    在这里插入图片描述

    147、二叉树的存储结构类型定义如下

    typedef struct node{
    int data;
    struct node
    *
    lchild ,

    • rchild ;
      } BinNode ;
      typedef BinNode

    BinTree;
    编写递归算法,求只有一个孩子结点的结点总数,并计算这些结点的数据值的和。
    函数的原型为: void f34(BinTree T, int

    • count,
      int

    sum)
    *
    count 和

    • sum 的初值为
      0。
      答 :
      在这里插入图片描述

    148、30.已知下列程序, Ls 指向带头结点的单链表。

    Typedefstruct node {
    DataType data;
    struct node * next;
    } * LinkList;
    void f30( LinkList Ls )
    { LinkList p, q;
    q = Ls->next;
    if ( q && q->next ) {
    Ls->next = q->next;
    p=q
    while ( p->next )
    p = p->next;
    p->next = q;
    q->next = NULL;
    }
    }
    请回答下列问题:
    (1) 当 Ls 指向的链表如下图所示,请画出执行本函数之后的链表的结果。
    在这里插入图片描述

    (2) 请简述算法的功能
    答 :
    在这里插入图片描述
    (2) 将单链表的首结点(第一个结点)移到链尾(作为最后一个结点) 。
    或将链头元素移到链尾。

    149、已知字符串处理函数 f31 程序如下。

    int f31(charstrl , charstr2)
    { while(*strl==*str2&&(*strl!= ’\0’)){
    strl++ ;
    str2++ ;
    }
    return(*strl-*str2 ? l ∶0);
    }
    请回答下列问题:
    (1) 若调用语句是 f31( ”abcde”,” abcdf ’) ,则函数的返回值是什么 ?若调用语句是
    f31( ”abcde”,” abcde”) ,则函数的返回值是什么 ?
    (2) 简述该函数的功能。

    31. (1)1 , 0 (2 分)
    (2) 判断两个字符串是否相等。若串相等,则返回 O,否则返回 1。

    32.数组 A[] 中存储有 n 个整数,请阅读下列程序。

    void f32(intA[] ,int n)
    { inti ,j , k,x;
    k=n-l ;
    while(k>0){
    i=k ; k=0 ;
    for(j=O ;j<i ;j++)
    if(A[j]>A[j+1]){
    x=A[j] ;
    A[j]=A[j+l] ;
    A[j+1]=x ;
    k=j ;
    } // end of if
    } // end of while
    return ;
    }
    请回答下列问题:
    (1) 当 A[]={10 ,8, 2,4,6,7} 时,执行 f32(A ,6)后,数组 A中存储的结果是什么 ?
    (2) 说明该算法的功能。

    答32.(1)A[]={2,4,6,7,8,10) (3 分)
    (2) 该算法实现了对数组 A进行冒泡排序。

    150、下面程序实现二分查找算法。
    Typedef struct{
    KeyType key ;
    InfoType otherinfo ;
    }SeqList[N+1] ;
    int BinSearch(SeqList R, int n ,KeyType K)
    { int low=1 ,high=n ;
    while( (1) ){
    mid=(1ow+high) /2;
    if( (2) )
    return mid ;
    if(R[mid] .key>K)
    high=mid-1 ;
    else
    (3) ;
    }
    return O ;
    } // BinSearch
    请在空白处填写适当内容,使该程序功能完整。
    (1)
    (2)
    (3)

    答:
    33. (1) low<=high (2 分)
    (2) R[mid].key==K (2 分)
    (3) low=mid+l

    151、已知二叉树采用二叉链表存储,其结点结构定义如下:
    typedef struct Node{
    ElmType data ;
    struct Node *lchild ,*rchild ;
    }*BiTree ;
    请编写递归函数 SumNodes(BiTree T) ,返回二叉树 T 的结点总数。

    参考答案
    int SumNodes( BiTree T)
    { inti ,j ;
    if( !T) retumO ; (空树处理, 2 分)
    i=SumNodes( T->lchild) ; (左右子树递归, 6 分)
    j=SumNodes( T->rchild);
    retum (i+j+1) ; (返回结果计算, 2 分)
    } //endofSumNodes(…)

    152、顺序表类型定义如下:

    typedef int SeqList[100] ;
    阅读下列算法,并回答问题:
    void f33(SeqList r, int n)
    { int a, b,i;
    if (r[0]<r[1])
    { a=r[0] ;b=r[1] ; >
    else { a=r[1] ; b=r[0] ; }
    for (i=2 ;i<n ;i++)
    if (r[i]<a) a=r[i];
    else if (r[i]>b) b=r[i] ;
    printf( " a=%d,b=%d。 n", a, b);
    }
    (1)给出该算法的功能;
    (2)给出该算法的时间复杂度。

    在这里插入图片描述

    153、阅读下列算法,并回答问题:

    void f32(int r[] , int n)
    {
    Int i, j;
    for (i=2 ;i<n;i++)
    { r[0]=r[i] ;
    j=i-l ;
    while (r[0]<r[j])
    { r[j+l]=r[j] ;
    j=j-1 ;
    }
    r[j+l]=r[0] ;
    }
    }
    (1)这是哪一种插入排序算法 ?该算法是否稳定 ?
    (2)设置 r[0] 的作用是什么 ?
    在这里插入图片描述

    154、有向图的邻接矩阵类型定义如下:
    #define MVN 100 ∥ 最大顶点数
    typedef int EType; ∥ 边上权值类型
    typedef struct{
    EType edges[MVN][MVN]; ∥ 邻接矩阵,即边表
    int n; ∥ 图的顶点数
    } MGraph; ∥ 图类型
    例如,一个有向图的邻接矩阵如下所示:
    在这里插入图片描述

    阅读下列算法,并回答问题:
    Void f31(MGraph G)
    {
    Int i,j,k=0;
    Step1:
    for (i=0; i<G.n; i++)
    for (j=0; j<G.n; j++)
    if (G.edges[i][j]= =1) k++;
    printf( “ %d n” ,k);
    step2:
    for (j=0; j<G.n; j++)
    { k=0;
    for (i=0; i<G.n; j++)
    if (G.edges[i][j]= =1) k++;
    printf ( “ %d n” ,k);
    }
    }
    (1)stepl 到 step2之间的二重循环语句的功能是什么 ?
    (2)step2 之后的二重循环语句的功能是什么 ?
    在这里插入图片描述

    155、顺序表类型定义如下:

    define ListSize 100

    typedef struct {
    int data[ListSize] ;
    int length;
    }SeqList ;
    阅读下列算法,并回答问题:
    void f30(SeqList *L)
    { int i,j;
    i=0;
    while(ilength)
    if (L->data[i] %2!=0)
    { for(j=i+1; jlength; j++ }
    L->data[j-1]=L->data[j];
    L->length–;
    }
    else i++
    }
    (1)若 L->data 中的数据为( 22,4,63,0,15,29,34,42,3),则执行上述算法后 L->data 中的数据以及 L->length 的值各是
    什么?
    (2)该算法的功能是什么?

    在这里插入图片描述

    156、一组记录关键字 (55,76,44,32,64,82,20,16,43) ,用散列函数 H(key)=key %11 将记录

    散列到散列表 HT[0…12] 中去,用线性探测法解决冲突。
    (1)画出存入所有记录后的散列表。
    (2)求在等概率情况下,查找成功的平均查找长度。
    在这里插入图片描述

    157、用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序,问:
    (1)一共需要几趟归并可完成排序。
    (2)写出第一趟归并后数据的排列次序。
    在这里插入图片描述

    158、已知一个无向图如题 27 图所示,以①为起点,用普里姆 (Prim)算法求其最小生成树,画出最小生成树的构
    造过程。
    在这里插入图片描述
    答:

    在这里插入图片描述

    159、假设 Q 是一个具有 11 个元素存储空间的循环队列 (队尾指针指向队尾元素的下一

    个位置,队头指针指向队头元素 ),初始状态 Q.front=Q.rear=0 ;写出依次执行
    下列操作后头、尾指针的当前值。
    a,b,c,d,e,f 入队, a,b,c,d出队; (1) Q.front=______ ;Q.rear=______。
    g,h,i,j,k,l 入队, e,f,g,h 出队; (2) Q.front=______ ;Q.rear=______。
    M,n,o,P 入队, i,j,k,l,m 出队; (3) Q.front=______ ;Q.rear=______。
    在这里插入图片描述

    160、

    161、

    162、

    163、

    164、

    165、

    166、

    167、

    168、

    展开全文
  • 给定三个整数a,b,Ka,b,Ka,b,K,求使得na⌈log2n⌉b&amp;lt;=Kna⌈log2n⌉b&amp;lt;=Kn^a {\lceil log_2n\rceil}^b nnn的最大值。 思路: 因为函数单调,显然可以直接二分nnn去验证。 此题有两个需要...
  • 二分法的时间复杂度计算

    千次阅读 2019-05-09 17:26:34
    先说下定义O(log2n)与O(n)的区别 O(log2n)含义说明: 比如123456789,你要找2,首先查中间元素5,大于2,所以直接排除掉5右边的6789,然后在1234里继续二分查找。每次排除1/2的元素,所以是O(log2n)。 O(n)含义...
  • 算法时间复杂度计算

    千次阅读 2016-05-16 11:41:11
    引言 常用的算法的时间复杂度和空间复杂度 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 ...O(n*log2n) ...O(log2n)~O
  • 找到条件规模[while(i<=n)],这里规模就是 i<...得出结论,立即推 时间复杂度为log2N 注意事项,有时候变量不是单一简单的改变,可能会随着另外一个变量的改变而改变,需要细心对待! ...
  • 算法时间复杂度,空间复杂度计算log2n,常数阶,线性阶,对数阶(count*2),平方阶,指数阶 算法设计要求:正确性,可读性,高效率,低存储量,健壮性。事前估算方法, 线性表,前驱,后继,有限集合--顺序...
  • 时间复杂度的计算

    2020-08-23 22:24:36
    执行次数函数举例 阶 非正式术语 12 O(1) 常数阶 2n+3 O(n) 线性阶 3n2+2n+1 O(n2) 平方阶 5log2n+20 O(logn) 对数阶 2n+3nlog2n+19 O(nlogn) nlogn阶 6n3+2n2+3n+4 O(n3) 立方阶 2n O(2n) 指数阶
  • 第几次查询 剩余查询数 1 N/2 2 N/22 3 N/23 ... ... k N/2k 在第k次已经找到 N/2k = 1 k = log2N 则复杂度为O(log2N) 转载于:https://www.cnblogs.com/19990219073x...
  • 一下列叙述中正确的是 对长度为的有序链表进行查找最坏情况下需要的比较次数为 对长度为的有序链表进行对分查找最坏情况下需要的比较次数为n/2 对长度为的有序链表进行对分查找最坏情况下需要的比较次数为log2n 对...
  • 【*】【https://blog.csdn.net/user11223344abc/article/details/81485842】【时间复杂度O(logN),比如二分法就是时间复杂度O(log2N) 递归也是O(log2N)】 ...
  • 一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。...常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(n log2n),平方阶O(n2),立方阶O(n3)k次方...
  • 计算机组成原理中总线判优方法中计数器查询方式,大致用log2N根线是怎么算出来的
  • O(log2N)O(log^2N)O(log2N) O(logN)O(logN)O(logN) 40ms (54.68%) Ans 2 (Python) Ans 3 (Python) 解法一: class Solution: def countNumbersWithUniqueDigits(self, n: int) -> int
  • O(log2N)O(log^2N)O(log2N) O(N)O(N)O(N) 44ms (70.52%) Ans 2 (Python) Ans 3 (Python) LeetCode的Python执行用时随缘,只要时间复杂度没有明显差异,执行用时一般都在同一个量级,仅作参考意义。 ...
  • 二叉树计算公式

    2020-11-25 19:21:36
    n个节点的二叉树一共有((2n)!)/(n! * (n+1)!)种 n层二叉树的第n层最多为2^(n-1)个 二叉树节点计算公式 N = n0+n1+n2,度为0的叶子...具有n 个结点的平衡二叉树的深度为[log2n]+1 树的高度:从根节点到所有叶节点中最大.
  • 乘法复数运算=N/2 * log2N 加法复数运算=N* log2N 实数运算次数分析 对于一次复数乘法运算来说: 一次复数乘法运算次数=4次实数乘法+2次实数加法 一次复数加法运算次数=2次实数加法运算 所以: DFT 实数运算次...
  • 一个算法的复杂度通常由其时间复杂度和空间复杂度来表达。... log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!计算方法: 根本上有二:计算一个语句的频度(执行次数...
  • 题目:原题链接(中等) 标签:树、二叉树、二分查找 ...O(log2N)O(log^2N)O(log2N) O(1)O(1)O(1) 84ms (97.23%) Ans 3 (Python) 解法一(暴力解法): class Solution: def countNodes(self, roo
  • 1、完全二叉树与满二叉树的区别: ...在完全二叉树中,具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。 计算完全二叉树深度公式-推导证明: 假设两种极端情况 <1>该树为满二叉树时...
  • 计算算法复杂度

    2017-08-23 15:47:03
    算法的复杂度分为时间复杂度和空间复杂度 1.时间复杂度 在计算算法复杂度时一般只用到大O符号,Landau符号体系中的小o符号、...常见的算法时间复杂度由小到大依次为:Ο(1)Ο(log2n)Ο(n)Ο(nlog2n)Ο(n2)Ο(n3)…
  • 计算机网络相关计算

    千次阅读 2012-10-04 12:39:31
    1。带宽为4KHZ,如果有8种不同的物理状态表示数据,...① C=2 F log2N=2*4K*log28=24Kbps ② 分贝(dB)的计算是:10lgS/N 即 本题为:10lgS/N=30 则:S/N=103 C=F log2(1+S/N)= 4K*log21001=40Kbps 2。对于带宽为6
  • 简单计算时间复杂度

    2020-11-12 16:48:03
    一、简介 二、时间复杂度:O(1) 三、时间复杂度:O(n)(线性阶) 四、时间复杂度:O(n^2)(平方阶) 五、时间复杂度:O(log2n)(对数阶) 六、总结
  • PAGE PAGE 1 [模拟] 计算机二级(JAVA)笔试10 一选择题(每...冒泡排序需要的比较次数为 A.log2n B.n2 C.O(n1.5) D.n(n-1)/2 参考答案D 您的答案 答案解析 假设线性表的长度为n则在最坏情况下冒泡排序要经过n/2遍的从前往
  • 二分计算x的n次方

    2014-03-17 12:26:00
    要求时间控制在log2n内。 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication3 { class Program { static void Ma...
  • 如何计算时间复杂度

    千次阅读 2016-10-09 19:05:33
    一. 概念时间复杂度描述的是程序的执行时间,时间... > 2^n (指数阶) > n^3 (立方阶)> n^2 (平方阶)> nlog2n (线性对数阶) > n (线性阶) > log2n (对数阶) > 1 (常数阶)二. 计算方法找到循环里的最基本的操作,把每个最

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 303
精华内容 121
关键字:

计算log2n