工商自考-數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料.doc  （行考）

C#語(yǔ)言中，數(shù)組的基類是Array。    棧是一種 線性結(jié)構(gòu)。 在C#語(yǔ)言中，System.Collections命名空間中定義了隊(duì)列類Queue。 鏈表結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)都是由兩部分組成的，即一個(gè)用來(lái)存儲(chǔ)數(shù)據(jù)一個(gè)用來(lái)存儲(chǔ)下一個(gè)節(jié)點(diǎn)         的引用。 C#語(yǔ)言中提供了兩種類分別用來(lái)表示棧和隊(duì)列，它們是Stack類和Queue類         。 StringBuilder類表達(dá)的值為可變字符序列的類似字符串的對(duì)象。 圖有鄰接矩陣、鄰接表等存儲(chǔ)結(jié)構(gòu)。 遍歷圖有深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷等方法。 ArrayList類在.Net框架的System.Collections命名空間中 查找指定字符的方法是substring。 C#中提供了兩種操作字符串的方式，分別是String和 StringBuilder類。 假設(shè)一個(gè)棧里面沒(méi)有任何元素存在，我們稱之為空棧。 常用的查找算法有順序查找和折半查找。 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入；若初始數(shù)據(jù)基本反序，則選用選擇。 Length表示數(shù)組所有維數(shù)內(nèi)元素的總數(shù)量。 Add方法用于向ArrayList中添加一個(gè)元素。 希爾排序比較適合大數(shù)據(jù)集合。 在實(shí)現(xiàn)插入排序過(guò)程中，一般通過(guò)二層來(lái)實(shí)現(xiàn)。 二叉樹屬于非線性結(jié)構(gòu)。 棧的基礎(chǔ)操作一般包括：判斷棧是否為空、判斷棧是否已滿、進(jìn)棧和退棧。 \n轉(zhuǎn)義字符表示的是換行。 對(duì)于字典數(shù)據(jù)類型而言，它是通過(guò)鍵去匹配值的。 在ArrayList類中，用于返回指定數(shù)據(jù)項(xiàng)首次出現(xiàn)的索引的方法是IndexOf方法。 面向?qū)ο笏枷胧欠庋b、繼承及多態(tài)。 時(shí)間復(fù)雜度、空間復(fù)雜度是用來(lái)描述算法性能的。 常見的圖結(jié)構(gòu)包括無(wú)向圖和有向圖。 多維數(shù)組就是多個(gè)一維數(shù)組組成的。 C#語(yǔ)言中字符串定義為字符的序列，它可以是字母、數(shù)字和其他符號(hào)的組合。 當(dāng)棧中元素的個(gè)數(shù)n=0時(shí)，則稱之為空棧。 隊(duì)列結(jié)構(gòu)：隊(duì)列(queue)也是一種特殊的線性表，但是它允許在表的一端進(jìn)行插入操作，而在表的另一端進(jìn)行刪除操作。一般允許刪除的一端稱之為隊(duì)頭，允許插入的一端則稱之為隊(duì)尾。不含任何元素的空列表則稱為空隊(duì)列。 歸并排序算法：將數(shù)據(jù)初始序列看成是由n個(gè)長(zhǎng)度為1的已排序子序列組成。反復(fù)將兩個(gè)子序列合并成一個(gè)已排序的序列。重復(fù)直到合并成一個(gè)序列時(shí)，排序完成。 正則表達(dá)式：正則表達(dá)式中還有一個(gè)重要性的概念就是元字符，它是一種特殊的字符，用于表示重復(fù)、替換或者分組。 參數(shù)數(shù)組：同其它變量一樣，數(shù)組也可以作函數(shù)的參數(shù)。數(shù)組元素只能作函數(shù)實(shí)參，且同其它變量的用法沒(méi)有區(qū)別。 關(guān)鍵字是指數(shù)據(jù)序列（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（或記錄）。 棧又被稱為后進(jìn)先出(Last In First Out)的線性表，簡(jiǎn)稱LIFO線性表。 散列是一種非常有用的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，它可以迅速的操作數(shù)據(jù)(插入、查找等)。散列采用的數(shù)據(jù)結(jié)構(gòu)我們通常稱之為散列表。 正則表達(dá)式：正則表達(dá)式中還有一個(gè)重要性的概念就是元字符，它是一種特殊的字符，用于表示重復(fù)、替換或者分組。 關(guān)鍵字：是指數(shù)據(jù)序列（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。 冒泡排序：排序算法的得名是由于數(shù)值“像氣泡一樣”從集合的一端浮動(dòng)到另一端。假如現(xiàn)在要把一列數(shù)據(jù)按照從小到大的方式進(jìn)行排序，那么較大的數(shù)值浮動(dòng)到數(shù)列的右邊，較小的數(shù)值浮動(dòng)到數(shù)列的左邊。這種冒泡的效果可以通過(guò)多次遍歷集合，并且比較相鄰元素的數(shù)值，根據(jù)數(shù)值大小進(jìn)行位置交換。 棧(stack)，它是限定在表的一端進(jìn)行插入、刪除操作的特殊線性表，通常把棧所操作的一端稱之為棧頂(top)，另一端則稱之為棧底(bottom)。不含任何元素的空列表則稱為空棧。 簡(jiǎn)述插入排序?qū)崿F(xiàn)原理及執(zhí)行過(guò)程? 每一數(shù)據(jù)比較都將一個(gè)待排序的數(shù)據(jù)元素，按照其關(guān)鍵字的大小，插入到已經(jīng)排序的數(shù)據(jù)序列中，使插入后的數(shù)據(jù)序列仍然是有序的，直到全部數(shù)據(jù)序列元素插入完畢為止。 定義一個(gè)多維數(shù)組，該數(shù)組用于代表學(xué)生成績(jī)信息，且數(shù)組中每位同學(xué)有4科成績(jī)，定義該結(jié)構(gòu)并算出每位學(xué)員的平均分?jǐn)?shù)？ int [,] stuGrades = new[,]             {                {0,75,85,79,93},                {1,89,90,87,79},                {2,70,83,68,90},                {3,78,96,84,73},                {4,80,70,65,84}             };             //學(xué)生平均分             float averageGrade = 0.0f;             int last_stu = stuGrades.GetUpperBound(0);             int last_grade = stuGrades.GetUpperBound(1);             int intTotal;               for (int numRow = 0; numRow <= last_stu; numRow++)             {                 intTotal = 0;                 for (int numColumn = 0; numColumn <= last_grade; numColumn++)                 {                     intTotal += stuGrades[numRow, numColumn];                 }                 averageGrade = intTotal / last_grade;                 Console.WriteLine(string.Format("The Average Score of {0} is {1} ！",numRow,averageGrade));             } 數(shù)組結(jié)構(gòu)與鏈表結(jié)構(gòu)的區(qū)別是什么？鏈表結(jié)構(gòu)優(yōu)勢(shì)有哪些？ 對(duì)于數(shù)組而言，有序數(shù)組對(duì)于查找效率好高很多。但是鏈表結(jié)構(gòu)的執(zhí)行效率更高。 簡(jiǎn)述折半查找算法的實(shí)現(xiàn)原理及執(zhí)行流程？ 假定元素按升序排列，對(duì)于給定值k，從表的中間位置開始比較，如果k等于當(dāng)前數(shù)據(jù)元素的關(guān)鍵字，則查找成功。若k小于當(dāng)前數(shù)據(jù)元素的關(guān)鍵字，則在表的前半部分繼續(xù)查找；反之，則在表的后半部分繼續(xù)查找。依次重復(fù)進(jìn)行，直至獲得查找成功或不成功的結(jié)果。 定義一個(gè)字符串?dāng)?shù)組，分別通過(guò)for及foreach語(yǔ)句進(jìn)行循環(huán)遍歷輸出？ string[] stuInfo = new String []{ "武大","華科","理工"}; //使用for語(yǔ)句循環(huán)遍歷數(shù)組             for (int temp = 0; temp < stuInfo.Length; temp++)             {                 Console.WriteLine(string.Format("The Value is {0}！", stuInfo[temp]));             }             Console.WriteLine("".PadLeft(20,'='));             //使用foreach語(yǔ)句循環(huán)遍歷數(shù)組             foreach (string strTemp in stuInfo)             {                 Console.WriteLine(string.Format("The Value of stuInfo is {0}！",strTemp));             } 簡(jiǎn)述隊(duì)列的內(nèi)部組成結(jié)構(gòu)？ 隊(duì)列同現(xiàn)實(shí)生活中到食堂排隊(duì)買飯相仿，新來(lái)的成員總是要加入到隊(duì)伍的尾部，每次離開的成員總是處于隊(duì)頭的。所以，與棧結(jié)構(gòu)不一樣，隊(duì)列操作時(shí)是按照先進(jìn)先出的原則進(jìn)行的。因此，隊(duì)列又被稱為先進(jìn)先出(First In First Out)的線性表，簡(jiǎn)稱FIFO線性表。 選擇排序：它是從數(shù)組的開始處開始，把第一個(gè)元素的值與數(shù)組中其他元素逐個(gè)進(jìn)行比較，然后把最小的元素放置到第0個(gè)位置上，接著再?gòu)牡?/span>1個(gè)元素開始再次進(jìn)行如上操作，直到條件終止。 簡(jiǎn)答敘述散列結(jié)構(gòu)實(shí)現(xiàn)的原理？ 散列的思想是把自身單元內(nèi)的每一個(gè)鍵都存儲(chǔ)到數(shù)組內(nèi)，但是，由于鍵的數(shù)量是有可能無(wú)限多的，而數(shù)組的大小的范圍是有限的，所以，散列函數(shù)會(huì)盡可能平均地分不到數(shù)組的單元內(nèi)。 簡(jiǎn)述插入排序?qū)崿F(xiàn)原理及執(zhí)行過(guò)程? 每一數(shù)據(jù)比較都將一個(gè)待排序的數(shù)據(jù)元素，按照其關(guān)鍵字的大小，插入到已經(jīng)排序的數(shù)據(jù)序列中，使插入后的數(shù)據(jù)序列仍然是有序的，直到全部數(shù)據(jù)序列元素插入完畢為止。 簡(jiǎn)述二叉樹的存儲(chǔ)結(jié)構(gòu)? 二叉樹的存儲(chǔ)結(jié)構(gòu)常見的有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，二叉樹的順序存儲(chǔ)結(jié)構(gòu)適用于完全二叉樹，對(duì)完全二叉樹進(jìn)行排序編號(hào)，將編號(hào)為i的結(jié)點(diǎn)存放在數(shù)組下標(biāo)為i-1的位置上。 通過(guò)現(xiàn)實(shí)生活場(chǎng)景描述棧和隊(duì)列結(jié)構(gòu)？ 隊(duì)列同現(xiàn)實(shí)生活中到食堂排隊(duì)買飯相仿，新來(lái)的成員總是要加入到隊(duì)伍的尾部，每次離開的成員總是處于隊(duì)頭的。所以，與棧結(jié)構(gòu)不一樣，隊(duì)列操作時(shí)是按照先進(jìn)先出的原則進(jìn)行的。 論述Hashtable是如何避免沖突的？ Hashtable類用來(lái)避免沖突的方法就是桶的思想。桶其實(shí)就是具有相同散列代碼對(duì)象的虛擬組合。如果兩個(gè)鍵具有相同的散列代碼，就把這兩個(gè)鍵放在同一個(gè)桶內(nèi)。否則，把每一個(gè)具有唯一散列代碼的鍵放在其對(duì)應(yīng)的桶內(nèi)。 其中，用于在一個(gè)Hashtable對(duì)象內(nèi)桶的數(shù)量被稱之為負(fù)載系統(tǒng)。它是元素與桶數(shù)量之間的比率值。其初始值為1.0。 如何對(duì)基礎(chǔ)排序算法進(jìn)行時(shí)間排序比較？ 定義一個(gè)類，該類里面通過(guò)時(shí)間函數(shù)分別對(duì)基礎(chǔ)排序算法的冒泡、排序及插入排序進(jìn)行比較，比較過(guò)程中通過(guò)循環(huán)增加比較項(xiàng)，以此來(lái)得到比較結(jié)構(gòu)。 當(dāng)我們利用string類定義一個(gè)對(duì)象后，如果對(duì)它進(jìn)行修改操作，在這個(gè)過(guò)程中，會(huì)產(chǎn)生新的字符串嗎？請(qǐng)闡明原理？ 當(dāng)我們利用string類定義一個(gè)對(duì)象后，如果對(duì)它進(jìn)行修改操作，在這個(gè)過(guò)程中，會(huì)產(chǎn)生新的字符串，因?yàn)樽址哪J(rèn)操作情況下，會(huì)通過(guò)產(chǎn)生新的字符串來(lái)代表操作后的字符串值。 可變字符串是如何確保在操作字符串的過(guò)程中可變的？請(qǐng)?jiān)敿?xì)描述。 StringBuilder類表達(dá)的值為可變字符序列的類似字符串的對(duì)象。之所以說(shuō)它定義的值是可變的，是因?yàn)樵谕ㄟ^(guò)追加、移除、替換或插入字符等操作后而創(chuàng)建的新字符串我們可以繼續(xù)對(duì)它進(jìn)行修改。StringBuilder 的容量是實(shí)例在任何給定時(shí)間可存儲(chǔ)的最大字符數(shù)，并且大于或等于實(shí)例值的字符串表示形式的長(zhǎng)度。容量可通過(guò) Capacity 屬性來(lái)增加或減少。 編寫一個(gè)IPAddress類，該類用于存儲(chǔ)IP地址信息，其中IP地址按照降序順序排列。 定義一個(gè)IPAddress類，類里面包含存儲(chǔ)IP的屬性和操作方法，字典類型Hahtable的每一個(gè)數(shù)據(jù)項(xiàng)保存一個(gè)IPAddress對(duì)象即可。 簡(jiǎn)述二叉樹的概念？ 二叉樹是n個(gè)結(jié)點(diǎn)組成的有限集合。n=0時(shí)稱為空二叉樹；n>0時(shí)，二叉樹由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為左子樹和右子樹的子二叉樹構(gòu)成。 什么是生成樹？ 如果圖T是無(wú)向圖G的生成子圖，且T是樹，則圖T稱為圖G的生成樹。那么，圖G的生成樹T包含G中的所有結(jié)點(diǎn)和盡可能少的邊。任意一個(gè)連通圖都至少有一棵生成樹。 什么是最小生成樹？ 設(shè)G是一個(gè)連通的帶權(quán)圖，w(e)為邊e上的權(quán)，T為G的生成樹，T中各邊權(quán)之和稱為生成樹T的權(quán)，也稱為生成樹的代價(jià)。權(quán)最小的生成樹稱為最小生成樹或最小代價(jià)生成樹。 什么是歸并排序算法？ 將數(shù)據(jù)初始序列看成是由n個(gè)長(zhǎng)度為1的已排序子序列組成。反復(fù)將兩個(gè)子序列合并成一個(gè)已排序的序列。重復(fù)直到合并成一個(gè)序列時(shí)，排序完成。