2015-05-10
敬叶 初稿

数值计算

位运算习题

  1. 给定一个实数，如3.72，打印二进制表示，如果不能精确用二进制表示，打印ERROR。
  2. 给定一个整数，打印下一个最小和前一个最大的整数，满足和给定整数二进制表示法1的位数总数相同。
  3. 写一个程序实现位交换，b0/b1，b2/b3依次类推。
  4. 写一个程序计算一个整数中二进制表示1的个数。
  5. 数组A[1..n]包括整数0..n中的所有整数，很显然有一个整数丢了，如何找出这个整数。限定条件是不能直接访问A[i]，只提供函数bit(i, j)用于访问A[i]的第j位。

顺序数据结构

数组与字符串

  1. 给定一个字符串，确定其中是否每个元素都只出现了一次。
  2. 编写一个程序，删除字符串中所有的重复出现的字符，只需删除重复部分。
  3. 判断两个字符串是否为变位词，所谓变位是指可以只通过调整字符位置让两个字符相同。
  4. 判断一个字符串是否是另一个字符串的广义子串。即是否可以通过对另一个字符串删除字符得到。
  5. 给定一个函数is_substring(s1, s2)用于判断s1是否为s2的子字符串，仅使用该函数如何确定两个字符串是否可以通过循环移位使其相同。
  6. 给定一个整数数组，每个元素独一无二，请计算能够排列成连续数字的子数组的最大长度。
  7. 给定一个 \(N \times N\) 矩阵，将其顺时针旋转90度。
  8. 给定一个 \(N \times N\) 矩阵，如果一个元素为0，将其所在的行和列都置0。

链表习题

  1. 删除链表中的重复元素。
  2. 查找链表倒数第n个元素。
  3. 给定一个单向链表中间节点，如何删除该节点。
  4. 查找一个循环链表的入口点。

堆栈和队列

  1. 如何实现一个栈能够以 \(O(1)\) 的效率返回栈中的最小值。
  2. 如何通过两个栈来实现队列。
  3. 如何通过两个队列来实现一个栈。
  4. 使用给定的方法给栈排序：push()、pop()、peek()、is_empty()。
  5. 将许多个已排序的文件合并为一个大文件。

网状数据结构

树和图

  1. 判断一个二叉树是否是平衡树。
  2. 编写一个二叉树非递归中序遍历。
  3. 编写一个二叉搜索树的插入删除操作。
  4. 给定一个已排序数组，创建一个高度最小的二叉树。
  5. 给定一个二叉树，为每层创建一个链表包含该层所有元素。
  6. 给定二叉树中的一个节点，找其IN-order遍历的下一个节点。
  7. 给定二叉树中任意两个节点，找其最小公共祖先，注意不一定是二叉搜索树。
  8. 给定两个二叉树，判断其中一个是否是另一个的子树，假定树的规模很大。
  9. 给定一个二叉树，每个节点包含一个值，打印节点相加的和为给定值的所有路径。
  10. 给定一个有向图中的两点，判断两者之间是否有路径可达。