Algorithm 版 (精华区)

发信人: Lerry (哈哈,我是大象), 信区: Algorithm
标  题: 校内ACM选拔赛笔试题
发信站: 哈工大紫丁香 (2002年07月07日20:34:12 星期天), 站内信件

一  简答(8*5)
    1.简述用贪心算法满足的条件和使用动态规划的问题满足的条件.
    2.简述优化一个搜索问题的方法.
    3.求8个字母A,B,C,D,E,F,G,H的全排列中只有4个元素不在原来位置
      上的排列数.
    4.在M个0,N个1组成的字符串中,出现01或10的总次数为K的有多少个.
    5.简单说出下列算法的功能和应用范围:
        A)龙格-库塔法
        B)单纯形法
        C)模拟退出算法
        D)拉斯维加斯算法
    6.写出一种你最熟悉的程序设计开发环境和下列功能热键:
        A)程序执行
        B)单步监视
        C)添加监视变量
        D)程序执行到当前位置
    7.当程序出现以下错误时,从哪些方面考虑修改程序:
        A)STATCK OVERFLOW
        B)NULL POINTER
        C)找不到库函数或者已经定义的函数
    8.写出任意一个NP完全问题的描述
二  算法设计题(6*10)
    注意:该部分试题要求写出算法所使用的数据结构的定义和算法的描述,
    自己设计输入和输出格式并且说明
    1.给出一棵树的先根和后根遍历的顺序,输出这棵树的中根遍历顺序.
    2.写出一种平均复杂是O(NlogN)的排序算法.
    3.求两个数组的最大公共子序列的算法,要求分析复杂性.
    4.写出求解八皇后问题的算法,要求不准使用递归.
    5.写出求一个图的最大连通分量,要求分析复杂性.
    6.写出求N个数的组合数的算法,要求分析复杂性.


--
当一个女孩儿觉得她不太容易了解那个男人的时候，她会爱他。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: FTCL.hit.edu.cn]