知名公司数据结构笔试题
1. 把一个链表反向,递归，非递归都写一遍。
1.试编写3个函数实现
（1）建立一个双向链表
（2）插入一个节点
（3）删除一个节点
2．自己定义数据结构，写出程序：二叉树的前序遍历。
3.实现双向链表删除一个节点P，在节点P后插入一个节点，写出这两个函数。
4.下面哪种排序法对12354最快
a quick sort
b.buble sort
c.merge sort
5.哪种结构，平均来讲，获取一个值最快
a. binary tree
b. hash table
c. stack
6.一个二叉树的三种遍历方法的输出结果
7.链表按升序打印每打印完一个节点就将该节点从链表中删除
8.选择一种算法来整理出一个链接表。你为什么要选择这种方法？现在用o(n)时间来做。
9. 用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。
10.给两个变量，如何找出一个带环单链表中是什么地方出现环的？
11.哈希表和数组的定义，区别，优缺点。
12.链接表和数组之间的区别是什么？
任选一门语言，当场定义二叉排序树数据结构，写出两个函数：初始化，删除一个节点，20分钟
13. 递归的折半查找算法[不限语言]
14. 解释一下什么是B+树,如何实现B+树的查找和插入.（用图示）
15．实现双向链表删除一个节点P，在节点P后插入一个节点，写出这两个函数。
13．排序方法比较 （ intel ）
排序方法 平均时间 最坏时间 辅助存储
直接插入排序 O(N2) O(N2) O(1)
起泡排序 O(N2) O(N2) O(1)
快速排序 O(Nlog2N) O(N2) O(Nlog2N)
简单选择排序 O(N2) O(N2) O(1)
堆排序 O(Nlog2N) O(Nlog2N) O(1)
归并排序 O(Nlog2N) O(Nlog2N) O(n)
基数排序 O(d(n+radix))O(d(n+radix)) O(radix)
17.一个链表的操作，注意代码的健壮和安全性。要求：
（1）增加一个元素；
（2）获得头元素；
（3）弹出头元素（获得值并删除）。
18.内排序算法
19.折半查找的复杂度，证明
20.sizeof()和strlen()的使用.
21.顺序存储结构的优点，散列法的思想是什么？
22.汉罗塔算法，不能递归...
23．一个链表的结点结构
struct Node
{
int data ;
Node *next ;
};
typedef struct Node Node ;
(1)已知链表的头结点head,写一个函数把这个链表逆序 (Intel)
(2)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表
依然有序。
(3)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表
依然有序，这次要求用递归方法进行。 ( Autodesk )
24．编最优化Bubble(int *pIntArray,int L)，要求:交换元素不能用临时变量，如果有序需要最优。