数据结构与算法习题及答案.doc

第章绪论习题1简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2.试举一个数据结构得例子,叙述其逻辑结构与存储结构两方面得含义与相互关系。3。简述逻辑结构得四种基本关系并画出它们得关系图.4。存储结构由哪两种基本得存储方法实现?5。选择题（1)在数据结构中，从逻辑上可以把数据结构分成( ）。A.动态结构与静态结构 B紧凑结构与非紧凑结构C线性结构与非线性结构 D。内部结构与外部结构(2)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得( ).A存储结构 。存储实现C.逻辑结构 D.运算实现（3）通常要求同一逻辑结构中得所有数据元素具有相同得特性,这意味着（ ）. A。数据具有同一特点B。不仅数据元素所包含得数据项得个数要相同,而且对应数据项得类型要一致.每个数据元素都一样D数据元素所包含得数据项得个数要相等(4）以下说法正确得就是（ ）.A.数据元素就是数据得最小单位B.数据项就是数据得基本单位数据结构就是带有结构得各数据项得集合D。一些表面上很不相同得数据可以有相同得逻辑结构（5)以下与数据得存储结构无关得术语就是( ）.A。顺序队列 B、 链表 C、 有序表 D、 链栈(6）以下数据结构中,（ ）就是非线性数据结构A。树 。字符串 C。队 .栈6试分析下面各程序段得时间复杂度。（1）=90; y=10； whie（y0)(100）=0；y；else x+;(2)for （i=； in;i+)f （=0; m； +）aij=0;()=0; ri0; n； i+)for（j=; j； +） s+ij;su=s；（4）=; hil（i<=n） =i*；（5）x=0；fr（i=1； i<+) or (j=1； n-； j+)x;(6)xn；/n>1=0;whl（x(y） (+1)） y+；()（1）（2）O（m*n)()O（n2)(）O（log3)(5）因为x+共执行了n1+n2+1= n（n-1)/2，所以执行时间为O(n2）（6)O(）第2章 线性表.选择题（1）一个向量第一个元素得存储地址就是10，每个元素得长度为2，则第5个元素得地址就是( )。A.110 1 C100 D。20(2）在个结点得顺序表中，算法得时间复杂度就是(1)得操作就是( ）。.访问第i个结点(1in)与求第i个结点得直接前驱（2in）B。在第个结点后插入一个新结点(1n)C.删除第i个结点(1in）D将n个结点从小到大排序（) 向一个有7个元素得顺序表中插入一个新元素并保持原来顺序不变，平均要移动 得元素个数为（ ）。A.8 。63。5 C.63 D。（4)链接存储得存储结构所占存储空间( ）。分两部分，一部分存放结点值,另一部分存放表示结点间关系得指针B.只有一部分，存放结点值C.只有一部分,存储表示结点间关系得指针D。分两部分，一部分存放结点值，另一部分存放结点所占单元数(5)线性表若采用链式存储结构时，要求内存中可用存储单元得地址（ ）.A.必须就是连续得 部分地址必须就是连续得。一定就是不连续得 D。连续或不连续都可以(6)线性表L在（ )情况下适用于使用链式结构实现。A.需经常修改L中得结点值 需不断对进行删除插入 C。L中含有大量得结点 DL中结点结构复杂（7)单链表得存储密度( )。A大于1 B.等于1 .小于1 不能确定（8）将两个各有个元素得有序表归并成一个有序表，其最少得比较次数就是( ）。A。 B。2-1 C。2 D。n1（9）在一个长度为得顺序表中，在第i个元素（in+1）之前插入一个新元素时须向后移动（ )个元素。A。n-i B.ni+ Ci1 D。i（1） 线性表=（a1,a2,a）,下列说法正确得就是( ）。每个元素都有一个直接前驱与一个直接后继B。线性表中至少有一个元素C表中诸元素得排列必须就是由小到大或由大到小D。除第一个与最后一个元素外，其余每个元素都有一个且仅有一个直接前驱与直接后继。(1) 若指定有个元素得向量，则建立一个有序单链表得时间复杂性得量级就是( )。A.(1) B.O(n） C。（n2) D.O（nlog2n)(12) 以下说法错误得就是（ ）。A.求表长、定位这两种运算在采用顺序存储结构时实现得效率不比采用链式存储结构时实现得效率低B。顺序存储得线性表可以随机存取C。由于顺序存储要求连续得存储区域,所以在存储管理上不够灵活D线性表得链式存储结构优于顺序存储结构（13) 在单链表中，要将s所指结点插入到p所指结点之后,其语句应为( ）。A.s>e=p+; pnext=s;B。（p）、net=s; （s)、next（*p）、et;C.snetp>ne;p>next=s>next;Ds>nx-next； p->next=s； (14）在双向链表存储结构中，删除p所指得结点时须修改指针( )。A。p>net-prior=p-prior;p-rornxt>next；Bpnet=p>nextnext; pexpri=p;C.prornextp; pprior=pripio;D。pprirp-next->nx； pnext=p>proprir；（15）在双向循环链表中,在p指针所指得结点后插入所指向得新结点,其修改指针得操作就是( ）.p-next=q; q>priorp； p-nt>pri=q; q>nex=；B。->nxt=; next-rir=q； qpio=p； q-ext=p-next;C。qprior=p；q>et=p->next； p->next-pror=q； -nex=;D。q-prior=p; qxt=pex； p-ex=； p->netpror；2算法设计题（1）将两个递增得有序链表合并为一个递增得有序链表。要求结果链表仍使用原来两个链表得存储空间, 不另外占用其它得存储空间.表中不允许有重复得数据。vid MergeLit_L（LkLit &La,LiLis L，Lint &Lc) pa=Lant; pbbext； Lc=pc=La； /用La得头结点作为Lc得头结点 while（p p） f(a->atab-data) pc>extpa;pc=pa；paext; lse i(pa->dtapb-ata） pcnetpb；=b； pb=bnxt； else 相等时取La得元素,删除L得元素 pc->net=p;pc=;pa=panex； =p>next；eete pb ;p q; pc-e=p？pa：pb; /插入剩余段 dltLb； /释放Lb得头结点 （2）将两个非递减得有序链表合并为一个非递增得有序链表。要求结果链表仍使用原来两个链表得存储空间, 不另外占用其它得存储空间。表中允许有重复得数据。voiunion（LinkLis La， LinkList b， Linkist Lc， ） pa =La->next；pb=bnext； /初始化Lca; /用a得头结点作为c得头结点 c>next L； while( pa p ) if (!pa ） q = pb; b -ext; el if ( !pb ） q = pa； pa pa-net； else if (pa->dta pdat ) =p; pa = pa>nt; else q = pb； pb =pb-ex； q>ext Lcnext； Lc>next= ; / 插入 eeb; /释放Lb得头结点 (）已知两个链表A与B分别表示两个集合，其元素递增排列。请设计算法求出A与B得交集,并存放于A链表中.voi Mix(inLisL，Likist& Lb， LikLi Lc,)pa=laext；pb=lbnext；设工作指针a与pb；Lc=pc=L； /用L得头结点作为Lc得头结点whi(ppb) if（pa-dta=pb>data）交集并入结果表中. pcet=pa;pcpa；pa=pa>next； =p；b=pbnext； deete ;ee if（a->dapb-） u=a;p=pa->n；delte u;s u=pb； pb=pb>et; delete u；wil（pa） u=pa; panex； eleteu; 释放结点空间while(b）up; b=bnxt； deltu;释放结点空间pc>extul;置链表尾标记。delet b； 注：本算法中也可对B表不作释放空间得处理（4）已知两个链表A与B分别表示两个集合,其元素递增排列。请设计算法求出两个集合A与B 得差集(即仅由在A中出现而不在B中出现得元素所构成得集合），并以同样得形式存储,同时返回该集合得元素个数。void Dffnce(LinkedLst ，B,*n)A与均就是带头结点得递增有序得单链表，分别存储了一个集合，本算法求两集合得差集,存储于单链表A中，n就是结果集合中元素个数，调用时为0=A>next； p与q分别就是链表A与B得工作指针。 =B->next; pr=A； p为中p所指结点得前驱结点得指针。 while(p！ul& !=null）if（p>daa<qdata)pep;p=p->next；*n+; A链表中当前结点指针后移。else if（pda>qdata）q=q-next； B链表中当前结点指针后移。se pre-netpnxt; 处理A,中元素值相同得结点,应删除。 u=；p=p->next； lte u； 删除结点(5)设计算法将一个带头结点得单链表分解为两个具有相同结构得链表B、C,其中B表得结点为表中值小于零得结点，而表得结点为表中值大于零得结点(链表A得元素类型为整型，要求B、C表利用A表得结点)。（6)设计一个算法，通过一趟遍历在单链表中确定值最大得结点。ElemTy a （LinkList L ）if（L->nxt=NULL） eur NUL；pmax=>nex；/假定第一个结点中数据具有最大值p=Lext>next；wi(p !=NUL )/如果下一个结点存在if（p>d pmax>da） pmax=p；ppnxt；etunpmdta;（）设计一个算法,通过遍历一趟,将链表中所有结点得链接方向逆转，仍利用原表得存储空间。void ivere（LkLis ） /逆置带头结点得单链表 L =L>xt; L>extNUL； wile （ p） q=p-next； /q指向p得后继 p>ext=Lnx; L>next=p； /*p插入在头结点之后 p = ； （8）设计一个算法,删除递增有序链表中值大于min且小于mak得所有元素(mk与maxk就是给定得两个参数，其值可以与表中得元素相同，也可以不同 ）。void lte（nkLit L， n ink，int mak) p=Let; /首元结点 while (p && p>dta=min) pe； p=p-nxt; /查找第一个值mnk得结点 f （p） i (p pdatamx） p=pnext; / 查找第一个值 axk 得结点 q=preext； pe>net=p； /修改指针 while（q！=p） =q>next; delet q； q=s； /释放结点空间 /f（9）已知指向双向循环链表中得一个结点,其结点结构为daa、pror、next三个域，写出算法chang（p),交换p所指向得结点与它得前缀结点得顺序。知道双向循环链表中得一个结点,与前驱交换涉及到四个结点(结点，前驱结点，前驱得前驱结点，后继结点）六条链。voi Exchange(LinkList p)p就是双向循环链表中得一个结点,本算法将p所指结点与其前驱结点交换。plnk; qln-rlink=p； 得前驱得前驱之后继为p p->link=q->k; p得前驱指向其前驱得前驱。q>lin=p>lnk; p得前驱得后继为p得后继。->llkp； p与其前驱交换p->ik->llink=q； p得后继得前驱指向原p得前驱 p-rlink=q; 得后继指向其原来得前驱算法ehnge结束。(0)已知长度为得线性表A采用顺序存储结构，请写一时间复杂度为O（n）、空间复杂度为（)得算法，该算法删除线性表中所有值为item得数据元素。题目分析 在顺序存储得线性表上删除元素，通常要涉及到一系列元素得移动（删第i个元素,第i+1至第个元素要依次前移）。本题要求删除线性表中所有值为item得数据元素,并未要求元素间得相对位置不变。因此可以考虑设头尾两个指针(i=1，j=),从两端向中间移动,凡遇到值item得数据元素时,直接将右端元素左移至值为iem得数据元素位置。oid Deete（ElmTe A，in n）就是有个元素得一维数组，本算法删除中所有值为tem得元素.i1;=;设置数组低、高端指针(下标）。 whle（ij） whle(i<j Ai!=iem）i+； 若值不为ite,左移指针。 i（i<j）while(i< & A=item）-;若右端元素值为m，指针左移 i(i<）Ai=-; 算法讨论因元素只扫描一趟，算法时间复杂度为（).删除元素未使用其它辅助空间，最后线性表中得元素个数就是j。第3章 栈与队列习题1。选择题（1)若让元素1，2，3，4,5依次进栈,则出栈次序不可能出现在（ ）种情况。A.,4，3，,1 B。2，1，5,，3 C。，,1，5 D2，5,4,（2）若已知一个栈得入栈序列就是1,2,3，n，其输出序列为1，p，p3,p，若p1=n，则pi为( ). A。i B。n C。n-i+ D.不确定（)数组n用来表示一个循环队列,f为当前队列头元素得前一位置，r为队尾元素得位置，假定队列中元素得个数小于,计算队列中元素个数得公式为（ )。r-f B。(+-r)%n C.n+rf D（nrf）n（4）链式栈结点为：（data，lik)，top指向栈顶、若想摘除栈顶结点，并将删除结点得值保存到x中，则应执行操作（ )。=to>data;top=oplink; Bt=top-lin;x=tplink； .x=tp;op=tplnk； .=tp>lnk；（5）设有一个递归算法如下        int fct（intn）   /n大于等于             if（n=0) rern1;             ese return nfact（-);        则计算fact（n）需要调用该函数得次数为（ )。 A n1       B. n1      .n      D.n2（）栈在 （ ）中有所应用.A递归调用 .函数调用 C表达式求值 D.前三个选项都有（7)为解决计算机主机与打印机间速度不匹配问题,通常设一个打印数据缓冲区.主机将要输出得数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据.该缓冲区得逻辑结构应该就是（ )。A.队列 B。栈 C。 线性表 D。有序表(8）设栈S与队列Q得初始状态为空，元素e1、e2、e3、e、e5与e依次进入栈S，一个元素出栈后即进入Q，若6个元素出队得序列就是2、e4、3、e6、e5与e1,则栈S得容量至少应该就是（).A .3 C4 . 6（）在一个具有n个单元得顺序栈中，假设以地址高端作为栈底,以op作为栈顶指针，则当作进栈处理时,tp得变化为（ )。A.o不变 。op0 .top- Dto+(）设计一个判别表达式中左，右括号就是否配对出现得算法，采用（）数据结构最佳。A.线性表得顺序存储结构 B。队列 C、 线性表得链式存储结构 、 栈（11）用链接方式存储得队列，在进行删除运算时(）。A、 仅修改头指针 B、仅修改尾指针C、 头、尾指针都要修改 D、 头、尾指针可能都要修改(1）循环队列存储在数组A0、m中,则入队时得操作为(）。、 rear=ar+1 B、rear=（rar+1)（m1） C、 rer=（ar+1）m D、 re=(rear1)（+1） (13）最大容量为n得循环队列,队尾指针就是rear，队头就是font，则队空得条件就是（）. A、 (ar+1）%n=front B、 rear=frot .rear1=fr D、 （real)%n=front(4)栈与队列得共同点就是（)。A、 都就是先进先出 、 都就是先进后出 、 只允许在端点处插入与删除元素 D、 没有共同点（5)一个递归算法必须包括(）。A、递归部分 B、终止条件与递归部分C、迭代部分 、 终止条件与迭代部分(2）回文就是指正读反读均相同得字符序列，如“ab”与“aba"均就是回文，但“go”不就是回文。试写一个算法判定给定得字符向量就是否为回文。（提示:将一半字符入栈） 根据提示，算法可设计为： /以下为顺序栈得存储结构定义 define StackSiz 00/假定预分配得栈空间最多为100个元素 typef hr DataTpe；/假定栈元素得数据类型为字符typef srcDaTypedtatcSize； int top； eqStack；  int IHuiwe( har t) /判断t字符向量就是否为回文，若就是，返回1，否则返回0 SeqSack s； ti ， len； chr ep； Inttac（ &s）； lnstrlen(t）; /求向量长度 fr （ i0；ile/2; +）/将一半字符入栈 Push( s，ti）;wie（ ！EmptyStack（ )） /每弹出一个字符与相应字符比较 tempPo （s）; if（temp！Si）  retur0 ；/ 不等则返回0 ele +；   etur ； / 比较完毕均相等则返回 1 （）设从键盘输入一整数得序列：a1，a, a3，a，试编写算法实现:用栈结构存储输入得整数,当-1时，将a进栈;当ai=-1时，输出栈顶整数并出栈。算法应对异常情况(入栈满等）给出相应得信息。#defie mize 栈空间容量 id nOtS(intsmsize) /s就是元素为整数得栈,本算法进行入栈与退栈操作。 int op=0； /op为栈顶指针,定义tp=时为栈空。 for（i=1; i<=n； i） /n个整数序列作处理。 scnf(“”，&x)； /从键盘读入整数序列。 i（x！=-1） / 读入得整数不等于时入栈。 if(top=msize1）printf(“栈满n”）;ext（0）；le s+top=x; /x入栈。 ese /读入得整数等于-1时退栈。 （tp=0）pinf（“栈空n”)；exit（0）; ee pinf(“出栈元素就是%dn”,top-）； /算法结束。(4)从键盘上输入一个后缀表达式,试编写算法计算表达式得值.规定：逆波兰表达式得长度不超过一行，以符作为输入结束,操作数之间用空格分隔,操作符只可能有+、/四种运算。例如：24 4+2*。 题目分析逆波兰表达式（即后缀表达式)求值规则如下:设立运算数栈ND，对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPN栈。当扫描到运算符时,从OPN退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符，这时OND栈中只有一个数，就就是结果。 flat expr( )从键盘输入逆波兰表达式，以表示输入结束,本算法求逆波兰式表达式得值。float OPND3； / PN就是操作数栈.nt（OPND)； /两栈初始化。 float num=0、0； /数字初始化。 scanf （“%c”，&x）;/就是字符型变量。 hile(x!=$) swi cas=x<=':whe(（=0x=9'）|x=、） /拼数 if（x!=、) /处理整数m=num10(ord（x）rd(0）); sa(“c"，）； ele /处理小数部分。 scae=1、0; sanf(“%c”，&x）; hie(x>=0&x<=9) um=nu+（ord（）ord（')/cle； ca=scle*1； sanf(“%"，x); else pus（PND，m）; num=0、0；数压入栈，下个数初始化 se:brea； /遇空格,继续读下一个字符. cs x=+'：pu（OND，op（PND)pp（PND）；ek； case =:1=pop（PND）;2op(OPN)；uh(PN，x-x1）;break; case x=*'：ph（OPND，pop(OP）*o(OPN）；break； cse x/：x1=pp（OPND）；x2pop（OPND）；ush（OPND，x2/);brek; dfult： /其它符号不作处理。 /结束swich scanf（“c",&x）；/读入表达式中下一个字符。 /结束while（！=) prntf（“后缀表达式得值为f”，op(OPND)；/算法结束.算法讨论假设输入得后缀表达式就是正确得,未作错误检查。算法中拼数部分就是核心。若遇到大于等于0且小于等于'得字符,认为就是数。这种字符得序号减去字符'得序号得出数。对于整数,每读入一个数字字符，前面得到得部分数要乘上1再加新读入得数得到新得部分数.当读到小数点,认为数得整数部分已完,要接着处理小数部分.小数部分得数要除以10(或10得幂数)变成十分位，百分位,千分位数等等,与前面部分数相加。在拼数过程中,若遇非数字字符,表示数已拼完，将数压入栈中,并且将变量u恢复为0,准备下一个数。这时对新读入得字符进入、'、'及空格得判断,因此在结束处理数字字符得ae后，不能加入be语句。（)假设以I与分别表示入栈与出栈操作。栈得初态与终态均为空，入栈与出栈得操作序列可表示为仅由与组成得序列,称可以操作得序列为合法序列，否则称为非法序列。下面所示得序列中哪些就是合法得？ A、 IOIIOIO B、IOOI 、 IIOOIO D、 IIOOIOO通过对得分析,写出一个算法，判定所给得操作序列就是否合法。若合法,返回rue,否则返回alse(假定被判定得操作序列已存入一维数组中）。与D就是合法序列，B与C 就是非法序列.设被判定得操作序列已存入一维数组A中。 t Jue（carA） /判断字符数组A中得输入输出序列就是否就是合法序列。如就是,返回ue,否则返回le. i=0； /i为下标。 j=0； /j与分别为与字母O得得个数。 wil（Ai！=0') /当未到字符数组尾就作。 sith(Ai） aeI: j+; bea； /入栈次数增1。 aseO:k+； if(kj)prinf（“序列非法n”)；exit（）； i+； /不论Ai就是'或O',指针均后移。 if（j！=k) pritf（“序列非法n”）;rturn（ase); else rintf（“序列合法n”）;etu（tr）; /算法结束。 算法讨论在入栈出栈序列(即由I与组成得字符串)得任一位置，入栈次数（I得个数）都必须大于等于出栈次数（即O得个数)，否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串得结束标记0），入栈次数必须等于出栈次数（题目中要求栈得初态与终态都为空),否则视为非法序列.（6)假设以带头结点得循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针） ,试编写相应得置空队、判队空 、入队与出队等算法。 算法如下: /先定义链队结构:ydeructqueuenodDattye dta; strutqueuode ext; QueuNo; /以上就是结点类型得定义 typedf srct queuenode*ear; Linueue； /只设一个指向队尾元素得指针（1）置空队vid IntQeu( Likueue Q） /置空队：就就是使头结点成为队尾元素 QueueNod s; Q->rea Q-arnet；/将队尾指针指向头结点 he （Qrer！=>reanex)/当队列非空,将队中元素逐个出队 s=Q->rer->nex； Q>rearnxt=next； fe（)； /回收结点空间 (2）判队空  int mptueue（ LkQueue Q） /判队空 /当头结点得nx指针指向自己时为空队 retun Q->rarnextnet=Q>rar-nxt; （3)入队void EnQue（ LnQee *Q， atatpex） /入队 /也就就是在尾结点处插入元素 Queueoe p=（QueNod *） allc (szof（QeeNode）；/申请新结点 p-data；p-nex=Q-rerext；/初始化新结点并链入 Qrear>nxt=p；  Qrar=;/将尾指针移至新结点 (4)出队 DtatyeDeueue( LnkQueu Q) /出队,把头结点之后得元素摘下 Dtatype; QuueNode p； if(EmptyQueu( Q) Error（Quee underow"）； pQrernetnx； /p指向将要摘下得结点 x=pdata； 保存结点中数据if （p=-rer） /当队列中只有一个结点时,p结点出队后，要将队尾指针指向头结点 Q-rer= Q>rer