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