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