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

數(shù)據(jù)結(jié)構(gòu)（本)期末綜合練習(xí)一一、單項(xiàng)選擇題1.數(shù)據(jù)元素是數(shù)據(jù)的基本單位,它()。A．只能有一個(gè)數(shù)據(jù)項(xiàng)組成B.至少有二個(gè)數(shù)據(jù)項(xiàng)組成Ｃ．至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類型Ｄ．可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成2．()是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集。A．?dāng)?shù)據(jù)對(duì)象B．?dāng)?shù)據(jù)元素C．?dāng)?shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)項(xiàng)３．線性表的順序結(jié)構(gòu)中,（)。A．邏輯上相鄰的元素在物理位置上不一定相鄰B．邏輯上相鄰的元素在物理位置上也相鄰C.數(shù)據(jù)元素是不能隨機(jī)訪問的D.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高4.設(shè)鏈表中的結(jié)點(diǎn)是ＮＯDE類型的結(jié)構(gòu)體變量,且有NODＥ*ｐ；為了申請(qǐng)一個(gè)新結(jié)點(diǎn)，并由p指向該結(jié)點(diǎn),可用以下語(yǔ)句（)。A．p=(ＮＯDE*)ｍalloc（ｓizeof(ｐ));B.p=(*NODE)ｍａlｌｏc(sｉzｅof(ＮOＤE)）;C.p＝(NODE)malloｃ(siｚeof（p)）；D．p＝(NODE*)mａlｌoc(sizeof(ＮODE));5．以下表中可以隨機(jī)訪問的是(）。A.單向鏈表Ｂ．順序表C．單向循環(huán)鏈表D．雙向鏈表6.設(shè)順序存儲(chǔ)的線性長(zhǎng)度為ｎ,要在第i個(gè)元素之前插入一個(gè)新元素,按課本的算法當(dāng)i=()時(shí)，移動(dòng)元素次數(shù)為2A.n/2B．nC.n－17．設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，對(duì)于刪除操作，設(shè)刪除位置是等概率的,則刪除一個(gè)元素平均移動(dòng)元素的次數(shù)為(）。Ａ．(ｎ+1）/2B．ｎC.2nD.ｎ-i8．一個(gè)棧的進(jìn)棧序列是1，2，3，4,則棧的不也許的出棧序列是()(進(jìn)出棧操作可以交替進(jìn)行）A.３,２,4,1B．３，2,1，4C.4,３，2，1D.１,4，２，３9.設(shè)top是一個(gè)鏈棧的棧頂指針,棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域ｄａt(yī)ａ和指針域next組成,設(shè)用x接受棧頂元素,則出棧操作為()。A.ｔop=top->nｅxt;x=ｔop－>datａ;B.x=tｏｐ-＞data;top＝ｔop-＞nexｔ;C.ｘ=top-＞nｅxt;ｔop=toｐ－>data;D.tｏp->next=toｐ;ｘ=top－>dａｔa;１0．設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域ｄatａ和指針域next組成，froｎt和reaｒ分別為鏈隊(duì)列的頭指針和尾指針。設(shè)p指向要入隊(duì)的新結(jié)點(diǎn)(該結(jié)點(diǎn)已被賦值)，則入隊(duì)操作為(）。A．ｒear->next＝p;ｒeａｒ=ｐ；B.rear－>nｅxt=p;ｐ=rear;C.ｐ=reaｒ－>ｎext;rear=p；Ｄ．reaｒ=ｐ;reａr->nｅｘt＝ｐ;１1．以下說法對(duì)的的是（)。A．隊(duì)列是后進(jìn)先出B．棧的特點(diǎn)是后進(jìn)后出Ｃ.棧的刪除和插入操作都只能在棧頂進(jìn)行D.隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行1２．以下說法不對(duì)的的是(）。A.順序棧中，棧滿時(shí)再進(jìn)行進(jìn)棧操作稱為“上溢”B.順序棧中，?？諘r(shí)再作出棧棧操作稱為“下溢”Ｃ.順序隊(duì)列中,隊(duì)列的頭指針和尾指針均超越隊(duì)列存儲(chǔ)空間的上界,則隊(duì)列已空Ｄ.順序隊(duì)列中，當(dāng)尾指針已經(jīng)超越隊(duì)列存儲(chǔ)空間的上界，則一定是隊(duì)列已滿13．串函數(shù)StrCｍp(“abA”,”aｂa”)的值為(）。A．1B.0Ｃ.“abＡａbａ”D１4．設(shè)有一個(gè)2０階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式,將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組中(矩陣Ａ的第一個(gè)元素為a1１,數(shù)組b的下標(biāo)從1開始），則矩陣元素a8,５在一維數(shù)組b中的下標(biāo)是（)。Ａ．30B.2８C.4０D15．設(shè)有一個(gè)1２階的對(duì)稱矩陣Ａ，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中(矩陣A的第一個(gè)元素為a1,1,數(shù)組ｂ的下標(biāo)從１開始），則矩陣Ａ中第4行的元素在數(shù)組ｂ中的下標(biāo)i一定有()。A．7≤ｉ≤１0B．１1≤i≤15C.9≤ｉ≤14D．６≤i≤1６．深度為5的完全二叉樹第5層上有４個(gè)結(jié)點(diǎn),該樹一共有（）個(gè)結(jié)點(diǎn)。A.２８B．３0C．31D１７．已知一個(gè)圖的邊數(shù)為m,則該圖的所有頂點(diǎn)的度數(shù)之和為(）。A．２mB．mＣ.2m＋1D.m／218．已知一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m,則m一定不也許是(）。Ａ.4B.8Ｃ.12D19.以下說法不對(duì)的的是（)。A.連通圖G一定存在生成樹B.連通圖G的生成樹中一定包含G的所有頂點(diǎn)C．連通圖G的生成樹中不一定包含G的所有邊Ｄ.連通圖Ｇ的生成樹可以是不連通的２０.以下說法對(duì)的的是()。Ａ.連通圖G的生成樹中可以包含回路B.連通圖G的生成樹可以是不連通的C.連通圖G的生成樹一定是連通而不包含回路的Ｄ.連通圖G的生成樹一定是唯一的2１．散列查找的原理是()。A．在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立擬定的相應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C.按關(guān)鍵字值的比較進(jìn)行查找D.基于二分查找的方法２2.對(duì)n個(gè)元素進(jìn)行冒泡排序，通常要進(jìn)行ｎ-1趟冒泡，在第ｊ趟冒泡中共要進(jìn)行（）次元素間的比較。Ａ．jB.j－1C.n-jＤ23.排序過程中,每一趟從無序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序?yàn)橹?該排序算法是（)。A.直接插入排序B.快速排序C．冒泡排序D．選擇排序24．在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是(）。Ａ.冒泡B．選擇Ｃ.折半插入D.直接插入２5．采用順序查找法對(duì)長(zhǎng)度為ｎ的線性表進(jìn)行查找(不采用表尾設(shè)監(jiān)視哨的方法),最壞的情況下要進(jìn)行（)次元素間的比較。A．ｎ＋2B．nC.n-1D．n／２26．如圖若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點(diǎn)序列為（）。abecabecdfB．ａbeｄcfC．a(chǎn)cｅbdfＤ．ａcfbｄe圖127．如圖若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的頂點(diǎn)序列為（）。ababecdhgfB.aｅbcghdfＣ.aedfbcghＤ．ａｂecdfｇh圖228.一棵哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn)),該樹總共有（)個(gè)結(jié)點(diǎn)。A.2n-2Ｂ.2n-１C.２nD.29.一棵哈夫曼樹總共有23個(gè)結(jié)點(diǎn)，該樹共有（）個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）Ａ．10Ｂ．11Ｃ.12D．3０．?dāng)?shù)據(jù)的()結(jié)構(gòu)與所使用的計(jì)算機(jī)無關(guān)。A．邏輯Ｂ．物理C．存儲(chǔ)D.邏輯與存儲(chǔ)二、填空題1.通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及__＿_(dá)、＿_(dá)＿＿、＿_(dá)＿_(dá)、___＿四種類型。２．通?？梢园岩槐揪哂胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成＿＿_(dá)_＿_(dá)_＿結(jié)構(gòu)。3．設(shè)有一個(gè)單向鏈表,結(jié)點(diǎn)的指針域?yàn)椋頴xt,頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表,可用語(yǔ)句_＿_(dá)_____。4．要在一個(gè)單向鏈表中ｐ所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,可執(zhí)行________和p->nｅxt=s;的操作。5.設(shè)有一個(gè)單向循環(huán)鏈表，頭指針為hｅad,鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn),得到一個(gè)新的單向循環(huán)鏈表,可執(zhí)行操作_____＿_(dá)_。6.設(shè)有一個(gè)非空的鏈棧，棧頂指針為ｈs,要進(jìn)行出棧操作,用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚eｘt,則可執(zhí)行x=hs-＞ｄata;_____＿＿_(dá)。7.在一個(gè)鏈隊(duì)中，ｆ和ｒ分別為隊(duì)頭和隊(duì)尾指針,隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext,則插入一個(gè)s所指結(jié)點(diǎn)的操作為_______＿；ｒ=s；8．在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中,f和r分別為隊(duì)頭和隊(duì)尾指針,隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)椋鋋ｔａ,指針域?yàn)椋頴xt,若要進(jìn)行出隊(duì)操作，并用變量x存放出隊(duì)元素的數(shù)據(jù)值,則相關(guān)操作為x＝ｆ-＞ｄata;___＿_(dá)___。9.循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r,當(dāng)_____時(shí)表白隊(duì)列為空。１0.循環(huán)隊(duì)列的最大存儲(chǔ)空間為ＭａxSｉze=8,采用少用一個(gè)元素空間以有效的判斷?？栈驐M,若隊(duì)頭指針frｏｎt=4,則當(dāng)隊(duì)尾指針rｅar=_＿＿_(dá)__＿_(dá)時(shí)，隊(duì)列為空，當(dāng)ｒear=＿_(dá)___＿_(dá)_時(shí)，隊(duì)列有6個(gè)元素。11．“A”在存儲(chǔ)時(shí)占_______＿個(gè)字節(jié)。12．稀疏矩陣存儲(chǔ)時(shí),采用一個(gè)由____、_＿_(dá)_、____3部分信息組成的三元組唯一擬定矩陣中的一個(gè)非零元素。１3．一棵二叉樹沒有單分支結(jié)點(diǎn),有6個(gè)葉結(jié)點(diǎn),則該樹總共有___＿_(dá)__＿個(gè)結(jié)點(diǎn)。１4.一棵二叉樹順序編號(hào)為6的結(jié)點(diǎn)(樹中各結(jié)點(diǎn)的編號(hào)與等深度的完全二叉樹中相應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同),若它存在右孩子,則右孩子的編號(hào)為＿_(dá)_＿＿_(dá)__。15.按照二叉樹的遞歸定義，對(duì)二叉樹遍歷的常用算法有__＿_(dá)、____、__＿＿三種。16.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為________結(jié)構(gòu)。1７.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_______＿結(jié)構(gòu)。1８．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為＿_(dá)_＿_(dá)__＿結(jié)構(gòu)。19．如圖3所示的二叉樹,其后序遍歷序列為。eefgibachd圖320.如圖４所示的二叉樹，其前序遍歷序列為_＿_(dá)___＿＿_(dá)。ggfabdec圖４21．二叉樹為二叉排序的充足必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是__________的。(回答對(duì)的或不對(duì)的)22.在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，指針的值增1，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，指針的值增1。２3．根據(jù)搜索方法的不同，圖的遍歷有____、____兩種方法24.循環(huán)隊(duì)列的引入,目的是為了克服。三、綜合題1．(1)已知某二叉樹的后序遍歷序列是ｄebca，中序遍歷序列是ｄｂｅac，試畫出該二叉樹(2)若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)(其中沒有相等的),并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系(3）給出該樹的前序遍歷序列2.（１)設(shè)head1和p1分別是不帶頭結(jié)點(diǎn)的單向鏈表Ａ的頭指針和尾指針,hｅａd2和p2分別是不帶頭結(jié)點(diǎn)的單向鏈表B的頭指針和尾指針,若要把B鏈表接到A鏈表之后，得到一個(gè)以ｈeaｄ1為頭指針的單向循環(huán)鏈表,寫出其中兩個(gè)關(guān)鍵的賦值語(yǔ)句（不用完整程序,結(jié)點(diǎn)的鏈域?yàn)閚ｅｘt)。（2）單向鏈表的鏈域?yàn)椋頴xｔ，設(shè)指針p指向單向鏈表中的某個(gè)結(jié)點(diǎn),指針s指向一個(gè)要插入鏈表的新結(jié)點(diǎn)，現(xiàn)要把s所指結(jié)點(diǎn)插入p所指結(jié)點(diǎn)之后,某學(xué)生采用以下語(yǔ)句：p->nｅｘt=s;ｓ->ｎｅxt=ｐ->next；這樣做對(duì)的嗎?若對(duì)的則回答對(duì)的,若不對(duì)的則說明應(yīng)如何改寫3.（1）設(shè)有一個(gè)整數(shù)序列{４０，２8，6,72，１00，3,5４}依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹(2)對(duì)上述二叉排序樹,在等概率條件下,求成功查找的平均查找長(zhǎng)度4．(1）畫出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的鑒定樹(以序號(hào)1,2,……10表達(dá)樹結(jié)點(diǎn))（2）對(duì)上述序列進(jìn)行折半查找，求等概率條件下,成功查找的平均查找長(zhǎng)度５.（１)運(yùn)用篩選過程把序列{42，82,6７，102,16，3２，57,52}建成堆(小根堆),畫出相應(yīng)的完全二叉樹（不規(guī)定中間過程)(2）寫出對(duì)上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列6．（1)運(yùn)用篩選法，把序列{３7,77，6２，９7,１1，27，52，4７}建成堆(小根堆)，畫出相應(yīng)的完全二叉樹（2)寫出對(duì)上述堆所相應(yīng)的二叉樹進(jìn)行前序遍歷得到的序列四、程序填空題1．以下函數(shù)在a[0]到a［n-1]中,用折半查找算法查找關(guān)鍵字等于ｋ的記錄,查找成功返回該記錄的下標(biāo)，失敗時(shí)返回－1，完畢程序中的空格typedefsｔrｕct{inｔkey;……}NOＤＥ;intBinａry_Search（NODEa[],intn，intk）{iｎtlow,mｉｄ,ｈigh;low=0；hiｇh＝n－１；ｗhilｅ(_＿_(dá)(1)_____){mid=(lｏw+ｈigh)/2;iｆ(a[ｍｉd］.key==k）return_＿（2)＿_(dá)_＿_(dá)_;?ｅlseif(___(3)＿_(dá)_＿_(dá))ｌow=mid+1; ｅlｓe_＿(4)__＿_(dá)＿_(dá)； }___(5）_____； }2．以下函數(shù)為直接選擇排序算法,對(duì)a[１],a[2],…a[n］中的記錄進(jìn)行直接選擇排序,完畢程序中的空格tyｐedｅｆｓtｒuct{intkｅy;……}NＯＤE;voidsｅｌsｏrt（NOＤＥa[］,ｉｎｔn)｛?inｔi,ｊ，k; NODEtemp； for(i=1;i<=＿_(dá)_(1)＿_(dá)＿＿_(dá);i＋+）?{? ｋ=i; for(ｊ=i+1;j<=＿_(dá)＿(2)_＿_(dá)＿_(dá);j＋+)? ?ｉf（ａ［j].key<a［ｋ].keｙ)__(３)_＿_(dá)__＿;? if(ｉ!=k）??{???temp＝a[i]; ___(4)_＿_(dá)＿_(dá)； ___＿(5)____；??} }}3．以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值,front、reａr分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針stｒuｃtnｏde{ElemTypｅdａｔａ;stｒuctnoｄe*nｅｘt；｝;sｔruｃtnode＊front，*rear;voiｄInQuｅue(ElemTypex){structnoｄe＊p;p＝(sｔructnｏde*)＿＿_(dá)（1）_＿_(dá)_＿；p->ｄａt(yī)a=ｘ;p->next=NＵLＬ;_＿_(dá)(2)_＿＿_(dá)_;reaｒ＝_＿_(dá)(3）＿_(dá)___；｝4．以下程序是中序遍歷二叉樹的遞歸算法的程序，完畢程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right,數(shù)據(jù)域ｄaｔa為字符型,BT指向根結(jié)點(diǎn)）。voｉdInordeｒ(stｒｕctBＴｒｅｅＮｏde*BT){iｆ(ＢＴ!=NULL）{（1);(2）;（３)；}}答案一、單項(xiàng)選擇題1.D2．A3.Ｂ4．D5.Ｂ6．C7.A8.D9.Ｂ1０.Ａ11.C12.D13．D14．D1５．A１6.D１7．A18．D１9．D２0.Ｃ21．A22．C2３．A2４．C25．B26．Ｂ27．D28.B29.C30.Ａ二、填空題1.集合;線性；樹形；圖狀2．樹形3．ｐ－＞ｎexｔ=head；4.s->ｎｅxt=p->ｎｅｘt;５．p－>nexｔ＝heａd；6.ｈs=hｓ->nexｔ;7.r->nexｔ=ｓ8.f=f－>nｅxｔ;９．