层次遍历算法笔试题
“kengqiang00”通过精心收集，向本站投稿了8篇层次遍历算法笔试题，下面小编给大家带来层次遍历算法笔试题，希望能帮助到大家!
篇1：层次遍历算法笔试题
// 二叉树的数据结构
structBinaryTree
{
int value; // 不写模板了，暂时用整形代替节点的数据类型
BinaryTree *left;
BinaryTree *right;
};
BinaryTree*root; // 已知二叉树的`根节点
//层次遍历
voidLevel( const BinaryTree *root )
{
Queue *buf = new Queue; // 定义一个空队列，假设此队列的节点数据类型也是整形的
BinaryTree t; // 一个临时变量
buf.push_back(root); //令根节点入队
while( buf.empty == false ) // 当队列不为空
{
p = buf.front(); // 取出队列的第一个元素
cout<
value<<' ';
if( p->left != NULL ) // 若左子树不空，则令其入队
{
q.push( p->left );
}
if( p->right != NULL ) // 若右子树不空，则令其入队
{
q.push( p->right );
}
buf.pop(); // 遍历过的节点出队
}
cout< } #define maxsize 100 typedef struct { Bitree Elem[maxsize]; 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; }//endwhile if (!StackEmpty(s)) { p=pop(s); visite(p->data); //访问根结点 p=p->rchild; //通过下一次循环实现右子树遍历 }//endif }//endwhile }//InOrderUnrec 冒泡法： 这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： #include void BubbleSort(int* pData,int Count) { int iTemp; for(int i=1;i { for(int j=Count-1;j>=i;j--) { if(pData[j] { iTemp = pData[j-1]; pData[j-1] = pData[j]; pData[j] = iTemp; } } } } void main { int data = {10,9,8,7,6,5,4}; BubbleSort(data,7); for (int i=0;i<7;i++) cout< } 倒序 第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次) 第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次) 第一轮：7,8,10,9->7,8,9,10(交换1次) 循环次数：6次 交换次数：6次 其他： 第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 第一轮：7,8,10,9->7,8,9,10(交换1次) 循环次数：6次 交换次数：3次 上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。 现在注意，我们给出O方法的定义： 若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵，不要说没学好数学呀，对于编程数学是非常重要的!!!) 现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以(n)=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样(每次循环判断都会交换)，复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因，我们通常都是通过循环次数来对比算法。 选择法： 现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能(某些情况下) 这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择最小的与第二个交换，这样往复下去。 #include void SelectSort(int* pData,int Count) { int iTemp; int iPos; for(int i=0;i { iTemp = pData[i]; iPos = i; for(int j=i+1;j { if(pData[j] { iTemp = pData[j]; iPos = j; } } pData[iPos] = pData[i]; pData[i] = iTemp; } } void main { int data = {10,9,8,7,6,5,4}; SelectSort(data,7); for (int i=0;i<7;i++) cout< } 倒序(最糟情况) 第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次) 第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次) 循环次数：6次 交换次数：2次 其他： 第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次) 第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次) 循环次数：6次 交换次数：3次 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n 所以我们有f(n)=O(n)。 所以，在数据较乱的时候，可以减少一定的交换次数。 交换法： 交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。 #include void ExchangeSort(int* pData,int Count) { int iTemp; for(int i=0;i { for(int j=i+1;j { if(pData[j] { iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; } } } } void main { int data = {10,9,8,7,6,5,4}; ExchangeSort(data,7); for (int i=0;i<7;i++) cout< } 倒序 第一轮：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次) 第二轮：7,10,9,8->7,9,10,8->7,8,10,9(交换2次) 第一轮：7,8,10,9->7,8,9,10(交换1次) 循环次数：6次 交换次数：6次 其他： 第一轮：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次) 第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 第一轮：7,8,10,9->7,8,9,10(交换1次) 循环次数：6次 交换次数：3次 从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好，在某些情况下稍差)。 笔试题（算法类） 算法 1，鸟与火车问题，鸟和a火车从A地出发开往B，b火车从B地同时开往A，鸟在碰到b后往回飞，碰到a再往回飞，直到两车相碰，问鸟飞了多远，知道a，b，鸟的速度，和AB距离， 2，3顶黑色和2顶白色帽子，3个outlaw，每人一顶，自己不知道自己什么颜色，第一个猜错入狱，第二个也猜错入狱，第3个猜对了出狱，问如何猜对的'。 3，Give 2 Node , 问如何找得 Common root.(大概意思）。 C/C++ 1，判断表达式正确与否(比较简单，会C就会) 2，x86,32位系统，sizeof的大小， char str[]=”Hello”;char *p=str; int n=10; 问sizeof(str);sizeof(p);sizeof(n)的大小； void *p=malloc(100) 问sizeof(p)大小； 3，问include 4，写一String类，实现atoi(const char *s)功能（大概意思）； 其他 explain how ping works. 1. 请简介各种排序算法(以箱排序，冒泡，快速排序和堆排序为例)的排序过程，及其空间复杂度，平均时间复杂度和最坏时间复杂度． 2. 请检测一个未知长度的单向链表(NULL结束)是否存在环路. 3. 输入一正整数N，去掉其中任意S个数字后，剩下的数字按原左右次序组成一新正整数．寻找一方案，使剩下的.数字组成的新数最小，输出结果． 4. 有一个整数数列, 每个数可以是正, 负或零. 请找出其最佳连续子列使其子列内各数之和为最大. 简答(30分) 1、extern “C”{}是什么含义?用来解决什么问题，(10分) 2、至少说出两种经典设计模式，并举例说明使用场景，有伪代码更加.(10分) 3、TCP连接的.time_wait是什么状态，描述其发生的场景，说明它存在的好处坏处。(10分) 【层次遍历算法笔试题】相关文章： 1.笔试题 3.CPMP笔试题 4.笔试题继承 5.笔试题编译程序 6.HTC笔试题 8.雅虎笔试题 9.摩托罗拉笔试题 10.Facebook笔试题篇2：中序遍历非递归算法笔试题
篇3：C笔试题算法
篇4：C笔试题算法
篇5：C笔试题算法
篇6：笔试题算法类
篇7：笔试题算法设计和编程
篇8：算法与程序设计笔试题
文档为doc格式
