一些常見的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_ 閱讀(265) | 評論 (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能直接訪問對齊的數據，當它試圖訪問一個未對齊的數據時，會在內部進行一系列的調整，這些調整對于程序來說是透明的，但是會降低運行速度，所以編譯器在編譯程序時會盡量保持數據對齊。
  閱讀全文