数据结构期末习题答案

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

2、个都是错误的8从逻辑上可以把数据结构分为（）两大类。A.动态结构、静态结构C. 线性结构、非线性结构 9程序段 for ( i=n-1;i=1;i-) for (j=1jAj+1) AjB 顺序结构、链式结构D 初等结构、构造型结构与 Aj+1 对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（）32A O（ n）B O（nlogn）C. O（n ）D O（n ）10连续存储设计时，存储单元的地址（）。A. 定连续B .定不连续 C 不一定连续D 部分连续，部分不连续A. 问题的规模B.待处理数据的初态C. A 和B6. 个算法应该是（）。A .程序 B.问题求解步骤的描述C.要满

3、足五个基本特性D . A和C.7. 下面关于算法说法错误的是（）A. 算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的，判断题1数据结构的抽象操作的定义与具体实现有关。（ ）2数据结构是数据对象与对象中数据元素之间关系的集合。 3在顺序存储结构中，有时也存储数据结构中元素之间的关系。（ ）4数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。 5算法和程序原则上没有区别，在讨论数据结构是两者是通用的。6同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的 个数都相等。7数据的逻辑结构与数据元素本身的内容和形式无关。

4、8算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）9. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()10. 算法可以用不同的语言描述，如果用C语言或PASCAI语言等高级语言来描述，则算法 实际上就是程序了。()一，选择题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 +) 语句 1x:=x+1 ;语句 2for( j=n;j=i;j +)语句 3y:=y+1;语句 4语句1执行的频度为；语句2执行的频度为；语句3执行的频度为；语句 4执行的频度为。&在下面的程序段中，对x的赋值语句的频度为 (表示为n的函数)for(i= 1;i=n ;i+)for(j =1

6、 ;j=i;j+)for(k = 1;k=j;j+)x = x+ delta ;9. 计算机执行下面的语句时，语句s的执行次数为。for(i=l ; i=i;j-)s;10. 下面程序段的时间复杂度为 。(n1)sum=1 ;for (i=0;sum n ;i+) sum+=1;三，填空题1. 数据元素数据元素间关系 集合线性结构树形结构图状结构或网状结构33表示（又称映像） 。数学特性4逻辑特性 在计算机内部如何表示和实现 5一对一一对多 多对多6 有穷性确定性 可行性7 n+1 n n(n+3)/2 n(n+1)/281+(1+2+(1+2+3)+, +(1+2+, +n) =n(n+1)

7、(n+2)/6 O(n3)9. (n+3)(n-2)/210. O(n)四，应用题1什么是数据 ? 它与信息是什么关系 ?2什么是数据结构 ? 数据结构是研究什么内容的学科？有关数据结构的讨论涉及哪三方面 ? 3评价一个好的算法，从哪几方面考虑？4. 若将数据结构定义为一个二元组（ D, R）,说明符号D, R应分别表示什么？ 5解释算法与程序的区别？6有下列几种用二元组表示的数据结构,画出它们分别对应的逻辑图形表示,并指出它们 分别属于何种结构。（1）A=（ K , R），其中：K=a ， b， c， d，e， f ， gR=rr=a, b, b, c, c, d, d, e, e, f,

8、f, g（2）B=（ K , R）,其中：K=a ， b， c， d，e， f ， g， hR=rr=d，b， d，g， d，a， b，c， g，e， g，h， a，f（3）C=（ K , R）,其中：K=1 ， 2， 3，4， 5， 6R=rr=（1, 2） ，（2, 3），（2，4），（ 3，4），（ 3，5），（ 3，6），（ 4，5），（ 4,6） 这里的圆括号对表示两结点是双向的。7分析以下程序段的时间复杂度。（1）a=0; b=1:for （ i=2 ； i =n ； i+）s=a+b；b=a；a=S；inti , j, k；for （ i=0 ； i n; i+，for（ j=0

9、 ； j n ； j+cij=O :for (k=0; k n; k+， cij=cij+aik+bkj;8求下列算法段的语句频度及时间复杂度( 1 )for(i=1; i=n; i+)for(j =1; j =i ; j+)x=x+1;( 2 )for ( i=1;i=n;i+)for (j=1;j=i;j+)for ( k=1;k=j;k+)x=i+j-k;四，应用题1什么是信息？广义地讲，信息就是消息。宇宙三要素(物质、能量、信息)之一。它是 现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。 信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可

10、压缩、可利用、可 共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理， 例如，一个大楼中 4 部电梯在软件控制下调度和运行的状态、 一个商店中商品的在库明细表 等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体， 是描述客观事物的数、 字符、 以及所有能输入到计算机中并被计算机程序识 别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。2数据结构是指数据以及相互之间的关系。记为：数据结构= D, R 。其中， D 是某一数据对象， R 是该对象中所有数据成员之间的关系的有限集合。数据结构是一门研究在非数值计算

11、的程序设计问题中，计算机的操作对象及对象间的关 系和施加于对象的操作等的学科。有关数据结构的讨论一般涉及以下三方面的内容：( 1)数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结 构；( 2)数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称 为存储结构；( 3)施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据， 它与数据的存储不是一码事， 是与计算机存储无 关的。 因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型， 是数据的应用 视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像) ，它是依赖 于计算机的，

12、 是数据的物理视图。 数据的操作是定义于数据逻辑结构上的一组运算， 每种数 据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。3评价好的算法有四个方面。 一是算法的正确性； 二是算法的易读性； 三是算法的健壮性； 四是算法的时空效率(运行) 。4. D是数据元素的有限集合， S是D上数据元素之间关系的有限集合。5 算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性： 有穷性确定性可行性有输入有输出算法与程序的联系和区别：(1) 算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏

13、， 它将永远不会停止。因此，操作系统不是一个算法。(2) 程序中的指令必须是机器可执行的，而算法中的指令则无此限制。(3) 算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建 它的框架。(4) 算法与数据结构是相辅相承的：解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。 反之，一种数据结构的优劣由各种算法的 执行来体现。6. ( 1)A对应逻辑图形如下，它是一种线性结构。o * -o - a OCZ) V 0(2) B对应逻辑图形如下，它是一种树形结构。5#(3) C对应逻辑图形如下，它是一种图形结构。#7.(1)解：语句的频度是2;语

14、句的频度是n；语句的频度是n-1;语句的频度是n-1;语句的频度是n-1;故，该程序段的时间复杂度T (n) =2+n+3* (n-1) =4n-仁O ( n)。(2)解：语句的循环控制变量i要增加到n测试到i=n成立才会终止，故它的频度为 n+1; 语句作为语句循环体内的语句应该执行n次，但语句本身要执行 n+1次，故语句的频度是 n(n+1)；同理可得语句、和的频度分别是n2，n2 (n+1)和n3。该程序段所有语句的频度之和为：T (n) =2n3+3n2+2n+1其复杂度为 O(n3)。8(1) 分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固2定，与外循环有

15、关，因此，时间频度T(n)=1+2+3+,+n=n*(n +1)/2。有 1/4 T(n”n 1,故它的时间复杂度为O (n 2),即T(n)与n2数量级相同。(2) 分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+.+(1+2+3+,+n)。 由于有1/6 next=h B. p-next=NIL C. p-next-next=h D. p-data=-1 2下面关于线性表的叙述中,错误的是哪一个？()A. 线性表采用顺序存储，必须占用一片连续的存储单元。B. 线性表采用顺序存储，便于进行插入和删除操作。C. 线性表采用链接存储，不必占用一片连续的存储单元。D. 线性表采用

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

17、C. 带尾指针的单循环链表 D. 带头结点的双循环链表 7在带有头结点的单链中插入一个新结点时不可能修改()。A .头指针B .头结点指针域C .开始结点指针域D .其它结点指针域8双向链表中有两个指针域，llink 和 rlink ，分别指向前驱及后继，设 p 指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为()。A. p-llink=q; q-rlink=p; p-llink-rlink=q; q-llink=p-llink;B. q-llink=p-llink; p-llink-rlink=q; q-rlink=p; p-llink=q_rlink;C. q-

18、rlink=p; p-rlink=q; p-llink-rlink=q; q-rlink=p;D. p-llink-rlink=q; q-rlink=p; q-llink=p-llink; p-llink=q;9对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是()。A. head=NULL B. head宀next=NULL C . headnext=head D . head!=NULL10在顺序表中查找第i个元素的时间效率最高的算法时间复杂度是()。D . O(n)A . 0(1) B . 0( . n)C. O(log2n)11. 最好的情况下，在顺序表中按值查找一个元

19、素的算法时间复杂度是（）D . O(1)A . O(n) B . O( , n )C . O(log 2n)12. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）（1=ili nk=head Bp-li nk=NILC. p=NIL D . p= head，选择1.A2.B3.C4.A5.D6.D7.A8.D9.B10.A11 . D12.C13.C14.C15.A，判断1. 链表中的头结点仅起到标识的作用。（）2. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）3 .顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（）

20、4 .顺序存储方式只能用于存储线性结构。（）5. 线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。6. 线性表的特点是每个元素都有一个前驱和一个后继。（）7. 取线性表的第i个元素的时间同i的大小有关。（）8. 循环链表不是线性表。（）9. 线性表就是顺序存储的表。（）10. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（） 二，判断1. X2. V3. X4. X5. X6. X7. X8. X9. X10. X，填空1当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取 线性表中的元素时，应采用 存储结构。2线性表 L=(a1,a2, , ,an

21、 )用数组表示，假定删除表中任一元素的概率相同，则删除一 个元素平均需要移动元素的个数是 。3在一个长度为 n 的顺序表中第 i 个元素( 1=inext=p ； s-prior= ； p-prior=s ； =s；7. 顺序存储结构通过 表示元素之间的关系 ; 链式存储结构通过 表示元素之间的关系。8. 对于双向链表 , 在两个结点之间插入一个新结点需修改的指针共 个，单链表为个。9. 已知指针 p 指向单链表 L 中的某结点，则删除其后继结点的语句是： , 时间复杂度是。10. 带头结点的双循环链表 L 中只有一个元素结点的条件是： 。三，填空1顺序2( n-1 )/23 n-i+14O(

22、1) ，O(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);O(1) ;10 L-next-next=L四，算法设计1试写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L，X)。2试写一算法在带头结点的单链表结构上实现线性表操作LENGTH ( L)。3试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表(ai, az,an)逆置为(an, an-1,，ai)。3. 试写一算

23、法，对单链表实现就地逆置。4. 设线性表A = (ai，a?,务)，B= (bi, b2,bn),试写一个按下列规则合并A , B为线 性表 C 的算法，即使得C= (ai, bi,am ,bm ,bm+i,bn) 当 mn 时；线性表 A， B 和 C 均以单链表作存储结构， 且 C 表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值 m 和 n 均未显式存储。1LNode* Locate(LinkList L,int x)/ 链表上的元素查找 , 返回指针for(p=l-next;p&p-data!=x;p=p-next);return p;/Locate2int Length

24、(LinkList L)/ 求链表的长度for(k=0,p=L;p-next;p=p-next,k+);return k;/Length3void reverse(SqList &A)/ 顺序表的就地逆置for(i=0,j=A.length-1;ij;i+,j-) A.elemiA.elemj;/reverse4void LinkList_reverse(Linklist &L)/ 链表的就地逆置 ;为简化算法 ,假设表长大于 2p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next; / 把

25、L 的元素逐个插入新表表头q-next=p;s-next=q;L-next=s;/LinkList_reverse分析 :本算法的思想是 ,逐个地把 L 的当前元素 q 插入新的链表头部 ,p 为新表表头 5void merge1(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;p-next=q; / 将 B 的元素插入if(s)t=q-next;q-next=s; / 如 A 非空 , 将 A 的元素插入11

26、p=s;q=t;/while/merge1第三章栈和队列，选择1. 对于栈操作数据的原则是( )。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序3. 最大容量为 n 的循环队列， 队尾指针是 rear ，队头是 front ，则队空的条件是 ( )。 A. (rear+1) MOD n=frontB. rear=frontC rear+1=frontD. (rear-l) MOD n=front4 当利用大小为 n 的数组顺序存储一个栈时，假定用 top= =n 表示栈空，则向这个栈插入一 个元素时首先应执行语句修改 top 指针。A top+B top-5. 若已知一个栈的入

27、栈序列是 pi 是 ( ) 。A. i B. n-i C. n-i+16. 一个递归算法必须包括(C. top=0D. topD.)。不确定A. 递归部分 B. 终止条件和递归部分7. 执行完下列语句段后， i 值为：( ) int f(int x) return (x0) ? x* f(x-1):2); int i ; i =f(f(1);A2B. 4 C. 8 D.8. 设栈S和队列Q的初始状态为空，元素 el,素出栈后即进队列 Q若6个兀素出队的序列是 该是 ( )。A 6B. 4 C. 39. 栈和队列的共同点是( A. 都是先进先出D. 2C.e2，e2，10.11. 点，八、5迭代

28、部分 D. 终止条件和迭代部分无限递归e3, e4,e5和e6依次通过栈S,个元e4, e3,e6,e5,e1 则栈S的容量至少应)。B.都是先进后出没有共同点C. 只允许在端点处插入和删除元素 设计一个判别表达式中左，右括号是否配对出现的算法，采用( A.线性表的顺序存储结构B.用不带头结点的单链表存储队列时 则在进行删除操作时 ()。A.仅修改队头指针B.C. 队头、队尾指针都要修改 D.D.)数据结构最佳。 队列 C. 线性表的链式存储结构 D. 栈 , 其队头指针指向队头结点 , 其队尾指针指向队尾结线性表的链式存储结构仅修改队尾指针队头, 队尾指针都可能要修改1,2,3, , ,n，

29、其输出序列为 pi,p2,p3, , ,Pn,若 Pn是 n,则12.D.13递归过程或函数调用时，处理参数及返回地址，要用一种称为()的数据结构。线性表A.队列B多维数组C 栈12.D.#13. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为()。A. (rear-front+m)%m B . rear-front+1 C . (front-rear+m)%m D . (rear-front)%m14. 循环队列存储在数组A0.m中，则入队时的操作为()。A. rear=rear+1B. rear=(rear+1) mod (m-1)C. r

30、ear=(rear+1) mod m D. rear=(rear+1)mod(m+1)15. 若用一个大小为 6的数组来实现循环队列，且当前 rear和front的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A. 1 和 5 B. 2和 4 C. 4和 2 D. 5 和 1，选择1.B3.B4 B5.D6.B7.B8.C9.C10.D11.D12.C13.A14.D15.B，填空1. 是限定仅在表尾进行插入或删除操作的线性表。3. 中缀表达式3* (x+2 ) -5所对应的后缀表达式为；后缀表达式“45*32+- ”的值为。4. 顺序栈用d

31、ata1.n存储数据，栈顶指针是top,则值为x的元素入栈的操作是 5. 向一个循环队列中插入一元素时，需首先移动，然后再向所指位置新插入的元素。6. 用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=7. 用长度为n的数组顺序存储一个栈时，若用top= =n表示栈空，则表示栈满的条件为。 二，填空1. 栈3. 3 x 2 + * 5 -154. data+top=x ;5 .队尾指针写入5. (M+1) MOD N (M+1)% N ;6. top=0三，应用题1. 指出下列程序段的功能(1) void Demo1(SeqStack

32、*S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S); for (i=0, i n; i+) Push(S, arri); Demo1(2) SeqStack S1, S2, tmp;DataType x;./假设栈tmp和S2已做过初始化while ( ! StackEmpty (&S1)x=Pop(&S1) ; Push(&tmp,x);while ( ! StackEmpty (&tmp) )x=Pop( &tmp);Push( &S1,x);Push( &S2, x);(1)程序段的功能是将一栈中的元素按反序重新排列，也就是

33、原来在栈顶的元素放到栈底， 栈底的元素放到栈顶。此栈中元素个数限制在 64 个以内。(2)程序段的功能是利用tmp栈将一个非空栈si的所有元素按原样复制到一个栈s2当中去。四，算法设计题1. 回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)1 .根据提示，算法可设计为：/ 以下为顺序栈的存储结构定义#define StackSize 100 /假定预分配的栈空间最多为100个元素typedef char DataType;/假定栈元素的数据类型为字符typedef structDataTyp

34、e dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/ 判断 t 字符向量是否为回文，若是，返回 1，否则返回 0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); / 求向量长度for ( i=0; ilen/2; i+)/将一半字符入栈Push( &s, ti);while( !EmptyStack( &s)/ 每弹出一个字符与相应字符比较temp=Pop (&s);if( temp!=Si)return 0 ;/ 不等则返回 0else i+;return

35、1 ; / 比较完毕均相等则返回 115第四章串，选择1.2.3.下面关于串的的叙述中，哪一个是不正确的？（）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D 串既可以采用顺序存储，也可以采用链式存储设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为（）A.求子串 B 联接串的长度是指（）A.串中所含不同字母的个数C.串中所含不同字符的个数匹配D .求串长4.若串S= software ,其子串的数目是A. 8 B . 37 C . 36.串中所含字符的个数.串中所含非空格字符的个数（ ）.917，选择1.B2.C3. B4.B二，填空1. 空

36、格串是指，其长度等于2. 组成串的数据元素只能是 3. 个字符串中 称为该串的子串4. INDEX （ DATASTRUCTURE STR） =7.设T和P是两个给定的串，在 T中寻找等于P的子串的过程称为 ，又称P为.二，填空1. 由空格字符（ASCII值32）所组成的字符串空格个数2. 字符3. 任意个连续的字符组成的子序列4. 57.模式匹配模式串第五章数组和广义表，选择1.已知广义表L= （x,y,z）,a, （u, t , w）,从L表中取出原子项t的运算是（A. head (tail (tail ( L)B. tail(head ( head (tail ( L)#C. head

37、(tail (head (tail (L)则下面式子的值为（D. d,即（）D. head (tail(head (tail (tail (L)2. 广义表 A=(a,b,(c,d),(e,(f,g),Head(Tail(Head(Tail(Tail(A)A. (g) B.(d)C. c3. 稀疏矩阵一般的压缩存储方法有两种A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表4. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10 。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素()的起始地址相同。设每个字符占一个字

38、节。A. A8,5B. A3,10C. A5,8 D. A0,95. 对稀疏矩阵进行压缩存储目的是()。A.便于进行矩阵运算B 便于输入和输出C.节省存储空间D .降低运算的时间复杂度6. 设A是n*n的对称矩阵，将 A的对角线及对角线上方的元素以列为主的次序存放在一维数组B仁n(n+1)/2中，对上述任一元素(1 i , j n,且i wj)在B中的位置为()。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-17. AN , N是对称矩阵，将下面三角(包括对角线)以行序存储到一维数组TN ( N+1) /2中，则对任一上三角

39、元素aij 对应Tk的下标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的长度和深度分别为()D. 2和3A. 1和 1B. 1和 3C. 1和29.数组 A0.4,-1.-3,5 .7中含有兀素的个数()A. 55B.45C. 36D.1610.下面说法不正确的是()。A.广义表的:表头总是个广义表B.广义表的表尾总是个广义表C.广义表难以用顺序存储结构D.广义表可以:是一个多层次的结构，选择1.D2.D3.C4.B5.C6.B7.B8.C9.B1

40、0.A，判断1. 一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换,并把m和n的值互换，则就完成了Am*n的转置运算。()2. 从逻辑结构上看，n维数组的每个元素均属于 n个向量。()3. 稀疏矩阵压缩存储后，必会失去随机存取功能。()4. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。()5. 数组可看成线性结构的一种推广，因此与线性表一样可对它进行插入，删除操作。(6. 所谓取广义表的表尾就是返回广义表中最后一个元素。()7. 二维以上的数组其实是一种特殊的广义表。()8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。()9

41、. 若一个广义表的表头为空表，则此广义表亦为空表。()10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。()，判断1. X2. V3. V4. V5. X6. X7. V8. X9. X10. X四应用题1. 画出下列广义表的两种存储结构图(),A,(B,(C,D),(E,F)2. 设某表H如下：ABCXa1a2b1c1c2其中A,B,C为子表名，a1,a2,b1,c1,c2,x为其元素。试用广义表形式表示H,并写出运算HEAD(H和TAIL(H)函数从H中取出单元素a2的运算;(1)H(A(ai,a2),B(b J ,C(Ci, C2),x)HEAD(TAIL(HEAD

42、(H)=a 2五，算法设计1. 设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面2. 设二维数组a1.m, 1.n 含有m*n个整数。判断a中所有元素是否互不相同？输出相关信息(yes/no)。1. 本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j , i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到i=j为止。void Arran ge(i nt A,i nt n)n个整数存于数组 A中，本算法将数组中所有正数排在所有负数的前面int i=0,j=n-1,x; /用类C编写，数组下标从 0开始

43、while(ij)while(i0) i+;while(ij & Aj0) j-;if(ij) x=Ai; Ai+=Aj; Aj-=x; /交换 Ai 与 Aj/ 算法Arrange结束.算法讨论对数组中元素各比较一次，比较次数为n。最佳情况(已排好，正数在前，负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界 偶是0.n-1。空间复杂度为 0(1).2. 判断二维数组中元素是否互不相同，只有逐个比较，找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次(下面第一个循环控制变量p

44、的for循环)，然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。int JudgEqual( ing am n,i nt m,n)/判断二维数组中所有元素是否互不相同，如是，返回1;否则，返回0。for(i=0;im;i+)for(j=0;j n_1;j+) for(p=j+1;p n ;p+)/和同行其它元素比较if(aij=aip) printf(“n0”)； return(0); /只要有一个相同的，就结论不是互不相同for(k=i+1;km;k+) /和第i+1行及以后元素比较for(p=0;p n; p+) if(aij=akp) pri ntf(/

45、 for(j=0;jlchild!=NULLC . p-ltag=O D . p-ltag=1.基础知识题1 .列出右图所示二叉树的叶结点、分支结点和每个结点的层次。#使用（1）顺序表示和（2）二叉链表表示法，分别画出右图所示二叉树的存储表示。#1(1 )顺序表示1011121314151617(2)二叉链表表示012345678923#试画出3个结点的二叉树的所有不同形态。4. 设有正文AADBAACACCDACACA字符，集为A,B,C,D,设计一套二进制编码，使得上述正 文的编码最短。字符A，B, C, D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:00

46、1第七章图一，选择1 图中有关路径的定义是()。B由不同顶点所形成的序列A.由顶点和相邻顶点序偶构成的边所形成的序列C.由不同边所形成的序列D.上述定义都不是2设无向图的顶点个数为 n,则该图最多有()条边。A. n-1 B . n(n-1)/2 C . n(n+1)/2 D3. 个n个顶点的连通无向图，其边的个数至少为()。A. n-1 B. n C. n+1D4. 要连通具有n个顶点的有向图，至少需要()条边。A. n-1 B. n C. n+lD5. n个结点的完全有向图含有边的数目()。A. n*nB. n (n +1) C . n / 2D6. 求解最短路径的Floyd算法的时间复杂度为()。A. O (n)B. O ( n+c) C. O (n*n ) D. O0.nlogn ;.2n.n* (n I )(n*n*n )7. 已知有向图 G=(V,E)，其中 V=V1,V2,V3,V4