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

PAGEPAGE1數(shù)據(jù)構(gòu)造〔本〕期末綜合練習(xí)期末綜合練習(xí)一一、單項(xiàng)選擇題1．?dāng)?shù)據(jù)的物理構(gòu)造〔D〕。A．與數(shù)據(jù)的邏輯構(gòu)造無(wú)關(guān)B．僅僅包括數(shù)據(jù)元素的表示C．只包括數(shù)據(jù)元素間關(guān)系的表示D．包括數(shù)據(jù)元素的表示和關(guān)系的表示2．?dāng)?shù)據(jù)元素是數(shù)據(jù)的根本單位，它〔C〕。A．只能有一個(gè)數(shù)據(jù)項(xiàng)組成B．至少有二個(gè)數(shù)據(jù)項(xiàng)組成C．可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)組成D．至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類(lèi)型3．從n個(gè)數(shù)中選取最大元素，〔C〕。A．根本操作是數(shù)據(jù)元素間的交換B．算法的時(shí)間復(fù)雜度是O(n2)C．算法的時(shí)間復(fù)雜度是O(n)D．需要進(jìn)展(n+1)次數(shù)據(jù)元素間的比擬4．線性表的順序構(gòu)造中，〔C〕。A．邏輯上相鄰的元素在物理位置上不一定相鄰B．?dāng)?shù)據(jù)元素是不能隨機(jī)訪問(wèn)的C．邏輯上相鄰的元素在物理位置上也相鄰D．進(jìn)展數(shù)據(jù)元素的插入、刪除效率較高5．以下表中可以隨機(jī)訪問(wèn)的是〔D〕。A．單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D．順序表6．帶頭結(jié)點(diǎn)的單向鏈表為空的判斷條件是〔B〕〔設(shè)頭指針為head〕。A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL7.設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，對(duì)于刪除操作，設(shè)刪除位置是等概率的，那么刪除一個(gè)元素平均挪動(dòng)元素的次數(shù)為〔A〕。A．(n+1)/2B．nC．2nD．n-i8．線性構(gòu)造中數(shù)據(jù)元素的位置之間存在〔A〕的關(guān)系。A．一對(duì)一B．一對(duì)多C．多對(duì)多D．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼9．設(shè)top是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，那么出棧操作為〔A〕。A．x=top->data;top=top->next;B．top=top->next;x=top->data;C．x=top->next;top=top->data;D．top->next=top;x=top->data;10．設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，要?jiǎng)h除第i個(gè)元素，按課本的算法，當(dāng)i=〔C〕時(shí)，挪動(dòng)元素的次數(shù)為3A．3B．n/2C．n-3D11．以下說(shuō)法正確的選項(xiàng)是〔C〕。A．隊(duì)列是后進(jìn)先出B．棧的特點(diǎn)是后進(jìn)后出C．棧的刪除和插入操作都只能在棧頂進(jìn)展D．隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)展12.以下說(shuō)法不正確的選項(xiàng)是〔C〕。A．棧的特點(diǎn)是后進(jìn)先出B．隊(duì)列的特點(diǎn)是先進(jìn)先出C．棧的刪除操作在棧底進(jìn)展，插入操作在棧頂進(jìn)展D．隊(duì)列的插入操作在隊(duì)尾進(jìn)展，刪除操作在隊(duì)頭進(jìn)展13．串函數(shù)StrCmp(“abA〞,〞aba〞)的值為〔D〕。A．1B．0C．“abAaba〞D14．一個(gè)棧的進(jìn)棧序列是a，b，c，d，那么棧的不可能的出棧序列是〔A〕。A．a(chǎn)dbcB．bcadC．cbadD．dcba15．設(shè)有一個(gè)12階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式將其下三角局部以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中〔矩陣A的第一個(gè)元素為a1,1，數(shù)組b的下標(biāo)從1開(kāi)場(chǎng)〕，那么矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有〔A〕。A．7≤i≤10B．11≤i≤15C．9≤i≤14D．6≤i≤16．一個(gè)圖的邊數(shù)為m，那么該圖的所有頂點(diǎn)的度數(shù)之和為〔A〕。A．2mB．mC．2m+1D．m/217．設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊(duì)列的頭指針和尾指針，要執(zhí)行出隊(duì)操作，用x保存出隊(duì)元素的值，p為指向結(jié)點(diǎn)類(lèi)型的指針，可執(zhí)行如下操作：p=front->next;x=p->data;然后執(zhí)行〔B〕。A．front=p->next;B．front->next=p->next;C．front=p;D．front->next=p;18．以下說(shuō)法不正確的選項(xiàng)是〔D〕。A．連通圖G一定存在生成樹(shù)B．連通圖G的生成樹(shù)中一定包含G的所有頂點(diǎn)C．連通圖G的生成樹(shù)中不一定包含G的所有邊D．連通圖G的生成樹(shù)可以是不連通的19．散列查找的原理是〔A〕。A．在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立確定的對(duì)應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C．按關(guān)鍵字值的比擬進(jìn)展查找D．基于二分查找的方法20．空串的長(zhǎng)度為〔A〕。A．0B．1C．2D21．排序過(guò)程中，每一趟從無(wú)序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序?yàn)橹?，該排序算法?D)。A．選擇排序B．快速排序C．冒泡排序D．直接插入排序22．采用順序查找法對(duì)長(zhǎng)度為n的線性表進(jìn)展查找〔不采用表尾設(shè)監(jiān)視哨的方法〕，最壞的情況下要進(jìn)展〔B〕次元素間的比擬。A．n+2B．nC．n-1D．n/223．設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式將其下三角局部以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中?！簿仃嘇的第一個(gè)元素為a1,1，數(shù)組b的下標(biāo)從1開(kāi)場(chǎng)〕，那么矩陣元素a5,3對(duì)應(yīng)一維數(shù)組b的數(shù)組元素是〔C〕。A．b[18]B．b[8]C．b[13]D．b[10]24．如圖1假設(shè)從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)展遍歷，那么可能得到的頂點(diǎn)序列為〔D〕。ababecdhgfB．a(chǎn)ebcghdfC．a(chǎn)edfbcghD．a(chǎn)becdfgh圖125．如圖2所示的一個(gè)圖，假設(shè)從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)展遍歷，那么可能得到的一種頂點(diǎn)序列為〔D〕。A．a(chǎn)becdfB．a(chǎn)cfebdC．a(chǎn)ebcfdD．a(chǎn)edfcbbbdfeca圖226．一棵哈夫曼樹(shù)總共有23個(gè)結(jié)點(diǎn)，該樹(shù)共有〔D〕個(gè)葉結(jié)點(diǎn)〔終端結(jié)點(diǎn)〕。A．10B．13C．11二、填空題1．通常數(shù)據(jù)的邏輯構(gòu)造包括集合、線性、_樹(shù)形_、_圖狀四種類(lèi)型。2．通常可以把某城市中各公交站點(diǎn)間的線路圖抽象成__圖狀__構(gòu)造。3．設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語(yǔ)句___p->next=head;_____。4．設(shè)有一個(gè)單向循環(huán)鏈表，頭指針為head，鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，假設(shè)要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)鏈表，可執(zhí)行操作________p->next=head。5．循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)___r=f_____時(shí)說(shuō)明隊(duì)列已空。6．在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，那么插入一個(gè)s所指結(jié)點(diǎn)的操作為_(kāi)__r->next=s___；r=s；7．設(shè)有一個(gè)鏈棧，棧頂指針為hs，現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，那么可執(zhí)行操作__s->next=hs和hs=s；8．循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)___r==f_時(shí)說(shuō)明隊(duì)列為空。9．在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，那么插入一個(gè)s所指結(jié)點(diǎn)的操作為_(kāi)_r->next=s___；r=s；10．“A〞在存儲(chǔ)時(shí)占___2____個(gè)字節(jié)。11．串的兩種最根本的存儲(chǔ)方式分別是_順序存儲(chǔ)__和__鏈?zhǔn)酱鎯?chǔ)__。12．一棵二叉樹(shù)沒(méi)有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，那么該樹(shù)總共有___11__個(gè)結(jié)點(diǎn)。13．一棵二叉樹(shù)中順序編號(hào)為i的結(jié)點(diǎn)，假設(shè)它存在左、右孩子，那么左、右孩子編號(hào)分別為_(kāi)___2i___、__2i+1___。14．按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有_先序、_中序_、_后序_三種。15．兩個(gè)串相等的充分必要條件是串長(zhǎng)度相等且對(duì)應(yīng)位置的字符相等。16．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并詳細(xì)表達(dá)數(shù)據(jù)之間的邏輯構(gòu)造稱(chēng)為_(kāi)物理〔存儲(chǔ)〕_構(gòu)造。17．一棵二叉樹(shù)葉結(jié)點(diǎn)〔終端結(jié)點(diǎn)〕數(shù)為5，單分支結(jié)點(diǎn)數(shù)為2，該樹(shù)共有__11__個(gè)結(jié)點(diǎn)。18．如圖3所示的二叉樹(shù)，其后序遍歷序列為gdbeihfca。eefgibachd圖319．根據(jù)搜索方法的不同，圖的遍歷有__深度優(yōu)先搜索遍歷_、_廣度優(yōu)先搜索遍歷方法。20．二叉樹(shù)為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是__錯(cuò)誤_____的。(答復(fù)正確或不正確)21．一個(gè)有序表{3，4，10，14，34，43，46，64，75，78，90，96，130}用折半查找法查找值為90的結(jié)點(diǎn)，經(jīng)___4____次比擬后查找成功。三、綜合題1．〔1〕某二叉樹(shù)的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫(huà)出該二叉樹(shù)ababced答：d<b<e<a<c〔3〕給出該樹(shù)的前序遍歷序列答：abdec2．〔1〕一組記錄的關(guān)鍵字序列為{45，40，65，43，35，95}，寫(xiě)出利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果〔要求給出一趟劃分中每次掃描和交換的結(jié)果〕答：454065433595354065433595354065436595354043436595354043456595〔2〕對(duì)序列{45，40，65，43，35，95}利用直接插入排序，寫(xiě)出逐次插入過(guò)程〔從第一個(gè)元素一直到第六個(gè)元素〕。答4045654335954043456535953540434565954028724028723100546〔2〕對(duì)上述二叉排序樹(shù)，在等概率條件下，求成功查找的平均查找長(zhǎng)度答：ASL=〔1x1+2x2+3x3+4〕/7=18/74．(1)設(shè)有查找表{5,14,2,6,18,7,4,16,3},依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù).242461673185145答：中序遍歷1642325216423252576782102初始樹(shù)堆4初始樹(shù)堆42826752573216102〔2〕寫(xiě)出對(duì)上述堆對(duì)應(yīng)的完全二叉樹(shù)進(jìn)展中序遍歷得到的序列答：102，52，42，82，16，67，32，57四、程序填空題1．以下函數(shù)在a[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回-1，完成程序中的空格typedefstruct{intkey;……}NODE;intBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0;high=n-1;while(__low<=high____){mid=(low+high)/2;if(a[mid].key==k)return__mid______; elseif(__a[mid].key<k;___)low=mid+1; else_high=mid-1_____; }__return-1____; }2．以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，top為棧頂指針structnode{ElemTypedata;structnode*next;};structnode*top;voidPush(ElemTypex){structnode*p;p=(structnode*)malloc(_sizeof(structnode)___);p->data=x;__p->next=top___;__top=p__;}3．以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、rear分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針structnode{ElemTypedata;structnode*next;};structnode*front，*rear;voidInQueue(ElemTypex){structnode*p;p=(structnode*)___malloc(sizeof(structnode))____;p->data=x;p->next=NULL;__rear->next=p____;rear=___p_____;}期末綜合練習(xí)二一、單項(xiàng)選擇題1．〔B〕是性質(zhì)一樣的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A．?dāng)?shù)據(jù)元素B．?dāng)?shù)據(jù)對(duì)象C．?dāng)?shù)據(jù)構(gòu)造D．?dāng)?shù)據(jù)項(xiàng)2．同一種邏輯構(gòu)造〔B〕。A．只能有唯一的存儲(chǔ)構(gòu)造B．可以有不同的存儲(chǔ)構(gòu)造C．只能表示某一種數(shù)據(jù)元素之間的關(guān)系D．以上三種說(shuō)法均不正確3．設(shè)鏈表中的結(jié)點(diǎn)是NODE類(lèi)型的構(gòu)造體變量，且有NODE*p；為了申請(qǐng)一個(gè)新結(jié)點(diǎn)，并由p指向該結(jié)點(diǎn)，可用以下語(yǔ)句〔A〕。A．p=(NODE*)malloc(sizeof(NODE));B．p=(*NODE)malloc(sizeof(NODE));C．p=(NODE)malloc(sizeof(p));D．p=(NODE*)malloc(sizeof(p));4．鏈表所具備的特點(diǎn)是〔C〕。A．可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B．占用連續(xù)的存儲(chǔ)空間C．插入刪除元素的操作不需要挪動(dòng)元素結(jié)點(diǎn)D．可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)展直接訪問(wèn)5．設(shè)順序存儲(chǔ)的線性長(zhǎng)度為n，要在第i個(gè)元素之前插入一個(gè)新元素，按課本的算法當(dāng)i=〔D〕時(shí)，挪動(dòng)元素次數(shù)為2A．n/2B．nC．1D．n-16．?dāng)?shù)據(jù)的物理構(gòu)造〔D〕。A．與數(shù)據(jù)的邏輯構(gòu)造無(wú)關(guān)B．僅僅包括數(shù)據(jù)元素的表示C．只包括數(shù)據(jù)元素間關(guān)系的表示D．包括數(shù)據(jù)元素的表示和關(guān)系的表示7．一個(gè)棧的進(jìn)棧序列是1，2，3，4，那么棧的不可能的出棧序列是〔B〕〔進(jìn)出棧操作可以交替進(jìn)展〕A．3，2，4，1B．1，4，2，3C．4，3，2，1D．3，2，1，48．線性構(gòu)造中數(shù)據(jù)元素的位置之間存在〔A〕的關(guān)系。A．一對(duì)一B．一對(duì)多C．多對(duì)多D．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼9．設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊(duì)列的頭指針和尾指針。設(shè)p指向要入隊(duì)的新結(jié)點(diǎn)(該結(jié)點(diǎn)已被賦值)，那么入隊(duì)操作為〔A〕。A．rear->next=p;rear=p;B．rear->next=p;p=rear;C．p=rear->next;rear=p;D．rear=p;rear->next=p;10．以下表中可以隨機(jī)訪問(wèn)的是〔D〕。A．單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D．順序表11．以下說(shuō)法不正確的選項(xiàng)是〔C〕。A．順序棧中，棧滿時(shí)再進(jìn)展進(jìn)棧操作稱(chēng)為“上溢〞B．順序棧中，棧空時(shí)再作出棧棧操作稱(chēng)為“下溢〞C．順序隊(duì)列中，當(dāng)尾指針已經(jīng)超越隊(duì)列存儲(chǔ)空間的上界，那么一定是隊(duì)列已滿D．順序隊(duì)列中，隊(duì)列的頭指針和尾指針均超越隊(duì)列存儲(chǔ)空間的上界，那么隊(duì)列已空12．算法的時(shí)間復(fù)雜度與〔C〕有關(guān)。A．所使用的計(jì)算機(jī)B．與計(jì)算機(jī)的操作系統(tǒng)C．與算法本身D．與數(shù)據(jù)構(gòu)造13．設(shè)有一個(gè)20階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，將其下三角局部以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組中〔矩陣A的第一個(gè)元素為a11，數(shù)組b的下標(biāo)從1開(kāi)場(chǎng)〕，那么矩陣元素a8,5在一維數(shù)組b中的下標(biāo)是〔D〕。A．30B．28C．40D14．設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素需挪動(dòng)元素的個(gè)數(shù)為〔B〕。A．n-i+1B．n-iC．n-i-1D．i15．深度為5的完全二叉樹(shù)第5層上有4個(gè)結(jié)點(diǎn)，該樹(shù)一共有〔D〕個(gè)結(jié)點(diǎn)。A．28B．30C．31D16．在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用的語(yǔ)句是〔C〕。A．p=q->nextB．p->next=qC．p->next=qnextD．q->next=NULL17．一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m，那么m一定不可能是〔D〕。A．4B．8C．12D18．從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保存被刪結(jié)點(diǎn)的值，那么執(zhí)行〔A〕。A．x=top->data;top=top->next;B．x=top->data;C．top=top->next;x=top->data;D．top=top->next;x=data;19．以下說(shuō)法正確的選項(xiàng)是〔D〕。A．連通圖G的生成樹(shù)中可以包含回路B．連通圖G的生成樹(shù)可以是不連通的C．連通圖G的生成樹(shù)一定是唯一的D．連通圖G的生成樹(shù)一定是連通而不包含回路的20．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，那么刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為〔C〕。A．r=f->next;B．r=r->next;C．f=f->next;D．f=r->next;21．對(duì)n個(gè)元素進(jìn)展冒泡排序，通常要進(jìn)展n-1趟冒泡，在第j趟冒泡中共要進(jìn)展〔C〕次元素間的比擬。A．jB．j-1C．n-jD22．一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，那么棧的不可能輸出序列是〔A〕〔進(jìn)棧出?？梢越惶孢M(jìn)展〕。A．dceabB．edcbaC．decbaD．a(chǎn)bcde23．在排序過(guò)程中，可以有效地減少一趟排序過(guò)程中元素間的比擬次數(shù)的算法是〔D〕。A．冒泡B．選擇C．直接插入D．折半插入24．有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)展查找，在等概率情況下查找成功的平均比擬次數(shù)為〔B〕。A．26/10B．29/10C25．如圖1假設(shè)從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)展遍歷，那么可能得到的頂點(diǎn)序列為〔B〕。abecabecdfB．a(chǎn)bedcfC．a(chǎn)cebdfD．a(chǎn)cfbde圖126．排序算法中，從未排序序列中依次取出元素與已排序序列〔初始為空〕中的元素進(jìn)展比擬〔要求比擬次數(shù)盡量少〕，然后將其放入已排序序列的正確位置的方法是〔C〕。A．冒泡B．直接插入C．折半插入D．選擇排序27．一棵哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)〔終端結(jié)點(diǎn)〕，該樹(shù)總共有〔B〕個(gè)結(jié)點(diǎn)。A．2n-2B．2n-1C．2nD28．設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角局部以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組B中〔數(shù)組下標(biāo)從1開(kāi)場(chǎng)〕，那么矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是〔A〕。A．33B．32C29．?dāng)?shù)據(jù)的〔A〕構(gòu)造與所使用的計(jì)算機(jī)無(wú)關(guān)。A．邏輯B．物理C．存儲(chǔ)D．邏輯與存儲(chǔ)30．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的〔D〕倍。A．3B．2.5C二、填空題1．通?？梢园岩槐竞胁煌鹿?jié)的書(shū)的目錄構(gòu)造抽象成___樹(shù)形__構(gòu)造。2．棧和隊(duì)列的操作特點(diǎn)分別是__先進(jìn)后出___和___先進(jìn)先出__。3．要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，假設(shè)鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行__s->next=p->next；______和p->next=s;的操作。4．構(gòu)造中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱(chēng)為_(kāi)___圖狀〔網(wǎng)狀〕__構(gòu)造。5．設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs，要進(jìn)展出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext，那么可執(zhí)行x=hs->data;___hs=hs->next;_____。6．根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通?？煞譃榧稀⒕€性、樹(shù)形、圖狀四類(lèi)根本構(gòu)造。7．在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata，指針域?yàn)閚ext，假設(shè)要進(jìn)展出隊(duì)操作，并用變量x存放出隊(duì)元素的數(shù)據(jù)值，那么相關(guān)操作為x=f->data;__f=f->next;______。8．要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)根本操作為元素間的比擬。那么比擬的次數(shù)和算法的時(shí)間復(fù)雜度分別為_(kāi)_______和_n-1,O(n)_______。9．循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxSize=8，采用少用一個(gè)元素空間以有效的判斷棧空或棧滿，假設(shè)隊(duì)頭指針front=4，那么當(dāng)隊(duì)尾指針rear=____4____時(shí)，隊(duì)列為空，當(dāng)rear=___2_____時(shí)，隊(duì)列有6個(gè)元素。10．稀疏矩陣存儲(chǔ)時(shí)，采用一個(gè)由__行號(hào)__、___列號(hào)_、__非零元__3局部信息組成的三元組唯一確定矩陣中的一個(gè)非零元素。11．在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)構(gòu)造中，通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是值域左指針、右指針。12．一棵二叉樹(shù)順序編號(hào)為6的結(jié)點(diǎn)〔樹(shù)中各結(jié)點(diǎn)的編號(hào)與等深度的完全二叉中對(duì)應(yīng)位置上結(jié)點(diǎn)的編號(hào)一樣〕，假設(shè)它存在右孩子，那么右孩子的編號(hào)為_(kāi)__13_____。13．向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行s->next=h;和__h=s__。14．在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，那么插入s所指結(jié)點(diǎn)的操作為_(kāi)_r->next=s__和r=s;(結(jié)點(diǎn)的指針域?yàn)閚ext)15．如圖2所示的二叉樹(shù)，其前序遍歷序列為_(kāi)__abdefcg__。ggfabdec圖216．設(shè)有一棵深度為4的完全二叉樹(shù)，第四層上有5個(gè)結(jié)點(diǎn)，該樹(shù)共有___12__個(gè)結(jié)點(diǎn)?！哺诮Y(jié)點(diǎn)為第1層〕17．在隊(duì)列的順序存儲(chǔ)構(gòu)造中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，尾指針的值增1，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，頭指針的值增1。18．對(duì)稀疏矩陣進(jìn)展壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的__行下標(biāo)_、__列下標(biāo)_和___非零元素值_三項(xiàng)信息。19．循環(huán)隊(duì)列的引入，目的是為了克制假上溢。20．在對(duì)一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)展直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比擬___3______次。三、綜合題1．〔1〕設(shè)head1和p1分別是不帶頭結(jié)點(diǎn)的單向鏈表A的頭指針和尾指針，head2和p2分別是不帶頭結(jié)點(diǎn)的單向鏈表B的頭指針和尾指針，假設(shè)要把B鏈表接到A鏈表之后，得到一個(gè)以head1為頭指針的單向循環(huán)鏈表，寫(xiě)出其中兩個(gè)關(guān)鍵的賦值語(yǔ)句〔不用完好程序，結(jié)點(diǎn)的鏈域?yàn)閚ext〕。答：p1->next=head2；p2->next=head1；〔2〕單向鏈表的鏈域?yàn)閚ext，設(shè)指針p指向單向鏈表中的某個(gè)結(jié)點(diǎn)，指針s指向一個(gè)要插入鏈表的新結(jié)點(diǎn)，現(xiàn)要把s所指結(jié)點(diǎn)插入p所指結(jié)點(diǎn)之后，某學(xué)生采用以下語(yǔ)句：p->next=s;s->next=p->next;這樣做正確嗎？假設(shè)正確那么答復(fù)正確，假設(shè)不正確那么說(shuō)明應(yīng)如何改寫(xiě)答：不對(duì)，s->next=p->next；p->next=s；2．(1)以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)(要求每個(gè)結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。3333(1)1518151879987998545432322：11103:11114：1107：008：019：10(2)一棵哈夫曼樹(shù)有n個(gè)葉結(jié)點(diǎn)，它一共有多少個(gè)結(jié)點(diǎn)？簡(jiǎn)述理由？答:2n-1個(gè)，因?yàn)榉侨~結(jié)點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個(gè)。3．〔1〕畫(huà)出對(duì)長(zhǎng)度為10的有序表進(jìn)展折半查找的斷定樹(shù)〔以序號(hào)1，2，……10表示樹(shù)結(jié)點(diǎn)〕5252849631071答：ASL=〔1x1+2x2+3x4+4x3〕/10=29/104．一組記錄的關(guān)鍵字序列為〔46，79，56，38，40，84〕〔1〕利用快速排序的方法，給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果〔給出逐次交換元素的過(guò)程，要求以升序排列〕初始序列46，79，56，38，40，8440，79，56，38，40，8440，79，56，38，79，8440，38，56，38，79，8440，38，56，56，79，8440，38，46，56，79，84〔2〕對(duì)上述序列用堆排序的方法建立大根堆，要求以二叉樹(shù)逐次描繪建堆過(guò)程。3777624752377762475227119711372747526277975679384084468479384046566567938404679384084845646初始樹(shù)堆初始樹(shù)堆〔2〕寫(xiě)出對(duì)上述堆所對(duì)應(yīng)的二叉樹(shù)進(jìn)展前序遍歷得到的序列答：11，37，47，97，77，27，62，526．設(shè)查找表為(50,60,75,85,96,98,105,110,120,130)(1)說(shuō)出進(jìn)展折半查找成功查找到元素120需要進(jìn)展多少次元素間的比擬？3次(2)為了折半查找元素95，經(jīng)過(guò)多少次元素間的比擬才能確定不能查到？4次967596759813010585501100512060四、程序填空題1．以下函數(shù)為直接選擇排序算法，對(duì)a[1],a[2],…a[n]中的記錄進(jìn)展直接選擇排序，完成程序中的空格typedefstruct{intkey;……}NODE;voidselsort(NODEa[],intn){ inti,j,k; NODEtemp; for(i=1;i<=__n-1___;i++) { k=i; for(j=i+1;j<=___n___;j++) if(a[j].key<a[k].key)__k=j_____; if(i!=k) { temp=a[i]; __a[i]=a[k]___; ___a[k]=temp_; } }}2．以下是用尾插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為1,2,3,……,n，完成程序中空格局部。NODE*create(n){NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;pnext=NULL;/*建立頭結(jié)點(diǎn)*/for(i=1;i<=n;i++){p=(NODE*)malloc(sizeof(NODE));pdata=i;pnext=NULL;qnext=p;q=p;}return(head);}3．以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格局部〔樹(shù)構(gòu)造中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)〕。voidInorder(structBTreeNode*BT){if(BT!=NULL){Inorder(BT->left);printf(“%c〞,BT->data);Inorder(BT->right);}}期末綜合練習(xí)三一、單項(xiàng)選擇題1．深度為5的完全二叉樹(shù)共有20個(gè)結(jié)點(diǎn)，那么第5層上有〔C〕個(gè)結(jié)點(diǎn)(根所在結(jié)點(diǎn)為第一層)。A．3B．8C．5D2．在C語(yǔ)言中，順序存儲(chǔ)長(zhǎng)度為3的字符串，需要占用〔A〕個(gè)字節(jié)。A．4B．3C3．一個(gè)圖的邊數(shù)為m，那么該圖的所有頂點(diǎn)的度數(shù)之和為〔A〕。A．2mB．mC．2m+1D．m/24．串函數(shù)StrCat〔a,b〕的功能是進(jìn)展串〔D〕。A．比擬B．復(fù)制C．賦值D．連接5．?dāng)?shù)據(jù)構(gòu)造中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的〔D〕構(gòu)造。A．物理B．存儲(chǔ)C．邏輯與物理D．邏輯6．一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)中，共有〔A〕個(gè)指針域?yàn)榭?。A．n+1B．nC．n-1D．n-27．鏈表所具備的特點(diǎn)是〔C〕。A．可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B．占用連續(xù)的存儲(chǔ)空間C．插入刪除不需要挪動(dòng)元素結(jié)點(diǎn)D．可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)展直接訪問(wèn)8．設(shè)一棵哈夫曼樹(shù)共有n個(gè)非葉結(jié)點(diǎn)，那么該樹(shù)有〔B〕個(gè)葉結(jié)點(diǎn)。A．nB．n+1C9．線性表只要以〔C〕方式存儲(chǔ)就能進(jìn)展折半查找。A．鏈接B．順序C．關(guān)鍵字有序的順序D．二叉樹(shù)10．從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保存被刪結(jié)點(diǎn)的值，那么執(zhí)行〔A〕。A．x=top->data;top=topnext;B．x=top->data;C．top=top->next;x=top->data;D．top=top->next;x=data;11．散列查找的原理是〔A〕。A．在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立確定的對(duì)應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C．按關(guān)鍵字值的比擬進(jìn)展查找D．基于二分查找的方法12．一棵完全二叉樹(shù)共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹(shù)共有〔C〕個(gè)結(jié)點(diǎn)。A．30B．20C13．對(duì)n個(gè)元素進(jìn)展冒泡排序假設(shè)某趟冒泡中只進(jìn)展了〔C〕次元素間的交換，那么說(shuō)明序列已經(jīng)排好序。A．1B．2C．0D14．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的〔D〕倍。A．3B．2.5C15．排序過(guò)程中，每一趟從無(wú)序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序?yàn)橹梗撆判蛩惴ㄊ?A)。A．直接插入排序B．快速排序C．冒泡排序D．選擇排序16．如圖1所示的一個(gè)圖，假設(shè)從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)展遍歷，那么可能得到的一種頂點(diǎn)序列為〔A〕。A．V1V2V4V8V5V3V6V7B．V1V2V4V5V8V3V6V7C．V1V2V4V8V3V5V6V7D．V1V3V6V7V2V4V5V8V6V6V7V1V2V3V8V4V5圖117．在對(duì)一組元素〔64，48，106，33，25，82，70，55，93〕進(jìn)展直接插入排序時(shí)，當(dāng)進(jìn)展到要把第7個(gè)元素70插入到已經(jīng)排好序的子表時(shí)，為找到插入位置，需進(jìn)展〔C〕次元素間的比擬〔指由小到大排序〕。A．6B．2C．3D18．如圖2所示的一個(gè)圖，假設(shè)從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)展遍歷，那么可能得到的一種頂點(diǎn)序列為〔B〕。A．a(chǎn)bcedfB．a(chǎn)bcefdC．a(chǎn)ebcfdD．a(chǎn)cfdebbdbdfeca圖219．采用順序查找法對(duì)長(zhǎng)度為n的線性表進(jìn)展查找〔不采用表尾設(shè)監(jiān)視哨的方法〕，最壞的情況下要進(jìn)展〔B〕次元素間的比擬。A．n+2B．nC．n-1D．n/220．對(duì)二叉排序樹(shù)進(jìn)展〔C〕遍歷，可以使遍歷所得到的序列是有序序列。A．按層次B．后序C．中序D．前序21．如圖3，假設(shè)從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)展遍歷，那么可能得到的頂點(diǎn)序列為〔B〕。A．a(chǎn)cebdgfB．a(chǎn)becdgfC．a(chǎn)cfedgbD．a(chǎn)becfdgaabecdfg圖322．在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120}中，用折半查找法查找值80時(shí)，經(jīng)〔B〕次比擬后查找成功。A．4B．2C．3D．523．元素2，4，6，8按順序依次進(jìn)棧，那么該棧的不可能輸出序列是〔D〕〔進(jìn)棧出?？梢越惶孢M(jìn)展〕。A．8，6，4，2B．2，4，6，8C．4，2，8，6D．8，6，2，424．有一個(gè)長(zhǎng)度為9的有序表，按折半查找對(duì)該表進(jìn)展查找，在等概率情況下查找成功的平均比擬次數(shù)為〔B〕。A．25/10B．25/9C25．排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列〔初始為空〕的一端的方法，稱(chēng)為〔C〕排序。A．歸并B．插入C．選擇D．快速26．排序算法中，從未排序序列中依次取出元素與已排序序列〔初始為空〕中的元素進(jìn)展比擬〔要求比擬次數(shù)盡量少〕，然后將其放入已排序序列的正確位置的方法是〔C〕。A．冒泡B．直接插入C．折半插入D．選擇排序27．一棵哈夫曼樹(shù)總共有23個(gè)結(jié)點(diǎn)，該樹(shù)共有〔D〕個(gè)葉結(jié)點(diǎn)〔終端結(jié)點(diǎn)〕A．10B．13C．1128．一組記錄的關(guān)鍵字序列為〔46，79，56，38，40，84〕，利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為〔B〕。A．40，38，46，79，56，84B．40，38，46，56，79，84C．40，38，46，84，56，79D．38，40，46，56，79，8429．隊(duì)列的插入操作在〔B〕進(jìn)展。A．隊(duì)頭B．隊(duì)尾C．隊(duì)頭或隊(duì)尾D．在任意指定位置二、填空題〔每題2分，共24分〕1．一棵二叉樹(shù)沒(méi)有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，那么該樹(shù)總共有____11____個(gè)結(jié)點(diǎn)。2．在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)構(gòu)造中，通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是_值域__、左指針、右指針。3．設(shè)一棵完全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10，該完全二叉樹(shù)一共有___21___個(gè)結(jié)點(diǎn)。4．一棵二叉樹(shù)中順序編號(hào)為i的結(jié)點(diǎn)，假設(shè)它存在左、右孩子，那么左、右孩子編號(hào)分別為_(kāi)___2i_、___2i+1____。5．按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有__先序_、___中序_、__后序_三種。6．串的兩種最根本的存儲(chǔ)方式是__順序存儲(chǔ)_和__鏈?zhǔn)酱鎯?chǔ)___。7．?dāng)?shù)據(jù)構(gòu)造中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱(chēng)為_(kāi)__樹(shù)形_____構(gòu)造。8．一棵有2n-1個(gè)結(jié)點(diǎn)的二叉樹(shù)，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，那么該樹(shù)共有___N____個(gè)葉結(jié)點(diǎn)。9．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并詳細(xì)表達(dá)數(shù)據(jù)之間的邏輯構(gòu)造稱(chēng)為_(kāi)__物理〔存儲(chǔ)〕_____構(gòu)造。10．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)構(gòu)造中共有__n+1______個(gè)指針域?yàn)榭铡?1．構(gòu)造中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱(chēng)為_(kāi)_線性__構(gòu)造。12．__中序______遍歷二叉排序樹(shù)可得到一個(gè)有序序列。13．如圖4所示的二叉樹(shù)，其后序遍歷序列為gdbeihfca。eefgibachd圖414．n個(gè)元素進(jìn)展冒泡法排序，通常需要進(jìn)展__n-1__趟冒泡。15．如圖5所示的二叉樹(shù)，其先序遍歷序列為_(kāi)_abdefcg__。ggfabdec圖516．二叉樹(shù)為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是__不正確____的。(答復(fù)正確或不正確)17．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_正確_____的。(答復(fù)正確或不正確)18．根據(jù)搜索方法的不同，圖的遍歷有__深度優(yōu)先搜索遍歷_、_廣度優(yōu)先搜索遍歷_兩種方法19．對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按__主關(guān)鍵字_______排序結(jié)果是唯一的。20．按某關(guān)鍵字對(duì)記錄序列排序，假設(shè)關(guān)鍵字相等的記錄在排序前和排序后仍保持它們的前后關(guān)系，那么排序算法是穩(wěn)定的，否那么是不穩(wěn)定的。1642164232525767821021．〔1〕利用挑選過(guò)程把序列{42，82，67，102，16，32，57，52}建成堆〔小根堆〕，畫(huà)出該堆〔不要求中間過(guò)程〕?！?〕寫(xiě)出對(duì)上述堆對(duì)應(yīng)的完全二叉樹(shù)進(jìn)展中序遍歷得到的序列。 答：102，52，42，82，16，67，32，572．設(shè)查找表為(16,15,20,53,64,7),(1)用冒泡法對(duì)該表進(jìn)展排序〔要求升序排列〕，寫(xiě)出每一趟的排序過(guò)程，通常對(duì)n個(gè)元素進(jìn)展冒泡排序要進(jìn)展多少趟冒泡？第j趟要進(jìn)展多少次元素間的比擬？答：(1)原序列16152053647151620