算法设计与分析复习题目及答案详解


    分治法
    1二分搜索算法利( 分治策略)实现算法
    9 实现循环赛日程表利算法(分治策略 )
    27Strassen矩阵法利(分治策略 )实现算法
    34.实现合排序利算法(分治策略 )
    实现整数法利算法( 分治策略 )
    17.实现棋盘覆盖算法利算法(分治法 )
    29分治法求解需满足条件(子问题必须样 )
    分治法求解(01背包问题 )

    动态规划
    列动态规划算法基步骤( 构造优解 )
    列动态规划算法基素(子问题重叠性质 )
    列算法中通常底方式求解优解(动态规划法 )
    备忘录方法种算法变形( 动态规划法 )
    长公子序列算法利算法( 动态规划法 )
    矩阵连问题算法(动态规划算法B)设计实现
    实现子段利算法(  动态规划法   )

    贪心算法
    解决问题:单源短路径问题花费生成树问题背包问题活动安排问题
    解决问题:N皇问题01背包问题
    贪心算法基素(贪心选择性质优子结构性质)

    回溯法
    回溯法解旅行售货员问题时解空间树( 排列树 )
    剪枝函数回溯法中避免效搜索采取策略
    回溯法效率赖列素( 确定解空间时间)

    分支限界法
    效益优先( 分支界限法 )搜索方式
    分支限界法解团问题时活结点表组织形式( 堆 )
    分支限界法解旅行售货员问题时活结点表组织形式( 堆 )
    优先队列式分支限界法选取扩展结点原( 结点优先级 )
    问题解空间树进行搜索方法中活结点次机会成活结点( 分支限界法 )
    活结点表中选择扩展结点方式导致分支限界法( 栈式分支限界法 )外常见方式
    (1)队列式(FIFO)分支限界法:队列先进先出(FIFO)原选取节点扩展节点
    (2)优先队列式分支限界法:优先队列中规定优先级选取优先级高节点成前扩展节点

    (优子结构性质)贪心算法动态规划算法点
    贪心算法动态规划算法区( 贪心选择性质   )
    回溯算法分支限界法问题解空间树会( 序树 )



    14.哈弗曼编码贪心算法需计算时间(   B     )
    AO(n2n) BO(nlogn) CO(2n) DO(n)
    21面关NP问题说法正确(B )
    A NP问题解决问题
    B P类问题包含NP类问题中
    C NP完全问题P类问题子集
    D NP类问题包含P类问题中
    40背包问题贪心算法需计算时间(  B      )
    AO(n2n)     BO(nlogn)    CO(2n)      DO(n)
    42.01背包问题回溯算法需计算时间(  A      )
    AO(n2n) BO(nlogn) CO(2n) DO(n)

    47背包问题贪心算法需计算时间(   B     )
    AO(n2n) BO(nlogn) CO(2n) DO(n)
    53.采贪心算法优装载问题计算量集装箱重量排序算法时间复杂度 ( B )
    AO(n2n) BO(nlogn) CO(2n) DO(n)
    56算法干条指令组成穷序列满足性质( D )
    (1) 输入:0输入
    (2) 输出:少输出
    (3) 确定性:指令清晰歧义
    (4) 限性:指令执行次数限执行时间限
    A (1)(2)(3) B(1)(2)(4) C(1)(3)(4) D (1) (2)(3)(4)
    57函数32n+10nlogn渐进表达式( B )
    A 2n B 32n C nlogn D 10nlogn
    59动态规划算法解决字段问题时间复杂性( B )
    Alogn Bn Cn2 Dnlogn
    61设f(N)g(N)定义正数集正函数果存正常数C然数N0N≥N0时f(N)≤Cg(N)称函数f(N)N充分时界g(N)记作
    f(N)∈○(g(N))f(N)阶( A )g(N)阶
    A高 B低C等价 D逼

    二 填空题
    2程序 算法  某种程序设计语言具体实现
    3算法确定性指组成算法条 指令 清晰歧义
    6算法指解决问题 种方法 程
    7分治法般设计模式出设计出程序般 递算法
    11计算算法时间复杂度通常计算 循环次数 基操作频率 计算步
    14解决01背包问题动态规划回溯法分支限界法中需排序 动态规划 需排序 回溯法 分支限界法
    15回溯法进行状态空间树裁剪分支时般两标准:约束条件目标函数界N皇问题01背包问题正两种类型中时约束条件目标函数界进行裁剪 01背包问题 约束条件进行裁剪 N皇问题
    30回溯法种带 系统性 带 跳跃性 搜索算法
    33.回溯法搜索解空间树时常两种剪枝函数 约束函数 限界函数
    34计算机求解问题需时间 规模 关
    35快速排序算法性取决 划分称性
    36 Prim算法利 贪心 策略求解 生成树 问题时间复杂度 O(n2)
    37 图m着色问题 回溯 法求解解空间树中叶子结点数 mn 解空间树中结点孩子数 m


    4序列X{BCADBCD}Y{ACBABDCD}请出序列XY长公子序列 {BABCD}{CABCD}{CADCD}
    5回溯法解问题时应明确定义问题解空间问题解空间少应包含(优)解
    801背包问题回溯算法需计算时间__o(n*2n)__动态规划算法需计算时间___o(min{nc2n}_
    二综合题(50分)
    1写出设计动态规划算法步骤
    ①问题具优子结构性质②构造优值递关系表达式3优值算法描述④构造优解
    2 流水作业调度问题johnson算法思想
    ①令N1{i|aibi}②N1中作业ai非减序排序N1’N2中作业bi非增序排序N2’③N1’中作业接N2’中作业构成满足Johnson法优调度
    3 n4机器M1M2加工作业i需时间分aibi(a1a2a3a4)(451210)(b1b2b3b4)(82159)求4作业优调度方案计算优值
    步骤:N1{13}N2{24}
    N1’{13} N2’{42}
    优值:38
    4 回溯法解01背包问题:n3C9V{6103}W{344}解空间长度301量组成求棵完全二叉树表示解空间(根出发左1右0)画出解空间树计算优值优解
    解空间{(000)(010)(001)(100)(011)(101)
    (110)(111)}
    解空间树:
    A
    B
    C
    F
    E
    D
    G
    K
    J
    I
    H
    O
    N
    M
    L
    1
    1
    1
    0
    0
    0
    0
    1
    0
    1
    1
    0
    1
    0

    该问题优值:16 优解:(110)
    5 设S{X1X2···Xn}严格递增序集利二叉树结点存储S中元素表示S二叉搜索树中搜索元素X返回结果两种情形(1)二叉搜索树结点中找XXi概率bi(2)二叉搜索树叶结点中确定X∈(XiXi+1)概率ai表示S二叉搜索树T中设存储元素Xi结点深度Ci叶结点(XiXi+1)结点深度di二叉搜索树T均路长p少?假设二叉搜索树T[i][j]{XiXi+1···Xj}优值m[i][j]W[i][j] ai1+bi+···+bj+ajm[i][j](1二叉树T均路长P+
    m[i][j]W[i][j]+min{m[i][k]+m[k+1][j]} (1m[i][j]0 (i>j)
    6 描述01背包问题
    已知背包容量Cn件物品物品i重量Wi价值Vi求应选择装入背包中物品装入背包中物品总价值
    三简答题(30分)
    1流水作业调度中已知n作业机器M1M2加工作业i需时间分aibi请写出流水作业调度问题johnson法中aibi排序算法(函数名写sort(sn))
    2优二叉搜索树问题动态规划算法(设函数名binarysearchtree))
    1
    void sort(flowjope s[]int n)
    {
    int ikjl
    for(i1i {
    ki
    while(k if(k>n) break没ai跳出
    else
    {for(jk+1j if(s[j]tag0)
    if(s[k]a>s[j]a) kj
    swap(s[i]indexs[k]index)
    swap(s[i]tags[k]tag) }
    }
    li记前第bi标
    for(ili {
    ki
    for(jk+1j if(s[k]b swap(s[i]indexs[k]index) 移动indextag
    swap(s[i]tags[k]tag) }
    }
    2
    void binarysearchtree(int a[]int b[]int nint **mint **sint **w)
    {
    int ijktl
    for(i1i { w[i][i1]a[i1]
    m[i][i1]0}
    for(l0lfor(i1i { ji+l
    w[i][j]w[i][j1]+a[j]+b[j]
    m[i][j]m[i][i1]+m[i+1][j]+w[i][j]
    s[i][j]i
    for(ki+1k { tm[i][k1]+m[k+1][j]+w[i][j]
    if(t{ m[i][j]t
    s[i][j]k
    }
    }
    }
    }
    填空题(题15分题1分)
    1 算法组穷 规 规定解决某特定类型问题 系列运算
    2 进行问题计算复杂性分析前首先必须建立求解问题计算模型3基计算模型 机存取机RAM 机存取存储程序机RASP 图灵机
    3 算法复杂性 算法效率 度量评价算法优劣重
    4 计算机资源重 时间 空间 资源
    5 f(n) 6×2n+n2f(n)渐进性态f(n) O(  2^n   )
    6 贪心算法总做出前 选择说贪心算法整体优考虑做出选择某种意义局部优结构
    二简答题(题25分题5分)
    1 简单描述分治法基思想
    2 简述动态规划方法运优化原理
    3 谓优子结构性质?
    4 简单描述回溯法基思想
    5 谓PNPNPC问题
    三算法填空(题20分题5分)
    1n问题回溯算法
    (1)二维数组A[N][N]存储皇位置第i行第j列放皇A[i][j]非0值否值0
    (2)分维数组M[N]L[2*N1]R[2*N1]表示竖列左斜线右斜线否放棋子值1否值0
    for(j0j if( 1 ) *安全检查*
    { A[i][j]i+1 *放皇*
    2
    if(iN1) 输出结果
    else 3 *试探行*
    4 *皇*
    5
    }
    2数塔问题形图示数塔顶部出发结点选择左走右走起走底层求找出条路径路径值
    for(rn2r>0r) 底递计算
    for(c0 1 c++)
    if( t[r+1][c]>t[r+1][c+1]) 2
    else 3
    3Hanoi算法
    Hanoi(nabc)
    if (n1) 1
    else
    { 2
    3
    Hanoi(n1b a c)
    }
    4Dijkstra算法求单源短路径
    d[u]su距离 p[u]记录前节点信息
    Initsinglesource(Gs)
    for each vertex v∈V[G]
    do { d[v]∞ 1 }
    d[s]0
    Relax(uvw)
    if d[v]>d[u]+w(uv)
    then { d[v]d[u]+w[uv]
    2
    }
    dijkstra(Gws)
    1 Initsinglesource(Gs)
    2 SΦ
    3 QV[G]
    4while Q<> Φ
    do umin(Q)
    SS∪{u}
    for each vertex 3
    do 4
    四算法理解题(题10分)
    根优先队列式分支限界法求图中v1点v9点单源短路径请画出求优解解空间树求中间舍弃结点×标记获中间解结点单圆圈○框起优解双圆圈◎框起
    五算法理解题(题5分)
    设n2k运动员进行循环赛现设计满足求赛日程表:
    ①选手必须n1名选手赛次
    ②选手天赛次
    ③循环赛短时间完成
    (1)果n2k循环赛少需进行天
    (2)n238时请画出循环赛日程表
    六算法设计题(题15分)
    分贪心算法动态规划法回溯法设计01背包问题求:说明算法策略写出算法实现步骤分析算法时间
    七算法设计题(题10分)
    通键盘输入高精度正整数n(n效位数≤240)掉中意s数字剩数字原左右次序组成新正整数编程定n s寻找种方案剩数字组成新数
    样例输入
    178543
    S4
    样例输出
    13
    二简答题(题25分题5分)
    6 分治法基思想规模n问题分解k规模较子问题子问题互相独立原问题相k子问题分求解果子问题规模然够划分k子问题递进行直问题规模足够容易求出解止求出规模问题解合更规模问题解底逐步求出原问题解
    7 优化原理数学化语言描述:假设解决某优化问题需次作出n决策D1D2…Dn决策序列优整数k1 < k < n前面k决策样优决策取决前面决策确定前状态决策Dk+1Dk+2…Dn优
    8 某问题优解包含着子问题优解种性质称优子结构性质
    9 回溯法基思想棵含问题全部解状态空间树进行深度优先搜索解叶子结点搜索程中达结点时判断该结点根子树否含问题解果确定该子树中含问题解放弃该子树搜索退回层父结点继续步深度优先搜索程回溯法中先构造出整棵状态空间树进行搜索搜索程逐步构造出状态空间树边搜索边构造
    10 P(Polynomial问题):项式复杂程度问题
    NPNondeterministic Polynomial问题项式复杂程度非确定性问题
    NPC(NP Complete)问题种问题解域里面穷举出答案样问题NP里面难问题种问题NPC问题
    三算法填空(题20分题5分)
    1n问题回溯算法
    (1) M[j]&&L[i+j]&&R[ij+N]
    (2) M[j]L[i+j]R[ij+N]1
    (3) try(i+1MLRA)
    (4) A[i][j]0
    (5) M[j]L[i+j]R[ij+N]0
    2数塔问题
    (1)c(2)t[r][c]+t[r+1][c]
    (3)t[r][c]+t[r+1][c+1]
    3Hanoi算法
    (1)move(ac)
    (2)Hanoi(n1 a c b)
    (3)Move(ac)
    4(1)p[v]NIL
    (2)p[v]u
    (3) v∈adj[u]
    (4)Relax(uvw)
    四算法理解题(题10分)










    1 2 3 4 5 6 7 8
    2 1 4 3 6 5 8 7
    3 4 1 2 7 8 5 6
    4 3 2 1 8 7 6 5
    5 6 7 8 1 2 3 4
    6 5 8 7 2 1 4 3
    7 8 5 6 3 4 1 2
    8 7 6 5 4 3 2 1





    五(1)8天(2分)
    (2)n238时循环赛日程表(3分)
    六算法设计题(题15分)
    (1)贪心算法 O(nlog(n))
    Ø 首先计算种物品单位重量价值ViWi然贪心选择策略单位重量价值高物品装入背包种物品全部装入背包背包物品总重量未超C选择单位重量价值次高物品装入背包策略直进行直背包装满止
    Ø 具体算法描述:
    void Knapsack(int nfloat Mfloat v[]float w[]float x[])
    {Sort(nvw)
    int i
    for (i1ifloat cM
    for (i1i{if (w[i]>c) break
    x[i]1
    cw[i]
    }
    if (i}
    (2)动态规划法 O(nc)
    m(ij)背包容量j选择物品ii+1…n时01背包问题优值01背包问题优子结构性质建立计算m(ij)递式

    void KnapSack(int v[]int w[]int cint nint m[][11])
    {int jMaxmin(w[n]1c)
    for (j0jm[n][j]0
    for (jw[n]jw[n]*
    m[n][j]v[n]
    for (in1i>1i)
    { int jMaxmin(w[i]1c)
    for (j0j m[i][j]m[i+1][j]
    for (jw[i]jw[n]*
    m[i][j]max(m[i+1][j]m[i+1][jw[i]]+v[i])
    }
    m[1][c]m[2][c]
    if(c>w[1])
    m[1][c]max(m[1][c]m[2][cw[1]]+v[1])
    }

    (3)回溯法 O(2n)
    cw前重量 cp前价值 bestp:前优值
    void backtrack(int i)
    回溯法  i初值1
    {    if(i > n) 达叶结点
    { bestp  cp              return            }   
         if(cw + w[i] < c) 搜索左子树   
             { cw + w[i]
      cp + p[i]              
    backtrack(i+1)   
               cw  w[i]
                cp  p[i]   
            }   
           if(Bound(i+1)>bestp)
    搜索右子树   
            backtrack(i+1)   
     }   

    七算法设计题(题10分)
    逼目标选取贪心策略:步总选择剩数数字删高位低位序搜索位数字递增删数字否删第递减区间首字符然回串首述规删数字重复程s次剩数字串便问题解
    具体算法:
    输入s n
    while( s > 0 )
    { i1 串首开始找
    while (i < length(n)) && (n[i]{i++}
    delete(ni1) 删字符串n第i字符
    s
    }
    while (length(n)>1)&& (n[1]0’)
    delete(n11) 删串首产生零
    输出n
    三算法填空
    1背包问题贪心算法
    void Knapsack(int nfloat Mfloat v[]float w[]float x[])
    {
    Sort(nvw)
    int i
    for (i1i float cM
    for (i1i if (w[i]>c) break
    x[i]1
    c w[i]
    }
    if (i}
    2子段 动态规划算法
    int MaxSum(int n int a[])
    {
    int sum0 b0 sum存储前b[j] b存储b[j]
    for(int j1 j if (b>0) b+ a[j]
    else ba[i] 旦某区段负位置累
    if(b>sum) sumb

    }
    return sum
    }
    3快速排序
    template
    void QuickSort (Type a[] int p int r)
    {
    if (p int qPartition(apr)
    QuickSort (apq1) 左半段排序
    QuickSort (aq+1r) 右半段排序
    }
    }

    4排列问题
    Template
    void perm(Type list[] int k int m )
    { 产生[list[km]排列
    if(km)
    { 剩元素
    for (int i0i cout< }
    else 元素排列递产生排列
    for (int ik i {
    swap(list[k]list[i])
    perm(listk+1m)
    swap(list[k]list[i])
    }
    }
    5定已升序排序n元素a[0n1]现n元素中找出特定元素x
    容易设计出二分搜索算法:
    template
    int BinarySearch(Type a[] const Type& x int l int r)
    {
    while (l int m ((l+r)2)
    if (x a[m]) return m
    if (x < a[m]) r m1 else l m+1
    }
    return 1
    }
    6合排序描述:
    template
    void Mergesort(Type a[ ] int left int right)
    {
    if (leftint i( left+right)2
    Mergesort(a left i )
    Mergesort(a i+1 right)
    Merge(ab leftiright)合数组b
    Copy(ab leftright ) 复制数组a
    }
    }

    7计算xm值程
    int power ( x m )
    {计算xm值返回
    y( 1 )im
    While(i >0)
    yy*x
    (return y) 
    }
    四问答题
    1计算机求解问题步骤:
    1问题分析2数学模型建立3算法设计选择4算法指标5算法分析6算法实现7程序调试8结果整理文档编制
    2 算法定义:
    算法指解决问题时某种机械步骤定问题结果处理程
    3算法三素
    1操作2控制结构3数结构
    13 分治法动态规划法相点:
    求解问题分解成干子问题先求解子问题然子问题解原问题解
    两者点:适合动态规划法求解问题分解子问题互相独立分治法求解问题分解子问题互相独立
    回溯法中常见两类典型解空间树子集树排列树
    22请叙述动态规划算法贪心算法异
    点:需优子结构性质求优化问题
    点:
    动态规划:步作选择—赖子问题解
    贪心方法:步作选择—赖子问题解
    动态规划方法条件:子问题重叠性质
    贪心方法条件:优子结构性质贪心选择性质
    动态规划:底求解贪心方法: 顶求解贪心法时动态规划方法适动态规划方法时贪心法适
    23 请说明动态规划方法什需优子结构性质
    答:优子结构性质指问题优解包含子问题优解
    动态规划方法底计算子问题优解先计算子问题优解然利子问题优解构造问题优解需优子结构
    24 请说明:
    (1)优先队列什数结构实现?
    (2)优先队列插入算法基思想?
    (3)优先队列插入算法时间复杂度?
    答:(1)堆
    (2)根堆中元素x插入堆末尾
    然元素x关键字双亲关键字较
    元素x关键字双亲关键字
    元素x双亲交换然元素x新双亲关键字相直元素x关键字双亲关键字元素x根止
    (3)O( log n)
    26 算法复杂性分析中OΩΘ三记号意义什?忽略常数子情况
    OΩΘ分提供算法运行时间什界?
    答:
    果存两正常数cN0N≥N0|f(N)|≤C|g(N)|记作:f(N) O(g(N))时说f(N)阶高g(N)阶
    存两正常数C然数N0N ≥ N0时|f(N)|≥C|g(N)|记f(N)Ω(g(N))时说f(N)阶低g(N)阶
    果存正常数c1c2n0n≥n0c1|g(N)| ≤|f(N)| ≤ c2|g(N)|
    记作 f(N) (g(N)
    OΩΘ分提供算法运行时间界界均
    五算法设计分析题
    1.动态规划策略求解长公子序列问题:
    (1)出计算优值递方程
    (2)定两序列X{BCDA}Y{ABCB}请采动态规划策略求出长公子序列求出程
    答:1

    (2)
       Y A B C B
    X    0  0  0  0
    B  0  0  1  1  1
    C  0  0  1  2  2
    D  0  0 1 2 2
    A  0 1 1 2 2 长公子序列:{BC}

    2.列组函数f (n) g (n)确定f (n) O (g (n)) f (n) Ω(g (n))f(n) θ(g(n))简说明理
    (1) f(n)2n g(n)n
    (2) f(n) g (n)log n2
    (3) f(n)100 g(n)log100
    (4) f(n)n3 g(n) 3n
    (5) f(n)3n g(n)2n
    答:
    (1) f(n) O(g(n)) g(n)阶f(n)阶高
    (2) f(n) Ω(g(n)) g(n)阶f(n)阶低
    (3) f(n) θ(g(n)) g(n)f(n)阶
    (4) f(n) O(g(n)) g(n)阶f(n)阶高
    (5) f(n) Ω(g(n)) g(n)阶f(n)阶低
    3.图示连通网络G克鲁斯卡尔(Kruskal)算法求G生成树T请写出算法执行程中次加入T边集TE中边说明该算法贪心策略算法基思想简分析算法时间复杂度
    1
    2
    3
    4
    5
    6
    18
    11
    17
    15
    19
    21
    26
    6
    7
    9
    答:
    TE{(34) (23)(15)(46)(45)}
    贪心策略次连接两连通分量边中选权值边
    基思想:首先图中顶点放生成树中然次连接两连通分量边中选权值边放入生成树中直生成树中n1条边
    时间复杂度:O(eloge)
    4 请分治策略设计递排序算法分析时间复杂性(求:分出divideconquercombine三阶段花时间基础列出递方程套公式法求出解渐进阶)
    答 : Template
    void MergeSort (Type a[ ] int left int right)
    { if (left { int i(left+right)2
    MergeSort(a left i)
    MergeSort(a i+1 right)
    Merge(a b left right)
    Copy(a b left right)
    }
    }
    Divide 阶段时间复杂性: O(1)
    Conquer阶段时间复杂性: 2T(n)
    Combine阶段时间复杂性: Θ(n)


    套公式法:a2 b2 nlog ba n f(n)n f(n)nlog ba 阶
    ∴T(n) Θ(nlogn)






    2
    3
    4
    5
    6
    7
    8
    2
    1
    4
    3
    6
    5
    8
    7
    3
    4
    1
    2
    7
    8
    5
    6
    4
    3
    2
    1
    8
    7
    6
    5
    5
    6
    7
    8
    1
    2
    3
    4
    6
    5
    8
    7
    2
    1
    4
    3
    7
    8
    5
    6
    3
    4
    1
    2
    8
    7
    6
    5
    4
    3
    2
    1
    1
    2
    3
    4
    5
    6
    7
    8
    2
    1
    4
    3
    6
    5
    8
    7
    3
    4
    1
    2
    7
    8
    5
    6
    4
    3
    2
    1
    8
    7
    6
    5
    5
    6
    7
    8
    1
    2
    3
    4
    6
    5
    8
    7
    2
    1
    4
    3
    7
    8
    5
    6
    3
    4
    1
    2
    8
    7
    6
    5
    4
    3
    2
    1
    1
    2
    3
    4
    5
    6
    7
    8
    2
    1
    4
    3
    6
    5
    8
    7
    3
    4
    1
    2
    7
    8
    5
    6
    4
    3
    2
    1
    8
    7
    6
    5
    5
    6
    7
    8
    1
    2
    3
    4
    6
    5
    8
    7
    2
    1
    4
    3
    7
    8
    5
    6
    3
    4
    1
    2
    8
    7
    6
    5
    4
    3
    2
    1

    1
    2
    3
    4
    5
    6
    7
    8
    2
    1
    4
    3
    6
    5
    8
    7
    3
    4
    1
    2
    7
    8
    5
    6
    4
    3
    2
    1
    8
    7
    6
    5
    5
    6
    7
    8
    1
    2
    3
    4
    6
    5
    8
    7
    2
    1
    4
    3
    7
    8
    5
    6
    3
    4
    1
    2
    8
    7
    6
    5
    4
    3
    2
    1

    1 2 3 4 5 6 7









    5设n2k运动员进行循环赛现设计满足求赛日程表
    选手必须n1名选手赛次选手天赛次
    循环赛短时间完成
    (1)(4分)循环赛少需进行( n1 )天
    (2)(6分)n238时请画出循环赛日程表

    6考虑哈夫曼算法找字符abcdef 优编码字符出现文件中
    频数 2010644416求:
    (1)(4 分)简述哈夫曼算法构造优编码基步骤
    (2)(5 分)构造应哈夫曼树出abcdef 种优编码
    解:1)哈夫曼算法构造优编码树贪心算法基思想首先
    字符应n 棵树构成森林棵树结点根权应字符频率然重复
    列程n1 次:森林中根权两棵树进行合产生新树该新树根两子
    树分参合两棵子树根权两子树根权
    2)根题中数构造哈夫曼树图示

    出 abcdef 组优编码:0100000001000011 1001
    7考虑序列A[1n]中找元素问题分治算法描述:果n≤2 直接求解否序列等分成两子序列A[1n2]A[n2+1n]分找出两子序列元素x1y1 x2y2然求出A[1n]元素xmax{x1x2}元素ymin{y1y2}请出该算法计算时间T(n)满足递方程解方程确定算法时间复杂度假定n2k(k 正整数)
    答:
    算法时间复杂度满足递方程:
    T(n)2T(n2)+2(n>2)T(2)1
    n2 k(k 正整数)
    T(n) T(2 k) 2T(2 k1)+2 22T(2 k2)+ 22+2

    2k1T(2)+ 2k2+⋯+23+22+2
    2k1+⋯+23+22+2T(n)Q(n)
    8 考虑动态规划方法求解列问题:
    01背包数表求:够放入背包价值物品集合

    物品
    i
    重量 wi
    价值 vi
    承重量 W
    1
    w12
    v112
    W5
    2
    w21
    v210
    3
    w33
    v320
    4
    w42
    v415

    设: V(i j) —— 前 i 物品中够装入承重量 j 背包中总价值请递推式填写完整:
    V(0 j) 0(0物品)V(i 0) 0(承重量0)
    V(i j) V(i1 j) 第 i 物品装入 j < wi (超重)
    V(i j) max { } j > wi (超重)
    i优子集中 i优子集中
    底:行列填写表
    V
    j0
    1
    2
    3
    4
    5
    i0
    0
    0
    0
    0
    0
    0
    1
    0





    2
    0





    3
    0





    4
    0






    V
    j0
    1
    2
    3
    4
    5
    i0
    0
    0
    0
    0
    0
    0
    1
    0





    2
    0





    3
    0





    4
    0












    答:
    V(0 j) 0(0物品)V(i 0) 0(承重量0)
    V(i j) V(i1 j) 第 i 物品装入 j < wi (超重)
    V(i j) max { vi + V(i1jwj) V(i1 j) } j > wi (超重)
    i优子集中 i优子集中

    V
    j0
    1
    2
    3
    4
    5
    i0
    0
    0
    0
    0
    0
    0
    1
    0





    2
    0





    3
    0





    4
    0






    V
    j0
    1
    2
    3
    4
    5
    i0
    0
    0
    0
    0
    0
    0
    1
    0
    0
    12
    12
    12
    12
    2
    0
    10
    12
    22
    22
    22
    3
    0
    10
    12
    22
    30
    32
    4
    0
    10
    15
    25
    30
    37







    9请画出回溯法解4皇问题解空间树搜索空间树:
    解空间树:










    回溯法搜索空间树:


    10考虑分支限界解01背包问题
    定n种物品背包物品i重量wi价值vi背包容量C问应选择装入背包物品装入背包中物品总价值
    示例:n3 C30 w{16 15 15} v{45 25 25}
    求:1问题解空间树
    2约束条件
    2剪枝?
    解:
    问题解空间树:


    约束条件:
    剪枝?:
    设r前尚未考虑剩余物品价值总Cv前价值bestv前优价值
    r+Cv≤bestv时剪右子树
    11请画出回溯法解n301背包问题解空间树三物品重量{20 15 10}价值{20 30 25}背包容量25时搜索空间树
    答:
    解空间树:
    1
    1
    1
    1
    1
    1
    0
    0
    0
    0
    0
    0
    0
    1
    1
    2
    3
    4
    5
    7
    8
    11
    12
    14
    15
    3
    10
    6
    9


    搜索空间树:
    1
    行解
    价值20
    价值55
    价值30
    价值25
    价值0
    1
    1
    1
    1
    0
    0
    0
    0
    0
    0
    1
    1
    2

    8
    11
    12
    14
    15
    13
    10
    6
    9

    文档香网(httpswwwxiangdangnet)户传


    《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
    该内容是文档的文本内容,更好的格式请下载文档

    下载文档到电脑,查找使用更方便

    文档的实际排版效果,会与网站的显示效果略有不同!!

    需要 2 香币 [ 分享文档获得香币 ]

    下载文档

    相关文档

    算法设计与分析复习题目及答案

     一、选择题1、二分搜索算法是利用(   A  )实现的算法。A、分治策略   B、动态规划法   C、贪心法    D、回溯法2、下列不是动态规划算法基本步骤的是( A  )。A、找出最优解...

    3年前   
    802    0

    算法设计与分析试卷及答案

    湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题题 号一二三四五总分统分人得 分阅卷人复查人考试类型:开卷 试卷类型:C卷 考...

    1年前   
    412    0

    算法设计与分析试卷A及答案

     试题纸(A卷) 课程名称: 算法设计与分析 适用专业年级: 2008级计算机、电本 考生学号: ...

    1年前   
    556    0

    数据结构和算法课程设计题目

    XX大学课程设计课程名称: 数 据 结 构 与 算 法院(部)名 称: 信息与计算科学学院组长姓名学号 同组人员姓名指导教师姓名: 设 计 时 间: 2010.6.7-...

    10个月前   
    362    0

    《算法分析与设计》期末考试复习题纲

    《算法分析与设计》期末复习题一、 选择题1. 算法必须具备输入、输出和( D )等4个特性。A.可行性和安全性 B.确定性和易读性C.有穷性和安全性 ...

    2年前   
    576    0

    算法设计与分析课程期末试卷A卷(含答案)

    华南农业大学期末考试试卷(A卷)2008学年第一学期  考试科目: 算法分析与设计 考试类型:(闭卷)   考试时间: 120 分钟学号 姓名 ...

    1年前   
    296    0

    毕业论文:TIPTOP双档算法设计与分析

    为了进一步完善现有的TIPTOP系统,针对工程部需求对企业设备进行有效登记管理,本人通过编写TIPTOP双档程序cfar222初步完成了对设备仪器的数据采集。在cfar281双档项目实施后,工程...

    5年前   
    1469    0

    算法分析期末试题集答案

    《算法分析与设计》期末复习题(一)一、 选择题1.应用Johnson法则的流水作业调度采用的算法是(D)A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法2.H...

    1年前   
    527    0

    粒子群算法(优化算法)毕业设计论文

     毕 业 论 文 题 目 粒子群算法及其参数设置 专 业 信息与计算科学 班 级 ...

    5年前   
    1449    0

    毕业设计题目

    毕业设计题目  营销1,2,3班毕业设计题目 学号 姓名 指导教师 毕业设计题目 张晓丹 面向营销网站规划设计 (3人) 利用电子邮件进行外向营销的方法设计 客户满意度调查与预测的模型设计 即...

    11年前   
    977    0

    浅谈算法设计与分析课程教学方法

    浅谈算法设计与分析课程教学方法摘要:“算法设计与分析(双语)”是北京林业大学计算机科学与技术专业的专业核心课程。根据课程的教学目标,提出“以赛启教”的教学实践思路,从教学内容、教学方法和考核方...

    1年前   
    299    0

    数值分析复习题及答案

    数值分析复习题一、选择题1. 3.142和3.141分别作为的近似数具有( )和( )位有效数字.   A.4和3          B.3和2    C.3和4          D....

    1年前   
    571    0

    SWOT分析详解

    ムᅝꩃ唆ⲙᕼ灞鲨쎭ꃱぶ쀓ުጧᒧᏄꋣ䑽ꃠꠎ㠹㼚軧Ĝ䳅⮪뺀嵀攜遛扠냿쀖蠮ϕ뮀움ဃ㹀㶗채ਟ锎耑꠽瀝‏ݐ軲ꎂ惪갋䨿̧ఐ切瀁耰泔缞볯拓‏ﲉ膬㰍᳕荲袂〵ⱸ儾䤼ⰿ愺ͼ唚艌恍䞵鞎ⷕରથֈ㲠脧...

    12年前   
    865    0

    农水复习题目

    第一章 农田水分状况和土壤水分运动一、填空1、农田水分存在三种基本型式,即:_________、_______和_______。2、土壤水分的形态有:_________、________、_...

    4年前   
    687    0

    最新NOIP初赛复习14基本算法思想总结

    一个程序往往要包含两个方面的描述:一是对数据组织的描述,就是数据的类型和数据的组织形式(例如数组),称作数据结构;一是对程序操作流程的描述,就是程序的操作步骤,也就是所谓算法。正如著名的计算机科...

    3年前   
    445    0

    幂的运算法则复习课练习

    1:把同类项的系数相加,所得的结果作为系数,字母和字母的指数保持不变2: “都为正整数〕〞和语言表述“同底数幂相乘,底数不变,指数相加,幂的乘方,底数不变,指数相乘,积的乘方,等于把积的每一个...

    7个月前   
    168    0

    数值分析各算法流程图

    数值分析各算法流程图 一、插值 1、 拉格朗日插值流程图:( 相应程序:lagrintp(x,y,xx)) ...

    5年前   
    1727    0

    C课程设计题目及要求

    课程设计题目 选题一: 学生信息管理系统设计 学生信息包括:学号,姓名,年龄,性别,出生年月,地址,电话,E-mail等。(测试数据不少5个人,可以用本班同学的具体数据为背景) 软件由下...

    7年前   
    3852    0

    —基于机器学习的人脸识别算法的设计与实现

    人脸识别技术是一种新型的生物特征认证技术。人脸识别技术也是一个非常活跃的研究领域,涵盖了许多领域,例如数字图像处理。随着人们对应用程序需求的增长,面部识别技术趋向于大量使用,使用微芯片和标准化。

    3年前   
    802    0

    线索二叉树算法的设计与实现

    随着时代的不断进步,计算机技术也随之得到发展。数据结构在计算机技术的发展中起到巨大的作用。数据结构为构建出高效的计算机算法打下了坚实的基础。良好的数据结构能够提高算法效率的同时也能减少对系统资源的占用[

    3年前   
    989    0

    文档贡献者

    文***品

    贡献于2020-11-28

    下载需要 2 香币 [香币充值 ]
    亲,您也可以通过 分享原创文档 来获得香币奖励!
    下载文档

    该用户的其他文档