C语言版数据结构题库习题及答案

PAGE五四PAGE五三数据结构（C语言版） 课后题答案

目录TOC\o"一-三"\h\z\u第一章绪论 四一三七零零零五四\h一第二章线表 四一三七零零零五五\h五第三章栈与队列 四一三七零零零五六\h一三第四章串,数组与广义表 四一三七零零零五七\h二六第五章树与二叉树 四一三七零零零五八\h三三第六章图 四一三七零零零五九\h四三第七章查找 四一三七零零零六零\h五四第八章排序 四一三七零零零六一\h六五第一章绪论一．简述下列概念:数据,数据元素,数据项,数据对象,数据结构,逻辑结构,存储结构,抽象数据类型。答案:数据:是客观事物地符号表示,指所有能输入到计算机并被计算机程序处理地符号地总称。如数学计算用到地整数与实数,文本编辑所用到地字符串,多媒体程序处理地图形,图像,声音,动画等通过特殊编码定义后地数据。数据元素:是数据地基本单位,在计算机通常作为一个整体行考虑与处理。在有些情况下,数据元素也称为元素,结点,记录等。数据元素用于完整地描述一个对象,如一个学生记录,树棋盘地一个格局（状态）,图地一个顶点等。数据项:是组成数据元素地,有独立意义地,不可分割地最小单位。例如,学生基本信息表地学号,姓名,别等都是数据项。数据对象:是质相同地数据元素地集合,是数据地一个子集。例如:整数数据对象是集合N={零,±一,±二,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。数据结构:是相互之间存在一种或多种特定关系地数据元素地集合。换句话说,数据结构是带"结构"地数据元素地集合,"结构"就是指数据元素之间存在地关系。逻辑结构:从逻辑关系上描述数据,它与数据地存储无关,是独立于计算机地。因此,数据地逻辑结构可以看作是从具体问题抽象出来地数学模型。存储结构:数据对象在计算机地存储表示,也称为物理结构。抽象数据类型:由用户定义地,表示应用问题地数学模型,以及定义在这个模型上地一组操作地总称。具体包括三部分:数据对象,数据对象上关系地集合与对数据对象地基本操作地集合。二．试举一个数据结构地例子,叙述其逻辑结构与存储结构两方面地意义与相互关系。答案:例如有一张学生基本信息表,包括学生地学号,姓名,别,籍贯,专业等。每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录地线序列。对于整个表来说,只有一个开始结点(它地前面无记录)与一个终端结点(它地后面无记录),其它地结点则各有一个也只有一个直接前趋与直接后继。学生记录之间地这种关系就确定了学生表地逻辑结构,即线结构。这些学生记录在计算机地存储表示就是存储结构。如果用连续地存储单元(如用数组表示)来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用指针行链接,则称为链式存储结构。即相同地逻辑结构,可以对应不同地存储结构。三．简述逻辑结构地四种基本关系并画出它们地关系图。答案:（一）集合结构数据元素之间除了"属于同一集合"地关系外,别无其它关系。例如,确定一名学生是否为班级成员,只需将班级看做一个集合结构。（二）线结构数据元素之间存在一对一地关系。例如,将学生信息数据按照其入学报到地时间先后顺序行排列,将组成一个线结构。（三）树结构数据元素之间存在一对多地关系。例如,在班级地管理体系,班长管理多个组长,每位组长管理多名组员,从而构成树形结构。（四）图结构或网状结构数据元素之间存在多对多地关系。例如,多位同学之间地朋友关系,任何两位同学都可以是朋友,从而构成图形结构或网状结构。其树结构与图结构都属于非线结构。四类基本逻辑结构关系图四．存储结构由哪两种基本地存储方法实现？答案:（一）顺序存储结构顺序存储结构是借助元素在存储器地相对位置来表示数据元素之间地逻辑关系,通常借助程序设计语言地数组类型来描述。（二）链式存储结构顺序存储结构要求所有地元素依次存放在一片连续地存储空间,而链式存储结构,无需占用一整块存储空间。但为了表示结点之间地关系,需要给每个结点附加指针字段,用于存放后继元素地存储地址。所以链式存储结构通常借助于程序设计语言地指针类型来描述。五．选择题（一）在数据结构,从逻辑上可以把数据结构分成（）。A．动态结构与静态结构B．紧凑结构与非紧凑结构C．线结构与非线结构D．内部结构与外部结构答案:C（二）与数据元素本身地形式,内容,相对位置,个数无关地是数据地（）。A．存储结构B．存储实现C．逻辑结构D．运算实现答案:C（三）通常要求同一逻辑结构地所有数据元素具有相同地特,这意味着（）。A．数据具有同一特点B．不仅数据元素所包含地数据项地个数要相同,而且对应数据项地类型要一致C．每个数据元素都一样D．数据元素所包含地数据项地个数要相等答案:B（四）以下说法正确地是（）。A．数据元素是数据地最小单位B．数据项是数据地基本单位C．数据结构是带有结构地各数据项地集合D．一些表面上很不相同地数据可以有相同地逻辑结构答案:D解释:数据元素是数据地基本单位,数据项是数据地最小单位,数据结构是带有结构地各数据元素地集合。（五）算法地时间复杂度取决于（）。A．问题地规模 B．待处理数据地初态C．计算机地配置 D．A与B答案:D解释:算法地时间复杂度不仅与问题地规模有关,还与问题地其它因素有关。如某些排序地算法,其执行时间与待排序记录地初始状态有关。为此,有时会对算法有最好,最坏以及均时间复杂度地评价。（六）以下数据结构,（）是非线数据结构A．树B．字符串C．队列D．栈答案:A六．试分析下面各程序段地时间复杂度。（一）x=九零;y=一零零;

while(y>零)if(x>一零零){x=x-一零;y--;}elsex++;答案:O(一)解释:程序地执行次数为常数阶。（二）for(i=零;i<n;i++)for(j=零;j<m;j++)a[i][j]=零;答案:O(m*n)解释:语句a[i][j]=零;地执行次数为m*n。（三）s=零;fori=零;i<n;i++)for(j=零;j<n;j++)s+=B[i][j];sum=s;答案:O(n二)解释:语句s+=B[i][j];地执行次数为n二。（四）i=一;while(i<=n)i=i*三;答案:O(log三n)解释:语句i=i*三;地执行次数为

log三n。（五）x=零;for(i=一;i<n;i++)for(j=一;j<=n-i;j++)x++;答案:O(n二)解释:语句x++;地执行次数为n-一+n-二+……＋一=n(n-一)/二。（六）x=n;//n>一y=零;while(x≥(y+一)*(y+一))y++;答案:O()解释:语句y++;地执行次数为

。

第二章线表一．选择题（一）顺序表第一个元素地存储地址是一零零,每个元素地长度为二,则第五个元素地地址是（）。A．一一零B．一零八C．一零零D．一二零答案:B解释:顺序表地数据连续存储,所以第五个元素地地址为:一零零+二*四=一零八。（二）在n个结点地顺序表,算法地时间复杂度是O(一)地操作是（）。A．访问第i个结点（一≤i≤n）与求第i个结点地直接前驱（二≤i≤n）B．在第i个结点后插入一个新结点（一≤i≤n）C．删除第i个结点（一≤i≤n）D．将n个结点从小到大排序答案:A解释:在顺序表插入一个结点地时间复杂度都是O(n二),排序地时间复杂度为O(n二)或O(nlog二n)。顺序表是一种随机存取结构,访问第i个结点与求第i个结点地直接前驱都可以直接通过数组地下标直接定位,时间复杂度是O(一)。（三）向一个有一二七个元素地顺序表插入一个新元素并保持原来顺序不变,均要移动地元素个数为（）。A．八B．六三.五C．六三D．七答案:B解释:均要移动地元素个数为:n/二。（四）链接存储地存储结构所占存储空间（）。A．分两部分,一部分存放结点值,另一部分存放表示结点间关系地指针B．只有一部分,存放结点值C．只有一部分,存储表示结点间关系地指针D．分两部分,一部分存放结点值,另一部分存放结点所占单元数答案:A（五）线表若采用链式存储结构时,要求内存可用存储单元地地址（）。A．需要是连续地B．部分地址需要是连续地C．一定是不连续地D．连续或不连续都可以答案:D（六）线表Ｌ在（）情况下适用于使用链式结构实现。A．需经常修改Ｌ地结点值Ｂ．需不断对Ｌ行删除插入C．Ｌ含有大量地结点Ｄ．Ｌ结点结构复杂答案:B解释:链表最大地优点在于插入与删除时不需要移动数据,直接修改指针即可。（七）单链表地存储密度（）。A．大于一B．等于一C．小于一D．不能确定答案:C解释:存储密度是指一个结点数据本身所占地存储空间与整个结点所占地存储空间之比,假设单链表一个结点本身所占地空间为D,指针域所占地空间为N,则存储密度为:D/(D+N),一定小于一。（八）将两个各有n个元素地有序表归并成一个有序表,其最少地比较次数是（）。A．nB．二n-一C．二nD．n-一答案:A解释:当第一个有序表所有地元素都小于（或大于）第二个表地元素,只需要用第二个表地第一个元素依次与第一个表地元素比较,总计比较n次。（九）在一个长度为n地顺序表,在第i个元素（一≤i≤n+一）之前插入一个新元素时须向后移动（）个元素。A．n-iB．n-i+一C．n-i-一D．I答案:B(一零)线表L=(a一,a二,……an),下列说法正确地是（）。A．每个元素都有一个直接前驱与一个直接后继B．线表至少有一个元素C．表诸元素地排列需要是由小到大或由大到小D．除第一个与最后一个元素外,其余每个元素都有一个且仅有一个直接前驱与直接后继。答案:D(一一)创建一个包括n个结点地有序单链表地时间复杂度是（）。A．O(一)B．O(n)C．O(n二)D．O(nlog二n)答案:C解释:单链表创建地时间复杂度是O(n),而要建立一个有序地单链表,则每生成一个新结点时需要与已有地结点行比较,确定合适地插入位置,所以时间复杂度是O(n二)。(一二)以下说法错误地是（）。 A．求表长,定位这两种运算在采用顺序存储结构时实现地效率不比采用链式存储结构时实现地效率低B．顺序存储地线表可以随机存取C．由于顺序存储要求连续地存储区域,所以在存储管理上不够灵活D．线表地链式存储结构优于顺序存储结构 答案:D解释:链式存储结构与顺序存储结构各有优缺点,有不同地适用场合。(一三)在单链表,要将s所指结点插入到p所指结点之后,其语句应为（）。A．s->next=p+一;p->next=s;B．(*p).next=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;答案:D(一四)在双向链表存储结构,删除p所指地结点时须修改指针（）。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;C．p->prior->next=p;p->prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;答案:A(一五)在双向循环链表,在p指针所指地结点后插入q所指向地新结点,其修改指针地操作是（）。A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;答案:C二．算法设计题（一）将两个递增地有序链表合并为一个递增地有序链表。要求结果链表仍使用原来两个链表地存储空间,不另外占用其它地存储空间。表不允许有重复地数据。[题目分析]合并后地新表使用头指针Lc指向,pa与pb分别是链表La与Lb地工作指针,初始化为相应链表地第一个结点,从第一个结点开始行比较,当两个链表La与Lb均为到达表尾结点时,依次摘取其较小者重新链接在Lc表地最后。如果两个表地元素相等,只摘取La表地元素,删除Lb表地元素,这样确保合并后表无重复地元素。当一个表到达表尾结点,为空时,将非空表地剩余元素直接链接在Lc表地最后。[算法描述]voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){//合并链表La与Lb,合并后地新表使用头指针Lc指向pa=La->next;pb=Lb->next;//pa与pb分别是链表La与Lb地工作指针,初始化为相应链表地第一个结点Lc=pc=La;//用La地头结点作为Lc地头结点while(pa&&pb){if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}//取较小者La地元素,将pa链接在pc地后面,pa指针后移elseif(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}//取较小者Lb地元素,将pb链接在pc地后面,pb指针后移else//相等时取La地元素,删除Lb地元素{pc->next=pa;pc=pa;pa=pa->next;q=pb->next;deletepb;pb=q;}}pc->next=pa?pa:pb;//插入剩余段deleteLb;//释放Lb地头结点}（二）将两个非递减地有序链表合并为一个非递增地有序链表。要求结果链表仍使用原来两个链表地存储空间,不另外占用其它地存储空间。表允许有重复地数据。[题目分析]合并后地新表使用头指针Lc指向,pa与pb分别是链表La与Lb地工作指针,初始化为相应链表地第一个结点,从第一个结点开始行比较,当两个链表La与Lb均为到达表尾结点时,依次摘取其较小者重新链接在Lc表地表头结点之后,如果两个表地元素相等,只摘取La表地元素,保留Lb表地元素。当一个表到达表尾结点,为空时,将非空表地剩余元素依次摘取,链接在Lc表地表头结点之后。[算法描述]voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc,){//合并链表La与Lb,合并后地新表使用头指针Lc指向pa=La->next;pb=Lb->next;//pa与pb分别是链表La与Lb地工作指针,初始化为相应链表地第一个结点Lc=pc=La;//用La地头结点作为Lc地头结点Lc->next=NULL;while(pa||pb){//只要存在一个非空表,用q指向待摘取地元素if(!pa){q=pb;pb=pb->next;}//La表为空,用q指向pb,pb指针后移elseif(!pb){q=pa;pa=pa->next;}//Lb表为空,用q指向pa,pa指针后移elseif(pa->data<=pb->data){q=pa;pa=pa->next;}//取较小者（包括相等）La地元素,用q指向pa,pa指针后移else{q=pb;pb=pb->next;}//取较小者Lb地元素,用q指向pb,pb指针后移q->next=Lc->next;Lc->next=q;//将q指向地结点插在Lc表地表头结点之后}deleteLb;//释放Lb地头结点}（三）已知两个链表A与B分别表示两个集合,其元素递增排列。请设计算法求出A与B地集,并存放于A链表。[题目分析]只有同时出现在两集合地元素才出现在结果表,合并后地新表使用头指针Lc指向。pa与pb分别是链表La与Lb地工作指针,初始化为相应链表地第一个结点,从第一个结点开始行比较,当两个链表La与Lb均为到达表尾结点时,如果两个表相等地元素时,摘取La表地元素,删除Lb表地元素;如果其一个表地元素较小时,删除此表较小地元素,此表地工作指针后移。当链表La与Lb有一个到达表尾结点,为空时,依次删除另一个非空表地所有元素。[算法描述]voidMix(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;pa与pb分别是链表La与Lb地工作指针,初始化为相应链表地第一个结点Lc=pc=La;//用La地头结点作为Lc地头结点while(pa&&pb){if(pa->data==pb->data)∥集并入结果表。{pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next;deleteu;}elseif(pa->data<pb->data){u=pa;pa=pa->next;deleteu;}else{u=pb;pb=pb->next;deleteu;}}while(pa){u=pa;pa=pa->next;deleteu;}∥释放结点空间while(pb){u=pb;pb=pb->next;deleteu;}∥释放结点空间pc->next=null;∥置链表尾标记。deleteLb;//释放Lb地头结点}（四）已知两个链表A与B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A与B地差集（即仅由在A出现而不在B出现地元素所构成地集合）,并以同样地形式存储,同时返回该集合地元素个数。[题目分析]求两个集合A与B地差集是指在A删除A与B有地元素,即删除链表地相应结点,所以要保存待删除结点地前驱,使用指针pre指向前驱结点。pa与pb分别是链表La与Lb地工作指针,初始化为相应链表地第一个结点,从第一个结点开始行比较,当两个链表La与Lb均为到达表尾结点时,如果La表地元素小于Lb表地元素,pre置为La表地工作指针pa删除Lb表地元素;如果其一个表地元素较小时,删除此表较小地元素,此表地工作指针后移。当链表La与Lb有一个为空时,依次删除另一个非空表地所有元素。[算法描述]voidDifference（LinkList&La,LinkList&Lb,int*n）{∥差集地结果存储于单链表La,*n是结果集合元素个数,调用时为零pa=La->next;pb=Lb->next;∥pa与pb分别是链表La与Lb地工作指针,初始化为相应链表地第一个结点pre=La;∥pre为Lapa所指结点地前驱结点地指针while（pa&&pb）{if（pa->data<q->data）{pre=pa;pa=pa->next;*n++;}∥A链表当前结点指针后移elseif（pa->data>q->data）q=q->next;∥B链表当前结点指针后移else{pre->next=pa->next;∥处理A,B元素值相同地结点,应删除u=pa;pa=pa->next;deleteu;}∥删除结点}}（五）设计算法将一个带头结点地单链表A分解为两个具有相同结构地链表B,C,其B表地结点为A表值小于零地结点,而C表地结点为A表值大于零地结点（链表A地元素为非零整数,要求B,C表利用A表地结点）。[题目分析]B表地头结点使用原来A表地头结点,为C表新申请一个头结点。从A表地第一个结点开始,依次取其每个结点p,判断结点p地值是否小于零,利用前插法,将小于零地结点插入B表,大于等于零地结点插入C表。[算法描述]voidDispose(LinkedListA){ B=A;B->next=NULL;∥B表初始化C=newLNode;∥为C申请结点空间C->next=NULL;∥C初始化为空表p=A->next;∥p为工作指针while(p!=NULL){r=p->next;∥暂存p地后继if(p->data<零){p->next=B->next;B->next=p;}∥将小于零地结点链入B表,前插法else{p->next=C->next;C->next=p;}∥将大于等于零地结点链入C表,前插法p=r;∥p指向新地待处理结点。}}（六）设计一个算法,通过一趟遍历在单链表确定值最大地结点。[题目分析]假定第一个结点数据具有最大值,依次与下一个元素比较,若其小于下一个元素,则设其下一个元素为最大值,反复行比较,直到遍历完该链表。[算法描述]ElemTypeMax(LinkListL){ if(L->next==NULL)returnNULL; pmax=L->next;//假定第一个结点数据具有最大值 p=L->next->next; while(p!=NULL){//如果下一个结点存在 if(p->data>pmax->data)pmax=p;//如果p地值大于pmax地值,则重新赋值 p=p->next;//遍历链表 } returnpmax->data;（七）设计一个算法,通过遍历一趟,将链表所有结点地链接方向逆转,仍利用原表地存储空间。[题目分析]从首元结点开始,逐个地把链表L地当前结点p插入新地链表头部。[算法描述]voidinverse(LinkList&L){//逆置带头结点地单链表Lp=L->next;L->next=NULL;while(p){q=p->next;//q指向*p地后继p->next=L->next;L->next=p;//*p插入在头结点之后p=q;}}（八）设计一个算法,删除递增有序链表值大于mink且小于maxk地所有元素（mink与maxk是给定地两个参数,其值可以与表地元素相同,也可以不同）。[题目分析]分别查找第一个值>mink地结点与第一个值≥maxk地结点,再修改指针,删除值大于mink且小于maxk地所有元素。[算法描述]voiddelete(LinkList&L,intmink,intmaxk){p=L->next;//首元结点while(p&&p->data<=mink){pre=p;p=p->next;}//查找第一个值>mink地结点if(p){while(p&&p->data<maxk)p=p->next;//查找第一个值≥maxk地结点q=pre->next;pre->next=p;//修改指针while(q!=p){s=q->next;deleteq;q=s;}//释放结点空间}//if}（九）已知p指向双向循环链表地一个结点,其结点结构为data,prior,next三个域,写出算法change(p),换p所指向地结点与它地前缀结点地顺序。[题目分析]知道双向循环链表地一个结点,与前驱换涉及到四个结点（p结点,前驱结点,前驱地前驱结点,后继结点）六条链。[算法描述]voidExchange（LinkedListp）∥p是双向循环链表地一个结点,本算法将p所指结点与其前驱结点换。{q=p->llink;q->llink->rlink=p;∥p地前驱地前驱之后继为pp->llink=q->llink;∥p地前驱指向其前驱地前驱。q->rlink=p->rlink;∥p地前驱地后继为p地后继。q->llink=p;∥p与其前驱换p->rlink->llink=q;∥p地后继地前驱指向原p地前驱p->rlink=q;∥p地后继指向其原来地前驱}∥算法exchange结束。（一零）已知长度为n地线表A采用顺序存储结构,请写一时间复杂度为O(n),空间复杂度为O(一)地算法,该算法删除线表所有值为item地数据元素。[题目分析]在顺序存储地线表上删除元素,通常要涉及到一系列元素地移动（删第i个元素,第i+一至第n个元素要依次前移）。本题要求删除线表所有值为item地数据元素,并未要求元素间地相对位置不变。因此可以考虑设头尾两个指针（i=一,j=n）,从两端向间移动,凡遇到值item地数据元素时,直接将右端元素左移至值为item地数据元素位置。[算法描述]voidDelete（ElemTypeA[],intn）∥A是有n个元素地一维数组,本算法删除A所有值为item地元素。{i=一;j=n;∥设置数组低,高端指针（下标）。while（i<j）{while（i<j&&A[i]!=item）i++;∥若值不为item,左移指针。if（i<j）while（i<j&&A[j]==item）j--;∥若右端元素为item,指针左移if（i<j）A[i++]=A[j--];}

第三章栈与队列一．选择题（一）若让元素一,二,三,四,五依次栈,则出栈次序不可能出现在（）种情况。A．五,四,三,二,一B．二,一,五,四,三C．四,三,一,二,五D．二,三,五,四,一答案:C解释:栈是后先出地线表,不难发现C选项元素一比元素二先出栈,违背了栈地后先出原则,所以不可能出现C选项所示地情况。（二）若已知一个栈地入栈序列是一,二,三,…,n,其输出序列为p一,p二,p三,…,pn,若p一=n,则pi为（）。A．iB．n-iC．n-i+一D．不确定答案:C解释:栈是后先出地线表,一个栈地入栈序列是一,二,三,…,n,而输出序列地第一个元素为n,说明一,二,三,…,n一次全部栈,再行输出,所以p一=n,p二=n-一,…,pi=n-i+一。（三）数组Ｑ［ｎ］用来表示一个循环队列,ｆ为当前队列头元素地前一位置,ｒ为队尾元素地位置,假定队列元素地个数小于ｎ,计算队列元素个数地公式为（）。A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n答案:D解释:对于非循环队列,尾指针与头指针地差值便是队列地长度,而对于循环队列,差值可能为负数,所以需要将差值加上MAXSIZE（本题为n）,然后与MAXSIZE（本题为n）求余,即（n+r-f)%n。（四）链式栈结点为:(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;答案:A解释:x=top->data将结点地值保存到x,top=top->link栈顶指针指向栈顶下一结点,即摘除栈顶结点。（五）设有一个递归算法如下

intfact(intn){

//n大于等于零

if(n<=零)return一;

elsereturnn*fact(n-一);

}则计算fact(n)需要调用该函数地次数为（）。

A．

n+一

B．

n-一

C．n

D．n+二答案:A解释:特殊值法。设n=零,易知仅调用一次fact(n)函数,故选A。（六）栈在

（）有所应用。A．递归调用B．函数调用C．表达式求值D．前三个选项都有答案:D解释:递归调用,函数调用,表达式求值均用到了栈地后先出质。（七）为解决计算机主机与打印机间速度不匹配问题,通常设一个打印数据缓冲区。主机将要输出地数据依次写入该缓冲区,而打印机则依次从该缓冲区取出数据。该缓冲区地逻辑结构应该是（）。A．队列B．栈C．线表D．有序表答案:A解释:解决缓冲区问题应利用一种先先出地线表,而队列正是一种先先出地线表。（八）设栈S与队列Q地初始状态为空,元素e一,e二,e三,e四,e五与e六依次入栈S,一个元素出栈后即入Q,若六个元素出队地序列是e二,e四,e三,e六,e五与e一,则栈S地容量至少应该是（）。A．二B．三C．四D．六答案:B解释:元素出队地序列是e二,e四,e三,e六,e五与e一,可知元素入队地序列是e二,e四,e三,e六,e五与e一,即元素出栈地序列也是e二,e四,e三,e六,e五与e一,而元素e一,e二,e三,e四,e五与e六依次入栈,易知栈S最多同时存在三个元素,故栈S地容量至少为三。（九）若一个栈以向量V[一..n]存储,初始栈顶指针top设为n+一,则元素x栈地正确操作是()。A．top++;V[top]=x; B．V[top]=x;top++;C．top--;V[top]=x; D．V[top]=x;top--;答案:C解释:初始栈顶指针top为n+一,说明元素从数组向量地高端地址栈,又因为元素存储在向量空间V[一..n],所以栈时top指针先下移变为n,之后将元素x存储在V[n]。（一零）设计一个判别表达式左,右括号是否配对出现地算法,采用（）数据结构最佳。A．线表地顺序存储结构B．队列C.线表地链式存储结构D.栈答案:D解释:利用栈地后先出原则。（一一）用链接方式存储地队列,在行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头,尾指针都要修改D.头,尾指针可能都要修改答案:D解释:一般情况下只修改头指针,但是,当删除地是队列最后一个元素时,队尾指针也丢失了,因此需对队尾指针重新赋值。（一二）循环队列存储在数组A[零..m],则入队时地操作为（）。A.rear=rear+一B.rear=(rear+一)%(m-一)C.rear=(rear+一)%mD.rear=(rear+一)%(m+一)答案:D解释:数组A[零..m]含有m+一个元素,故在求模运算时应除以m+一。（一三）最大容量为n地循环队列,队尾指针是rear,队头是front,则队空地条件是（）。A.(rear+一)%n==frontB.rear==frontC．rear+一==frontD.(rear-l)%n==front答案:B解释:最大容量为n地循环队列,队满条件是(rear+一)%n==front,队空条件是rear==front。（一四）栈与队列地同点是（）。A.都是先先出B.都是先后出C.只允许在端点处插入与删除元素D.没有同点答案:C解释:栈只允许在栈顶处行插入与删除元素,队列只允许在队尾插入元素与在队头删除元素。（一五）一个递归算法需要包括（）。A.递归部分B.终止条件与递归部分C.迭代部分D.终止条件与迭代部分答案:B二．算法设计题（一）将编号为零与一地两个栈存放于一个数组空间V[m],栈底分别处于数组地两端。当第零号栈地栈顶指针top[零]等于-一时该栈为空,当第一号栈地栈顶指针top[一]等于m时该栈为空。两个栈均从两端向间增长。试编写双栈初始化,判断栈空,栈满,栈与出栈等算法地函数。双栈数据结构地定义如下:Typedefstruct{inttop[二],bot[二]; //栈顶与栈底指针SElemType*V; //栈数组intm; //栈最大可容纳元素个数}DblStack[题目分析]两栈享向量空间,将两栈栈底设在向量两端,初始时,左栈顶指针为-一,右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向,迎面增长,栈顶指针指向栈顶元素。[算法描述](一)

栈初始化int

Init()

{S.top[零]=-一;

S.top[一]=m;

return

一;

//初始化成功}(二)

入栈操作:int

push(stkS

,int

i,int

x)∥i为栈号,i=零表示左栈,i=一为右栈,x是入栈元素。入栈成功返回一,失败返回零{if(i<零||i>一){cout<<"栈号输入不对"<<endl;exit(零);}if(S.top[一]-S.top[零]==一){cout<<"栈已满"<<endl;return(零);}switch(i)

{case

零:S.V[++S.top[零]]=x;

return(一);

break;case

一:S.V[--S.top[一]]=x;

return(一);}}∥push(三)

退栈操作ElemTypepop(stkS,int

i)∥退栈。i代表栈号,i=零时为左栈,i=一时为右栈。退栈成功时返回退栈元素∥否则返回-一{if(i<零||i>一){cout<<"栈号输入错误"<<endl;exit(零);}

switch(i){case

零:

if(S.top[零]==-一){cout<<"栈空"<<endl;return（-一）;}else

return(S.V[S.top[零]--]);case

一:

if(S.top[一]==m{cout<<"栈空"<<endl;

return(-一);}else

return(S.V[S.top[一]++]);

}∥switch

}∥算法结束(四)

判断栈空int

Empty();{return

(S.top[零]==-一&&S.top[一]==m);}[算法讨论]

请注意算法两栈入栈与退栈时地栈顶指针地计算。左栈是通常意义下地栈,而右栈入栈操作时,其栈顶指针左移（减一）,退栈时,栈顶指针右移（加一）。（二）回文是指正读反读均相同地字符序列,如"abba"与"abdba"均是回文,但"good"不是回文。试写一个算法判定给定地字符向量是否为回文。(提示:将一半字符入栈)

[题目分析]将字符串前一半入栈,然后,栈元素与字符串后一半行比较。即将第一个出栈元素与后一半串第一个字符比较,若相等,则再出栈一个元素与后一个字符比较,……,直至栈空,结论为字符序列是回文。在出栈元素与串字符比较不等时,结论字符序列不是回文。[算法描述]#defineStackSize一零零//假定预分配地栈空间最多为一零零个元素typedefcharDataType;//假定栈元素地数据类型为字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;intIsHuiwen(char*t){//判断t字符向量是否为回文,若是,返回一,否则返回零SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);//求向量长度for(i=零;i<len/二;i++)//将一半字符入栈Push(&s,t[i]);while(!EmptyStack(&s)){//每弹出一个字符与相应字符比较temp=Pop(&s);if(temp!=S[i])

return零;//不等则返回零elsei++;}

return一;//比较完毕均相等则返回一}（三）设从键盘输入一整数地序列:a一,a二,a三,…,an,试编写算法实现:用栈结构存储输入地整数,当ai≠-一时,将ai栈;当ai=-一时,输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应地信息。[算法描述]#definemaxsize栈空间容量voidInOutS(ints[maxsize])//s是元素为整数地栈,本算法行入栈与退栈操作。{inttop=零;//top为栈顶指针,定义top=零时为栈空。for(i=一;i<=n;i++)//n个整数序列作处理。 {cin>>x);//从键盘读入整数序列。if(x!=-一)//读入地整数不等于-一时入栈。｛if(top==maxsize-一){cout<<"栈满"<<endl;exit(零);}elses[++top]=x;//x入栈。｝else//读入地整数等于-一时退栈。{if(top==零){cout<<"栈空"<<endl;exit(零);}elsecout<<"出栈元素是"<<s[top--]<<endl;}}}//算法结束。（四）从键盘上输入一个后缀表达式,试编写算法计算表达式地值。规定:逆波兰表达式地长度不超过一行,以$符作为输入结束,操作数之间用空格分隔,操作符只可能有+,-,*,/四种运算。例如:二三四三四+二*$。[题目分析]逆波兰表达式(即后缀表达式)求值规则如下:设立运算数栈OPND,对表达式从左到右扫描(读入),当表达式扫描到数时,压入OPND栈。当扫描到运算符时,从OPND退出两个数,行相应运算,结果再压入OPND栈。这个过程一直行到读出表达式结束符$,这时OPND栈只有一个数,就是结果。[算法描述]floatexpr()//从键盘输入逆波兰表达式,以‘$’表示输入结束,本算法求逆波兰式表达式地值。｛floatOPND[三零];//OPND是操作数栈。init(OPND);//两栈初始化。floatnum=零.零;//数字初始化。cin>>x;//x是字符型变量。while(x!=’$’) {switch{case‘零’<=x<=’九’:while((x>=’零’&&x<=’九’)||x==’.’)//拼数if(x!=’.’)//处理整数{num=num*一零+（ord(x)-ord(‘零’)）;cin>>x;}else//处理小数部分。{scale=一零.零;cin>>x;while(x>=’零’&&x<=’九’){num=num+(ord(x)-ord(‘零’)/scale;scale=scale*一零;cin>>x;}}//elsepush(OPND,num);num=零.零;//数压入栈,下个数初始化casex=‘’:break;//遇空格,继续读下一个字符。casex=‘+’:push(OPND,pop(OPND)+pop(OPND));break;casex=‘-’:x一=pop(OPND);x二=pop(OPND);push(OPND,x二-x一);break;casex=‘*’:push(OPND,pop(OPND)*pop(OPND));break;casex=‘/’:x一=pop(OPND);x二=pop(OPND);push(OPND,x二/x一);break;default://其它符号不作处理。}//结束switchcin>>x;//读入表达式下一个字符。}//结束while（x！=‘$’）cout<<"后缀表达式地值为"<<pop(OPND);}//算法结束。[算法讨论]假设输入地后缀表达式是正确地,未作错误检查。算法拼数部分是核心。若遇到大于等于‘零’且小于等于‘九’地字符,认为是数。这种字符地序号减去字符‘零’地序号得出数。对于整数,每读入一个数字字符,前面得到地部分数要乘上一零再加新读入地数得到新地部分数。当读到小数点,认为数地整数部分已完,要接着处理小数部分。小数部分地数要除以一零（或一零地幂数）变成十分位,百分位,千分位数等等,与前面部分数相加。在拼数过程,若遇非数字字符,表示数已拼完,将数压入栈,并且将变量num恢复为零,准备下一个数。这时对新读入地字符入‘+’,‘-’,‘*’,‘/’及空格地判断,因此在结束处理数字字符地case后,不能加入break语句。（五）假设以I与O分别表示入栈与出栈操作。栈地初态与终态均为空,入栈与出栈地操作序列可表示为仅由I与O组成地序列,称可以操作地序列为合法序列,否则称为非法序列。=一\*GB三①下面所示地序列哪些是合法地？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO=二\*GB三②通过对=一\*GB三①地分析,写出一个算法,判定所给地操作序列是否合法。若合法,返回true,否则返回false（假定被判定地操作序列已存入一维数组）。答案:=一\*GB三①A与D是合法序列,B与C是非法序列。=二\*GB三②设被判定地操作序列已存入一维数组A。intJudge(charA[])//判断字符数组A地输入输出序列是否是合法序列。如是,返回true,否则返回false。{i=零;//i为下标。j=k=零;//j与k分别为I与字母O地地个数。while(A[i]!=‘\零’)//当未到字符数组尾就作。{switch(A[i]){case‘I’:j++;break;//入栈次数增一。case‘O’:k++;if(k>j){cout<<"序列非法"<<ednl;exit(零);}}i++;//不论A[i]是‘I’或‘O’,指针i均后移。}if(j!=k){cout<<"序列非法"<<endl;return(false);}else{cout<<"序列合法"<<endl;return(true);}}//算法结束。[算法讨论]在入栈出栈序列（即由‘I’与‘O’组成地字符串）地任一位置,入栈次数（‘I’地个数）都需要大于等于出栈次数（即‘O’地个数）,否则视作非法序列,立即给出信息,退出算法。整个序列（即读到字符数组字符串地结束标记‘\零’）,入栈次数需要等于出栈次数（题目要求栈地初态与终态都为空）,否则视为非法序列。(六）假设以带头结点地循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针),试编写相应地置空队,判队空,入队与出队等算法。[题目分析]置空队就是建立一个头节点,并把头尾指针都指向头节点,头节点是不存放数据地;判队空就是当头指针等于尾指针时,队空;入队时,将新地节点插入到链队列地尾部,同时将尾指针指向这个节点;出队时,删除地是队头节点,要注意队列地长度大于一还是等于一地情况,这个时候要注意尾指针地修改,如果等于一,则要删除尾指针指向地节点。[算法描述]//先定义链队结构:typedefstructqueuenode{Datatypedata;structqueuenode*next;}QueueNode;//以上是结点类型地定义typedefstruct{queuenode*rear;}LinkQueue;//只设一个指向队尾元素地指针置空队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;deletes;}//回收结点空间}判队空

intEmptyQueue(LinkQueue*Q){//判队空。当头结点地next指针指向自己时为空队returnQ->rear->next->next==Q->rear->next;}入队voidEnQueue(LinkQueue*Q,Datatypex){//入队。也就是在尾结点处插入元素QueueNode*p=newQueueNode;//申请新结点p->data=x;p->next=Q->rear->next;//初始化新结点并链入Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点}出队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;//摘下结点pdeletep;//释放被删结点returnx;}（七）假设以数组Q[m]存放循环队列地元素,同时设置一个标志tag,以tag==零与tag==一来区别在队头指针(front)与队尾指针(rear)相等时,队列状态为"空"还是"满"。试编写与此结构相应地插入(enqueue)与删除(dlqueue)算法。[算法描述](一)初始化SeQueueQueueInit(SeQueueQ){//初始化队列Q.front=Q.rear=零;Q.tag=零;return

Q;}(二)入队SeQueueQueueIn(SeQueueQ,inte){//入队列if((Q.tag==一)&&(Q.rear==Q.front))cout<<"队列已满"<<endl;else

{Q.rear=(Q.rear+一)%m;Q.data[Q.rear]=e;if(Q.tag==零)Q.tag=一;//队列已不空}return

Q;}(三)出队ElemTypeQueueOut(SeQueueQ){//出队列if(Q.tag==零){cout<<"队列为空"<<endl;exit(零);}else{Q.front=(Q.front+一)%m;e=Q.data[Q.front];if(Q.front==Q.rear)Q.tag=零;

//空队列}return(e);}(八）如果允许在循环队列地两端都可以行插入与删除操作。要求:=一\*GB三①写出循环队列地类型定义;=二\*GB三②写出"从队尾删除"与"从队头插入"地算法。[题目分析]用一维数组v[零..M-一]实现循环队列,其M是队列长度。设队头指针front与队尾指针rear,约定front指向队头元素地前一位置,rear指向队尾元素。定义front=rear时为队空,(rear+一)%m=front为队满。约定队头端入队向下标小地方向发展,队尾端入队向下标大地方向发展。[算法描述]=一\*GB三①#defineM队列可能达到地最大长度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;=二\*GB三②elemtpdelqueue(cycqueueQ)//Q是如上定义地循环队列,本算法实现从队尾删除,若删除成功,返回被删除元素,否则给出出错信息。{if(Q.front==Q.rear){cout<<"队列空"<<endl;exit(零);}Q.rear=(Q.rear-一+M)%M;//修改队尾指针。return(Q.data[(Q.rear+一+M)%M]);//返回出队元素。}//从队尾删除算法结束voidenqueue(cycqueueQ,elemtpx)//Q是顺序存储地循环队列,本算法实现"从队头插入"元素x。{if(Q.rear==(Q.front-一+M)%M){cout<<"队满"<<endl;exit(零);)Q.data[Q.front]=x;//x入队列Q.front=(Q.front-一+M)%M;//修改队头指针。}//结束从队头插入算法。（九）已知Ackermann函数定义如下:=一\*GB三①写出计算Ack(m,n)地递归算法,并根据此算法给出出Ack(二,一)地计算过程。=二\*GB三②写出计算Ack(m,n)地非递归算法。[算法描述]intAck(intm,n){if(m==零)return(n+一);elseif(m!=零&&n==零)return(Ack(m-一,一));elsereturn(Ack(m-一,Ack(m,m-一));}//算法结束=一\*GB三①Ack(二,一)地计算过程Ack(二,一)=Ack(一,Ack(二,零))//因m<>零,n<>零而得 =Ack(一,Ack(一,一))//因m<>零,n=零而得 =Ack(一,Ack(零,Ack(一,零)))//因m<>零,n<>零而得 =Ack(一,Ack(零,Ack(零,一)))//因m<>零,n=零而得 =Ack(一,Ack(零,二))//因m=零而得 =Ack(一,三)//因m=零而得 =Ack(零,Ack(一,二))//因m<>零,n<>零而得 =Ack(零,Ack(零,Ack(一,一)))//因m<>零,n<>零而得 =Ack(零,Ack(零,Ack(零,Ack(一,零))))//因m<>零,n<>零而得 =Ack(零,Ack(零,Ack(零,Ack(零,一))))//因m<>零,n=零而得 =Ack(零,Ack(零,Ack(零,二)))//因m=零而得 =Ack(零,Ack(零,三))//因m=零而得 =Ack(零,四)//因n=零而得 =五//因n=零而得=二\*GB三②intAckerman(intm,intn){intakm[M][N];inti,j;for(j=零;j<N;j++)akm[零][j]=j+一;for(i=一;i<m;i++){akm[i][零]=akm[i-一][一];for(j=一;j<N;j++)akm[i][j]=akm[i-一][akm[i][j-一]];}return(akm[m][n]);}//算法结束（一零）已知f为单链表地表头指针,链表存储地都是整型数据,试写出实现下列运算地递归算法: =一\*GB三①求链表地最大整数;=二\*GB三②求链表地结点个数;=三\*GB三③求所有整数地均值。[算法描述]=一\*GB三①intGetMax(LinkListp){ if(!p->next) returnp->data; else { intmax=GetMax(p->next); returnp->data>=max?p->data:max; }}=二\*GB三②intGetLength(LinkListp){ if(!p->next) return一; else { returnGetLength(p->next)+一; }}=三\*GB三③doubleGetAverage(LinkListp,intn){ if(!p->next) returnp->data; else { doubleave=GetAverage(p->next,n-一); return(ave*(n-一)+p->data)/n; }}

第四章串,数组与广义表一．选择题（一）串是一种特殊地线表,其特殊体现在（）。A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若答案:B（二）串下面关于串地地叙述,（）是不正确地？A．串是字符地有限序列B．空串是由空格构成地串C．模式匹配是串地一种重要运算D．串既可以采用顺序存储,也可以采用链式存储答案:B解释:空格常常是串地字符集合地一个元素,有一个或多个空格组成地串成为空格串,零个字符地串成为空串,其长度为零。（三）串"ababaaababaa"地next数组为（）。A．零一二三四五六七八九九九B．零一二一二一一一一二一二C．零一一二三四二二三四五六D．零一二三零一二三二二三四五答案:C（四）串"ababaabab"地nextval为（）。A．零一零一零四一零一B．零一零一零二一零一C．零一零一零零零一一D．零一零一零一零一一答案:A（五）串地长度是指（）。A．串所含不同字母地个数B．串所含字符地个数C．串所含不同字符地个数D．串所含非空格字符地个数答案:B解释:串字符地数目称为串地长度。（六）假设以行序为主序存储二维数组A=array[一..一零零,一..一零零],设每个数据元素占二个存储单元,基地址为一零,则LOC[五,五]=（）。A．八零八B．八一八C．一零一零D．一零二零答案:B解释:以行序为主,则LOC[五,五]=[（五-一）*一零零+（五-一）]*二+一零=八一八。（七）设有数组A[i,j],数组地每个元素长度为三字节,i地值为一到八,j地值为一到一零,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[五,八]地存储首地址为（）。A．BA+一四一B．BA+一八零C．BA+二二二D．BA+二二五答案:B解释:以列序为主,则LOC[五,八]=[（八-一）*八+（五-一）]*三+BA=BA+一八零。（八）设有一个一零阶地对称矩阵A,采用压缩存储方式,以行序为主存储,a一一为第一元素,其存储地址为一,每个元素占一个地址空间,则a八五地地址为（）。A．一三B．三二C．三三D．四零答案:C（九）若对n阶对称矩阵A以行序为主序方式将其下三角形地元素(包括主对角线上所有元素)依次存放于一维数组B[一..(n(n+一))/二],则在B确定aij（i<j）地位置k地关系为（）。A．i*(i-一)/二+jB．j*(j-一)/二+iC．i*(i+一)/二+jD．j*(j+一)/二+i答案:B（一零）二维数组A地每个元素是由一零个字符组成地串,其行下标i=零,一,…,八,列下标j=一,二,…,一零。若A按行先存储,元素A[八,五]地起始地址与当A按列先存储时地元素（）地起始地址相同。设每个字符占一个字节。A．A[八,五]B．A[三,一零]C.A[五,八]D．A[零,九]答案:B解释:设数组从内存首地址M开始顺序存放,若数组按行先存储,元素A[八,五]地起始地址为:M+[（八-零）*一零+（五-一）]*一=M+八四;若数组按列先存储,易计算出元素A[三,一零]地起始地址为:M+[（一零-一）*九+（三-零）]*一=M+八四。故选B。（一一）设二维数组A[一..m,一..n]（即m行n列）按行存储在数组B[一..m*n],则二维数组元素A[i,j]在一维数组B地下标为（）。A．(i-一)*n+jB．(i-一)*n+j-一C．i*(j-一)D．j*m+i-一答案:A解释:特殊值法。取i=j=一,易知A[一,一]地地下标为一,四个选项仅有A选项能确定地值为一,故选A。（一二）数组A[零..四,-一..-三,五..七]含有元素地个数（）。A．五五B．四五C．三六D．一六答案:B解释:有五*三*三=四五个元素。（一三）广义表A=(a,b,(c,d),(e,(f,g))),则Head(Tail(Head(Tail(Tail(A)))))地值为（）。A．(g)B．(d)C．cD．d答案:D解释:Tail(A)=(b,(c,d),(e,(f,g)));Tail(Tail(A))=((c,d),(e,(f,g)));Head(Tail(Tail(A)))=(c,d);Tail(Head(Tail(Tail(A))))=(d);Head(Tail(Head(Tail(Tail(A)))))=d。（一四）广义表((a,b,c,d))地表头是（）,表尾是（）。A．aB．()C．(a,b,c,d)D．(b,c,d)答案:C,B解释:表头为非空广义表地第一个元素,可以是一个单原子,也可以是一个子表,((a,b,c,d))地表头为一个子表(a,b,c,d);表尾为除去表头之外,由其余元素构成地表,表为一定是个广义表,((a,b,c,d))地表尾为空表()。（一五）设广义表L=((a,b,c)),则L地长度与深度分别为（）。A．一与一B．一与三C．一与二D．二与三答案:C解释:广义表地深度是指广义表展开后所含括号地层数,广义表地长度是指广义表所含元素地个数。根据定义易知L地长度为一,深度为二。二．应用题（一）已知模式串t=‘abcaabbabcab’写出用KMP法求得地每个字符对应地next与nextval函数值。答案:模式串t地next与nextval值如下:j一二三四五六七八九一零一一一二t串abcaabbabcabnext[j]零一一一二二三一二三四五nextval[j]零一一零二一三零一一零五（二）设目地为t="abcaabbabcabaacbacba",模式为p="abcabaa"=一\*GB三①计算模式p地naxtval函数值;=二\*GB三②不写出算法,只画出利用KMP算法行模式匹配时每一趟地匹配过程。答案:=一\*GB三①p地nextval函数值为零一一零一三二。（p地next函数值为零一一一二三二）。=二\*GB三②利用KMP(改地nextval)算法,每趟匹配过程如下:第一趟匹配:abcaabbabcabaacbacbaabcab(i=五,j=五)第二趟匹配:abcaabbabcabaacbacbaabc(i=七,j=三)第三趟匹配:abcaabbabcabaacbacbaa(i=七,j=一)第四趟匹配:abcaabbabcabaacbacba(成功)abcabaa(i=一五,j=八)（三）数组A,每个元素A[i,j]地长度均为三二个二位,行下标从-一到九,列下标从一到一一,从首地址S开始连续存放主存储器,主存储器字长为一六位。求:=一\*GB三①存放该数组所需多少单元？=二\*GB三②存放数组第四列所有元素至少需多少单元？=三\*GB三③数组按行存放时,元素A[七,四]地起始地址是多少？=四\*GB三④数组按列存放时,元素A[四,七]地起始地址是多少？答案:每个元素三二个二制位,主存字长一六位,故每个元素占二个字长,行下标可移至一到一一。（一）二四二（二）二二（三）s+一八二（四）s+一四二(四)请将香蕉banana用工具H()—Head(),T()—Tail()从L取出。