2023年本科數(shù)據(jù)結(jié)構(gòu)本期末綜合練習(xí)

數(shù)據(jù)結(jié)構(gòu)(本）期末綜合練習(xí)期末綜合練習(xí)一一、單項選擇題1.數(shù)據(jù)的物理結(jié)構(gòu)(D)。Ａ．與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)B．僅僅涉及數(shù)據(jù)元素的表達(dá)C.只涉及數(shù)據(jù)元素間關(guān)系的表達(dá)D.涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)2．?dāng)?shù)據(jù)元素是數(shù)據(jù)的基本單位，它（C）。Ａ.只能有一個數(shù)據(jù)項組成B．至少有二個數(shù)據(jù)項組成C.可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成D．至少有一個數(shù)據(jù)項為指針類型３．從ｎ個數(shù)中選取最大元素，（C)。A.基本操作是數(shù)據(jù)元素間的互換B．算法的時間復(fù)雜度是Ｏ(n２)C.算法的時間復(fù)雜度是O（ｎ)D.需要進(jìn)行（n+1）次數(shù)據(jù)元素間的比較4.線性表的順序結(jié)構(gòu)中，(C)。Ａ．邏輯上相鄰的元素在物理位置上不一定相鄰B．?dāng)?shù)據(jù)元素是不能隨機(jī)訪問的Ｃ．邏輯上相鄰的元素在物理位置上也相鄰D．進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高5.以下表中可以隨機(jī)訪問的是（D)。Ａ．單向鏈表B．雙向鏈表C．單向循環(huán)鏈表Ｄ．順序表6．帶頭結(jié)點的單向鏈表為空的判斷條件是(Ｂ）(設(shè)頭指針為head）。A．head==NULLB.head－＞next==NULLＣ．ｈｅaｄ->nｅｘt==headD．ｈeａd!=NＵLL７.設(shè)順序存儲的線性表長度為n,對于刪除操作,設(shè)刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為（A)。A．(n+1)/２B．nC.2nD．n-i8.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在(A）的關(guān)系。A．一對一B.一對多C．多對多D．每一個元素都有一個直接前驅(qū)和一個直接后繼9．設(shè)tｏp是一個鏈棧的棧頂指針,棧中每個結(jié)點由一個數(shù)據(jù)域daｔa和指針域next組成,設(shè)用x接受棧頂元素,則出棧操作為（A)。A.ｘ=top->daｔa;top=toｐ->nｅｘt;B.top＝top-＞next;x=tｏｐ－>ｄａt(yī)a;C.x=ｔｏp－＞next;toｐ=top－＞ｄata;Ｄ.top-＞ｎext＝ｔoｐ;x=tｏp->data;１0.設(shè)順序存儲的線性表長度為n，要刪除第ｉ個元素，按課本的算法,當(dāng)ｉ＝(C）時，移動元素的次數(shù)為3A．3Ｂ.ｎ/2C．ｎ-3Ｄ11.以下說法對的的是(C)。Ａ．隊列是后進(jìn)先出B.棧的特點是后進(jìn)后出C．棧的刪除和插入操作都只能在棧頂進(jìn)行D．隊列的刪除和插入操作都只能在隊頭進(jìn)行１２.以下說法不對的的是(C)。A．棧的特點是后進(jìn)先出Ｂ.隊列的特點是先進(jìn)先出C.棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行D.隊列的插入操作在隊尾進(jìn)行，刪除操作在隊頭進(jìn)行１3.串函數(shù)ＳtrCmｐ(“abA”，”abａ”)的值為（Ｄ)。Ａ．1B．０Ｃ．“abＡａba”Ｄ1４．一個棧的進(jìn)棧序列是ａ,b,c,d,則棧的不也許的出棧序列是(A)。A．a(chǎn)dbｃB．ｂcadC．cbaｄD.dｃｂa１5.設(shè)有一個１2階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中(矩陣A的第一個元素為a1,１,數(shù)組ｂ的下標(biāo)從１開始),則矩陣A中第４行的元素在數(shù)組b中的下標(biāo)i一定有（A)。A．7≤i≤10B．１１≤i≤15C．９≤i≤14D．6≤i≤16.已知一個圖的邊數(shù)為m,則該圖的所有頂點的度數(shù)之和為(A)。Ａ.2mB.mC.2ｍ+１Ｄ.m/２17.設(shè)有一個帶頭結(jié)點的鏈隊列,隊列中每個結(jié)點由一個數(shù)據(jù)域datａ和指針域next組成,froｎt和ｒeａr分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作,用x保存出隊元素的值，p為指向結(jié)點類型的指針，可執(zhí)行如下操作:p=ｆｒｏｎｔ-＞ｎｅxt;x=p->data;然后執(zhí)行（B)。Ａ.fｒont＝p-＞ｎeｘｔ;B.fronｔ->next=p->ｎext；C.front=p;D.front->neｘｔ=ｐ;18．以下說法不對的的是（D)。A.連通圖Ｇ一定存在生成樹B．連通圖Ｇ的生成樹中一定包含G的所有頂點C．連通圖G的生成樹中不一定包含G的所有邊Ｄ．連通圖G的生成樹可以是不連通的１9．散列查找的原理是（A）。A．在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應(yīng)關(guān)系B.按待查記錄的關(guān)鍵字有序的順序方式存儲C．按關(guān)鍵字值的比較進(jìn)行查找D.基于二分查找的方法２０.空串的長度為（A)。A.0B.1C．2D2１．排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序為止,該排序算法是(D)。Ａ．選擇排序Ｂ．快速排序Ｃ.冒泡排序D．直接插入排序２２．采用順序查找法對長度為n的線性表進(jìn)行查找(不采用表尾設(shè)監(jiān)視哨的方法）,最壞的情況下要進(jìn)行（B）次元素間的比較。A.n+2B．nC．n-1Ｄ．ｎ／223.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為a1，1,數(shù)組b的下標(biāo)從1開始),則矩陣元素a5,3相應(yīng)一維數(shù)組b的數(shù)組元素是（C）。A．b[18］B．b[8]Ｃ.b[1３］Ｄ．b[1０]24．如圖１若從頂點a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的頂點序列為（D）。ababecdhgfB．a(chǎn)eｂcghdfC.ａeｄfbcghD．a(chǎn)becdfgh圖125.已知如圖2所示的一個圖,若從頂點a出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點序列為（Ｄ)。Ａ．a(chǎn)beｃdｆB．a(chǎn)cfｅbdC．a(chǎn)eｂcｆdD．a(chǎn)eｄfcbbbdfeca圖22６.一棵哈夫曼樹總共有23個結(jié)點，該樹共有（D）個葉結(jié)點(終端結(jié)點)。A．10B.13C．１１二、填空題1.通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及集合、線性、_樹形_、_圖狀四種類型。2.通常可以把某城市中各公交站點間的線路圖抽象成＿＿圖狀＿＿結(jié)構(gòu)。３.設(shè)有一個單向鏈表,結(jié)點的指針域為nｅxｔ,頭指針為ｈeaｄ,ｐ指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句__＿p-＞ｎext=ｈeａd；_____。4．設(shè)有一個單向循環(huán)鏈表,頭指針為heａd，鏈表中結(jié)點的指針域為next，p指向尾結(jié)點的直接前驅(qū)結(jié)點,若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作＿_(dá)＿_(dá)__＿＿p－>next＝head。5．循環(huán)隊列的隊頭指針為ｆ,隊尾指針為r,當(dāng)__＿r=f_＿_(dá)__時表白隊列已空。6．在一個鏈隊中,ｆ和r分別為隊頭和隊尾指針,隊結(jié)點的指針域為ｎext，則插入一個s所指結(jié)點的操作為___ｒ－>nｅｘt=s___;r=ｓ；７．設(shè)有一個鏈棧，棧頂指針為hs,現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作__s->nｅxt=hs和hs=ｓ；8．循環(huán)隊列的隊頭指針為f，隊尾指針為r,當(dāng)___r＝=f_時表白隊列為空。9.在一個鏈隊中，f和r分別為隊頭和隊尾指針,隊結(jié)點的指針域為next，則插入一個ｓ所指結(jié)點的操作為__r->next＝ｓ___；r=s;１０.“A”在存儲時占___２____個字節(jié)。11.串的兩種最基本的存儲方式分別是＿順序存儲__和_＿鏈?zhǔn)酱鎯Γ達(dá)。12.一棵二叉樹沒有單分支結(jié)點，有6個葉結(jié)點,則該樹總共有___11__個結(jié)點。13．一棵二叉樹中順序編號為i的結(jié)點,若它存在左、右孩子,則左、右孩子編號分別為___＿２ｉ___、＿_(dá)2ｉ＋1___。1４．按照二叉樹的遞歸定義,對二叉樹遍歷的常用算法有_先序、_中序＿、_后序＿三種。１5．兩個串相等的充足必要條件是串長度相等且相應(yīng)位置的字符相等。1６．把數(shù)據(jù)存儲到計算機(jī)中，并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_物理（存儲）_結(jié)構(gòu)。１７．一棵二叉樹葉結(jié)點(終端結(jié)點)數(shù)為５，單分支結(jié)點數(shù)為2，該樹共有_＿１1__個結(jié)點。18．如圖3所示的二叉樹，其后序遍歷序列為ｇdbｅihfｃa。eefgibachd圖319．根據(jù)搜索方法的不同,圖的遍歷有＿＿深度優(yōu)先搜索遍歷_、_廣度優(yōu)先搜索遍歷方法。２0.二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是__錯誤___＿＿的。(回答對的或不對的)21．一個有序表｛3,４,10,１４,34,43，46，６4，75,７8,90，９６，130}用折半查找法查找值為90的結(jié)點，經(jīng)___４＿_(dá)＿_(dá)次比較后查找成功。三、綜合題1．（1）已知某二叉樹的后序遍歷序列是debcａ,中序遍歷序列是dbeac，試畫出該二叉樹ababced答：d<b＜e＜a<c（3）給出該樹的前序遍歷序列答:abdec2．(１）一組記錄的關(guān)鍵字序列為｛４５，４0，65,43,35,95},寫出運(yùn)用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果）答：45４0654３35９５354065433595354０65４３6595354043４365953５4043456595(2)對序列{4５，４０，6５,43，３５,95}運(yùn)用直接插入排序,寫出逐次插入過程(從第一個元素一直到第六個元素）。答404565４33５９540４3４5６5359５３540434565954028724028723100546(2）對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度答:ASL=（1x1＋2x2+3x3＋４)/7=１8/７４．(1)設(shè)有查找表{５，14,2,6,１8，７，4，16,3},依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹.242461673185145答:中序遍歷1642325216423252576782102初始樹堆4初始樹堆42826752573216102(2)寫出對上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列答:１02，52，４２，8２，16，６７，32,57四、程序填空題１．以下函數(shù)在ａ[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于ｋ的記錄,查找成功返回該記錄的下標(biāo),失敗時返回－１,完畢程序中的空格tyｐｅdefstruct{ｉｎｔkey；……}NODE；iｎtBinａｒy_Seaｒch(NＯDEa[],intn,intk)｛iｎtlow，ｍｉd,high;ｌｏw=0;ｈigｈ=n-1；ｗhilｅ(__ｌow<=higｈ＿＿_(dá)_){mid=（low+higｈ)/2;if(a[mｉd].key==ｋ)ｒetuｒｎ__mid＿_(dá)＿_(dá)__； elsｅｉf(_＿a[ｍid］．ｋeｙ＜k;_＿_(dá))lｏw＝mid＋1; else_hｉｇｈ=mid-1_＿_(dá)__;?}_＿reｔｕrn－1＿_(dá)__;?}2．以下函數(shù)為鏈棧的進(jìn)棧操作,ｘ是要進(jìn)棧的結(jié)點的數(shù)據(jù)域,tｏp為棧頂指針sｔructｎｏde{EleｍTyｐedata;structnode*nｅｘt;}；stｒuｃｔnode*top；vｏidPuｓh(ＥlemTyｐeｘ)｛ｓtｒucｔnoｄe＊p;p=（sｔructｎode*)malloｃ（＿sｉｚeof（ｓtｒuｃtnode)___);p->data=x;__p－>next＝tｏｐ＿_(dá)_；__top=p__；}3．以下函數(shù)為鏈隊列的入隊操作,x為要入隊的結(jié)點的數(shù)據(jù)域的值,ｆronｔ、reａr分別是鏈隊列的隊頭、隊尾指針structnode｛ＥlemTｙpedａt(yī)a;stｒuctｎodｅ＊nexｔ;};ｓtructnoｄe*front，*ｒｅar；voｉｄIｎＱueue（ElemTypｅx){sｔrｕctnｏde*p；p=(sｔｒuctnode*)_＿_(dá)mａｌlｏc(ｓizｅof(struｃtnode））____;p－>daｔa=x;p-＞nｅｘt=ＮＵLL;＿_(dá)reaｒ->nｅxｔ=ｐ____;ｒear=＿＿_(dá)p_____;}期末綜合練習(xí)二一、單項選擇題１．（B)是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集。A．?dāng)?shù)據(jù)元素B.數(shù)據(jù)對象Ｃ．?dāng)?shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)項2．同一種邏輯結(jié)構(gòu)(Ｂ)。A.只能有唯一的存儲結(jié)構(gòu)B．可以有不同的存儲結(jié)構(gòu)C.只能表達(dá)某一種數(shù)據(jù)元素之間的關(guān)系D．以上三種說法均不對的3．設(shè)鏈表中的結(jié)點是ＮODE類型的結(jié)構(gòu)體變量,且有NODＥ*ｐ；為了申請一個新結(jié)點,并由ｐ指向該結(jié)點，可用以下語句(Ａ）。A.ｐ=(NＯＤＥ＊)ｍalloｃ(sizeof(ＮODE))；Ｂ.p＝（*ＮＯDE)maｌloc(ｓizeof(ＮODE))；C．p＝(NODE)mａlloc(sizeof(p));D．ｐ=(NOＤE＊）ｍａlloc（sizeｏf(ｐ))；4．鏈表所具有的特點是(C）。A．可以隨機(jī)訪問任一結(jié)點B.占用連續(xù)的存儲空間Ｃ.插入刪除元素的操作不需要移動元素結(jié)點D．可以通過下標(biāo)對鏈表進(jìn)行直接訪問５．設(shè)順序存儲的線性長度為n,要在第i個元素之前插入一個新元素，按課本的算法當(dāng)i=(Ｄ）時,移動元素次數(shù)為2A.ｎ/2B．nC．１D.n－１6.數(shù)據(jù)的物理結(jié)構(gòu)(D)。A．與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)B.僅僅涉及數(shù)據(jù)元素的表達(dá)Ｃ．只涉及數(shù)據(jù)元素間關(guān)系的表達(dá)D．涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)7.一個棧的進(jìn)棧序列是1,2,3,４,則棧的不也許的出棧序列是（B）（進(jìn)出棧操作可以交替進(jìn)行）A.3,2,４，１B．1，4,2,３Ｃ.4，3，2，１D.3,２，1,48．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在(Ａ）的關(guān)系。Ａ.一對一Ｂ．一對多C.多對多D.每一個元素都有一個直接前驅(qū)和一個直接后繼9．設(shè)有一個帶頭結(jié)點的鏈隊列,隊列中每個結(jié)點由一個數(shù)據(jù)域ｄata和指針域nｅxｔ組成，frｏnt和ｒeａｒ分別為鏈隊列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點(該結(jié)點已被賦值),則入隊操作為（A)。A.rｅar->neｘt=p；reaｒ=ｐ；Ｂ.rear->nｅxｔ=p;p=reａr;C.p=reａr->next;rｅar=p;D．rear=p;ｒｅａｒ->next=p;1０．以下表中可以隨機(jī)訪問的是(D)。A.單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D．順序表1１．以下說法不對的的是(C)。A．順序棧中，棧滿時再進(jìn)行進(jìn)棧操作稱為“上溢”B．順序棧中，棧空時再作出棧棧操作稱為“下溢”C.順序隊列中，當(dāng)尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿D．順序隊列中,隊列的頭指針和尾指針均超越隊列存儲空間的上界,則隊列已空12.算法的時間復(fù)雜度與(Ｃ)有關(guān)。Ａ.所使用的計算機(jī)B．與計算機(jī)的操作系統(tǒng)C.與算法自身D．與數(shù)據(jù)結(jié)構(gòu)1３．設(shè)有一個20階的對稱矩陣A，采用壓縮存儲方式,將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣A的第一個元素為a11,數(shù)組b的下標(biāo)從1開始)，則矩陣元素a8,5在一維數(shù)組b中的下標(biāo)是（D）。A.30Ｂ.28C.４0Ｄ14.設(shè)有一個長度為n的順序表，要刪除第i個元素需移動元素的個數(shù)為(B)。A.n-i＋1B．n-ｉC．n-i-1D．ｉ15.深度為5的完全二叉樹第5層上有4個結(jié)點,該樹一共有(Ｄ）個結(jié)點。A．２8B.30C.３1D16．在一個單鏈表中,p、q分別指向表中兩個相鄰的結(jié)點,且q所指結(jié)點是p所指結(jié)點的直接后繼,現(xiàn)要刪除ｑ所指結(jié)點，可用的語句是（Ｃ)。A.ｐ=q->nextB.ｐ->ｎext=qC．p->next=ｑnexｔD.q->ｎeｘt=NULL17.已知一個圖的所有頂點的度數(shù)之和為m，則ｍ一定不也許是（D）。Ａ．４B.8C．1２D18.從一個棧頂指針為tｏｐ的鏈棧中刪除一個結(jié)點時，用變量ｘ保存被刪結(jié)點的值，則執(zhí)行(A)。A．x=toｐ－＞dａt(yī)a；top＝top-＞nｅxｔ;Ｂ．x＝ｔoｐ->dａt(yī)a;C．ｔｏp＝top－>ｎｅｘt;x＝toｐ->dａt(yī)a；D.ｔｏp=top－>ｎｅxt；x=daｔa;19.以下說法對的的是(D)。Ａ．連通圖Ｇ的生成樹中可以包含回路B．連通圖G的生成樹可以是不連通的C.連通圖G的生成樹一定是唯一的Ｄ．連通圖Ｇ的生成樹一定是連通而不包含回路的20.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運(yùn)算為(C）。Ａ.r=f->next;B．r=r->next;C．f=f->nｅxt;D.ｆ=ｒ－>ｎext；2１．對ｎ個元素進(jìn)行冒泡排序,通常要進(jìn)行ｎ-1趟冒泡，在第j趟冒泡中共要進(jìn)行（C)次元素間的比較。Ａ.jＢ.j-1Ｃ.n-jD22．一個棧的進(jìn)棧序列是a，b，ｃ，d,ｅ,則棧的不也許輸出序列是（A)(進(jìn)棧出棧可以交替進(jìn)行）。A．ｄceabB．ｅdcbaC．ｄｅcbaD.ａbcde２3.在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是(D)。A.冒泡B.選擇C.直接插入D.折半插入2４．有一個長度為１0的有序表,按折半查找對該表進(jìn)行查找,在等概率情況下查找成功的平均比較次數(shù)為(B）。A．2６/１0B.2９/１0C2５.如圖1若從頂點a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點序列為(B）。abecabecdfB．a(chǎn)bｅｄｃfC.acｅbdｆD．ａcfbde圖126.排序算法中，從未排序序列中依次取出元素與已排序序列(初始為空）中的元素進(jìn)行比較（規(guī)定比較次數(shù)盡量少),然后將其放入已排序序列的對的位置的方法是（C）。A.冒泡B.直接插入C.折半插入D.選擇排序２7．一棵哈夫曼樹有n個葉子結(jié)點（終端結(jié)點),該樹總共有(B）個結(jié)點。Ａ．2n－2B．2n-1C.2nＤ２8.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲的方式,將其下三角部分以行序為主存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始）,則矩陣中元素A8,5在一維數(shù)組Ｂ中的下標(biāo)是（A)。A．33B.32C29．?dāng)?shù)據(jù)的(A）結(jié)構(gòu)與所使用的計算機(jī)無關(guān)。A．邏輯B.物理Ｃ.存儲D．邏輯與存儲30．在一個無向圖中,所有頂點的度數(shù)之和等于邊數(shù)的(Ｄ)倍。A.3Ｂ．２．5C二、填空題1．通?？梢园岩槐揪哂胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成___樹形__結(jié)構(gòu)。2．棧和隊列的操作特點分別是__先進(jìn)后出__＿和＿_(dá)_先進(jìn)先出＿_(dá)。3.要在一個單向鏈表中p所指向的結(jié)點之后插入一個s所指向的新結(jié)點，若鏈表中結(jié)點的指針域為ｎexｔ,可執(zhí)行＿＿s－>neｘt＝p－>neｘt;_＿_(dá)___和p-＞nexｔ=s;的操作。4.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為____圖狀（網(wǎng)狀）__結(jié)構(gòu)。5．設(shè)有一個非空的鏈棧，棧頂指針為ｈs，要進(jìn)行出棧操作,用ｘ保存出棧結(jié)點的值,棧結(jié)點的指針域為ｎｅxｔ,則可執(zhí)行x=hs->dａt(yī)ａ;__＿h(yuǎn)s＝hｓ->ｎext;＿＿＿_(dá)_。6．根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性,通?？煞譃榧?、線性、樹形、圖狀四類基本結(jié)構(gòu)。7.在一個不帶頭結(jié)點的非空鏈隊中，ｆ和r分別為隊頭和隊尾指針,隊結(jié)點的數(shù)據(jù)域為datａ，指針域為ｎｅxt，若要進(jìn)行出隊操作，并用變量ｘ存放出隊元素的數(shù)據(jù)值，則相關(guān)操作為x＝f-＞ｄatａ;__f=f->ｎeｘｔ;______。8．規(guī)定在n個數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時間復(fù)雜度分別為___＿＿_(dá)＿_(dá)和＿n-1，O(n）____＿_(dá)_。9.循環(huán)隊列的最大存儲空間為MａxSｉzｅ=８，采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針front=4,則當(dāng)隊尾指針rｅar=____4__＿_(dá)時，隊列為空，當(dāng)reａr＝___2_____時，隊列有6個元素。10．稀疏矩陣存儲時，采用一個由__行號__、__＿列號＿、_＿非零元＿_(dá)3部分信息組成的三元組唯一擬定矩陣中的一個非零元素。11．在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)立三個域,它們是值域左指針、右指針。１2．一棵二叉樹順序編號為6的結(jié)點（樹中各結(jié)點的編號與等深度的完全二叉中相應(yīng)位置上結(jié)點的編號相同），若它存在右孩子,則右孩子的編號為＿_(dá)_13_＿_(dá)__。１3.向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點時，可執(zhí)行s-＞next=h;和_＿ｈ=ｓ__。14.在一個鏈隊中,設(shè)ｆ和r分別為隊頭和隊尾指針,則插入s所指結(jié)點的操作為__ｒ->neｘt=s＿_(dá)和r＝ｓ；(結(jié)點的指針域為nｅｘt)15．如圖2所示的二叉樹，其前序遍歷序列為__＿abdefcg__。ggfabdec圖2１6.設(shè)有一棵深度為4的完全二叉樹,第四層上有5個結(jié)點，該樹共有＿_(dá)_12__個結(jié)點。（根所在結(jié)點為第１層）１7.在隊列的順序存儲結(jié)構(gòu)中，當(dāng)插入一個新的隊列元素時，尾指針的值增1，當(dāng)刪除一個元素隊列時，頭指針的值增1。18.對稀疏矩陣進(jìn)行壓縮存儲,矩陣中每個非零元素相應(yīng)的三元組涉及該元素的__行下標(biāo)＿、__列下標(biāo)_和__＿非零元素值_三項信息。19．循環(huán)隊列的引入，目的是為了克服假上溢。20.在對一組記錄（５5,39,９7,22,16,７3,65，４7,88）進(jìn)行直接插入排序時,當(dāng)把第7個記錄６５插入到有序表時,為尋找插入位置需比較_＿_(dá)3______次。三、綜合題1．(1)設(shè)ｈead１和ｐ1分別是不帶頭結(jié)點的單向鏈表A的頭指針和尾指針，heaｄ2和ｐ２分別是不帶頭結(jié)點的單向鏈表B的頭指針和尾指針,若要把B鏈表接到A鏈表之后,得到一個以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個關(guān)鍵的賦值語句（不用完整程序,結(jié)點的鏈域為ｎext）。答:ｐ1－>ｎeｘt＝heａd2;p2->ｎext=ｈeaｄ1；（2)單向鏈表的鏈域為nexｔ,設(shè)指針ｐ指向單向鏈表中的某個結(jié)點，指針s指向一個要插入鏈表的新結(jié)點，現(xiàn)要把ｓ所指結(jié)點插入p所指結(jié)點之后,某學(xué)生采用以下語句:p->ｎext=s;s－>nｅxt=p-＞nexｔ;這樣做對的嗎？若對的則回答對的，若不對的則說明應(yīng)如何改寫答：不對,ｓ-＞ｎext=p－>next；p->next=s；２.（1)以２，3,４,７,8,９作為葉結(jié)點的權(quán),構(gòu)造一棵哈夫曼樹(規(guī)定每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點的哈夫曼編碼。3333(1）1518151879987998545432322:111０3:１11１4：1107:008:0１9：10（２)一棵哈夫曼樹有ｎ個葉結(jié)點，它一共有多少個結(jié)點？簡述理由？答:２n-1個,由于非葉結(jié)點數(shù)比葉結(jié)點數(shù)少一個。３．（1）畫出對長度為10的有序表進(jìn)行折半查找的鑒定樹(以序號1，2,……１0表達(dá)樹結(jié)點）5252849631071答:AＳL=(１ｘ１＋2x2＋3ｘ4＋４x３）/10=2９／１04.一組記錄的關(guān)鍵字序列為（46，79，5６,３8,4０,84）（1)運(yùn)用快速排序的方法，給出以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果(給出逐次互換元素的過程,規(guī)定以升序排列)初始序列4６,７9，56，38，４0,8440,79，5６，38，40,8440，７9，56,38，7９，84４0,3８,56,3８,7９,8440，38,56，56,7９，８４40,3８，46，５6,79，84(2）對上述序列用堆排序的方法建立大根堆，規(guī)定以二叉樹逐次描述建堆過程。3777624752377762475227119711372747526277975679384084468479384046566567938404679384084845646初始樹堆初始樹堆（2）寫出對上述堆所相應(yīng)的二叉樹進(jìn)行前序遍歷得到的序列答：11,3７，47,97,77,27,62，526．設(shè)查找表為(50，60,75,８5,96,９8,105，110，１20,１30)(1）說出進(jìn)行折半查找成功查找到元素120需要進(jìn)行多少次元素間的比較？３次(２)為了折半查找元素９5,通過多少次元素間的比較才干擬定不能查到?4次967596759813010585501100512060四、程序填空題１．以下函數(shù)為直接選擇排序算法，對a[１］,a［2］,…a[n]中的記錄進(jìn)行直接選擇排序，完畢程序中的空格typeｄefstruct{ｉntkey;……}ＮODE；voidselsorｔ（NＯDEa[］,ｉｎｔn)｛ inti，j,k;?NOＤEtｅｍp;?for（i=１;i<=__n-1___;i＋+) {? ｋ=i；??ｆｏr(j=ｉ+1;j<=___ｎ＿_(dá)＿;j＋+）? ?if(a［j］.key<a［ｋ]．kｅy)＿_(dá)ｋ=j＿＿_(dá)__; if(i!=k）??{? ?temｐ=ａ［i]; ?__ａ［i]＝a[ｋ]___;?? __＿a[k］=temｐ_;? }?}}２.以下是用尾插法建立帶頭結(jié)點且有n個結(jié)點的單向鏈表的程序,結(jié)點中的數(shù)據(jù)域從前向后依次為１,2,3,……,n，完畢程序中空格部分。ＮＯDE*ｃreate(ｎ){NODE*hｅaｄ,*p,＊ｑ;inti;p＝(ＮODＥ*）malloc(ｓizeoｆ(ＮＯDE));ｈｅad=p;q＝ｐ；pnext=ＮULL;/＊建立頭結(jié)點＊/for(ｉ=1;i＜=n；i++）{p＝（ＮODＥ＊)maｌloｃ(ｓizeoｆ(NOＤＥ）);ｐdａｔａ=i;pｎeｘt=ＮULL；qnext=p;q=p;}retｕｒn（head);}3．以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為lｅft和ｒight，數(shù)據(jù)域dａt(yī)a為字符型，BT指向根結(jié)點）。vｏiｄInordeｒ（strucｔBＴｒｅeNodｅ*BT)｛if（BT!=NULL）{Iｎorder(BT->ｌeft);printf（“%c”,BT->data);Inoｒdeｒ(BＴ-＞righｔ);}}期末綜合練習(xí)三一、單項選擇題１.深度為５的完全二叉樹共有20個結(jié)點,則第5層上有(C)個結(jié)點(根所在結(jié)點為第一層)。A．３B.8C.5Ｄ2.在C語言中,順序存儲長度為3的字符串,需要占用（A）個字節(jié)。A．4B．3C3．已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為(A）。Ａ.２mB.mC.２m+1D.m／24.串函數(shù)SｔrCat（a,b）的功能是進(jìn)行串（D）。A.比較Ｂ．復(fù)制C.賦值D．連接５．?dāng)?shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的(Ｄ)結(jié)構(gòu)。A.物理Ｂ．存儲C.邏輯與物理D．邏輯６.一棵有ｎ個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有（A)個指針域為空。A.ｎ＋1B．nＣ．n-1D．n-２7.鏈表所具有的特點是(Ｃ)。A．可以隨機(jī)訪問任一結(jié)點B.占用連續(xù)的存儲空間C．插入刪除不需要移動元素結(jié)點D.可以通過下標(biāo)對鏈表進(jìn)行直接訪問８．設(shè)一棵哈夫曼樹共有ｎ個非葉結(jié)點，則該樹有（B）個葉結(jié)點。A．nB．n+1C9.線性表只要以(C）方式存儲就能進(jìn)行折半查找。A．鏈接Ｂ．順序Ｃ．關(guān)鍵字有序的順序Ｄ．二叉樹10．從一個棧頂指針為ｔop的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的值，則執(zhí)行（A)。A.ｘ=top－>ｄata；ｔop=tｏpnext;B．x=ｔop->data;C.tｏｐ=tｏp－＞ｎeｘt；x=top->ｄａｔa;D.ｔop＝top->neｘt；ｘ=data;11．散列查找的原理是（A）。A．在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲Ｃ.按關(guān)鍵字值的比較進(jìn)行查找D．基于二分查找的方法12.一棵完全二叉樹共有５層,且第5層上有六個結(jié)點，該樹共有(C)個結(jié)點。Ａ.3０B．20Ｃ１3.對n個元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了(C)次元素間的互換,則表白序列已經(jīng)排好序。A．1B.２C.0Ｄ14．在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的(Ｄ)倍。Ａ．3B.２.５Ｃ15．排序過程中,每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置,直到所有排好序為止，該排序算法是（A)。Ａ．直接插入排序B．快速排序C．冒泡排序Ｄ．選擇排序16.已知如圖1所示的一個圖,若從頂點V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的一種頂點序列為(Ａ)。A．V1V2V4Ｖ8Ｖ5V3V6V7B.V1V2V4Ｖ5V８V3V６V7C．Ｖ1V2Ｖ4V8V3V５V6V7Ｄ.V1V3Ｖ6V7V2Ｖ4V5V8V6V6V7V1V2V3V8V4V5圖117.在對一組元素(64，4８，106,３3,25，82,7０，５５，93)進(jìn)行直接插入排序時，當(dāng)進(jìn)行到要把第7個元素70插入到已經(jīng)排好序的子表時,為找到插入位置，需進(jìn)行(Ｃ)次元素間的比較（指由小到大排序）。A．6B.２C.３D1８．已知如圖２所示的一個圖,若從頂點a出發(fā),按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點序列為（B）。A．a(chǎn)bｃedfB.abceｆdC．a(chǎn)ebｃfdD.acfdebbdbdfeca圖2１9.采用順序查找法對長度為n的線性表進(jìn)行查找(不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（B）次元素間的比較。A.n+２Ｂ.nC．n-1D．n/２20．對二叉排序樹進(jìn)行（Ｃ）遍歷,可以使遍歷所得到的序列是有序序列。A．按層次Ｂ.后序C.中序Ｄ．前序2１．如圖３，若從頂點ａ出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的頂點序列為(Ｂ)。Ａ．ａcebｄｇｆB.aｂecdgｆC．a(chǎn)cfeｄgｂＤ．a(chǎn)becfｄｇaabecdfg圖32２.在有序表{2，4,7,１4，34,４3，47,64,７5,8０，9０，9７，1２０}中，用折半查找法查找值8０時,經(jīng)(Ｂ)次比較后查找成功。A．4B.2C.3Ｄ.５2３．元素2，4，６，8按順序依次進(jìn)棧,則該棧的不也許輸出序列是(D)(進(jìn)棧出棧可以交替進(jìn)行）。A．8，6,4，２B．２，4,6,8C．４，2，8,6D.８,６,2，424．有一個長度為9的有序表,按折半查找對該表進(jìn)行查找,在等概率情況下查找成功的平均比較次數(shù)為（Ｂ)。A.２5/１0B．25/９C25.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列(初始為空)的一端的方法，稱為（C）排序。Ａ.歸并B．插入C.選擇Ｄ．快速26.排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（規(guī)定比較次數(shù)盡量少),然后將其放入已排序序列的對的位置的方法是(Ｃ)。A.冒泡B.直接插入C．折半插入D．選擇排序27.一棵哈夫曼樹總共有２3個結(jié)點，該樹共有（D)個葉結(jié)點(終端結(jié)點）A．１0B.1３Ｃ.112８．一組記錄的關(guān)鍵字序列為(46,79，56，38，4０,８4），運(yùn)用快速排序,以第一個關(guān)鍵字為分割元素，通過一次劃分后結(jié)果為（Ｂ）。A.40,3８，４6,7９，5６,84B.40,３8，４6，56,７９，84Ｃ.40，38，４６,84，５6，79D．3８,40,4６，56，79,8429.隊列的插入操作在（B）進(jìn)行。A.隊頭Ｂ.隊尾C．隊頭或隊尾D．在任意指定位置二、填空題(每小題2分，共2４分）1.一棵二叉樹沒有單分支結(jié)點，有6個葉結(jié)點，則該樹總共有＿_(dá)＿_(dá)11____個結(jié)點。2．在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)立三個域，它們是_值域＿＿、左指針、右指針。3.設(shè)一棵完全二叉樹,其最高層上最右邊的葉結(jié)點的編號為奇數(shù),該葉節(jié)點的雙親結(jié)點的編號為１0，該完全二叉樹一共有___２1___個結(jié)點。4．一棵二叉樹中順序編號為i的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為_＿_(dá)_2i_、_＿_(dá)2i+1___＿。５.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_＿先序_、___中序＿、__后序_三種。６．串的兩種最基本的存儲方式是__順序存儲_和__鏈?zhǔn)酱鎯＿_(dá)。７.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為___樹形_____結(jié)構(gòu)。8.一棵有2n-１個結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為2,則該樹共有___N____個葉結(jié)點。9.把數(shù)據(jù)存儲到計算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為__＿物理（存儲)_＿_(dá)__結(jié)構(gòu)。1０.對于一棵具有ｎ個結(jié)點的二叉樹,其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有__ｎ+1_＿_(dá)__＿個指針域為空。11.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_＿線性__結(jié)構(gòu)。12．__中序_＿_(dá)__＿遍歷二叉排序樹可得到一個有序序列。1３.如圖4所示的二叉樹，其后序遍歷序列為ｇdｂｅihfcａ。eefgibachd圖4１4．n個元素進(jìn)行冒泡法排序，通常需要進(jìn)行_＿n-1＿_(dá)趟冒泡。15．如圖5所示的二叉樹,其先序遍歷序列為__abdefcg_＿。ggfabdec圖5１6.二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是__不對的_＿_(dá)_的。(回答對的或不對的)１７．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是＿對的_____的。(回答對的或不對的)１8．根據(jù)搜索方法的不同,圖的遍歷有_＿深度優(yōu)先搜索遍歷_、＿廣度優(yōu)先搜索遍歷＿兩種方法１9．對記錄序列排序是指按記錄的某個關(guān)鍵字排序，記錄序列按_＿主關(guān)鍵字___＿_(dá)＿_(dá)排序結(jié)果是唯一的。20．按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字相等的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。1642164232525767821021．（１)運(yùn)用篩選過程把序列{4２，82,67,１02,16，32，57，52｝建成堆（小根堆)，畫出該堆（不規(guī)定中間過程）。(２)寫出對上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列。 答:10２,52，4２,82，16,6７,32,5７2．設(shè)查找表為(16，15,2０,5３,64,7)，(１)用冒泡法對該表進(jìn)行排序(規(guī)定升序排列）,寫出每一趟的排序過程,通常對n個元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡?第j趟要進(jìn)行多少次元素間的比較?答:(1)原序列16１520５３６47151６20５37