数据结构期末习题答案.pdf

《数据结构期末习题答案.pdf》由会员分享，可在线阅读，更多相关《数据结构期末习题答案.pdf（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章绪论一，选择题1 .组成数据的基本单位是（）A.数据项 B.数据类型 C.数据元素 D.数据变量2 .数据结构是研究数据的（）以及它们之间的相互关系。A.理想结构，物理结构 B.理想结构，抽象结构C.物理结构，逻辑结构 D.抽象结构，逻辑结构3 .算法分析的两个主要方面是（）A.正确性和简单性 B.可读性和文档性C.数据复杂性和程序复杂性D.时间复杂度和空间复杂度4 .算法分析的目的是A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性5 .算法的时间复杂度取决于（）A.问题的规模 B.待处理数据的初态 C.A和 B D.以上都不

2、是6.一个算法应该是（）。A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和 C.7 .下面关于算法说法错误的是（）A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的8 .从逻辑上可以把数据结构分为（）两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构9 .程序段 f o r（i=n-l;i =l;i）f o r（j=l j A j+l ）A j 与 A j+1 对换;其 中 n 为正整数，则最后一行的语句频度在最坏情况下是（）A

3、.0 （n）B.O（nlogn）C.0（n3）D.0（n2）1 0 .连续存储设计时，存储单元的地址（）。A.一 定 连 续 B.一 定 不 连 续 C.不 一 定 连 续 D.部分连续，部分不连续二，判断题1 .数据结构的抽象操作的定义与具体实现有关。（）2 .数据结构是数据对象与对象中数据元素之间关系的集合。3 .在顺序存储结构中，有时也存储数据结构中元素之间的关系。（）4 .数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。5 .算法和程序原则上没有区别，在讨论数据结构是两者是通用的。6.同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数

4、都相等。7 .数据的逻辑结构与数据元素本身的内容和形式无关。8 .算法的优劣与算法描述语言无关，但与所用计算机有关。（）9.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()1 0.算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。()一，选择题1.C2.C3.D4.C5.C6.B7.D8.C9.D10.A二，判断题1.X2.V3.X4.V5.X6.X7.V8.X9.V10.X三，填空1.数据的物理结构包括的表示和的表示。2.对于给定的n 个元素，可以构造出的逻辑结构有,，四种。3.一个数据结构在计算机中称为存储结构。4.抽 象 数 据

5、类 型 的 定 义 仅 取 决 于 它 的 一 组,而与 无关，即不论其内部结构如何变化，只要它的 不变，都不影响其外部使用。5.线性结构中元素之间存在关系，树形结构中元素之间存在关系,图形结构中元素之间存在关系。6.一个算法有5 个特性:、，有零个或多个输入、有一个或多个输出。7.已知如下程序段for(i=n；i=1 ;i+)语句 1(x:=x+l；语句 2for(j=n;j=i;j+)语句 3y:=y+l;语句 4语 句 1 执行的频度为；语句2 执行的频度为；语句3 执行的频度为；语句4 执行的频度为。8.在下面的程序段中，对 x 的 赋 值 语 句 的 频 度 为 (表示为n 的函数)

6、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 的执行次数为 ofo r(i=l；i=i;j)10.下面程序段的时间复杂度为一。(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 .1

7、+(1+2+(1+2+3)+(1+2+n)=n(n+l)(n+2)/6 0(n3)9 .(n+3)(n-2)/21 0 .O(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=a,b)，(b,c)

8、,(c,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=(1,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；in：i+f o r (j=0；j c iJ j

9、 J-O；f o r (k=0；k (n；k+)(4)c i U=c i U +a i k +b k U;)8.求下列算法段的语句频度及时间复杂度(1)f o r(i=l;i =n;i+)f o r(j =1;j =i ;j+)x=x+1;(2)f o r (i=l;i =n;i+)f o r (j=l;j =i;j+)f o r (k=l;k n e x t=h B.p-n e x t=NI L C.p-n e x t-n e x t=h D.p-d a t a=-l2.F 面关于线性表的叙述中，A.线性表采用顺序存储,B.线性表采用顺序存储,C.线性表采用链接存储,D.线性表采用链接存储,

10、3.线性表是具有n个()A.表元素 B.字符错误的是哪一个？()必须占用一片连续的存储单元。便于进行插入和删除操作。不必占用一片连续的存储单元。便于插入和删除操作。的有限序列(n 0)。C.数据元素 D.数据项4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利 用()存储方式最节省时间。A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A.单 链 表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表6.设一个链表最常用的操作

11、是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表 B.单循环链表 C.带尾指针的单循环链表 D.带头结点的双循环链表7.在带有头结点的单链中插入一个新结点时不可能修改A.头指针B.头 结 点 指 针 域 C.开始结点指针域 D.其它结点指针域8.双向链表中有两个指针域，H 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-11i n k-r 1i n k=q;q-H i n k=p-l l i n k;B.q-l l i

12、n k=p-11 i n k;p-l l i n k-r 1i n k=q;q-r 1i n k=p;p-l l i n k=q-r l i n k;C.q-r l i n k=p;p-r l i n k=q;p-l 1i n k-r l i n k=q;q-r l i n k=p;D.p-H i n k-r 1 i n k=q;q-r l i n k=p;q-H i n k=p-11 i n k;p-l l i n k=q;9.对于一个头指针为h e a d 的带头结点的单链表，判定该表为空表的条件是（）。A.h e a d 二 二 NU L L B.h e a d-*n e x t=二 N

13、U L L C.h e a d f n e x t 二 二 h e a d D.h e a d!=NU L L10.在顺序表中查找第i 个元素的时间效率最高的算法时间复杂度是（）。A.0(1)B.0()C.O(log2n)D.0(n)11.最好的情况下，在顺序表中按值查找一个元素的算法时间复杂度是()。A.0(n)B.0(G)C.O(log2n)D.0(1)12.若长度为n的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为()(K=i l i n k=h e a d B.p-l i n k=NI L C.p=NI L D.p=h e a d一,选择1.A2.B3.C4

14、.A5.D6.D7.A8.D9.B10.A11.D12.C13.C14.C15.A二，判断1.链表中的头结点仅起到标识的作用。()2.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()3.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()4.顺序存储方式只能用于存储线性结构。()5.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。6.线性表的特点是每个元素都有一个前驱和一个后继。()7.取线性表的第i 个元素的时间同i 的大小有关。()8.循环链表不是线性表。()9.线性表就是顺序存储的表。()10.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

15、()二，判断1.X2.J3.X1.X5.X6.X7.X8.X9.X10.X三，填空1.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。2.线 性 表 L=(al,a2,a n)用数组表示，假定删除表中任一元素的概率相同，则删除一个 元 素 平 均 需 要 移 动 元 素 的 个 数 是。3.在一个长度为n 的顺序表中第i 个 元 素(l=inext=p；s-prior=；p-prior=s；=s；7.顺序存储结构通过 表示元素之间的关系;链式存储结构通过 表示元素之间的关系。8.对于双向链表，在两个结点之间插入一个新结点需修改的指

16、针共 个，单链表为_个。9.已知指针p 指向单链表L 中的某结点，则删除其后继结点的语句是：时间复杂度是。10.带头结点的双循环链表L 中只有一个元素结点的条件是：。三，填空1 .顺 序2.(n-1)/23.n-i+l4.0(1),0(n)5.f-next=p-next;f-prior=p;p-next-prior=f;p-next=f;6.p-prior s-prior-next7.物 理 上 相 邻 指 针8.4 29.u=p-next;p-next=u-next;free(u);0(1);10.L-next-next=L四，算法设计1.试写一算法在带头结点的单链表结构上实现线性表操作LO

17、CATE(L,X)。2.试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。3.试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表(a a2,逆置为(a”an-i,a4.试写一算法，对单链表实现就地逆置。5.设线性表A=(ai，a2.,an),B=(b|.b2.,bn).试写一个按下列规则合并A,B 为线性表C 的算法，即使得C=(ai,bam,bm,bm+1.,bn)I mn 时；线性表A,B 和 C 均以单链表作存储结构，且C 表利用A 表和B 表中的结点空间构成。注意：单链表的长度值m 和 n 均未显式存储。1.LNode*Locate(LinkList L,i

18、nt 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+);return k;/Length3.void reverse(SqList&A)顺序表的就地逆置(for(i=0,j=A.length-1;inext;q=p-next;s=q-next;p-next=NULL;while(s-next)(q-next=p;p=q;q=s;s=snext;把L 的元素逐个插入新表表头)q-next=

19、p;s-next=q;L-next=s;/LinkLi st_re verse分析:本算法的思想是，逐个地把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 l e/m e r g e 1第三章栈和队列一

20、，选择1.对于栈操作数据的原则是（）。A.先进先出 B.后进先出 C.后进后出 D,不分顺序3.最大容量为n的循环队列，队尾指针是r e a r,队头是f r o n t,则 队 空 的 条 件 是（）。A.（r e a r+1）M OD n=f r o n t B.r e a r=f r o n tC.r e a r+l=f r o n t D.（r e a r-1）M OD n=f r o 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

21、p5 .若已知一个栈的入栈序列是1,2,3,n,其输出序列为p i,p z,p：”，p”若 p、是 n,则p（）。A.i B.n-i C.n-i+1 D.不确定6 .一个递归算法必须包括（）。A.递归部分 B.终止条件和递归部分 C.迭代部分 D.终止条件和迭代部分7 .执行完下列语句段后，i 值为：（）i n t f （i n t x）r e t u r n （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,

22、若 6 个元素出队的序列是e 2,e 4,e 3,e 6,e 5,e l 贝 U 栈 S的容量至少应该是（）oA.6 B.4 C.39.栈和队列的共同点是（）。A.都是先进先出C.只允许在端点处插入和删除元素D.2B.都是先进后出D.没有共同点1 0 .设计一个判别表达式中左，右括号是否配对出现的算法，采 用（）数据结构最佳。A.线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈1 1 .用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时（）A.仅修改队头指针 B.仅修改队尾指针C.队头、队尾指针都要修改D.队头，队尾指针都可能要修

23、改1 2 .递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A.队列 B.多维数组 C.栈 D.线性表1 3 .假设以数组A m 存放循环队列的元素,其头尾指针分别为f r o n 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)%m1 4 .循环队列存储在数组A 中，则入队时的操作为()0A.r e a r=r e a r+l B.r e a r=(r e a r+1)m o d

24、(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)1 5 .若用一个大小为6的数组来实现循环队列，且当前r e a r和f r o n t的值分别为。和3,当从队列中删除一个元素，再加入两个元素后，r e a r和f r o n t的值分别为多少？()A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 1一，选择l.B3.B4 B5.D6.B7.B8.C9.C1 0.D1 1.D1 2.C1 3.A1 4.D1 5.B二，填空1._ _ _ _ _ _ _是限定仅在表尾进行插入或删除操作的线性表。3 .中缀

25、表达式3*(x+2)-5所对应的后缀表达式为；后缀表达式“4 5*3 2+-”的值为。4.顺序栈用d a t a 1.n 存储数据，栈顶指针是t o p,则值为x的 元 素 入 栈 的 操 作 是。5 .向一个循环队列中插入一元素时.，需首先移动，然后再向所指位置新插入的元素。6.用下标0开始的N元数组实现循环队列时，为实现卜标变量M加1后在数组有效卜标范围内循环，可采用的表达式是：M=7 .用长度为n的数组顺序存储一个栈时，若用t o p=n表示栈空，则表示栈满的条件为。二，填空1.栈3.3 x 2 +*5-1 54.d a t a +t o p =x；5 .队尾指针 写入6.(M+1)M

26、OD N(M+1)%N；7.t o p=0三，应用题1 .指出下列程序段的功能(1)v o i d D e m o l(S e q S t a c k *S)i n t i;a r r l 64 J ;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 (i=0,i n;i+)P u s h(S,a r r f i );/D e m o l(2)S e q S t a c k S 1,S 2,I m p;D a t a T y p e x;假设栈t m p和S2已做过初始化w h i l e (!S t ac k E m

27、p t y (&S 1)x=Pop(&Sl);Push(&tmp,x);)while(!StackEmpty(&tmp)(x=Pop(&tmp);Push(&Sl,x);Push(&S2,x);程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在6 4 个以内。程序段的功能是利用t m p 栈将一个非空栈s i 的所有元素按原样复制到一个栈s 2 当中去。四，算法设计题1.回文是指正读反读均相同的字符序列，如“abba”和“abd ba”均是回文，但“g o o d”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一

28、半字符入栈)1.根据提示，算法可设计为：以下为顺序栈的存储结构定义#d e f i n e S t ac k S i z e 1 0 0 假定预分配的栈空间最多为1 0 0 个元素t y p e d e f c h ar D at aT y p e;假定栈元素的数据类型为字符t y p e d e f s t r u c t D at aT y p e d at aS t ac k S i z e;i n t t o p;S e q S t ac k;i n t I s H u i w e n (c h ar *t)判断t 字符向量是否为回文，若是，返 回 1,否则返回0S e q S t a

29、c k s;i n t i ,l e n;c h ar t e m p;I n i t S t ac k(&s);l e n=s t r l e n(t);求向量长度f o r (i=0;i l e n/2;i+)将一半字符入栈P u s h(&s,t i);w h i l e(!E m p t y S t ac k(&s)/每弹出一个字符与相应字符比较t e m p=P o p (&s);i f(t e m p!=S i)r e t u r n 0 ;/不等则返回 0e l s e i+;)r e t u r n 1 ;/比较完毕均相等则返回1)第四章串一，选择1 .下面关于串的的叙述中，哪

30、一个是不正确的？（）A.串是字符的有限序列 B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储2 .设有两个串p 和 q,其中q是 p的子串，求 q 在 p中首次出现的位置的算法称为（）A.求子串 B.联接 C.匹配D.求串长3 .串的长度是指（）A.串中所含不同字母的个数C.串中所含不同字符的个数B.串中所含字符的个数D.串中所含非空格字符的个数4 .若串S=s o f t w ar e ,其子串的数目是（）。A.8 B.3 7 C.3 6 D.9一，选择1.B2.C3.B4.B二，填空1 .空格串是指，其 长 度 等 于。2 .组成串的数据元

31、素只能是_o3 .一个字符串中 称为该串的子串。4 .I N D E X （D AT AS T R U C T U R E ,S T R ）=。7.设 T和 P是两个给定的串，在 T中寻找等于P的子串的过程称为，又称P为二，填空1 .由 空 格 字 符（A S C H 值 3 2）所组成的字符串 空格个数2 .字符3 .任意个连续的字符组成的子序列4 .57.模式匹配 模式串第五章数组和广义表一，选择1 .已知广义表L=(x,y,z),a,(u,t,w),从 L表中取出原子项t的运算是()。A.h e ad (t ai l (t ai l (L)B.t ai l (h e ad (h e ad

32、 (t ai l (L)C.h e ad (t ai l (h e ad (t ai l (L)D.h e ad (t ai l (h e ad (t ai l (t ai l (L)2 .广义表A=(a,b,(c,d),(e,(f,g),则下面式子的值为()。H e ad(T ai l(H e ad(T ai 1(T ai 1(A)A.(g)B.(d)C.c D.d3 .稀疏矩阵一般的压缩存储方法有两种,即()A.二维数组和三维数组B.三元组和散列C.三元组和十字链表 D.散列和十字链表4 .二 维 数 组 A 的 每 个 元 素 是 由 6 个字符组成的串，其 行 下 标 i=0,1,8,

33、列下标j=l,2,，1 0。若 A按行先存储，元素A 8,5 的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。A.A 8,5 B.A 3,1 0 C.A 5,8 D.A 0,95.对稀疏矩阵进行压缩存储目的是（）。A.便于进行矩阵运算B.便于输入和输出C.节省存储空间 D.降低运算的时间复杂度6.设 A是 n*n 的对称矩阵，将 A的对角线及对角线上方的元素以列为主的次序存放在一维数组B L .n（n+l）/2 中，对上述任一元素a“（l i,j W n,且 ij）在 B 中的位置为（）。A.i（i-l）/2+j B.j（j-l）/2+i C.j（j-l）/2+i-

34、l D.i（i-l）/2+j-l7.A N,N 是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T N （N+1）/2 中，则对任一上三角元素对应T 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.设广义表L=(a,b,c),则 L的长度和深度分别为()。A.1 和 1 B.1 和 3 C.1 和 2 D.2 和 39.数组A 0.4,-L.-3,5.7 中含有元素的个数()。A.55 B.4 5 C.1 0 .下面说法不正确的是（）。A.广义表的表头总是一个广义表C.广义表难以用顺序存储结构3 6 D.1

35、 6B.广义表的表尾总是一个广义表D.广义表可以是一个多层次的结构一，选择l.D2.D3.C4.B5.C6.B7.B8.C9.B1 0.A二，判断1.一个稀疏矩阵A*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换,并把m 和 n的值互换，则就完成了 A*,的转置运算。（）2 .从逻辑结构上看，n 维数组的每个元素均属于n个向量。（）3 .稀疏矩阵压缩存储后，必会失去随机存取功能。（）4 .对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（）5.数组可看成线性结构的种推广，因此与线性表一样可对它进行插入，删除操作）6.所谓取广义表的表尾就是返回广义表中最后一个元素

36、。（）7.二维以上的数组其实是种特殊的广义表。（）8.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）9.若一个广义表的表头为空表，则此广义表亦为空表。（）1 0 .广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（）二，判断1.X2.V3.J4.V5.X6.X7.V8.X9.X1 0.X四应用题1 .画出下列广义表的两种存储结构图（）,A,（B,（C,D）,（E,F）。2 .设某表H如下：ABCXala2b lc lc 2其 中 A,B,C为子表名，al,a2,b l,c l,c 2,x 为其元素。试用广义表形式表示H,并写出运算H E A D(H)和 T

37、A I L(H)函数从H中取出单元素a2 的运算；(1)H(A(at,a2),B(b i),C(c i,C 2),x)H E A D(T A I L(H E A 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

38、id A r r an ge(in t A ,in t n)/n 个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面(in t i=0,j=n-l,x;用类C编写，数组下标从。开始w hil e(ij)w hil e(i 0)i+;w hil e(ij&A j 0)j;if(ij)x=A i;A i+=A j;A j-=x;交换 A i 与 A j)/算法A r r an ge 结束.算法讨论 对数组中元素各比较一次，比较次数为n。最佳情况(已排好，正数在前，负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2 次交换。用类c 编写，数组界偶是O.n T。空间复杂度为0(1)

39、.2 .判断二维数组中元素是否互不相同，只有逐个比较，找到 对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次(下面第一个循环控制变量P的 fo r 循环)，然后同第i +1 行及以后各行元素比较一次，这就是循环控制变量k和 p的二层fo r 循环。in t J u d gE q u al(in g a m n ,in t m,n)判断二维数组中所有元素是否互不相同，如是，返 回 1；否则，返回0。fo r(i=0;im;i+)fo r(j=0;jn-l;j+)fo r (p=j+l ;p n;p+)和同行其它元素比较

40、if(a i j=a i p )p r in t f(n o );r e t u r n(0);只要有一个相同的，就结论不是互不相同fo r(k=i+l;k m;k+)和第i+1 行及以后元素比较fo r(p=0;p n;p+)if(a i j=a k p )p r in t f(n o );r e t u r n(0);/fo r(j=0;j l chi l d!=N U L LC.p-l t ag=0 D.p-l t ag=1二基础知识题1.列出右图所示二叉树的叶结点、分支结点和每个结点的层次。2.使用（1）顺序表示和（2）二叉链表表示法，分别画出右图所示二叉树的存储表示。i(1)顺序表示

41、0 1 2 3 4 5 6 7 8 9I I I I I I I I I10 I I 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.由不同边所形成的序列2.设无向图的顶点个数为n,则该图最多有()条边。A.n-1 B

42、.n(n-l)/2 C.n(n+l)/23.一个n个顶点的连通无向图，其边的个数至少为()A.n-1 B.n C.n+14.要连通具有n个顶点的有向图，至少需要()条边。A.n-1 B.n C.n+15.n个结点的完全有向图含有边的数目()。A.n*n B .n (n+1)C.n /26 .求解最短路径的F l o y d算法的时间复杂度为()。A.0 (n)B.0 (n+c)C.0 (n*n)7.已知有向图 G=(V,E),其中 V=%,V2,V3,V,V5,V6,VT,D.上述定义都不是D.0D.n l o gn；D.2nD.n*(n 1)D.0 (n*n*n)E=,V,V，,G 的拓扑序

43、列是()。A.V 1,V3,V.V6 V2 V5,V7 B.V,.V3,V2 V6)V,.V5,V7C.V V3(V4,V5,V2)V6)V r D.V,V V 6,V 78.在用邻接表表示图时，拓扑排序算法时间复杂度为()oA.0(n)B.0(n+e)C.0(n*n)D.0 (n*n*n)9.有n个结点的有向完全图的边数是()A.n2 B.2n C.n(n-1)D.2n(n+1)10 .下列哪一种图的邻接矩阵是对称矩阵？()A.有向图 B.无向图 C.A 0 V网 D.A 0 E网11.当一个有N个顶点的图用邻接矩阵A表示时，顶点V i的 度 是()。SA i,j 曲 内 t 4反刃1 同A

44、.=B.j=l C.i=l D.1=1+j=l12.对图做宽度优先遍历时会使用何种数据结构()A.队列 B.树 C.栈 D.集合13.无向图 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,b14.下 列 关 于A OE网的叙述中，不正确的是()。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完

45、成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成1 5.下面哪一 一 方 法可以判断出一个有向图是否有环()：A.深度优先遍历 B.拓扑排序 C.求 最 短 路 径D.求关键路径一,选择1.A2.B3.A4.B5.D6.D 7.A 8.B 9.C10.B11.B 12.A13.D14.B 15.B二，判断1.树中的结点和图中的顶点就是指数据结构中的数据元素。（Y）2.一个图G 有 个顶点，-1条边，则该图可以看成是G 的 棵生成树。（N ）3.如 果 AOE网中某一个关键活动延迟一天，则整个工程将延期一天。反之，如果缩短该关键活动的持续时

46、间，则一定可使整个工程提前完工。（N）4.有飞条边的无向图，在邻接表中有e个结点。（N ）5 .有向图中顶点V的度等于其邻接矩阵中第V 行中的1 的个数。（N ）6 .强连通图的各顶点间均可达。（Y）7 .强连通分量是无向图的极大强连通子图。（N ）8 .连通分量指的是有向图中的极大连通子图。（N ）9 .无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（N ）10.在图G 的最小生成树G 1 中，可能会有某条边的权值超过未选边的权值。（Y）四，应用题1.画 出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和5个顶点的无向完全图。2.给出右图的邻接矩阵、领接表表示。3.对下

47、图所示的连通图，请分别用普里姆（P r i m）和克鲁斯卡尔（K r u s k a l）算法构造其最小生成树。4.已知某图的邻接表为（1）.写出此邻接表对应的邻接矩阵；（2）.写出山v l 开始的深度优先遍历的序列；时间复杂度是多少？（4）.写出由v l 开始的广度优先遍历的序列；时间复杂度是多少？(2)V1V2V5V3V4V6(4)V1V2V3V4V5V65.画出下图所示的AOV网的所有拓扑有序序列。-+共有8 种:ADBECF ADBEFC ADEBCF ADEBFCDABECF DABEFC DAEBCF DAEBFC6.对图所示的有向图，试利用Dijkstra算法求出从源点1到其他各

48、顶点的最短路径,从顶点1 到其他各顶点的最短路径及距离如下：1-3(1 5)1-3-2 (19)3 f 6-4 (29)3 f 2-5 (29)13 f 6(25)第九章查找一，选择1.对 N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()A.(N+l)/2 B.N/2 C.N D.(1+N)*N/22.对线性表进行二分查找时，要求线性表必须()A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序3.散列函数有一个共同的性质，即 函 数 值 应 当 以()取其值域的每个值。A.最大概率 B.最小概率 C.平均概率 D.同

49、等概率4.具 有 12个关键字的有序表，折半查找的平均查找长度()A.3.1 B.4 C.2.5 D.55.设有一组记录的关键字为19,14,23,1,68,20,84,27,55,11,10,7 9 ,用链地址法构造散列表，散列函数为II(key)=key M O D 13,散列地址为1 的链中有()个记录。A.1 B.2 C.3 D.47 .假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？（）A.k-1 次 B.k 次 C.k+1 次 D.k（k+l）/2 次8 .既希望较快的查找又便于线性表动态变化的查找方法是（）A.顺序查找 B.折半查找 C

50、.索引顺序查找 D.哈希法查找9 .分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）A.（10 0,8 0,9 0,6 0,12 0,110,13 0）B.（10 0,12 0,110,13 0,8 0,6 0,9 0）C.（10 0,6 0,8 0,9 0,12 0,110,13 0）D.（10 0,8 0,6 0,9 0,12 0,13 0,110）10.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作（）型调整以使其平衡。A.LL B.LR C.R L D.R R1.A2.B3.D4.A5.