..第3章棧和隊列習題1．選擇題〔1若讓元素1,2,3,4,5依次進棧,則出棧次序不可能出現在〔種情況。A．5,4,3,2,1B．2,1,5,4,3C．4,3,1,2,5D．2,3,5,4,1〔2若已知一個棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為〔。A．iB．n-iC．n-i+1D．不確定〔3數組Ｑ［ｎ］用來表示一個循環隊列,ｆ為當前隊列頭元素的前一位置,ｒ為隊尾元素的位置,假定隊列中元素的個數小于ｎ,計算隊列中元素個數的公式為〔。A．r-fB．<n+f-r>%nC．n+r-fD．〔n+r-f>%n〔4鏈式棧結點為：<data,link>,top指向棧頂.若想摘除棧頂結點,并將刪除結點的值保存到x中,則應執行操作〔。A．x=top->data;top=top->link； B．top=top->link;x=top->link；C．x=top;top=top->link； D．x=top->link；〔5設有一個遞歸算法如下intfact<intn>{//n大于等于0if<n<=0>return1;elsereturnn*fact<n-1>;}則計算fact<n>需要調用該函數的次數為〔。A．n+1B．n-1C．nD．n+2〔6棧在〔中有所應用。A．遞歸調用B．函數調用C．表達式求值D．前三個選項都有〔7為解決計算機主機與打印機間速度不匹配問題,通常設一個打印數據緩沖區。主機將要輸出的數據依次寫入該緩沖區,而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是〔。A．隊列B．棧C．線性表D．有序表〔8設棧S和隊列Q的初始狀態為空,元素e1、e2、e3、e4、e5和e6依次進入棧S,一個元素出棧后即進入Q,若6個元素出隊的序列是e2、e4、e3、e6、e5和e1,則棧S的容量至少應該是〔。A．2B．3C．4D．6〔9在一個具有n個單元的順序棧中,假設以地址高端作為棧底,以top作為棧頂指針,則當作進棧處理時,top的變化為〔。A．top不變B．top=0C．top--D．top++〔10設計一個判別表達式中左,右括號是否配對出現的算法,采用〔數據結構最佳。A．線性表的順序存儲結構B．隊列C.線性表的鏈式存儲結構D.棧〔11用鏈接方式存儲的隊列,在進行刪除運算時〔。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改〔12循環隊列存儲在數組A[0..m]中,則入隊時的操作為〔。A.rear=rear+1B.rear=<rear+1>%<m-1>C.rear=<rear+1>%mD.rear=<rear+1>%<m+1>〔13最大容量為n的循環隊列,隊尾指針是rear,隊頭是front,則隊空的條件是〔。A.<rear+1>%n==frontB.rear==frontC．rear+1==frontD.<rear-l>%n==front〔14棧和隊列的共同點是〔。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點〔15一個遞歸算法必須包括〔。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分〔2回文是指正讀反讀均相同的字符序列,如"abba"和"abdba"均是回文,但"good"不是回文。試寫一個算法判定給定的字符向量是否為回文。<提示：將一半字符入棧>

根據提示,算法可設計為：

//以下為順序棧的存儲結構定義

#defineStackSize100//假定預分配的棧空間最多為100個元素

typedefcharDataType;//假定棧元素的數據類型為字符

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;

intIsHuiwen<char*t>

{//判斷t字符向量是否為回文,若是,返回1,否則返回0

SeqStacks;

inti,len;

chartemp;

InitStack<&s>;

len=strlen<t>;//求向量長度

for<i=0;i<len/2;i++>//將一半字符入棧

Push<&s,t[i]>;

while<!EmptyStack<&s>>

{//每彈出一個字符與相應字符比較

temp=Pop<&s>;

if<temp!=S[i]>

return0;//不等則返回0

elsei++;

}

return1;//比較完畢均相等則返回1

}〔3設從鍵盤輸入一整數的序列：a1,a2,a3,…,an,試編寫算法實現：用棧結構存儲輸入的整數,當ai≠-1時,將ai進棧；當ai=-1時,輸出棧頂整數并出棧。算法應對異常情況〔入棧滿等給出相應的信息。#definemaxsize棧空間容量voidInOutS<ints[maxsize]>//s是元素為整數的棧,本算法進行入棧和退棧操作。{inttop=0;//top為棧頂指針,定義top=0時為棧空。for<i=1;i<=n;i++>//n個整數序列作處理。{scanf<"%d",&x>;//從鍵盤讀入整數序列。if<x!=-1>//讀入的整數不等于-1時入棧。if<top==maxsize-1>{printf<"棧滿\n">;exit<0>;}elses[++top]=x;//x入棧。else//讀入的整數等于-1時退棧。{if<top==0>{printf<"棧空\n">;exit<0>;}elseprintf<"出棧元素是%d\n",s[top--]>；}}}//算法結束。〔4從鍵盤上輸入一個后綴表達式,試編寫算法計算表達式的值。規定：逆波蘭表達式的長度不超過一行,以$符作為輸入結束,操作數之間用空格分隔,操作符只可能有+、-、*、/四種運算。例如：23434+2*$。[題目分析]逆波蘭表達式<即后綴表達式>求值規則如下：設立運算數棧OPND,對表達式從左到右掃描<讀入>,當表達式中掃描到數時,壓入OPND棧。當掃描到運算符時,從OPND退出兩個數,進行相應運算,結果再壓入OPND棧。這個過程一直進行到讀出表達式結束符$,這時OPND棧中只有一個數,就是結果。floatexpr<>//從鍵盤輸入逆波蘭表達式,以‘$’表示輸入結束,本算法求逆波蘭式表達式的值。｛floatOPND[30];//OPND是操作數棧。init<OPND>;//兩棧初始化。floatnum=0.0;//數字初始化。scanf<"%c",&x>;//x是字符型變量。while<x!=’$’>{switch{case‘0’<=x<=’9’:while<<x>=’0’&&x<=’9’>||x==’.’>//拼數if<x!=’.’>//處理整數{num=num*10+〔ord<x>-ord<‘0’>;scanf<"%c",&x>;}else//處理小數部分。{scale=10.0;scanf<"%c",&x>;while<x>=’0’&&x<=’9’>{num=num+<ord<x>-ord<‘0’>/scale;scale=scale*10;scanf<"%c",&x>;}}//elsepush<OPND,num>;num=0.0;//數壓入棧,下個數初始化casex=‘’:break;//遇空格,繼續讀下一個字符。casex=‘+’:push<OPND,pop<OPND>+pop<OPND>>;break;casex=‘-’:x1=pop<OPND>;x2=pop<OPND>;push<OPND,x2-x1>;break;casex=‘*’:push<OPND,pop<OPND>*pop<OPND>>;break;casex=‘/’:x1=pop<OPND>;x2=pop<OPND>;push<OPND,x2/x1>;break;default://其它符號不作處理。}//結束switchscanf<"%c",&x>;//讀入表達式中下一個字符。}//結束while〔x！=‘$’printf<"后綴表達式的值為%f",pop<OPND>>;}//算法結束。[算法討論]假設輸入的后綴表達式是正確的,未作錯誤檢查。算法中拼數部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符,認為是數。這種字符的序號減去字符‘0’的序號得出數。對于整數,每讀入一個數字字符,前面得到的部分數要乘上10再加新讀入的數得到新的部分數。當讀到小數點,認為數的整數部分已完,要接著處理小數部分。小數部分的數要除以10〔或10的冪數變成十分位,百分位,千分位數等等,與前面部分數相加。在拼數過程中,若遇非數字字符,表示數已拼完,將數壓入棧中,并且將變量num恢復為0,準備下一個數。這時對新讀入的字符進入‘+’、‘-’、‘*’、‘/’及空格的判斷,因此在結束處理數字字符的case后,不能加入break語句。〔5假設以I和O分別表示入棧和出棧操作。棧的初態和終態均為空,入棧和出棧的操作序列可表示為僅由I和O組成的序列,稱可以操作的序列為合法序列,否則稱為非法序列。=1\*GB3①下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO=2\*GB3②通過對=1\*GB3①的分析,寫出一個算法,判定所給的操作序列是否合法。若合法,返回true,否則返回false〔假定被判定的操作序列已存入一維數組中。=1\*GB3①A和D是合法序列,B和C是非法序列。=2\*GB3②設被判定的操作序列已存入一維數組A中。intJudge<charA[]>//判斷字符數組A中的輸入輸出序列是否是合法序列。如是,返回true,否則返回false。{i=0;//i為下標。j=k=0;//j和k分別為I和字母O的的個數。while<A[i]!=‘\0’>//當未到字符數組尾就作。{switch<A[i]>{case‘I’:j++;break;//入棧次數增1。case‘O’:k++;if<k>j>{printf<"序列非法\n">；exit<0>;}}i++;//不論A[i]是‘I’或‘O’,指針i均后移。}if<j!=k>{printf<"序列非法\n">；return<false>;}else{printf<"序列合法\n">；return<true>;}}//算法結束。[算法討論]在入棧出棧序列〔即由‘I’和‘O’組成的字符串的任一位置,入棧次數〔‘I’的個數都必須大于等于出棧次數〔即‘O’的個數,否則視作非法序列,立即給出信息,退出算法。整個序列〔即讀到字符數組中字符串的結束標記‘\0’,入棧次數必須等于出棧次數〔題目中要求棧的初態和終態都為空,否則視為非法序列。<6假設以帶頭結點的循環鏈表表示隊列,并且只設一個指針指向隊尾元素站點<注意不設頭指針>,試編寫相應的置空隊、判隊空、入隊和出隊等算法。

算法如下：

//先定義鏈隊結構:

typedefstructqueuenode{

Datatypedata;

structqueuenode*next;

}QueueNode;//以上是結點類型的定義

typedefstruct{

queuenode*rear;

}LinkQueue;//只設一個指向隊尾元素的指針

<1>置空隊

voidInitQueue<LinkQueue*Q>

{//置空隊：就是使頭結點成為隊尾元素

QueueNode*s;

Q->rear=Q->rear->next;//將隊尾指針指向頭結點

while<Q->rear!=Q->rear->next>//當隊列非空,將隊中元素逐個出隊

{s=Q->rear->next;

Q->rear->next=s->next;

free<s>;

}//回收結點空間

}

<2>判隊空

intEmptyQueue<LinkQueue*Q>

{//判隊空

//當頭結點的next指針指向自己時為空隊

returnQ->rear->next->next==Q->rear->next;

}

<3>入隊

voidEnQueue<LinkQueue*Q,Datatypex>

{//入隊

//也就是在尾結點處插入元素

QueueNode*p=<QueueNode*>malloc<sizeof<QueueNode>>;//申請新結點

p->data=x;p->next=Q->rear->next;//初始化新結點并鏈入

Q-rear->next=p;

Q->rear=p;//將尾指針移至新結點

}

<4>出隊

DatatypeDeQueue<LinkQueue*Q>

{//出隊,把頭結點之后的元素摘下

Datatypet;

QueueNode*p;

if<EmptyQueue<Q>>

Error<"Queueunderflow">;

p=Q->rear->next->next;//p指向將要摘下的結點

x=p->data;//保存結點中數據

if<p==Q->rear>

{//當隊列中只有一個結點時,p結點出隊后,要將隊尾指針指向頭結點

Q->rear=Q->rear->next;Q->rear->next=p->next;}

else

Q->rear->next->next=p->next;//摘下結點p

free<p>;//釋放被刪結點

returnx;

}〔7假設以數組Q[m]存放循環隊列中的元素,同時設置一個標志tag,以tag==0和tag==1來區別在隊頭指針<front>和隊尾指針<rear>相等時,隊列狀態為"空"還是"滿"。試編寫與此結構相應的插入<enqueue>和刪除<dlqueue>算法。[解答]循環隊列類定義 #include<assert.h> template<classType>classQueue{ //循環隊列的類定義 public:Queue<int=10>; ~Queue<>{delete[]Q;}voidEnQueue<Type&item>;TypeDeQueue<>;TypeGetFront<>;voidMakeEmpty<>{front=rear=tag=0;} //置空隊列intIsEmpty<>const{returnfront==rear&&tag==0;} //判隊列空否intIsFull<>const{returnfront==rear&&tag==1;} //判隊列滿否 private:intrear,front,tag; //隊尾指針、隊頭指針和隊滿標志Type*Q; //存放隊列元素的數組intm; //隊列最大可容納元素個數 }構造函數 template<classType>Queue<Type>::Queue<intsz>:rear<0>,front<0>,tag<0>,m<sz>{ //建立一個最大具有m個元素的空隊列。Q=newType[m]; //創建隊列空間assert<Q!=0>; //斷言:動態存儲分配成功與否 }插入函數template<classType>voidQueue<Type>::EnQueue<Type&item>{ assert<!IsFull<>>;//判隊列是否不滿,滿則出錯處理rear=<rear+1>%m;//隊尾位置進1,隊尾指針指示實際隊尾位置Q[rear]=item; //進隊列tag=1; //標志改1,表示隊列不空 }刪除函數template<classType>TypeQueue<Type>::DeQueue<>{ assert<!IsEmpty<>>;//判斷隊列是否不空,空則出錯處理front=<front+1>%m; //隊頭位置進1,隊頭指針指示實際隊頭的前一位置tag=0; //標志改0,表示棧不滿returnQ[front]; //返回原隊頭元素的值}讀取隊頭元素函數template<classType>TypeQueue<Type>::GetFront<>{ assert<!IsEmpty<>>;//判斷隊列是否不空,空則出錯處理returnQ[<front+1>%m]; //返回隊頭元素的值}<8如果允許在循環隊列的兩端都可以進行插入和刪除操作。要求：=1\*GB3①寫出循環隊列的類型定義；=2\*GB3②寫出"從隊尾刪除"和"從隊頭插入"的算法。[題目分析]用一維數組v[0..M-1]實現循環隊列,其中M是隊列長度。設隊頭指針front和隊尾指針rear,約定front指向隊頭元素的前一位置,rear指向隊尾元素。定義front=rear時為隊空,<rear+1>%m=front為隊滿。約定隊頭端入隊向下標小的方向發展,隊尾端入隊向下標大的方向發展。〔1#defineM隊列可能達到的最大長度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;〔2elemtpdelqueue<cycqueueQ>//Q是如上定義的循環隊列,本算法實現從隊尾刪除,若刪除成功,返回被刪除元素,否則給出出錯信息。 {if<Q.front==Q.rear>{printf<"隊列空">;exit<0>;} Q.rear=<Q.rear-1+M>%M;//修改隊尾指針。return<Q.data[<Q.rear+1+M>%M]>;//返回出隊元素。}//從隊尾刪除算法結束voidenqueue<cycqueueQ,elemtpx>//Q是順序存儲的循環隊列,本算法實現"從隊頭插入"元素x。{if<Q.rear==<Q.front-1+M>%M>{printf<"隊滿";exit<0>;>Q.data[Q.front]=x;//x入隊列Q.front=<Q.front-1+M>%M;//修改隊頭指針。}//結束從隊頭插入算法。〔9已知Ackermann函數定義如下:=1\*GB3①寫出計算Ack<m,n>的遞歸算法,并根據此算法給出出Ack<2,1>的計算過程。=2\*GB3②寫出計算Ack<m,n>的非遞歸算法。intAck<intm,n>{if<m==0>return<n+1>;elseif<m!=0&&n==0>return<Ack<m-1,1>>;elsereturn<Ack<m-1,Ack<m,m-1>>;}//算法結束〔1Ack<2,1>的計算過程Ack<2,1>=Ack<1,Ack<2,0>>//因m<>0,n<>0而得=Ack<1,Ack<1,1>>//因m<>0,n=0而得=Ack<1,Ack<0,Ack<1,0>>>//因m<>0,n<>0而得=Ack<1,Ack<0,Ack<0,1>>>//因m<>0,n=0而得=Ack<1,Ack<0,2>>//因m=0而得=Ack<1,3>//因m=0而得=Ack<0,Ack<1,2>>//因m<>0,n<>0而得=Ack<0,Ack<0,Ack<1,1>>>//因m<>0,n<>0而得=Ack<0,Ack<0,Ack<0,Ack<1,0>>>>//因m<>0,n<>0而得=Ack<0,Ack<0,Ack<0,Ack<0,1>>>>//因m<>0,n=0而得=Ack<0,Ack<0,Ack<0,2>>>//因m=0而得=Ack<0,Ack<0,3>>//因m=0而得=Ack<0,4>//因n=0而得=5//因n=0而得〔2intAckerman<intm,intn>{intakm[M][N];inti,j;for<j=0;j<N;j++>akm[0][j];=j+1;for<i=1;i<m;i++>{akm[i][0]=akm[i-1][1];for<j=1;j<N;j++>akm[i][j]=akm[i-1][akm[i][j-1]];}return<akm[m][n]>;}//算法結束〔10已知f為單鏈表的表頭指針,鏈表中存儲的都是整型數據,試寫出實現下列運算的遞歸算法：=1\*GB3①求鏈表中的最大整數；=2\*GB3②求鏈表的結點個數；=3\*GB3③求所有整數的平均值。#include<iostream.h>//定義在頭文件"RecurveList.h"中classList; classListNode{ //鏈表結點類friendclassList;private:intdata; //結點數據ListNode*link; //結點指針ListNode<constintitem>:data<item>,link<NULL>{} //構造函數};classList{ //鏈表類private:ListNode*first,current;intMax<ListNode*f>;intNum<ListNode*f>;floatAvg<ListNode*f,int&n>;public:List<>:first<NULL>,current<NULL>{} //構造函數 ~List<>{} //析構函數ListNode*NewNode<constintitem>; //創建鏈表結點,其值為itemvoidNewList<constintretvalue>; //建立鏈表,以輸入retvalue結束voidPrintList<>; //輸出鏈表所有結點數據intGetMax<>{returnMax<first>;} //求鏈表所有數據的最大值intGetNum<>{returnNum<first>;} //求鏈表中數據個數floatGetAvg<>{returnAvg<first>;} //求鏈表所有數據的平均值}; ListNode*List::NewNode<constintitem>{ //創建新鏈表結點ListNode*newnode=newListNode<item>;returnnewnode;}voidList::NewList<constintretvalue>{ //建立鏈表,以輸入retvalue結束first=NULL;intvalue;ListNode*q;cout<<"Inputyourdata:\n"; //提示cin>>value; //輸入while<value!=retvalue>{//輸入有效q=NewNode<value>; //建立包含value的新結點if<first==NULL>first=current=q; //空表時,新結點成為鏈表第一個結點else{current->link=q;current=q;} //非空表時,新結點鏈入鏈尾cin>>value; //再輸入}current->link=NULL; //鏈尾封閉}voidList::PrintList<>{ //輸出鏈表cout<<"\nTheListis:\n";ListNode*p=first;while<p!=NULL>{ cout<<p->data<<'';p=p->link;} cout<<‘\n’;}intList::Max<ListNode*f>{ //遞歸算法:求鏈表中的最大值if<f->link==NULL>returnf->data; //遞歸結束條件 inttemp=Max<f->link>; //在當前結點的后繼鏈表中求最大值if<f->data>temp>returnf->data; //如果當前結點的值還要大,返回當前檢點值 elsereturntemp; //否則返回后繼鏈表中的最大值}intList::Num<ListNode*f>{ //遞歸算法:求鏈表中結點個數 if<f==NULL>return0; //空表,返回0return1+Num<f->link>; //否則,返回后繼鏈表結點個數加1}floatList::Avg<ListNode*f,int&n>{//遞歸算法:求鏈表中所有元素的平均值if<f->link==NULL> //鏈表中只有一個結點,遞歸結束條件{n=1;return<float><f->data>;}else{floatSum=Avg<f->link,n>*n;n++;return<f->data+Sum>/n;}}#include"RecurveList.h" //定義在主文件中intmain<intargc,char*argv[]>{Listtest;intfinished;cout<<"輸入建表結束標志數據：";cin>>finished; //輸入建表結束標志數據test.NewList<finished>; //建立鏈表test.PrintList<>; //打印鏈表cout<<"\nTheMaxis:"<<test.GetMax<>;cout<<"\nTheNumis:"<<test.GetNum<>;cout<<"\nTheAveis:"<<test.GetAve<><<'\n'; printf<"HelloWorld!\n">;return0;}第4章串、數組和廣義表習題1．選擇題〔1串是一種特殊的線性表,其特殊性體現在〔。A．可以順序存儲B．數據元素是一個字符C．可以鏈式存儲D．數據元素可以是多個字符若〔2串下面關于串的的敘述中,〔是不正確的？A．串是字符的有限序列B．空串是由空格構成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲,也可以采用鏈式存儲〔3串"ababaaababaa"的next數組為〔。〔4串"ababaabab"的nextval為〔。A．010104101B．010102101C．010100011D．010101011〔5串的長度是指〔。A．串中所含不同字母的個數B．串中所含字符的個數C．串中所含不同字符的個數D．串中所含非空格字符的個數〔6假設以行序為主序存儲二維數組A=array[1..100,1..100],設每個數據元素占2個存儲單元,基地址為10,則LOC[5,5]=〔。A．808B．818C．1010D．1020〔7設有數組A[i,j],數組的每個元素長度為3字節,i的值為1到8,j的值為1到10,數組從內存首地址BA開始順序存放,當用以列為主存放時,元素A[5,8]的存儲首地址為〔。A．BA+141B．BA+180C．BA+222D．BA+225〔8設有一個10階的對稱矩陣A,采用壓縮存儲方式,以行序為主存儲,a11為第一元素,其存儲地址為1,每個元素占一個地址空間,則a85的地址為〔。A．13B．33C．18D．40〔9若對n階對稱矩陣A以行序為主序方式將其下三角形的元素<包括主對角線上所有元素>依次存放于一維數組B[1..<n<n+1>>/2]中,則在B中確定aij〔i<j的位置k的關系為〔。A．i*<i-1>/2+jB．j*<j-1>/2+iC．i*<i+1>/2+jD．j*<j+1>/2+i〔10A[N,N]是對稱矩陣,將下面三角〔包括對角線以行序存儲到一維數組T[N<N+1>/2]中,則對任一上三角元素a[i][j]對應T[k]的下標k是〔。A．i<i-1>/2+jB．j<j-1>/2+iC．i<j-i>/2+1D．j<i-1>/2+1〔11設二維數組A[1..m,1..n]〔即m行n列按行存儲在數組B[1..m*n]中,則二維數組元素A[i,j]在一維數組B中的下標為〔。A．<i-1>*n+jB．<i-1>*n+j-1C．i*<j-1>D．j*m+i-1〔12數組A[0..4,-1..-3,5..7]中含有元素的個數〔。A．55B．45C．36D．16〔13廣義表A=<a,b,<c,d>,<e,<f,g>>>,則Head<Tail<Head<Tail<Tail<A>>>>>的值為〔。A．<g>B．<d>C．cD．d〔14廣義表<<a,b,c,d>>的表頭是〔,表尾是〔。A．aB．<>C．<a,b,c,d>D．<b,c,d>〔15設廣義表L=<<a,b,c>>,則L的長度和深度分別為〔。A．1和1B．1和3C．1和2D．2和3〔1已知模式串t=‘abcaabbabcab’寫出用KMP法求得的每個字符對應的next和nextval函數值。模式串t的next和nextval值如下：j123456789101112t串abcaabbabcabnext[j]011122312345nextval[j]011021301105〔2設目標為t="abcaabbabcabaacbacba",模式為p="abcabaa"=1\*GB3①計算模式p的naxtval函數值；=2\*GB3②不寫出算法,只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。=1\*GB3①p的nextval函數值為0110132。〔p的next函數值為0111232。=2\*GB3②利用KMP<改進的nextval>算法,每趟匹配過程如下：第一趟匹配：abcaabbabcabaacbacbaabcab<i=5,j=5>第二趟匹配：abcaabbabcabaacbacbaabc<i=7,j=3>第三趟匹配：abcaabbabcabaacbacbaa<i=7,j=1>第四趟匹配：abcaabbabcabaacbacba<成功>abcabaa<i=15,j=8>〔3數組A中,每個元素A[i,j]的長度均為32個二進位,行下標從-1到9,列下標從1到11,從首地址S開始連續存放主存儲器中,主存儲器字長為16位。求：=1\*GB3①存放該數組所需多少單元？=2\*GB3②存放數組第4列所有元素至少需多少單元？=3\*GB3③數組按行存放時,元素A[7,4]的起始地址是多少？=4\*GB3④數組按列存放時,元素A[4,7]的起始地址是多少？每個元素32個二進制位,主存字長16位,故每個元素占2個字長,行下標可平移至1到11。〔1242〔222〔3s+182〔4s+142<4>請將香蕉banana用工具H<>—Head<>,T<>—Tail<>從L中取出。L=<apple,<orange,<strawberry,<banana>>,peach>,pear>H〔H〔T〔H〔T〔H〔T〔L〔5寫一個算法統計在輸入字符串中各個不同字符出現的頻度并將結果存入文件〔字符串中的合法字符為A-Z這26個字母和0-9這10個數字。voidCount〔//統計輸入字符串中數字字符和字母字符的個數。｛inti,num[36]；charch；for〔i＝0；i<36；i++num[i]＝０；//初始化while〔〔ch＝getchar〔!=‘#’//‘#’表示輸入字符串結束。if〔‘0’<=ch<=‘9’｛i=ch－48;num[i]++；｝//數字字符elseif〔‘A’<=ch<=‘Z’｛i=ch-65+10;num[i]++；｝//字母字符for〔i=0；i<10；i++//輸出數字字符的個數printf〔"數字％d的個數＝％d\n",i,num[i]；for〔i＝10；i<36；i++//求出字母字符的個數printf〔"字母字符％c的個數＝％d\n",i＋55,num[i]；｝//算法結束。〔6寫一個遞歸算法來實現字符串逆序存儲,要求不另設串存儲空間。[題目分析]實現字符串的逆置并不難,但本題"要求不另設串存儲空間"來實現字符串逆序存儲,即第一個輸入的字符最后存儲,最后輸入的字符先存儲,使用遞歸可容易做到。voidInvertStore<charA[]>//字符串逆序存儲的遞歸算法。{charch;staticinti=0;//需要使用靜態變量scanf<"%c",&ch>;if<ch!='.'>//規定'.'是字符串輸入結束標志 {InvertStore<A>; A[i++]=ch;//字符串逆序存儲 }A[i]='\0';//字符串結尾標記}//結束算法InvertStore。〔7編寫算法,實現下面函數的功能。函數voidinsert<char*s,char*t,intpos>將字符串t插入到字符串s中,插入位置為pos。假設分配給字符串s的空間足夠讓字符串t插入。〔說明：不得使用任何庫函數[題目分析]本題是字符串的插入問題,要求在字符串s的pos位置,插入字符串t。首先應查找字符串s的pos位置,將第pos個字符到字符串s尾的子串向后移動字符串t的長度,然后將字符串t復制到字符串s的第pos位置后。對插入位置pos要驗證其合法性,小于1或大于串s的長度均為非法,因題目假設給字符串s的空間足夠大,故對插入不必判溢出。voidinsert<char*s,char*t,intpos>//將字符串t插入字符串s的第pos個位置。{inti=1,x=0;char*p=s,*q=t;//p,q分別為字符串s和t的工作指針if<pos<1>{printf<"pos參數位置非法\n">;exit<0>;}while<*p!=’\0’&&i<pos>{p++;i++;}//查pos位置//若pos小于串s長度,則查到pos位置時,i=pos。if<*p=='/0'>{printf<"%d位置大于字符串s的長度",pos>;exit<0>;}else//查找字符串的尾while<*p!='/0'>{p++;i++;}//查到尾時,i為字符‘\0’的下標,p也指向‘\0’。while<*q!='\0'>{q++;x++;}//查找字符串t的長度x,循環結束時q指向'\0'。for<j=i;j>=pos;j-->{*<p+x>=*p;p--;}//串s的pos后的子串右移,空出串t的位置。q--;//指針q回退到串t的最后一個字符for<j=1;j<=x;j++>*p--=*q--;//將t串插入到s的pos位置上[算法討論]串s的結束標記<'\0'>