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

PAGEPAGE20數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)期末綜合練習(xí)一一、單項(xiàng)選擇題1．?dāng)?shù)據(jù)的物理結(jié)構(gòu)（D）。A．與數(shù)據(jù)的邏輯結(jié)構(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)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成D．至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類型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．線性表的順序結(jié)構(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．線性結(jié)構(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ō)法正確的是（C）。A．隊(duì)列是后進(jìn)先出B．棧的特點(diǎn)是后進(jìn)后出C．棧的刪除和插入操作都只能在棧頂進(jìn)行D．隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行12.以下說(shuō)法不正確的是（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ì)稱矩陣A，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中（矩陣A的第一個(gè)元素為a1,1，數(shù)組b的下標(biāo)從1開(kāi)始），則矩陣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)類型的指針，可執(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ō)法不正確的是（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ì)稱矩陣A，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中。（矩陣A的第一個(gè)元素為a1,1，數(shù)組b的下標(biāo)從1開(kāi)始），則矩陣元素a5,3對(duì)應(yīng)一維數(shù)組b的數(shù)組元素是（C）。A．b[18]B．b[8]C．b[13]D．b[10]24．如圖1若從頂點(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è)圖，若從頂點(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ù)的邏輯結(jié)構(gòu)包括集合、線性、_樹(shù)形_、_圖狀四種類型。2．通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成__圖狀__結(jié)構(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)，若要?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í)表明隊(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í)表明隊(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)，若它存在左、右孩子，則左、右孩子編號(hào)分別為_(kāi)___2i___、__2i+1___。14．按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有_先序、_中序_、_后序_三種。15．兩個(gè)串相等的充分必要條件是串長(zhǎng)度相等且對(duì)應(yīng)位置的字符相等。16．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_(kāi)物理（存儲(chǔ)）_結(jié)構(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ò)誤_____的。(回答正確或不正確)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ù)結(jié)構(gòu)D．?dāng)?shù)據(jù)項(xiàng)2．同一種邏輯結(jié)構(gòu)（B）。A．只能有唯一的存儲(chǔ)結(jié)構(gòu)B．可以有不同的存儲(chǔ)結(jié)構(gòu)C．只能表示某一種數(shù)據(jù)元素之間的關(guān)系D．以上三種說(shuō)法均不正確3．設(shè)鏈表中的結(jié)點(diǎn)是NODE類型的結(jié)構(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ù)的物理結(jié)構(gòu)（D）。A．與數(shù)據(jù)的邏輯結(jié)構(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．線性結(jié)構(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ō)法不正確的是（C）。A．順序棧中，棧滿時(shí)再進(jìn)行進(jìn)棧操作稱為“上溢”B．順序棧中，棧空時(shí)再作出棧棧操作稱為“下溢”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ù)結(jié)構(gòu)13．設(shè)有一個(gè)20階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組中（矩陣A的第一個(gè)元素為a11，數(shù)組b的下標(biāo)從1開(kāi)始），則矩陣元素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ō)法正確的是（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若從頂點(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ì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是（A）。A．33B．32C29．?dāng)?shù)據(jù)的（A）結(jié)構(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ū)的目錄結(jié)構(gòu)抽象成___樹(shù)形__結(jié)構(gòu)。2．棧和隊(duì)列的操作特點(diǎn)分別是__先進(jìn)后出___和___先進(jìn)先出__。3．要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行__s->next=p->next；______和p->next=s;的操作。4．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_(kāi)___圖狀（網(wǎng)狀）__結(jié)構(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ù)形、圖狀四類基本結(jié)構(gòu)。7．在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata，指針域?yàn)閚ext，若要進(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è)元素空間以有效的判斷?？栈驐M，若隊(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ǔ)結(jié)構(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)相同），若它存在右孩子，則右孩子的編號(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)。（根所在結(jié)點(diǎn)為第1層）17．在隊(duì)列的順序存儲(chǔ)結(jié)構(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的頭指針和尾指針，若要把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;這樣做正確嗎？若正確則回答正確，若不正確則說(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ù)結(jié)構(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ù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（D）結(jié)構(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)行冒泡排序若某趟冒泡中只進(jìn)行了（C）次元素間的交換，則表明序列已經(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è)圖，若從頂點(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è)圖，若從頂點(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，若從頂點(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)棧出棧可以交替進(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．排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（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ǔ)結(jié)構(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)，若它存在左、右孩子，則左、右孩子編號(hào)分別為_(kāi)___2i_、___2i+1____。5．按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有__先序_、___中序_、__后序_三種。6．串的兩種最基本的存儲(chǔ)方式是__順序存儲(chǔ)_和__鏈?zhǔn)酱鎯?chǔ)___。7．?dāng)?shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為_(kāi)__樹(shù)形_____結(jié)構(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ī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_(kāi)__物理（存儲(chǔ)）_____結(jié)構(gòu)。10．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有__n+1______個(gè)指針域?yàn)榭铡?1．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為_(kāi)_線性__結(jié)構(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ō)法是__不正確____的。(回答正確或不正確)17．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_正確_____的。(回答正確或不正確)18．根據(jù)搜索方法的不同，圖的遍歷有__深度優(yōu)先搜索遍歷_、_廣度優(yōu)先搜索遍歷_兩種方法19．對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按__主關(guān)鍵字_______排序結(jié)果是唯一的。20．按某關(guān)鍵字對(duì)記錄序列排序，若關(guān)鍵字相等的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。1642164232525767821021．（1）利用篩選過(guò)程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），畫(huà)出該堆（不要求中間過(guò)程）。（2）寫(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)原序列1615205364715162053