數(shù)據結構復習提綱

復習提綱第一章數(shù)據結構概述基本概念與術語數(shù)據：數(shù)據是用來描述現(xiàn)實世界的文字，字符，圖像，聲音，以及能夠輸入到計算機中并能被計算機處理的符號。數(shù)據元素：數(shù)據元素是數(shù)據的基本單位，是數(shù)據這個集合中的個體，也稱之為元素，結點，頂點記錄。（補充：一個數(shù)據元素可由若干個數(shù)據項組成。數(shù)據項是數(shù)據的不可分割的最小單位。）數(shù)據對象：數(shù)據對象是具有相同性質的數(shù)據元素的集合，是數(shù)據的一個子集。（有時候也叫做屬性。）數(shù)據結構：數(shù)據結構是相互之間存在一種或多種特定關系的數(shù)據元素的集合。（1） 數(shù)據的邏輯結構：數(shù)據的邏輯結構是指數(shù)據元素之間存在的固有邏輯關系，常稱為數(shù)據結構。數(shù)據的邏輯結構是從數(shù)據元素之間存在的邏輯關系上描述數(shù)據與數(shù)據的存儲無關，是獨立于計算機的。數(shù)據的邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。依據數(shù)據元素之間的關系，可以把數(shù)據的邏輯結構分成以下幾種：集合：數(shù)據中的數(shù)據元素之間除了“同屬于一個集合“的關系以夕卜，沒有其他關系。線性結構：結構中的數(shù)據元素之間存在“一對一“的關系。若結構為非空集合，則除了第一個元素之外，和最后一個元素之外，其他每個元素都只有一個直接前驅和一個直接后繼。樹形結構：結構中的數(shù)據元素之間存在“一對多“的關系。若數(shù)據為非空集，則除了第一個元素（根）之外，其它每個數(shù)據元素都只有一個直接前驅，以及多個或零個直接后繼。圖狀結構：結構中的數(shù)據元素存在“多對多”的關系。若結構為非空集，折每個數(shù)據可有多個（或零個）直接后繼。（2） 數(shù)據的存儲結構：數(shù)據元素及其關系在計算機內的表示稱為數(shù)據的存儲結構。想要計算機處理數(shù)據，就必須把數(shù)據的邏輯結構映射為數(shù)據的存儲結構。邏輯結構可以映射為以下兩種存儲結構：順序存儲結構：把邏輯上相鄰的數(shù)據元素存儲在物理位置也相鄰的存儲單元中，借助元素在存儲器中的相對位置來表示數(shù)據之間的邏輯關系。鏈式存儲結構：借助指針表達數(shù)據元素之間的邏輯關系。不要求邏輯上相鄰的數(shù)據元素物理位置上也相鄰。5.時間復雜度分析：1.常量階：算法的時間復雜度與問題規(guī)模n無關系T(n)=O(1)線性階：算法的時間復雜度與問題規(guī)模n成線性關系T(n)=O(n)平方階和立方階：一般為循環(huán)的嵌套，循環(huán)體最后條件為i++時間復雜度的大小比較：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)算法與程序：1、 輸入：有零個或多個輸入2、 輸出：有一個或多個輸出3、 有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個指令序列的執(zhí)行在有限的時間內結束。(程序與算法的區(qū)別在于，程序不需要有有窮性)4、 確定性：算法中的每一個步驟都必須是確定的，而不應當含糊、模棱兩可。沒有歧義。5、 可行性：算法中的每一個步驟都應當能被有效的執(zhí)行，并得到確定的結果。算法設計的準則：1、 正確性(達到預期效果，滿足問題需求)2、 健壯性(能處理合法數(shù)據，也能對不合法的數(shù)據作出反應，不會產生不可預期的后果)3、 可讀性(要求算法易于理解，便于分析)4、 可修改可擴展性5、 高效率(較好的時空性能)1、 名詞解釋：數(shù)據結構、二元組數(shù)據結構就是相互之間存在一種或多種特定關系的數(shù)據元素的集合。二元組就是一種用來表示某個數(shù)據對象以及各個元素之間關系的有限集合。2、 根據數(shù)據元素之間關系的不同，數(shù)據的邏輯結構可以分為集合、線性結構、樹形結構和圖狀結構四種類型。3、 常見的數(shù)據存儲結構一般有兩種類型，它們分別是順序存儲結構、鏈式存儲結構4、 以下說法中，正確的是(D)數(shù)據元素是數(shù)據這個集合中的個體數(shù)據元素均由數(shù)據項組成數(shù)據項是數(shù)據的基本單位數(shù)據元素是數(shù)據的最小單位以下有關抽象數(shù)據類型的描述中，正確的是(B抽象數(shù)據類型是一個值的集合抽象數(shù)據類型是數(shù)據的邏輯結構及操作的組合抽象數(shù)據類型的操作可以沒有操作結果抽象數(shù)據類型只能夠用C語言來描述在一般情況下，一個算法的時間復雜度是問題規(guī)模的函數(shù)7.常見時間復雜度有：常數(shù)階O(1)、線性階O(n)、對數(shù)階O(log2n)、平方階。(”2)、指數(shù)階0(25)。通常認為，具有常數(shù)階量級的算法是好算法，而具有指數(shù)階量級的算法是差算法。第二章線性表順序表結構線性表的順序存儲是指在內存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱為順序表。2.單鏈表鏈表結點結構線性表中的數(shù)據元素可以用任意的一組存儲單元來存儲，用指針表示邏輯關系邏輯相鄰的兩元素的存儲空間可以是不連續(xù)的。結點遍歷鏈表操作算法：初始化、插入、輸出、刪除1、 線性表中，第一個元素沒有直接前驅，最后一個元素沒有直接后驅。2、 在一個單鏈表中，若p所指結點是q所指結點的前驅結點，則刪除結點q的操作語句為P->next=q->next;free(q);3、 在長度為N的順序表仲，插入一個新元素平均需要移動表中N/2個元素，刪除一個元素平均需要移動(N-1)/2個元素。4、 若線性表的主要操作是在最后一個元素之后插入一個元素或刪除最后一個元素，則采用數(shù)序表存儲結構最節(jié)省運算時間。5、 已知順序表中每個元素占用3個存儲單元，第13個元素的存儲地址為336,則順序表的首地址為300

6、設有一帶頭結點單鏈表L,請編寫該單鏈表的初始化，插入、輸出和刪除函數(shù)。(函數(shù)名自定義)結點定義：typedefintdatatype; 〃結點數(shù)據類型，假設為inttypedefstructnode{ 〃結點結構datatypedata;structnode*next;}Lnode,*pointer;〃結點類型，結點指針類型typedefpointerlklist;〃單鏈表類型，即頭指針類型初始化函數(shù)：lklistinitlist(){pointerhead;head=newnode;head->next=NULL;returnhead;}插入函數(shù)：intinsert(lklisthead,datatypex,inti){pointerq,s;q=get(head,i-1);//找第i-1個點if(q==NULL) 〃無第/T點，即/<1或i>n+1時{cout<<”非法插入位置!\n”;return0;}s=newnode; 〃生成新結點s->data=x;s->next=q->next;〃新點的后繼是原第i個點q->next=s; 〃原第i-1個點的后繼是新點return1; 〃插入成功}刪除函數(shù)：intdelete(lklisthead,inti){pointerp,q;q=get(head,i-1); 〃找待刪點的直接前趨if(q==NULL||q->next==NULL)//即i<1或i>n時{cout<<”非法刪除位置!\n”;return0;}〃保存待刪點地址〃修改前趨的后繼指針〃釋放結點〃刪除成〃保存待刪點地址〃修改前趨的后繼指針〃釋放結點〃刪除成q->next=p->next;deletep;return1;不帶頭結點的單鏈表head為空的判定條件是(A)head=NULLB.head->next=NULLC.head->next=headD.head!=NULL帶頭結點的單鏈表head為空的判定條件是(B)A.head=NULLB.head->next=NULLC.head->next=headD.head!=NULL在一個單鏈表中，若p所指結點不是最后結點，在p之后插入s所指結點，則執(zhí)行(B)A.s->next=p;p->next=s; B.s->next=p->next;p->next=s;C.s->next=p->next;p=s; D.p->next=s;s->next=p;在一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(zhí)行(A)p->next=p->next->next;p=p->next;p->next=p->next->next;p->next=p->nextp=p->next->next從一個具有n個結點的有序單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比較(B)個結點。A.nB.n/2C.(n-1)/2 D.O(nlog2n)給定有n個元素的向量，建立一個有序單鏈表的時間復雜度(BA.O(1)B.O(n) C.O(n2) D.O(ng2n)在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是(B)A.O(1)B.O(n) C.O(n2) D.O(ng2n)在一個單鏈表中刪除q所指結點時，應執(zhí)行如下操作：q=p->next;p->next=(p->next->next);free(q);//這種題目靠一根指針是沒有辦法完成的，必須要借助第二根指針。在一個單鏈表中p所指結點之后插入一個s所指結點時，應執(zhí)行：s->next=(p->next)p->next=(s)操作。對于一個具有n個節(jié)點的單鏈表，在已知所指結點后插入一個新結點的時間復雜度是(O)；在給定值為x的結點后插入一個新結點的時間復雜度是(O(n))。問答題線性表可用順序表或鏈表存儲。試問：⑴兩種存儲表示各有哪些主要優(yōu)缺點?順序表的存儲效率高，存取速度快。但它的空間大小一經定義，在程序整個運行期間不會發(fā)生改變，因此，不易擴充。同時，由于在插入或刪除時，為保持原有次序，平均需要移動一半（或近一半）元素，修改效率不高。鏈接存儲表示的存儲空間一般在程序的運行過程中動態(tài)分配和釋放，且只要存儲器中還有空間，就不會產生存儲溢出的問題。同時在插入和刪除時不需要保持數(shù)據元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動數(shù)據，只需修改它們的鏈接指針，修改效率較高。但存取表中的數(shù)據元素時，只能循鏈順序訪問，因此存取效率不高。（2）若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時，應采用哪種存儲表示？為什么？應采用順序存儲表示。因為順序存儲表示的存取速度快，但修改效率低。若表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取表中的元素，這時采用順序存儲表示較好。第三章棧和隊列棧（1） 棧的結構與定義（2） 順序棧操作算法：入棧、出棧、判斷?？盏龋?） 鏈棧的結構與定義隊列（1） 隊列的定義1、 一個棧的入棧序列為“ABCDE”，則以下不可能的出棧序列是（BA.BCDAE B.EDACB C.BCADE D.AEDCB2、 棧的順序表示中，用TOP表示棧頂元素，那么?？盏臈l件是（DA.TOP==STACKSIZEB.TOP==1C.TOP==0D.TOP==-13、 允許在一端插入，在另一端刪除的線性表稱為隊列。插入的一端為表頭，刪除的一端為表尾。4、 棧的特點是先進后出，隊列的特點是先進先出。5、 對于棧和隊列，無論他們采用順序存儲結構還是鏈式存儲結構，進行插入和刪除操作的時間復雜度都是O（1）。6、 已知鏈棧Q，編寫函數(shù)判斷棧空，如果?？談t進行入棧操作，否則出棧并輸出。（要求判斷?？铡⒊鰲?、入棧用函數(shù)實現(xiàn)）考點1：隊列的編程：考點2：棧的編程：出隊與取隊頭元素的區(qū)別：出隊就是刪除對頭的數(shù)據元素，取隊頭元素是獲取對頭的數(shù)據元素值，不需要刪除。鏈棧與順序棧相比，比較明顯的優(yōu)點是：(D1插入操作比較容易 B.刪除操作比較容易C.不會出現(xiàn)?？盏那闆r D.不會出現(xiàn)棧滿的情況第六章樹和二叉樹樹樹的概念及術語樹：n(〃30)個結點的有限集合。當n=0時，稱為空樹；任意一棵非空樹滿足以下條件：⑴有且僅有一個特定的稱為根的結點；⑵當n>1時，除根結點之外的其余結點被分成m(m>0)個互不相交的有限集合T1,T2,...,Tm，其中每個集合又是一棵樹，并稱為這個根結點的壬樹。結點的度：結點所擁有的子樹的個數(shù)。樹的度：樹中所有結點的度的最大值。葉子結點：度為0的結點，也稱為終端結點。分支結點：度不為0的結點，也稱為非終端結點。孩子、雙親樹中某結點的子樹的根結點稱為這個結點的孩子結點，這個結點稱為它孩子結點的雙親結點；兄弟： 具有同一個雙親的孩子結點互稱為兄弟。路徑：如果樹的結點序列n1,n2,…,nk有如下關系:結點ni是ni+1的雙親(1<=i<k)，則把n1,n2,...,nk稱為一條由n1至nk的路徑；路徑上經過的邊的個數(shù)稱為路徑長度。祖先、子孫：在樹中，如果有一條路徑從結點x到結點y，那么x就稱為y的祖先，而y稱為x的子孫。結點所在層數(shù)：根結點的層數(shù)為1；對其余任何結點，若某結點在第k層，則其孩子結點在第k+1層。樹的深度： 樹中所有結點的最大層數(shù)，也稱高度。層序編號：將樹中結點按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。有序樹、無序樹：如果一棵樹中結點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據結構中討論的一般都是有序樹樹通常有前序(根)遍歷、后序(根)遍歷和層序(次)遍歷三種方式(樹，不是二叉樹，沒中序遍歷。二叉樹二叉樹的定義：二叉樹是n(n30)個結點的有限集合，該集合或者為空集(稱為空二叉樹)，或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上。(滿二叉樹的特點:葉子只能出現(xiàn)在最下一層;只有度為0和度為2的結點。)完全二叉樹：對一棵具有n個結點的二叉樹按層序編號，如果編號為i(1</<n)的結點與同樣深度的滿二叉樹中編號為i的結點在二叉樹中的位置完全相同。(完全二叉樹的特點：1.在滿二叉樹中，從最后一個結點開始，連續(xù)去掉任意個結點，即是一棵完全二叉樹。葉子結點只能出現(xiàn)在最下兩層，且最下層的葉子結點都集中在二叉樹的左部；完全二叉樹中如果有度為1的結點，只可能有一個，且該結點只有左孩子。深度為k的完全二叉樹在k-1層上一定是滿二叉樹。)二叉樹的性質：性質1：二叉樹的第i層上最多有2/-1個結點(i31)。，性質2：一棵深度為k的二叉樹中，最多有2k-1個結點，最少有k個結點。深度為k且具有2k-1個結點的二叉樹一定是滿二叉樹性質3：在一棵二叉樹中，如果葉子結點數(shù)為n0，度為2的結點數(shù)為n2，則有:n0=n2+1。(一個結點的度就是指它放出的射線)，性質4：具有n個結點的完全二叉樹的深度為log2n+1。性質5：對一棵具有n個結點的完全二叉樹中從1開始按層序編號，則對于任意的序號為/(1WiWn)的結點(簡稱為結點i)，有：如果/?>1，則結點/?的雙親結點的序號為i/2；如果i=1，則結點/?是根結點，無雙親結點。如果2iWn，則結點/?的左孩子的序號為2i；如果2i>n，則結點/?無左孩子。如果2/+1Wn，則結點/?的右孩子的序號為2/+1；如果2/+1>n，則結點i無右孩子。二叉樹的遍歷前序遍歷中序遍歷后序遍歷森林(1)森林的遍歷：先序遍歷森林和中序森林先序遍歷：若森林不空，則訪問森林中第一棵樹的根結點；

先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中（除第一棵樹之外）其余樹構成的森林。（約定：依次從左至右對森林中的每一棵樹進行先根遍歷。）后序遍歷：若森林不空，則后序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結點；后序遍歷森林中（除第一棵樹之外）其余樹構成的森林。（約定：依次從左至右對森林中的每一棵樹進行后根遍歷。）（2）森林：m（m30）棵互不相交的樹的集合。二叉搜索樹（1）二叉搜索樹的定義及構建：哈夫曼樹（1） 哈夫曼樹的基本概念：哈夫曼樹：給定一組具有確定權值的葉子結點，帶權路徑長度最小的二叉樹。（2） 哈夫曼樹的特點：權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。只有度為0（葉子結點）和度為2（分支結點）的結點，不存在度為1的結點.（3） 哈夫曼樹的構造算法思想及構造過程（7森林與哈夫曼編碼1、 已知一棵完全二叉樹有47個結點，則該二叉樹有（）個葉子結點。A.6B.12C.24 D.482、 已知遍歷一棵二叉樹的前序序列ABCDEFG和中序序列CBEDAFG，那么是下面哪棵AB樹（C）

AB3、如下圖所示的一棵二叉樹進行遍歷，得到的遍歷序列是CADREFB，則該遍歷序列是哪種遍歷（3、如下圖所示的一棵二叉樹進行遍歷，得到的遍歷序列是CADREFB，則該遍歷序列是哪種遍歷（B）的結果。A.前序遍歷B.中序遍歷 C.后序遍歷D.層次遍歷4、 完全二叉樹必須滿足的條件為：:一棵具有n個結點的二叉樹，它的結構與滿二叉樹的前n個結點的的結構相同。5、 哈夫曼樹不存在度為1的結點。6、有5個帶權結點，其權值分別為2,5,3,7,11，根據哈夫曼算法構建該樹，并計算該樹的帶權路徑長度。（構建哈夫曼樹，很簡單，從小開始，計算相加，然后把所有葉子結點乘以等級數(shù)字然后相加。也即是：帶權路徑長度=葉結點的權值*路徑長度）8、寫出前序和后序遍歷下面森林得到的序列，并將森林轉化成二叉樹前序：abdjcefhi后序：djbaechif前序遍歷和中序遍歷結果相同的二叉樹是（D）。A根結點無左孩子的二叉樹 B根結點無右孩子的二叉樹C所有結點只有左子樹的二叉樹D所有結點只有右子樹的二叉樹用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數(shù)組A[1]~A[n]中，結點A[i]若有左子樹，則左子樹的根結點是(D)。AA[2i-1]BA[2i+1]CA[i/2]DA[2i]對任何一棵二叉樹T,如果其終端結點的個數(shù)為n0,度為2的結點個數(shù)為門2,則(C)。A.n0=n2-1B.n0=n2C.n0=n2+1D.沒有規(guī)律對于完全二叉樹中的任一結點，若其右分支下的子孫的最大層次為h,則其左分支下的子孫的最大層次為(C)。A.h B.h+1C.h或h+1D任意假定一棵度為3的樹的結點個數(shù)為50,則它的最小深度為—如最大深度為_5d。A3 B4 C5 D6試找出分別滿足下列條件的所有二叉樹：⑴前序序列和中序序列相同：只有右子樹⑵中序序列和后序序列相同：只有左子樹⑶前序序列和后序序列相同：只有根，空二叉樹8二叉樹的前序遍歷序列中，任意一個結點均處在其子女結點的前面，這種說法(A)(A)正確(B)錯誤由于二叉樹中每個結點的度最大為2,所以二叉樹是一種特殊的樹，這種說法(B)(A)正確(B)錯誤已知某二叉樹的后序遍歷序列是dabec。中序遍歷序列是debac，它的前序遍歷序列是(D)。(A)acbed(B)decab(C)deabc(D)cedba某二叉樹的前序遍歷結點訪問順序是abdgcefh,中序遍歷的結點訪問順序是dgbaechf,則其后序遍歷的結點訪問順序是(D)。(A)bdgcefha(B)gdbecfha(C)bdgaechf(D)gdbehfca在一非空二叉樹的中序遍歷序列中，根結點的右邊(C)(A)只有右子樹上的所有結點 (B)只有右子樹上的部分結點(C)只有左子樹上的部分結點 (D)只有左子樹上的所有結點15.任何一棵二叉樹的葉子結點在先序、中序和后序遍歷序列中的相對次序(B)(A)不發(fā)生改變 (B)發(fā)生改變(C)不能確定(D)以上都不對第七章圖圖的基本概念：圖的基本術語及推論鄰接矩陣：鄰接矩陣的定義圖的遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷1、 對于上圖所示的有向圖，其深度優(yōu)先搜索遍歷序列為ADFCEB，廣度優(yōu)先搜索遍歷序列為ABCDEF，其拓撲排序序列為A(去掉A發(fā)出的射線)B(去掉B發(fā)出的射線)EDFC。2、 一個具有N個頂點的完全無向圖的邊數(shù)為1/2N(N-1)；一個具有N個頂點的完全有向圖的弧數(shù)為N(N-1)。3、 在有向圖中，總入度、總出度和總邊數(shù)相等。在無向圖中，總度數(shù)是總邊數(shù)的兩倍。4、 一個有16個頂點的無向圖，至少應該有15(n-1)條邊才能確保它是連通圖。5、 給出下面所示有向圖的鄰接矩陣。第九章排序1.直接排序：直接插入、直接選擇算法思想直接插入排序法：依次將待排序數(shù)據元素按其關鍵字的大小插入到有序區(qū)的適當位置上，這就是直接插入排序法。Eg:(25，6，23，11，67，45)25，6，23，11，67，456,25，23，11，67，4523,25,11，67，45(在有序區(qū)內進行比較排序)直接選擇排序法：每趟排序在當前待排序序列中選出關鍵碼最小的記錄，添加到有序序列中。Eg:(70,89,3,8,25,18)先固定第一個元素，然后從剩下的元素中選出最小的，與固定元素比較，交換(3,89,70,8,25,18)(3,8,70,89,25,18)冒泡排序:算法思想：兩兩比較相鄰記錄的關鍵碼，如果反序則交換，直到沒有反序的記錄為止。Eg（98,25,70,36,13,85）首先，我們假設是升序排序，98先出來與25比，若大于25,交換繼續(xù)比較，直到遇見比它大的數(shù)字或者到了最后，停下。詳細參考書本P295筆記3.快速排序：算法思想首先選一個軸值（即比較的基準），通過一趟排序將待排序記錄分割成獨立的兩部分，前一部分記錄的關鍵碼均小于或等于軸值，后一部分記錄的關鍵碼均大于或等于軸值，然后分別對這兩部分重復上述方法，直到整個序列有序?？焖倥判虮容^難以理解，（31， 68，45， 90， 23， 39， 54， 12， 87， 7631<76,指向31的左指針不用移動；指向76的右指針移動87，12。當?shù)搅?2之后，因為31>12，交換，（12，68，45， 90， 23， 39， 54， 31， 87， 76）68與31按照前面的，交換！堆排序：堆的定義首先將待排序的記錄序列構造成一個堆，此時，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調整成堆，然后又將它從堆中移走，這樣又找出了次小的記錄，以此類推，直到堆中只有一個記錄。（大根堆：越往上越大；小根堆：越往下越大）按照給出的數(shù)據的順序由上往下建一個堆；根據題目要求，看是要大根堆還是小根堆；從最下面的支點開始調整；1、 排序方法的穩(wěn)定性是指（BA.排序算法能在規(guī)定的時間內完成排序 B.排序算法能得到確定的結果C.排序算法不允許有相同關鍵字的數(shù)據元素D.以上都不對2、 在對一組關鍵字序列｛70，55，100，15，33，65，50，40，95｝進行直接插入排序時，把65插入到有序序列需要比較（B）次。A.2B.4C.6D.83、 若有關鍵字序列｛42,70,50,33,40,80｝，則利用快速排序的方法，以第一個關鍵字為基準元素得到的一次劃分結果為（A）。（指著第一個原始元素的那個指針成為不動指針，又叫做伴隨指針，另一個指針叫做比較指針）A.40,33,42,50,70,80 B.40,33,80,42,50,70C.40,33,42,80,50,70 D.33,40,42,50,70,804、 以下排序方法中，排序過程中的比較次數(shù)與排序方法無關的是（A）A.直接選擇排序B.快速排序法 C.堆排序 D.直接插入排序5、 以下（B）排序方法是不穩(wěn)定的排序方法A.冒泡 B.堆 C.直接插入 D.二路歸并以下各種排序方法中，最好情況下時間復雜度為O（n）的是（D）。A.歸并排序B.快速排序 C.堆排序D.直接插入排序和冒泡排序在待排序序列局部有序時，效率最高的排序方法是（C）。A.直接選擇排序B.快速排序C.直接插入排序和冒泡排序 D.歸并排序已知