數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題要點(diǎn)(整理版)-免費(fèi)閱讀
【正文】 第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫做回路或環(huán)頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫簡(jiǎn)單路徑若圖中任意兩個(gè)頂點(diǎn)之間存在路徑（不一定是直接相連），則稱作連通圖2. 鄰接矩陣： Wi,j Vi，Vj ∈VR鄰接矩陣的定義： A[i][j]={ 0 即VR中不存在Vi，Vj時(shí)3. 圖的遍歷 （1）深度優(yōu)先遍歷 步驟：。已知一棵完全二叉樹(shù)有47個(gè)結(jié)點(diǎn)，則該二叉樹(shù)有（C）個(gè)葉子結(jié)點(diǎn)。 （2）如果2i≤n，則結(jié)點(diǎn)i的左孩子的序號(hào)為2i；如果2i＞n，則結(jié)點(diǎn)i無(wú)左孩子。完全二叉樹(shù)的特點(diǎn)：，從最后一個(gè)結(jié)點(diǎn)開(kāi)始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹(shù)。樹(shù)的深度： 樹(shù)中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。（2） 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)。 =m。typedef struct{ int mu,nu,tu。 //元素值 }Triple。一般是給出數(shù)組元素的首元素地址和每個(gè)元素占用的地址空間并組給出多維數(shù)組的維數(shù)，然后要求你求出該數(shù)組中的某個(gè)元素所在的位置。 p=headnext。 pnext=NULL。 e=pdate。 pdate=e。typedef struct{ QueuePtr front。插入的一端為表頭，刪除的一端為表尾。因?yàn)轫樞虼鎯?chǔ)表示的存取速度快，但修改效率低。線性表可用順序表或鏈表存儲(chǔ)。 pnext=pnextnext。 B. snext=pnext。return 0。//生成新結(jié)點(diǎn) 即C語(yǔ)言中的 s=( pointer)malloc(sizeof(Lnode))。//雙向鏈表應(yīng)加上headprevios=NULL。 struct node *next。在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)是q所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則刪除結(jié)點(diǎn)q的操作語(yǔ)句為 Pnext = qnext 。輸出：printf(“%d”,pdata)。通常認(rèn)為，具有常數(shù)階量級(jí)的算法是好算法，而具有指數(shù)階量級(jí)的算法是差算法。 ：：算法的時(shí)間復(fù)雜度與問(wèn)題規(guī)模n無(wú)關(guān)系T(n)=O(1) ：算法的時(shí)間復(fù)雜度與問(wèn)題規(guī)模n成線性關(guān)系T(n)=O(n) ：一般為循環(huán)的嵌套，循環(huán)體最后條件為i++時(shí)間復(fù)雜度的大小比較：O(1) O(log 2 n) O(n ) O(n log 2 n) O(n2) O(n3) O(2 n )O(n!)O(n n)：（1）算法的5個(gè)特性 輸入：有零個(gè)或多個(gè)輸入 輸出：有一個(gè)或多個(gè)輸出有窮性：要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個(gè)指令序列的執(zhí)行在有限的時(shí)間內(nèi)結(jié)束。若數(shù)據(jù)為非空集，則除了第一個(gè)元素（根）之外，其它 每個(gè)數(shù)據(jù)元素都只有一個(gè)直接前驅(qū)，以及多個(gè)或零個(gè) 直接后繼。（有時(shí)候也叫做屬性。 （補(bǔ)充：一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一對(duì)一“的關(guān)系。邏輯結(jié)構(gòu)可以映射為以下兩種存儲(chǔ)結(jié)構(gòu)：：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置也相鄰的存儲(chǔ)單元中，借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)之間的邏輯關(guān)系。二元組就是一種用來(lái)表示某個(gè)數(shù)據(jù)對(duì)象以及各個(gè)元素之間關(guān)系的有限集合。（2） 鏈表操作算法：初始化、插入、輸出、刪除、遍歷初始化：p=(struct student *)malloc(sizeof(struct student))。p。（第n個(gè)元素的地址即首地址+(n1)*每個(gè)元素的存儲(chǔ)空間，如a[12]（第13個(gè)元素）的地址=a[0]+12*3）設(shè)有一帶頭結(jié)點(diǎn)單鏈表L，請(qǐng)編寫(xiě)該單鏈表的初始化，插入、輸出和刪除函數(shù)。//這是C++做法 //head=( pointer)malloc(sizeof(Lnode))。 //這是C++做法，即C語(yǔ)言中的 printf(“非法插入位置!\n”)。 //插入成功}：（C語(yǔ)言中需要把head轉(zhuǎn)化為全局變量才能實(shí)現(xiàn)此程序）int delete(lklist head,int i) { pointer p,q。 return 1。 snext=p。//這種題目靠一根指針是沒(méi)有辦法完成的，必須要借助第二根指針。同時(shí)在插入和刪除時(shí)不需要保持?jǐn)?shù)據(jù)元素原來(lái)的物理順序，只需要保持原來(lái)的邏輯順序，因此不必移動(dòng)數(shù)據(jù)，只需修改它們的鏈接指針，修改效率較高。 //棧頂指針 struct list *base。，比較明顯的優(yōu)點(diǎn)是：（D） 考點(diǎn)1：隊(duì)列的編程：結(jié)構(gòu)：typedef struct QNode{ int date。 return (Q)。 }出隊(duì)：LinkQueue DeQueue(LinkQueue Q){ int e。 return (Q)。 pnext=head。}第四章 串 （不是重點(diǎn)內(nèi)容）：x=’abc’。掌握將稀疏矩陣的三元組或二元組向十字鏈表進(jìn)行轉(zhuǎn)換的算法。 //元素行下標(biāo)及列下標(biāo) int e。m,amp。 //開(kāi)辟行列頭指針組
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1