/* *晚上花了几个小时翻译了下,第一次翻译这么长的文字;挺累呀,翻译的很多地方也不算通顺,权当自娱自乐了。 *版权所有 xt2120#gmail
c++ 虚函数 原理 机制 c 虚函数表 表指针
上个月,我介绍了虚拟函数。我概述了如何使用虚拟函数来实现一个设备无关的文件系统,并详细描述了如何创建一个具有多态行为的几何图形类。这个月我将继续解释虚拟函数的工作机制。首先,扼要重复一下其中的关键概念。 在c++中在基础类和基类之间的公共继承定义了一个is-a的关系。这就是说,给出了定义:
D从B公共派生而来,所以任何D对象同时也是一个B对象。一个接收B对象指针或引用作为形式参数的函数也会允许一个指向D对象的指针(或引用,相应的)作为参数。
更一般的情况,将一个指向D对象的指针转换为一个指向B对象的指针是一个标准转换而不需要cast。例如,如果d是一个类D的对象,B是D的公共继承类,你可以写下如下代码:
当讨论指向基类和继承类对象的指针行为时,它将能够帮助你区分一个对象的动态类型和静态类型。一个对象的静态类型是用于引用那个对象的表达式。一个对象的动态类型是其“实际的”类型--当指针被创建时对象的类型。
比如,使用上面定义和初始化的pb,*pb的静态类型为B,但是其动态类型为D(B* pb = &d;)。或者考虑:
rb的静态类型为B同时其动态类型为D。*pb的静态类型总是B,但是其动态类型在程序执行的时候可能会发生变化。例如,如果b是一个B对象,那么
会改变*pb的动态类型为B。
一个派生类继承了其基类的所有成员。一个派生类不能丢弃任何其所继承的成员,但是它能够使用覆写(override)一个继承的成员函数。
在c++中,一个非静态成员函数默认是非虚拟函数。c++通过静态绑定来解析一个非虚函数调用。也就是说,如果pb被声明为B*,并且B有一个非虚函数,那么pb->f总是调用B的函数f。即使在调用时pb实际指向的是一个D对象(此中D从B派生而来并且覆写了函数),那么调用pb->f仍旧调用的是隶属于B的函数f,而不是D的f。从另一方面来说,虚拟成员函数调用是动态绑定的。如果pb是B*指针并且f在中被声明为一个虚拟成员函数,那么pb->f所实际调用的函数取决于*pb的动态类型。这样的话,如果pb实际指向的是B对象,那么pb->f调用的隶属于B的f。而如果pb实际是想一个D对象(D由B派生而来并且覆写了函数f),那么pb->f调用的是D的f。
一个至少有一个虚拟成员函数的类被称作多态类型,这样类型的对象们展示了多态性。多态能让你为逻辑上相似但实体行为不同的子类型继承体系定义统一的接口。通过使用多态,你能够将一个派生类对象指针或引用传递给只知其基类型对象的函数。对象仍将保持其动态类型以使得成员函数调用能够施行派生类的行为。Listing 1显示了shape类定义,一个多态的几何类。
Listing 5包含了一个函数展示了多态的威力。函数largest从一个shapes集合中找到具有最大面积的shape。既然shape是多态类型,那么调用sa[i]->area不用调用者准确知晓*sa[i]实际的shape类型就能返回其面积。
ARM(Ellis)和新兴的c++标准都在竭力描述虚函数的行为特征,就如同其所描述的C++语言的其他部分,而没有没有建议具体的实现策略。但是,ARM里面在第十章的结尾派生类的评注中确实描述了实现技术。我觉得仰仗一个模型来实现简化了虚拟函数习性的细节描述。下面就是这样的一个模型。典型的c++实现里为每一个多态类的对象增加了一个指针。这个指针被称作vptr。不论何时一个多态类的构造函数初始化一个对象时,它都会将对象的vptr设置为一个叫做vtbl的函数指针表的地址。vtbl中的每一个条目都一个虚函数的地址。一个既定类的所有对象都共享同样的vtbl;这个vtbl包含了包含了该类中的每一个虚函数的入口地址。
例如,上图显示了类shape的一个对象的布局(在listing 1中定义的)和其相应的vtbl。每一个shape对象都拥有同样顺序的两个值域:vptr和一个_colo两个派生类的vtbls和基类的vtbl拥有同样的函数指针序,尽管指针值是不同的。例如,area函数的vtbl入口在每一个从shape派生而来的类中都排在第一位。name的vtbl入口总在第二,put的入口序总为3。
然而一个非虚函数调用所产生的调用指令直接指向了在转换中(编译和链接)就已确定的地址,一个虚函数调用产生的额外的代码以定位vtbl中的函数地址。
ARM一书中建议将vtbl看作函数地址的一个队列,以使得每一次对被调用函数的定位能够vtbl的下标来定位。比如,如果ps只一个指向shape的指针,那么
会被转换成如下这个样子:
每一个虚函数可能会有不同的签名式(形式参数类型次序)和返回类型返回类型。所以严格来讲,你不能将vtbls实现成函数数组,因为数组需要其所有类型都具有同样的类型。比如, shape::area 类型为 double (*)() , shape::put 类型为
与此类似,你能够如下定义circle vtbl:
一次具有n个参数的虚拟函数调用将被转换成具有n+1个参数的调用(通过vtbl入口)。增加的那个参数就是被应用函数的对象的地址;在上例中,其值总是ps。在被调用函数中,这个额外的参数就成了this的值。虚函数不能为静态成员,所以他们总是隐式的有一个this参数。
记住我所描述的只是一种典型的实现策略。c++ translators 可能在实现虚函数时并不一致,但是效果是一样的。vptr并不需要在每个多态对象的开头。但是,对于任何从多态类型B派生而来的类D而言,D的vptr在D中的偏移量和B的vptr在B中的偏移量一致。类似地,vtbl中的函数指针的顺序也并不一定和类中声明的顺序一致,但对于任何任何从多态类B派生而来的D,D的vtbl的初始部分必须和B的vtbl的布局一致,即便因D已经覆写了某些所继承的虚函数而造成D的实际的指针值与B的不同。
简而言之,一个C++ TRANSLATOR必须确保派生对象的基子对象与任何基类型对象的布局一致,并且派生类型vtbl基portion部分和基类对象的vtbl一致。因此,当translator转换一个虚函数调用时不需要预见任何派生类的声明。不考虑p的动态类型,一个如p->f这样的虚函数调用总是转成这样的代码
所有既定多态类型的多态对象能够共享共同的vtbl实体。一些c++成功剔除了vtbls的重复。另一些产生多酚vtbls的拷贝,由于开发环境所限或者为提供更好的系统性能。许多实现提供了编译和链接选项让你自行作出决定。
继承体系,图4显示了相应的vtbls。类B定义了三个虚函数f,g和h。由B派生而来的C只覆写了函数f,所以C的vtbl中的g和h的入口仍旧是B的g和h。由C派生的类D只覆写了函数h,所以D的vtbl中的f和g的入口和C的vtbl中的一致。既然C和D都没有覆写g,所有三个;类的vtbl对于g的入口都具有同样的值,也就是B'g。
在Listing 6中,pc有一个静态类型C*.但是当程序执行到这句前
pc的动态类型为D*。所以所有应用到rb上的调用都使用D的vtbl。
假设 a1
。b1
。c1
和 d1
指向堆内存,我的数字代码具有以下核心循环。
这里循环通过另一个外部 for
循环执行 10,000次。为了提高速度,我将代码更改为:
PS: 我不确定,如果有帮助的话:
第一个循环的反汇编基本上类似于这里( 这个块在整个程序中重复了大约五次):
双循环示例的每个循环都生成这里代码( 以下块重复三次):
收费:问题没有关联,因为行为严重取决于数组的( n ) 和CPU缓存的大小。因此,如果有进一步的兴趣,我将重新解释这个问题:
可以提供对导致不同缓存行为的细节的一些细节,如下面图中所示的五个区域。?
通过提供类似的图,可以指出 cpu/缓存体系结构之间的差异,这可能是有趣的。
PPS: 这是完整的代码。它使用 用于更高分辨率的计时,可以通过不定义宏来禁用该功能:
( 它显示 n
的不同值的触发器/s 。)
⑴( )是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
⑵( )是数据的最小单位,( )是讨论数据结构时涉及的最小数据单位。
⑶ 从逻辑关系上讲,数据结构主要分为( )、( )、( )和( )。
⑷ 数据的存储结构主要有( )和( )两种基本方法,不论哪种存储结构,都要存储两方面的内容:( )和( )。
⑸ 算法具有五个特性,分别是( )、( )、( )、( )、( )。
⑹ 算法的描述方法通常有( )、( )、( )和( )四种,其中,( )被称为算法语言。
⑺ 在一般情况下,一个算法的时间复杂度是( )的函数。
⑻ 设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为( ),若为n*log25n,则表示成数量级的形式为( )。
⑴ 顺序存储结构中数据元素之间的逻辑关系是由( )表示的,链接存储结构中的数据元素之间的逻辑关系是由( )表示的。
⑵ 假设有如下遗产继承规则:丈夫和妻子可以相互继承遗产;子女可以继承父亲或母亲的遗产;子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是( )。
⑶ 算法指的是( )。
⑷ 下面( )不是算法所必须具备的特性。
⑸ 算法分析的目的是( ),算法分析的两个主要方面是( )。
⑴ 算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。
⑵ 每种数据结构都具备三个基本操作:插入、删除和查找。
⑶ 所谓数据的逻辑结构指的是数据之间的逻辑关系。
⑷ 逻辑结构与数据元素本身的内容和形式无关。
⑸ 基于某种逻辑结构之上的基本操作,其实现是唯一的。 4. 分析以下各程序段,并用大O记号表示其执行时间。
6. 为整数定义一个抽象数据类型,包含整数的常见运算,每个运算对应一个基本操作,每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。
7. 求多项式A(x)的算法可根据下列两个公式之一来设计:
8. 算法设计(要求:算法用伪代码和C++描述,并分析最坏情况下的时间复杂度) 下面是简单选择排序算法的C++描述。 分析算法,有两层嵌套的for循环,所以, 。
⑵ 找出整型数组A[n]中元素的最大值和次最大值。 算法的C++描述如下: 分析算法,只有一层循环,共执行n-2次,所以,T(n)=O(n)。
1.顺序存储结构的特点是( ),链接存储结构的特点是( )。
2. 算法在发生非法操作时可以作出处理的特性称为( )。
3. 常见的算法时间复杂度用大O记号表示为:常数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。
5.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
⑴ 在顺序表中,等概率情况下,插入和删除一个元素平均需移动( )个元素,具体移动元素的个数与( )和( )有关。
⑵ 顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是( )。
⑶ 设单链表中指针p 指向结点A,若要删除A的后继结点(假设A存在后继结点),则需修改指针的操作为( )。
⑷ 单链表中设置头结点的作用是( )。
⑸ 非空的单循环链表由头指针head指示,则其尾结点(由指针p所指)满足( )。
⑺ 一个具有n个结点的单链表,在指针p所指结点后插入一个新结点的时间复杂度为( );在给定值为x的结点后插入一个新结点的时间复杂度为( )。
⑻ 可由一个尾指针唯一确定的链表有( )、( )、( )。
⑴ 线性表的顺序存储结构是一种( )的存储结构,线性表的链接存储结构是一种( )的存储结构。
⑵ 线性表采用链接存储时,其地址( )。
⑶ 单循环链表的主要优点是( )。
⑷ 链表不具有的特点是( )。
⑸ 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋,则采用( )存储方法最节省时间。
⑹ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则采用( )存储方法最节省时间。
⑺ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用( )存储方法最节省运算时间。
⑻ 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。
⑼ 对于n个元素组成的线性表,建立一个有序单链表的时间复杂度是( )。
⑽ 使用双链表存储线性表,其优点是可以( )。
⑴ 线性表的逻辑顺序和存储顺序总是一致的。
⑵ 线性表的顺序存储结构优于链接存储结构。 【解答】错。p=q只能表示p和q指向同一起始地址,而所指类型则不一定相同。
⑷ 线性结构的基本特征是:每个元素有且仅有一个直接前驱和一个直接后继。
⑸ 在单链表中,要取得某个元素,只要知道该元素所在结点的地址即可,因此单链表是随机存取结构。
4.请说明顺序表和单链表各有何优缺点,并分析下列情况下,采用何种存储结构更好些。
⑴ 设计一个时间复杂度为O(n)的算法,实现将数组A[n]中所有元素循环右移k个位置。 分析算法,第一次调用Reverse函数的时间复杂度为O(k),第二次调用Reverse函数的时间复杂度为O(n-k),第三次调用Reverse函数的时间复杂度为O(n),所以,总的时间复杂度为O(n)。
⑵ 已知数组A[n]中的元素为整型,设计算法将其调整为左右两部分,左边所有元素为奇数,右边所有元素为偶数,并要求算法的时间复杂度为O(n)。 分析算法,两层循环将数组扫描一遍,所以,时间复杂度为O(n)。
⑶ 试编写在无头结点的单链表上实现线性表的插入操作的算法,并和带头结点的单链表上的插入操作的实现进行比较。
⑷ 试分别以顺序表和单链表作存储结构,各写一实现线性表就地逆置的算法。 单链表的逆置请参见2.2.4算法2-4和算法2-6。
⑸ 假设在长度大于1的循环链表中,即无头结点也无头指针,s为指向链表中某个结点的指针,试编写算法删除结点s的前趋结点。
⑹ 已知一单链表中的数据元素含有三类字符:字母、数字和其他字符。试编写算法,构造三个循环链表,使每个循环链表中只含同一类字符。 ⑺ 设单链表以非递减有序排列,设计算法实现在单链表中删去值相同的多余结点。 【解答】从头到尾扫描单链表,若当前结点的元素值与后继结点的元素值不相等,则指针后移;否则删除该后继结点。具体算法如下:
⑻ 判断带头结点的双循环链表是否对称。
1. 已知一维数组A采用顺序存储结构,每个元素占用4个存储单元,第9个元素的地址为144,则第一个元素的地址是( )。
3.在一个长度为n的顺序表的第i(1≤i≤n+1)个元素之前插入一个元素,需向后移动( )个元素,删除第i(1≤i≤n)个元素时,需向前移动( )个元素。
4.在单链表中,除了头结点以外,任一结点的存储位置由( )指示。
5.当线性表采用顺序存储结构时,其主要特点是( )。
6.在双链表中,每个结点设置了两个指针域,其中一个指向( )结点,另一个指向( )结点。
7.设A是一个线性表(a1, a2, …, an),采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为多少?若元素插在ai与ai+1之间(1≤i≤n)的概率为 ,则平均每插入一个元素所要移动的元素个数又是多少?
8.线性表存放在整型数组A[arrsize]的前elenum 个单元中,且递增有序。编写算法,将元素x插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。
9. 已知单链表中各结点的元素值为整型且递增有序,设计算法删除链表中所有大于mink且小于maxk的所有元素,并释放被删结点的存储空间。
10.设单循环链表L1,对其遍历的结果是:x1, x2, x3,…, xn-1, xn。请将该循环链表拆成两个单循环链表L1和L2,使得L1中含有原L1表中序号为奇数的结点且遍历结果为:x1, x3,… ;L2中含有原L1表中序号为偶数的结点且遍历结果为:… , x4, x2。
⑴ 设有一个空栈,栈顶指针为1000H,现有输入序列为1、2、3、4、5, 经过push,push,pop,push,pop,push,push后,输出序列是( ),栈顶指针为( )。
⑵ 栈通常采用的两种存储结构是( );其判定栈空的条件分别是( ),判定栈满的条件分别是( )。
⑶( )可作为实现递归函数调用的一种数据结构。
⑷ 表达式a*(b+c)-d的后缀表达式是( )。
⑸ 栈和队列是两种特殊的线性表,栈的操作特性是( ),队列的操作特性是( ),栈和队列的主要区别在于( )。
⑹ 循环队列的引入是为了克服( )。
⑺ 数组Q[n]用来表示一个循环队列,front为队头元素的前一个位置,rear为队尾元素的位置,计算队列中元素个数的公式为( )。
⑻ 用循环链表表示的队列长度为n,若只设头指针,则出队和入队的时间复杂度分别是( )和( )。
⑼ 串是一种特殊的线性表,其特殊性体现在( )。
⑽ 两个串相等的充分必要条件是( )。
⑴ 若一个栈的输入序列是1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素是( )。
⑵ 设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5、e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的顺序是e2、e4、e3、e6、e5、e1,则栈S的容量至少应该是( )。
⑶ 一个栈的入栈序列是1,2,3,4,5,则栈的不可能的输出序列是( )。
⑷ 设计一个判别表达式中左右括号是否配对的算法,采用( )数据结构最佳
⑸ 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区,该缓冲区应该是一个( )结构。
⑹ 一个队列的入队顺序是1,2,3,4,则队列的输出顺序是( )。
⑺ 栈和队列的主要区别在于( )。
⑻ 设数组S[n]作为两个栈S1和S2的存储空间,对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是( )。
⑼ 设有两个串p和q,求q在p中首次出现的位置的运算称作( )。
⑴ 有n个元素依次进栈,则出栈序列有(n-1)/2种。
⑵ 栈可以作为实现过程调用的一种数据结构。
⑶ 在栈满的情况下不能做进栈操作,否则将产生“上溢”。
⑷ 在循环队列中,front指向队头元素的前一个位置,rear指向队尾元素的位置,则队满的条件是front=rear。
⑸ 空串与空格串是相同的。
4. 设有一个栈,元素进栈的次序为A,B,C,D,E,能否得到如下出栈序列,若能,请写出操作序列,若不能,请说明原因。
5. 举例说明顺序队列的“假溢出”现象。 【解答】栈顶元素为6,栈底元素为1。其执行过程如图3-7所示。
8.空串和空格串有何区别?串中的空格符有何意义?空串在串处理中有何作用?
⑴ 假设以不带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针。试设计相应的入队和出队的算法。
⑵ 设顺序栈S中有2n个元素,从栈顶到栈底的元素依次为a2n,a2n-1,…,a1,要求通过一个循环队列重新排列栈中元素,使得从栈顶到栈底的元素依次为a2n,a2n-2,…,a2,a2n-1,a2n-3,…,a1,请设计算法实现该操作,要求空间复杂度和时间复杂度均为O(n)。
⑶ 用顺序存储结构存储串S,编写算法删除S中第 i个字符开始的连续j个字符。
⑷ 对于采用顺序存储结构的串S,编写一个函数删除其值等于ch的所有字符。
⑸ 对串的模式匹配KMP算法设计求模式滑动位置的next函数。
1.在一个具有n个单元的顺序栈中,假定以地址低端(即下标为0的单元)作为栈底,以top作为栈顶指针,当出栈时,top的变化为( )。
6.对于栈和队列,无论它们采用顺序存储结构还是链接存储结构,进行插入和删除操作的时间复杂度都是( )。
8.简述队列和栈这两种数据结构的相同点和不同点。
9. 利用两个栈S1和S2模拟一个队列,如何利用栈的运算实现队列的插入和删除操作,请简述算法思想。
10. 设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。
11.假设一个算术表达式中可以包含三种括号:圆括号“(”和“)”,方括号“[”和“]”以及花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否配对出现。
第 4 章 广义线性表——多维数组和广义表
⑴ 数组通常只有两种运算:( )和( ),这决定了数组通常采用( )结构来实现存储。
⑵ 二维数组A中行下标从10到20,列下标从5到10,按行优先存储,每个元素占4个存储单元,A[10][5]的存储地址是1000,则元素A[15][10]的存储地址是( )。
⑶ 设有一个10阶的对称矩阵A采用压缩存储,A[0][0]为第一个元素,其存储地址为d,每个元素占1个存储单元,则元素A[8][5]的存储地址为( )。
⑷ 稀疏矩阵一般压缩存储方法有两种,分别是( )和( )。
⑸ 广义表((a), (((b),c)),(d))的长度是( ),深度是( ),表头是( ),表尾是( )。
⑴ 二维数组A的每个元素是由6个字符组成的串,行下标的范围从0~8,列下标的范围是从0~9,则存放A至少需要( )个字节,A的第8列和第5行共占( )个字节,若A按行优先方式存储,元素A[8][5]的起始地址与当A按列优先方式存储时的( )元素的起始地址一致。
⑵ 将数组称为随机存取结构是因为( )
⑸ 广义表((a), (((b),c)),(d))的长度是( ),深度是( ),表头是( ),表尾是( )。
⑴ 二维数组A的每个元素是由6个字符组成的串,行下标的范围从0~8,列下标的范围是从0~9,则存放A至少需要( )个字节,A的第8列和第5行共占( )个字节,若A按行优先方式存储,元素A[8][5]的起始地址与当A按列优先方式存储时的( )元素的起始地址一致。
⑵ 将数组称为随机存取结构是因为( )
⑶ 下面的说法中,不正确的是( )
⑷ 对特殊矩阵采用压缩存储的目的主要是为了( )
⑸ 下面( )不属于特殊矩阵。
⑺ 下面的说法中,不正确的是( )
⑻ 下面的说法中,不正确的是( )
⑴ 数组是一种复杂的数据结构,数组元素之间的关系既不是线性的,也不是树形的。
⑵ 使用三元组表存储稀疏矩阵的元素,有时并不能节省存储空间。
⑶ 稀疏矩阵压缩存储后,必会失去随机存取功能。
⑷ 线性表可以看成是广义表的特例,如果广义表中的每个元素都是单元素,则广义表便成为线性表。
⑸ 若一个广义表的表头为空表,则此广义表亦为空表。 4.一个稀疏矩阵如图4-4所示,写出对应的三元组顺序表和十字链表存储表示。
5.已知A为稀疏矩阵,试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求 运算的优缺点。 6.设某单位职工工资表ST由“工资”、“扣除”和“实发金额”三项组成,其中工资项包括“基本工资”、“津贴”和“奖金”,扣除项包括“水”、“电”和“煤气” 。
⑴ 请用广义表形式表示所描述的工资表ST,并用表头和表尾求表中的“奖金”项;
7.若在矩阵A中存在一个元素ai,j(0≤i≤n-1,0≤j≤m-1),该元素是第i行元素中最小值且又是第j列元素中最大值,则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A,试设计一个求该矩阵所有马鞍点的算法,并分析最坏情况下的时间复杂度。 分析算法,外层for循环共执行n次,内层第一个for循环执行m次,第二个for循环最坏情况下执行n次,所以,最坏情况下的时间复杂度为O(mn+n2)。
1.二维数组M中每个元素的长度是3个字节,行下标从0到7,列下标从0到9,从首地址d开始存储。若按行优先方式存储,元素M[7][5]的起始地址为( ),若按列优先方式存储,元素M[7][5]的起始地址为( )。
2.一个n×n的对称矩阵,按行优先或列优先进行压缩存储,则其存储容量为( )。
3.设n行n列的下三角矩阵A(行列下标均从1开始)已压缩到一维数组S[1]~S[n(n+1)/2]中,若按行优先存储,则A[i][j]在数组S中的存储位置是( )。
6.设有三对角矩阵An×n(行、列下标均从0开始),将其三条对角线上的元素逐行存于数组B[3n-2]中,使得B[k]=aij求:
7.已知两个n×n的对称矩阵按压缩存储方法存储在已维数组A和B中,编写算法计算对称矩阵的乘积。
第 5 章 树和二叉树
6.已知一棵度为m的树中有:n1个度为1的结点,n2个度为2的结点,……,nm个度为m的结点,问该树中共有多少个叶子结点?
9.已知某字符串S中共有8种字符,各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次,对该字符串用[0,1]进行前缀编码,问该字符串的编码至少有多少位。
⑴ 设计算法求二叉树的结点个数。
⑵ 设计算法按前序次序打印二叉树中的叶子结点。
⑶ 设计算法求二叉树的深度。
⑷ 编写算法,要求输出二叉树后序遍历序列的逆序。
⑸ 以二叉链表为存储结构,编写算法求二叉树中结点x的双亲。
⑹ 以二叉链表为存储结构,在二叉树中删除以值x为根结点的子树。
⑺ 一棵具有n个结点的二叉树采用顺序存储结构,编写算法对该二叉树进行前序遍历。
⑻ 编写算法交换二叉树中所有结点的左右子树。
⑼ 以孩子兄弟表示法做存储结构,求树中结点x的第i个孩子。
1.前序遍历和中序遍历结果相同的二叉树是( )。 A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树【解答】D
11.现有按前序遍历二叉树的结果ABC,问有哪几种不同的二叉树可以得到这一结果?
12.试找出分别满足下列条件的所有二叉树: 【解答】图5-16所示树转换的二叉树如图5-18所示,图5-17所示二叉树转换的森林如图5-19所示。
14.以孩子兄弟表示法作为存储结构,编写算法求树的深度。
15.设计算法,判断一棵二叉树是否为完全二叉树。 |
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。