《数据结构期末习题答案1.pdf》由会员分享，可在线阅读，更多相关《数据结构期末习题答案1.pdf（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章绪论一，选择题1 .组成数据的根本单位是()A.数据项 B.数据类型 C.数据元素 D.数据变量2 .数据结构是研究数据的()以及它们之间的相互关系。A.理想结构，物理结构 B.理想结构，抽象结构C.物理结构，逻辑结构 D.抽象结构，逻辑结构3 .算法分析的两个主要方面是1 )A.正确性和简单性 B.可读性和文档性C.数据复杂性和程序复杂性 D.时间复杂度和空间复杂度4 .算法分析的目的是()。A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改良D.分析算法的易懂性和文档性5 .算法的时间复杂度取决于()A.问题的规模 B.待处理数据的初态 C.A和 B
2、D.以上都不是6.一个算法应该是()oA.程序 B.问题求解步骤的描述 C.要满足五个根本特性 D.A和 C.7 .下面关于算法说法错误的选项是()A.算法最终必须由计算机程序实现C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的8 .从逻辑上可以把数据结构分为()两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构9 .程序段 f o r(i=nT;i =l;i)f o r(j=l j A j+l )A j 与 A j+1 对换；其 中 n 为正整数，那么最后一行的语句频度在最坏情况下是()A.0(n)B.O(nlogn)C.0(
3、n3)D.0(n2)1 0 .连续存储设计时，存储单元的地址()。A.一定 连 续 B.一 定 不 连 续 C.不 一 定 连 续 D.局部连续，局部不连续二，判断题1 .数据结构的抽象操作的定义与具体实现有关。()2 .数据结构是数据对象与对象中数据元素之间关系的集合。3 .在顺序存储结构中，有时也存储数据结构中元素之间的关系。()4 .数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。5 .算法和程序原那么上没有区别，在讨论数据结构是两者是通用的。6.同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。7 .数据的逻辑结构与数据元素本
4、身的内容和形式无关。8 .算法的优劣与算法描述语言无关，但与所用计算机有关。()9.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()10.算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，那么算法实际上就是程序了。()一，选择题1.C2.C3.D4.C5.C6.B7.D8.C9.D10.A二，判断题1.X2.V3.X4.J5.X6.X7.J8.X9.10.X三，填空1.数据的物理结构包括 的表示和 的表示。2.对于给定的n 个元素，可 以 构 造 出 的 逻 辑 结 构 有,四种。3.一个数据结构在计算机中 称为存储结构。4.抽 象 数 据 类 型 的 定 义
5、 仅 取 决 于 它 的 一 组,而与 无关，即不管其内部结构如何变化，只要它的 不变，都不影响其外部使用。5.线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。6.一个算法有5 个特性:、,有零个或多个输入、有一个或多个输出。7.如下程序段for(i=n；i=l;i+)语句 1(x:=x+l；语句2 for(j=n;j=i;j+)语句 3y:=y+l;语句 4)语 句 1 执 行 的 频 度 为；语句2 执 行 的 频 度 为；语 句 3 执行的频度为；语句4 执 行 的 频 度 为。8.在下面的程序段中，对 x 的 赋 值 语 句 的 频 度 为 (
6、表示为n 的函数)for(i=l;i=n;i+)fo r(j=1;j=i;j+)for(k=l;k=j;j+)x x+d e lta；9.计算机执行下面的语句时，语句s 的执行次数为。fo r(i=l；i=i;j)s;10.下面程序段的时间复杂度为 _o(nl)sum=l；for(i=0;sumn;i+)sum+=l;三，填空题1.数据元素数据元素间关系2.集 合 线 性 结 构 树 形 结 构 图 状 结 构 或 网 状 结 构3.表示(又称映像).4.逻辑特性在计算机内部如何表示和实现数学特性5.一对一6.有穷性7.n+1 n一对多 多对多确定性 可行性n(n+3)/2 n(n+l)/28
7、.1+(1+2+(1+2+3)+(l+2+-+n)=n(n+l)(n+2)/6 0(n3)9.(n+3)(n-2)/21 0.0(n)四，应用题1 .什么是数据？它与信息是什么关系？2 .什么是数据结构？数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面?3 .评价一个好的算法，从哪几方面考虑？4 .假设将数据结构定义为一个二元组(D,R)，说明符号D,R应分别表示什么？5 .解释算法与程序的区别？6 .有以下几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。(1)A=(K,R),其中：K=a,b,c,d,e,f,g R=r r=,b,c ,c,
8、d),(d,e),e,f),f,g)(2)B=(K,R),其中：K=a,b,c,d,e,f,g,h R=r r=d,b)，d,g，d,a),(b,c),g,e),g,h),a,f)(3)C=(K,R),其中：K=1,2,3,4,5,6)R=r r=(l,2),(2,3),(2,4),(3,4),3,5),3,6),(4,5),(4,6)这里的圆括号对表示两结点是双向的。7.分析以下程序段的时间复杂度。(1)a=0；b=l；f o r (i=2；i =n；i+)(s=a+b：b-a；a=S：(2)in t i,j,k；f o r (i=0；i n；i+)f o r (j=0；j n；j+c i皿
9、=0;f o r (k=0；k (n；k+c i r j =c i|j +a i k +b k j;I8.求以下算法段的语句频度及时间复杂度(1)f b r(i=l;i=n;i+)f o r(j =l；j =i；j+)x=x+l;(2)f o r (i=l;i =n;i+)f o r (j=l;j =i;j+)f o r (k=l;k =j;k+)x=i+j-k;四，应用题1 .什么是信息？广义地讲，信息就是消息。宇宙三要素(物质、能量、信息)之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、
10、可压缩、可利用、可共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(d a t a)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。2 .数据结构是指数据以及相互之间的关系。记为：数据结构=D,R。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。数据结构是一门研究在非数值计算的程序设计问题中，计算
11、机的操作对象及对象间的关系和施加于对象的操作等的学科。有关数据结构的讨论一般涉及以下三方面的内容：(1)数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；(2)数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；(3)施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像)，它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上
12、的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。3 .评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性;四是算法的时空效率(运行)。4 .D是数据元素的有限集合，S是D上数据元素之间关系的有限集合。5 .算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：有 穷 性 确 定 性 可 行 性 有输入 有输出算法与程序的联系和区别：(1)算法代表了对问题的解，而程序那么是算法在计算机上的特定的实现。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止。因此，操作系统不是一个算法
13、。(2)程序中的指令必须是机器可执行的，而算法中的指令那么无此限制。(3)算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。(4)算法与数据结构是相辅相承的：解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来表达。6.(1)A对应逻辑图形如下，它是一种线性结构。(1)解：语句的频度是2；语句的频度是n；语句的频度是n-1；语句的频度是n-1；语句的频度是n-1；故，该程序段的时间复杂度T I n)=2+n+3*(n-1)=4 n-l=0 (n J (2)解:语句的循环控制变量i 要增加到
14、n,测试到i=n 成立才会终止，故它的频度为n+1；语句作为语句循环体内的语句应该执行n次，但语句本身要执行n+1次，故语句的频度是n (n+1)；同理可得语句、和的频度分别是n 2,n 2 (n+1)和 n 3。该程序段所有语句的频度之和为：T (n)=2 n 3+3 n 2+2 n+l其复杂度为0 (n 3)8.(1)分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关,因此，时间频度T(n)=l+2+3+n=n*(n+l)/2。有 l/4 W T(n)/n W l,故它的时间复杂度为0 (n)即 T(n)与 r?数量级相同。(2)分析算法规律可知时间
15、频度T(n)=l+(l+2)+(l+2+3)+.+(1+2+3+n)。由于有1/6 n e x t=h B.p-n e x t=N I L C.p-n e x t-n e x t=h D.p-d a t a=-l2 .下面关于线性表的表达中，A.线性表采用顺序存储,B.线性表采用顺序存储,C.线性表采用链接存储,D.线性表采用链接存储,3 .线性表是具有n个()A.表元素 B.字符错误的选项是哪一个？(必须占用一片连续的存储单元。便于进行插入和删除操作。不必占用一片连续的存储单元。便于插入和删除操作。的有限序列(n 0)oC.数据元素 D.数据项4.假设某线性表最常用的操作是存取任一指定序号的
16、元素和在最后进行插入和删除运算,那 么 利 用()存储方式最节省时间。A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表5 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么采 用()存储方式最节省运算时间。A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表6 .设一个链表最常用的操作是在末尾插入结点和删除尾结点，那 么 选 用()最节省时间。7 .在带有头结点的单链中插入一个新结点时不可能修改()。A.头指针 B.头 结 点 指 针 域 C.开 始 结 点 指 针 域 D.其它结点指针域8 .双向链表中有两个指针域，l l
17、i n k 和 r l i n k,分别指向前驱及后继，设 p指向链表中的一个结点，q指向一待插入结点，现要求在P前插入q,那么正确的插入为(A.p-l l i n k=q;q-r l i n k=p;p-l l i n k-r l i n k=q;q-l l i n k=p-l 1 i n k;B.q-l l i n k=p-l l i n k;p-l l i n k-r l i n k=q;q-r l i n k=p;p-H i n k=q-r 1 i n k;C.q-r l i n k=p;p-r l i n k=q;p-l l i n k-r l i n k=q;q-r l i n k
18、=p;D.p-l 1 i n k-r l i n k=q;q-r l i n k=p;q-H i n k=p-1 1 i n k;p-l l i n k=q;9 .对于一个头指针为h e a d 的带头结点的单链表，判定该表为空表的条件是()。A.h e a d=N U L L B.h e a d-n e x t=N U L L C.h e a d-n e x t=h e a d D.h e a d!=N U L L1 0 .在顺序表中查找第i 个元素的时间效率最高的算法时间复杂度是()A.0(1)B.0(4)C.O(log2n)D.O(n)1 1 .最好的情况下，在顺序表中按值查找一个元素的
19、算法时间复杂度是(A.O(n)B.0(C.O(log2n)D.0(1)1 2 .假设长度为n的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为()(l l i n k=h e a d B.p-l i n k=N I L C.p=N I L D.p=h e a d,选择1 1.D二，判断1 .链表中的头结点仅起到标识的作用。()2 .线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()3 .顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()4 .顺序存储方式只能用于存储线性结构。()5 .线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同
20、。6 .线性表的特点是每个元素都有一个前驱和一个后继。()7 .取线性表的第i 个元素的时间同i 的大小有关。()8 .循环链表不是线性表。()9 .线性表就是顺序存储的表。()1 0 .顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()二，判断1.X2.V3.X4.X5.X6.X7.X8.X9.X1 0.X三，填空1.当线性表的元素总数根本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。2 .线 性 表 L=(a l,a 2,a n)用数组表示，假定删除表中任一元素的概率相同，那么删除一个 元 素 平 均 需 要 移 动 元 素 的 个 数
21、 是。3 .在一个长度为n的顺序表中第i个 元 素(l=i =n)之前插入一个元素时，需向后移动个元素。4 .对于一个具有n 个结点的单链表，在的结点*p 后 插 入 一 个 新 结 点 的 时 间 复 杂 度 为,在给定值为x的 结 点 后 插 入 一 个 新 结 点 的 时 间 复 杂 度 为。5.在双向循环链表中，向 p所指的结点之后插入指针f 所指的结点，其操作是、_ _ _ _ _ _ _、_ _ _ _ _ _ _、_ _ _ _ _ _ _ _O6 .在双向链表结构中，假设要求在p指针所指的结点之前插入指针为s所指的结点，那么需执行以下语句：s-n e x t=p；s-p ri
22、o r=；p-p ri o r=s；=s；表示元素之间的关系;链式存储结构通过 表示元素之间的关系。8 .对于双向链表，在两个结点之间插入一个新结点需修改的指针共 个，单链表为_ _ _ _ _ _ _ 个。9.指针p 指向单链表L 中的某结点，那么删除其后继结点的语句是：，时间复杂度是 o1 0.带头结点的双循环链表L 中只有一个元素结点的条件是：。三，填空1.顺序2.(n-1)/23 .n-i+14.0(1),0(n)5.f-n e x t=p-n e x t;f-p ri o r=p;p-n e x t-p ri o r=f;p-n e x t=f;6.p-p ri o r s-p ri
23、 o r-n e x t7.物 理 上 相 邻 指 针8.4 29.u=p-n e x t;p-n e x t=u-n e x t;fre e(u);0(1);1 0.L-n e x t-n e x t=L四，算法设计1 .试写一算法在带头结点的单链表结构上实现线性表操作LO C A T E (L,X)。2 .试写一算法在带头结点的单链表结构上实现线性表操作L E N G T H (L)。3 .试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表(a La 2,即)逆置为(a n,a n“，,a 1)o4 .试写一算法，对单链表实现就地逆置。5.设线性表人=(a i，a 2,.,an)
24、,B=(b i.b 2.,bnL试写一个按以下规那么合并A,B为线性表C的算法，即使得C=(aL b i.,am,bm,bm+i.,bn)当 m n 时；线性表A,B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。1.LNode*Locate(LinkList L,int x)链表上的元素查找，返回指针(for(p=l-next;p&p-data!=x;p=p-next);return p;/Locate2.int Length(LinkList L)求链表的长度(for(k=0,p=L;p-next;p=p-next,k+)；retur
25、n k;/Length3.void reverse(SqList&A)顺序表的就地逆置(for(i=0-l;i j;i+,j-)A.elemiA.elem j;/reverse4.void LinkList_reverse(Linklist&L)/链表的就地逆置;为简化算法,假设表长大于2(p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)(q-next=p;p=q;q=s;s=s-next;/把 L 的元素逐个插入新表表头)q-next=p;s-next=q;L-next=s;/LinkList_reverse分析:本算法的思想是，逐个地
26、把L 的当前元素q 插入新的链表头部,p 为新表表头.5.void merge 1 (LinkList&A,LinkList&B,LinkList&C)把链表A 和 B 合并为C,A和 B 的元素间隔排列，且使用原存储空间(p=A-next;q=B-next;C=A;while(p&q)(s=p-next;pnext=q;/将 B 的元素插入if(s)(t=q-next;q-next=s;如A 非空，将 A 的元素插入p=s;q=t;/w h i le/m e rg e 1第三章栈和队列一，选择1.对于栈操作数据的原那么是(A.先进先出 B.后进先出 C.后进后出 D.不分顺序3.最大容量为n
27、的循环队列，队尾指针是re a r,队头是fro n t,那么队空的条件是()。A.(re a r+1)M O D n=fro n t B.re a r=fro n tC.re a r+l=fro n t D.(re a r-1)M O D n=fro n t4当利用大小为n的数组顺序存储一个栈时，假定用t o p=n 表示栈空，那么向这个栈插入一个元素时首先应执行 语句修改t o p 指针。A.t o p+B.t o p-C.t o p=0 D.t o p5.假设一个栈的入栈序列是1,2,3,n,其输出序列为p i,p z,P 3,，PM假 设 6是 n,那么小是()oA.i B.n-i C
28、.n-i+1 D,不确定6 .一个递归算法必须包括()o7 .执行完以下语句段后，i 值为：()i n t f(i n t x)re t u rn (x 0)?x*f(x-1):2);i n t i ;i =f(f);A.2 B.4 C.8 D.无限递归8 .设 栈 S和队列Q的初始状态为空，元素e l,e 2,e 3,e 4,e 5 和 e 6 依次通过栈S,一个元素出栈后即进队列Q,假设6个元素出队的序列是e 2,e 4,e 3,e 6,e 5,e l 那么栈S的容量至少 应 该 是()。A.6 B.4 C.39 .栈和队列的共同点是(A.都是先进先出C.只允许在端点处插入和删除元素D.2
29、B.都是先进后出D.没有共同点10.设计一个判别表达式中左，右括号是否配对出现的算法，采 用()数据结构最正确。A.线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈11.用不带头结点的单链表存储队列时.，其队头指针指向队头结点，其队尾指针指向队尾结点，那么在进行删除操作时()。A.仅修改队头指针 B.仅修改队尾指针C.队头、队尾指针都要修改D.队头，队尾指针都可能要修改12.递归过程或函数调用时，处理参数及返回地址，要用一种称为()的数据结构。A.队列 B.多维数组 C.栈 D.线性表13.假 设 以 数 组 存 放 循 环 队 列 的 元 素，其头尾指针分别为f r o n
30、t 和 r e a r,那么当前队列中的元素个数为(A.(r e a r-f r o n t+m)%m B.r e a r-f r o n t+1 C.(f r o n t-r e a r+m)%m D.(r e a r-f r o n t)%m14.循环队列存储在数组A 中，那么入队时的操作为()。A.r e a r=r e a r+l B.r e a r=(r e a r+l)m o d (m-1)C.r e a r=(r e a r+1)m o d m D.r e a r=(r e a r+1)m o d(m+1)15 .假设用一个大小为6的数组来实现循环队列，且当前r e a r和f
31、r o n t的值分别为0和3,当从队列中删除一个元素，再参加两个元素后，r e a r和f r o n t的值分别为多少？()A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 1一，选择4 B二，填空1.是限定仅在表尾进行插入或删除操作的线性表.3.中缀表达式3*(x+2)-5所 对 应 的 后 缀 表 达 式 为；后缀表达式“45*32+-”的值为4.顺 序 栈 用d a t a l.n 存储数据，栈 顶 指 针 是t o p,那 么 值 为x的元素入栈的操作是5.向一个循环队列中插入一元素时，需首先移动,然后再向所指位置新插入的元素。6 .用下标0开始的N元数组实现循环队列时，
32、为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=7 .用长度为n的数组顺序存储一个栈时，假设用t o p=n表示栈空，那么表示栈满的条件为。二，填空1.栈3.3 x 2 +*5-154.d a t a +t o p =x；5 .队尾指针 写入6.(M+l)M O D N (M+l)%N；7.t o p=0三，应用题1.指出以下程序段的功能(1)v o i d De m o l(S e q S t a c k *S)i n t i;a r r|6 4 ;n=0;w h i l e (S t a c k E m p t y(S)a r r n+=P o p(S);f o r
33、(i=0,i n;i+)P u s h(S,a r r i );/De m o 1(2)S e q S t a c k S I,S 2,t m p;Da t a T y p e x;/假设栈t m p和S2已做过初始化while(!StackEmpty(&S1)(x=Pop(&Sl);Push(&tmp,x);)while(!StackEmpty(&tmp)(x=Pop(&tmp);Push(&Sl,x);Push(&S2,x);程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。(2)程序段的功能是利用tmp栈将一个
34、非空栈s i 的所有元素按原样复制到一个栈s2 当中去。四，算法设计题1.回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)1.根据提示，算法可设计为：以下为顺序栈的存储结构定义#define StackSize 100 假定预分配的栈空间最多为100个元素typedef char DataType;假定栈元素的数据类型为字符typedef stru c tDataType dataStackSize;int top;SeqStack;int IsHuiwen(char*t)判断t
35、 字符向量是否为回文，假设是，返 回 1,否那么返回0SeqStack s;int i,len;char temp;InitStack(&s);len=s trle n(t);求向量长度for(i=0;ilen/2;i+)将一半字符入栈Push(&s,t i );while(!EmptyStack(&s)/每弹出一个字符与相应字符比拟temp=Pop(&s);if(temp!=Si)return 0;/不等那么返回 0else i+;)r e t ur n 1 ;/比拟完毕均相等那么返回1第 四 章 串一，选择1 .下面关于串的的表达中，哪一个是不正确的？()A.串是字符的有限序列 B.空串是
36、由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储2 .设有两个串p 和 q,其中q是 p的子串，求 q 在 p中首次出现的位置的算法称为()A.求子串 B.联接 C.匹配 D.求串长3 .串的长度是指()A.串中所含不同字母的个数 B.串中所含字符的个数C.串中所含不同字符的个数 D.串中所含非空格字符的个数4 .假设串S=s o f t wa r e ,其子串的数目是()。A.8 B.3 7 C.3 6 D.9选择2.C3.B4.B二，填空1 .空格串是指，其 长 度 等 于。2 .组成串的数据元素只能是_ _ _ _ _ _.3 .一个字符串中 称为
37、该串的子串。4 .IN D E X (D A T A S T R U C T U R E ,S T R )=7.设 T和 P是两个给定的串，在 T中寻找等于P的子串的过程称为_,又称P为.二，填空1 .由空格字符(A S C II值 3 2)所组成的字符串 空格个数2 .字符3 .任意个连续的字符组成的子序列4 .57.模式匹配 模式串第五章数组和广义表一，选择1 .广义表L=(x,y,z),a,(u,t,w),从 L 表中取出原子项t的运算是()。A.h e a d(t a i l(t a i l(L)B.t a i l(h e a d(h e a d(t a i l(L)C.h e a d
38、(t a i l(h e a d(t a i l(L)D.h e a d(t a i l(h e a d(t a i l(t a i l(L)2 .广义表A=(a,b,(c,d),(e,(f,g),那么下面式子的值为(2H e a d(T a i l(H e a d(T a i l(T a i 1(A)A.(g)B.(d)C.c D.d3 .稀疏矩阵一般的压缩存储方法有两种，即 0A.二维数组和三维数组 B.三元组和散列C.三元组和十字链表 D.散列和十字链表4 .二维 数 组 A 的 每 个 元 素 是 由 6个字符组成的串，其 行 下 标 i=0,1,8,列下标j=l,2,，1 0。假设A
39、 按行先存储，元素A 8,5 的起始地址与当A按列先存储时的元素()的起始地址相同。设每个字符占一个字节。A.A 8,5 B.A 3,1 0 C.A 5,8 D.A 0,9 5 .对稀疏矩阵进行压缩存储目的是()。A.便于进行矩阵运算B.便于输入和输出C.节省存储空间 D.降低运算的时间复杂度6 .设 A是 n*n的对称矩阵，将 A的对角线及对角线上方的元素以列为主的次序存放在一维数组B l.n(n+l)/2 中，对上述任一元素a“(li,j W n,且 i j)在 B中的位置为()。A.i(i-l)/2+j B.j(j-l)/2+i C.j(j-l)/2+i-l D.i(i-l)/2+j-l
40、7 .A N,N 是对称矩阵，将下面三角(包括对角线)以行序存储到一维数组T N (N+1)/2 中，那么对任一上三角元素对应T k 的下标k是()。A.i(i-1)/2+j B.j (j-1)/2+i C.i(j-i)/2+1 D.j (i-1)/2+18 .设广义表1=(a,b,c),那么L的长度和深度分别为(A.1 和 1 B.1 和 3 C.1 和 2 D.2 和 39 .数组A 0.4,-1.-3,5.7 中含有元素的个数()。A.5 5 B.4 5 C.1 0 .下面说法不正确的选项是()。A.广义表的表头总是一个广义表C.广义表难以用顺序存储结构一，选择1 1 IM 1111 r
41、n3 6 D.1 6B.广义表的表尾总是一个广义表D.广义表可以是一个多层次的结构二，判断1 .一个稀疏矩阵A.采 用三元组形式表示，假设把三元组中有关行下标与列下标的值互换，并把m 和 n 的值互换，那么就完成了 A.的转置运算。()2 .从逻辑结构上看，n 维数组的每个元素均属于n 个向量。()3 .稀疏矩阵压缩存储后，必会失去随机存取功能。()4 .对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。(5 .数组可看成线性结构的一种推广，因此与线性表一样可对它进行插入，删除操作。()6 .所谓取广义表的表尾就是返回广义表中最后一个元素。()7 .二维以上的数组其实是一种特殊的
42、广义表。()8 .广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。()9 .假设一个广义表的表头为空表，那么此广义表亦为空表。()1 0 .广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。(二，判断1.X2.V3.J1.75.X6.X7.V8.X9.X1 0.X四应用题1.画出以下广义表的两种存储结构图(O,A,(B,(C,D),(E,F)。2.设某表H 如下:ABCXa la 2blclc2其中A,B,C为子表名，a l,a 2,bl,cl,c2,x为其元素。试用广义表形式表示H,并写出运算HE A D(H)和 T A I L(H)函数从H中取出单元素a 2 的
43、运算；(1)H(A(a i,a2),B(b i),C(C 1,c2),x)H EA D(TA I L(H EA D(H)=a2五，算法设计1.设任意n个整数存放于数组A(l:n)中，试编写程序，将所有正数排在所有负数前面2 .设二维数组l.n 含有m*n 个整数。判断a中所有元素是否互不相同?输出相关信息(y e s/n o)。1.此题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i 和 j,i自小至大搜索到负数停止，j自大至小搜索到正数停止。然 后 i 和 j 所指数据交换，继续以上过程，直 到 i=j 为止。v o i d A r r a n ge(i n t A ,i n
44、 t n)/n 个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面i n t i=0,j=n-l,x;用类C 编写，数组下标从。开始w h i l e(i j)w h i l e(i 0)i+;w h i l e(i j&A j 0)j-;i f(i j)x=A i ;A i+=A j ;A j T=x;交换 A i 与 A j)/算法A r r a n ge 结束.算法讨论 对数组中元素各比拟一次，比拟次数为n。最正确情况(已排好，正数在前，负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2 次交换。用类c编写，数组界偶是O.n T。空间复杂度为0(1).2 .判断二维数
45、组中元素是否互不相同，只有逐个比拟，找到一对相等的元素，就可结论为不是互不相同。如何到达每个元素同其它元素比拟一次且只一次？在当前行，每个元素要同本行后面的元素比拟一次(下面第一个循环控制变量p的 f o r 循环)，然后同第i +1行及以后各行元素比拟一次，这就是循环控制变量k 和 p的二层f o r 循环。i n t J u d gEq u a l (i n g a m n ,i n t i n,n)判断二维数组中所有元素是否互不相同，如是，返 回 1；否那么，返回0。f o r(i=0;i m;i+)f o r(j=0;j n-l;j+)f o r(p=j+l ;p n;p+)和同行其它
46、元素比拟i f(a i j =a i p )p r i n t f(n o );r e t u r n(0);只要有一个相同的，就结论不是互不相同f o r(k=i+l;k m;k+)和第i+1行及以后元素比拟f o r(p=0;p n;p+)i f (a i j =a k p )p r i n t f(n o );r e t u r n(0);/f o r(j=0;j lchild!=NULLC.p-ltag=O D.p-ltag=l二根底知识题1.列出右图所示二叉树的叶结点、分支结点和每个结点的层次。2.使 用(1)顺序表示和(2)二叉链表表示法，分别画出右图所示二叉树的存储表示。(1)顺
47、序表示0 1 2 3 4 5 6 7 8 9|10 II 12 13 14 15 16 17(2)二叉链表表示试画出3 个结点的二叉树的所有不同形态。4.设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。字符A,B,C,D 出现的次数为9,1,5,3。其哈夫曼编码如下A:L B:000,C:01,D:001第七章图一，选择1.图中有关路径的定义是()。A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形成的序列C.由不同边所形成的序列D.上述定义都不是2 .设无向图的顶点个数为n,那么该图最多有()条边。A.n-1 B
48、.n(n-l)/2 C.n(n+l)/23 .一个n个顶点的连通无向图，其边的个数至少为()。A.n-1 B.n C.n+14 .要连通具有n个顶点的有向图，至 少 需 要()条边。A.n-l B.n C.n+15 .n个结点的完全有向图含有边的数目A.n*n B.n (n+1)C.n /26 .求解最短路径的F lo y d算法的时间复杂度为()。A.0 (n)B.0 (n+c)C.0 (n*n)D.0D.n lo g n；D.2 nD.n*(n 1)D.0 (n*n*n)7.有向图 G=(V,E),其中 V=E=,G 的拓扑序列是()。A.Vb V3,V4,V6,V2,V5,V7B.Vb
49、V3,V2,V6,V4,V5,V7C.V i,v3,v.b v5,V2,V6,V7D.V 1,V2,V5,V3,V4,V6,v78 .在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.0(n)B.0(n+e)C.0(n*n)9.有n个结点的有向完全图的边数是(A.n2 B.2 n C.n (n-1)D.0(n*n*n)D.2 n (n+1)1 0 .以下哪一种图的邻接矩阵是对称矩阵？()A.有向图B.无向图 C.A 0 V网 D.A 0 E网1 1 .当一个有N个顶点的图用邻接矩阵A表示时，顶点V i的 度 是()。E A i,j YAj,i 之 AU,刃 E A j,iA.C.i=l D
50、.i=l+1 2 .对图做宽度优先遍历时会使用何种数据结构()A.队列 B.树 C.栈 D.集合1 3 .无向图 G=(V,E),其中：V=a,b,c,d,e,f ,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d),对该图进行深度优先遍历，得到的顶点序列正确的选项是()。A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b1 4 .以下关于A O E网的表达中，不正确的选项是()(,A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活