【正文】 n的循環(huán)隊(duì)列，隊(duì)滿(mǎn)條件是(rear+1)%n==front，隊(duì)空條件是rear==front。A. 遞歸部分 B. 終止條件和遞歸部分C. 迭代部分 D. 終止條件和迭代部分答案：B2．算法設(shè)計(jì)題（1）將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedef struct{int top[2],bot[2]。兩棧頂指針相鄰時(shí)為棧滿(mǎn)。Init()[1]=m。1。push(stk S入棧成功返回1，失敗返回0{if(i0||i1){ cout“棧號(hào)輸入不對(duì)”endl。}switch(i)return(1)。1: [[1]]=x。退棧操作ElemType pop(stk S,int}return([[0]])。 }∥算法結(jié)束(4)([0]==1 amp。請(qǐng)注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。(提示：將一半字符入棧)[算法描述]define StackSize 100 //假定預(yù)分配的?？臻g最多為100個(gè)元素typedef char DataType。int IsHuiwen( char *t){//判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStack s。s)。 i++)//將一半字符入棧Push( amp。s)。}[算法描述]define maxsize ?？臻g容量void InOutS(int s[maxsize])//s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。 i=n。 if(x!=1) // 讀入的整數(shù)不等于1時(shí)入棧。 //x入棧。} else cout“出棧元素是” s[top]endl。struct queuenode *next。 //只設(shè)一個(gè)指向隊(duì)尾元素的指針(1) 置空隊(duì)void InitQueue( LinkQueue *Q){ //置空隊(duì)：就是使頭結(jié)點(diǎn)成為隊(duì)尾元素　QueueNode *s。delete s。}(3) 入隊(duì)void EnQueue( LinkQueue *Q, Datatype x){ //入隊(duì)。//初始化新結(jié)點(diǎn)并鏈入Qrearnext=p。QueueNode *p。 //保存結(jié)點(diǎn)中數(shù)據(jù)if (p==Qrear){//當(dāng)隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí)，p結(jié)點(diǎn)出隊(duì)后，要將隊(duì)尾指針指向頭結(jié)點(diǎn)　Qrear = Qrearnext。//摘下結(jié)點(diǎn)pdelete p。 （3）串“ababaaababaa”的next數(shù)組為（ ）。（6）假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100,1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5,5]=（ ）。（8）設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。設(shè)每個(gè)字符占一個(gè)字節(jié)。A．(i1)*n+j B．(i1)*n+j1 C．i*(j1) D．j*m+i1答案：A解釋?zhuān)禾厥庵捣?。?3）廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為（ ）。（15）設(shè)廣義表L=((a,b,c))，則L的長(zhǎng)度和深度分別為（ ）。L=(apple,(orange,(strawberry,(banana)),peach),pear)答案：H（H（T（H（T（H（T（L）））））））3．算法設(shè)計(jì)題（1）寫(xiě)一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為AZ這26個(gè)字母和09這10個(gè)數(shù)字）。[算法描述]void Count（）//統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。num[i]++；｝// 字母字符　for（i=0；i10；i++） // 輸出數(shù)字字符的個(gè)數(shù) cout“數(shù)字”i “的個(gè)數(shù)=”num[i]endl。[算法描述]void InvertStore(char A[])//字符串逆序存儲(chǔ)的遞歸算法。if (ch!= 39。是字符串輸入結(jié)束標(biāo)志 {InvertStore(A)。 //字符串結(jié)尾標(biāo)記}（3）編寫(xiě)算法，實(shí)現(xiàn)下面函數(shù)的功能。首先應(yīng)查找字符串s的pos位置，將第pos個(gè)字符到字符串s尾的子串向后移動(dòng)字符串t的長(zhǎng)度，然后將字符串t復(fù)制到字符串s的第pos位置后。 char *p=s,*q=t。amp。 if(*p == 39。} else //查找字符串的尾 while(*p!= 39。} //查到尾時(shí)，i為字符‘\0’的下標(biāo)，p也指向‘\0’。 x++。j=pos 。 q。 //將t串插入到s的pos位置上 [算法討論] 串s的結(jié)束標(biāo)記(39。 A．唯一的 Ｂ．有多種C．有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子 Ｄ．有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子答案：A 解釋?zhuān)阂驗(yàn)槎鏄?shù)有左孩子、右孩子之分，故一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是唯一的。A．11 B．10 C．11至1025之間 D．10至1024之間答案：C解釋?zhuān)喝裘繉觾H有一個(gè)結(jié)點(diǎn)，則樹(shù)高h(yuǎn)為1025；且其最小樹(shù)高為+（6）利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（ ）。（8）若二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹(shù)的位置，利用（ ）遍歷方法最合適。A．所有的結(jié)點(diǎn)均無(wú)左孩子 B．所有的結(jié)點(diǎn)均無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn) D．是任意一棵二叉樹(shù)答案：C解釋?zhuān)阂驗(yàn)橄刃虮闅v結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當(dāng)沒(méi)有左子樹(shù)時(shí)，就是“中右”和“右中”；當(dāng)沒(méi)有右子樹(shù)時(shí)，就是“中左”和“左中”。設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，由二叉樹(shù)的性質(zhì)n0=n2+1，則總結(jié)點(diǎn)數(shù)n= n0+n2=2*n01，得到n0=100。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ ）個(gè)。2．應(yīng)用題（1）試找出滿(mǎn)足下列條件的二叉樹(shù)① 先序序列與后序序列相同 ②中序序列與后序序列相同③ 先序序列與中序序列相同 ④中序序列與層次遍歷序列相同答案：先序遍歷二叉樹(shù)的順序是“根—左子樹(shù)—右子樹(shù)”，中序遍歷“左子樹(shù)—根—右子樹(shù)”，后序遍歷順序是：“左子樹(shù)—右子樹(shù)―根＂，根據(jù)以上原則有① 或?yàn)榭諛?shù)，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(shù)②③將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)（或森林）。 //如果是空樹(shù)，則葉子結(jié)點(diǎn)個(gè)數(shù)為0 else if(Tlchild==NULLamp。}（2）判別兩棵樹(shù)是否相等。bool tree2IsNull = (tree2==NULL)。 tree2IsNull){//如果兩個(gè)都是NULL，則相等return 0。pareTree(tree1right,tree2left))。T){ BiTree temp。 else { temp = Tlchild。 //遞歸交換左子樹(shù) ChangeLR(Trchild)。[算法描述]int Width(BiTree bt)//求二叉樹(shù)bt的最大寬度{if (bt==null) return (0)。last=1。 //根結(jié)點(diǎn)入隊(duì)列while(front=last) {p=Q[front++]。 //右子女入隊(duì)if (frontlast) //一層結(jié)束， {last=rear。}//結(jié)束width若某個(gè)結(jié)點(diǎn)左子樹(shù)空右子樹(shù)非空或者右子樹(shù)空左子樹(shù)非空，則該結(jié)點(diǎn)為度為1的結(jié)點(diǎn)第7章 查找1．選擇題（1）對(duì)n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為（ ）。（3）如果要求一個(gè)線(xiàn)性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，最好采用( )查找法。（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。=5，與第五個(gè)元素20比較，58大于20，再取235。A．3 B．4 C．5 D．6答案：B解釋?zhuān)?2個(gè)記錄的有序表，其折半查找的判定樹(shù)深度為+ A．（100，80， 90， 60， 120，110，130） B．（100，120，110，130，80， 60， 90）C．（100，60， 80， 90， 120，110，130）D．(100，80， 60， 90， 120，130，110)答案：C解釋?zhuān)篈、B、C、D四個(gè)選項(xiàng)構(gòu)造二叉排序樹(shù)都以100為根，易知A、B、D三個(gè)序列中第一個(gè)比100小的關(guān)鍵字為80，即100的左孩子為80，而C選項(xiàng)中100的左孩子為60，故選C。 A．B樹(shù)和B+樹(shù)都是平衡的多叉樹(shù) B．B樹(shù)和B+樹(shù)都可用于文件的索引結(jié)構(gòu)C．B樹(shù)和B+樹(shù)都能有效地支持順序檢索 D．B樹(shù)和B+樹(shù)都能有效地支持隨機(jī)檢索答案：C（11）m階B樹(shù)是一棵（ ）。=6）：305 633 7 42 87 4 24 54 72 95②查找元素54，需依次與30, 63, 42, 54 元素比較；③查找元素90，需依次與30, 63,87, 95元素比較；④求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。{if（low≤high） //low和high分別是有序表的下界和上界 {mid=（low+high）/2； if（r[mid].key==k）return （mid）； else if（r[mid].keyk）return （BinSrch（r,k，mid+1，high））。[題目分析] 根據(jù)二叉排序樹(shù)中序遍歷所得結(jié)點(diǎn)值為增序的性質(zhì)，在遍歷中將當(dāng)前遍歷結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)值比較，即可得出結(jié)論，為此設(shè)全局指針變量pre（初值為null）和全局變量flag，初值為true。} *BTree。 flag） { Judgebst（Tlchild,flag）；// 中序遍歷左子樹(shù) if（pre==null）pre=T；// 中序遍歷的第一個(gè)結(jié)點(diǎn)不必判斷 else if（predataTdata）pre=T；//前驅(qū)指針指向當(dāng)前結(jié)點(diǎn) else{flag=flase；} //不是完全二叉樹(shù) Judgebst （Trchild,flag）；// 中序遍歷右子樹(shù)}//JudgeBST算法結(jié)束第8章 排序1．選擇題（1）從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，這種排序方法稱(chēng)為（ ）。（4）對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)最多為（ ）。（6）對(duì)n個(gè)關(guān)鍵字作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（ ）。A．16，72，31，23，94，53 B．94，23，31，72，16，53 C．16，53，23，94，31，72 D．16，23，53，31，94，72答案：D解釋?zhuān)篋選項(xiàng)為小根堆（9）堆是一種（ ）排序。A．希爾排序 B．快速排序 C．歸并排序 D．堆排序答案：C解釋?zhuān)憾雅判?、希爾排序的空間復(fù)雜度為O(1)，快速排序的空間復(fù)雜度為O(log2n)，歸并排序的空間復(fù)雜度為O(n)。A．冒泡排序 B．快速排序 C．簡(jiǎn)單選擇排序 D．堆排序答案：D（15）下列排序算法中，（ ）不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。設(shè)此組記錄存放于數(shù)組r[l..n]中。int index (RecType R[],int l,h,datatype key){int i=l,j=h。 if (R[j].key==key) return j。 if (R[i].key==key) return