数据结构复习题.pdf

1 / 19 数据结构复习题 第一章 绪论 一、知识脉络图解 1、 基本概念（数据、数据元素、数据对象、数据结构） 2、 数据的逻辑结构（集合、线性、树、图） 3、 数据的存储结构（线性存储、链式存储、索引、散列存储） 4、 数据类型（原子类型、结构类型、抽象数据类型） 5、 算法（算法定义、算法具有的 5 各特性） 6、 算法的效率（时间复杂度、空间复杂度） 二、重点：逻辑结构、存储结构、数据运算三方面的概念及相互关系；时间复杂度分析。 三、难点：时间复杂度分析。 四、考试要点点击 五、典型题型 选择题 1.计算机算法指的是（1） ，它必须具备（2） 这三个特性。 (1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 2一个算法应该是（ ） 。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA 和 C. 3从逻辑上可以把数据结构分为（ ）两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构 4以下与数据的存储结构无关的术语是（ ） 。 A循环队列 B. 链表 C. 哈希表 D. 栈 5以下数据结构中，哪一个是线性结构（ ）？ A广义表 B. 二叉树 C. 稀疏矩阵 D. 串 6以下那一个术语与数据的存储结构无关？（ ） A栈 B. 哈希表 C. 线索树 D. 双向链表 7以下数据结构中， （ ）是非线性数据结构 A树 B字符串 C队 D栈 8. 下列数据中， （ ）是非线性数据结构。 A栈 B. 队列 C. 完全二叉树 D. 堆 9连续存储设计时，存储单元的地址（ ） 。 A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续 10以下属于逻辑结构的是（ ） 。 A顺序表 B. 哈希表 C.有序表 D. 单链表 填空题 1数据的物理结构包括 的表示和 的表示。 （数据元素 数据元素间关系） 2. 对于给定的 n 个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） ，_（4）_四种。 （集合 线性结构 树形结构 图状结构或网状结构） 2 / 19 3数据的逻辑结构是指 。 【数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻 接关系” 】 4 一个算法具有 5 个特性: （1） 、 （2） 、 （3） ，有零个或多个输入、有一个或多个输出。 5数据结构中评价算法的两个重要指标是 。 （算法的时间复杂度和空间复杂度。 ） 简答题 1. 数据结构和数据类型两个概念之间有区别吗？数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而 且还在其上定义了一组操作。且还在其上定义了一组操作。 2. 简述线性结构与非线性结构的不同点。简述线性结构与非线性结构的不同点。 答：线性结构反映结点间的逻辑关系是答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。一对一的，非线性结构反映结点间的逻辑关系是多对多的。 3. 分析下面各程序段的时间复杂度分析下面各程序段的时间复杂度 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 第二章 线性表 一、知识脉络图解 1. 线性表的定义、逻辑结构、基本运算 2. 线性表的顺序表示与实现 3. 线性表的链式表示与实现 二、重点：线性表的定义和特点、线性表的存储结构以及顺序表和链表的组织方式及算法设计 三、难点：单链表和双向链表上各种算法设计、循环链表 四、考试要点点击 五、典型题型 选择题 1下述哪一条是顺序存储结构的优点？（ ） A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示 2下面关于线性表的叙述中，错误的是哪一个？（ ） 2. s=0; for i=0; inext=head Bp-next =NIL Cp=NIL Dp= head 19完成在双循环链表结点 p 之后插入 s 的操作是（ ） 注意变形题 A p-next=s ; s-priou:=p; p-next-priou:=s ; s-next:=p-next; B p-next-priou:=s; p-next:=s; s-priou:=p; s-next:=p-next; C s-priou:=p; s-next:=p-next; p-next:=s; p-next-priou:=s ; D s-priou:=p; s-next:=p-next; p-next-priou:=s ; p-next:=s; 24在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是： （ ） 。 注意变形题 Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s; Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s; 25对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（ ） Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL 4 / 19 简答题 1.试比较顺序存储结构和链式存储结构特点及各自的优缺点。在什么情况下用顺序表比链表好？ 答：答： 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一） ；要求内存中可用存储单元的地址必须是连续的。顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一） ；要求内存中可用存储单元的地址必须是连续的。 优点：存储密度大（优点：存储密度大（1？） ，存储空间利用率高。缺点：插入或删除元素？） ，存储空间利用率高。缺点：插入或删除元素时不方便。时不方便。 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系 的指针的指针 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（next;L-next=NULL; /构造空表 while(p) q=p-next; p-next=L-next; L-next=p; p=q; /把 L 的元素逐个插入新表表头 /LinkList_reverse 4、试写一算法，在无头结点的动态单链表上实现线性表操作 Insert(L,i,b)，并和带头结点的单链表上 实现相同操作的算法进行比较。 5 / 19 Status Insert(LinkList q=(LinkList*)malloc(sizeof(LNode); q.data=b; /给新结点赋值 if(i=1) /插入位置为第一个结点之前，单独考虑 q.next=p;L=q; /插入在链表头部 else while(-i1) p=p-next; q-next=p-next;p-next=q; /插入在第 i 个元素的位置 /Insert 相关题： 4_1 在无头结点的动态单链表上实现线性表操作 Delete(L，i)。 Status Delete(LinkList /删除第一个元素 else p=L; while(-i1) p=p-next; /while p-next=p-next-next; /删除第 i 个元素 /Delete 5、 试编写在带头结点的单链表中删除 （一个） 最小值结点的 （高效） 算法。 void delete （Linklist j=0;k=0; while(iB.elemj) j+; else / A.elemi=B.elemj C.elem+k=A.elemi; /当发现了一个在 A,B 中都存在的元素，就添加到 C 中 i+;j+; /while /SqList_Intersect （*）6-1 假设两个元素依值递增有序排列的线性表 A 和 B 分别表示两个集合（即同一表中的元素值各不相 同） ，现要求另辟空间构成一个线性表 C，其元素为 A 和 B 中元素的交集，且 C 中的元素也依值递增有序排 列。试对链表编写 C 的算法 void LinkList_Intersect(LinkList A,LinkList B,LinkList q=B-next; /p，q 分别指向 A 和 B 的第一个结点 pc=(LNode*)malloc(sizeof(LNode); /给新表分配头结点 C=pc; while(p else if(p-data q-data) q=q-next; else /相等 s=(LNode*)malloc(sizeof(LNode); /给新结点分配存储空间 s-data=p-data; /赋值 pc-next=s;pc=s; /插入到新表的表尾，pc 始终指向新表的最后一个结点。 p=p-next;q=q-next; /while /LinkList_Intersect 第三章 栈和队列 一、知识脉络图解 1. 栈的基本概念、特性、基本操作，栈顶的概念 2. 栈的表示与实现（顺序栈、链栈） 3. 队列的基本概念、特性、基本操作，队头、队尾的概念 4. 队列的表示与实现（顺序队、链队） 二、重点：栈和队列的特点，顺序栈和链栈的基本运算算法的实现；顺序队列、循环队列和链队上的基本 操作和算法实现。 三、难点：灵活运用栈和队列设计解决应用问题的算法 四、考试要点点击 五、典型题型 选择题 1. 对于栈操作数据的原则是（ ） 。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ),在作退栈运算时应先判别栈是否( )。 当栈中元素为 n 个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( )分别设在这片内存空间的两端,这样,当( )时，才产生上溢。 , : A. 空 B. 满 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 长度 B. 深度 C. 栈顶 D. 栈底 : A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为 123n，若输出序列的第一个元素是 n，输出第 i（10) ? x* f(x-1):2); int i ; i =f(f(1); A2 B. 4 C. 8 D. 无限递归 19. 表达式 a*(b+c)-d 的后缀表达式是( )。 Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删 除操作时( )。 （有可能队列只有一个接点，此结点既是第一个也是最后一个） A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改 24. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。 A队列 B多维数组 C栈 D. 线性表 25. 假设以数组 Am存放循环队列的元素,其头尾指针分别为 front 和 rear，则当前队列中的元素个数为 （ ） 。 A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m 27. 循环队列存储在数组 A0m中，则入队时的操作为（ ） 。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 28. 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，当从队列中删除 一个元素，再加入两个元素后，rear 和 front 的值分别为多少？( ) A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1 31. 最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是 （ ） 。 9 / 19 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front 32. 栈和队列的共同点是（ ） 。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 34. 栈和队都是（ ） 【南京理工大学 1997 一、3（2 分） 】 A顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构 35. 设栈 S 和队列 Q 的初始状态为空，元素 e1，e2，e3，e4,e5 和 e6 依次通过栈 S，一个元素出栈后即进 队列 Q，若 6 个元素出队的序列是 e2，e4，e3,e6,e5,e1 则栈 S 的容量至少应该是( )。 A 6 B. 4 C. 3 D. 2 37. 依次读入数据元素序列a，b，c，d，e，f，g进栈,每进一个元素，机器可要求下一个元素进栈或弹 栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？ Ad ，e，c，f，b，g，a B. f，e，g，d，a，c，b C. e，f，d，g，b，c，a D. c，d，b，e，f，a，g 简答题： 1. 说明线性表、栈与队的异同点。 答：答：相同点：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限 的线性表，只是对插入、删除运算加以限制。 不同点：不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表 LIFO；队列 是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表 FIFO。 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。 2. 设有编号为 1，2，3，4 的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的 所有可能的顺序。 答：至少有 14 种。 全进之后再出情况，只有 1 种：4，3，2，1 进 3 个之后再出的情况，有 3 种，3,4,2,1 3,2,4,1 3,2,1,4 进 2 个之后再出的情况，有 5 种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 进 1 个之后再出的情况，有 5 种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3 3. 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？ 答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出” 。 采用循环队列是解决假溢出的途径。 另外，解决队满队空的办法有三： 设置一个布尔变量以区别队满还是队空； 浪费一个元素的空间，用于区别队满还是队空。 使用一个计数器记录队列中元素个数（即队列长度） 。 我们常采用法，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： front=rear 队满标志是：front=(rear+1)%N 5. 设循环队列的容量为 40（序号从 0 到 39） ，现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？ 答：用答：用队列长度计算公式： (Nrearfront)% N L=（401911）% 40=8 L=（401119）% 40=32 6. 写出下列程序段的输出结果（栈的元素类型 SElem Type 为 char） 。 void main( ) 10 / 19 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); while(!StackEmpty(S) Pop(S,y);printf(y); ; Printf(x); 答：输出为“stack” 。 7. 写出下列程序段的输出结果（队列中的元素类型 QElem Type 为 char） 。 void main( ) Queue Q; Init Queue (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(y); ; Printf(x); 答：输出为“char” 。 8. 简述以下算法的功能（栈和队列的元素类型均为 int） 。 void algo3(Queue int d; InitStack(S); while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d); ; while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。 算法题 1、 栈的基本操作（入栈、出栈） （书上算法） 2、 队列的基本操作（入队、出队） （书上算法） 3、 数制转换 4、 试写一个算法判别读入的一个以试写一个算法判别读入的一个以为结束符的字符序列是否是“回文” 。为结束符的字符序列是否是“回文” 。 int Palindrome_Test( void)/判别输入的字符串是否回文序列,是则返回 1,否则返回 0 InitStack(S); InitQueue(Q); /初始化栈和队列 11 / 19 while(c=getchar()!=) Push(S,c); EnQueue(Q,c); /同时入栈和入队列 while(!StackEmpty(S) Pop(S,a); DeQueue(Q,b); /出栈和出队列的顺序相反 if(a!=b) return ERROR; return OK; /Palindrome_Test 5、 设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当 ai -1 时， 将 ai进栈； 当 ai=-1 时， 输出栈顶整数并出栈。 算法应对异常情况 （入栈满等） 给出相应的信息。 #define maxsize 栈空间容量 void InOutS(int smaxsize) /s 是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top 为栈顶指针，定义 top=0 时为栈空。 for(i=1; i1)printf(“栈号输入不对”);exit(0); if(s.top1-s.top0=1) printf(“栈已满n”);return(0); switch(i) case 0: s.stack+s.top0=x; return(1); break; case 1: s.stack-s.top1=x; return(1); /push （2） 退栈操作 elemtp pop(int i) /退栈算法。 i 代表栈号， i=0 时为 s1 栈， i=1 时为 s2 栈。 退栈成功返回退栈元素， 否则返回-1。 if(i1)printf(“栈号输入错误n”)；exit(0); switch(i) case 0: if(s.top0=-1) printf(“栈空n”)；return（-1） ； else return(s.stacks.top0-); case 1: if(s.top1=maxsize printf(“栈空n”); return(-1); else return(s.stacks.top1+); /算法结束 算法讨论 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图略，s1 栈是通 常意义下的栈，而 s2 栈入栈操作时，其栈顶指针左移（减 1） ，退栈时，栈顶指针右移（加 1） 。 （*）7、. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写 出相应的入队列和出队列算法 （1）void EnQueue (LinkedList rear, ElemType x) / rear 是带头结点的循环链队列的尾指针，本算法将元素 x 插入到队尾。 s= (LinkedList) malloc (sizeof(LNode); /申请结点空间 s-data=x; s-next=rear-next; /将 s 结点链入队尾 rear-next=s; rear=s; /rear 指向新队尾 （2）void DeQueue (LinkedList rear) / rear 是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则 给出出错信息。 if (rear-next=rear) printf(“队空n”); exit(0); s=rear-next-next; /s 指向队头元素， rear-next-next=s-next; /队头元素出队。 printf (“出队元素是” ，s-data); if (s=rear) rear=rear-next; /空队列 free(s); （*）8、设整数序列 a1,a2,an，给出求解最大值的递归程序。 int MaxValue (int a,int n) /设整数序列存于数组 a 中，共有 n 个，本算法求解其最大值。 if (n=1) max=a1; else if (anMaxValue(a,n-1) max=an; else max=MaxValue(a,n-1); 13 / 19 return(max); / MaxValue （*）9、线性表中元素存放在向量 A（1,n）中，元素是整型数。试写出递归算法求出 A 中的最大和最 小元素。 本题与上题类似，只是这里是同时求 n 个数中的最大值和最小值的递归算法。 int MinMaxValue(int A,int n,int *max,int *min) /一维数组 A 中存放有 n 个整型数，本算法递归的求出其中的最大、最小数。 if (n0) if(*maxAn) *min=An; MinMaxValue(A,n-1,max,min); /MinMaxValue 注： 调用本算法的格式是 MinMaxValue(arr,n,其中， arr 是具有 n 个整数的一维数组， max=-32768 是最大数的初值,min=32767 是最小数的初值。 第四章 串 一、知识脉络图解 1. 串的基本概念（串的定义、主串、字串、空串、空格串、串的基本运算） 2. 串的顺序存储与实现（定义顺序存储表示、堆分配存储表示、基本运算的实现） 3. 串的链式存储与实现（链串的类型说明、基本算法实现*） 4. 串的模式匹配算法（定长顺序存储结构上的匹配算法、KMP 算法*） 二、重点：串的顺序存储方法和串的链接存储方法以及串的基本运算算法的实现 三、难点：模式匹配算法的实现 四、考试要点点击 五、典型题型 选择题 1 下面关于串的的叙述中，哪一个是不正确的？（ ） A 串是字符的有限序列 B 空串是由空格构成的串 C 模式匹配是串的一种重要运算 D 串既可以采用顺序存储，也可以采用链式存储 （*）2. 若串S1=ABCDEFG, S2=9898 ,S3=#,S4=012345,执行 concat(replace(S1,substr(S1,length(S2),length(S3),S3),substr(S4,index(S2, 8 ),length(S2) 其结果为（ ） A ABC#G0123 B ABCD#2345 C ABC#G2345 D ABC#2345 E ABC#G1234 F ABCD#1234 G ABC#01234 3 设有两个串 p 和 q ，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（ ） A 求子串 B 联接 C 匹配 D 求串长 （*）4 已知串 S=aaab, 其 Next 数组值为（ ） 。 A 0123 B 1123 C 1231 D 1211 （*）5 串 ababaaababaa的 next 数组为（ ） 。 A 012345678999 B 012121111212 C 011234223456 D 0123012322345 （*）6 字符串ababaabab 的 nextval 为（ ） 14 / 19 A (0,1,0,1,04,1,0,1) B (0,1,0,1,0,2,1,0,1) C (0,1,0,1,0,0,0,1,1) D (0,1,0,1,0,1,0,1,1 ) 7 模式串 t= abcaabbcabcaabdab ，该模式串的 next 数组的值为（ ） ， nextval 数组的值为 （ ） 。 A 0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B 0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C 0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E 0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 8 若 串 S= software , 其子串的数目是（ ） 。 A 8 B 37 C 36 D 9 注：空串是任意串的子串，自己是自己的子串 9 设 S 为一个长度为 n 的字符串，其中的字符各不相同，则 S 中的互异的非平凡子串（非空且不同 于 S 本身）的个数为（ ） 。 A 2n-1 B n2 C (n2/2)+(n/2) D (n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F. 其他情况 10 串的长度是指（ ） A 串中所含不同字母的个数 B 串中所含字符的个数 C 串中所含不同字符的个数 D 串中所含非空格字符的个数 简答题 1 名词解释：串 答：答：串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。 2 描述以下概念的区别：空格串与空串。 答：空格是一个字符，其答：空格是一个字符，其 ASCII 码值是码值是 32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的 串，即空串的长度是零。串，即空串的长度是零。 编程题 1、 串的五种基本操作 （书上算法） 2、 串的简单模式匹配算法 （书上算法） 第六章 树 一、知识脉络图解 1. 树及二叉树的定义 2. 树及二叉树的性质 3. 树的逻辑表示（树形表示法、嵌套集合表示法、凹入表示法、广义表形式表示法） 4. 树的存储结构（双亲表示法、孩子表示法、孩子兄弟表示法） 5. 特殊二叉树（满二叉树、完全二叉树、二叉排序树、平衡二叉树） 6. 二叉树的存储结构（顺序存储结构、链式存储结构） 7. 二叉树的基本运算 8. 二叉树的遍历（先序、中序、后序）和线索二叉树 9. 树和森林与二叉树的转换 10. 赫夫曼树（赫夫曼树的定义及构造、赫夫曼编码） 二、重点：二叉树的性质、二叉树的各种遍历方法及它们所确定的序列间的关系、二叉树上的基本运算算 法的实现、二叉树的线索化方法，构造赫夫曼树的方法。 三、难点：二叉树上各种算法，特别树递归算法的设计。 四、考试要点点击 五、典型题型 15 / 19 E F D G A B / + + * - C * 选择题 1已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为 ABC*+DE/-，其前缀形式为( ) A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE 2算术表达式 a+b*（c+d/e）转为后缀表达式后为（ ） Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+ 3. 设有一表示算术表达式的二叉树（见下图） ， 它所表示的算术表达式是（ ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G 4. 设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1 则 T 中的叶子数为（ ） A5 B6 C7 D8 5. 在下述结论中，正确的是（ ） 【南京理工大学 1999 一、4 （1 分） 】 只有一个结点的二叉树的度为 0; 二叉树的度为 2； 二叉树的左右子树可任意交换; 深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D 6. 设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p,p 的右子树结点个数为 n,森林 F 中第一棵树的 结点个数是（ ） Am-n Bm-n-1 Cn+1 D条件不足，无法确定 【南京理工大学 2000 一、17（1.5 分） 】 7. 树是结点的有限集合，它（ (1）)根结点，记为 T。其余结点分成为 m（m0）个(（2）)的集合 T1， T2， ，m，每个集合又都是树，此时结点 T 称为 Ti 的父结点，Ti 称为 T 的子结点（1im） 。一个 结点的子结点个数称为该结点的( （3） )。二叉树与树是两个不同的概念，二叉树也是结点的有限集合， 它(（4）)根结点。可以把树的根结点的层数定义为 1，其他结点的层数等于其父结点所在层数加上 1。令 T 是一棵二叉树，Ki 和 Kj 是 T 中子结点数小于 2 的结点中的任意两个，它们所在的层数分别为 Ki 和 Kj，当关系式 Ki- Kj1 一定成立时，则称 T 为一棵（(5)） 。供选择的答案： （1）(4) A. 有 0 个或 1 个 B. 有 0 个或多个 C. 有且只有一个 D. 有 1 个或 1 个以上 （2） A. 互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交 （3） A. 权 B.维数 C.次数 D.序 （5） A. 丰满树 B.查找树 C.平衡树 D.完全树 【上海海运学院 1999 二、2(5 分） 】 8若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（ ） A9 B11 C15 D不确定 【北京工商大学 2001 一.7(3 分)】 9在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为（ ）个 A4 B5 C6 D7 【哈尔滨工业大学 2001 二、2 （2 分） 】 10设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为 M1，M2 和 M3。与森林 F 对应的二叉 树根结点的右子树上的结点个数是（ ） 。 【北方交通大学 2001 一、16 （2 分） 】 AM1 BM1+M2 CM3 DM2+M3 11具有 10 个叶结点的二叉树中有（ ）个度为 2 的结点， 【北京航空航天大学 2000 一、5（2 分)】 A8 B9 C10 Dll 12 一棵完全二叉树上有 1001 个结点， 其中叶子结点的个数是 （ ）【西安交通大学 1996 三、 2 (3 分)】 A 250 B 500 C254 D505 E以上答案都不对 13. 设给定权值总数有 n 个，其哈夫曼树的结点总数为( ) 【福州大学 1998 一、5 (2 分)】 A不确定 B2n C2n+1 D2n-1 14. 有 n 个叶子的哈夫曼树的结点总数为（ ） 。 【青岛大学 2002 二、1 （2 分） 】 A不确定 B2n C2n+1 D2n-1 16 / 19 15若度为 m 的哈夫曼树中，其叶结点个数为 n，则非叶结点的个数为（ ） 。 【中科院计算所 1999 一、2 （2 分） 】 An-1 Bn/m-1 C(n-1)/(m-1) D n/(m-1)-1 E(n+1)/(m+1)-1 16. 有关二叉树下列说法正确的是（ ） 【南京理工大学 2000 一、11 （1.5 分） 】 A二叉树的度为 2 B一棵二叉树的度可以小于 2 C二叉树中至少有一个结点的度为 2 D二叉树中任何一个结点的度都为 2 17二叉树的第 I 层上最多含有结点数为（ ） 【中山大学 1998 二、7 （2 分） 】 【北京理工大学 2001 六、5（2 分） 】 A2 I B 2I-1-1 C 2I-1 D2I -1 18. 一个具有 1025 个结点的二叉树的高 h 为（ ） 【南京理工大学 1999 一、19 （2 分） 】 A11 B10 C11 至 1025 之间 D10 至 1024 之间 19一棵二叉树高度为 h,所有结点的度或为 0，或为 2，则这棵二叉树最少有( )结点 A2h B2h-1 C2h+1 Dh+1 【南京理工大学 2001 一、11(1.5 分） 】 20对于有 n 个结点的二叉树, 其高度为（ ） 【武汉交通科技大学 1996 一、5 (4 分)】 Anlog2n Blog2n Clog2n|+1 D不确定 21. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ ） 【南京理工大学 1996 一、8 （2 分） 】 Alogn+1 Blogn+1 Clogn Dlogn-1 22深度为 h 的满 m 叉树的第 k 层有（ ）个结点。(1=k=h)【北京航空航天大学 2000 一、4（2 分） 】 Am k-1 Bmk-1 Cmh-1 Dmh-1 23在一棵高度为 k 的满二叉树中，结点总数为（ ） 【北京工商大学 2001 一、3 (3 分)】 A2 k-1 B2k C2k-1 Dlog2k+1 24高度为 K 的二叉树最大的结点数为（ ） 。 【山东大学 2001 二、3 (1 分)】 A2 k B2 k-1 C2k -1 D2 k-1-1 25. 一棵树高为 K 的完全二叉树至少有（ ）个结点【南京理工大学 1998 一、3 （2 分） 】 A2 k 1 B. 2k-1 1 C. 2k-1 D. 2k 26. 将有关二叉树的概念推广到三叉树，则一棵有 244 个结点的完全三叉树的高度（） A4 B5 C6 D7 【南京理工大学 2000 一、5 1.5 分） 】 27. 利用二叉链表存储树，则根结点的右指针是（ ） 。 【青岛大学 2001 五、5 （2 分） 】 A指向最左孩子 B指向最右孩子 C空 D非空 28对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的 左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 【北京理工大学 2000 一、4 （2 分） 】 A先序 B. 中序 C. 后序 D. 从根开始按层次遍历 29树的后根遍历序列等同于该树对应的二叉树的( ). 【北京理工大学 2001 六、6 （2 分） 】 A. 先序序列 B. 中序序列 C. 后序序列 30若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最 合适。 A前序 B中序 C后序 D按层次【北京航空航天大学 1999 一、4 （2 分） 】 31在下列存储形式中，哪一个不是树的存储形式？（ ） 【北方交通大学 2001 一、23 （2 分） 】 A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法 32一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是（ ） 【北京工业大学 2001 一、 2 (2 分)】 ACABDEFG BABCDEFG CDACEFBG DADCFEG 33已知一棵二叉树的前序遍历结果为 ABCDEF,中序遍历结果为 CBAEDF,则后序遍历的结果为（ ） 。 ACBEFDA B FEDCBA C CBEDFA D不定 【浙江大学 1999 四、2 ( 4 分)】 17 / 19 34已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac , 它的前序遍历是（ ） 。 Aacbed Bdecab Cdeabc Dcedba 【山东大学 2001 二、7 ( 1 分)】 35. 某二叉树中序序列为 A,B,C,D,E,F,G，后序序列为 B,D,C,A,F,G,E 则前序序列是： AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不对 【南京理工大学 2000 一、14 （1.5 分） 】 36. 上题的二叉树对应的森林包括多少棵树（ ） 【南京理工大学 2000 一、15 （1.5 分） 】 Al B2 C3 D概念上是错误的 37二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子 树的根是： 【北方交通大学 2001 一、21（2 分） 】 A、 E B、 F C、 G D、 H 38将一棵树 t 转换为孩子兄弟链表表示的二叉树 h，则 t 的后根序遍历是 h 的 A前序遍历 B中序遍历 C后序遍历（ ） 【北京邮电大学 2001 一、2 （2 分） 】 39. 某二叉树 T 有 n 个结点，设按某种顺序对 T 中的每个结点进行编号，编号为 1，2， ，n，且有如 下性质：T 中任一结点 V，其编号等于左子树上的最小编号减 1，而 V 的右子树的结点中，其最小编号等 于 V 左子树上结点的最大编号加 1。这时是按( )编号的。 A.中序遍历序列 B.前序遍历序列 C