笔试面试前需要掌握的专业知识.doc

需要掌握的知识汇总 2007-9-22 前面是各种专业知识及里面所需要掌握的各种重点,后面是一些常用的技术点。 1. 程序运行中堆与栈的区别。栈,就是那些由编译器在需要的时候分配,在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。堆,就是那些由 new 分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制, 一般一个 new 就要对应一个 delete 。如果程序员没有释放掉, 那么在程序结束后, 操作系统会自动回收。 2. 排序二叉树的增、删、查等基本操作。先把二叉树的基本思路和大致操作方法看一下书,然后敲敲代码练****一下。这里我写了一个二叉树的增、查、删功能,写得不是很简洁。#include <cstdlib> #include <iostream> using namespace std; typedef struct p{ int value; struct p* left; struct p* right; } Point; int addPoint(Point **root, int targetValue) { if(*root == NULL) { *root = new Point(); (*root)->left = (*root)->right = NULL; (*root)->value = targetValue; return 0; } Point* p= *root; Point* q= *root; while(p != NULL) {q= p; if(q->value < targetValue) p= q->right; else if(q->value > targetValue) p= q->left; else return 0; }p= new Point(); p->left = p->right = NULL; p->value = targetValue; if(q->value < targetValue) q->right = p; else if(q->value > targetValue) q->left = p; return 0;} int showTree(Point* p) { if(p == NULL) return 0; showTree(p->left); cout<<p->value<<" "; showTree(p->right); return 0;} int delPoint(Point **root, int targetValue) { if(*root == NULL) return 1; //首先找到要删除的节点 Point* p= *root; Point* q= p; while(p != NULL) { if(p->value == targetValue) break; q= p; if(q->value < targetValue) p= q->right; else if(q->value > targetValue) p= q->left; } //如果没有对应值,则退出 if(p == NULL) return 1; //如果 p没有右子树,则直接将左子树上移 if(p->right == NULL) { if(q->value < targetValue) q->right = p->left; else if(q->value > targetValue) q->left = p->left; delete p; return 0; } //如果 p有右子树,则使用 p的后继替换 p Point* r= p->right; Point* s= p; while(r->left != NULL) {s= r;r= r->left; } if(s == p){ s->right = r->right; } else { s->left = r->right; } if(p == *root) *root = r; else { if(q->value < targetValue) q->right = r; else if(q->value > targetValue) q->left = r; } r->left = p->left; r->right = p->right; delete p; return 0;}i nt main(int argc, char *argv[]) { Point* mainRoot = NULL; int values[] = {10,5,4,2,7,1,20,2,31,5}; for(int i=0;i<10;i++) { addPoint