数据结构习题1217

1、选择题（ ）由某一数据对象和该对象中各个成员之间的关系组成。依据所有数据成员之间关系的不同，（ ）分为两大类：（ ）和（ ）。在（ ）中的各个数据成员依次排列在一个线性序列中；（ ）的各个数据成员不再保持在一个线性序列中，每个数据成员可能与零个或多个其他数据成员发生联系。根据视点的不同，数据结构分为数据的（ ）和（ ）。（ ）是面向问题的，（ ）是面向计算机的。绪论练习绪论练习A：数据结构B：线性结构 C：非线性结构D：逻辑结构E：存储结构A AA AB BC CB BC CD DE ED DE E判断题数据元素是数据的最小单位。数据结构是数据对象与对象中数据元素之间关系的集合。数据结构是具有

2、结构的数据对象。数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。算法和程序原则上没有区别，在讨论数据结构时二者是通用的。从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。数据的逻辑结构与数据元素本身的内容和形式无关。FTFTFTT填空题算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、（ ）、有穷性和可执行性等特性。算法效率的度量分为（ ）和（ ）。（ ）主要通过在算法的某些部位插装时间函数来测定算法完成某一规定功能所需要的时间。而（ ）不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂度。A：确定性 B：事后测

3、量C：事前估计A AB BB BC CC C有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示。A=（K,R）其中K=a,b,c,d,R= C=（K,R）其中K=1,2,3,4,5,6,R=,B=（K,R）其中K=a,b,c,d,e,f,g,h,R=,选择题一个数据元素ai与 的表示等价。A.*(a+i) B.a+i C.*a+i D.&a+i对于两个函数，若函数名相同，但只是 不同则不是重载函数。A.参数类型 B.参数个数 C.函数类型 若需要利用形参直接访问实参，则应把形参变量说明为 参数。A.指针 B.引用 C.值下面程序的时间复杂度为 。For(int i=0;im

4、;i+)for (int j=0;jn;j+)aij=I*j;A.O(m2) B. O(n2) C.O(m*n) D.O(m+n)ACBC执行下面程序，执行S语句的次数为 。For(int i=1;i=n;i+)for (int j=1;ji;j+)S;A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 下面算法的时间复杂度为 。int if f(unsigned int n) if (n=0|n=1) return 1;else return n*f(n-1) A. O(1) B. O(n2) C.O(n) D.O(n!)下面程序中s=s+p语句执行的次数为 ，p*=j语

5、句执行的次数为 ，该程序段T(n)为 。int i=0,s=0;while(+i=n)int p=1;for (int j=1;j=i;j+) p*=j;s=s+p;DCA. n2B. nC. n(n+1)D.n(n+1)/2BDE. O(n2)F. O(n)G. O(n!)H. O(1)E第二章 线性表线性表（Linear list）是最简单且最常用的一种数据）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此

6、外，每一个数据元素均有一个直接前驱和数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。通过本章的学习，大家应能掌一个直接后继数据元素。通过本章的学习，大家应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。算以及实现算法。【知识点知识点】线性表、顺序表、链表线性表、顺序表、链表2.1 线性表及逻辑结构线性表及逻辑结构2.2 线性表的顺序存储线性表的顺序存储2.3 线性表的链式存储线性表的链式存储2.4 链式存储结构的应用链式存储结构的应用2.5 小结小结2.6 练习练习 线性表：线性表：一个线性表是n0个数据

7、元素a0，a1，a2，an-1的有限序列。 线性表的顺序存储结构：线性表的顺序存储结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。 线性表的链式存储结构：线性表的链式存储结构：线性表的链式存储结构就是用一组任意的存储单元结点（可以是不连续的）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。 单链表：单链表：单链表（Linear Linked List）是指链表中的每一个结点中只包含一个指针域指向直接后继。本章小结本章小结循环链表：循环链表：循环链表(Circular Li

8、nked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结点。双向链表：双向链表：双向链表中，在每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。除上述基本概念以外，学生还应该了解：线性表的基本操作（初始化、插入、删除、存取）、顺序存储结构的表示、线性表的链式存储结构的表示、一元多项式Pn(x)，掌握顺序存储结构（初始化、插入操作、删除操作）、单链表（单链表的初始化、单链表的插入、单链表的删除）。一、判断题线性表的逻辑顺序与物理顺序总是一致的。线性

9、表的顺序存储表示优于链式存储表示。线性表若采用链式存储表示。时所有存储单元的地址可连续可不连续。每种数据结构都应具备三种基本运算：插入、删除和搜索。线性表的特点是每个元素都有一个前驱和一个后继。1.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。 F FF FT TT T练习练习F FF F二、填空题线性表（ a1,a2,an）有两种存储结构：（A）和（B）。（A）存储密度较大，（B）存储利用率较高，（A）可随机存取，（B）不可随机存取，（B）插入和删除操作比较方便。在单链表中，删除指针p所指结点的后继结点的语句是：（）带头结点的单循环链表Head的判空条件是（）。1.画出下列数据

10、结构的图示：顺序表 单链表 双链表 循环链表A：顺序存储结构B：链式存储结构pnext=pnextnextHeadnext=Head在一个长度为n的顺序表中第i个元素（1=inext-next=L 2p-next!=null 顺序 指针三、选择题设单链表中结点的结构为（data,link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？A：s-link=p-link; p-link=s;B: q-link=s;s-link=p;C: p-link=s-link;s-link=p;D: p-link=s;s-link=q;答案：答案：B B

11、设单链表中结点的结构为（data,link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？A：s-link=p; p-link=s;B：s-link=p-link;p-link=s;C：s-link=p-link;p=s;D：p-link=s;s-link=p;答案：答案：B B设单链表中结点的结构为（data,link）。若想摘除结点*p的直接后继，则应执行下列哪一个操作？A：p-link=p-link-link;B： p=p-link; p-link=p-link-link;C：p-link=p-link;D：p=p-link-link;答案：答案：A

12、A设单链表中结点的结构为（data,link）。且rear是指向非空的带表头结点的单循环链表的尾结点的指针，若想删除链表第一个结点，则应执行下列哪一个操作？A：s=rear; rear=rear-link;free(s);B：rear=rear-link; free(rear);C： rear=rear-link-link; free(rear) ;D： s=rear-link-link; rear-link-link=s-link; free(s);答案：答案：D D设双向循环链表中结点的结构为(data,lLink,rLink),且不带头结点。若想在指针p所指结点之后插入指针s所指结点，则

13、应执行下列哪一个操作？A：p-rLink=s; s-lLink=p; p-rLink-lLink=s; s-rLink=p-rLink;B： p-rLink=s;p-rLink-lLink=s; s-lLink=p; s-rLink =p-rLink;C：s-lLink=p; s-rLink=p-rLink; p-rLink=s; p-rLink-lLink=s;D： s-lLink=p;s-rLink=p-rLink; p-rLink-lLink=s;p-rLink=s;答案：答案：D D若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间

14、。 A顺序表B双链表C带头结点的双循环链表D单循环链表 A A在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。A(p-llink)-rlink:=p-rlink;(p-rlink)-llink:= p-llink;Bp- llink:=(p-llink)-llink;(p-llink)- rlink:=p;C(p-rlink)-llink:=p;p-rlink:=(p-rlink)- rlinkDp-rlink:=(p-llink)-llink;p-llink:=(p- rlink)-rlink; A A第三章 栈和队列从数据结构上看，栈和队列也是线性表，不过是两种特从数据结构上看，

15、栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。通过本章的学习，大家应能掌握栈和队列的的线性表。通过本章的学习，大家应能掌握栈和队列的逻辑结构和存储结构，以及栈和队列的基本运算以及实逻辑结构和存储结构，以及栈和队列的基本运算以及实现算法。现算法。【知识点知识点】栈、队列栈、队列3.0 课前思考课前思考3.1 栈栈

16、3.2 栈的应用栈的应用3.3 队列队列 3.4 队列的应用队列的应用3.5 小结小结 2.6 练习练习本章主要介绍了如下一些基本概念：本章主要介绍了如下一些基本概念：栈：是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。因此，栈也被称为“后进先出”的线性表。栈的顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的各个数据元素，称为栈的顺序存储结构。双向栈：使两个栈共享一维数组stackMAXNUM，利

17、用栈的“栈底位置不变，栈顶位置动态变化”的特性，将两个栈底分别设为-1和MAXNUM，而它们的栈顶都往中间方向延伸的栈称为双向栈。本章小结本章小结栈的链式存储结构：栈的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储栈中的数据元素，这种结构的栈简称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。队列：队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头(front)。队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列

18、，因而也是最后出队列。因此，队列也被称为“先进先出”表。队列的顺序存储结构：利用一组地址连续的存储单元依次存放队列中的数据元素，称为队列的顺序存储结构。重点是循环队列。其中：约定初始化建空队列时， front=rear=0，在非空队列中，头指针始终指向队头元素，而尾指针指向队尾元素的“下一个”位置。队列的链式存储结构：队列的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储队列中的数据元素，这种结构的队列称为链队列。在一个链队列中需设定两个指针(头指针和尾指针)分别指向队列的头和尾。除上述基本概念以外，学生还应该了解：栈的基本操作（初始化、栈的非空判断、入栈、出栈、取栈元素、置栈空操作

19、）、栈的顺序存储结构的表示、栈的链式存储结构的表示、队列的基本操作（初始化、队列非空判断、入队列、出队列、取队头元素、求队列长度）、队列的顺序存储结构、队列的链式存储结构，掌握顺序栈（入栈操作、出栈操作）、链栈（入栈操作、出栈操作）、顺序队列（入队列操作、出队列操作）、链队列（入队列操作、出队列操作）等。一、判断题两个栈共用静态存储空间，对头使用也存在空间溢出问题。 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。栈与队列是一种特殊操作的线性表。 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1 。若输

20、入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 栈和队列都是线性表，只是在插入和删除时受到了一些限制。 1.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。T TT TT T练习练习T TF FF FT TT T二、填空题栈是（ ）的线性表，其运算遵循（）的原则。（）是限定仅在表尾进行插入或删除操作的线性表。设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是（ ）

21、，而栈顶指针值是（） H。设栈为顺序栈，每个元素占4个字节。 1.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为（ ） 。 后进先出23100C 操作受限 栈 SSSS （）又称作先进先出表。 区分循环队列的满与空，只有两种方法，它们是（ ）和（ ）。设循环队列用数组A1.M表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为 （） 。 表达式求值是（ ） 应用的一个典型例子。循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是（ ）。 队列 牺牲一个存储单元 设标

22、记 （TAIL+1）MOD M=FRONT 栈 （rear-front+m）% m三、选择题对于栈操作数据的原则是（ ）。 A. 先进先出B. 后进先出C. 后进后出D. 不分顺序 B B一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i B B有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？( ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 C C在作进栈运算时,应先判别栈是否(),在作退栈

23、运算时应先判别栈是否()。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为()。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ()分别设在这片内存空间的两端,这样,当()时，才产生上溢。 : A.空 B. 满 C. 上溢 D.下溢 : A. n-1 B. n C. n+1 D.n/2 : A. 长度 B. 深度 C. 栈顶 D.栈底 : A. 两个栈的栈顶同时到达栈空间的中心点。 B. 其中一个栈的栈顶到达栈空间的中心点。 C. 两个栈的栈顶在栈空间的某一位置相遇。 D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底。 答案：答案：

24、 B B A A B B D DC C设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 D D表达式3* 2(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中为乘幂 。 A. 3,2,4,1,1；#*(+*- B. 3,2,8；#*- C. 3,2,4,2,2；#*(- D. 3,2,8；#*(- D D用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针B. 仅修改尾指针C. 头、尾指针都要修改 D. 头、尾指针

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

26、，再加入两个元素后，rear和front的值分别为多少？( )A. 1和 5 B. 2和4C. 4和2 D. 5和1 B B栈的特点是（）,队列的特点是（）,栈和队列都是（）。若进栈序列为1,2,3,4 则（）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（）是一个出队列序列。栈和队列的共同点是（）。: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进: A.顺序存储的线性结构 B.链式存储的线性结构C.限制存取点的线性结构 D.限制存取点的非线性结构: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F

27、. 1,2,3,4 G. 1,3,2,4 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素D. 没有共同点 答案：答案： B B A A C C C CF F C C四、写出下列程序段的输出结果四、写出下列程序段的输出结果1、 （栈的元素类型（栈的元素类型SElemTypeSElemType为为CharChar）Void main()stack s;char x,y;Initstack(s);x=c;y=k;Push(s,x);Push(s,a);Push(s,y);Pop(s,x);Push(s,t);Push(s,x);Pop(s,x);Push(s,s);whi

28、le(!StackEmpty(s) Pop(s,y);Printf(y);Printf(x);输出结果：输出结果：stackstack2、 （队列中的元素类型（队列中的元素类型QElemTypeQElemType为为CharChar）Void main()Queue Q;InitQueue(Q);char x=e,y=c;EnQueue(Q,h); EnQueue(Q,r); EnQueue(Q,y);DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,a);while(!QueueEmpty(Q) DeQueue(Q,y); Printf(

29、y);Printf(x);输出结果：输出结果：charchar五、简述算法的功能五、简述算法的功能1 1、（栈的元素类型、（栈的元素类型SElemTypeSElemType为为intint）Status sf1(stack s,int e)stack t;int d;initstack(T);while(!stackEmpty(S)Pop(S,d);if (d!=e) Push(T,d);while(!StackEmpty(T) Pop(T,d);Push(S,d);利用栈利用栈T T辅助将栈辅助将栈S S中所有值为中所有值为e e的数据的数据元素删除去。元素删除去。2 2、（栈和队列的元素类

30、型均为、（栈和队列的元素类型均为intint）void sf2(Queue &Q)stack S;int d;initstack(S);while(! QueueEmpty(Q)DeQueue(Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d);EnQueue(Q,d); 利用栈利用栈S S作辅助，将队列作辅助，将队列Q Q中的数据元中的数据元素进行逆置。素进行逆置。第四章 串在计算机的各方面应用中，非数值处理问题的应用越来在计算机的各方面应用中，非数值处理问题的应用越来越多。在早期的程序设计语言中，串仅作为输入和输出越多。在早期的程序设计语言中

31、，串仅作为输入和输出的常量出现。随着计算机应用的扩展，需要在程序中进的常量出现。随着计算机应用的扩展，需要在程序中进行对行对串串的操作，如在事务处理系统中，用户的姓名和的操作，如在事务处理系统中，用户的姓名和地址及货物的名称、规格等也是字符串数据。地址及货物的名称、规格等也是字符串数据。字符串一般简称为串，可以将它看作是一种特殊的线性字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符表，这种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。在一般线性表的基本操作串的数据对象约束为字符集。在一般线性表的基本操作中，大多以中，大多以“单

32、个元素单个元素”作为操作对象，而在串中，则作为操作对象，而在串中，则是以是以“串的整体串的整体”或一部分作为操作对象。因此，一般或一部分作为操作对象。因此，一般线性表和串的操作有很大的不同。本章主要讨论串的基线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。本概念、存储结构和一些基本的串处理操作。【知识点知识点】串的类型定义、串的存储表示、串匹配串的类型定义、串的存储表示、串匹配4.1 串的基本概念串的基本概念 4.2 串的存储结构串的存储结构 4.3 串的基本运算及其实现串的基本运算及其实现 4.4 模式匹配模式匹配4.5 串的应用串的应用 4.6 小结

33、小结 4.7 练习练习本章主要介绍了如下一些基本概念：本章主要介绍了如下一些基本概念：串：串（或字符串）（String）是由零个或多个字符组成的有限序列。主串和子串：一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串。串的静态存储结构：类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储结构。串的链式存储结构：类似于线性表的链式存储结构，采用链表方式存储串值字符序列的存储方式称为串的顺序存储结构。堆存储结构：用一组空间足够大的、地址连续的存储单元存放串值字符序列，但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构。

34、本章小结本章小结除上述基本概念以外，学生还应该了解串的基本运算（字符串拷贝（赋值、字符串的联接、求字符串的长度、子串的查询、字符串的比较）、串的静态存储结构的表示、串的链式存储结构的表示、串的堆存储结构的表示，能在各种存储结构方式中求字符串的长度、能在各种存储结构方式中利用C语言提供的串函数进行操作。一、判断题如果两个串含有相同的字符，则说明它们相等。如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。设有两个串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中的位置的算法称为匹配。单引号和双引号都可做为串的定界符。单引号是串的一部分。1.设s= ，t= ，则s

35、=tF FF FT T练习练习F FF FF F二、选择题串是（ ）。 A.少于一个字母的序列 B.任意个字母的序列 C.不少于一个字母的序列 D.有限个字母的序列D D串的长度是（ ）。 A.串中不同字母的个数B.串中不同字符的个数 C.串中所含字符的个数，且大于0D.串中所含字符的个数 D D设有两中串p和q，求q在p中首次出现的位置的运算( ）。A. 连接 B.模式匹配C.求子串D. 求串长B B串的联结运算不满足（ ）。 A.分配律B.交换律C.结合律B B设字符串s1=ABCDEFG,s2=PQRST,而T，sub1，sub2为空串，则运算S=Concation(T,SubStrin

36、g(sub1,s1,2,SubLength(s2),SubString(sub2,s1,SubLength(s2),2)后的串T的值为（ ）。 A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEFE.BCQR D D三、填空题1.设s=I am a student,t=good,q=worker。则：S t r L e n g t h ( s ) = （ ） ，S u b S t r i n g ( s , 8 , 7 ) = （） ，BFIndex(s,a)= （ ）, BFIndex(s,t)=（ ）, Concation (SubString (s,6,2),Concati

37、on(t, SubString(s,7,8)=（ ）,Replace(s,student,q)=（ ）studenta good studentI am a worker14 3 0 2.已知下列字符串：a=this,f=a sample, c=good,d=ne,b=,g=is。则：s=Concation(a,Concation(SubString(f,2,7), Concation(b,SubString(a,3,2)= （ ） t=Replace(f,SubString(f,3,6),c)=（ ） u=Concation(SubString(c,3,1),d)= （ ） v=Concat

38、ion(s,Concation(b,Concation(t,Concation(b,u)=（ ） StrLength(s)=（ ），BFIndex(v,g)=（）, BFIndex(u,g)=（）。a good143s=this sample is one This sample is a good one0四、写出下列程序段的输出结果写出下列程序段的输出结果Void demonstrate()StrAssign(s,this is a book);Replace(s,SubString(s,3,7),ese are);StrAssign(t,Concation(s,s);StrAssign(

39、u,xyxyxyxyxyxy);StrAssign(v,SubString(u,6,3);StrAssign(w,w);printf(t=,t,v=,v,u=,Replace(u,v,w);/demonstrate输出结果：输出结果：t=these are books,v=yxy,u=xwxwxw第五章第五章 数组和广义表数组和广义表本章主要介绍数组的概念及在计算机中的存放，特殊矩本章主要介绍数组的概念及在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。通过本章学习，要求掌握如下内容其相关运算的实现。通过本

40、章学习，要求掌握如下内容:1数组的定义及在计算机中的存储表示；数组的定义及在计算机中的存储表示；2对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式；中的压缩存储表示及地址计算公式；3稀疏矩阵的三元组表示；稀疏矩阵的三元组表示；4广义表存储结构表示。广义表存储结构表示。【知识点知识点】数组的类型定义、数组的存储表示、特殊矩数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、稀疏矩阵的压缩存储表示方法阵的压缩存储表示方法、稀疏矩阵的压缩存储表示方法5.1 数组的基本概念数组的基本概念 5.2 数组的存储结构数组的存储

41、结构 5.3 特殊矩阵及其压缩存储特殊矩阵及其压缩存储 5.4 稀疏矩阵稀疏矩阵5.5 广义表广义表 5.6 小结小结 5.7 练习练习1多维数组在计算机中有两种存放形式多维数组在计算机中有两种存放形式:行优先和列优先。行优先和列优先。2行优先规则是左边下标变化最慢，右边下标变化最快，行优先规则是左边下标变化最慢，右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。右边下标变化一遍，与之相邻的左边下标才变化一次。3列优先规则是右边下标变化最慢，左边下标变化最快，列优先规则是右边下标变化最慢，左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。左边下标变化一遍，与之相

42、邻的右边下标才变化一次。4对称矩阵关于主对角线对称。为节省存储单元，可以进对称矩阵关于主对角线对称。为节省存储单元，可以进行压缩存储，对角线以上的元素和对角线以下的元素可以行压缩存储，对角线以上的元素和对角线以下的元素可以共用存储单元，故共用存储单元，故n n的对称矩阵只需的对称矩阵只需 个存储单元即可。个存储单元即可。5三角矩阵有上三角矩阵和下三角矩阵之分，为节省内存三角矩阵有上三角矩阵和下三角矩阵之分，为节省内存单元，可以采用压缩存储，单元，可以采用压缩存储，n n的三角矩阵进行压缩存储时的三角矩阵进行压缩存储时，只需，只需+1个存储单元即可。个存储单元即可。6稀疏矩阵的非零元排列无任何规

43、律，为节省内存单元，稀疏矩阵的非零元排列无任何规律，为节省内存单元，进行压缩存储时，可以采用三元组表示方法，即存储非零进行压缩存储时，可以采用三元组表示方法，即存储非零元素的行号、列号和值。若干个非零元有若干个三元组，元素的行号、列号和值。若干个非零元有若干个三元组，若干个三元组称为三元组表。若干个三元组称为三元组表。7广义表为线性表的推广，里面的元素可以为原子，也可广义表为线性表的推广，里面的元素可以为原子，也可以为子表，故广义表的存储采用动态链表较方便。以为子表，故广义表的存储采用动态链表较方便。本章小结本章小结一、判断题数组是同类型值的集合。数组是一组相继的内存单元。数组是一种复杂的数据

44、结构，数组元素之间的关系，既不是线性的，也不是树型的。插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。数组的存储方式分为顺序和链式两种。使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间。广义表是由零或多个单元素或子表所组成的有序列，所以广义表可能为空表。1.线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。T TT TT T练习练习F FF FF FT TT T二、选择题一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（ ）。 A.n*nB.n*n/2C.n(n+1)/2D.(n+1)*(n+1)/2E.(n-

45、1)*n/2F.n(n-1)C C在二维数组A79中，假定每个数据元素占4个存储单元， A00的存储位置（基地址）为100，则A56的存储位置为（ ）。 A.232B.151C.204D.304D D设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（ ）。 A.13 B.33 C.18 D.40B二维数组a的每个元素是由6个字符组成的串，行下标i的范围从0-8，列下标j的范围是从1-10。存放a至少需要( ）个字节。 A.90 B.180 C.240D.270E.540A的第8列和第5行共占（ ）字节。

46、A.108B.114 C.54D.60E.150若a按行存放，元素a8,5的起始地址与当a按列存放的元素( ）的起始地址一致。A.a8,5 B. a3,10C.a5,8D. a0,9E EA AB B已知广义表LS=（a,(b,c,c),e）,运用HEAD和T A I L 函 数 取 出 L S 中 的 单 元 素 b 的 运 算 是（ ）。 A.HEAD(HEAD(LS) B.TAIL(HEAD(LS)C.HEAD(HEAD(TAIL(LS) D.HEAD(TAIL(LS)C C已知广义表A=(a,b,c),(d,e,f),从A中取出单元素e的运算是（ ）。 A.TAIL(HEAD(A)B.

47、HEAD(TAIL(A) C.HEAD(TAIL(TAIL(HEAD(A)D.HEAD(TAIL(HEAD(TAIL(A)E.HEAD(TAIL(TAIL(A)D D设广义表LS=（a,b,LS）, 其长度是（ ），其深度为（ ）。 A. B.3C.2 D.5B B下列广义表为线性表的是（ ）。 A.E(a,(b,c) B.E(a,E)C.E(a,b)D.E(a,L()A AC C第六章第六章 树和二叉树树和二叉树本章主要介绍树和二叉树的概念，以及它们的存储结构本章主要介绍树和二叉树的概念，以及它们的存储结构和相应的算法，二叉树的各种遍历，树和森林与二叉树和相应的算法，二叉树的各种遍历，树和森

48、林与二叉树之间的转换等。通过本章学习，要求掌握如下内容之间的转换等。通过本章学习，要求掌握如下内容:1.领会树和二叉树的类型定义，理解树和二叉树的结构差领会树和二叉树的类型定义，理解树和二叉树的结构差别。别。2.熟记二叉树的主要特性，并掌握它们的证明方法。熟记二叉树的主要特性，并掌握它们的证明方法。3.熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。法实现二叉树的其它操作。4.理解二叉树的线索化过程以及在中序线索化树上找给定理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。结点的前驱和后继的方法。5.

49、熟练掌握二叉树和树的各种存储结构及其建立的算法。熟练掌握二叉树和树的各种存储结构及其建立的算法。6.学会编写实现树的各种操作的算法。学会编写实现树的各种操作的算法。7.了解最优树的特性，掌握建立最优树和赫夫曼编码的方了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。法。【知识点知识点】树的类型定义、二叉树的类型定义、二叉树树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码它操作的实现

50、、最优树和赫夫曼编码第六章第六章 树和二叉树树和二叉树6.0 课前思考课前思考6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 线索二叉树线索二叉树6.4 树、森林和二叉树的关系树、森林和二叉树的关系6.5 哈夫曼树哈夫曼树6.6 小结小结6.7 练习练习1在这一章讨论了树和二叉树两种数据类型的在这一章讨论了树和二叉树两种数据类型的定义以及它们的实现方法。树是以分支关系定义定义以及它们的实现方法。树是以分支关系定义的层次结构，结构中的数据元素之间存在着的层次结构，结构中的数据元素之间存在着一一对多对多的关系，因此它为计算机应用中出现的具的关系，因此它为计算机应用中出现的具有层次关系或

51、分支关系的数据，提供了一种自然有层次关系或分支关系的数据，提供了一种自然的表示方法。如用树描述人类社会的族谱和各种的表示方法。如用树描述人类社会的族谱和各种社会组织机构。在计算机学科和应用领域中树也社会组织机构。在计算机学科和应用领域中树也得到广泛应用，例如在编译程序中，用树来表示得到广泛应用，例如在编译程序中，用树来表示源程序的语法结构等。源程序的语法结构等。2二叉树是和树不同的另一种树型结构，它有二叉树是和树不同的另一种树型结构，它有明确的左子树和右子树，因此当用二叉树来描述明确的左子树和右子树，因此当用二叉树来描述层次关系时，其层次关系时，其左孩子左孩子表示表示下属关系下属关系，而，而右

52、孩子右孩子表示的是表示的是同一层次的关系同一层次的关系。本章小结本章小结3树和二叉树的遍历算法是实现各种操作的基础。对非树和二叉树的遍历算法是实现各种操作的基础。对非线性结构的遍历需要选择合适的搜索路径，以确保在这条线性结构的遍历需要选择合适的搜索路径，以确保在这条路径上可以访问到结构中的所有数据元素，并使每一个数路径上可以访问到结构中的所有数据元素，并使每一个数据元素只被访问一次。由于树和二叉树是层次分明的结构，据元素只被访问一次。由于树和二叉树是层次分明的结构，因此按层次进行遍历是自然的事，它必能实现既访问到所因此按层次进行遍历是自然的事，它必能实现既访问到所有元素，又不会重复访问。此外，

53、对树和二叉树还可进行有元素，又不会重复访问。此外，对树和二叉树还可进行先左后右的遍历。先左后右的遍历。 4遍历的实质是按某种规则将二叉树中的数据元素排列遍历的实质是按某种规则将二叉树中的数据元素排列成一个线性序列，二叉树的线索链表便可看成是二叉树的成一个线性序列，二叉树的线索链表便可看成是二叉树的一种一种线性线性存储结构，在线索链表上可对二叉树进行存储结构，在线索链表上可对二叉树进行线线性化性化的遍历，即不需要的遍历，即不需要递归递归，而是从，而是从第一个元素第一个元素起起，逐个访问，逐个访问后继元素后继元素直至直至后继后继为为空空止。因此线索止。因此线索链表是通过遍历生成的，即在遍历过程中保

54、存结点之间的链表是通过遍历生成的，即在遍历过程中保存结点之间的前驱前驱和和后继后继的关系，并为方便起见，在线索链表中添的关系，并为方便起见，在线索链表中添加一个加一个头结点头结点，并由此构成一个，并由此构成一个双向循环链表双向循环链表。在实。在实际应用时也可简化为际应用时也可简化为单向循环链表单向循环链表（即只保存后继或前（即只保存后继或前驱关系）。驱关系）。5在这一章作为应用，介绍了最优树和最优前在这一章作为应用，介绍了最优树和最优前缀编码的构造方法，最优树是一种缀编码的构造方法，最优树是一种带权路径长带权路径长度最短度最短的树，最优前缀编码是最优二叉树的一的树，最优前缀编码是最优二叉树的一

55、种应用。种应用。 一、一、选择选择二、二、判断判断三、三、填空填空四、四、应用题应用题一、选择题一、选择题n已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A-A+B*C/DE B. -A+B*CD/EC-+*ABC/DE D. -+A*BC/DEn算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）Aab+cde/* Babcde/+*+Cabcde/*+Dabcde*/+1.设有一表示算术表达式的二叉树，它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G) C.(A*B+C)/(

56、D*E+（F-G）)D. A*B+C/D*E+F-G EFDGAB/+*-C*DBC练习练习n在下述结论中，正确的是（ ）只有一个结点的二叉树的度为0;二叉树的度为2；二叉树的左右子树可任意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C Dn若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定n有关二叉树下列说法正确的是（ ）A二叉树的度为2B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2D二叉树中任何一个结点的度都为2 DBBn具有10个叶结点的二叉树中有（ ）个度为2的结点。 A8 B9

57、C10 Dll n一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A 250 B 500 C254 D505 E以上答案都不对 BE由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 n二叉树的第i层上最多含有结点数为（ ） A2i B 2i-1-1 C 2i-1 D2i -1 n一个具有1025个结点的二叉树的高h为（ ） A11 B10 C11至1025之间D10至1024之间n一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1 n对于有n 个结点的二叉树, 其高度为（ ） Anlog2n Blog2n Clog2n|+1 D不确定n一棵具有 n个结点的完全二叉树的树