數(shù)據(jù)結(jié)構(gòu)與算法分析復(fù)習(xí)資料

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料總結(jié)2012-052012-06-05MODIFY目錄1.第一章 31.1根本概念題 31.2邏輯結(jié)構(gòu)題 31.3物理結(jié)構(gòu)題 31.4算法特性題 42.線性表 42.1根本概念題 42.2順序表 42.3鏈表概念題 52.4鏈表指針題 52.5鏈表編程題 63.棧和隊(duì)列 83.1棧的概念題 83.2進(jìn)棧出棧題 83.3鏈棧指針題 93.4鏈棧編程題 93.5隊(duì)列概念題 103.6鏈隊(duì)指針題 103.7鏈隊(duì)編程題 113.8循環(huán)隊(duì)列題 124.串 124.1串的根本概念 124.2串函數(shù) 134.5串的編程題 135.數(shù)組和廣義表 145.1數(shù)組坐標(biāo)換算題 145.2矩陣題 145.3廣義表 156.樹(shù)和二叉樹(shù) 156.1二叉樹(shù)的概念性質(zhì) 156.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ) 176.3樹(shù)的遍歷概念題 176.4樹(shù)的遍歷操作題 186.5樹(shù)的遍歷編程題 206.6哈夫曼樹(shù) 216.7樹(shù)的遍歷反過(guò)來(lái)做的題 227.圖 237.1圖的根本概念 237.2圖的遍歷 247.3圖的最小生成樹(shù) 247.5圖的連通性 258.查找 258.1順序查找 258.2折半查找 258.3二叉排序樹(shù) 268.4二叉判定樹(shù) 288.5哈希函數(shù) 298.6折半查找編程題 298.7二叉排序樹(shù)編程題 309.排序 319.1排序根本概念 319.2直接插入排序 319.3折半插入排序 329.4交換排序之冒泡排序 329.5交換排序之快速排序 339.6選擇排序之直接選擇排序 349.7選擇排序之堆排序 359.8選擇排序之歸并排序 389.9排序穩(wěn)定性題 38

1.第一章1.1根本概念題1．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在〔〕的關(guān)系。【B】A．一對(duì)多B．一對(duì)一 C．多對(duì)多D．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼注：D選不全的，第一個(gè)元素就木有前驅(qū)，最后一個(gè)元素就木有后繼。2．?dāng)?shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的〔〕結(jié)構(gòu)。【D】A．物理B．存儲(chǔ)C．邏輯與物理D．邏輯3．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為_(kāi)_______結(jié)構(gòu)?！揪€性】4．?dāng)?shù)據(jù)元素是數(shù)據(jù)的根本單位，它〔〕?！綜】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)為指針類型5．一種邏輯結(jié)構(gòu)〔〕存儲(chǔ)結(jié)構(gòu)?！続】A．可以有不同的B．只能有唯一的C．的數(shù)據(jù)元素在計(jì)算機(jī)中的表示稱為D．的數(shù)據(jù)元素之間的關(guān)系稱為1.2邏輯結(jié)構(gòu)題1．通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括_____、_____、_____、_____四種類型?！炯?；線性；樹(shù)形；圖狀】2．通?？梢园岩槐竞胁煌鹿?jié)的書(shū)的目錄結(jié)構(gòu)抽象成_____結(jié)構(gòu)?！緲?shù)形】3．通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成_____結(jié)構(gòu)?！緢D狀】4．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_(kāi)_______結(jié)構(gòu)。【圖狀〔網(wǎng)狀〕】5．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為_(kāi)_______結(jié)構(gòu)?！緲?shù)形】6．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為_(kāi)_______結(jié)構(gòu)?！揪€性】1.3物理結(jié)構(gòu)題1．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體表達(dá)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱稱為物理〔〕結(jié)構(gòu)?！敬鎯?chǔ)】2．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體表達(dá)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_(kāi)_______結(jié)構(gòu)?！参锢怼泊鎯?chǔ)〕〕1.4算法特性題1．以下特征中，〔〕不是算法的特性?！綜】A．有窮性B．確定性C．有0個(gè)或多個(gè)輸出D．可行性2．算法的時(shí)間復(fù)雜度與〔〕有關(guān)?！綝】 A．所使用的計(jì)算機(jī)B．與計(jì)算機(jī)的操作系統(tǒng)C．與數(shù)據(jù)結(jié)構(gòu)D．與算法本身3．要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)根本操作為元素間的比擬。那么比擬的次數(shù)和算法的時(shí)間復(fù)雜度分別為_(kāi)_______和O(n)?！緉-1】2.線性表2.1根本概念題1．針對(duì)線性表，在存儲(chǔ)后如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，那么采用〔〕存儲(chǔ)方式最節(jié)省時(shí)間?！綛】A．單鏈表B．順序表C．單循環(huán)鏈表D．雙鏈表2.2順序表1．設(shè)有一個(gè)長(zhǎng)度為n的順序表，要在第i個(gè)元素之前〔也就是插入元素作為新表的第i個(gè)元素〕，那么移動(dòng)元素個(gè)數(shù)為〔〕。【A】A．n-i+1B．n-iC．n-i-1D．i注：元素要插入到i的位置，不動(dòng)的是前面i-1個(gè)元素，總元素有n個(gè)，要移動(dòng)的元素個(gè)數(shù)是：n-(i-1)即：n-i+12.設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，對(duì)于插入操作，設(shè)插入位置是等概率的，那么插入一個(gè)元素平均移動(dòng)元素的次數(shù)為〔〕。【A】A．n/2B．nC．n-1D．n-i+13.設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，對(duì)于刪除操作，設(shè)刪除位置是等概率的，那么刪除一個(gè)元素平均移動(dòng)元素的次數(shù)為〔〕?！続】A．(n+1)/2B．nC．2nD．n-i4．線性表的順序結(jié)構(gòu)中，〔〕。【C】A．邏輯上相鄰的元素在物理位置上不一定相鄰B．?dāng)?shù)據(jù)元素是不能隨機(jī)訪問(wèn)的C．邏輯上相鄰的元素在物理位置上也相鄰D．進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高2.3鏈表概念題1．鏈表所具備的特點(diǎn)是〔〕。【D】A．可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B．占用連續(xù)的存儲(chǔ)空間C．可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)D．插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)2．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址〔〕?！綜】A．一定是不連續(xù)的B．必須是連續(xù)的C．可以連續(xù)也可以不連續(xù)D．局部地址必須是連續(xù)的3．設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，指針p指向尾結(jié)點(diǎn)，現(xiàn)要使p指向第一個(gè)結(jié)點(diǎn)，可用語(yǔ)句_______?！緋=p->next;】4．在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向________，另一個(gè)指向________?！窘Y(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的直接前驅(qū)】5．以下說(shuō)法中不正確的選項(xiàng)是〔〕?！綛】A．雙向循環(huán)鏈表中每個(gè)結(jié)點(diǎn)需要包含兩個(gè)指針域B．單向鏈表中任一結(jié)點(diǎn)的指針就能訪問(wèn)到鏈表中每個(gè)結(jié)點(diǎn)C．順序存儲(chǔ)的線性鏈表是可以隨機(jī)訪問(wèn)的D．單向循環(huán)鏈表中尾結(jié)點(diǎn)的指針域中存放的是頭指針6．以下表中可以隨機(jī)訪問(wèn)的是〔〕。【D】A．單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D．順序表2.4鏈表指針題根本圖形：1．在一個(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=NULL2．在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向結(jié)點(diǎn)的直接后繼，另一個(gè)指向____?！窘Y(jié)點(diǎn)的直接前驅(qū)】3．設(shè)有一個(gè)頭指針為head的單向循環(huán)鏈表，p指向鏈表中的結(jié)點(diǎn)，假設(shè)p->next==_______，那么p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。【head】4．設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有p->next==NULL,通過(guò)操作________，就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表?！緋->next=head;】5．帶頭結(jié)點(diǎn)的單向鏈表的頭指針為head，該鏈表為空的判定條件是〔〕的值為真?！綜】A．head==NULLB．head->next==headC．head->next==NULLD．head==head->next6．雙向循環(huán)鏈表結(jié)點(diǎn)的數(shù)據(jù)類型為：【B】structnode{intdata;structnode*next;/*指向直接后繼*/structnode*prior;}；設(shè)p指向表中某一結(jié)點(diǎn)，要顯示p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的數(shù)據(jù)元素，可用操作〔〕。A．printf(“%d”,p->next->data);B．printf(“%d”,p->prior->data);C．printf(“%d”,p->prior->next);D．printf(“%d”,p->data);7．要在一個(gè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中刪除頭結(jié)點(diǎn)，得到一個(gè)新的不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，假設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，尾指針為p，那么可執(zhí)行head=head->next;_______。【p->next=head；】8．設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有p->next==NULL,通過(guò)操作________，就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表?！緋->next=head;】9．雙向循環(huán)鏈表中，p指向表中某結(jié)點(diǎn)，那么通過(guò)p可以訪問(wèn)到p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)和直接前驅(qū)結(jié)點(diǎn)，這種說(shuō)法是________的〔答復(fù)正確或不正確〕?！菊_】10．設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語(yǔ)句________?！緋->next=head;】11．設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，指針p指向表中某結(jié)點(diǎn)，假設(shè)邏輯表達(dá)式________的結(jié)果為真，那么p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。【p->next==head;】12．設(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í)行操作_____?！緋->next=head；】13．要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，假設(shè)鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，可執(zhí)行________和p->next=s;的操作。【s->next=p->next；】14．要在一個(gè)單向鏈表中刪除p所指向的結(jié)點(diǎn)，q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，假設(shè)鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，那么可執(zhí)行_______?！緌->next=p->next；】2.5鏈表編程題1．編程題以下是用頭插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，要求結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為n,n-1,……,1，完成程序中空格局部。NODE*create2(n){ NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));p->next=NULL;head=〔1〕;〔2〕;for(i=1;i<=n;i++){p=〔3〕;p->data=i;if(i==1)p->next=NULL;elsep->next=〔4〕;q->next=〔5〕;}return(head);}下面答案： 〔1〕p〔2〕q=p〔3〕(NODE*)malloc(sizeof(NODE))〔4〕q->next〔5〕p2．編程題以下函數(shù)在head為頭指針的具有頭結(jié)點(diǎn)的單向鏈表中刪除第i個(gè)結(jié)點(diǎn)，structnode{intdata;structnode*next;};typedefstructnodeNODEintdelete(NODE*head,inti){NODE*p,*q;intj;q=head;j=0;while((q!=NULL)&&(___(1)_____)){___(2)_____;j++;}if(q==NULL)return(0);p=___(3)_____;___(4)_____=p->next;free(___(5)_____);return(1);} 下面答案：〔1〕j<i-1〔2〕q=q->next〔3〕q->next〔4〕q->next〔5〕p3.棧和隊(duì)列3.1棧的概念題1．棧的插入刪除操作在〔〕進(jìn)行。【B】A．棧底B．棧頂C．任意位置D．指定位置2．以下說(shuō)法正確的選項(xiàng)是〔〕?！綜】A．棧的特點(diǎn)是先進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)后出B．棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出C．棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出D．棧和隊(duì)列的特點(diǎn)都是先進(jìn)先出3．棧和隊(duì)列的相同點(diǎn)是〔〕?！綝】A．都是后進(jìn)先出B．都是后進(jìn)后出C．邏輯結(jié)構(gòu)與線性表不同D．邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)那么受到限制的線性表3.2進(jìn)棧出棧題1．元素3，6，9按順序依次進(jìn)棧，那么該棧的不可能輸出序列是〔〕〔進(jìn)棧出棧可以交替進(jìn)行〕。A．9，3，6B．9，6，3【A】C．6，3，9D．3，9，62．元素2，4，6，8按順序依次進(jìn)棧，那么該棧的不可能輸出序列是〔〕〔進(jìn)棧出?？梢越惶孢M(jìn)行〕?！綝】A．8，6，4，2B．2，4，6，8C．4，2，8，6D．8，6，2，43．一個(gè)棧的進(jìn)棧序列是5，6，7，8，那么棧的不可能的出棧序列是〔〕〔進(jìn)出棧操作可以交替進(jìn)行〕【A】A．5，8，6，7B．7，6，8，5C．7，6，5，8D．8，7，6，54.一個(gè)棧的進(jìn)棧序列是efgh，那么棧的不可能的出棧序列是〔〕〔進(jìn)出棧操作可以交替進(jìn)行〕?！綝】A．hgfeB．gfehC．fgehD．ehfg3.3鏈棧指針題1．從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，可執(zhí)行x=h->data;和________。(結(jié)點(diǎn)的指針域?yàn)閚ext)【h=h->next;】2．向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行______和h=s;?！緎->next=h;】3．從一個(gè)棧頂指針為h的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，可執(zhí)行______和h=h->next;。(結(jié)點(diǎn)的指針域?yàn)閚ext)【x=h->data;】4．設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext，數(shù)據(jù)域?yàn)閐ata，那么可執(zhí)行x=______；和hs=______；【hs->data;hs->next;】5．設(shè)top是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，那么出棧操作為〔〕?！続】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;6．設(shè)top是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，那么取棧頂元素的操作為〔〕。【C】A．top->data=x;B．top=top->next;C．x=top->data;D．x=top->data;top=top->next;11．C12．C13．D14．B15．A7．設(shè)有一個(gè)鏈棧，棧頂指針為hs，現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，那么可執(zhí)行操作s->next=hs;________。【hs=s；】8．設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext，那么可執(zhí)行x=hs->data;_______?！緃s=hs->next;】9．設(shè)有一個(gè)鏈棧，棧頂指針為hs，現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，那么可執(zhí)行操作_______和hs=s；【s->next=hs;】3.4鏈棧編程題1．編程題以下函數(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(___(1)_____);p->data=x;___(2)_____;_____(3)___;} 下面答案： 〔1〕sizeof(structnode)〔2〕p->next=top〔3〕top=p3.5隊(duì)列概念題1．隊(duì)列的刪除操作在〔〕進(jìn)行?！続】A．隊(duì)頭B．隊(duì)尾C．隊(duì)頭或隊(duì)尾D．在任意指定位置2．以下說(shuō)法正確的選項(xiàng)是〔〕?！綜】A．隊(duì)列是后進(jìn)先出B．棧的特點(diǎn)是后進(jìn)后出C．棧的刪除和插入操作都只能在棧頂進(jìn)行D．隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行3．以下說(shuō)法不正確的選項(xiàng)是〔〕?！綜】A．棧的特點(diǎn)是后進(jìn)先出B．隊(duì)列的特點(diǎn)是先進(jìn)先出C．棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行D．隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)頭進(jìn)行4．在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，指針的值增1，當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，指針的值增1。【尾頭】3.6鏈隊(duì)指針題1．在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，那么刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為〔〕?！綝】A．r=f->next;B．r=r->next;C．f=r->next;D．f=f->next;2．在一個(gè)鏈隊(duì)中，設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，那么插入s所指結(jié)點(diǎn)的操作為_(kāi)_______和r=s;(結(jié)點(diǎn)的指針域?yàn)閚ext)【r->next=s;】3．在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，s指向一個(gè)要入隊(duì)的結(jié)點(diǎn)，那么入隊(duì)操作為_(kāi)_______；________；【r->next=s；r=s；】4．在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，那么插入一個(gè)s所指結(jié)點(diǎn)的操作為_(kāi)_______；r=s；【r->next=s】5．棧和隊(duì)列的操作特點(diǎn)分別是________和________?！鞠冗M(jìn)后出〔后進(jìn)先出〕先進(jìn)先出〔后進(jìn)后出〕】6．在一個(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)操作為_(kāi)_______;_______?！緓=f->data;f=f->next;】7．綜合題〔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〕?！?〕單向鏈表的鏈域?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ě)下面答案： 〔1〕p1->next=head2；p2->next=head1；〔2〕不對(duì)，s->next=p->next；p->next=s；3.7鏈隊(duì)編程題1．編程題以下函數(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*)___(1)_____;p->data=x;p->next=NULL;___(2)_____;rear=___(3)_____;} 下面答案：〔1〕malloc(sizeof(structnode))〔2〕rear->next=p〔3〕p2．編程題以下函數(shù)為鏈隊(duì)列的出隊(duì)操作〔鏈隊(duì)列帶有頭結(jié)點(diǎn)〕，出隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域的值由x返回，front、rear分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針structnode{ElemTypedata;structnode*next;};structnode*front，*rear;ElemTypeOutQueue(){ ElemTypex; if(___(1)_____){printf("隊(duì)列下溢錯(cuò)誤！\n");exit(1);}else{structnode*p=front->next;x=p->data;front->next=___(2)_____;if(p->next==NULL)rear=front;free(p);___(3)_____;}} 下面答案： 〔1〕front==rear〔2〕p->next〔3〕return(x)3.8循環(huán)隊(duì)列題1．循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)_____時(shí)說(shuō)明隊(duì)列為空。【r==f】2．循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxSize=6，采用少用一個(gè)元素空間以有效地判斷?？栈驐M，假設(shè)隊(duì)頭指針front=4，當(dāng)隊(duì)尾指針rear=_______時(shí)隊(duì)滿，隊(duì)列中共有________個(gè)元素?！?；5】3．循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxSize=8，采用少用一個(gè)元素空間以有效的判斷棧空或棧滿，假設(shè)隊(duì)頭指針front=4，那么當(dāng)隊(duì)尾指針rear=_______時(shí)，隊(duì)列為空，當(dāng)rear=________時(shí)，隊(duì)列有6個(gè)元素?！?；2】4．循環(huán)隊(duì)列的引入，目的是為了克服_____?！炯偕弦纭?．循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxSize，隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)_______時(shí)說(shuō)明隊(duì)列已滿?！尽瞨+1〕%MaxSize=f】4.串4.1串的根本概念性質(zhì)：“”雙引號(hào)內(nèi)的字符串是以‘\0’表示結(jié)束的。要多占一個(gè)字節(jié)。1．在C語(yǔ)言中，順序存儲(chǔ)長(zhǎng)度為3的字符串，需要占用〔〕個(gè)字節(jié)?！尽緼．3B．4C．6D．122．在C語(yǔ)言中，利用數(shù)組a存放字符串“Hello”，以下語(yǔ)句中正確的選項(xiàng)是〔〕。【A】A．chara[10]=“Hello”;B．chara[10];a=“Hello”;C．chara[10]=‘Hello’;D．chara[10]={‘H’,’e’,’l’,’l’,’o’};3．兩個(gè)串相等的充分必要條件是__________?！敬L(zhǎng)度相等且對(duì)應(yīng)位置的字符相等】4．串的兩種最根本的存儲(chǔ)方式是________和________?！卷樞虼鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)】5．‘A‘在存儲(chǔ)時(shí)占________個(gè)字節(jié)?！癆”在存儲(chǔ)時(shí)占________個(gè)字節(jié)?！?；2】6.順序存儲(chǔ)字符串“ABCD”需要占用________個(gè)字節(jié)?！?】4.2串函數(shù)性質(zhì)StrCmp函數(shù)有三個(gè)結(jié)果：第一個(gè)字符串大于第二個(gè)字符串，結(jié)果：1第一個(gè)字符串等于第二個(gè)字符串，結(jié)果：0第一個(gè)字符串小于第二個(gè)字符串，結(jié)果：-1對(duì)應(yīng)位置比擬，根據(jù)ASCII碼進(jìn)行比擬。數(shù)字編碼最小，其次大寫(xiě)字母，其后是小寫(xiě)字母。1．串函數(shù)StrCmp〔“d”，“D”〕的值為〔〕?！綛】A．0B．1C2．串函數(shù)StrCmp(“abA”,”aba”)的值為〔〕?！綝】A．1B．0C．“abAaba”D4.5串的編程題1．程序段intcount=0;char*s=”ABCD”;while(*s!=’\0’執(zhí)行后count=________【4】2．char*p;【B】p=StrCat(“ABD”,”ABC”);Printf(“%s”,p);的顯示結(jié)果為〔〕。A．-1B．ABDABCC．ABD．13．程序段char*s=”aBcD”;n=0;while(*s!=’\0’{if(*s>＝’a’&&*s<＝’z’)n++;s++;}執(zhí)行后n=________【2】5.數(shù)組和廣義表5.1數(shù)組坐標(biāo)換算題三個(gè)公式：對(duì)稱矩陣：P77下三角矩陣：P77對(duì)角矩陣：P781．設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角局部以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組B中〔數(shù)組下標(biāo)從1開(kāi)始〕，那么矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是〔〕?！続】A．33B．32C2．設(shè)有一個(gè)15階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角局部以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中〔數(shù)組下標(biāo)從1開(kāi)始〕，那么矩陣中元素a7,6在一維數(shù)組B中的下標(biāo)是〔〕?！綜】A．42B．13C3．設(shè)有一個(gè)15階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式將其下三角局部以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中?！簿仃嘇的第一個(gè)元素為a1,1，數(shù)組b的下標(biāo)從1開(kāi)始〕，那么數(shù)組元素b[13]對(duì)應(yīng)A的矩陣元素是〔〕。【A】A．a(chǎn)5,3B．a(chǎn)6,4C．a(chǎn)7,2D4．設(shè)有n階對(duì)稱矩陣A，用數(shù)組S進(jìn)行壓縮存儲(chǔ)，當(dāng)i<j時(shí)，A的數(shù)組元素aij相應(yīng)于數(shù)組S的數(shù)組元素的下標(biāo)為_(kāi)______?！矓?shù)組元素的下標(biāo)從1開(kāi)始〕【i(i-1)/2+j】5．設(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≤5.2矩陣題1．稀疏矩陣存儲(chǔ)時(shí)，采用一個(gè)由____、____、____3局部信息組成的三元組唯一確定矩陣中的一個(gè)非零元素。【行號(hào)；列號(hào)；非零元】5.3廣義表6.樹(shù)和二叉樹(shù)6.1二叉樹(shù)的概念性質(zhì)P92二叉樹(shù)的性質(zhì)1.二叉樹(shù)上終端結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。2.二叉樹(shù)上第i層上至多有個(gè)結(jié)點(diǎn)〔〕。3.深度為h的二叉樹(shù)至多有個(gè)結(jié)點(diǎn)。4.對(duì)于一顆二叉樹(shù)中順序編號(hào)為i的結(jié)點(diǎn)，假設(shè)它存在左孩子，那么左孩子結(jié)點(diǎn)的編號(hào)為；假設(shè)它存在右孩子，那么右孩子結(jié)點(diǎn)的編號(hào)為2i+1，假設(shè)它存在雙親結(jié)點(diǎn)〔即編號(hào)不等于1〕，那么雙親結(jié)點(diǎn)的編號(hào)為。5.具有n個(gè)結(jié)點(diǎn)的理想二叉樹(shù)的深度為或。1．在一棵二叉樹(shù)中，假設(shè)編號(hào)為i的結(jié)點(diǎn)存在右孩子，那么右孩子的順序編號(hào)為〔〕。【D】A．2iB．2i-1C2．一棵二叉樹(shù)中順序編號(hào)為i的結(jié)點(diǎn)，假設(shè)它存在左、右孩子，那么左、右孩子編號(hào)分別為_(kāi)_____、_______?！?i和2i+1】注釋：1題和2題都是利用性質(zhì)43．一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，那么該樹(shù)共有_______個(gè)結(jié)點(diǎn)?！?n-1】4．一棵有2n-1個(gè)結(jié)點(diǎn)的二叉樹(shù)，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，那么該樹(shù)共有_______個(gè)葉結(jié)點(diǎn)?！緉】注釋：３題和４題是利用同一個(gè)性質(zhì)１完成。結(jié)點(diǎn)總數(shù)：每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，說(shuō)明：，就是結(jié)點(diǎn)要么沒(méi)有孩子，要么有兩個(gè)孩子。結(jié)果： 根據(jù)性質(zhì)1又有： 根據(jù)上面兩個(gè)結(jié)論，可以求出3題和4題。5．一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，那么它的最高層上有_______個(gè)結(jié)點(diǎn)?！?】 注釋：完全二叉樹(shù)如下列圖所示：最高一層數(shù)一下有七個(gè)結(jié)點(diǎn)。6.綜合題之一“一棵二叉樹(shù)假設(shè)它的根結(jié)點(diǎn)的值大于左子樹(shù)所有結(jié)點(diǎn)的值，小于右子樹(shù)所有結(jié)點(diǎn)的值，那么該樹(shù)一定是二叉排序樹(shù)”。該說(shuō)法是否正確，假設(shè)認(rèn)為正確，那么答復(fù)正確，假設(shè)認(rèn)為不正確那么說(shuō)明理由？【不正確，二叉排序樹(shù)要求其子樹(shù)也是二叉排序樹(shù)。】7．一棵完全二叉樹(shù)共有30個(gè)結(jié)點(diǎn)，那么該樹(shù)一共有〔〕層(根結(jié)點(diǎn)所在層為第一層)?！綝】A．6B．4C．3D注釋：兩個(gè)方法：1.畫(huà)圖2.套公式：性質(zhì)5的公式。8．一棵二叉樹(shù)總結(jié)點(diǎn)數(shù)為11，葉結(jié)點(diǎn)數(shù)為5，該樹(shù)有________個(gè)雙分支結(jié)點(diǎn)，________個(gè)單分支結(jié)點(diǎn)。【4；2】注釋：和３題４題一樣，是利用同一個(gè)性質(zhì)１完成。參閱前面的注釋。9．深度為k的二叉樹(shù)最多有______結(jié)點(diǎn)?！?k-1】10．深度為5的滿二叉樹(shù)至多有〔〕個(gè)結(jié)點(diǎn)〔根結(jié)點(diǎn)為第一層〕【B】A．40B．31C．34D注釋：9題和10題是套性質(zhì)3的公式11．一棵二叉樹(shù)中順序編號(hào)為5的結(jié)點(diǎn)〔樹(shù)中各結(jié)點(diǎn)的編號(hào)與等深度的完全二叉中對(duì)應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同〕，假設(shè)它存在左孩子，那么左孩子的編號(hào)為_(kāi)______?！?0】12．一棵二叉樹(shù)沒(méi)有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn)，那么該樹(shù)總共有________個(gè)結(jié)點(diǎn)?！?1】13．一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，那么該樹(shù)共有_______個(gè)結(jié)點(diǎn)?！?n-1】14．一棵二叉樹(shù)葉結(jié)點(diǎn)〔終端結(jié)點(diǎn)〕數(shù)為5，單分支結(jié)點(diǎn)數(shù)為2，該樹(shù)共有______個(gè)結(jié)點(diǎn)?！?1】 注釋：12題13題14題和３題４題一樣，是利用同一個(gè)性質(zhì)１完成。參閱前面的注釋。15．二叉樹(shù)為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是__________的。(答復(fù)正確或不正確)【錯(cuò)誤】注釋：論斷太絕對(duì)，葉子結(jié)點(diǎn)沒(méi)有后代。16．一棵二叉樹(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)_______?！?3】注釋：利用性質(zhì)417．設(shè)一棵完全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10，該完全二叉樹(shù)一共有________個(gè)結(jié)點(diǎn)?！?1】注釋：參閱下列圖：6.2二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)1．設(shè)一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)，那么該樹(shù)共有〔〕個(gè)指針域?yàn)榭铡！綛】A．2nB．n+1C．2n+1D．2n+26.3樹(shù)的遍歷概念題1．對(duì)二叉排序樹(shù)進(jìn)行〔〕遍歷，遍歷所得到的序列是有序序列。【C】A．按層次B．前序C．中序D．后序2．________遍歷二叉排序樹(shù)可得到一個(gè)有序序列?！局行颉?．對(duì)二叉樹(shù)的遍歷可分為_(kāi)______、_______、_______、_______四種不同的遍歷次序?！鞠刃?、中序、后序、層次】4．設(shè)一棵完全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為偶數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為9，該完全二叉樹(shù)一共有________個(gè)結(jié)點(diǎn)?！?8】5．一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，那么該樹(shù)共有_______個(gè)結(jié)點(diǎn)?！?n-1】6．一棵哈夫曼樹(shù)總共有23個(gè)結(jié)點(diǎn)，該樹(shù)共有〔〕個(gè)葉結(jié)點(diǎn)〔終端結(jié)點(diǎn)〕【D】A．10B．13C．11注釋：此題和３題４題一樣，是利用同一個(gè)性質(zhì)１完成。參閱前面的注釋。此題由“哈夫曼樹(shù)”隱含的說(shuō)明了一個(gè)條件：沒(méi)有單分支的結(jié)點(diǎn)。7．一棵哈夫曼樹(shù)總共有25個(gè)結(jié)點(diǎn)，該樹(shù)共有〔〕個(gè)非葉結(jié)點(diǎn)〔非終端結(jié)點(diǎn)〕?！続】A．12B．13C．148．按照二叉樹(shù)的遞歸定義，對(duì)二叉樹(shù)遍歷的常用算法有______、______、______三種?！鞠刃?；中序；后序】6.4樹(shù)的遍歷操作題1．如圖2所示的二叉樹(shù)，其先序遍歷序列為_(kāi)________。【abdgcefhi】 2．如圖假設(shè)從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，那么可能得到的頂點(diǎn)序列為〔〕?！続】A．a(chǎn)cfgedbB．a(chǎn)edcbgfC．a(chǎn)cfebdgD．a(chǎn)ecbdgf3．如圖假設(shè)從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，那么可能得到的頂點(diǎn)序列為〔〕?！綝】A．a(chǎn)cebdfghB．a(chǎn)ebcghdfC．a(chǎn)edfbcghD．a(chǎn)becdfgh4．如圖2所示的二叉樹(shù)，其后序遍歷序列為。【gdbeihfca】5．如圖2所示的二叉樹(shù)，其前序遍歷序列為_(kāi)________?！綼bdefcg】6．如圖2所示的二叉樹(shù)，其后序遍歷序列為?！緂dbeihfca】7．如圖假設(shè)從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，那么可能得到的頂點(diǎn)序列為〔〕?！綛】A．a(chǎn)cfgedbB．a(chǎn)edbgfcC．a(chǎn)cfebdgD．a(chǎn)ecbdgf6.5樹(shù)的遍歷編程題1．編程題以下程序是先序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格局部〔樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)〕。voidPreorder(structBTreeNode*BT){if(BT!=NULL){〔1〕;〔2〕;〔3〕;}}下面答案：〔1〕printf(“%c”,BT->data)〔2〕Preorder(BT->left)〔3〕Preorder(BT->right)2．編程題以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格局部〔樹(shù)結(jié)構(gòu)中，左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)〕。voidPostorder(structBTreeNode*BT){if(BT!=NULL){〔1〕;〔2〕;〔3〕;}} 下面答案：〔1〕Postorder(BT->left)〔2〕Postorder(BT->right)〔3〕printf(“%c”,BT->data)3．編程題以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格局部〔樹(shù)結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)〕。voidInorder(structBTreeNode*BT){if(BT!=NULL){〔1〕;〔2〕;〔3〕;}}下面答案： 〔1〕Inorder(BT->left)〔2〕printf(“%c”,BT->data)〔3〕Inorder(BT->right)6.6哈夫曼樹(shù)1．設(shè)一棵哈夫曼樹(shù)共有n個(gè)葉結(jié)點(diǎn)，那么該樹(shù)有〔〕個(gè)非葉結(jié)點(diǎn)?！続】A．n-1B．nC．n+1D．2n2．一棵哈夫曼樹(shù)有12個(gè)葉子結(jié)點(diǎn)〔終端結(jié)點(diǎn)〕，該樹(shù)總共有〔〕個(gè)結(jié)點(diǎn)?！綜】A．22B．21C．23D．3．〔1〕以給定權(quán)重值1，2，12，13，20，25為葉結(jié)點(diǎn)，建立一棵哈夫曼樹(shù)〔2〕假設(shè)哈夫曼樹(shù)有n個(gè)非葉子結(jié)點(diǎn)，那么樹(shù)中共有多少結(jié)點(diǎn)。對(duì)給定的一組權(quán)重值建立的棵哈夫曼樹(shù)是否一定唯一 下面答案

6.7樹(shù)的遍歷反過(guò)來(lái)做的題1．綜合題〔1〕某二叉樹(shù)的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫(huà)出該二叉樹(shù)〔2〕假設(shè)上述二叉樹(shù)的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)〔其中沒(méi)有相等的〕，并恰好使該樹(shù)成為一棵二叉排序樹(shù)，試給出a、b、c、d、e的大小關(guān)系〔3〕給出該樹(shù)的前序遍歷序列下面答案：2．綜合題〔1〕某二叉樹(shù)的先序遍歷序列是aecdb，中序遍歷序列是eadcb，試畫(huà)出該二叉樹(shù)〔2〕給出上述二叉樹(shù)的后序遍歷序列〔3〕假設(shè)上述二叉樹(shù)的各個(gè)結(jié)點(diǎn)的字符分別是1，2，3，4，5，并恰好使該樹(shù)成為一棵二叉排序樹(shù)，試問(wèn)a、b、c、d、e的值各為多少？ 下面答案： 7.圖7.1圖的根本概念P124:全部頂點(diǎn)的度數(shù)為所有邊數(shù)的2倍，或者說(shuō)，邊數(shù)為全部頂點(diǎn)的度數(shù)的一半。1．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的〔〕倍。【D】A．3B．2.5C2．一個(gè)圖的邊數(shù)為m，那么該圖的所有頂點(diǎn)的度數(shù)之和為〔〕。【A】A．2mB．mC．2m+1D．m/23．一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m，那么該圖的邊數(shù)為〔〕?！綝】A．2mB．mC．2m+1D．m/24．以下說(shuō)法不正確的選項(xiàng)是〔〕?！綝】A．連通圖G一定存在生成樹(shù)B．連通圖G的生成樹(shù)中一定包含G的所有頂點(diǎn)C．連通圖G的生成樹(shù)中不一定包含G的所有邊D．連通圖G的生成樹(shù)可以是不連通的5．以下說(shuō)法不正確的選項(xiàng)是〔〕?！続】A．連通圖G的生成樹(shù)一定是唯一的B．連通圖G一定存在生成樹(shù)C．連通圖G的生成樹(shù)中一定要包含G的所有頂點(diǎn)D．連通圖G的生成樹(shù)一定是連通而且不包含回路7.2圖的遍歷1．根據(jù)搜索方法的不同，圖的遍歷有____、____兩種方法【深度優(yōu)先廣度優(yōu)先】2．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是______的。(答復(fù)正確或不正確)【正確】3．如圖1所示的一個(gè)圖，假設(shè)從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，那么可能得到的一種頂點(diǎn)序列為〔〕?！綜】A．a(chǎn)bcedfB．a(chǎn)ebcfdC．a(chǎn)bcefdD．a(chǎn)cfdeb4．如圖1所示的一個(gè)圖，假設(shè)從頂點(diǎn)V1出發(fā)，按廣度優(yōu)先進(jìn)行遍歷，那么可能得到的一種頂點(diǎn)序列為〔〕?！綜】A．V1V2V3V6V7V4V5V8B．V1V2V3V4V5V8V6V7C．V1V2V3V4V5V6V7V8D．V1V2V3V4V8V5V6V77.3圖的最小生成樹(shù)應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程7.5圖的連通性1．以下說(shuō)法正確的選項(xiàng)是〔〕?！綝】A．連通圖G的生成樹(shù)中不一定包含G的所有頂點(diǎn)B．連通圖G的生成樹(shù)中一定要包含G的所有邊C．連通圖G的生成樹(shù)一定是唯一的D．連通圖G一定存在生成樹(shù)8.查找8.1順序查找1．對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在等概率情況下，平均查找長(zhǎng)度為〔〕?！綛】A．nB．〔n+1〕/2C．2n2．采用順序查找法對(duì)長(zhǎng)度為n的線性表進(jìn)行查找〔不采用表尾設(shè)監(jiān)視哨的方法〕，最壞的情況下要進(jìn)行〔〕次元素間的比擬。【B】A．n+2B．nC．n-1D．n/28.2折半查找1．在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120}中，用折半查找法查找值80時(shí)，經(jīng)〔〕次比擬后查找成功?！尽緼．2B．3C．42．有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比擬次數(shù)為〔A〕。 A．29/10B．31/10C3．在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86時(shí)，經(jīng)〔〕次比擬后查找成功?！綝】 A．6B．3C4．用折半查找法，對(duì)長(zhǎng)度為12的有序的線性表進(jìn)行查找，最壞情況下要進(jìn)行〔〕次元素間的比擬【A】A．4B．3C．5D5．綜合題設(shè)有序表為〔13，19，25，36，48，51，63，84，91，116，135，200〕，元素的下標(biāo)依次為1,2,……,12?！?〕說(shuō)出有哪幾個(gè)元素需要經(jīng)過(guò)4次元素間的比擬才能成功查到〔2〕畫(huà)出對(duì)上述有序表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)〔樹(shù)結(jié)點(diǎn)用下標(biāo)表示〕〔3〕設(shè)查找元素5，需要進(jìn)行多少次元素間的比擬才能確定不能查到下面答案： 6．折半查找只適用于____________存儲(chǔ)的有序表?！卷樞虼鎯?chǔ)結(jié)構(gòu)】7．有序表為{1，2，4，6，10，18，20，32}，用課本中折半查找算法查找值18，經(jīng)〔〕次比擬后成功查到?！綛】A．3B．2C．4D8.3二叉排序樹(shù)1．二叉樹(shù)為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是__________的。(答復(fù)正確或不正確)【不正確】2．綜合題〔1〕對(duì)給定數(shù)列{7,16,4,8,20,9,6,18,5}，依次取數(shù)列中的數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù)。(2)對(duì)一個(gè)給定的查找值,簡(jiǎn)述針對(duì)二叉排序樹(shù)進(jìn)行查找的算法步驟，在上述二叉樹(shù)中查找元素20共要進(jìn)行多少次元素的比擬?下面答案：3．綜合題(1)“一棵二叉樹(shù)假設(shè)它的根結(jié)點(diǎn)的值大于左子樹(shù)所有結(jié)點(diǎn)的值，小于右子樹(shù)所有結(jié)點(diǎn)的值，那么該樹(shù)一定是二叉排序樹(shù)”。該說(shuō)法是否正確，假設(shè)認(rèn)為正確，那么答復(fù)正確，假設(shè)認(rèn)為不正確那么說(shuō)明理由？(2)設(shè)有查找表{7，16，4，8，20，9，6，18，5}，依次取表中數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù).對(duì)上述二叉樹(shù)給出后序遍歷的結(jié)果.下面答案： 4．二叉樹(shù)排序中任一棵子樹(shù)都是二叉排序樹(shù)，這種說(shuō)法是_______的。(答復(fù)正確或不正確)【正確】5．綜合題〔1〕設(shè)有一個(gè)整數(shù)序列{40，28，6，72，100，3，54}依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(shù)〔2〕對(duì)上述二叉排序樹(shù)，在等概率條件下，求成功查找的平均查找長(zhǎng)度 下面答案： 6．綜合題〔1〕給定數(shù)列{8，17，5，9，21，10，7，19，6}，依次取序列中的數(shù)構(gòu)造一棵二叉排序樹(shù)〔2〕對(duì)上述二叉樹(shù)給出中序遍歷得到的序列。 下面答案： 7．綜合題〔1〕設(shè)有一個(gè)整數(shù)序列{50，38，16，82，110，13，64}，依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(shù)〔2〕利用上述二叉排序樹(shù)，為了查找110，經(jīng)多少次元素間的比擬能成功查到，為了查找15，經(jīng)多少次元素間的比擬可知道查找失敗下面答案：8.4二叉判定樹(shù) 解析：寫(xiě)判定樹(shù)最重要是每次找子樹(shù)對(duì)應(yīng)的頂點(diǎn)1．綜合題設(shè)查找表為(16,15,20,53,64,7),(1)用冒泡法對(duì)該表進(jìn)行排序〔要求升序排列〕，寫(xiě)出每一趟的排序過(guò)程，通常對(duì)n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第j趟要進(jìn)行多少次元素間的比擬？(2)在排序后的有序表的根底上，畫(huà)出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù).(要求以數(shù)據(jù)元素作為樹(shù)結(jié)點(diǎn))(3)求在等概率條件下,對(duì)上述有序表成功查找的平均查找長(zhǎng)度.2．綜合題〔1〕畫(huà)出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹(shù)〔以序號(hào)1，2，……10表示樹(shù)結(jié)點(diǎn)〕〔2〕對(duì)上述序列進(jìn)行折半查找，求等概率條件下，成功查找的平均查找長(zhǎng)度 下面答案：〔2〕ASL=〔1x1+2x2+3x4+4x3〕/10=29/108.5哈希函數(shù)1．哈希函數(shù)是記錄關(guān)鍵字值與該記錄存儲(chǔ)地址之間所構(gòu)造的。【對(duì)應(yīng)關(guān)系】2．哈希函數(shù)是記錄關(guān)鍵字值與該記錄______之間所構(gòu)造的對(duì)應(yīng)關(guān)系?！敬鎯?chǔ)地址】3．散列查找的原理是〔〕。【A】A．在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立確定的對(duì)應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C．按關(guān)鍵字值的比擬進(jìn)行查找D．基于二分查找的方法8.6折半查找編程題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(___(1)_____){mid=(low+high)/2;if(a[mid].key==k)return__(2)______; elseif(___(3)_____)low=mid+1; else__(4)______; }___(5)_____; } 下面答案：〔1〕low<=high〔2〕mid〔3〕a[mid].key<k;〔4〕high=mid-1〔5〕return-1;8.7二叉排序樹(shù)編程題1．編程題以下函數(shù)是二叉排序樹(shù)的查找算法，假設(shè)二叉樹(shù)為空，那么返回根結(jié)點(diǎn)的指針，否那么，返回值是指向樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)指針p〔查找成功p指向查到的樹(shù)結(jié)點(diǎn)，不成功p指向?yàn)镹ULL〕完成程序中的空格typedefstructBnode{intkey;structBnode*left;structBnode*right;}Bnode;Bnode*BSearch(Bnode*bt,intk)/*bt用于接收二叉排序樹(shù)的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/{Bnode*p;if(bt==___(1)_____)return(bt);p=bt;while(p->key!=__(2)______) {if(k<p->key) ___(3)_____;else___(4)_____; if(p==NULL)break;}Return(___(5)_____);} 下面答案：〔1〕NULL〔2〕k〔3〕p=p->left〔4〕p=p->right〔5〕p9.排序9.1排序根本概念1．按某關(guān)鍵字對(duì)記錄序列排序，假設(shè)在排序前和排序后仍保持它們的前后關(guān)系，那么排序算法是穩(wěn)定的，否那么是不穩(wěn)定的?！娟P(guān)鍵字相等的記錄】2．以下排序算法中，在一趟排序過(guò)程中，除了其它相關(guān)操作外，只進(jìn)行一次元素間的交換的算法是〔〕。【A】A．直接選擇B．冒泡C．直接插入D．折半插入9.2直接插入排序1．排序算法中，從未排序序列中依次取出元素與已排序序列〔初始為空〕中的元素進(jìn)行比擬〔要求比擬次數(shù)盡量少〕，然后將其放入已排序序列的正確位置的方法是〔〕?！綝】A．冒泡B．直接插入C．選擇排序D．折半插入3．排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列〔初始為空〕的一端的方法，稱為〔〕排序?！綜】A．歸并B．插入C．選擇D．快速4．排序過(guò)程中，每一趟從無(wú)序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序?yàn)橹?，該排序算法?)?！続】A．直接插入排序B．快速排序C．冒泡排序D．選擇排序5．綜合題〔1〕一組記錄的關(guān)鍵字序列為{45，40，65，43，35，95}寫(xiě)出利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果〔要求給出一趟劃分中每次掃描和交換的結(jié)果〕〔2〕同樣對(duì)序列{45，40，65，43，35，95}利用直接插入排序，寫(xiě)