八叉树三维数据结构及示例程序

八叉树三维数据结构

（一）基本原理

用八叉树来表示三维形体，并研究在这种表示下的各种操作及应用是在进入80年代后才比较全面地开展起来的。这种方法，既可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。

八叉树的逻辑结构如下：

假设要表示的形体V可以放在一个充分大的正方体C内，C的边长为2 n，形体V C，它的八叉树可以用以下的递归方法来定义：

八叉树的每个节点与C的一个子立方体对应，树根与C本身相对应，如果V＝C，那么V 的八叉树仅有树根，如果V≠C，则将C等分为八个子立方体，每个子立方体与树根的一个子节点相对应。只要某个子立方体不是完全空白或完全为V所占据，就要被八等分（图

2-5-1），从而对应的节点也就有了八个子节点。这样的递归判断、分割一直要进行到节点所对应的立方体或是完全空白，或是完全为V占据，或是其大小已是预先定义的体素大小，并且对它与V之交作一定的“舍入”，使体素或认为是空白的，或认为是V占据的。

如此所生成的八叉树上的节点可分为三类：

灰节点，它对应的立方体部分地为V所占据；

白节点，它所对应的立方体中无V的内容；

黑节点，它所对应的立方体全为V所占据。

后两类又称为叶结点。形体V关于C的八叉树的逻辑结构是这样的：它是一颗树，其上的节点要么是叶节点，要么就是有八个子节点的灰节点。根节点与C相对应，其它节点与C 的某个子立方体相对应。

因为八叉树的结构与四叉树的结构是如此的相似，所以八叉树的存贮结构方式可以完全沿用四叉树的有关方法。因而，根据不同的存贮方式，八叉树也可以分别称为常规的、线性的、一对八的八叉树等等。

另外，由于这种方法充分利用了形体在空上的相关性，因此，一般来说，它所占用的存贮空间要比三维体素阵列的少。但是实际上它还是使用了相当多的存贮，这并不是八叉树的主要优点。这一方法的主要优点在于可以非常方便地实现有广泛用途的集合运算(例如可以求两个物体的并、交、差等运算)，而这些恰是其它表示方法比较难以处理或者需要耗费许多计算资源的地方。不仅如此，由于这种方法的有序性及分层性，因而对显示精度和速度的平衡、隐线和隐面的消除等，带来了很大的方便，特别有用。

（二）八叉树的存贮结构

八叉树有三种不同的存贮结构，分别是规则方式、线性方式以及一对八方式。相应的八叉树也分别称为规则八叉树、线性八叉树以及一对八式八叉树。不同的存贮结构的空间利用率及运算操作的方便性是不同的。分析表明，一对八式八叉树优点更多一些。

1、规则八叉树

规则八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字段用来描述该结点的特性(在目前假定下，只要描述它是灰、白、黑三类结点中哪一类即可)，其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存贮结构方式。

规则八叉树缺陷较多，最大的问题是指针占用了大量的空间。假定每个指针要用两个字节表示，而结点的描述用一个字节，那么存放指针要占总的存贮量的94％。因此，这种方法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。

2、线性八叉树

线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度第一的方式)，将八叉树转换成一个线性表（图2-5-2），表的每个元素与一个结点相对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，可以不用指针或者仅用一个指针表示即可。

线性八叉树不仅节省存贮空间，对某些运算也较为方便。但是为此付出的代价是丧失了一定的灵活性。例如为了存取属于原图形右下角的子图形对应的结点，那么必须先遍历了其余七个子图形对应的所有结点后才能进行；不能方便地以其它遍历方式对树的结点进行存取，导致了许多与此相关的运算效率变低。因此尽管不少文章讨论了这种八叉树的应用，但是仍很难令人满意。

3、一对八式的八叉树

一个非叶结点有八个子结点，为了确定起见，将它们分别标记为0，1，2，3，4，5，6，7。从上面的介绍可以看到，如果一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地假定了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的(例如，该结点已是叶结点)，那么相应的存贮位置也必须空闲在那里（图2-5-3），以保证不会错误地存取到其它同辈结点的记录。这样当然会有一定的浪费，除非它是完全的八叉树，即所有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非叶结点。

为了克服这种缺陷，有两条途径可以采纳。一是增加计算量，在记录中增加一定的信息，使计算工作适当减少或者更方便。

栅格数据压缩存储方式之四叉树、八叉树编码

四叉树编码(quad-tree code)

四又树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值(或灰度)。如果某个子区的所有格网值都具有相同的值。则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。

四叉树编码法有许多有趣的优点：①容易而有效地计算多边形的数量特征；②阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；②栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；④多边形中嵌套异类小多边形的表示较方便。

四叉树编码的最大缺点是转换的不定性，用同一形状和大小的多边形可能得出多种不同的四叉树结构，故不利于形状分析和模式识别。但因它允许多边形中嵌套多边形即所谓“洞”这种结构存在，使越来越多的地理信息系统工作者都对四叉树结构很感兴趣。上述这些压缩数据的方法应视图形的复杂情况合理选用，同时应在系统中备有相应的程序。另外，用户的分析目的和分析方法也决定着压缩方法的选取。

四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。

线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。

线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。

————————————————————————————————————————————

八叉树结构就是将空间区域不断地分解为八个同样大小的子区域(即将一个六面的立方体再分解为八个相同大小的小立方体)，分解的次数越多，子区域就越小，一直到同—区域的属性单一为止。按从下而上合并的方式来说，就是将研究区空间先按—定的分辨率将三维空间划分为三维栅格网，然后按规定的顺序每次比较3个相邻的栅格单元，如果其属性值相同则合并，否则就记盘。依次递归运算，直到每个子区域均为单值为止。

八叉树同样可分为常规八叉树和线性八叉树。常规八叉树的结点要记录十个位，即八个指向子结点的指针，—个指向父结点的指针和一个属性值(或标识号)。而线性八叉树则只需要记录叶结点的地址码和属性值。因此，它的主要优点是，其一节省存储空间，因为只需对叶结点编码，节省了大量中间结点的存储。每个结点的指针也免除了，而从根到某一特定结点的方向和路径的信息隐含在定位码之中，定位码数字的个位数显示分辨率的高低或分解程度；其次，线性八叉树可直接寻址，通过其坐标值则能计算出任何输入结点的定位码(称编码)，而不必实际建立八叉树，并且定位码本身就是坐标的另—种形式，不必有意去存储坐标值。若需要的话还能从定位码中获取其坐标值(称解码)；其三，在操作方面，所产生的定位码容易存储和执行，容易实现象集合、相加等组合操作。

八叉树主要用来解决地理信息系统中的三维问题。

#include "stdafx.h"

#include

#include

#include

#include

#include

#include "octree.h"

/* ------------------------------------------------------------------------ */ /* ------------------------------------------------------------------------ */

Vec3 makeVec3( double x, double y, double z)

{

Vec3 v3 = (Vec3) malloc(3 * sizeof(double));

v3[0] = x; v3[1] = y; v3[2] = z;

return v3;

}

Vec3 copyVec3( Vec3 src )

{

Vec3 v3 = (Vec3) malloc(3 * sizeof(double));

v3[0] = src[0]; v3[1] = src[1]; v3[2] = src[2];

return v3;

}

/* ------------------------------------------------------------------------ */

Octree* make_octree( Vec3 min, Vec3 max )

{

//Octree* o = (Octree*) malloc(sizeof(Octree));

Octree* o = new Octree;

o->min = copyVec3(min);

o->max = copyVec3(max);

o->children = 0;

o->at_max_depth = 0;

/*

printf("creating octree %.3lf,%.3lf,%.3lf ... %.3lf,%.3lf,%.3lf\n", o->min[2], o->min[1], o->min[0],

o->max[2], o->max[1], o->max[0] );

*/

return o;

}

void subpoint( Octree* o,int oc,Vec3 min, Vec3 max)

{

pvex_nor *m_p1,*m_p2;

POSITION pos1,pos2;

for(pos1=o->vex.GetHeadPosition(),pos2=o->normal.GetHeadPosition();pos1!=NULL;) {

//pos1=o->vex.FindIndex(i);//pos2=o->normal.FindIndex(i);

m_p1=(pvex_nor*)o->vex.GetNext(pos1);m_p2=(pvex_nor*)o->normal.GetNext(pos2);

if((m_p1->x>min[0]&&m_p1->xy>min[1]&&m_p1->yz>min[2]&&m_p1->z

{

o->children[oc]->vex.AddHead(new pvex_nor(m_p1->x,m_p1->y,m_p1->z));

o->children[oc]->normal.AddHead(new pvex_nor(m_p2->x,m_p2->y,m_p2->z));

}

}

}

void split_octree( Octree* o )

{

double oc_min[3];

double oc_max[3];

Vec3 mid = makeVec3( (o->min[0] + o->max[0]) * 0.5,

(o->min[1] + o->max[1]) * 0.5,

(o->min[2] + o->max[2]) * 0.5 );

int xp, yp, zp;

int oc = 0;

//o->children = (Octree**) malloc( 8 * sizeof(Octree*));

o->children = new Octree*;

for(zp=0; zp < 2; zp++)

{

if(zp == 0)

{

oc_min[2] = o->min[2];

oc_max[2] = mid[2];

}

else

{

oc_min[2] = mid[2];

oc_max[2] = o->max[2];

}

for(yp=0; yp < 2; yp++)

{

if(yp == 0)

{

oc_min[1] = o->min[1];

oc_max[1] = mid[1];

}

else

{

oc_min[1] = mid[1];

oc_max[1] = o->max[1];

}

for(xp=0; xp < 2; xp++)

{

if(xp == 0)

{

oc_min[0] = o->min[0];

oc_max[0] = mid[0];

}

else

{

oc_min[0] = mid[0];

oc_max[0] = o->max[0];

}

o->children[ (zp*4) + (yp*2) + xp ] = make_octree( oc_min, oc_max );

subpoint( o,(zp*4) + (yp*2) + xp,oc_min,oc_max);

}

}

}

}

/* ------------------------------------------------------------------------ */

int recursively_evaluate_octree( int min_depth, int max_depth, int current_depth, Octree* o ) {

int deepest_child = current_depth;

//int xp, yp, zp;

int oc;

int cd;

//pvex_nor *m_p;

//POSITION pos;

/*Vec3 point = makeVec3(0,0,0);

int p = 0;

for(zp=0; zp < 2; zp++)

{

point[2] = (zp == 0) ? o->min[2] : o->max[2];

for(yp=0; yp < 2; yp++)

{

point[1] = (yp == 0) ? o->min[1] : o->max[1];

for(xp=0; xp < 2; xp++)

{

point[0] = (xp == 0) ? o->min[0] : o->max[0];

o->value[ p++] = evaluate_point( point,o);

}

}

}

*/

o->density=evaluate1_point(o);

current_depth++;

o->not_fully_divided = (char) octree_needs_to_be_split( o );

if( current_depth <= max_depth )

{

if(( current_depth <= min_depth) || ( o->not_fully_divided ))

{

//if(deepest_child==current_depth||deepest_child==0)

//{

split_octree( o );

// }

for(oc = 0; oc < 8; oc++)

{

/*Vex.RemoveAll();

for( pos = vex[oc].GetHeadPosition(); pos != NULL; )

{

m_p=(pvex_nor*)vex[oc].GetNext( pos );

Vex.AddHead(new pvex_nor(m_p->x,m_p->y,m_p->z));

}*/

//if(deepest_child==current_depth||deepest_child==0)

//{

cd = recursively_evaluate_octree( min_depth, max_depth, current_depth, o->children[ oc ] );

//}

if(cd > deepest_child)

deepest_child = cd;

}

}

}

else

{

o->at_max_depth = 1;

}

return deepest_child;

}

/* ------------------------------------------------------------------------ */

int subdivide_octree( int min_depth, int max_depth, Octree* o )

{

return recursively_evaluate_octree(min_depth, max_depth, 0, o );

}

double demo1( Vec3 pos )

{

/* demo 1: the surface is a sphere of radius 0.75 centered at 0,0,0

function returns 1.0 if point inside sphere, 0.0 otherwise

*/

double dist_sq = (pos[0] * pos[0]) + (pos[1] * pos[1]) + (pos[2] * pos[2]);

return ( dist_sq < 0.5625 ) ? 1.0 : 0.0;

}

double demo2( Vec3 pos )

{

/* demo 2: the surface is two spheres,

A: radius 0.25 centered at -.25,-.5,0

and B: radius 0.5 centered at -0.5,0,0

function returns 1.0 if point inside sphere A, 2.0 for sphere B, 0.0 for neither

*/

double dist_sq_a = ((pos[0]+.25) * (pos[0]+.25)) + ((pos[1]+.5) * (pos[1]+.5)) + (pos[2] * pos[2]);

double dist_sq_b = ((pos[0]+.8) * (pos[0]+.8)) + (pos[1] * pos[1]) + (pos[2] * pos[2]);

if( dist_sq_a <= .0625 )

return 1.0;

if( dist_sq_b <= .25 )

return 2.0;

return 0.0;

}

double demo3( Vec3 pos )

{

/* demo 3: the surface is tiny sphere, radius 0.1 centered at -.5,.5,0

function returns 1.0 if point inside sphere A, 0.0 otherwise

*/

double dist_sq = ((pos[0]+.5) * (pos[0]+.5)) + ((pos[1]-.5) * (pos[1]-.5)) + (pos[2] * pos[2]); return ( dist_sq < 0.01 ) ? 1.0 : 0.0;

}

double demo4( Vec3 pos )

{

/* demo 4: wavey surface

function returns 1.0 if point 'near' surface , 0.0 otherwise

*/

double surface_height = sin( (pos[0] * 3.0) ) * cos ( (pos[1] * 3.0) );

double distance_sq = (pos[2] - surface_height) * (pos[2] - surface_height);

return ( distance_sq < 0.01 ) ? 1.0 : 0.0;

}

double demo5( Vec3 pos )

{

/* demo 5: hemisphere, center 0,0,0 radius 0.5, cut by plane at z=0

*/

double abs_dist_sq = ((pos[0]) * (pos[0])) + ((pos[1]) * (pos[1])) + (pos[2] * pos[2]);

double surf_dist_sq = abs_dist_sq - 0.5625;

if(surf_dist_sq < 0)

surf_dist_sq = -surf_dist_sq;

if( (pos[2] > 0) && (surf_dist_sq < 0.1 ))

return 1.0;

else

return .0;

}

double demo6( Vec3 pos )

{

/* demo 6: another wavey surface

function returns 1.0 if point 'near' surface , 0.0 otherwise

*/

double surface_height = sin( (pos[0] * 2.0) ) + sin ( (pos[1] * 2.0) );

double distance_sq = (pos[2] - surface_height) * (pos[2] - surface_height);

return ( distance_sq < 0.01 ) ? 1.0 : 0.0;

}

double demo7( Vec3 pos )

{

/* demo 7: a cylinder

function returns 1.0 if point 'near' surface , 0.0 otherwise

*/

double disc_dist_sq = ((pos[1]) * (pos[1])) + ((pos[2] * pos[2]));

double surf_dist_sq = disc_dist_sq - 0.5625;

if(surf_dist_sq < 0)

surf_dist_sq = -surf_dist_sq;

if( ( pos[0] > -0.75 ) && ( pos[0] < 0.75 ) ) {

if( surf_dist_sq < 0.1 )

return 1.0;

}

return 0.0;

}

double demo8( Vec3 pos )

{

/* demo8 : mandlebrot */

int max_iters = 500;

int it_count = 0;

double cr, ci, zr, zi, new_zr, new_zi;

int inside = 1;

/* only exists near the plane z=0 */

if((pos[2] > 0.001) || (pos[2] < -0.001))

return .0;

zr = cr = (pos[0] * 2.0);

zi = ci = (pos[1] * 2.0);

while((it_count < max_iters) && (inside)) {

/* z = z^2 + c */

it_count++;

new_zr = (zr*zr) - (zi*zi) + cr;

new_zi = (2*zr*zi) + ci;

zr = new_zr;

zi = new_zi;

inside = (zr * zr) + (zi * zi) < (2.0 * 20);

}

return (it_count == max_iters) ? 1.0 : 0.0;

}

double demo9( Vec3 pos, Octree *o)

{

pvex_nor *m_p1,*m_p2;

POSITION po;

double dis;

double zx,zy,zz,tempx,tempy,tempz,temp;

for(int i=0;ivex.GetCount();i++)

{

po=o->vex.FindIndex(i);

m_p1=(pvex_nor *)o->vex.GetAt(po);

m_p2=(pvex_nor *)o->normal.GetAt(po);

tempx=pos[0]-m_p1->x;tempy=pos[1]-m_p1->y;tempz=pos[2]-m_p1->z;

temp=tempx*m_p2->x+tempy*m_p2->y+tempz*m_p2->z;

zx=m_p1->x-temp*m_p2->x;zy=m_p1->y-temp*m_p2->y;zz=m_p1->z-temp*m_p2->z;

dis=sqrt((pos[0]-zx)*(pos[0]-zx)+(pos[1]-zy)*(pos[1]-zy)+(pos[2]-zz)*(pos[2]-zz));

//dis=sqrt((pos[0]-m_p1->x)*(pos[0]-m_p1->x)+(pos[1]-m_p1->y)*(pos[1]-m_p1->y) //+(pos[2]-m_p1->y)*(pos[2]-m_p1->y));

if(dis<0.1) goto loop;

}

loop:

return (dis<0.1) ? 1.0 : 0.0;

}

/* ------------------------------------------------------------------------ */

double evaluate_point( Vec3 pos,Octree *o )

{

return demo9( pos,o );

}

int evaluate1_point( Octree *o )

{

int tCnt=o->vex.GetCount()+1;

return(tCnt);

}

/* ------------------------------------------------------------------------ */

/* returns 1 if the octree should be split, 0 otherwise */

/*

this implementation checks whether all 8 corner values are the same

(if any corner 1..7 is different to corner 0 then the function returns 1) */

int octree_needs_to_be_split( Octree* o )

{

/*int i;

double v = o->value[0];

for(i=1; i < 8; i++)

if( o->value[i] != v)

return 1;

/* if we got here, then all corners have the same value */

//return 0;

if(o->density>40) return 1;

else return 0;

}

void isoface(Octree* o)

{

char bf[2];

//CPtrList vexlist,norlist;

float v1,v2,v3;

ifstream file("ww9.obj");

if(!o->vex.IsEmpty())

o->vex.RemoveAll();

if(!o->normal.IsEmpty())

o->normal.RemoveAll();

if(!file.fail())

{

while(!file.eof())

{

file>>bf>>v1>>v2>>v3;

if(bf[0]=='v'&&bf[1]==0)

o->vex.AddTail(new pvex_nor(v1,v2,v3));

if(bf[0]=='v'&&bf[1]=='n')

o->normal.AddTail(new pvex_nor(v1,v2,v3));

}

//o->vex=vexlist;

}

file.close();

}

/*

Linearly interpolate the position where an isosurface cuts

an edge between two vertices, each with their own scalar value

*/

Vec3 VertexInterp(double isolevel,Vec3 p1,Vec3 p2,double valp1,double valp2) {

double mu;

Vec3 p= makeVec3(0,0,0);

if (fabs(isolevel-valp1) < 0.00001)

return(p1);

if (fabs(isolevel-valp2) < 0.00001)

return(p2);

if (fabs(valp1-valp2) < 0.00001)

return(p1);

mu = (isolevel - valp1) / (valp2 - valp1);

p[0] = p1[0] + mu * (p2[0] - p1[0]);

p[1] = p1[1] + mu * (p2[1] - p1[1]);

p[2] = p1[2] + mu * (p2[2] - p1[2]);

return(p);

}

/*

Given a grid cell and an isolevel, calculate the triangular

facets required to represent the isosurface through the cell.

Return the number of triangular facets, the array "triangles"

will be loaded up with the vertices at most 5 triangular facets.

0 will be returned if the grid cell is either totally above

of totally below the isolevel.

*/

int Polygonise(GRIDCELL grid,double isolevel,TRIANGLE *triangles)

{

int i,ntriang;

int cubeindex;

Vec3 vertlist[12];

int edgeTable[256]={

0x0 , 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c, 0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00,

0x190, 0x99 , 0x393, 0x29a, 0x596, 0x49f, 0x795, 0x69c,

0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90,

0x230, 0x339, 0x33 , 0x13a, 0x636, 0x73f, 0x435, 0x53c,

0xa3c, 0xb35, 0x83f, 0x936, 0xe3a, 0xf33, 0xc39, 0xd30,

0x3a0, 0x2a9, 0x1a3, 0xaa , 0x7a6, 0x6af, 0x5a5, 0x4ac,

0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0,

0x460, 0x569, 0x663, 0x76a, 0x66 , 0x16f, 0x265, 0x36c,

0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60,

0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff , 0x3f5, 0x2fc,

0xdfc, 0xcf5, 0xfff, 0xef6, 0x9fa, 0x8f3, 0xbf9, 0xaf0,

0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55 , 0x15c,

0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950,

0x7c0, 0x6c9, 0x5c3, 0x4ca, 0x3c6, 0x2cf, 0x1c5, 0xcc ,

0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0,

0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc,

0xcc , 0x1c5, 0x2cf, 0x3c6, 0x4ca, 0x5c3, 0x6c9, 0x7c0,

0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c,

0x15c, 0x55 , 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650,

0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6, 0xfff, 0xcf5, 0xdfc,

0x2fc, 0x3f5, 0xff , 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0,

0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c,

0x36c, 0x265, 0x16f, 0x66 , 0x76a, 0x663, 0x569, 0x460,

0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac,

0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa , 0x1a3, 0x2a9, 0x3a0,

0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f, 0xb35, 0xa3c,

0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33 , 0x339, 0x230,

0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c,

0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99 , 0x190,

0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c,

0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0 }; int triTable[256][16] =

{{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1},

{3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},

{3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1}, {3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1}, {9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1}, {9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1}, {2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1}, {8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1}, {9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1}, {4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1}, {3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1}, {1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1}, {4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1}, {4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1}, {5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1}, {2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1}, {9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1}, {0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1}, {2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1}, {10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1}, {4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1}, {5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1}, {5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1}, {9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1}, {0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1}, {1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1}, {10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1}, {8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1},

{7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1},

{2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1}, {11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1}, {5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1}, {11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1}, {11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1}, {1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1}, {9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1}, {5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1},

{2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1}, {0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1}, {5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1}, {6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1}, {3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1},

{6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1}, {5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1}, {1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1}, {10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1},

{6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1},

{8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1},

{7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1},

{3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1}, {5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1}, {0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1}, {9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1}, {8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1}, {5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1}, {0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1},

{6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1}, {10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1}, {10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1},

{1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1}, {3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1},

{0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1}, {10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1}, {3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1}, {6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1},

{9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1},

{8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1},

{3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1}, {6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1}, {0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1}, {10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1}, {10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1},

{2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1},

{7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1}, {7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1}, {2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1},

{1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1}, {11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1}, {8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1},

{0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1}, {7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1}, {10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1}, {2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1}, {6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1}, {7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1}, {2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1}, {1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1}, {10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1}, {10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1}, {0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1},

{6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1}, {8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1}, {9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1}, {6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1}, {4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1}, {10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1}, {8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1}, {0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1},

{1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1}, {8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1}, {10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1}, {4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1}, {10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1}, {5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1}, {11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1}, {9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1}, {6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1}, {7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1}, {3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1},

{7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1}, {9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1},

{3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1},

{6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1},

{9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1}, {1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1},

{4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1}, {7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1}, {6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1}, {3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1}, {0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1}, {6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1}, {1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1}, {0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1}, {11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1}, {6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1}, {5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1},

{9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1}, {1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1},

{1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1},

{10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1}, {0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1}, {5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1}, {10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1}, {11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1},

{9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1},

{7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1},

{2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1}, {8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1},

{9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1}, {9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1},

{1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1}, {9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1}, {9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1}, {5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1}, {0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1}, {10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1}, {2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1},

{0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1}, {0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1},

{9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1},

{5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1}, {3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1},

{5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1},

{8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1}, {0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1},

{9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1}, {0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1}, {1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1}, {3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1}, {4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1}, {9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1}, {11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1},

数据结构树的有关算法

《数据结构》课程设计任务书 学期：11-12-2 班级：网络10 一、设计目的 《数据结构》是一门实践性较强的专业基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 二、设计要求 1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 2、学生必须仔细研读《数据结构》课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。 3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。 4、编程语言任选。 三、设计选题 题一：线索二叉树（**） 任务： 1.建立中序线索二叉树，并且中序遍历； 2.求中序线索二叉树上已知结点中序的前驱和后继； 需求分析和概要设计： 建立中序线索二叉树，并且中序遍历。首先就是要建立树，再将树中序线索化。求中序线索二叉树上已知结点中序的前驱和后继时，即是将树在遍历一遍。也可以在遍历的过程中，将树的结点放在数组中，当然必须讲述先遍历一遍，这是用空间来换时间。 详细设计： 树的结构体的声明： typedef char TElemtype; typedef enum PointerTag{Link,Thread}; //设置标志：Link为指针，Thread为线索typedef struct BiThrNode{ //树结点结构体 TElemtype data; struct BiThrNode *lchild,*rchild; PointerTag LTag,RTag; }BiThrNode,*BiThrTree; 相关函数的声明：

数据结构习题与答案

第 1 章绪论 课后习题讲解 1、填空 ⑴( )就是数据的基本单位,在计算机程序中通常作为一个整体进行考虑与处理。 【解答】数据元素 ⑵( )就是数据的最小单位,( )就是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素 【分析】数据结构指的就是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲,数据结构主要分为( )、( )、( )与( )。 【解答】集合,线性结构,树结构,图结构 ⑷数据的存储结构主要有( )与( )两种基本方法,不论哪种存储结构,都要存储两方面的内容:( )与( )。 【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 ⑸算法具有五个特性,分别就是( )、( )、( )、( )、( )。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 ⑹算法的描述方法通常有( )、( )、( )与( )四种,其中,( )被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 ⑺在一般情况下,一个算法的时间复杂度就是( )的函数。 【解答】问题规模 ⑻设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为( ),若为 n*log25n,则表示成数量级的形式为( )。 【解答】Ο(1),Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。 2、选择题 ⑴顺序存储结构中数据元素之间的逻辑关系就是由( )表示的,链接存储结构中的数据元素之间的逻辑关系就是由( )表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C,D 【分析】顺序存储结构就就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中的指针表示。

2020年智慧树知道网课《算法与数据结构》课后章节测试满分答案

绪论单元测试 1 【判断题】(1分) 学好算法与数据结构的关键在于多多实践。 A. 对 B. 错 第一章测试 1 【单选题】(1分) 数据结构是（） A. 一组性质相同的数据元素的集合 B. 一种数据类型 C. 数据的存储结构 D. 相互之间存在一种或多种特定关系的数据元素的集合 2

【单选题】(1分) 下列说法的是（） A. 数据在计算机存储器内的存在形式称为机外表示 B. 数据元素是数据的基本单位 C. 数据处理方式总是与数据的表示形式相联系 D. 数据是指描述客观事物的特征及活动所采用的符号形式 3 【判断题】(1分) 算法的描述方法只有语言方式。 A. 错 B. 对 4 【单选题】(1分) 下列关于算法说法的是（） A. 算法就是数学中的计算方法 B.

算法是指令的有限序列 C. 算法是对特定问题求解步骤的一种描述 D. 算法是在存储结构上的操作实现方法 5 【多选题】(1分) 有哪几种存储结构？ A. 链式存储方式 B. 散列存储方式 C. 索引存储方式 D. 顺序存储方式 6 【单选题】(1分) 算法的效率主要是指（） A. 其他选项都不对 B. 算法的空间效率

C. 算法的时间效率 D. 算法的空间效率和时间效率 7 【单选题】(1分) 在数据结构的讨论中把数据结构从逻辑上分为（） A. 静态结构与动态结构 B. 内部结构与外部结构 C. 紧凑结构与非紧凑结构 D. 线性结构与非线性结构 8 【单选题】(1分) 指出下列程序段的时间复杂度（） sum=1； for(i=0;sum

数据结构树的实现实验报告

数据结构设计性实验报告 课程名称_____ ____ 题目名称 学生学院 专业班级 学号 学生姓名 指导教师 2010 年 7 月 6 日

抽象数据类型：树的实现 一．需求分析 树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的内部结构。树的结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得广泛应用，如在编译程序中，可用树来表示源程序的语法结构，又如在数据库系统中，树形结构也是信息的重要组织形式之一。 二．实验目的 对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。 三．实验环境 1、硬件：PC机 2、软件：Microsoft Visual C++ 6.0 四．设计说明 本程序采用树的二叉链表（孩子指针-兄弟指针-双亲指针）存储表示，以下是树的结构定义和基本操作： ADT Tree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3, …,Dm(m>0)，对于任意j ≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有∈H; (3) 对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di 上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。 基本操作P： InitTree(&T); 操作结果：构造空树T。 DestroyTree(&T); 初始条件：树T存在。 操作结果：销毁树T。 CreateTree(&T,definition); 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 ClearTree(&T);

数据结构习题及参考答案 .

习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对

数据结构-树练习题

数据结构－树练习题 一、选择题 1、二叉树的深度为k，则二叉树最多有（ C ）个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 2、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。 A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。 A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为（ A ）。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。 A. 能 B. 不能 7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ C ）。 A. 3 B. 2 C. 4 D. 5 8、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（ C ）。 A. 67 B. 68 C. 69 D. 70 9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是（ B ）。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示（ C ）。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 13、表达式A*(B+C)/(D-E+F)的后缀表达式是（ C ） A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+ 14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 15、假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为（）个。 A. 15 B. 16 C. 17 D. 47 16、由权值为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A. 51 B. 23 C. 53 D. 74

《数据结构》程序填空复习题

《数据结构》程序填空复习题 说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题，黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。不能放弃其他内容的复习，切记！！！ 一、线性表 1.设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 #define NULL 0 void main( ) {NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16; d.data=4; /*d是尾结点*/ head= （1）; a.next=&b; b.next=&c; c.next=&d; （2）; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do {printf(“%d\n”, （3）); （4）; }while( （5）); } 答案： （1）&a （2）d next=NULL （3）p->data （4）p=p->next （5）p!=NULL 2. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点， struct node { int data; struct node *next; }; typedef struct node NODE int delete(NODE *head,int i ) {

NODE *p,*q; int j; q=head; j=0; while((q!=NULL)&&( ___(1)_____)) { ___(2)_____; j++; } if(q==NULL) return(0); p= ___(3)_____; ___(4)_____=p->next; free(___(5)_____); return(1); } 答案： （1）jnext （3）q->next （4）q->next （5）p 3.将新元素插入到线性表中的第i位，MAX是数组的个数，a[0]用以存放线性表长度，b存放待插入的元素值，i存放插入的位置，n存放线性表长度 { int a[MAX]; int i,j,b,n; scanf(“%d%d%d”,&b,&i,&n); for(j=1;j<=n;j++) scanf(“%d”,&a[j]); a[0]=n; for(j=n; （1）;j- -) （2）; （3）; （4）; for(j=1;j<=a[0];j++) printf(“%5d\n”,a[j]); } 答案： （1）j>=i （2）a[j+1]=a[j] （3）a[i]=b （4）a[0]=n+1

智慧树知道网课《数据结构(海南联盟)》课后章节测试满分答案

第一章测试 1 【单选题】(2分) 从一个二维数组b[m][n]中找出最大值元素的时间复杂度为 A. m*n B. m C. n D. m+n 2 【单选题】(2分) 在以下时间复杂度的数量级中，数量级最大的是 A. B. C. D.

3 【单选题】(2分) 下面程序段的时间复杂度为____________。for(inti=0;i

A. n(n+1)/2 B. n2 C. n(n+1) D. n2/2 5 【单选题】(2分) 线性结构是数据元素之间存在一种：（）。 A. 一对一关系 B. 多对多关系 C. 一对多关系 D. 多对一关系

6 【单选题】(2分) 数据结构中，与所使用的计算机无关的是数据的（）结构。 A. 物理和存储 B. 存储 C. 逻辑 D. 物理 7 【单选题】(2分) 算法分析的目的是：（）。 A. 研究算法中的输入和输出的关系 B. 找出数据结构的合理性 C. 分析算法的效率以求改进

D. 分析算法的易懂性和文档性 8 【单选题】(2分) 算法分析的两个主要方面是：（）。 A. 正确性和简明性 B. 空间复杂性和时间复杂性 C. 数据复杂性和程序复杂性 D. 可读性和文档性 9 【单选题】(2分) 计算机算法指的是：（）。 A. 调度方法 B.

树在数据结构中的简单应用

题目：树在数据结构中的简单应用树在数据结构中的简单应用

Simple Application of Tree In Data-structure 摘要 树形结构是一类重要的非线性结构.本文研究了树形数据结构的基础知识，包括相关定义、操作以及树在数据结构中的简单应用问题.主要运用图示以及相关的算法来研究树以及树在数据结构中的若干应用问题，如在编码问题中的应用、在查找算法中的应用等. 关键词:树;二叉树;数据结构;树的应用

ABSTRACT The construction of tree form is an important construction of not line. In this paper, we research the base knowledge of tree including some correlation definition, operation and the simple application of tree in data structure. We research tree and some application of tree in data structure by diagram and some correlative arithmetic, for example, in coding, in arithmetic and so on. Key words : Tree, Tree of two fork; Data construction; The tree's application 目录

数据结构和C++程序设计_题库

《数据结构》 Part1 一．选择 1. 组成数据的基本单位是（） A）数据项B）数据类型C）数据元素D）数据变量 2．算法分析的目的是（） A）找出数据结构的合理性B）研究算法的输入/输出关系 C）分析算法的效率以求改进D）分析算法的易读性 3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（） A）112 B）144 C）148 D）412 5．下面关于线性表的叙述中，错误的是（） A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元. C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适 A）单链表B）双链表C）顺序表D）循环链表 7．队列通常采用的两种存储结构是（） A）顺序存储结构和链式存储结构B）散列方式和索引方式 C）链表存储结构和线性存储结构D）线性存储结构和非线性存储结构 8．在一个单链表中，若删除p所指结点的后继结点，则执行（） A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next； C）p->next=p->next；D）p=p->next->next； 9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间 A）单链表B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表 10．按二叉树的定义，具有三个结点的二元树共有（）种形态。 A）3 B）4 C）5 D）6 11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12．深度为5的二叉树至多有（）个结点 A）16 B）32 C）31 D）10 13．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。 A）4 B）5 C）6 D）7 14．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（） A）n B）n+1 C）n-1 D）n/2 15．静态查找表和动态查找表二者的根本差别在于（）

树在数据结构中的简单应用

题目：树在数据结构中的简单应用

树在数据结构中的简单应用 Simple Application of Tree In Data-structure 摘要 树形结构是一类重要的非线性结构.本文研究了树形数据结构的基础知识，包括相关定义、操作以及树在数据结构中的简单应用问题.主要运用图示以及相关的算法来研究树以及树在数据结构中的若干应用问题，如在编码问题中的应用、在查找算法中的应用等.

关键词:树;二叉树;数据结构;树的应用 ABSTRACT The construction of tree form is an important construction of not line. In this paper, we research the base knowledge of tree including some correlation definition, operation and the simple application of tree in data structure. We research tree and some application of

tree in data structure by diagram and some correlative arithmetic, for example, in coding, in arithmetic and so on. Key words : Tree, Tree of two fork; Data construction; The tree's application 目录 摘要 (Ⅰ)

数据结构试题库答案

数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s

数据结构考试题库含答案

数据结构习题集含答案 目录

选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性

7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0;

数据结构程序设计题目共29题

目录 题目1：设计一元多项式简单计算 (1) 题目2：链表应用1 (1) 题目3：链表应用2 (1) 题目4：通讯录 (2) 题目5：停车场管理系统............................................. 错误！未定义书签。题目6：约瑟夫环 (3) 题目7：运动会分数统计 (3) 题目8：文学研究助手问题 (3) 题目9：银行业务模拟与离散事件模拟 (4) 题目10：学生信息管理系统任务（用顺序表/链表）.... 错误！未定义书签。题目11：文章编辑功能 .............................................. 错误！未定义书签。题目12：实验室管理.................................................. 错误！未定义书签。题目13：二叉树的基本操作（建立、求二叉树树深度、遍历）.. (4) 题目14：纸牌游戏任务 (5) 题目15：算术表达式求值 (5) 题目16：内部排序算法比较 (5) 题目17：哈夫曼树的构造和哈夫曼编码/译码 (6) 题目18：构造可以使n个城市连接的最小生成树 (7) 题目19：交通咨询系统中的最短路径 (7) 题目20：集合的交、并、差运算 ................................ 错误！未定义书签。题目21：长整数四则运算 (7) 题目22：机订票系统.................................................. 错误！未定义书签。题目23：图书管理系统 (8) 题目24：哈希表应用 (8) 题目25：模拟旅馆管理系统的一个功能——床位的分配与回收 (9) 题目26：地图着色问题 (9) 题目27：俄罗斯套娃问题 (10) 题目28：扫雷 (11) 题目29：用C语言设计一个日历系统 (11)

数据结构习题 树 数据机构c语言版

1.设二叉树bt 的存储结构如下，其中bt为树根结点指针，left，right分别为结 点的左、右孩子指针，dada为结点的数据域。请完成下列各题： 1）画出二叉树bt的逻辑结构 2）写出按先序、中序、后序遍历二叉树所得到的结点序列 3）画出二叉树bt的后序线索化树 1 2 3 4 5 6 7 8 9 10 2.二叉树结点数值采用顺序存储结构，如图所示， 1）画出二叉树表示 2）写出前序遍历，中序遍历和后序遍历的结果 3）写出结点值c的父结点，其左、右孩子。 4）画出将此二叉树还原成森林的图

3.已知一棵二叉树的中序序列为cbedahgijk，后序序列为cedbhjifa，画出该二叉 树的先序线索二叉树。 4.有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、 2、9，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点 的权的次序构造），求出每个字符的Huffman编码。 5.设给定权集w={2，3，4，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路 径长度WPL。 6.假设二叉树采用链接存储方式存储，编写一个中序遍历二叉树的非递归过程。 7.假设二叉树采用链接存储方式存储，root指向根结点，p所指结点为任一给定的 结点。编写一个求出从根结点到p所指结点之间路径的函数。 8.在二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先的算法，假 设值为x的结点不多于1个。 9.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的所有 结点数。 10.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的单孩 子结点数。

数据结构试题及答案

第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i

数据结构程序填空题

数据结构程序填空题 Last revision date: 13 December 2020.

数据结构程序填空题S设有一个头指针为head的不带头结点单向链表, 且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点 a的数据域相同）, 写出相关语句 答案 （1）q->next=head;（2）p=p->next;（3）q->next=p->next; 设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中结点a, （设链表中没有结点的数据域与结点a 的数据域相同）,写出相关语句 答案：（1）q->next=head (2) p=p->next; （3）q->next=p->next 设有一个不带头结点的单向链表，头指针为head，p、prep是指向结点类型的指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序 段是在该单向链表中查找这相邻两个结点，把该结点的数据域data打印 出来，并把其中之一从链表中删除，填写程序中的空格。 （1）p=p->next;（2）p->data或prep->data（3）p->next 设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表， 并输出链表中各结点中的数据。 答案：（1）&a（2）（3）p->data（4）p=p->next（5）p!=NULL

设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data。 答案：（1）p->data（2）p=p->next（3）p!=NULL 设线性表为（1，3，7，5），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 答：（1）&a（2）d->next=NULL（3）p->data（4）p=p->next（5）P指向NULL X 学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到n-1。数组元素按学号num由小到大有序排列，以下函数在a[0]到a[n-1] 中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记录的下标（数组元素的下标）。失败时返回-1，完成程序中的空格。 （1）low<=high（2）mid（3）a[mid].numleft（4）p=p->rig（5）p 以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查找到的树结点，不成功，则p指向为NULL），完成程序中的空格。

数据结构第三章 树 答案

数据结构与算法上机作业第三章树

一、选择题 1、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为 D A. 1 B. 2 C. 3 D. 4 2、深度为h的完全二叉树至少有 D 个结点，至多有 B 个结点 A. 2h B. 2h-1 C. 2h+1 D. 2h-1 3、具有n个结点的满二叉树有 C 个叶结点。 A. n/2 B. (n-1)/2 C. (n+1)/2 D. n/2+1 4、一棵具有25个叶结点的完全二叉树最多有 C 个结点。 A. 48 B. 49 C. 50 D. 51 5、已知二叉树的先根遍历序列是ABCDEF，中根遍历序列是CBAEDF，则后根遍历序列 是 A 。 A. CBEFDA B. FEDCBA C. CBEDFA D. 不定 6、具有10个叶结点的二叉树中有 B 个度为2的结点。 A. 8 B. 9 C. 10 D. 11 7、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满 足 C 。 A. 所有非叶结点均无左孩子 B. 所有非叶结点均无右孩子 C. 只有一个叶子结点 D. A和B同时成立 8、在线索二叉树中，t所指结点没有左子树的充要条件是 B 。 A. t->left=NULL B. t->ltag=TRUE C. t->ltag=TRUE且t->left=NULL D. 以上都不对 9、n个结点的线索二叉树上含有的线索数为 C 。 A. 2n B. n-1 C. n+1 D. n 10、二叉树按照某种顺序线索化后，任一结点都有指向其前驱和后继的线索，这种说法 B 。 A. 正确 B. 错误 C. 不确定 D. 都有可能 11、具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是 D 。 A. 2i B. 2i+1 C. 2i-1 D. 不存在 12、具有64个结点的完全二叉树的深度为 C 。 A. 5 B. 6 C.7 D. 8 13、将一颗有100个结点的完全二叉树从上到下、从左到右一次对结点进行编号，根结点的编号为1，则编号为45的结点的右孩子的编号为 D 。 A. 46 B. 47 C. 90 D. 91 14、在结点数为n的堆中插入一个结点时，复杂度为 C 。 A. O(n) B. O(n2) C. O(log2n) D. O(log n2) 15、两个二叉树是等价的，则它们满足 D 。 A. 它们都为空 B. 它们的左右子树都具有相同的结构 C. 它们对应的结点包含相同的信息 D. A、B和C 16、包含n个元素的堆的高度为 C 。（符号「a表示取不小a最小整数） A. n B. 「log2n C. 「log2(n+1) D. n+1 17、以下说法错误的是 B 。 A. 存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同 B. 二叉树是树的特殊情形

数据结构考试题库含参考答案

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的

6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】

2020智慧树知到《算法分析与设计》章节测试完整答案

2020智慧树知到《算法分析与设计》章节 测试完整答案 智慧树知到《算法分析与设计》章节测试答案 第一章 1、给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。 答案: 错 2、一个问题的同一实例可以有不同的表示形式 答案: 对 3、同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。 答案: 对 4、问题的两个要素是输入和实例。 答案: 错 5、算法与程序的区别是() A:输入 B:输出 C:确定性 D:有穷性 答案: 有穷性 6、解决问题的基本步骤是()。(1)算法设计(2)算法实现(3)数学

建模(4)算法分析(5)正确性证明 A:(3)(1)(4)(5)(2) B:(3)(4)(1)(5)(2) C:(3)(1)(5)(4)(2) D:(1)(2)(3)(4)(5) 答案: (3)(1)(5)(4)(2) 7、下面说法关于算法与问题的说法错误的是()。 A:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。 B:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。 C:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。 D:证明算法不正确，需要证明对任意实例算法都不能正确处理。 答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。 8、下面关于程序和算法的说法正确的是()。 A:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。 B:程序是算法用某种程序设计语言的具体实现。 C:程序总是在有穷步的运算后终止。 D:算法是一个过程，计算机每次求解是针对问题的一个实例求