数据结构期末习题答案

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 以上都不是6一个算法应该是（）。 A程序 B问题求解步骤的描述

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

3、 DO(n2) 10连续存储设计时，存储单元的地址（）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续二，判断题1数据结构的抽象操作的定义与具体实现有关。( ) 2数据结构是数据对象与对象中数据元素之间关系的集合。3在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )4数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。5算法和程序原则上没有区别，在讨论数据结构是两者是通用的。6同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。7数据的逻辑结构与数据元素本身的容和形式无关。8算法的优劣与算法描述语言无关，但与所用计

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

6、)delta；9. 计算机执行下面的语句时，语句s的执行次数为 _ 。 for(i=l；i<n-l；i+) for(j=n;j>=i;j-) s; 10. 下面程序段的时间复杂度为_。(n>1) sum=1； for (i=0;sum<n;i+) sum+=1; 三，填空题1数据元素数据元素间关系2集合线性结构树形结构图状结构或网状结构3表示（又称映像）。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)(n+2)/6 O(n3)

7、9. (n+3)(n-2)/2 10. 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，f，g（2）B=（K，R），其中：K=a，b

8、，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；（2）inti，j，k；for（i=0；in；i+for（j=0；jn；j+cij=0；for（k=0；kn；k+cij=cij+aik+bkj；8求下列算法段的语句频度及时间复杂度（1）for(i=1;

9、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什么是信息.广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。什么是数据.因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和

10、运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。2数据结构是指数据以及相互之间的关系。记为：数据结构 = D, R 。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。有关数据结构的讨论一般涉及以下三方面的容：（1）数据成员以及它们相互之间的逻辑关系，也称为

11、数据的逻辑结构，简称为数据结构；（2）数据成员及其关系在计算机存储器的存储表示，也称为数据的物理结构，简称为存储结构；（3）施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。3评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算

12、法的健壮性；四是算法的时空效率（运行）。4D是数据元素的有限集合，S是D上数据元素之间关系的有限集合。5算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：有穷性确定性可行性有输入有输出算法与程序的联系和区别：（1）算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止。因此，操作系统不是一个算法。（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。（3）算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建它的框架。（4）算法与数据结构是相辅相承

13、的：解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。6（1）A对应逻辑图形如下，它是一种线性结构。（2）B对应逻辑图形如下，它是一种树形结构。（3）C对应逻辑图形如下，它是一种图形结构。7（1）解：语句的频度是2；语句的频度是n；语句的频度是n-1；语句的频度是n-1；语句的频度是n-1；故，该程序段的时间复杂度T（n）=2+n+3*（n-1）=4n-1=O（n）。（2）解：语句的循环控制变量i要增加到n，测试到i=n成立才会终止，故它的频度为n+1；语句作为语句循环体的语句应该执行n次，但语句本身要执行n+

14、1次，故语句的频度是n（n+1）；同理可得语句、和的频度分别是n2，n2（n+1）和n3。该程序段所有语句的频度之和为：T（n）=2n3+3n2+2n+1其复杂度为O（n3）。8（1）分析：该算法为一个二重循环，执行次数为、外循环次数相乘，但循环次数不固定，与外循环有关，因此，时间频度T(n)=1+2+3+n=n*(n+1)/2。有 1/4T(n)/n21，故它的时间复杂度为(n2), 即(n)与n2数量级相同。（2）分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+.+(1+2+3+n)。由于有1/6 T（n)/ n31，故时间复杂度为(n3) 第二章线性表一，选择1在一个以

15、 h 为头的单循环链中，p 指针指向链尾的条件是（） A. p->next=h B. p->next=NIL C. p->next->next=h D. p->data=-12下面关于线性表的叙述中，错误的是哪一个.（）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用存储，不必占用一片连续的存储单元。D线性表采用存储，便于插入和删除操作。3线性表是具有n个（）的有限序列（n>0）。A表元素 B字符 C数据元素 D数据项4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用

16、（）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表7在带有头结点的单链中插入一个新结点时不可能修改（）。A头指针 B头结点指针域 C开始结点指针域 D其它结点指针域8双向链表中有两个指针域，llink和rlink，分别指向前驱及后继

17、，设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->rlink=p; p->rlink=q; p->llink->rlink=q; q->rlink=p;D. p->

18、llink->rlink=q; q->rlink=p; q->llink=p->llink; p->llink=q;9对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL10在顺序表中查找第i个元素的时间效率最高的算法时间复杂度是（）。AO(1) BO() CO(log2n) DO(n) 11最好的情况下，在顺序表中按值查找一个元素的算法时间复杂度是（）。AO(n) BO() CO(log2n) DO(1) 12. 若长度为n的线性表采用顺序

19、存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2) 13. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)14线性表（ a1,a2,an）以方式存储时，访问第i位置元素的时间复杂性为（）。AO（i） BO（1） CO（n） DO（i-1）15非空的循环单链表head的尾结点p满足（）。Ap->link=head Bp->link=NIL Cp=NIL Dp

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

21、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )二，判断1. ×2. 3.×4. ×5. ×6.×7.×8.×9. ×10.×三，填空1当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。2线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。3在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_个元素。4对于一个具有n个结点的

22、单链表，在已知的结点*p后插入一个新结点的时间复杂度为_,在给定值为x的结点后插入一个新结点的时间复杂度为_。5在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_、_、_、_。6. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：s->next=p； s->prior= _；p->prior=s；_=s；7.顺序存储结构通过_表示元素之间的关系;链式存储结构通过_表示元素之间的关系。8. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _个，单链表为_个。9. 已知指针p指向单链表L中的某结点，则删除其后

23、继结点的语句是：_,时间复杂度是。10. 带头结点的双循环链表L中只有一个元素结点的条件是：。三，填空1顺序2（n-1）/2 3 n-i+14O(1)，O(n) 5f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;6p->prior s->prior->next7物理上相邻指针84 29u=p->next; p->next=u->next; free(u); O(1) ; 10L->next->next=L 四，算法设计1试写一算法在带头结点的单链

24、表结构上实现线性表操作LOCATE（L，X）。2试写一算法在带头结点的单链表结构上实现线性表操作LENGTH（L）。3试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2, ,an）逆置为（an, an-1, ,a1）。4 试写一算法，对单链表实现就地逆置。5 设线性表A =（a1， a2， ,an），B=（b1, b2, ,bn），试写一个按下列规则合并A，B为线性表C的算法，即使得C=（a1, b1, , am ,bm ,bm+1, ,bn）当m<=n时；或者 C=（a1, b1, , an ,bn ,an+1, ,an）当m.>n时；线性表A，B和C均以

25、单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。1LNode* Locate(LinkList L,int x)/链表上的元素查找,返回指针for(p=l->next;p&&p->data!=x;p=p->next);return p;/Locate 2int Length(LinkList L)/求链表的长度for(k=0,p=L;p->next;p=p->next,k+);return k;/Length3void reverse(SqList &A)/顺序表的就地逆置for(i=0,j=

26、A.length-1;i<j;i+,j-)A.elemi<->A.elemj;/reverse 4void 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; /把L的元素逐个插入新表表头q->next=p;s->next=q;L->next=s;/LinkList_reverse分析:本算

27、法的思想是,逐个地把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的元素插入p=s;q=t;/while/merge1第三章栈和队列一，选择1. 对于栈操作数据的原则是

28、（）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序3. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front4当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一个元素时首先应执行语句修改top指针。Atop+ Btop- Ctop=0 Dtop5. 若已知一个栈的入栈序列是1,2,3,n，其输出序列为p1,p2,p3，pN,若pN是n，则pi是( )。 A. i

29、B. n-i C. n-i+1 D. 不确定6. 一个递归算法必须包括（）。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分7. 执行完下列语句段后，i值为：（） int f(int x) return (x>0) " x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 无限递归8. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。A 6 B. 4 C. 3

30、D. 29. 栈和队列的共同点是（）。A. 都是先进先出 B. 都是先进后出C. 只允许在端点处插入和删除元素 D. 没有共同点10. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈11. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。A仅修改队头指针 B. 仅修改队尾指针C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改12. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A队列 B多维数组 C栈D.

31、 线性表13. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m14. 循环队列存储在数组A0.m中，则入队时的操作为（）。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 15. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，

32、再加入两个元素后，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. 顺序栈用data1.n存储数据，栈顶指针是top,则值为x的元素入栈的操作是_。5向一个循环队列中插入一元素时，需首先移动，然后再向所指位置新插入的元素。6用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下

33、标围循环，可采用的表达式是： M= _7用长度为n的数组顺序存储一个栈时，若用top= =n表示栈空，则表示栈满的条件为。二，填空1栈33 x 2 + * 5 - 154data+top=x；5 队尾指针写入6(M+1) MOD N (M+1)% N；7top=0三，应用题1指出下列程序段的功能(1) void Demo1(SeqStack *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;D

34、ataType 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)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以。(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。四，算法设计题1回

35、文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 1 根据提示，算法可设计为：/以下为顺序栈的存储结构定义*define StackSize 100 /假定预分配的栈空间最多为100个元素typedef char DataType;/假定栈元素的数据类型为字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判

36、断t字符向量是否为回文，若是，返回1，否则返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量长度for ( i=0; i<len/2; i+)/将一半字符入栈Push( &s, ti);while( !EmptyStack( &s)/ 每弹出一个字符与相应字符比较temp=Pop (&s);if( temp!=Si)  return 0 ;/ 不等则返回0else i+;return 1 ; / 比较完毕均相等则返回 1第四章串一，选择1下面关于串的的叙述中

37、，哪一个是不正确的.（）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储2设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A求子串 B联接 C匹配 D求串长3串的长度是指（）A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数4若串S=software,其子串的数目是（）。A8 B37 C36 D9一，选择1.B2.C3B4.B二，填空1空格串是指_，其长度等于_。2组成串的数据元素只能是_。3一个字符串中_称为该串的子串。4INDEX（DATASTRUC

38、TURE，STR）=_。7设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_，又称P为_。二，填空1由空格字符（ASCII值32）所组成的字符串空格个数2字符3任意个连续的字符组成的子序列45 7模式匹配模式串第五章数组和广义表一，选择1. 已知广义表L=（x,y,z），a，（u，t，w），从L表中取出原子项t的运算是（）。A. head（tail（tail（L） B. tail（head（head（tail（L）C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）2. 广义表A=(a,b,(c,d),(e,(f,g),则

39、下面式子的值为（）。Head(Tail(Head(Tail(Tail(A)A. (g) B. (d) C. c D. d3.稀疏矩阵一般的压缩存储方法有两种,即（）A二维数组和三维数组 B三元组和散列C三元组和十字链表 D散列和十字链表4. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。A. A8,5 B. A3,10 C. A5,8 D. A0,95. 对稀疏矩阵进行压缩存储目的是（）。A便于进行矩阵运算 B便于输入和输出C节省存储空间 D降低运

40、算的时间复杂度6. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B1.n(n+1)/2中，对上述任一元素aij(1i，jn，且ij)在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中，则对任一上三角元素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的长度和深

41、度分别为（）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 9. 数组A0.4,-1.-3,5.7中含有元素的个数（）。A 55 B45 C 36 D1610. 下面说法不正确的是( )。A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构一，选择1.D2.D3.C4.B5.C6.B7.B8.C9.B10.A二，判断1一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（）2. 从逻辑结构上看，n维数组的每个元素均属于n个向量

42、。（）3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（）4. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（）5. 数组可看成线性结构的一种推广，因此与线性表一样可对它进行插入，删除操作。（）6. 所谓取广义表的表尾就是返回广义表中最后一个元素。（）7. 二维以上的数组其实是一种特殊的广义表。（）8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（）9. 若一个广义表的表头为空表，则此广义表亦为空表。（）10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（）二，判断1.×2.3.4. 5.×6. ×7.

43、8.×9.×10.×四应用题1. 画出下列广义表的两种存储结构图(),A,(B,(C,D),(E,F)。2. 设某表H如下：ABCXa1a2 b1 c1c2其中A,B,C为子表名，a1,a2,b1,c1,c2,x为其元素。试用广义表形式表示H,并写出运算HEAD(H)和TAIL(H) 函数从H中取出单元素a2的运算；（1）H(A(a1,a2）,B(b1）,C(c1，c2）,x）HEAD(TAIL(HEAD(H)=a2五，算法设计1设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面2. 设二维数组a1.m, 1.n 含有m*n 个整数。判

44、断a中所有元素是否互不相同"输出相关信息(yes/no)。1.本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。void Arrange(int A,int n) /n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面 int i=0,j=n-1,x; /用类C编写，数组下标从0开始 while(i<j)while(i<j && Ai>0) i+;while(i<j && Aj<0)

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

46、k和p的二层for循环。int JudgEqual(ing amn,int m,n) /判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。for(i=0;i<m;i+) for(j=0;j<n-1;j+) for(p=j+1;p<n;p+) /和同行其它元素比较 if(aij=aip) printf(“no”); return(0); /只要有一个相同的，就结论不是互不相同 for(k=i+1;k<m;k+) /和第i+1行及以后元素比较 for(p=0;p<n;p+) if(aij=akp) printf(“no”); return(0); / f

47、or(j=0;j<n-1;j+)printf(yes”); return(1); /元素互不相同/算法JudgEqual结束第6章树和二叉树一选择1算术表达式a+b*（c+d/e）转为后缀表达式后为（）Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+2. 在下述结论中，正确的是（）只有一个结点的二叉树的度为0; 二叉树的度为2；二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A B C D3具有10个叶结点的二叉树中有（）个度为2的结点，4A8 B9 C10 Dll4. 有n个叶子的哈夫曼树的结点总数为（）。A不确定

48、 B2n C2n+1 D2n-15已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。ACBEFDA B FEDCBA C CBEDFA D不定6已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（）。 Aacbed Bdecab Cdeabc Dcedba 7在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A都不相同B完全相同 C先序和中序相同，而与后序不同 D中序和后序相同，而与先序不同8n个结点的线索二叉树上含有的线索数为（）A2n Bnl Cnl Dn 9深度为k的二叉树，结点数最多

49、有（） A2kB2k -1 C2k-1 D2k-1-110判断线索二叉树中某结点p有左孩子的条件是（） Ap!=NULL Bp->lchild!=NULL Cp->ltag=0 Dp->ltag=1二基础知识题1 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。2 使用（1）顺序表示和（2）二叉链表表示法，分别画出右图所示二叉树的存储表示。（1）顺序表示01234567891011121314151617（2）二叉链表表示试画出3个结点的二叉树的所有不同形态。4.设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。字符A，B，C，D出现