程序员复习资料.doc

|常考基础必知必会A. 排序：排序有几种，各种排序的比较，哪些排序是稳定的，快排的算法;B. 查找：哈希查找、二叉树查找、折半查找的对比，哈希映射和哈希表的区别?C. 链表和数组的区别，在什么情况下用链表什么情况下用数组?D. 栈和队列的区别?E. 多态，举例说明;overload 和 override 的区别?F. 字符串有关的函数，比如让你写一个拷贝字符串的函数啊，或者字符串反转啊什么的。strcpy 和 memcpy?G. 继承、多继承?H. 面向对象有什么好处 ?I. 说说 static 的与众不同之处，如果一个变量被声明为 static，它会被分配在哪里?在什么时候分配空间等?J. 什么是虚函数、纯虚函数、虚的析构函数，用途?K. 内存泄漏及解决方法 ?网络部分：OSI 模型 7 层结构，TCP/IP 模型结构?B. TCP/UDP 区别?|C. TCP 建立连接的步骤?D. 香农定理?二叉树三种遍历的非递归算法1.先序遍历非递归算法#define maxsize 100typedef structBitree Elemmaxsize;int top;SqStack;void PreOrderUnrec(Bitree t)SqStack s;StackInit(s);p=t;while (p!=null | !StackEmpty(s)while (p!=null) /遍历左子树visite(p->data);push(s,p);p=p->lchild; |/endwhileif (!StackEmpty(s) /通过下一次循环中的内嵌 while 实现右子树遍历p=pop(s);p=p->rchild; /endif /endwhile /PreOrderUnrec2.中序遍历非递归算法#define maxsize 100typedef structBitree Elemmaxsize;int top;SqStack;void InOrderUnrec(Bitree t)SqStack s;StackInit(s);p=t;while (p!=null | !StackEmpty(s)|while (p!=null) /遍历左子树push(s,p);p=p->lchild;/endwhileif (!StackEmpty(s)p=pop(s);visite(p->data); /访问根结点p=p->rchild; /通过下一次循环实现右子树遍历/endif /endwhile/InOrderUnrec3.后序遍历非递归算法#define maxsize 100typedef enumL,R tagtype;typedef struct Bitree ptr;tagtype tag;stacknode;|typedef structstacknode Elemmaxsize;int top;SqStack;/后序遍历void PostOrderUnrec(Bitree t)SqStack s;stacknode x;StackInit(s);p=t;do while (p!=null) /遍历左子树x.ptr = p; x.tag = L; /标记为左子树push(s,x);p=p->lchild;|while (!StackEmpty(s) p = x.ptr;visite(p->data); /tag 为 R，表示右子树访问完毕，故访问根结点 if (!StackEmpty(s)s.Elems.top.tag =R; /遍历右子树p=s.Elems.top.ptr->rchild; while (!StackEmpty(s);/PostOrderUnrec3.后序遍历非递归算法#define maxsize 100typedef enumL,R tagtype;typedef struct Bitree ptr;tagtype tag;stacknode;|typedef structstacknode Elemmaxsize;int top;SqStack;/后序遍历void PostOrderUnrec(Bitree t)SqStack s;stacknode x;StackInit(s);p=t;do while (p!=null) /遍历左子树x.ptr = p; x.tag = L; /标记为左子树push(s,x);p=p->lchild;|while (!StackEmpty(s) p = x.ptr;visite(p->data); /tag 为 R，表示右子树访问完毕，故访问根结点 if (!StackEmpty(s)s.Elems.top.tag =R; /遍历右子树p=s.Elems.top.ptr->rchild; while (!StackEmpty(s);/PostOrderUnrec2、线性表(1) 性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。(2)单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。(3)单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。3、栈与队列|你可以问一下自己是不是已经知道了以下几点：(1)栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据(请注意包括：存和取两部分) 的特点。(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n! 阶乘问题，fib 数列问题，hanoi 问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。(3)栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。(4)循环队列中判队空、队满条件，循环队列中入队与出队( 循环队列在插入时也要判断其是否已满，删除时要判断其是否已空)算法。【循环队列的队空队满条件为了方便起见，约定：初始化建空队时，令front=rear=0,当队空时：front=rear ，当队满时：front=rear 亦成立，因此只凭等式 front=rear 无法判断队空还是队满。有两种方法处理上述问题：(1)另设一个标志位以区别队列是空还是满。|(2)少用一个元素空间，约定以“队列头指针 front 在队尾指针 rear 的下一个位置上” 作为队列“满”状态的标志。队空时： front=rear，队满时： (rear+1)%maxsize=front】如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。循环队列的主要操作：(1)创建循环队列(2)初始化循环队列(3)判断循环队列是否为空(4)判断循环队列是否为满(5)入队、出队/空出头尾之间的一个元素不用#include#include#define MAXSIZE 100typedef struct