初赛复习:程序设计基础知识

算法

  1. 有穷性,确定性,输入,输出,可行性
  2. 复杂度分时空复杂度,时间复杂度为O(x),空间复杂度可以划分为输入所需存储,程序本身存储,逻辑运算所需存储。
  3. 算法结构有顺序结构,选择结构,循环结构

  1. 操作插入查询弹出的都是栈顶元素

队列

  1. 操作的查询弹出都是队头元素
  2. 插入都是插入到队尾

  1. N个点N-1条边列检的结构
  2. 一般有一个确定的跟根Root
  3. 先中后序遍历指的是根节点的遍历顺序
  4. 后缀表达式用的是中序遍历

  1. 有向图和无向图以及不连通图或者是连通图之分。
  2. 度可分入度出度
  3. 欧拉路有两个奇点,欧拉回路有零个奇点

N,P,C问题

  1. P问题:指存在多项式时间解法的问题,比如二分查找
  2. NP问题:指存在多项式时间验证的问题,比如独立集问题
    P问题一定是NP的,因为只需要判定给定的解是否等于计算得到的解就可以。
  3. NPC:指所有的NP问题都可以多项式规约到它的问题

发表评论

电子邮件地址不会被公开。 必填项已用*标注