㈠ 為什麼我用單向鏈表寫的快速排序這么慢
的確是很慢,因為鏈表是順序訪問,如果想快就改成雙向鏈表或者用順序存儲
㈡ 順序存儲結構和鏈式存儲結構優缺點
順序存儲結構和鏈式存儲結構的區別
鏈表存儲結構的內存地址不一定是連續的,但順序存儲結構的內存地址一定是連續的;
鏈式存儲適用於在較頻繁地插入、刪除、更新元素時,而順序存儲結構適用於頻繁查詢時使用。
順序存儲結構和鏈式存儲結構的優缺點:
空間上
順序比鏈式節約空間。是因為鏈式結構每一個節點都有一個指針存儲域。
存儲操作上:
順序支持隨機存取,方便操作
插入和刪除上:
鏈式的要比順序的方便(因為插入的話順序表也很方便,問題是順序表的插入要執行更大的空間復雜度,包括一個從表頭索引以及索引後的元素後移,而鏈表是索引後,插入就完成了)
例如:當你在字典中查詢一個字母j的時候,你可以選擇兩種方式,第一,順序查詢,從第一頁依次查找直到查詢到j。第二,索引查詢,從字典的索引中,直接查出j的頁數,直接找頁數,或許是比順序查詢最快的。
㈢ 計算機二級office理論知識點
2017年計算機二級office理論知識點
計算機網路就是由大量獨立的、但相互連接起來的計算機來共同完成計算機任務。下面是我整理的關於計算機二級office理論知識點,歡迎大家參考!
1.1演算法
1.演算法的基本概念
(1)概念:演算法是指一系列解決問題的清晰指令。
(2)4個基本特徵:可行性、確定性、有窮性、擁有足夠的情報。
(3)兩種基本要素:對數據對象的運算和操作、演算法的控制結構(運算和操作時問的順序)。
(4)設計的基本方法:列舉法、歸納法、遞推法、遞歸法、減半遞推技術和回溯法。
2.演算法的復雜度
(1)演算法的時間復雜度:執行演算法所需要的計算工作量。
(2)演算法的空間復雜度:執行演算法所需的內存空間。
1.2數據結構的基本概念
數據結構指相互有關聯的數據元素的集合,即數據的組織形式。其中邏輯結構反映數據元素之間邏輯關系;存儲結構為數據的邏輯結構在計算機存儲空間中的存放形式,有順序存儲、鏈式存儲、索引存儲和散列存儲4種方式。
數據結構按各元素之間前後件關系的復雜度可劃分為:
(1)線性結構:有且只有一個根節點,且每個節點最多有一個直接前驅和一個直接後繼的非空數據結構。
(2)非線性結構:不滿足線性結構的數據結構。
1.3線性表及其順序存儲結構
1.線性表的基本概念
線性結構又稱線性表,線性表是最簡單也是最常用的一種數據結構。
2.線性表的順序存儲結構
元素所佔的存儲空間必須連續。
元素在存儲空間的位置是按邏輯順序存放的。
3.線性表的插入運算
在第i個元素之前插入一個新元素的步驟如下:
步驟一:把原來第n個節點至第i個節點依次往後移一個元素位置。
步驟二:把新節點放在第i個位置上。
步驟三:修正線性表的節點個數。
在最壞情況下,即插入元素在第一個位置,線性表中所有元素均需要移動。
4.線性表的刪除運算
刪除第i個位置的元素的步驟如下:
步驟一:把第i個元素之後不包括第i個元素的n-i個元素依次前移一個位置;
步驟二:修正線性表的結點個數。
1.4棧和隊列
1.棧及其基本運算
(1)基本概念:棧是一種特殊的線性表,其插入運算與刪除運算都只在線性表的一端進行,也被稱為「先進後出」表或「後進先出」表。
棧頂:允許插入與刪除的一端。
棧底:棧頂的另一端。
空棧:棧中沒有元素的棧。
(2)特點。
棧頂元素是最後插入和最早被刪除的元素。
棧底元素是最早插入和最後被刪除的元素。
棧有記憶作用。
在順序存儲結構下,棧的插入和刪除運算不需移動表中其他數據元素。
棧頂指針top動態反映了棧中元素的變化情況
(3)順序存儲和運算:入棧運算、退棧運算和讀棧頂運算。
2.隊列及其基本運算
(1)基本概念:隊列是指允許在一端進行插入,在另一端進行刪除的.線性表,又稱「先進先出」的線性表。
隊尾:允許插入的一端,用尾指針指向隊尾元素。
排頭:允許刪除的一端,用頭指針指向頭元素的前一位置。
(2)循環隊列及其運算。
所謂循環隊列,就是將隊列存儲空間的最後一個位置繞到第一個位置,形成邏輯上的環狀空間。
入隊運算是指在循環隊列的隊尾加入一個新元素。
當循環隊列非空(s=1)且隊尾指針等於隊頭指針時,說明循環隊列已滿,不能進行人隊運算,這種情況稱為「上溢」。
退隊運算是指在循環隊列的隊頭位置退出一個元素並賦給指定的變數。首先將隊頭指針進一,然後將排頭指針指向的元素賦給指定的變數。當循環隊列為空(s=0)時,不能進行退隊運算,這種情況稱為「下溢」。
1.5線性鏈表
在定義的鏈表中,若只含有一個指針域來存放下一個元素地址,稱這樣的鏈表為單鏈表或線性鏈表。
在鏈式存儲方式中,要求每個結點由兩部分組成:一部分用於存放數據元素值,稱為數據域;另一部分用於存放指針,稱為指針域。其中指針用於指向該結點的前一個或後一個結點(即前件或後件)。
1.6樹和二叉樹
1.樹的基本概念
樹是簡單的非線性結構,樹中有且僅有一個沒有前驅的節點稱為「根」,其餘節點分成m個互不相交的有限集合T1,T2,…,T}mm,每個集合又是一棵樹,稱T1,T2,…,T}mm為根結點的子樹。
父節點:每一個節點只有一個前件,無前件的節點只有一個,稱為樹的根結點(簡稱樹的根)。
子節點:每~個節點可以後多個後件,無後件的節點稱為葉子節點。
樹的度:所有節點最大的度。
樹的深度:樹的最大層次。
2.二叉樹的定義及其基本性質
(1)二叉樹的定義:二叉樹是一種非線性結構,是有限的節點集合,該集合為空(空二叉樹)或由一個根節點及兩棵互不相交的左右二叉子樹組成。可分為滿二叉樹和完全二叉樹,其中滿二叉樹一定是完全二叉樹,但完全二叉樹不一定是滿二叉樹。二叉樹具有如下兩個特點:
二叉樹可為空,空的二叉樹無節點,非空二叉樹有且只有一個根結點;
每個節點最多可有兩棵子樹,稱為左子樹和右子樹。
(2)二叉樹的基本性質。
性質1:在二叉樹的第k層上至多有2k-1個結點(k≥1)。
性質2:深度為m的二叉樹至多有2m-1個結點。
性質3:對任何一棵二叉樹,度為0的結點(即葉子結點)總是比度為2的結點多一個。
性質4:具有n個結點的完全二叉樹的深度至少為[log2n]+1,其中[log2n]表示log2n的整數部分。
3.滿二叉樹與完全二叉樹
(1)滿二叉樹:滿二叉樹是指這樣的一種二叉樹:除最後一層外,每一層上的所有結點都有兩個子結點。滿二叉樹在其第i層上有2i-1個結點。
從上面滿二叉樹定義可知,二叉樹的每一層上的結點數必須都達到最大,否則就不是滿二叉樹。深度為m的滿二叉樹有2m-1個結點。
(2)完全二叉樹:完全二叉樹是指這樣的二叉樹:除最後一層外,每一層上的結點數均達到最大值;在最後一層上只缺少右邊的若干結點。
如果—棵具有n個結點的深度為k的二叉樹,它的每—個結點都與深度為k的滿二叉樹中編號為1~n的結點——對應。
3.二叉樹的存儲結構
二叉樹通常採用鏈式存儲結構,存儲節點由數據域和指針域(左指針域和右指針域)組成。二叉樹的鏈式存儲結構也稱二叉鏈表,對滿二叉樹和完全二叉樹可按層次進行順序存儲。
4.二叉樹的遍歷
二叉樹的遍歷是指不重復地訪問二叉樹中所有節點,主要指非空二叉樹,對於空二叉樹則結束返回。二叉樹的遍歷包括前序遍歷、中序遍歷和後序遍歷。
(1)前序遍歷。
前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中,首先訪問根結點,然後遍歷左子樹,最後遍歷右子樹;並且,在遍歷左右子樹時,仍然先訪問根結點,然後遍歷左子樹,最後遍歷右子樹。前序遍歷描述為:若二叉樹為空,則執行空操作;否則①訪問根結點;②前序遍歷左子樹;③前序遍歷右子樹。
(2)中序遍歷。
中序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中,首先遍歷左子樹,然後訪問根結點,最後遍歷右子樹;並且,在遍歷左、右子樹時,仍然先遍歷左子樹,然後訪問根結點,最後遍歷右子樹。中序遍歷描述為:若二叉樹為空,則執行空操作;否則①中序遍歷左子樹;②訪問根結點;③中序遍歷右子樹。
(3)後序遍歷。
後序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中,首先遍歷左子樹,然後遍歷右子樹,最後訪問根結點,並且,在遍歷左、右子樹時,仍然先遍歷左子樹,然後遍歷右子樹,最後訪問根結點。後序遍歷描述為:若二叉樹為空,則執行空操作;否則①後序遍歷左子樹;②後序遍歷右子樹;③訪問根結點。
1.7查找技術
(1)順序查找:在線性表中查找指定的元素。
(2)最壞情況下,最後一個元素才是要找的元素,則需要與線性表中所有元素比較,比較次數為n。
(2)二分查找:二分查找也稱折半查找,它是一種高效率的查找方法。但二分查找有條件限制,它要求表必須用順序存儲結構,且表中元素必須按關鍵字有序(升序或降序均可)排列。對長度為n的有序線性表,在最壞情況下,二分查找法只需比較log2n次。
1.8排序技術
(1)交換類排序法。
冒泡排序:通過對待排序序列從後向前或從前向後,依次比較相鄰元素的排序碼,若發現逆序則交換,使較大的元素逐漸從前部移向後部或較小的元素逐漸從後部移向前部,直到所有元素有序為止。在最壞情況下,對長度為n的線性表排序,冒泡排序需要比較的次數為n(n-1)/2。
快速排序:是迄今為止所有內排序演算法中速度最快的一種。它的基本思想是:任取待排序序列中的某個元素作為基準(一般取第一個元素),通過一趟排序,將待排元素分為左右兩個子序列,左子序列元索的排序碼均小於或等於基準元素的排序碼,右子序列的排序碼則大於基準元素的排序碼,然後分別對兩個子序列繼續進行排序,直至整個序列有序。最壞情況下,即每次劃分,只得到一個序列,時間效率為O(n2)。
(2)插人類排序法。
簡單插入排序法:把n個待排序的元素看成為一個有序表和一個無序表,開始時有序表中只包含一個元素,無序表中包含有n-1個元素,排序過程中每次從無序表中取出第一個元素,把它的排序碼依次與有序表元素的排序碼進行比較,將它插入到有序表中的適當位置,使之成為新的有序表。在最壞情況下,即初始排序序列是逆序的情況下,比較次數為n(n-1)/2,移動次數為n(n-1)/2。
希爾排序法:先將整個待排元素序列分割成若干個子序列(由相隔某個「增量」的元素組成的)分別進行直接插入排序。待整個序列中的元素基本有序(增量足夠小)時,再對全體元素進行一次直接插入排序。
(3)選擇類排序法。
簡單選擇排序法:掃描整個線性表。從中選出最小的元素。將它交換到表的最前面;然後對剩下的子表採用同樣的方法,直到子表空為止。最壞情況下需要比較n(n-1)/2次。
堆排序的方法:首先將一個無序序列建成堆;然後將堆頂元素(序列中的最大項)與堆中最後一個元素交換(最大項應該在序列的最後)。不考慮已經換到最後的那個元素,只考慮前n-1個元素構成的子序列,將該子序列調整為堆。反復做步驟②,直到剩下的子序列空為止。在最壞情況下,堆排序法需要比較的次數為0(nlog2n)
;㈣ 鏈式存儲序列能用冒泡排序嗎
可以啊,冒泡排序就是和鄰居逆序時交換記錄或者關鍵字,在單鏈表上可以完成下沉的冒泡排序,雙鏈表則還可以完成上浮的冒泡排序
㈤ 1. 用c語言編寫順序存儲結構下的順序查找法和鏈式存儲結構下的順序查找法。
是啊!而且非常重要它在筆試中佔30%!!!
這是我找到的一些資料:第一章 數據結構與演算法
1.1 演算法
1、演算法是指解題方案的准確而完整的描述。換句話說,演算法是對特定問題求解步驟的一種描述。
*:演算法不等於程序,也不等於計算方法。程序的編制不可能優於演算法的設計。
2、演算法的基本特徵
(1)可行性。針對實際問題而設計的演算法,執行後能夠得到滿意的結果。
(2)確定性。每一條指令的含義明確,無二義性。並且在任何條件下,演算法只有唯一的一條執行路徑,即相同的輸入只能得出相同的輸出。
(3)有窮性。演算法必須在有限的時間內完成。有兩重含義,一是演算法中的操作步驟為有限個,二是每個步驟都能在有限時間內完成。
(4)擁有足夠的情報。演算法中各種運算總是要施加到各個運算對象上,而這些運算對象又可能具有某種初始狀態,這就是演算法執行的起點或依據。因此,一個演算法執行的結果總是與輸入的初始數據有關,不同的輸入將會有不同的結果輸出。當輸入不夠或輸入錯誤時,演算法將無法執行或執行有錯。一般說來,當演算法擁有足夠的情報時,此演算法才是有效的;而當提供的情報不夠時,演算法可能無效。
*:綜上所述,所謂演算法,是一組嚴謹地定義運算順序的規則,並且每一個規則都是有效的,且是明確的,此順序將在有限的次數下終止。
3、演算法復雜度主要包括時間復雜度和空間復雜度。
(1)演算法時間復雜度是指執行演算法所需要的計算工作量,可以用執行演算法的過程中所需基本運算的執行次數來度量。
(2)演算法空間復雜度是指執行這個演算法所需要的內存空間。
1.2 數據結構的基本概念
1、數據結構是指相互有關聯的數據元素的集合。
2、數據結構主要研究和討論以下三個方面的問題:
(1)數據集合中各數據元素之間所固有的邏輯關系,即數據的邏輯結構。
數據的邏輯結構包含:1)表示數據元素的信息;2)表示各數據元素之間的前後件關系。
(2)在對數據進行處理時,各數據元素在計算機中的存儲關系,即數據的存儲結構。
數據的存儲結構有順序、鏈接、索引等。
1)順序存儲。它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里,結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構。
2)鏈接存儲。它不要求邏輯上相鄰的結點在物理位置上亦相鄰,結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構。
3)索引存儲:除建立存儲結點信息外,還建立附加的索引表來標識結點的地址。
*:數據的邏輯結構反映數據元素之間的邏輯關系,數據的存儲結構(也稱數據的物理結構)是數據的邏輯結構在計算機存儲空間中的存放形式。同一種邏輯結構的數據可以採用不同的存儲結構,但影響數據處理效率。
(3)對各種數據結構進行的運算。
3、數據結構的圖形表示
一個數據結構除了用二元關系表示外,還可以直觀地用圖形表示。在數據結構的圖形表示中,對於數據集合D中的每一個數據元素用中間標有元素值的方框表示,一般稱之為數據結點,並簡稱為結點;為了進一步表示各數據元素之間的前後件關系,對於關系R中的每一個二元組,用一條有向線段從前件結點指向後件結點。
4、數據結構分為兩大類型:線性結構和非線性結構。
(1)線性結構(非空的數據結構)條件:1)有且只有一個根結點;2)每一個結點最多有一個前件,也最多有一個後件。
*:常見的線性結構有線性表、棧、隊列和線性鏈表等。
(2)非線性結構:不滿足線性結構條件的數據結構。
*:常見的非線性結構有樹、二叉樹和圖等。
1.3 線性表及其順序存儲結構
1、線性表由一組數據元素構成,數據元素的位置只取決於自己的序號,元素之間的相對位置是線性的。線性表是由n(n≥0)個數據元素組成的一個有限序列,表中的每一個數據元素,除了第一個外,有且只有一個前件,除了最後一個外,有且只有一個後件。線性表中數據元素的個數稱為線性表的長度。線性表可以為空表。
*:線性表是一種存儲結構,它的存儲方式:順序和鏈式。
2、線性表的順序存儲結構具有兩個基本特點:(1)線性表中所有元素所佔的存儲空間是連續的;(2)線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
*:由此可以看出,在線性表的順序存儲結構中,其前後件兩個元素在存儲空間中是緊鄰的,且前件元素一定存儲在後件元素的前面,可以通過計算機直接確定第i個結點的存儲地址。
3、順序表的插入、刪除運算(學吧學吧獨家稿件)
(1)順序表的插入運算:在一般情況下,要在第i(1≤i≤n)個元素之前插入一個新元素時,首先要從最後一個(即第n個)元素開始,直到第i個元素之間共n-i+1個元素依次向後移動一個位置,移動結束後,第i個位置就被空出,然後將新元素插入到第i項。插入結束後,線性表的長度就增加了1。
*:順性表的插入運算時需要移動元素,在等概率情況下,平均需要移動n/2個元素。
(2)順序表的刪除運算:在一般情況下,要刪除第i(1≤i≤n)個元素時,則要從第i+1個元素開始,直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結束後,線性表的長度就減小了1。
*:進行順性表的刪除運算時也需要移動元素,在等概率情況下,平均需要移動(n-1)/2個元素。插入、刪除運算不方便。
1.4 棧和隊列
1、棧及其基本運算(學吧學吧獨家稿件)
棧是限定在一端進行插入與刪除運算的線性表。
在棧中,允許插入與刪除的一端稱為棧頂,不允許插入與刪除的另一端稱為棧底。棧頂元素總是最後被插入的元素,棧底元素總是最先被插入的元素。即棧是按照「先進後出」或「後進先出」的原則組織數據的。
棧具有記憶作用。
棧的基本運算:1)插入元素稱為入棧運算;2)刪除元素稱為退棧運算;3)讀棧頂元素是將棧頂元素賦給一個指定的變數,此時指針無變化。
棧的存儲方式和線性表類似,也有兩種,即順序棧和鏈式棧。
2、隊列及其基本運算
隊列是指允許在一端(隊尾)進入插入,而在另一端(隊頭)進行刪除的線性表。尾指針(Rear)指向隊尾元素,頭指針(front)指向排頭元素的前一個位置(隊頭)。
隊列是「先進先出」或「後進後出」的線性表。
隊列運算包括:1)入隊運算:從隊尾插入一個元素;2)退隊運算:從隊頭刪除一個元素。
循環隊列及其運算:所謂循環隊列,就是將隊列存儲空間的最後一個位置繞到第一個位置,形成邏輯上的環狀空間,供隊列循環使用。在循環隊列中,用隊尾指針rear指向隊列中的隊尾元素,用排頭指針front指向排頭元素的前一個位置,因此,從頭指針front指向的後一個位置直到隊尾指針rear指向的位置之間,所有的元素均為隊列中的元素。
*:循環隊列中元素的個數=rear-front。
1.5 線性鏈表(學吧學吧獨家稿件)
1、線性表順序存儲的缺點(學吧學吧獨家稿件):(1)插入或刪除的運算效率很低。在順序存儲的線性表中,插入或刪除數據元素時需要移動大量的數據元素;(2)線性表的順序存儲結構下,線性表的存儲空間不便於擴充;(3)線性表的順序存儲結構不便於對存儲空間的動態分配。
2、線性鏈表:線性表的鏈式存儲結構稱為線性鏈表,是一種物理存儲單元上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接來實現的。因此,在鏈式存儲方式中,每個結點由兩部分組成:一部分用於存放數據元素的值,稱為數據域;另一部分用於存放指針,稱為指針域,用於指向該結點的前一個或後一個結點(即前件或後件),如下圖所示:
線性鏈表分為單鏈表、雙向鏈表和循環鏈表三種類型。
在單鏈表中,每一個結點只有一個指針域,由這個指針只能找到其後件結點,而不能找到其前件結點。因此,在某些應用中,對於線性鏈表中的每個結點設置兩個指針,一個稱為左指針,指向其前件結點;另一個稱為右指針,指向其後件結點,這種鏈表稱為雙向鏈表,如下圖所示:
3、線性鏈表的基本運算
(1)在線性鏈表中包含指定元素的結點之前插入一個新元素。
*:在線性鏈表中插入元素時,不需要移動數據元素,只需要修改相關結點指針即可,也不會出現「上溢」現象(學吧學吧獨家稿件)。
(2)在線性鏈表中刪除包含指定元素的結點。
*:在線性鏈表中刪除元素時,也不需要移動數據元素,只需要修改相關結點指針即可。
(3)將兩個線性鏈表按要求合並成一個線性鏈表。
(4)將一個線性鏈表按要求進行分解。
(5)逆轉線性鏈表。
(6)復制線性鏈表。
(7)線性鏈表的排序。
(8)線性鏈表的查找。
*:線性鏈表不能隨機存取。
4、循環鏈表及其基本運算
在線性鏈表中,其插入與刪除的運算雖然比較方便,但還存在一個問題,在運算過程中對於空表和對第一個結點的處理必須單獨考慮,使空表與非空表的運算不統一。為了克服線性鏈表的這個缺點,可以採用另一種鏈接方式,即循環鏈表。
與前面所討論的線性鏈表相比,循環鏈表具有以下兩個特點:1)在鏈表中增加了一個表頭結點,其數據域為任意或者根據需要來設置,指針域指向線性表的第一個元素的結點,而循環鏈表的頭指針指向表頭結點;2)循環鏈表中最後一個結點的指針域不是空,而是指向表頭結點。即在循環鏈表中,所有結點的指針構成了一個環狀鏈。
下圖a是一個非空的循環鏈表,圖b是一個空的循環鏈表:
循環鏈表的優點主要體現在兩個方面:一是在循環鏈表中,只要指出表中任何一個結點的位置,就可以從它出發訪問到表中其他所有的結點,而線性單鏈表做不到這一點;二是由於在循環鏈表中設置了一個表頭結點,在任何情況下,循環鏈表中至少有一個結點存在,從而使空表與非空表的運算統一。
*:循環鏈表是在單鏈表的基礎上增加了一個表頭結點,其插入和刪除運算與單鏈表相同。但它可以從任一結點出發來訪問表中其他所有結點,並實現空表與非空表的運算的統一。
1.6 樹與二叉樹(學吧學吧獨家稿件)
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種數據結構中,所有數據元素之間的關系具有明顯的層次特性。
在樹結構中,每一個結點只有一個前件,稱為父結點。沒有前件的結點只有一個,稱為樹的根結點,簡稱樹的根。每一個結點可以有多個後件,稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中,一個結點所擁有的後件的個數稱為該結點的度,所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
(1)什麼是二叉樹
二叉樹是一種很有用的非線性結構,它具有以下兩個特點:1)非空二叉樹只有一個根結點;2)每一個結點最多有兩棵子樹,且分別稱為該結點的左子樹與右子樹。
*:根據二叉樹的概念可知,二叉樹的度可以為0(葉結點)、1(只有一棵子樹)或2(有2棵子樹)。
(2)二叉樹的基本性質(學吧學吧獨家稿件)
性質1 在二叉樹的第k層上,最多有 個結點。
性質2 深度為m的二叉樹最多有個 個結點。
性質3 在任意一棵二叉樹中,度數為0的結點(即葉子結點)總比度為2的結點多一個。性質4 具有n個結點的二叉樹,其深度至少為 ,其中 表示取 的整數部分。
3、滿二叉樹與完全二叉樹
滿二叉樹:除最後一層外,每一層上的所有結點都有兩個子結點。
完全二叉樹:除最後一層外,每一層上的結點數均達到最大值;在最後一層上只缺少右邊的若干結點。
*:根據完全二叉樹的定義可得出:度為1的結點的個數為0或1。
下圖a表示的是滿二叉樹,下圖b表示的是完全二叉樹:
完全二叉樹還具有如下兩個特性:
性質5 具有n個結點的完全二叉樹深度為 。
性質6 設完全二叉樹共有n個結點,如果從根結點開始,按層序(每一層從左到右)用自然數1,2,…,n給結點進行編號,則對於編號為k(k=1,2,…,n)的結點有以下結論:
①若k=1,則該結點為根結點,它沒有父結點;若k>1,則該結點的父結點的編號為INT(k/2)。
②若2k≤n,則編號為k的左子結點編號為2k;否則該結點無左子結點(顯然也沒有右子結點)。
③若2k+1≤n,則編號為k的右子結點編號為2k+1;否則該結點無右子結點。
4、二叉樹的存儲結構
在計算機中,二叉樹通常採用鏈式存儲結構。
與線性鏈表類似,用於存儲二叉樹中各元素的存儲結點也由兩部分組成:數據域和指針域。但在二叉樹中,由於每一個元素可以有兩個後件(即兩個子結點),因此,用於存儲二叉樹的存儲結點的指針域有兩個:一個用於指向該結點的左子結點的存儲地址,稱為左指針域;另一個用於指向該結點的右子結點的存儲地址,稱為右指針域。
*:一般二叉樹通常採用鏈式存儲結構,對於滿二叉樹與完全二叉樹來說,可以按層序進行順序存儲。
5、二叉樹的遍歷(學吧學吧獨家稿件)
二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種:
(1)前序遍歷(DLR):若二叉樹為空,則結束返回。否則:首先訪問根結點,然後遍歷左子樹,最後遍歷右子樹;並且,在遍歷左右子樹時,仍然先訪問根結點,然後遍歷左子樹,最後遍歷右子樹。
(2)中序遍歷(LDR):若二叉樹為空,則結束返回。否則:首先遍歷左子樹,然後訪問根結點,最後遍歷右子樹;並且,在遍歷左、右子樹時,仍然先遍歷左子樹,然後訪問根結點,最後遍歷右子樹。
(3)後序遍歷(LRD):若二叉樹為空,則結束返回。否則:首先遍歷左子樹,然後遍歷右子樹,最後訪問根結點,並且,在遍歷左、右子樹時,仍然先遍歷左子樹,然後遍歷右子樹,最後訪問根結點。
1.7 查找技術(學吧學吧獨家稿件)
查找:根據給定的某個值,在查找表中確定一個其關鍵字等於給定值的數據元素。
查找結果:(查找成功:找到;查找不成功:沒找到。)
平均查找長度:查找過程中關鍵字和給定值比較的平均次數。
1、順序查找
基本思想:從表中的第一個元素開始,將給定的值與表中逐個元素的關鍵字進行比較,直到兩者相符,查到所要找的元素為止。否則就是表中沒有要找的元素,查找不成功。
在平均情況下,利用順序查找法在線性表中查找一個元素,大約要與線性表中一半的元素進行比較,最壞情況下需要比較n次。
順序查找一個具有n個元素的線性表,其平均復雜度為O(n)。
下列兩種情況下只能採用順序查找:
1)如果線性表是無序表(即表中的元素是無序的),則不管是順序存儲結構還是鏈式存儲結構,都只能用順序查找。
2)即使是有序線性表,如果採用鏈式存儲結構,也只能用順序查找。
2、二分法查找
思想:先確定待查找記錄所在的范圍,然後逐步縮小范圍,直到找到或確認找不到該記錄為止。
前提:必須在具有順序存儲結構的有序表中進行。
查找過程:
1)若中間項(中間項mid=(n-1)/2,mid的值四捨五入取整)的值等於x,則說明已查到;
2)若x小於中間項的值,則在線性表的前半部分查找;
3)若x大於中間項的值,則在線性表的後半部分查找。
特點:比順序查找方法效率高。最壞的情況下,需要比較log2n次。
*:二分法查找只適用於順序存儲的線性表,且表中元素必須按關鍵字有序(升序)排列。對於無序線性表和線性表的鏈式存儲結構只能用順序查找。在長度為n的有序線性表中進行二分法查找,其時間復雜度為O(log2n)。
1.8 排序技術(學吧學吧獨家稿件)
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列,即是將無序的記錄序列調整為有序記錄序列的一種操作。
1、交換類排序法(方法:冒泡排序,快速排序)。
2、插入類排序法(方法:簡單插入排序,希爾排序)。
3、選擇類排序法(方法:簡單選擇排序,堆排序)。
總結:各種排序法比較:
本章應考點撥:本章內容在筆試中會出現5-6個題目,是公共基礎知識部分出題量比較多的一章,所佔分值也比較大,約10分。
㈥ 計算機二級選擇題干貨(五)——數據結構和演算法
1、線性表、棧和隊列等數據結構所表達和處理的數據以線性結構為組織形式。棧是一種特殊的線性表,這種線性表只能在固定的一端進行插入和刪除操作,允許插入和刪除的一端稱為棧頂,另一端稱為棧底。一個新元素只能從棧頂一端進入,刪除時,只能刪除棧頂的元素,即剛剛被插入的元素。所以棧又稱後進先出表(Last In First Out);隊列可看作是插入在一端進行,刪除在另一端進行的線性表,允許插入的一端稱為隊尾,允許刪除的一端稱為隊頭。在隊列中,只能刪除隊頭元素,隊列的最後一個元素一定是最新入隊的元素。因此隊列又稱先進先出表(First In First Out)。
2、棧和隊列都是一種特殊的操作受限的線性表,只允許在端點處進行插入和刪除。二者的區別是:棧只允許在表的一端進行插入或刪除操作,是一種"後進先出"的線性表;而隊列只允許在表的一端進行插入操作,在另一端進行刪除操作,是一種"先進先出"的線性表。
3、棧是一種特殊的線性表,這種線性表只能在固定的一端進行插入和刪除操作,允許插入和刪除的一端稱為棧頂,另一端稱為棧底。一個新元素只能從棧頂一端進入,刪除時,只能刪除棧頂的元素,即剛剛被插入的元素。所以棧又稱先進後出表(FILO-First In Last Out)。線性表可以順序存儲,也可以鏈式存儲,而棧是一種線性表,也可以採用鏈式存儲結構。
4、棧和隊列都是一種特殊的操作受限的線性表,只允許在端點處進行插入和刪除。二者的區別是:棧只允許在表的一端進行插入或刪除操作,是一種"後進先出"的線性表;而隊列只允許在表的一端進行插入操作,在另一端進行刪除操作,是一種"先進先出"的線性表。
5、在棧中,棧底指針不變,棧中元素隨棧頂指針的變化而動態變化
top=0表示棧空,top=50表示棧滿。入棧操作首先將top加1,然後將新元素插入到top指針指向的位置;退棧操作首先將top指針指向的元素賦給一個指定的變數,然後將top減1。棧頂指針top動態反映了棧中元素的變化情況。
6、棧是一種先進後出的線性表,棧實際上也是線性表,只不過是一種特殊的線性表。隊列是指允許在一端進行插入、而在另一端進行刪除的線性表,隊列是一種"先進先出"或"後進後出"的線性表
隊列是指允許在一端進行插入、而在另一端進行刪除的線性表。它又稱為"先進先出"或"後進後出"的線性表,體現了"先來先服務"的原則。
7、帶鏈的隊列也是線性鏈表,在線性鏈表中指向線性表中的第一個結點的指針稱為頭指針,頭指針為NULL或0時稱為空表,指向隊尾元素的指針稱為尾指針。隊列在隊尾插入元素,稱為入隊運算;在隊頭刪除元素,稱為退隊運算。帶鏈隊列在開辟存儲空間時,可以按照存儲空間地址增大的方向開辟,也可以按照存儲空間地址減少的方向開辟。
8、所謂循環隊列,就是將隊列存儲空間的最後一個位置繞到第1個位置,形成邏輯上的環狀空間,供隊列循環使用。所以循環隊列還是屬於線性結構。循環隊列的頭指針front指向隊列的第一個元素的前一位置,隊尾指針rear指向隊列的最後一個元素,循環隊列的動態變化需要頭尾指針共同反映循環隊列的長度是:(sq.rear-sq.front+maxsize)%maxsize,所以循環隊列的長度是由隊頭和隊尾指針共同決定的
在循環隊列中,用隊尾指針rear指向隊列中的隊尾元素,用排頭指針front指向排頭元素的前一個位置。
循環隊列主要有兩種基本運算:入隊運算與退隊運算。每進行一次入隊運算,隊尾指針就進一。每進行一次退隊運算,排頭指針就進一。當rear或front的值等於隊列的長度+1時,就將rear或front的值置為1。一般情況下,rear大於front,因為入隊的元素肯定比出隊的元素多。特殊的情況是rear到達數組的上限之後又從數組的低端開始,此時,rear是小於front的。
循環隊列就是將隊列存儲空間的最後一個位置繞到第一個位置,形成邏輯上的環狀空間,供隊列循環使用。在實際應用中,隊列的順序存儲結構一般採用循環隊列的形式。因此,循環隊列不是隊列的一種鏈式存儲結構。循環隊列是一種存儲結構,因此循環隊列是一種物理結構,而不是邏輯結構。循環隊列是隊列的順序存儲結構,因此循環隊列是線性結構。
9、循環隊列不同於循環鏈表,循環隊列是順序存儲結構,循環鏈表是鏈式存儲結構。雙向鏈表是鏈式存儲結構,其中每個結點都有左指針和右指針,不同於二叉樹結點的左子樹指針和右子樹指針。非線性結構和線性結構是數據的邏輯結構,順序和鏈式是數據的存儲結構,例如二叉樹是非線性結構,也可以按照層序進行順序存儲。
10、非線性結構的邏輯特徵是一個結點元素可能對應多個直接前驅和多個後驅。常見的非線性結構有:樹(二叉樹等),圖(網等)。
11、由於二叉樹的存儲結構中每一個存儲結點有兩個指針域,因此,二叉樹的鏈式存儲結構也稱為二叉鏈表,二叉鏈表屬於非線性結構。
12、遍歷是指不重復的訪問所有結點。線性單鏈表每個結點只有一個指針域,由這個指針只能找到後件結點,但不能找到前件結點。雙向鏈表中的每個結點設置兩個指針,左指針指向其前件結點,右指針指向其後件結點。循環鏈表中增加了一個表頭結點,循環鏈表中的所有結點的指針構成了一個環狀鏈。二叉鏈表即二叉樹的鏈式存儲結構,每個存儲結點有兩個指針域,左指針域指向該結點的左子結點的存儲地址,右指針域指向該結點的右子結點的存儲地址。
13、線性表的順序存儲結構具有兩個基本特點:(1)線性表中所有元素所佔的存儲空間是連續的;(2)線性表中各元素在存儲空間中是按邏輯順序依次存放的。
14、循環鏈表具有以下兩個特點:(1)在循環鏈表中增加了一個表頭結點,其數據域為任意或者根據需要來設置,指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。(2)循環鏈表中最後一個結點的指針域不是空,而是指向表頭結點。即在循環鏈表中,所有結點的指針構成了一個環狀鏈。
15、在循環鏈表中,只要指出表中任何一個結點的位置,就可以從它出發訪問到表中其他所有的結點,而線性單鏈表做不到這一點。
16、根據二叉樹的性質:二叉樹第i(i≥1)層上至多有2i-1個結點。
17、所謂滿二叉樹是指這樣的一種二叉樹:除最後一層外,每層上的所有結點都有兩個子結點。這就是說,在滿二叉樹中,每一層上的結點數都達到最大值,即在滿二叉樹的第K層上有2K-1個結點,且深度為m的滿二叉樹有2m個結點。
18、在任意一顆樹中,結點總數=總分支數目+1
19、二叉樹的性質:在任意一棵二叉樹中,度為0的結點(即葉子結點)總是比度為2的結點多一個。本題中度為2的結點數為n,故葉子結點數為n+1個。
二叉樹的性質:在任意一棵二叉樹中,度為0的結點(即葉子結點)總是比度為2的結點多一個。
20、在用完全二叉樹表示堆,樹中所有非葉子結點值均不小於其左右子樹的根結點值,因此,堆頂元素必為序列的n個元素中的最大項。
21、作為一個演算法,一般應具有以下幾個基本特徵。
可行性
確定性
有窮性
擁有足夠的情報
22、計算機演算法是指解題方案的准確而完整的描述
演算法的有窮性,是指演算法必須在有限的時間內做完,即演算法必須能在執行有限個步驟之後終止。
23、希爾排序法的基本思想是:將整個無序序列分割成若干小的子序列分別進行插入排序。所以希爾排序法屬於插入類排序,但它對簡單插入排序做了很大的改進。
24、快速排序的基本思想是,通過一趟排序將待排序記錄分割成獨立的兩部分,其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小,再分別對這兩部分記錄繼續進行排序,以達到整個序列有序;插入排序的基本操作是指將無序序列中的各元素依次插入到已經有序的線性表中,從而得到一個新的序列;選擇排序的基本思想是:掃描整個線性表,從中選出最小的元素,將它交換到表的最前面(這是它應有的位置),然後對剩下的子表採用同樣的方法,直到表空為止;歸並排序是將兩個或兩個以上的有序表組合成一個新的有序表。
25、在單鏈表中,增加頭結點的目的是______。
頭結點不僅標識了表中首結點的位置,而且根據單鏈表(包含頭結點)的結構,只要掌握了表頭,就能夠訪問整個鏈表,因此增加頭結點目的是為了便於運算的實現。
26、演算法分析是指對一個演算法的運行時間和佔用空間做定量的分析,一般計算出相應的數量級,常用時間復雜度和空間復雜度表示。分析演算法的目的就是要降低演算法的時間復雜度和空間復雜度,提高演算法的執行效率。
27、演算法是指解題方案的准確而完整的描述。但演算法不等於程序,也不等於計算方法。當然,程序也可以作為演算法的一種描述,但程序通常還需要考慮很多與方法和分析無關的細節問題,這是因為在編寫程序時要受到計算機系統運行環境的限制。通常,程序的編制不可能優於演算法的設計。作為一個演算法,一般應具有可行性、確定性、有窮性、擁有足夠情報四個基本特徵。因此設計演算法時不僅僅要考慮結果的可靠性,即不僅考慮演算法結果的可行性,還要考慮步驟的確定性,時間和步驟的有窮性等。因此,演算法是一組嚴謹地定義運算順序的規則,並且每一個規則都是有效的,且是明確的,此順序將在有限的次數下終止。
28、一個演算法通常由兩種基本要素組成:一是對數據對象的運算和操作,二是演算法的控制結構。因此設計演算法時不僅需要考慮數據結構的設計,還要考慮數據的操作和運算及各操作之間的執行順序。
29、在有向圖中,若任意兩個頂點都連通,則稱該圖是強連通圖,這樣的有向圖的形狀是環狀,因而至少應有n條邊。
30、當數據表A中每個元素距其最終位置不遠,說明數據表A按關鍵字值基本有序,在待排序序列基本有序的情況下,採用插入排序所用時間最少。
31、數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構(也稱數據的物理結構)。
32、假設線性表的長度為n,則在最壞情況下,冒泡排序需要經過n/2遍的從前往後掃描和n/2遍的從後往前掃描,需要比較次數為n(n-1)/2。快速排序法的最壞情況比較次數也是n(n-1)/2
(1)冒泡排序法:是一種最簡單的交換類排序法,它是通過相鄰數據元素的交換逐步將線性表變成有序。假設線性表的長度為n,則在最壞情況下,冒泡排序需要經過n/2遍的從前往後的掃描和n/2遍的從後往前的掃描,需要比較的次數為n(n-1)/2次。
(2)簡單插入排序法:在簡單插入排序法中,每一次比較後最多移掉一個逆序,因此,這種排序方法的效率與冒泡排序法相同。在最壞情況下,簡單插入排序需要n(n-1)/2次比較。
(3)簡單選擇排序法:對於長度為n的序列,選擇排序需要掃描n-1遍,每一遍掃描均從剩下的子表中選出最小的元素,然後將該最小的元素與子表中的第一個元素進行交換。簡單選擇排序法在最壞情況下需要比較n(n-1)/2次。
(4)堆排序法:堆排序的方法為:①首先將一個無序序列建成堆。②然後將堆頂元素(序列中的最大項)與堆中最後一個元素交換(最大項應該在序列的最後)。在最壞情況下,堆排序需要比較的次數為。
假設線性表的長度為16,那麼冒泡排序、直接插入排序、簡單選擇排序都需要比較120次,而堆排序需要比較64次。
33、對於長度為n的線性表,在最壞的情況下,快速排序所需要的比較次數為n(n-1)/2;冒泡排序所需要的比較次數為n(n-1)/2;直接插入排序所需要的比較次數為n(n-1)/2;堆排序所需要的比較次數為。
34、在進行順序查找過程中,如果線性表中的第一個元素就是被查找元素,則只需做一次比較就查找成功,查找效率最高;但如果被查找的元素是線性表中的最後一個元素,或者被查找的元素根本就不在線性表中,則為了查找這個元素需要與線性表中所有的元素進行比較,這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找,在最壞情況下需要比較n次。
35、二分法查找只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列(即從小到大,但允許相鄰元素值相等)。
二分法檢索要求線性表結點按關鍵值排序且以順序方式存儲。在查找時,首先與表的中間位置上結點的關鍵值比較,若相等則檢索成功;否則根據比較結果確定下一步在表的前半部分或後半部分繼續進行。二分法檢索的效率比較高,設線性表有n個元素,則最多的檢索次數為大於log2n(2為底數)的最小整數,最少的檢索次數為1。
36、一般來說,一種數據的邏輯結構根據需要可以表示成多種存儲結構,常用的存儲結構有順序、鏈接、索引等存儲結構。而採用不同的存儲結構,其數據處理的效率是不同的。
37、順序存儲結構就是用一組地址連續的存儲單元依次存儲該線性表中的各個元素,鏈式存儲結構中各數據結點的存儲序號是不連續的,並且各結點在存儲空間中的位置關系與邏輯關系也不一致。兩者都可以存儲線性的、有序的邏輯結構,順序結構使用的是連續物理空間,鏈式結構可以使用零散的物理空間存儲,鏈式結構更靈活,不存在誰節約空間的說法
38、順序存儲結構中,數據元素存放在一組地址連續的存儲單元中,每個數據元素地址可通過公式LOC(ai)=LOC(a1)+(i-1)L計算得到,從而實現了隨機存取。對於鏈式存儲結構,要對某結點進行存取,都得從鏈的頭指針指向的結點開始,這是一種順序存取的存儲結構。
39、鏈式存儲結構克服了順序存儲結構的缺點:它的結點空間可以動態申請和釋放;它的數據元素的邏輯次序靠結點的指針來指示,不需要移動數據元素。故鏈式存儲結構下的線性表便於插入和刪除操作。
40、線性表的順序存儲結構的存儲空間只用於存放結點數據,而鏈式存儲結構的存儲空間不僅要存放結點數據,還要存放數據的指針,所以線性表的鏈式存儲結構所需要的存儲空間一般要多於順序存儲結構
41、在進行順序查找過程中,如果線性表中的第1個元素就是被查找元素,則只需做一次比較就查找成功,查找效率最高;但如果被查找的元素是線性表中的最後一個元素,或者被查找的元素根本就不在線性表中,則為了查找這個元素需要與線性表中所有的元素進行較,這是順序查找的最壞情況。所以對長度為n的線性表進行順序查找,在最壞情況下需要比較n次
42、對於長度為n的有序線性表,在最壞情況下,二分查找只需要比較 次,而順序查找需要比較n次。二分法查找只適用於順序存儲的有序表,如果採用鏈式存儲結構,也只能用順序查找,所以,對長度為n的有序鏈表進行查找,最壞情況下需要的比較次數為n
43、根據數據結構中各數據元素之間前後件關系的復雜程度,一般將數據結構分為兩大類型:線性結構與非線性結構。
44、如果一個非空的數據結構滿足下列兩個條件:(1)有且只有一個根結點;(2)每一個結點最多有一個前件,也最多有一個後件。則稱該數據結構為線性結構,又稱線性表。
45、有一個以上根結點的數據結構肯定是非線性結構,循環鏈表、雙向鏈表是線性結構;線性表、棧與隊列、線性鏈表都是線性結構,而二叉樹是非線性結構。
46、在鏈表中,如果有兩個結點的同一個指針域的值相等,則該鏈表一定是非線性結構
47、線性表的鏈式存儲結構稱為線性鏈表,為了適應線性表的鏈式存儲結構,計算機存儲空間被劃分為一個一個小塊,每一小塊占若干位元組,通常稱這些小塊為存儲結點。每一個存儲結點分為兩部分:一部分用於存儲數據元素的值,稱為數據域;另一部分用於存放下一個數據元素的存儲序號,即指向後件的結點,稱為指針域。在鏈式存儲結構中,存儲數據結構的存儲空間可以不連續,各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致。為了要在線性鏈表中插入一個新元素,首先要給該元素分配一個新結點,以便用於存儲該元素的值,然後將存放新元素值的結點鏈接到線性表中指定的位置。在線性鏈表的插入過程中不發生數據無素移動的現象,只需改變有關結點的指針即可,從而提高了插入的效率。為了在線性鏈表中刪除包含指定元素的結點,首先要在線性鏈表中找到這個結點,然後將要刪除結點放回到可利用棧。在線性鏈表中刪除一個元素後,不需要移動表的數據元素,只需改變被刪元素所在結點的前一個結點的指針域即可。因此,進行插入與刪除時,不需要移動表中的元素。
48、在先左後右的原則下,根據訪問根結點的次序,二叉樹的遍歷可以分為3種:前序遍歷、中序遍歷和後序遍歷。
前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中,首先訪問根結點,然後遍歷左子樹,最後遍歷右子樹;並且遍歷左、右子樹時,仍然先訪問根結點,然後遍歷左子樹,最後遍歷右子樹。
後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中,首先遍歷左子樹,然後遍歷右子樹,最後訪問根結點;並且遍歷左、右子樹時,仍然先遍歷左子樹,然後遍歷右子樹,最後訪問根結點。
二叉樹的中序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中,首先遍歷左子樹,然後訪問根結點,最後遍歷右子樹;並且遍歷左、右子樹時,仍然先遍歷左子樹,然後訪問根結點,最後遍歷右子樹。
49、鏈表有線性鏈表,也有非線性鏈表。線性鏈表和二叉樹鏈表的結點都有兩個指針域,前者是線性結構,後者是非線性結構。線性單鏈表中的結點只有一個指針,葉子結點一般是對樹結構而言,樹結構是非線性結構,不是線性表。
50、演算法的復雜度主要包括時間復雜度和空間復雜度:演算法在運行過程中需輔助存儲空間的大小稱為演算法的空間復雜度;演算法的時間復雜度是指執行演算法所需要的計算工作量,即演算法執行過程中所需要的基本運算次數,為了能夠比較客觀地反映出一個演算法的效率,在度量一個演算法的工作量時,不僅應該與所使用的計算機、程序設計語言以及程序編制者無關,而且還應該與演算法實現過程中的許多細節無關。為此,可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。二者沒有直接關系。
51、一個演算法的空間復雜度,一般是指執行這個演算法所需要的內存空間。一個演算法所佔用的存儲空間包括程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間相對於問題規模來說是常數,則稱該演算法是原地(in place)工作的。
52、我們通常用時間復雜度和空間復雜度來衡量演算法效率,演算法的時間復雜度是指執行演算法所需要的計算工作量;演算法所執行的基本運算次數與問題的規模有關,而一個演算法的空間復雜度,一般是指執行這個演算法所需要的內存空間;一般來說,一種數據的邏輯結構根據需要可以表示成多種存儲結構。
所謂演算法的時間復雜度,是指執行演算法所需要的計算工作量。為了能夠比較客觀地反映出一個演算法的效率,在度量一個演算法的工作量時,不僅應該與所使用的計算機、程序設計語言以及程序編制者無關,而且還應該與演算法實現過程中的許多細節無關。為此,可以用演算法在執行過程中所需基本運算的執行次數來度量演算法的工作量。
53、子程序調用是一種層次關系,子程序調用功能模塊,調用功能模塊的個數也不確定,可以是一個,也可以是多個。二叉樹是一種很有用的非線性結構,二叉樹不同於樹形結構。二叉樹具有以下兩個特點:①非空二叉樹只有一個根結點;②每一個結點最多有兩棵子樹,且分別稱為該結點的左子樹與右子樹。選項D規定每個結點只能有兩個後件。在子程序調用中,調用的功能模塊可以是多個,可以調用超過兩個功能模塊。
54、結構圖的深度表示控制的層數結構圖的深度表示控制的層數
55、數據結構是指反映數據元素之間關系的數據元素集合的表示。更通俗地說,數據結構是指帶有結構的數據元素的集合。所謂結構實際上就是指數據元素之間的前後件關系。線性結構與非線性結構都可以是空的數據結構。一個空的數據結構究竟是屬於線性結構還是屬於非線性結構,還要根據具體情況來確定。如果對該數據結構的運算是按線性結構的規則來處理的,則屬於線性結構;否則屬於非線性結構。
㈦ 鏈式存儲結構和順序存儲結構的區別
區別如下:
1、鏈表存儲結構的內存地址不一定是連續的,但順序存儲結構的內存地址一定是連續的。
2、鏈式存儲適用於在較頻繁地插入、刪除、更新元素是,而順序存儲結構適用於頻繁查詢時使用。
3、順序比鏈式節約空間,是因為鏈式結構每一個節點都有一個指針存儲域。順序支持隨機存取,方便操作。鏈式的要比順序的方便,快捷。
官方一點來說可以使用網路的介紹:順序存儲結構是存儲結構類型中的一種,該結構是把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元中,結點之間的邏輯關系由存儲單元的鄰接關系來體現。
當然不得不說一般這種官方的解釋都是不太適合我的,所以用小甲魚的方式來說這個概念的話,簡單來說就是,用一段連續的地址存放數據元素,數據間的邏輯關系和物理關系相同。
優點1:存儲密度大,空間利用度高,比鏈式存儲節約空間。
優點2:存儲操作上方便操作,順序支持隨機存取,查找會比較容易。
缺點1:插入或者刪除元素時不方便,花費的時間更多。
㈧ 數據結構面試常見問題
數據結構面試常見問題
數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。下面就是我整理的數據結構面試常見問題,一起來看一下吧。
數據結構面試常見問題 篇1
數據結構與演算法,這個部分的內容其實是十分的龐大,要想都覆蓋到不太容易。在校學習階段我們可能需要對每種結構,每種演算法都學習,但是找工作筆試或者面試的時候,要在很短的時間內考察一個人這方面的能力,把每種結構和演算法都問一遍不太現實。所以,實際的情況是,企業一般考察一些看起來很基本的概念和演算法,或者是一些變形,然後讓你去實現。也許看起來簡單,但是如果真讓你在紙上或者是計算機上快速地完成一個演算法,並且設計測試案例,最後跑起來,你就會發現會很難了。這就要求我們要熟悉,並牢固掌握常用的演算法,特別是那些看起來貌似簡單的演算法,正是這些用起來很普遍的演算法,才要求我們能很扎實的掌握,在實際工作中提高工作效率。遇到復雜的演算法,通過分析和扎實的基本功,應該可以很快地進行開發。
閑話少說,下面進入正題。
一.數據結構部分
1.數組和鏈表的區別。(很簡單,但是很常考,記得要回答全面)
C++語言中可以用數組處理一組數據類型相同的數據,但不允許動態定義數組的大小,即在使用數組之前必須確定數組的大小。而在實際應用中,用戶使用數組之前有時無法准確確定數組的大小,只能將數組定義成足夠大小,這樣數組中有些空間可能不被使用,從而造成內存空間的浪費。鏈表是一種常見的數據組織形式,它採用動態分配內存的形式實現。需要時可以用new分配內存空間,不需要時用將已分配的空間釋放,不會造成內存空間的浪費。
從邏輯結構來看:數組必須事先定義固定的長度(元素個數),不能適應數據動態地增減的情況,即數組的大小一旦定義就不能改變。當數據增加時,可能超出原先定義的元素個數;當數據減少時,造成內存浪費;鏈表動態地進行存儲分配,可以適應數據動態地增減的.情況,且可以方便地插入、刪除數據項。(數組中插入、刪除數據項時,需要移動其它數據項)。
從內存存儲來看:(靜態)數組從棧中分配空間(用NEW創建的在堆中), 對於程序員方便快速,但是自由度小;鏈表從堆中分配空間, 自由度大但是申請管理比較麻煩.
1.從訪問方式來看:數組在內存中是連續存儲的,因此,可以利用下標索引進行隨機訪問;鏈表是鏈式存儲結構,在訪問元素的時候只能通過線性的方式由前到後順序訪問,所以訪問效率比數組要低。
2.鏈表的一些操作,如鏈表的反轉,鏈表存在環路的判斷(快慢指針),雙向鏈表,循環鏈表相關操作。
3.隊列(特殊的如優先順序隊列),棧的應用。(比如隊列用在消息隊列,棧用在遞歸調用中)
4.二叉樹的基本操作
二叉樹的三種遍歷方式(前序,中序,後序)及其遞歸和非遞歸實現,三種遍歷方式的主要應用(如後綴表達式等)。相關操作的時間復雜度。
5.字元串相關
整數,浮點數和字元串之間的轉換(atoi,atof,itoa)
字元串拷貝注意異常檢查,比如空指針,字元串重疊,自賦值,字元串結束符'/0'等。
二.演算法部分
1.排序演算法:
排序可以算是最基本的,最常用的演算法,也是筆試面試中最常被考察到的演算法。最基本的冒泡排序,選擇排序,插入排序要可以很快的用代碼實現,這些主要考察你的實際編碼能力。堆排序,歸並排序,快排序,這些演算法需要熟悉主要的思想,和需要注意的細節地方。需要熟悉常用排序演算法的時間和空間復雜度。
各種排序演算法的使用范圍總結:
(1)當數據規模較小的時候,可以用簡單的排序演算法如直接插入排序或直接選擇排序。
(2)當文件的初態已經基本有序時,可以用直接插入排序或冒泡排序。
(3)當數據規模比較大時,應用速度快的排序演算法。可以考慮用快速排序。當記錄隨機分布的時候,快排的平均時間最短,但可能出現最壞的情況,這時候的時間復雜度是O(n^2),且遞歸深度為n,所需的棧空間問O(n)。
(4)堆排序不會出現快排那樣的最壞情況,且堆排序所需的輔助空間比快排要少。但這兩種演算法都不是穩定的,若要求排序時穩定的,可以考慮用歸並排序。
(5)歸並排序可以用於內排序,也可以用於外排序。在外排序時,通常採用多路歸並,並且通過解決長順串的合並,產生長的初始串,提高主機與外設並行能力等措施,以減少訪問外存額次數,提高外排序的效率。
2,查找演算法
能夠熟練寫出或者是上機編碼出二分查找的程序。
3.hash演算法
4.一些演算法設計思想。
貪心演算法,分治演算法,動態規劃演算法,隨機化演算法,回溯演算法等。這些可以根據具體的例子程序來復習。
5.STL
STL(Standard Template Library)是一個C++領域中,用模版技術實現的數據結構和演算法庫,已經包含在了C++標准庫中。其中的vecor,list,stack,queue等結構不僅擁有更強大的功能,還有了更高的安全性。除了數據結構外,STL還包含泛化了的迭代器,和運行在迭代器上的各種實用演算法。這些對於對性能要求不是太高,但又不希望自己從底層實現演算法的應用還是很具有誘惑力的。
數據結構面試常見問題 篇2
1. 什麼是數據結構?
數據結構是數據組織(存儲)和操作進行檢索和訪問的方式。它還定義了不同數據集相互關聯、建立關系和形成演算法的方式。
2. 描述數據結構的類型?
列表:鏈接到先前或/和後續數據項的相關事物的集合。
數組:所有相同的值的集合。
Records:欄位的集合,每個欄位都包含來自單一數據類型的數據。
樹:在分層框架中組織數據的數據結構。這種形式的數據結構遵循數據項插入、刪除和修改的順序。
表格:數據以行和列的形式保存。這些與記錄相當,因為數據的結果或更改反映在整個表中。
3. 什麼是線性數據結構?請舉例
如果數據結構的所有元素或數據項都按順序或線性順序排列,則數據結構是線性的。元素以非分層方式存儲,因此除了列表中的第一個和最後一個元素外,每個項目都有後繼者和前驅者。數組、堆棧、字元串、隊列和鏈表,都屬於線性數據結構。
4. 數據結構有哪些應用?
數值分析、操作系統、人工智慧、編譯器設計、資料庫管理、圖形、統計分析和模擬。
5、文件結構和存儲結構有什麼區別?
區別在於訪問的內存區域。存儲結構是指計算機系統內存中的數據結構,而文件結構是指輔助存儲器中的存儲結構。
6、什麼是多維數組?
多維數組的意思是指三維或者三維以上的數組。 三維數組具有高、寬、深的概念,或者說行、列、層的概念,即數組嵌套數組達到三維及其以上。是最常見的多維數組,由於其可以用來描述三維空間中的位置或狀態而被廣泛使用。
7. 什麼是鏈表數據結構?
這是最常見的數據結構面試問題之一,面試官希望你能給出全面的答案。嘗試盡可能多地解釋,而不是用一句話來完成你的答案!
它是一個線性數據結構或一系列數據對象,其中元素不存儲在相鄰的內存位置。元素使用指針鏈接以形成鏈。每個元素都是一個單獨的對象,稱為節點。每個節點有兩項:數據欄位和對下一個節點的引用。鏈表中的入口點稱為頭。如果列表為空,則頭部為空引用,最後一個節點具有對空的引用。
一個鏈表是一個動態的數據結構,其中節點的數量是不固定的,這樣的例子有擴大和縮小需求的能力。
它適用於以下情況:
我們處理未知數量的對象或不知道列表中有多少項目;
我們需要從列表中進行恆定時間的插入/刪除,就像在時間可預測性至關重要的實時計算中一樣;
不需要隨機訪問任何元素;
該演算法需要一個數據結構,無論對象在內存中的物理地址如何,都需要在其中存儲對象;
我們需要在列表中間插入項目,就像在優先隊列中一樣;
一些實現是堆棧和隊列、圖形、名稱目錄、動態內存分配以及對長整數執行算術運算
8.什麼是雙向鏈表?請舉例
它是鏈表的一種復雜類型(雙端 LL),其中一個節點有兩個鏈接,一個連接到序列中的下一個節點,另一個連接到前一個節點。這允許在兩個方向上遍歷數據元素。
舉例:
帶有下一個和上一個導航按鈕的音樂播放列表
具有 BACK-FORWARD 訪問頁面的瀏覽器緩存
瀏覽器上的撤消功能
9. 為什麼要做演算法分析?
一個問題可以使用多種解決演算法以多種方式解決。演算法分析提供對演算法所需資源的估計,以解決特定的計算問題。還確定了執行所需的時間和空間資源量。
演算法的時間復雜度量化了演算法運行所花費的時間,作為輸入長度的函數。空間復雜度量化了演算法佔用的空間或內存量,以作為輸入長度的函數運行。
;㈨ 試述隊列的鏈式存儲結構和順序存儲結構的優缺點
順序存儲結構是在內存中開辟一個連續的空間用來存儲數據,因此對於內存的需求和苛刻,必須是連續的空間.在數據查找(特別是不按照規律排列的數據),時間復雜度教少.效率高.
鏈式存儲結構是採取連表指針來指示數據的存儲位置,這就可以是在內存中隨意的存儲,沒有必須連續儲存空間的要求,對於內存的要求相對教容易.但是要是是從小到大順序排列的數據,鏈式存儲結構的時間復雜度教小,效率高.但是要是不規則排布的數據一般時間復雜度較高,效率更低