一些常見的C/C++題目（二）

歸并排序      摘要: 歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法。
　　申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
　　設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
　　比較兩個指針?biāo)赶虻脑兀x擇相對小的元素放入到合并空間，并移動指針到下一位置
　　重復(fù)步驟3直到某一指針達(dá)到序列尾   閱讀全文

一些常見的C/C++題目（一）      摘要: 1、static有什么用途？（請至少說明兩種）
(1).限制變量的作用域（變量、函數(shù)只能在該文件中使用）
(2).設(shè)置變量的存儲域 （在全局區(qū)分配內(nèi)存）
  閱讀全文

指針與sizeof

內(nèi)存池基本      摘要: 1、為什么使用內(nèi)存池？
通常我們習(xí)慣直接使用new、malloc等API申請分配內(nèi)存，這樣做的缺點(diǎn)在于：由于所申請內(nèi)存塊的大小不定，當(dāng)頻繁使用時(shí)會造成大量的內(nèi)存碎片并進(jìn)而降低性能。
  閱讀全文

線程池的使用（轉(zhuǎn)）      摘要: 為什么要使用線程池：
創(chuàng)建多線程應(yīng)用程序是非常困難的。需要會面臨兩個大問題。
一個是要對線程的創(chuàng)建和撤消進(jìn)行管理，另一個是要對線程對資源的訪問實(shí)施同步　。　
  閱讀全文

線程與內(nèi)核對象的同步      摘要: 若干種內(nèi)核對象，包括進(jìn)程，線程和作業(yè)。可以將所有這些內(nèi)核對象用于同步目的。對于線程同步來說，這些內(nèi)核對象中的每種對象都可以說是處于已通知或未通知的狀態(tài)之中。

例如：：當(dāng)進(jìn)程正在運(yùn)行的時(shí)候，進(jìn)程內(nèi)核對象處于未通知狀態(tài)，當(dāng)進(jìn)程終止運(yùn)行的時(shí)候，它就變?yōu)橐淹ㄖ獱顟B(tài)。進(jìn)程內(nèi)核對象中是個布爾值，當(dāng)對象創(chuàng)建時(shí)，該值被初始化為FALSE（未通知狀態(tài)）。當(dāng)進(jìn)程終止運(yùn)行時(shí)，操作系統(tǒng)自動將對應(yīng)的對象布爾值改為TRUE，表示該對象已經(jīng)得到通知。當(dāng)線程終止運(yùn)行時(shí)，操作系統(tǒng)會自動將線程對象的狀態(tài)改為已通知狀態(tài)。因此，可以將相同的方法用于應(yīng)用程序，以確定線程是否不再運(yùn)行。
  閱讀全文

線程通信與同步      摘要: 線程需要在下面兩種情況下互相進(jìn)行通信：
? 當(dāng)有多個線程訪問共享資源而不使資源被破壞時(shí)。
? 當(dāng)一個線程需要將某個任務(wù)已經(jīng)完成的情況通知另外一個或多個線程時(shí)。
  閱讀全文

線程      摘要: 1、線程的組成
（1）、一個是線程的內(nèi)核對象，操作系統(tǒng)用它管理線程。內(nèi)核對象還是系統(tǒng)用來存放線程統(tǒng)計(jì)信息的地方。
（2）、一個線程堆棧，用于維護(hù)線程執(zhí)行時(shí)所需的所有函數(shù)參數(shù)和局部變量。
  閱讀全文

進(jìn)程間通信與同步      摘要: 討論三個問題：
1、進(jìn)程間如何通信呢，如何來相互傳遞信息呢？
（1）、低級通信：只能傳遞狀態(tài)和整數(shù)值（控制信息）
–信號量（semaphore）
–信號（signal）
（2）、高級通信：能夠傳送任意數(shù)量的數(shù)據(jù)
–共享內(nèi)存（shared memory）
–消息傳遞（message passing）
–管道（pipe）
  閱讀全文

進(jìn)程管理      摘要: 1、什么是進(jìn)程？
：：一般將進(jìn)程定義成一個正在運(yùn)行的程序的一個實(shí)例。進(jìn)程由兩部分組成：
①、一個內(nèi)核對象，操作系統(tǒng)用它來管理進(jìn)程。內(nèi)核對象也是系統(tǒng)保存進(jìn)程統(tǒng)計(jì)信息的地方。
②、一個地址空間，其中包含所有執(zhí)行體（executable）或DLL模塊的代碼和數(shù)據(jù)。此外，它還包含動態(tài)內(nèi)存分配，比如線程堆棧和堆的分配。
  閱讀全文

內(nèi)核對象      摘要: 1、什么是內(nèi)核對象？
內(nèi)核對象的數(shù)據(jù)結(jié)構(gòu)只能由內(nèi)核訪問。
他們有：令牌（access token）對象、事件對象、文件對象、文件映射對象、I/O完成端口對象、作業(yè)對象、mailslot對象、mutex對象、pipe對象、進(jìn)程對象、semaphore對象、線程對象、waitable timer對象以及thread pool worker factory對象等等。大多數(shù)成員都是不同的對象類型特有的。
  閱讀全文

B-樹及B＋樹      摘要: 1、B樹的定義
B樹是一種平衡的多分樹，通常我們說m階的B樹，它必須滿足如下條件：
（1）每個結(jié)點(diǎn)至多有m個子結(jié)點(diǎn)；
（2）除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外，其它每個結(jié)點(diǎn)至少有個子結(jié)點(diǎn)；
（3）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩個子結(jié)點(diǎn)；
（4）所有的葉結(jié)點(diǎn)在同一層；
（5）有k個子結(jié)點(diǎn)的非根結(jié)點(diǎn)恰好包含k-1個關(guān)鍵碼。
  閱讀全文

平衡二叉樹 （AVL樹）      摘要: 　在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個結(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了樹的平衡性，如果是因插入結(jié)點(diǎn)而破壞了樹的平衡性，則找出其中最小不平衡子樹，在保持排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的連接關(guān)系，以達(dá)到新的平衡。通常將這樣得到的平衡二叉排序樹簡稱為 AVL 樹。
那么什么是 最小不平衡子樹
　　以離插入結(jié)點(diǎn)最近、且平衡因子絕對值大于 1 的結(jié)點(diǎn)作根結(jié)點(diǎn)的子樹。為了簡化討論，不妨假設(shè)二叉排序樹的最小不平衡子樹的根結(jié)點(diǎn)為 A ，則調(diào)整該子樹的規(guī)律可歸納為下列四種情況：
  閱讀全文

各種查找算法的實(shí)現(xiàn)

二叉搜索樹（二叉排序樹）（二叉查找樹）      摘要: 1、二叉搜索樹是二叉樹的一種，樹的每個結(jié)點(diǎn)含有一個數(shù)據(jù)項(xiàng)，每個數(shù)據(jù)項(xiàng)有一個鍵值。結(jié)點(diǎn)的存儲位置是由鍵值的大小決定的，所以二叉搜索樹是關(guān)聯(lián)式容器。
(1)、 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的鍵值均小于它的根結(jié)點(diǎn)的鍵值；
(2)、若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的鍵值均大于它的根結(jié)點(diǎn)的鍵值；
(3)、它的左、右子樹也分別為二叉排序樹。
注意：：：二叉排序樹是一種動態(tài)樹表，樹的結(jié)構(gòu)通常不是一次生成的。而是在查找的過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的節(jié)點(diǎn)時(shí)再進(jìn)行插入。新插入的結(jié)點(diǎn)一定是一個新添加的葉子結(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。
  閱讀全文

哈夫曼樹      摘要: 哈夫曼樹定義為：給定n個權(quán)值作為n個葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman tree)。
1、那么什么是權(quán)值？什么是路徑長度？什么是帶權(quán)路徑長度呢？
權(quán)值：哈夫曼樹的權(quán)值是自己定義的，他的物理意義表示數(shù)據(jù)出現(xiàn)的次數(shù)、頻率。可以用樹的每個結(jié)點(diǎn)數(shù)據(jù)域data存放一個特定的數(shù)表示它的值。

路徑長度：在一棵樹中，從一個結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長度為L-1。

結(jié)點(diǎn)的帶權(quán)路徑長度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積。 樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和，WPL=sigma(w*l)

  閱讀全文

優(yōu)先隊(duì)列      摘要: 優(yōu)先隊(duì)列是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素。每個元素都有一個優(yōu)先權(quán)或值
/////用堆實(shí)現(xiàn)優(yōu)先隊(duì)列
1、把優(yōu)先隊(duì)列中的元素按優(yōu)先級大小組織成堆，堆頂元素具有最大優(yōu)先級。
2、優(yōu)先隊(duì)列的插入與刪除可以用堆的插入與刪除實(shí)現(xiàn)。
3、優(yōu)先隊(duì)列在定義為priority_queue ，在STL中#include 中實(shí)現(xiàn)、
priority_queue, greater >qi2;
其中

  閱讀全文

posted @ 2011-10-02 11:22 Yu_ 閱讀(264) | 評論 (0)  編輯

堆排序      摘要: 估計(jì)還要問問：什么是堆，什么是堆排序？堆與計(jì)算機(jī)分配內(nèi)存的堆相同嗎？
很多資料給出：堆的定義是
（1）、n個關(guān)鍵字序列（Kl，K2，…，Kn）稱為(Heap)，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡稱為堆性質(zhì))：
ki≤K2i且ki≤K2i+1 或 Ki≥K2i且ki≥K2i+1 (1≤i≤ n) //ki相當(dāng)于二叉樹的非葉結(jié)點(diǎn)，K2i則是左孩子，k2i+1是右孩子

  閱讀全文

C/C++內(nèi)存中的數(shù)據(jù)對齊問題      摘要: 數(shù)據(jù)對齊，是指數(shù)據(jù)所在的內(nèi)存地址必須是該數(shù)據(jù)長度的整數(shù)倍。比如DWORD數(shù)據(jù)的內(nèi)存其實(shí)地址能被4除盡，WORD數(shù)據(jù)的內(nèi)存地址能被2除盡。x86 CPU能直接訪問對齊的數(shù)據(jù)，當(dāng)它試圖訪問一個未對齊的數(shù)據(jù)時(shí)，會在內(nèi)部進(jìn)行一系列的調(diào)整，這些調(diào)整對于程序來說是透明的，但是會降低運(yùn)行速度，所以編譯器在編譯程序時(shí)會盡量保持?jǐn)?shù)據(jù)對齊。
  閱讀全文