数据结构与算法面试题

16,72,31,23,94,53 16,23,53,31,94,72 94,23,31,72,16,53 16,53,23,94,31,72

3）下列关键字序列为堆的是（）？ 100，60，70，50，32，65 60，70，65，50，32，100 65，100，70，32，50，60 70，65，100，32，50，60 32，50，100，70，65，60 50，100，70，65，60，32

4）以下关于堆的叙述中正确的是（）

Ⅰ.在一个大根堆中，最小关键字的记录一定属于最底层的叶子结点层

Ⅱ.在一个小根堆中，从根结点到某个叶子结点所经路径上的结点构成一个递增有序序列 Ⅲ.堆一定是一棵完全二叉树

Ⅳ.由某关键字序列构造的一棵完全二叉树经过一次筛选便可以变成一个堆 仅Ⅰ、Ⅲ 仅Ⅱ、Ⅲ 仅Ⅱ、Ⅲ、Ⅳ 仅Ⅰ、Ⅱ、Ⅲ

5）最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（） [3，2，5，7，4，6，8] [2，3，5，7，4，6，8] [2，3，4，5，7，8，6] [2，3，4，5，6，7，8]

6）下列关于堆和栈的区别描述错误的有？

申请方式的不同，堆是系统自动分配，栈是自己申请

栈的大小是固定的，堆的大小受限于系统中有效的虚拟内存 栈的空间由系统决定何时释放，堆需要自己决定何时去释放 堆的使用容易产生碎片，但是用起来最方便

7）【0、2、1、4、3、9、5、8、6、7】是以数组形式存储的最小堆，删除堆顶元素0后的结果是（）

【2、1、4、3、9、5、8、6、7】 【1、2、5、4、3、9、8、6、7】 【2、3、1、4、7、9、5、8、6】 【1、2、5、4、3、9、7、8、6】

8）关于数据结构，下面叙述中正确的是（） 直接选择排序是一种稳定的排序方法

哈弗曼树带权路径长度最短的树，路径上权值较大的结点离根较近 拓扑排序是指结点值得有序排序

当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整到合适位置

问答题：

1）TopK问题，求数组中最大的K个元素 代码：

public class heap_test {//求第k大的数，维护一个大小为k的最小堆 private static int k,n; private static int []a=new int [101]; public static void down(int i,int n){ int t,temp; while(i*2<=n){ if (a[i]>a[i*2]){ t=i*2; }else{ t=i; } if (a[t]>a[i*2+1]){ t=i*2+1; } if (t!=i){ temp=a[t]; a[t]=a[i]; a[i]=temp; i=t; }else break; } } public static void main(String[] args) { Scanner cin=new Scanner(System.in); k=cin.nextInt();//读取k n=0; while(cin.hasNextInt()){ n++; a[n]=cin.nextInt(); } cin.close(); if (k<=n){ for (int i=k/2;i>=1;i--){ down(i,k); } int num=n; for (int i=k+1;i<=num;i++){ if (a[i]>a[1]){//如果更大 a[1]=a[i]; down(1,i); } }

} } }

System.out.println(a[1]);

6. 二叉树

面试题 选择题：

1）设某二叉树的后序序列为cba，中序序列为abc，则前序序列为什么 CBA ABC CAB BCA

2）一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有______________个 33 34 32 30

3）下列关于m阶的B-树的论述不正确的是 B-树是一种平衡的多路查找树 树中每个结点至多有m棵子树

若根结点不是叶子结点，则至少有两棵子树 树中的叶子结点可出现在不同层次上

4）设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子数为() 5 6 7 8

6）已知二叉树Node定义如下, 现在需要设计一个方法交换左子树和右子树, 下列方法中, 可以实现交换的是? （） class Node { public:

Node* left; Node* right; char content;

Node(char content); private:

Node(const Node&);

Node& operator=(const Node& node);

};

void swap(Node root) {Node* temp=root.left;root.left=root.right;root.right=temp;} void swap(Node& left, Node& right) {Node temp=left; left=right;right=temp;} void swap(Node* left, Node* right) {Node* temp=left; left=right;right=temp;} void swap(Node*& left, Node*& right) {Node* temp=left; left=right;right=temp;}

6）已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（）。 115 116 1895 1896

问答题： 1）前序遍历 递归代码：

public static void preorderTraversalRec(TreeNode root){ if (root == null) { return; }

System.out.print(root.val + \ preorderTraversalRec(root.left); preorderTraversalRec(root.right); }

非递归代码：

public void preOrder1(BinaryNode Node) {

Stack stack = new Stack<>(); while(Node != null || !stack.empty()) {

while(Node != null) {

System.out.print(Node.element + \ stack.push(Node); Node = Node.left; }

if(!stack.empty()) {

Node = stack.pop(); Node = Node.right; } } }

\ 1）中序遍历 递归代码：

public static void inorderTraversalRec(TreeNode root){ if (root == null) { return; }

inorderTraversalRec(root.left); System.out.print(root.val + \ inorderTraversalRec(root.right); }

非递归代码：

public void midOrder1(BinaryNode Node) {

Stack stack = new Stack<>(); while(Node != null || !stack.empty()) {

while (Node != null) {

stack.push(Node); Node = Node.left; }

if(!stack.empty()) {

Node = stack.pop();

System.out.print(Node.element + \ \ Node = Node.right; } }

}

2）后序遍历 递归代码：

public static void postorderTraversalRec(TreeNode root){ if (root == null) { return; }

postorderTraversalRec(root.left); postorderTraversalRec(root.right); System.out.print(root.val + \}

非递归代码：

public void posOrder1(BinaryNode Node) {

Stack stack1 = new Stack<>();