一些常见的C/C++题目（二）

归并排序      摘要: 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法。
　　申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
　　设定两个指针，最初位置分别为两个已经排序序列的起始位置
　　比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
　　重复步骤3直到某一指针达到序列尾   阅读全文

一些常见的C/C++题目（一）      摘要: 1、static有什么用途？（请至少说明两种）
(1).限制变量的作用域（变量、函数只能在该文件中使用）
(2).设置变量的存储域 （在全局区分配内存）
  阅读全文

指针与sizeof

内存池基本      摘要: 1、为什么使用内存池？
通常我们习惯直接使用new、malloc等API申请分配内存，这样做的缺点在于：由于所申请内存块的大小不定，当频繁使用时会造成大量的内存碎片并进而降低性能。
  阅读全文

线程池的使用（转）      摘要: 为什么要使用线程池：
创建多线程应用程序是非常困难的。需要会面临两个大问题。
一个是要对线程的创建和撤消进行管理，另一个是要对线程对资源的访问实施同步　。　
  阅读全文

线程与内核对象的同步      摘要: 若干种内核对象，包括进程，线程和作业。可以将所有这些内核对象用于同步目的。对于线程同步来说，这些内核对象中的每种对象都可以说是处于已通知或未通知的状态之中。

例如：：当进程正在运行的时候，进程内核对象处于未通知状态，当进程终止运行的时候，它就变为已通知状态。进程内核对象中是个布尔值，当对象创建时，该值被初始化为FALSE（未通知状态）。当进程终止运行时，操作系统自动将对应的对象布尔值改为TRUE，表示该对象已经得到通知。当线程终止运行时，操作系统会自动将线程对象的状态改为已通知状态。因此，可以将相同的方法用于应用程序，以确定线程是否不再运行。
  阅读全文

线程通信与同步      摘要: 线程需要在下面两种情况下互相进行通信：
• 当有多个线程访问共享资源而不使资源被破坏时。
• 当一个线程需要将某个任务已经完成的情况通知另外一个或多个线程时。
  阅读全文

线程      摘要: 1、线程的组成
（1）、一个是线程的内核对象，操作系统用它管理线程。内核对象还是系统用来存放线程统计信息的地方。
（2）、一个线程堆栈，用于维护线程执行时所需的所有函数参数和局部变量。
  阅读全文

进程间通信与同步      摘要: 讨论三个问题：
1、进程间如何通信呢，如何来相互传递信息呢？
（1）、低级通信：只能传递状态和整数值（控制信息）
–信号量（semaphore）
–信号（signal）
（2）、高级通信：能够传送任意数量的数据
–共享内存（shared memory）
–消息传递（message passing）
–管道（pipe）
  阅读全文

进程管理      摘要: 1、什么是进程？
：：一般将进程定义成一个正在运行的程序的一个实例。进程由两部分组成：
①、一个内核对象，操作系统用它来管理进程。内核对象也是系统保存进程统计信息的地方。
②、一个地址空间，其中包含所有执行体（executable）或DLL模块的代码和数据。此外，它还包含动态内存分配，比如线程堆栈和堆的分配。
  阅读全文

内核对象      摘要: 1、什么是内核对象？
内核对象的数据结构只能由内核访问。
他们有：令牌（access token）对象、事件对象、文件对象、文件映射对象、I/O完成端口对象、作业对象、mailslot对象、mutex对象、pipe对象、进程对象、semaphore对象、线程对象、waitable timer对象以及thread pool worker factory对象等等。大多数成员都是不同的对象类型特有的。
  阅读全文

B-树及B＋树      摘要: 1、B树的定义
B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：
（1）每个结点至多有m个子结点；
（2）除根结点和叶结点外，其它每个结点至少有个子结点；
（3）若根结点不是叶子结点，则至少有两个子结点；
（4）所有的叶结点在同一层；
（5）有k个子结点的非根结点恰好包含k-1个关键码。
  阅读全文

平衡二叉树 （AVL树）      摘要: 　在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为 AVL 树。
那么什么是 最小不平衡子树
　　以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。为了简化讨论，不妨假设二叉排序树的最小不平衡子树的根结点为 A ，则调整该子树的规律可归纳为下列四种情况：
  阅读全文

各种查找算法的实现

二叉搜索树（二叉排序树）（二叉查找树）      摘要: 1、二叉搜索树是二叉树的一种，树的每个结点含有一个数据项，每个数据项有一个键值。结点的存储位置是由键值的大小决定的，所以二叉搜索树是关联式容器。
(1)、 若它的左子树不空，则左子树上所有结点的键值均小于它的根结点的键值；
(2)、若它的右子树不空，则右子树上所有结点的键值均大于它的根结点的键值；
(3)、它的左、右子树也分别为二叉排序树。
注意：：：二叉排序树是一种动态树表，树的结构通常不是一次生成的。而是在查找的过程中，当树中不存在关键字等于给定值的节点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
  阅读全文

哈夫曼树      摘要: 哈夫曼树定义为：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。
1、那么什么是权值？什么是路径长度？什么是带权路径长度呢？
权值：哈夫曼树的权值是自己定义的，他的物理意义表示数据出现的次数、频率。可以用树的每个结点数据域data存放一个特定的数表示它的值。

路径长度：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 树中所有叶子节点的带权路径长度之和，WPL=sigma(w*l)

  阅读全文

优先队列      摘要: 优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。每个元素都有一个优先权或值
/////用堆实现优先队列
1、把优先队列中的元素按优先级大小组织成堆，堆顶元素具有最大优先级。
2、优先队列的插入与删除可以用堆的插入与删除实现。
3、优先队列在定义为priority_queue ，在STL中#include 中实现、
priority_queue, greater >qi2;
其中

  阅读全文

posted @ 2011-10-02 11:22 Yu_ 阅读(218) | 评论 (0)  编辑

堆排序      摘要: 估计还要问问：什么是堆，什么是堆排序？堆与计算机分配内存的堆相同吗？
很多资料给出：堆的定义是
（1）、n个关键字序列（Kl，K2，…，Kn）称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：
ki≤K2i且ki≤K2i+1 或 Ki≥K2i且ki≥K2i+1 (1≤i≤ n) //ki相当于二叉树的非叶结点，K2i则是左孩子，k2i+1是右孩子

  阅读全文

C/C++内存中的数据对齐问题      摘要: 数据对齐，是指数据所在的内存地址必须是该数据长度的整数倍。比如DWORD数据的内存其实地址能被4除尽，WORD数据的内存地址能被2除尽。x86 CPU能直接访问对齐的数据，当它试图访问一个未对齐的数据时，会在内部进行一系列的调整，这些调整对于程序来说是透明的，但是会降低运行速度，所以编译器在编译程序时会尽量保持数据对齐。
  阅读全文