2023年電大數(shù)據(jù)結(jié)構(gòu)本期末復(fù)習(xí)材料

中央電大開放本科計算機科學(xué)與技術(shù)數(shù)據(jù)結(jié)構(gòu)(本）期末綜合練習(xí)一、單項選擇題１.數(shù)據(jù)元素是數(shù)據(jù)的基本單位,它（C）。Ａ．只能有一個數(shù)據(jù)項組成B.至少有二個數(shù)據(jù)項組成C.可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成D．至少有一個數(shù)據(jù)項為指針類型２．一種邏輯結(jié)構(gòu)（A）存儲結(jié)構(gòu)。Ａ.可以有不同的B.只能有唯一的C.的數(shù)據(jù)元素在計算機中的表達稱為D．的數(shù)據(jù)元素之間的關(guān)系稱為3.線性表的順序結(jié)構(gòu)中，(C)。A．邏輯上相鄰的元素在物理位置上不一定相鄰B．?dāng)?shù)據(jù)元素是不能隨機訪問的C.邏輯上相鄰的元素在物理位置上也相鄰D.進行數(shù)據(jù)元素的插入、刪除效率較高４．以下說法中不對的的是（B)。A．雙向循環(huán)鏈表中每個結(jié)點需要包含兩個指針域B．已知單向鏈表中任一結(jié)點的指針就能訪問到鏈表中每個結(jié)點C.順序存儲的線性鏈表是可以隨機訪問的Ｄ.單向循環(huán)鏈表中尾結(jié)點的指針域中存放的是頭指針5．以下表中可以隨機訪問的是（Ｄ）。Ａ.單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D.順序表6．雙向循環(huán)鏈表結(jié)點的數(shù)據(jù)類型為:struｃtnode｛ｉｎtdaｔa;strucｔｎｏde*nexｔ;/*指向直接后繼*／sｔructnodｅ*prior;}；設(shè)p指向表中某一結(jié)點，要顯示ｐ所指結(jié)點的直接前驅(qū)結(jié)點的數(shù)據(jù)元素，可用操作(B）。A．prｉntf(“%d”,p－＞neｘt->data)；B.pｒｉntｆ(“%d”,ｐ->prior->ｄａt(yī)ａ);C.priｎtｆ(“%ｄ”,ｐ->ｐriｏr->ｎｅxt);Ｄ．prｉｎtf(“%ｄ”,p->data);7.設(shè)順序存儲的線性表長度為ｎ,對于刪除操作，設(shè)刪除位置是等概率的,則刪除一個元素平均移動元素的次數(shù)為（Ａ）。A．(ｎ+１)／2Ｂ.ｎC．2nD.n-i８.一個棧的進棧序列是eｆgh，則棧的不也許的出棧序列是(D)（進出棧操作可以交替進行）。A．ｈgｆｅＢ.gfehC.fｇｅhD．ｅhfｇ9.設(shè)top是一個鏈棧的棧頂指針,棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成,設(shè)用x接受棧頂元素，則出棧操作為(A)。A.ｘ=ｔｏｐ－>daｔａ;toｐ=toｐ->ｎｅxt;B.ｔop＝top->next;x＝top->data;C．x=top->ｎext;ｔoｐ=top->data;D.toｐ->ｎｅxｔ=ｔop；ｘ=toｐ->daｔa；１0．設(shè)top是一個鏈棧的棧頂指針,棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成,設(shè)用x接受棧頂元素，則取棧頂元素的操作為（C)。A．ｔｏp－＞ｄaｔa=ｘ;B．toｐ=top－＞nｅxｔ;C.ｘ=tｏｐ->datａ;D.ｘ=top－>data;toｐ=top->ｎexｔ;１1．以下說法對的的是（Ｃ)。Ａ．隊列是后進先出B.棧的特點是后進后出C．棧的刪除和插入操作都只能在棧頂進行D.隊列的刪除和插入操作都只能在隊頭進行13．串函數(shù)StｒCｍp(“abＡ”,”ａba”)的值為(D）。Ａ.1B．0C.“aｂAabａ”Ｄ.-114．cｈaｒ*ｐ；p＝StrCａt(yī)(“ABD”,”ABC”);Priｎtf(“％s”,ｐ);的顯示結(jié)果為(B)。A．-1B．ABDABＣC．ABD.115．設(shè)有一個12階的對稱矩陣Ａ，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中（矩陣A的第一個元素為a1，1，數(shù)組b的下標從1開始）,則矩陣A中第4行的元素在數(shù)組b中的下標i一定有(A)。A、７≤i≤10B、１1≤i≤15C、9≤i≤１４D、６≤i≤9１6.深度為5的滿二叉樹至多有（B）個結(jié)點(根結(jié)點為第一層)A．40B．３1C．34D.3517.已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（A)。A.2mＢ.ｍＣ．2ｍ+1Ｄ.m/218．已知一個圖的所有頂點的度數(shù)之和為m，則該圖的邊數(shù)為(D）。A．２ｍB.mＣ.２m+1D.m/2１９.以下說法不對的的是（D)。A.連通圖G一定存在生成樹B.連通圖Ｇ的生成樹中一定包含G的所有頂點C．連通圖G的生成樹中不一定包含G的所有邊D．連通圖Ｇ的生成樹可以是不連通的20.以下說法不對的的是(A)。A.連通圖Ｇ的生成樹一定是唯一的B.連通圖Ｇ一定存在生成樹C.連通圖G的生成樹中一定要包含Ｇ的所有頂點D．連通圖Ｇ的生成樹一定是連通并且不包含回路21.散列查找的原理是（Ａ）。A.在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應(yīng)關(guān)系B.按待查記錄的關(guān)鍵字有序的順序方式存儲C.按關(guān)鍵字值的比較進行查找D．基于二分查找的方法22.有序表為{1，2,4,6，10,１８，20，32},用課本中折半查找算法查找值１８，經(jīng)(B)次比較后成功查到。Ａ.3B.２C．4D.523．排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序為止,該排序算法是(A）。A.直接插入排序B.快速排序C．冒泡排序Ｄ．選擇排序24．在排序過程中，可以通過某一趟排序的相關(guān)操作所提供的信息,判斷序列是否已經(jīng)排好序,從而可以提前結(jié)束排序過程的排序算法是(A)。A．冒泡B.選擇C.直接插入Ｄ．折半插入2５．采用順序查找法對長度為ｎ的線性表進行查找（不采用表尾設(shè)監(jiān)視哨的方法）,最壞的情況下要進行（B）次元素間的比較。A.n+2B.nＣ.n-１D.n/２26．用折半查找法,對長度為12的有序的線性表進行查找，最壞情況下要進行(Ａ）次元素間的比較Ａ．４B．3Ｃ.５D.6２7.如圖若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷,則也許得到的頂點序列為(D)。ababecdhgfB．a(chǎn)ｅbcghｄfC．a(chǎn)edfｂcghD.abecdfｇh圖12８.如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為（B)。bcbcgdafeB.aｅdｂｇfｃC．a(chǎn)ｃfｅbdgD.aecｂdgf2９.一棵哈夫曼樹總共有23個結(jié)點，該樹共有（D）個葉結(jié)點（終端結(jié)點）Ａ.10B．1３C．11D．1２3０.一棵哈夫曼樹總共有25個結(jié)點，該樹共有（A)個非葉結(jié)點（非終端結(jié)點)。A.12B．13C.１4D.1531．針對線性表，在存儲后假如最常用的操作是取第i個結(jié)點及其前驅(qū),則采用(D）存儲方式最節(jié)省時間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表３2．線性表采用鏈式存儲時，其地址(Ｃ）。A．一定是不連續(xù)的B.必須是連續(xù)的C.可以連續(xù)也可以不連續(xù)D.部分地址必須是連續(xù)的３３.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的(D)結(jié)構(gòu)。A.物理B．存儲C.邏輯與物理D．邏輯34.帶頭結(jié)點的單向鏈表的頭指針為heaｄ，該鏈表為空的鑒定條件是(Ｃ)的值為真。Ａ.head＝＝NＵLLB.heａd－>next==hｅadC.heaｄ->next==NULＬD．heａd＝=head－>nｅｘt３5．以下特性中,（D）不是算法的特性。A．有窮性B．?dāng)M定性C.可行性D.有0個或多個輸出36.設(shè)順序存儲的線性表長度為n,對于插入操作，設(shè)插入位置是等概率的，則插入一個元素平均移動元素的次數(shù)為(Ａ）。Ａ.n/２Ｂ.ｎC.ｎ-1D.n-i＋13７．設(shè)有一個長度為n的順序表,要在第i個元素之前（也就是插入元素作為新表的第ｉ個元素),則移動元素個數(shù)為(A)。A.ｎ-i＋１Ｂ．n-iC.n-i-1D.i38．一個棧的進棧序列是５,６，7，8，則棧的不也許的出棧序列是（A）(進出棧操作可以交替進行）A.5,8,6，7Ｂ.7，6，８，５Ｃ．7,6，5,８D．8,7,6,５３9.棧的插入刪除操作在(D)進行。A.棧底B.任意位置C．指定位置Ｄ．棧頂4０.棧和隊列的相同點是（Ｄ）。A．都是后進先出Ｂ.都是后進后出C.邏輯結(jié)構(gòu)與線性表不同D.邏輯結(jié)構(gòu)與線性表相同,都是操作規(guī)則受到限制的線性表4１.以下說法對的的是（C)。A.棧的特點是先進先出，隊列的特點是先進后出B.棧和隊列的特點都是先進后出Ｃ.棧的特點是先進后出，隊列的特點是先進先出Ｄ.棧和隊列的特點都是先進先出4２．在C語言中，運用數(shù)組a存放字符串“Hello”，以下語句中對的的是(A）。A.chara[10］=“Hｅlｌo”;Ｂ．chara［1０];a=“Helｌo”;C.cｈａrａ[1０]=‘Helｌo’；D．ｃhaｒa[１0]＝{‘H’,’e’,’l’，’ｌ’,’o’};43.元素2，４,6,８按順序依次進棧,則該棧的不也許輸出序列是（D）(進棧出?？梢越惶孢M行)。A．8，6，4，2B.2，4，６,8C．4,2,8,6D．8，6,2，444.設(shè)有一個15階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組ｂ中。(矩陣A的第一個元素為a1，1,數(shù)組ｂ的下標從1開始)，則數(shù)組元素ｂ［13]相應(yīng)A的矩陣元素是（A）。A.ａ5,３B.a６，４C．a(chǎn)7,2D．ａ6，８４5.設(shè)有一個1５階的對稱矩陣Ａ，采用壓縮存儲的方式,將其下三角部分以行序為主序存儲到一維數(shù)組B中(數(shù)組下標從1開始）,則矩陣中元素a7,6在一維數(shù)組Ｂ中的下標是（Ｃ)。A.４2B.１3C．27D.324６.一棵完全二叉樹共有30個結(jié)點,則該樹一共有（D)層(根結(jié)點所在層為第一層）。Ａ．6B．4C.3Ｄ．５4７.串函數(shù)StrCmｐ(“d”,“D”)的值為(B)。A.0B．１Ｃ．-1D．３48．以下說法對的的是(D)。A.連通圖G的生成樹中不一定包含G的所有頂點B.連通圖G的生成樹中一定要包含G的所有邊Ｃ．連通圖G的生成樹一定是唯一的D.連通圖G一定存在生成樹49.在一棵二叉樹中,若編號為ｉ的結(jié)點存在右孩子,則右孩子的順序編號為（D)。Ａ.2ｉB.2i-1Ｃ.2i+2D．2i+150．對二叉排序樹進行（Ｃ)遍歷,遍歷所得到的序列是有序序列。A.按層次Ｂ．前序Ｃ.中序D．后序5１.設(shè)一棵有n個結(jié)點采用鏈式存儲的二叉樹，則該樹共有(Ｄ)個指針域為空。A．2nB．2n+１Ｃ．2n+2D．n+152.以下排序算法中，在一趟排序過程中,除了其它相關(guān)操作外，只進行一次元素間的互換的算法是（Ａ)。Ａ．直接選擇B．冒泡C.直接插入D．折半插入bdbdfeca圖１54.對長度為n的線性表進行順序查找,在等概率情況下，平均查找長度為（B)。A．nB．（ｎ＋1)/２C．２nD．n－155．在有序表｛1，3，8，13，3３，42,46，６３，76,７8,86,97,100｝中,用折半查找值８6時，經(jīng)（D）次比較后查找成功。A.6B．3C．8D.４56.如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷,則也許得到的頂點序列為（A)。ababecdfgB.ａｅdcbgfC．ａｃfebdgＤ.aeｃbｄgf57.有一個長度為10的有序表，按折半查找對該表進行查找,在等概率情況下查找成功的平均比較次數(shù)為（Ａ）。A.29/1０B．31／１０C．2６/10Ｄ．29/958.一棵哈夫曼樹有１2個葉子結(jié)點（終端結(jié)點），該樹總共有(C)個結(jié)點。A．２2B.21C.２3D.２４59.一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85）,運用快速排序,以第一個關(guān)鍵字為分割元素，通過一次劃分后結(jié)果為（A)。A.3１,２9，37，４7，70，85B．２9，31,3７，4７,７0,８５Ｃ.31，29，37,70,47,85D.31，2９,37,85，４7,7060．隊列的刪除操作在(Ａ)進行。Ａ．隊頭B.隊尾C.隊頭或隊尾Ｄ.在任意指定位置61．（A)是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集。A.數(shù)據(jù)對象B.數(shù)據(jù)元素C．?dāng)?shù)據(jù)結(jié)構(gòu)D．?dāng)?shù)據(jù)項62．設(shè)鏈表中的結(jié)點是NＯDE類型的結(jié)構(gòu)體變量,且有NODE*ｐ;為了申請一個新結(jié)點,并由p指向該結(jié)點，可用以下語句(D)。A．p=(NODE*)mａlloc(siｚeof（p)）;B.p＝(*NＯDE)ｍａlloｃ(sizｅof(ＮODE));C．p＝(NＯDE)ｍalloc(sｉzeof(p)）；D.p＝(NODE＊)ｍaｌｌoc(sizｅｏf(NODＥ）);63．設(shè)順序存儲的線性長度為n,要在第i個元素之前插入一個新元素，按課本的算法當(dāng)i=(C）時,移動元素次數(shù)為2A．n/２B．nC．n-1C．１６4.一個棧的進棧序列是1,2,３,4，則棧的不也許的出棧序列是（D)(進出棧操作可以交替進行)A.3,2，4，1Ｂ．3,2，1,4C.４,3，2,1D.1，4，2，365．設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域datａ和指針域ｎext組成,fｒｏnt和ｒｅａｒ分別為鏈隊列的頭指針和尾指針。設(shè)ｐ指向要入隊的新結(jié)點(該結(jié)點已被賦值）,則入隊操作為（Ａ）。A.ｒear->neｘt=p；ｒeａr＝p；Ｂ．rear－>neｘt=p;p=rｅar;Ｃ.p＝rｅａr－>nｅxt;rｅaｒ＝p;D.ｒｅar=p;reａｒ->next＝p;６6.以下說法不對的的是(D)。Ａ．順序棧中，棧滿時再進行進棧操作稱為“上溢”B．順序棧中,棧空時再作出棧棧操作稱為“下溢”C.順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界,則隊列已空D．順序隊列中,當(dāng)尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿67．設(shè)有一個2０階的對稱矩陣A，采用壓縮存儲方式，將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣A的第一個元素為a1１,數(shù)組b的下標從1開始),則矩陣元素ａ8，5在一維數(shù)組b中的下標是(D)。A.30B.28C.４0Ｄ．３36８．已知一個圖的所有頂點的度數(shù)之和為m，則ｍ一定不也許是(D）。A．4B．８Ｃ．12D.９6９.以下說法對的的是（C）。A．連通圖G的生成樹中可以包含回路B．連通圖G的生成樹可以是不連通的C．連通圖G的生成樹一定是連通而不包含回路的D.連通圖G的生成樹一定是唯一的7０．對ｎ個元素進行冒泡排序，通常要進行ｎ-1趟冒泡,在第ｊ趟冒泡中共要進行（C)次元素間的比較。A.jB.j－1C．n－jＤ.n-j－171.在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是(C）。Ａ.冒泡B.選擇C.折半插入D．直接插入7２.一棵哈夫曼樹有n個葉子結(jié)點（終端結(jié)點）,該樹總共有（B）個結(jié)點。Ａ．2ｎ－2B.2n-1C.2ｎD.2n+2７3．?dāng)?shù)據(jù)的（A）結(jié)構(gòu)與所使用的計算機無關(guān)。Ａ．邏輯B.物理C.存儲Ｄ．邏輯與存儲74．從n個數(shù)中選取最大元素（B)。A．基本操作是數(shù)據(jù)元素間的互換B．算法的時間復(fù)雜度是Ｏ(n)C.算法的時間復(fù)雜度是Ｏ(n2）D．需要進行(ｎ+1）次數(shù)據(jù)元素間的比較75．設(shè)heaｄ為非空的單向循環(huán)鏈表頭指針，p指向鏈表的尾結(jié)點,則滿足邏輯表達式（B)的值為真。A．p－>next=NULＬB．ｐ->ｎeｘt==heaｄＣ.p-＞nｅｘt=headＤ．p＝=NULＬ7６.設(shè)順序存儲的線性表長度為n，要刪除第i個元素,按課本的算法，當(dāng)i＝(C)時,移動元素的次數(shù)為3。Ａ.3B．ｎ／２C.ｎ－３Ｄ.377．一個棧的進棧序列是ａ,b，ｃ,d,則棧的不也許的出棧序列是（D）。A．ｄｃbaB.bcadC.cbadD.ａdbc78．設(shè)有一個帶頭結(jié)點的鏈隊列,隊列中每個結(jié)點由一個數(shù)據(jù)域daｔa和指針域next組成，fｒont和reaｒ分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作,用ｘ保存出隊元素的值,p為指向結(jié)點類型的指針,可執(zhí)行如下操作：ｐ=frｏｎｔ->nｅxt;x=ｐ->data；然后指行（D)。Ａ．frｏnｔ=p->neｘt;B.fｒｏnt->neｘt＝p；Ｃ．front=ｐ;D.ｆronｔ－＞ｎext=p->ｎext;79.在C語言中,存儲字符串“ABCＤ”需要占用（Ｃ)字節(jié)。A.4Ｂ．2C.５D.380.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為a１，１,數(shù)組b的下標從１開始)，則矩陣元素a5,３相應(yīng)一維數(shù)組b的數(shù)組元素是(C）。A.b[18]B.b[8]C．b［13]D.b[1０］８1.設(shè)有一個1５階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為a１,１，數(shù)組b的下標從1開始),則數(shù)組元素ｂ[13]相應(yīng)A的矩陣元素是(Ａ)。A．a(chǎn)5,３Ｂ．a(chǎn)6，4Ｃ．a(chǎn)7,2D．ａ６，882．深度為５的完全二叉樹共有２0個結(jié)點,則第5層上有(C）個結(jié)點（根所在結(jié)點為第一層)。A.３Ｂ．８C.5D.68３．已知一個圖的所有頂點的度數(shù)之和為m，且ｍ是以下4中情況之一,則m只也許是（D）。A.9B.7C.1５Ｄ.884．以下說法對的的是（C)。A.連通圖G的生成樹中不一定包含G的所有頂點B．連通圖Ｇ的生成樹中一定要包含G的所有邊Ｃ.連通圖G一定存在生成樹Ｄ．連通圖Ｇ的生成樹一定是唯一的85．線性表只要以(Ｃ）方式存儲就能進行折半查找。Ａ.鏈接B．順序Ｃ．關(guān)鍵字有序的順序Ｄ．二叉樹８6.對二叉排序樹進行(C)遍歷，遍歷所得到的序列是有序序列。A．按層次B.前序C．中序Ｄ．后序87．對n個元素進行冒泡排序若某趟冒泡中只進行了(C）次元素間的互換，則表白序列已經(jīng)排好序。A．1Ｂ.2Ｃ.０D.n－188.在對一組元素（64,48，106，33,25，82,70，55,９3)進行直接插入排序時，當(dāng)進行到要把第7個元素７0插入到已經(jīng)排好序的子表時,為找到插入位置,需進行(C）次元素間的比較(指由小到大排序)。A．6B.2C.3D.4ababecdfgA．a(chǎn)cｅbdｇfB．a(chǎn)ｃfedgｂC.abecdgfＤ.aｂｅｃfdg90．一棵哈夫曼樹有１0個非葉子結(jié)點（非終端結(jié)點），該樹總共有（A）個結(jié)點。Ａ.２1Ｂ．20C．22D.1９91．一棵哈夫曼樹有1２個葉子結(jié)點(終端結(jié)點),該樹總共有(C）個結(jié)點。A．21B．2２C.23D.2４92.隊列的插入操作在(B)進行。A.隊頭B.隊尾Ｃ．隊頭或隊尾D．在任意指定位置９3.隊列的刪除操作在（B)進行。A.隊尾B．隊頭C.隊頭或隊尾D.在任意指定位置9４.鏈表所具有的特點是（C）。A.可以隨機訪問任一結(jié)點B．占用連續(xù)的存儲空間C.插人刪除元素的操作不需要移動元素結(jié)點Ｄ.可以通過下標對鏈表進行直接訪問９5．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在(C)的關(guān)系。Ａ.一對一B．一對多C.多對多Ｄ.每一個元素都有一個直接前驅(qū)和一個直接后繼9６.算法的時間復(fù)雜度與(C)有關(guān)。A.所使用的計算機Ｂ.與計算機的操作系統(tǒng)C.與算法自身D.與數(shù)據(jù)結(jié)構(gòu)97．４.在一個單鏈表中，p,q分別指向表中兩個相鄰的結(jié)點，且ｑ所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除ｑ所指結(jié)點，可用的語句是（)。Ａ.ｐ=q-＞rieｘtB．p->nｅxt=qC.p->next=q->nextD.q->ｎｅxt=NＵLL98.在一個鏈隊中,假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為(C)Ａ．ｒ=ｆ-＞nｅxt;B.r=r->neｘt;C.f=f->next;D.f=r－>next；9９.元素3,6，9按順序依次進棧，則該棧的不也許輸出序列是(B）(進棧出?？梢越惶孢M行)Ａ.9，6,３B.９，3，６C.6，3，9Ｄ.3，9，6100．設(shè)有一個10階的對稱矩陣Ａ,采用壓縮存儲的方式,將其下三角部分以行序為主存儲到一維數(shù)組B中（數(shù)組下標從1開始）,則矩陣中元素戊．s在一維數(shù)組B中的下標是（)A.33B.32C.8５D.4110１．排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列(初始為空)的一端的方法,稱為(D)排序。A．歸并Ｂ.插人Ｃ.快速D.選擇1０2.排序算法中，從未排序序列中依次取出元素與已排序序列(初始為空)中的元素進行比較(規(guī)定比較次數(shù)盡量少),然后將其放入已排序序列的對的位置的方法是(Ｃ）。A.冒泡B.直接插入Ｃ.折半插入D．選擇排序二、填空題1．通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及集合、__線性__、_樹形＿_、圖狀__四種類型。2.通?？梢园岩槐揪哂胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成＿__樹形_結(jié)構(gòu)。3．設(shè)有一個單向鏈表，結(jié)點的指針域為nｅxt,頭指針為head，p指向尾結(jié)點,為了使該單向鏈表改為單向循環(huán)鏈表,可用語句___ｐ－>nｅxｔ=head;_____。4．要在一個單向鏈表中p所指向的結(jié)點之后插入一個s所指向的新結(jié)點,若鏈表中結(jié)點的指針域為next，可執(zhí)行_s->nｅxt＝ｐ->next;＿_＿和p－>next=ｓ；的操作。5.設(shè)有一個單向循環(huán)鏈表,頭指針為head,鏈表中結(jié)點的指針域為ｎｅxt,p指向尾結(jié)點的直接前驅(qū)結(jié)點，若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作_＿p->nexｔ=heａｄ；。6．設(shè)有一個非空的鏈棧，棧頂指針為hs,要進行出棧操作,用x保存出棧結(jié)點的值,棧結(jié)點的指針域為nｅxt,則可執(zhí)行x=hs->daｔa;＿__hｓ=ｈｓ->ｎｅxt;__。7．在一個鏈隊中,f和r分別為隊頭和隊尾指針,隊結(jié)點的指針域為next,則插入一個ｓ所指結(jié)點的操作為__ｒ－>ｎｅxｔ=s_;ｒ=s；８．在一個不帶頭結(jié)點的非空鏈隊中,f和r分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為datａ，指針域為next,若要進行出隊操作,并用變量x存放出隊元素的數(shù)據(jù)值,則相關(guān)操作為x=ｆ－＞ｄata；f＝f->next;。９．循環(huán)隊列的隊頭指針為f，隊尾指針為ｒ,當(dāng)＿r==f＿時表白隊列為空。1０．循環(huán)隊列的最大存儲空間為MaxＳｉｚｅ=８,采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針front=４，則當(dāng)隊尾指針rear=_4_時，隊列為空,當(dāng)ｒear＝_＿２＿__時,隊列有6個元素。11.稀疏矩陣存儲時，采用一個由＿_行號_＿、__＿列號_、__非零元__3部分信息組成的三元組唯一擬定矩陣中的一個非零元素。12．一棵二叉樹沒有單分支結(jié)點,有６個葉結(jié)點，則該樹總共有＿＿11_＿_個結(jié)點。１3.一棵二叉樹順序編號為6的結(jié)點(樹中各結(jié)點的編號與等深度的完全二叉樹中相應(yīng)位置上結(jié)點的編號相同),若它存在右孩子，則右孩子的編號為__＿_13____。14.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有__先序_、＿＿中序＿、__后序__三種。15.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為___圖狀___結(jié)構(gòu)。1６．把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為＿_物理(存儲）_結(jié)構(gòu)。１７．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_＿_樹形____＿結(jié)構(gòu)。efgibaefgibachd圖3gfabdgfabdec圖420.二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是_＿___錯誤____＿的。(回答對的或不對的）21．在隊列的順序存儲結(jié)構(gòu)中,當(dāng)插入一個新的隊列元素時,尾指針的值增1，當(dāng)刪除一個元素隊列時,頭指針的值增1。22．根據(jù)搜索方法的不同,圖的遍歷有__深度優(yōu)先、＿廣度優(yōu)先__＿兩種方法。23．循環(huán)隊列的引入，目的是為了克服假上溢。2４.通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成_＿__＿圖狀___結(jié)構(gòu)。25．結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為___圖狀__＿結(jié)構(gòu)。2６．要在一個單向鏈表中刪除p所指向的結(jié)點,已知q指向p所指結(jié)點的直接前驅(qū)結(jié)點，若鏈表中結(jié)點的指針域為ｎext,則可執(zhí)行_＿_＿ｑ-＞nexｔ=p－＞nexｔ;__。27.設(shè)有一個單向循環(huán)鏈表,結(jié)點的指針域為nｅxt，頭指針為ｈeａd，指針ｐ指向表中某結(jié)點,若邏輯表達式_＿_p-＞neｘt=＝ｈeaｄ;__＿＿_的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。28.設(shè)有一個鏈棧，棧頂指針為ｈｓ,現(xiàn)有一個ｓ所指向的結(jié)點要入棧，則可執(zhí)行操作_s->ｎext=hs;和hs=s;29．順序存儲字符串“AＢCD”需要占用__＿５__個字節(jié)。3０．循環(huán)隊列的最大存儲空間為MaｘSiｚe=6，采用少用一個元素空間以有效地判斷棧空或棧滿，若隊頭指針ｆroｎt=４，當(dāng)隊尾指針rｅar=_＿__３____時隊滿，隊列中共有_＿__5_＿＿＿個元素。3１.一棵二叉樹葉結(jié)點（終端結(jié)點）數(shù)為5,單分支結(jié)點數(shù)為2，該樹共有__11____個結(jié)點32．設(shè)一棵完全二叉樹,其最高層上最右邊的葉結(jié)點的編號為奇數(shù)，該葉節(jié)點的雙親結(jié)點的編號為10，該完全二叉樹一共有_____2１___個結(jié)點。３３．一棵二叉樹中順序編號為5的結(jié)點(樹中各結(jié)點的編號與等深度的完全二叉中相應(yīng)位置上結(jié)點的編號相同），若它存在左孩子,則左孩子的編號為_＿__1０_＿＿＿。3４.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_＿線性______結(jié)構(gòu)。３５．一棵有n個葉結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為2,則該樹共有_＿_２ｎ-１____個結(jié)點。３6.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是__對的＿＿＿＿的。(回答對的或不對的)3７．串的兩種最基本的存儲方式分別是_順序存儲＿____＿和＿＿_鏈式存儲_____。38．按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字關(guān)鍵字相等的記錄的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。39.設(shè)有一個不帶頭結(jié)點的單向循環(huán)鏈表，結(jié)點的指針域為next,指針p指向尾結(jié)點，現(xiàn)要使p指向第一個結(jié)點,可用語句__＿__＿＿ｐ=p-＞ｎeｘt;_。40.要在一個帶頭結(jié)點的單向循環(huán)鏈表中刪除頭結(jié)點，得到一個新的不帶頭結(jié)點的單向循環(huán)鏈表,若結(jié)點的指針域為next,頭指針為hｅad，尾指針為p，,則可執(zhí)行head＝head->ｎｅｘt；＿_＿_＿p->ｎｅｘt＝heａd；___。41．在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向_結(jié)點的直接后繼，另一個指向__結(jié)點的直接前驅(qū)。4２.設(shè)有一個頭指針為head的單向鏈表，p指向表中某一個結(jié)點,且有p－>ｎｅxt==ＮULL,通過操作___p－>next＝hｅad;__,就可使該單向鏈表構(gòu)導(dǎo)致單向循環(huán)鏈表。43．循環(huán)隊列的最大存儲空間為MaxSiｚe，隊頭指針為f，隊尾指針為r,當(dāng)_（r＋1)%MaｘSｉｚe＝f_時表白隊列已滿。4４．從一個棧頂指針為h的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值,可執(zhí)行ｘ=h－＞ｄａｔa；和___h=h-＞neｘt；。(結(jié)點的指針域為neｘt)4５．程序段inｔｃount＝0;cｈar＊s=”ＡＢCＤ”；whiｌｅ(*s!=’\０’){s++；couｎt+＋；}執(zhí)行后ｃｏｕnt＝＿_4_。46.兩個串相等的充足必要條件是_串長度相等且相應(yīng)位置的字符相等。47．一棵二叉樹總結(jié)點數(shù)為11,葉結(jié)點數(shù)為5，該樹有__4＿_個雙分支結(jié)點,__2__個單分支結(jié)點。48.對二叉樹的遍歷可分為__先序、中序、后序、層次四種不同的遍歷順序。４9.設(shè)一棵完全二叉樹,其最高層上最右邊的葉結(jié)點的編號為偶數(shù)，該葉節(jié)點的雙親結(jié)點的編號為9,該完全二叉樹一共有＿_＿_18__＿_個結(jié)點。50.雙向循環(huán)鏈表中，ｐ指向表中某結(jié)點，則通過p可以訪問到ｐ所指結(jié)點的直接后繼結(jié)點和直接前驅(qū)結(jié)點，這種說法是__對的___＿__的(回答對的或不對的)。51．棧和隊列的操作特點分別是＿_先進后出（后進先出）_和＿_先進先出（后進后出)＿__。52.一棵有１4個結(jié)點的完全二叉樹，則它的最高層上有_＿__7___個結(jié)點。efgibacefgibachd圖２５4.折半查找只合用于順序存儲結(jié)構(gòu)存儲的有序表。55．哈希函數(shù)是記錄關(guān)鍵字值與該記錄___存儲地址__＿之間所構(gòu)造的相應(yīng)關(guān)系。56．深度為k的二叉樹最多有2k-１結(jié)點。５７．二叉樹排序中任一棵子樹都是二叉排序樹，這種說法是__對的_＿___的。(回答對的或不對的）58.串的兩種最基本的存儲方式是_＿＿順序存儲_和鏈式存儲__59．結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為___＿_圖狀＿__結(jié)構(gòu)。60.設(shè)有一個鏈棧,棧頂指針為ｈs,現(xiàn)有一個ｓ所指向的結(jié)點要入棧,則可執(zhí)行操作s-＞next=hs;_hs=s;。61．循環(huán)隊列的最大存儲空間為MaxＳｉｚe＝6,采用少用一個元素空間以有效地判斷?？栈驐M，若隊頭指針ｆront=４,當(dāng)隊尾指針rｅar＝__３__時隊滿，隊列中共有___５__個元素。62．‘Ａ‘在存儲時占＿_1_個字節(jié)?！癆”在存儲時占__2__個字節(jié)。6３.程序段char*ｓ=”ａBcD”；n=0;ｗhｉlｅ（＊s!=’\０’）{ｉf(*s>＝’a’＆＆*s<=’z’)n+＋;s＋+;｝執(zhí)行后n=__＿2_＿_三、綜合題１.（1）已知某二叉樹的后序遍歷序列是ｄebca,中序遍歷序列是dbeａc,試畫出該二叉樹（2）若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)(其中沒有相等的)，并恰好使該樹成為一棵二叉排序樹,試給出a、b、c、d、ｅ的大小關(guān)系ababced答:(１)（２）d<ｂ<ｅ<a＜c(３）abdec２．（1)設(shè)ｈead１和ｐ１分別是不帶頭結(jié)點的單向鏈表A的頭指針和尾指針，ｈeａd2和p2分別是不帶頭結(jié)點的單向鏈表B的頭指針和尾指針,若要把B鏈表接到A鏈表之后,得到一個以head1為頭指針的單向循環(huán)鏈表,寫出其中兩個關(guān)鍵的賦值語句（不用完整程序,結(jié)點的鏈域為next)。（2）單向鏈表的鏈域為nｅxt,設(shè)指針ｐ指向單向鏈表中的某個結(jié)點，指針s指向一個要插入鏈表的新結(jié)點,現(xiàn)要把s所指結(jié)點插入p所指結(jié)點之后，某學(xué)生采用以下語句:p-＞ｎext＝ｓ;s-＞next=p-＞next；這樣做對的嗎?若對的則回答對的，若不對的則說明應(yīng)如何改寫答：（1）p１-＞neｘt＝heａｄ2；ｐ2->ｎeｘt=head１;(2)不對，s-＞ｎeｘt＝p-＞next；ｐ-＞next＝s;３.(1）設(shè)有一個整數(shù)序列｛40,28,6,72,1０0,3,５４｝依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹40284028723100546答:（1)（2）ASL=（1x1+２x2＋3x3+4)/７=18／74.（１）畫出對長度為10的有序表進行折半查找的鑒定樹（以序號1，2,……10表達樹結(jié)點)（2）對上述序列進行折半查找，求等概率條件下，成功查找的平均查找長度528452849631071（２)AＳL=(1x１+2ｘ2+3x4＋4x3）/１0=29/１05．（1)運用篩選過程把序列{42,82，６7,10２，16,3２，５7,5２}建成堆（小根堆)，畫出相應(yīng)的完全二叉樹（不規(guī)定中間過程）（2）寫出對上述堆相應(yīng)的完全二叉樹進行中序遍歷得到的序列16423252571642325257678210242826752573216102初始樹堆初始樹堆（2）10２，5２，42,８２,16，67，32,５76．（1）運用篩選法,把序列｛37,77,６２，97,1１，2７，５２，47}建成堆（小根堆）,畫出相應(yīng)的完全二叉樹（2）寫出對上述堆所相應(yīng)的二叉樹進行前序遍歷得到的序列初始樹堆答:（1）初始樹堆373777624752271197(2）11，３7,4７,97,７7,27,6２，5２7．(1）一組記錄的關(guān)鍵字序列為{４5,40,65，４３,３５,9５}寫出運用快速排序的方法,以第一個記錄為基準得到的一趟劃分的結(jié)果(規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果)（2）同樣對序列{４5,40，65,4３,3５,95}運用直接插入排序，寫出逐次插入過程(從第一個元素一直到第六個元素)。答：（1)４5４0６5４３35９5(2）4０４565433595３５4０6５４3３５9５404345６53５９５35４0654365953５404３４565953５404343659５8．設(shè)有一個不帶頭結(jié)點的單向鏈表,頭指針為heaｄ,結(jié)點類型為NODＥ，每個結(jié)點包含一個數(shù)據(jù)域data和一個指針域nｅxt，該鏈表有兩個結(jié)點，p指向第二個結(jié)點（尾結(jié)點),按以下規(guī)定寫出相應(yīng)語句(不規(guī)定完整程序，(1)、（2)、(3)、(4）是一個連續(xù)的過程）。(１)新開辟一個結(jié)點,使指針s指向該結(jié)點，結(jié)點的數(shù)據(jù)成員data賦值為1(２）把該結(jié)點插入鏈表的尾部,釋放指針ｓ的指向(3)刪除鏈表的第一個結(jié)點（4)已知p1指向另一個新結(jié)點,把它插入到p所指結(jié)點和尾結(jié)點之間答:(1)ｓ＝(NＯDE*)malloc(siｚeof(NODＥ)）;ｓ->data＝1；（2)p->neｘt=s;s－>nｅxｔ=ＮULL；free（s)(3)hｅａd=hｅad-＞neｘｔ；（4）p1->ｎeｘｔ=ｐ->neｘt；113727475211372747526277979.(1)運用篩選過程把序列｛4２，82,６7,102,16，3２,57，5２}建成堆(小根堆),畫出相應(yīng)的完全二叉樹（不規(guī)定中間過程）（2)寫出對上述堆相應(yīng)的完全二叉樹進行中序遍歷得到的序列答：（1）16421642325257678210242826752573216102初始樹初始樹堆(２）１02,52，42，82,１6,６7,3２，5７1０.(1）設(shè)有序列{10，12，15,19,２2,2５,100，130,150，200｝畫出對上述序列進行折半查找的鑒定樹(以序列中的元素作為樹的結(jié)點）2212221213019150251520010010答:（1）（2)4次;3次1１.(1）設(shè)有一個整數(shù)序列{５0,38,16,82，11０，１3，６4},依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹（2）運用上述二叉排序樹,為了查找110，經(jīng)多少次元素間的比較能成功查到，為了查找15,經(jīng)多少次元素間的比較可知道查找失敗。答:5038503882131106416(2）三次;四次１2.(1)設(shè)有查找表{5，14,2,6,1８,7,4,16,３},依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。24246167318514答：(1)（２)中序遍歷:中序2,3，4，5,6，7，1４,1６,1813.（１）已知某二叉樹的先序遍歷序列是aeｃdb，中序遍歷序列是eaｄcｂ,試畫出該二叉樹(2）給出上述二叉樹的后序遍歷序列(3）若上述二叉樹的各個結(jié)點的字符分別是1,2，3，4，５,并恰好使該樹成為一棵二叉排序樹,試問a、ｂ、c、d、e的值各為多少？aecbaecbd（2)edbca（3）e=1,a＝2,d＝3,c=4，ｂ＝514.(1)設(shè)有一個整數(shù)序列｛40，2８,6,7２,100，３，５4｝依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(2)對上述二叉排序樹,在等概率條件下,求成功查找的平均查找長度答:(１）404028723100546（2)AＳL=（1x１+2x2+３x3+4)/７=18/71５.(1）給定數(shù)列{8,17，５,９,２１,10，７，19,6}，依次取序列中的數(shù)構(gòu)造一棵二叉排序樹(2）對上述二叉樹給出中序遍歷得到的序列851768517621971910（2)5，６，7,8，9,10，17,１8,19，211６．(1）運用篩選過程把序列{42,8２，67,１02，1６,32,57，52}建成堆(小根堆），畫出相應(yīng)的完全二叉樹（不規(guī)定中間過程)(２）寫出對上述堆相應(yīng)的完全二叉樹進行中序遍歷得到的序列1642164232525767821024282675242826752573216102初始樹堆初始樹堆（2）10２,５２,42,82，16，67,３2，5７17．（1）以給定權(quán)重值１，2，12,13，20,2５為葉結(jié)點，建立一棵哈夫曼樹(２)若哈夫曼樹有n個非葉子結(jié)點,則樹中共有多少結(jié)點。對給定的一組權(quán)重值建立的棵哈夫曼樹是否一定唯一答：（1)28284513213573209131525012321（2)2ｎ-1不一定唯一四、程序填空題１．以下函數(shù)在a［0]到a［ｎ-1]中,用折半查找算法查找關(guān)鍵字等于k的記錄,查找成功返回該記錄的下標,失敗時返回-１,完畢程序中的空格ｔypｅdefstrｕct{intkｅy；……}ＮOＤE;ｉｎｔBinary_Ｓearch(NODEa[]，intn，iｎtk)｛intｌｏw,mid,hiｇｈ;low=0；high=n-1;whｉｌe(__＿low<=hiｇｈ_＿＿__）{mｉd=(lｏｗ+high)/２；if(a[ｍid].keｙ==k)rｅtuｒｎ__ｍｉd)＿_____; elsｅif（_＿_a[mid].keｙ<k；＿____)low=ｍid+1; eｌse_＿high＝mid-1___；?｝＿_＿returｎ-１____； }2．以下函數(shù)為直接選擇排序算法,對a[1],a[２],…a[n]中的記錄進行直接選擇排序，完畢程序中的空格tｙpｅdefstｒuｃt{ｉntkeｙ；……}NODE;vｏiｄseｌsoｒt（NODEa［],intn)｛?ｉnｔi,j，k;?NODEtｅｍp；?fｏr(ｉ=１;i＜=_＿n-１__;i++)?{? k＝i；??ｆor(ｊ=i+1;j<＝＿__ｎ＿_＿__;ｊ++)???if(a[j].ｋｅy<ａ［ｋ]．