數(shù)據(jù)結(jié)構(gòu)考點(范圍縮小版)

數(shù)據(jù)結(jié)構(gòu)考點第一章緒論什么是數(shù)據(jù)結(jié)構(gòu)？(選擇)在應(yīng)用程序中涉及到各種各樣的數(shù)據(jù)，如何在計算機中組織、存儲、傳遞數(shù)據(jù)，需要討論它們的歸類及它們之間的關(guān)系，從而建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，依此實現(xiàn)軟件功能。綜上，描述這類非數(shù)值計算問題的數(shù)學模型不是數(shù)學方程,而是樹、表和圖之類的數(shù)據(jù)結(jié)構(gòu)。因此從廣義上講，數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實世界實體的數(shù)學模型及其上的操作在計算機中的表示和實現(xiàn)。什么是算法？(選擇)算法定義：為了解決某類問題而規(guī)定的一個有限長的操作序列。第二章線性表線性表的定義(選擇)n(0)個數(shù)據(jù)元素的有限序列，記作q,.叫,a,a+i,...,a)其中卩是表中數(shù)據(jù)元素，n是表長度。 ' ”順序表的定義(選擇)將線性表中的元素相繼存放在一個連續(xù)的存儲空間中。用順序表實現(xiàn)“交并減(算法)集合的“并”運算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i<m;i++){intx=GetData(B,i);〃在B中取一元素intk=Find(A,x); 〃在A中查找它if(k==-1) //若未找到插入它{Insert(A,x,n); n++;}}}集合的“交”運算voidIntersection(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);inti=0;while(i<n){intx=GetData(A,i);//在A中取一元素intk=Find(B,x); 〃在B中查找它if(k==-1){Delete(A,i);n--;}elsei++; 〃未找到在A中刪除它}}鏈表的定義（選擇）鏈表是線性表的鏈接存儲表示。單鏈表是用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。5.單鏈表的結(jié)構(gòu)（選擇）每個元素由結(jié)點（Node）構(gòu)成,,它包括兩個域:數(shù)據(jù)域Data和指針域Link。6.單鏈表的插入刪除（應(yīng)用）帶頭結(jié)點①插入第一種情況：在第一個結(jié)點前插入newnode->link=first;first=newnode;第二種情況：在鏈表中間插入newnode->link=p->link;p->link=newnode；第三種情況：在鏈表末尾插入newnode->link=p->link;？p->link=newnode；若將要插入的位置的節(jié)點命名為P，可簡化為q->link=p->link;P->link=q;②刪除在單鏈表中刪除ai結(jié)點q=P->link;P->link=q->link;deleteq;算法：掃描兩個多項式，若都未檢測完：若當前被檢測項指數(shù)相等，系數(shù)相加。若未變成0，則將結(jié)果加到結(jié)果多項式若當前被檢測項指數(shù)不等，將指數(shù)小者加到結(jié)果多項式。若一個多項式已檢測完，將另一個多項式剩余部分復制到結(jié)果多項式。8.順序表與鏈表的比較(選擇)基于空間的比較存儲分配的方式順序表的存儲空間是靜態(tài)分配的鏈表的存儲空間是動態(tài)分配的存儲密度=結(jié)點數(shù)據(jù)本身所占的存儲量/結(jié)點結(jié)構(gòu)所占的存儲總量順序表的存儲密度=1鏈表的存儲密度＜1基于時間的比較存取方式順序表可以隨機存取，也可以順序存取鏈表是順序存取的插入/刪除時移動元素個數(shù)順序表平均需要移動近一半元素鏈表不需要移動元素，只需要修改指針第三章棧和隊列棧的定義與特點(選擇)定義:是限定僅在表尾進行插入或刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top),另一端稱為棧底(bottom)。特點：后進先出(LIFO)。順序棧的定義(選擇)棧的順序存儲結(jié)構(gòu)，利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，指針top指向棧頂元素在順序棧中的下一個位置，base為棧底指針，指向棧底的位置。順序棧壓入與彈出(不考)①壓入StatusPush(SqStack&S,SElemTypee){//將元素e插入棧成為新的棧頂元素,要考慮上溢情況if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e; //元素e插入棧頂，修改棧頂指針returnOK;}//Push②彈出StatusPop(SqStack&S,SElemType&e){〃若棧不空，則刪除S的棧頂元素，用e返回其值并返回OK，否則返回ERRORif(S.top==S.base)returnERROR;//?？?，返回ERRORe=*--S.top;//刪除棧頂元素，用e返回其值，并修改棧頂指針returnOK;}//Pop鏈棧的定義(選擇)棧的鏈接表示，鏈式棧無棧滿問題，空間可擴充，插入與刪除僅在棧頂處執(zhí)行，鏈式棧的棧頂在鏈頭，適合于多棧操作鏈棧的壓入與彈出(不考)①壓入voidPush(LStack&S,ElemTypee){//在棧頂之上插入元素e為新的棧頂元素p=(LNode*)malloc(sizeof(LNode);//建新的結(jié)點if(!p)exit(1);//存儲分配失敗p->data=e;p->next=S.top;//鏈接到原來的棧頂S.top=p; //移動棧頂指針++S.length; //棧的長度增1}//Push②彈出boolPop(LStack&S,ElemType&e){//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回TRUE；否則返回FALSEif(!S.top)returnFALSE;else{e=S.top->data;//返回棧頂元素q=S.top;S.top=S.top->next;//修改棧頂指針--S.length; //棧的長度減1deleteq; //釋放被刪除的結(jié)點空間returnTRUE;}}//Pop棧的應(yīng)用(選擇)要求能與隊列的應(yīng)用分開數(shù)制轉(zhuǎn)換，行編輯程序，迷宮求解，表達式求值隊列的定義與特點(選擇)定義:只允許在表的一端進行插入，而在另一端刪除元素的線性表。在隊列中，允許插入的一端叫隊尾(rear),允許刪除的一端稱為對頭(front)。特點：先進先出(FIFO)。鏈隊列的定義隊列的鏈式表示。鏈隊列中，有兩個分別指示隊頭和隊尾的指針。鏈式隊列在進隊時無隊滿問題，但有隊空問題。鏈隊列的出隊入隊(不考)入隊StatusEnQueue_L(LinkQueue&Q,QElemType){〃在鏈隊列Q隊尾，插入新的隊尾結(jié)點p=(QueuePtr)malloc(sizeof(QNode));//為新元素e分配結(jié)點空間if(!p)exit(OVERFLOW); //存儲分配失敗p->date=e;p->next=NULL;Q.rear->next=p; //修改隊尾指針，插入新隊尾結(jié)點Q.rear=p;returnOK;}出隊StatusDeQueue_L(LinkQueue&Q,QElemType&e){〃若隊列不空，則刪除Q的隊頭元素結(jié)點，用e返回其值，并返回OK；否則返回ERRORif(Q.front==Q.rear)returnERROR;//若隊列空，返回ERRORp=Q.front->next; //p指向隊頭元素結(jié)點？e=p->data;Q.front->next=p->next;//修改鏈隊列頭結(jié)點指針if(Q.rear==p)Q.rear=Q.front;//對于鏈隊列只有一個元素結(jié)點的情況,要同時修改隊尾指針free（p）;returnOK;}循環(huán)隊列的定義隊滿時再進隊將溢出，解決辦法：將順序隊列臆造為一個環(huán)狀的空間，形成循環(huán)（環(huán)形）隊列。循環(huán)隊列的出隊入隊（應(yīng)用）要求會操作隊頭、隊尾指針加1，可用取模（余數(shù)）運算實現(xiàn)隊頭指針進1:front=（front+1）%maxsize;隊尾指針進1:rear=（rear+1）%maxsize;隊列初始化：front=rear=0;隊空條件：front==rear;隊滿條件：（rear+1）%maxsize==front;fromflnBDCrear空隊列_股情況Vole隊滿（錯誤}rearfront7嚴frontfromflnBDCrear空隊列_股情況Vole隊滿（錯誤}rearfront7嚴frontrear_front限滿（正確）12.隊列的應(yīng)用楊輝三角第四章字符串字符串的定義（選擇）字符串是n（0）個字符的有限序列，記作 S:“c_,c2c3...c"其中，S是串名字，“cy.c"123n 123n是串值，ci是串中字符，n是串的長度。例如,S=“TsinghuaUniversity”串模式匹配定義：在串中尋找子串（第一個字符）在串中的位置

詞匯：在模式匹配中，子串稱為模式，串稱為目標。示例：目標T:"Beijing”，模式P:"jin”，匹配結(jié)果=3①窮舉的模式匹配（應(yīng)用）要求能把演示過程寫出來第1趟Ti=L；ihhhl>a.窮舉的模式P啼bii匹配過程第2趙Tabbabaestt式：血P^'ba第3趟Tab；kl>aPUha腳趟Tsibb';ihii1=3②匹配的改進算法不需要寫過程了，要知道它的復雜度O（m+n）模戒匹配的改進算法：匹酉漲式血￡肚第1趟Tahit1)cbc?€b岔bPi=.I i=7第2趟T汕b?I)€ilbC11￡bAbPiib€i?第3趙T?hahcticiichab第五章數(shù)組與廣義表數(shù)組的定義(選擇)？？行優(yōu)先存放地址計算(應(yīng)用)二維三維給數(shù)組，求地址一維數(shù)組：LOC(i)=LOC(i-1)+l=a+i*l二維數(shù)組：LOC(i,j)=a+(i*m+j)*l設(shè)數(shù)組開始存放位置LOC(0,0)=a,每個元素占用l個存儲單元三維數(shù)組：LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l各維元素個數(shù)為m『m2,m3N維數(shù)組：LOC(i,i,i)=a+(i*m*m*...*m+i*m*m*...*m++i*m+i)*l12n123n234n n-1nn各維元素個數(shù)為m1,m2,m3,…,mn用三元組表表示的稀疏矩陣及其轉(zhuǎn)置與加法（應(yīng)用）給矩陣，求轉(zhuǎn)置非零元素個數(shù)遠遠少于矩陣元素個數(shù)用三元組表表示的稀疏矩陣及其轉(zhuǎn)置til[21【3]行til[21【3]行(row)列(col)值(value)032206151111151723=635394091522811-w卩12p[4ls[^[7時間復雜度(選擇)只要知道復雜度O(nu*tu) nu為矩陣列數(shù)，tu為非零元素個數(shù)第六章樹和二叉樹樹的定義(選擇)樹是由n(n>0)個結(jié)點的有限集合。如果n=0,稱為空樹；如果n>0,則有且僅有一個特定的稱之為根(Root)的結(jié)點，它只有直接后繼，但沒有直接前驅(qū)；當n>1除根以外的其它結(jié)點劃分為m(m>0)個互不相交的有限集T2，…，T其中每個集合本身又是一棵樹，并1 2m且稱為根的子樹(SubTree)。基本術(shù)語結(jié)點：一個數(shù)據(jù)元素及指向其子樹的分支。結(jié)點的度：結(jié)點擁有的子樹個數(shù)。葉結(jié)點：度為零的結(jié)點。子女：結(jié)點子樹的根。兄弟：同一結(jié)點子女。祖先：根到該結(jié)點路徑上的所有結(jié)點。子孫：某結(jié)點為根的子樹上的任意結(jié)點。結(jié)點層次：從根開始，根為第一層，根的子女為第二層，以此類推。樹的深度(高度)：樹中結(jié)點的最大層次數(shù)。有序樹：樹中結(jié)點的子樹由左向右有序。森林：m(m>0)棵互不相交的樹。二叉樹的定義一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。樹的鏈表表示法(選擇)

IChiWdata含兩個指針域的結(jié)點結(jié)構(gòu)LChikl含三個指針域的結(jié)點結(jié)構(gòu)arentIChUdK：IChiWdata含兩個指針域的結(jié)點結(jié)構(gòu)LChikl含三個指針域的結(jié)點結(jié)構(gòu)arentIChUdK：hildntIChUd性質(zhì)：含有n個結(jié)點的二叉鏈表中有n+1個空鏈域IChUd二叉樹的遍歷會寫出順序就可以前序、中序、后續(xù)遍歷二叉樹的算法(不考)計算結(jié)點個數(shù)(遞歸算法)intCount(BinTreeNode*T){if(T==NULL)return0;elsereturn1+Count(T->leftChild)+Count(T->rightChild);}計算葉子結(jié)點個數(shù)intLeaf_Count(BitreeT){//求二叉樹中葉子結(jié)點的數(shù)目if(!T)return0;//空樹沒有葉子elseif(!T->lchild&&!T->rchild)return1;//葉子結(jié)點elsereturnLeaf_Count(T-lchild)+Leaf_Count(T-rchild);//左子樹的葉子數(shù)加上右子樹的葉子數(shù)}計算二叉樹的高度intHeight(BinTreeNode*T){if(T==NULL)return0;else{intm=Height(T->leftChild);intn=Height(T->rightChild));return(m>n)?m+1:n+1;}}非遞歸用棧實現(xiàn)？？（不考）線索二叉樹的定義（選擇）為什么用？利用的是什么？對二叉樹遍歷的過程實質(zhì)上是對一個非線性結(jié)構(gòu)進行線性化的操作.以二叉鏈表為存儲結(jié)構(gòu)時,結(jié)點的左右孩子可以直接找到,但不能直接找到結(jié)點的前驅(qū)和后繼,而結(jié)點的前驅(qū)和后繼只有在遍歷二叉樹的過程中才能得到.用二叉鏈表表示的二叉樹中,n個結(jié)點的二叉樹有n+1個空鏈域，可利用這些空鏈域存儲結(jié)點的前驅(qū)或后繼。9?線索二叉樹的結(jié)點結(jié)構(gòu)（選擇）結(jié)點結(jié)構(gòu)Child 如佃 EtlghHJhildT.efiThreadRighkhrendLeftThread=<kItftthild為左子攻指針T.etrnbiTj^I, LeftChild洵前馳線索Ri^htTliiriidHI,Ri^litChiI<1為右子女指針Ri盟htThread=1,Ri^liKhilJ^后繼摘針10.樹的左二子-右兄弟表示法（應(yīng)用）與下一個一起考33(:10.樹的左二子-右兄弟表示法（應(yīng)用）與下一個一起考33(:/>11結(jié)點結(jié)構(gòu)firstChildncitSiblin胃鏈域滸1個森林與二叉樹的轉(zhuǎn)換樹的遍歷（選擇）知道哪個對應(yīng)哪個將樹化為二叉樹，樹的先根遍歷對應(yīng)二叉樹的前序遍歷，樹的后根遍歷對應(yīng)二叉樹的中序遍歷前序中序遍歷唯一確定一個二叉樹（選擇）知道這個原理就行霍夫曼算法（應(yīng)用）能畫出霍夫曼樹，求WPL⑴由給定的n個權(quán)值｛w0,W],w2,...,wn-i｝，構(gòu)造具有n棵擴充二叉樹的森林F=｛T0,T2,...,T1｝，其中每棵擴充二叉樹Ti只有一個帶權(quán)值w.的根結(jié)點，其左、右子樹均為空。n-i i i（2）重復以下步驟,直到F中僅剩下一棵樹為止：①在F中選取兩棵根結(jié)點的權(quán)值最小的擴充二叉樹, 做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。②在F中刪去這兩棵二叉樹。③把新的二叉樹加入F。第七章圖1.圖的定義(選擇)圖是由頂點集合(vertex)及頂點間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph=(V,E)其中V={x|xe某個數(shù)據(jù)對象}是頂點的有窮非空集合；E1={(x,y)|x,yeV}或E2={<x,y>|x,yeV&&Path(x,y)淇中，E1是頂點之間關(guān)系的有窮集合，也叫做邊(edge)集合，此時的圖稱為無向圖。E2表示從x到y(tǒng)的一條弧，且稱x為弧尾，y為弧頭，這樣的圖稱為有向圖。2.圖的存儲結(jié)構(gòu)(選擇)①鄰接矩陣A.Edge[i][/]={0：若<i,j>eE或(i^j)eE否則②網(wǎng)絡(luò)的鄰接矩陣(有權(quán))’W(i,j),若心j且<i,j>eE或(i,j)eEA.edge[i][j]=<g, 若i豐j且<i,j E或(i,j)電E0, 若i==j2.補一些術(shù)語，如頂點的度，出入度，強連通等(選擇)3.鄰接表是圖的一種鏈式存儲結(jié)構(gòu)?！龌〉慕Y(jié)點結(jié)構(gòu)adjyex；//該弧所指向的頂點的位置nextarc;//指向下一條弧指針info;"該弧相關(guān)信息的指針adjvexnextarcinfo■頂點的結(jié)點結(jié)構(gòu)data;〃頂點信息datafirstarc19fii-starc；"指向第一條依附該頂點的弧19有向圖有鄰接表和逆鄰接表。4.圖的遍歷(應(yīng)用)給圖求dfs或bfs生成樹①深度優(yōu)先前進——- 深度優(yōu)先生成樹|||[退 ②廣度優(yōu)先22ECj3/￡)73V①H）69-廣度優(yōu)先搜索過程廣度優(yōu)先生成樹5.圖的連通性問題（選擇）用深度和廣度都可以最短路徑的算法及三個子問題（應(yīng)用&選擇）應(yīng)用要求掌握下列步驟，選擇要知道Dijkstra解決的是哪個問題初始化：Se{v0};dist[j]eEdge[O][j],j=1,2,n-1;//n為圖中頂點個數(shù)求出最短路徑的長度：dist[k]emin{dist[i]},ieV-S;SeSU{k};修改：dist[i]emin{dist[i],dist[k]+Edge[k][i]},對于每一個ieV-S;④判斷：若S=V,則算法結(jié)束，否則轉(zhuǎn)②。7?利用Prim算法求最小生成樹（應(yīng)用）第九章查找1.有序表的查找折半查找的算法（算法）intSearch_Bin（SSTableST,KeyTypekval）{low=1;high=ST.length;//置區(qū)間初值while(low<=high){mid=(low+high)/2;if(kval==ST.elem[mid].key)returnmid;//找到待查元素elseif(kval<ST.elem[mid].key))high=mid-1;//繼續(xù)在前半?yún)^(qū)間進行查找elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間進行查找}return0;//順序表中不存在待查元素}//Search_Bin時間復雜度O(log2n)2.順序表和有序表的比較（選擇）順序表有序表表的特性無序有序存儲結(jié)構(gòu)順序或鏈式順序插刪操作易于進行需移動兀素ASL的值大小第十章內(nèi)部排序1.排序的定義（選擇）在??上排？（查找表）將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序的序列。排序方法的穩(wěn)定性（選擇）知道那種排序方法是穩(wěn)定的，不穩(wěn)定的如果在對象序列中有兩個對象r[i]和r[j],它們的排序碼k[i]==k[j],且在排序之前，對象r[i]排在r[j]前面。如果在排序之后，對象r[i]仍在對象r[j]的前面，則稱這個排序方法是穩(wěn)定的，否則稱這個排序方法是不穩(wěn)定的。內(nèi)排序與外排序（選擇）內(nèi)排序是指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對象個數(shù)太多，不能同時存放在內(nèi)