当前位置：文档之家 › 数据结构 第5章

数据结构 第5章

  • 格式：ppt
  • 大小：1006.00 KB
  • 文档页数：62

下载文档原格式

  / 62

合集下载

数据结构第五章

数据结构第五章

2012年11月1日 13
2．三角矩阵 （1）上三角矩阵 即矩阵上三角部分元素是随机的，而下三角部分元素全部 相同（为某常数C或全为0），具体形式见图5-2（a）。 （2）下三角矩阵 即矩阵的下三角部分元素是随机的，而上三角部分元素全 部相同（为某常数C或全为0），具体形式见图5-2（b）。
2012年11月1日
2012年11月1日
12
5.3.1 特殊矩阵
2 3 1 A＝ 5 4 2 4 6 3
图5-1 一个对称矩阵
1．对称矩阵 若一个n阶方阵A中元素满足下列条件： aij=aji 其中0≤i, j≤n-1，则称A为对称矩阵。 例如，如图5-1所示是一个3×3的对称矩阵。
0
1
2
3
4
5
6
7
……
n ( n +1 ) 2
-3
n ( n +1 ) 2
-2
n ( n +1 ) -1 2
a00 a01 a02 a03 a04 a05 a06 a07
……
an-2n-2
an-2n-1
an-1n-1
2012年11月1日
（b）上三角矩阵的压缩存储形式 图5-5 对称矩阵及用上三角压缩存储
第5章 多维数组和广义表
本章学习内容
5.1 多维数组
5.2 多维数组的存储结构
5.3 特殊矩阵及其压缩存储
5.4 稀疏矩阵
5.5 广义表
2012年11月1日 1
5.1 多维数组
5.1.1 多维数组的概念
1．一维数组
一维数组可以看成是一个线性表或一个向量（第2章中 已经介绍），它在计算机内是存放在一块连续的存储 单元中，适合于随机查找。
数据结构第五章 数组与广义表

数据结构第五章 数组与广义表

an-1,n-1
压缩存储方法：只需要存储下三角 （含对角线）上的元素。可节省一 半空间。
可以使用一维数组Sa[n(n+1)/2]作为n阶对称矩阵A的存 储结构，且约定以行序为主序存储各个元素，则在Sa[k]和矩
阵元素aij之间存在一一对应关系： （下标变换公式）
i(i+1)/2 + j 当i≥j k = j(j+1)/2 + i 当i<j
q = cpot[col];
T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; ++cpot[col]; }
分析算法FastTransposeSMatrix的时间 复杂度：
for (col=1; col<=M.nu; ++col) … … for (t=1; t<=M.tu; ++t) … … for (col=2; col<=M.nu; ++col) … … for (p=1; p<=M.tu; ++p) … …
//对当前行中每一个非零元
处
brow=M.data[p].j;
理
if (brow < N.nu ) t = N.rpos[brow+1];
M
else { t = N.tu+1 }
的
for (q=N.rpos[brow]; q< t; ++q) { ccol = N.data[q].j; // 乘积元素在Q中列号
一、三元组顺序表
对于稀疏矩阵，非零元可以用三元组表示， 整个稀疏矩阵可以表示为所有非零元的三元组所 构成的线性表。例如：
数据结构答案 第5章 串学习指导

数据结构答案 第5章 串学习指导

第5章串5.1 知识点分析1．串的定义串（String）是由零个或多个任意字符组成的有限序列。

一般记作：s=＂a1 a2 …a i…a n＂。

其中s 是串名，用双引号括起来的字符序列为串值，但引号本身并不属于串的内容。

a i（1<=i<=n）是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数。

2．几个术语（1）长度串中字符的个数，称为串的长度。

（2）空串长度为零的字符串称为空串。

（3）空格串由一个或多个连续空格组成的串称为空格串。

（4）串相等两个串相等，是指两个串的长度相等，且每个对应字符都相等。

（5）子串串中任意连续字符组成的子序列称为该串的子串。

（6）主串包含子串的串称为该子串的主串。

（7）模式匹配子串的定位运算又称为串的模式匹配，是一种求子串的第一个字符在主串中序号的运算。

被匹配的主串称为目标串，子串称为模式。

3．串的基本运算（1）求串长：LenStr(s)。

（2）串连接：ConcatStr(s1,s2) 。

（3）求子串：SubStr (s,i,len)。

（4）串比较：EqualStr (s1,s2)。

（5）子串查找：IndexStr (s,t)，找子串t在主串s中首次出现的位置（也称模式匹配）。

（6）串插入：InsStr (s,t,i)。

（7）串删除：DelStr(s,i,len)。

4．串的存储（1）定长顺序存储。

（2）链接存储。

（3）串的堆分配存储。

5.2 典型习题分析【例1】下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储分析：空串是不含任何字符的串，即空串的长度是零。

空格串是由空格组成的串，其长度等于空格的个数。

答案为B。

【例2】两个串相等的充分必要条件是( )。

A．两个串长度相等B．两个串有相同字符C．两个串长度相等且有相同字符D．以上结论均不正确分析：根据串相等定义，两个串是相等是指两个串的长度相等且对应字符都相等，故A、B、C均不正确，答案为D。

数据结构 5数组和广义表A

数据结构 5数组和广义表A

12
1 Status Locate(Array A,va_list ap,int &off) 2{ 3 //若ap指示的各下标值合法，则求出该元素在A中，相对地
址off
4 off=0; 5 for(i=0;i<A.dim;++i) 6 { 7 ind=va_arg(ap,int); 8 if(ind<0||ind>A.bounds[i]) return OVERFLOW; 9 off+=A.constants[i] *ind; 10 } 11 return OK; 12 }
行数 总列数，即 第2维长度 元素个数
ij
补充：计算二维数组元素地址的通式
设一般的二维数组是A[c1..d1, c2..d2]，这里c1,c2不一定是0。
单个元素 长度
二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L
6
例1〖软考题〗：一个二维数组A[1..6, 0..7]，每个数组元素
16
5.4
1、定义：
广义表的定义
广义表是线性表的推广，也称为列表（lists） 记为： LS = ( a1 , a2 , ……， an ) 广义表名 表头(Head） 表尾 (Tail) n是表长
在广义表中约定：
① 第一个元素是表头，而其余元素组成的表称为表尾； ② 用小写字母表示原子类型，用大写字母表示列表。
13
1 Status Value(Array A,ElemType &e,…){ 2 //A是n维数组，e为元素变量，随后是n个下标值，若各下
标不超界，则e赋值为所指定的A的元素值，即将指定元素值 读到e变量中。
数据结构(c语言版)第五章答案

数据结构(c语言版)第五章答案

第五章1、设二维数组A【8】【10】是一个按行优先顺序存储在内存中的数组，已知A【0】【0】的起始存储位置为1000，每个数组元素占用4个存储单元，求：（1）A【4】【5】的起始存储位置。

A【4】【5】的起始存储位置为1000+（10*4+5）*4=1180；（2）起始存储位置为1184的数组元素的下标。

起始存储位置为1184的数组元素的下标为4（行下标）、6（列下标）。

2、画出下列广义表D=（（c），(e)，(a，(b，c，d))）的图形表示和它们的存储表示。

略，参考第5·2节应用题第5题分析与解答。

3、已知A为稀疏矩阵，试从时间和空间角度比较采用两种不同的存储结构（二维数组和三元组表）实现求∑a(i，j)运算的优缺点。

稀疏矩阵A采用二维数组存储时，需要n*n个存储单元，完成求∑ii a(1≤i≤n)时，由于a【i】【i】随机存取，速度快。

但采用三元组表时，若非零元素个数为t，需3t+3个存储单元（t个分量存各非零元素的行值、列值、元素值），同时还需要三个存储单元存储存稀疏矩阵A的行数、列数和非零元素个数，比二维数组节省存储单元；但在求∑ii a（1≤i≤n）时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。

4、利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间？当m行n列稀疏矩阵中非零元素个数为t，当满足关系3*t<m*n时，利用三元组存储稀疏数组时，才能节省存储空间。

5、求下列各广义表的操作结果。

（1）GetHead((a,(b,c),d))GetHead((a,(b,c),d))=a（2）GetTail((a,(b,c),d))GetTail((a,(b,c),d))=((b,c),d)（3）GetHead(GetTail((a,(b,c),d)))GetHead(GetTail((a,(b,c),d)))=(b,c)（4）GetTail(GetHead((a,(b,c),d)))GetTail(GetHead((a,(b,c),d)))=()第六章1、已知一棵树边的集合为{（i,m）,(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶结点？（3）哪个是g的双亲？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（10）以结点c为根的子树的深度是多少？（11）树的度数是多少？略。

数据结构第五章考试题库（含答案）

数据结构第五章考试题库（含答案）

第 5 章数组和广义表一、选择题为第一元素，其存储地址为1，1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11的地址为（）。

【燕山大学 2001 一、2 （2分）】每个元素占一个地址空间，则a85A. 13B. 33C. 18D. 402. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。

假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。

若按行存储，则A[2，4]的第一个字节的地址是（③）。

若按列存储，则A[5，7]的第一个字节的地址是（④）。

就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。

供选择的答案：【上海海运学院 1998 二、2 （5分）】①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120G. 156 H. 234 I. 276 J. 282 K. 283 L. 288⑤： A．行与列的上界相同 B. 行与列的下界相同C. 行与列的上、下界都相同D. 行的元素个数与列的元素个数相同3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。

A. BA+141B. BA+180C. BA+222D. BA+225【南京理工大学 1997 一、8 （2分）】4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。

【福州大学 1998 一、10 (2分)】A. 808B. 818C. 1010D. 10205. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

数据结构第5章课件 中国石油大学(华东)

数据结构第5章课件 中国石油大学(华东)

leftChild data rightChild
二叉链表
leftChild
data rightChild
22
二叉树的链表表示（三叉链表）
每个结点增加一个指向双亲的指针parent，使 得查找双亲也很方便。
leftChild data parent rightChild
三叉链表
data
leftChild
27
BinTreeNode *LeftChild (BinTreeNode *current ) { return (current != NULL )? current->leftChild :NULL; } BinTreeNode *RightChild (BinTreeNode *current ) { return ( current!= NULL) ? current->rightChild : NULL; } int Height( ){return Height(root);} int Size( ){return Size(root);} BinTreeNode *GetRoot ( ) const { return root; } void preOrder( ) {preOrder(root);} //前序遍历 void inOrder( ) {inOrder(root);} //中序遍历 void postOrder( ) {postOrder(root);} //后序遍历 void levelOrder( ) ; // 不需要递归，所以直接对外接 口调用即可。层序遍历 28
b
f
c
d
g
6
e
a
b.嵌套集合表示法： b 根据树的集合定义，写出集合划分。 { a, {b,{e},{f}}, {c}, {d,{g}} } e c d
数据结构预算法 第5章习题解答

数据结构预算法 第5章习题解答

（图 5-37）
④
③
0 1 2 3 4 5
1 2 3 4 5 6 ^
3 0 3
^ 2 4 ^ 5 ^
0 1
1 4 ^
3 ^
4）逆邻接表： 0 1 2 3 4 5 1 2 3 4 5 6 5）强连通分量：
1 4 1 0 2 2 ^ ^ 2 5 ^ 4 ^ 4 5 ^ ^
（2）设无向图 G 如图 5-38 所示，试给出： 1）该图的邻接矩阵； 2）该图的邻接表； 3）该图的多重邻接表； 4）从 V1 出发的“深度优先”遍历序列； 5）从 V1 出发的“广度优先”遍历序列。 【解答】 1） 该图的邻接矩阵： 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0
{if(p!=s) p->next=s->next; else (G->adjlist[e->adjvex].firstedge=s->next;)} if(s) free(s); break; } } for(i=v;i<G->n;i++) /*删除顶点值*/ {G->adjlist[i].vertex=G->adjlist[i+1].vextex; G->adjlist[i].first[i].firstedge=G->adjlist[i+1].firstedge; } } void DeleteArc(AALGraph *G,int v,int w) /*在图 G 中删除序号为 v,w 的顶点之的边*/ {EdgeNode *s,*p; s=G->adjlist[v].firstedge; p=s; for(;s;s=s->next); /*在与 m 邻接的点中找 n*/ {if(s->adjvex==w) /*若找到邻接点 n，则将该边从边表中脱出*/ {if(p!=s) p->next=s->next; else G->adjlist[v].firstedge=s->next; } if(s) free(s); /*释放要删除的边结点*/ } s=G->adjlist[w].firstedge;p=s; for(;s;p=s,s=s->next) /*在与 n 邻接的点中找 m*/ {if(s->adjvex==v) /*若找到邻接点 m，则将该边从边表中脱出*/ {if(p!=s) p->next=s->next; else G->adjlist[w].firstedge=s->next; } if(s) free(s); /*释放要删除的边结点*/ } G->e--; } （3）试以十字链表为存储结构实现算法设计题（1）中所列图的基本操作。 算法略。 （4）试以邻接多重表为存储结构实现算法设计题（1）中所列图的基本操作。 算法略。 （5）对于含有 n 个顶点的有向图，编写算法由其邻接表构造相应的逆邻接表。 【解答】 Void InvertAdjList(ALGraph G, ALGraph *H) /*由有向图的邻接表 G 建立其逆邻接表 H*/ {for (i=1;i<=n;i++) /*设有向图有 n 个顶点，建逆邻接表的顶点向量*/ {H[i]->vertex=G.adjlist[i].vertex; H->firstedge=NULL;} for (i=0; i<n; i++) /*邻接表转为逆邻接表*/ {p= G.adjlist[i].firstedge; /*取指向邻接表的指针*/ while (p!=null) {j=p->adjvex;
数据结构第五章习题答案

数据结构第五章习题答案

1.二维数组A行下标i的范围从1到12，列下标j的范围从3到10，采用行序为主序存储，每个数据存储元素占用4个存储单元，该数组的首地址（既A[1][3]的地址）为1200，则A[6][5]的地址为（D）A.1400B.1404C.1372D.13682.有一个M*N的矩阵A,若采用行序为主序进行顺序存储，每个元素占用8个字节，则A ij (1≤i≤M,1≤i≤N)元素的相对字节地址（相对首元素地址而言）为（B）A.((i-1)*N+j)*8B.((i-1)*N+j-1)*8C.(i*N+j-1)*8D.((i-1)*N+j+1)*83.稀疏矩阵一般的压缩存储方法有两种，即（D）A.二维数组和三维数组B.三元组和散列C.散列和十字链表D.三元组和十字链表4.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点(B)A.正确B.错误5.广义表（（a,b）,c,d)的表头是（C），表尾是（D）。

A.aB.bC.(a,b)D.(c,d)6.一个广义表的表头总是广义表，这个断言是（B）A.正确B.错误7.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是（326）8.有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1），则A[4][3]的地址是（14）9.一个广义表为（a,（a,b）,d,e,((i,j),k))，则该广义表的长度为（5），深度为（3）10.广义表((a),((b),c),(((d))))的表头是（（a）），表尾是（（((b),c),(((d)))））11.已知广义表A=（（a,b,c），（d,e,f）），则广义表运算head(tail(tail(A)))=(e)12.已知广义表GL=（a,(b,c,d),e），运用head和tail函数取出GL中的原子b的运算是（head(head(tail(GL)))）13.特殊矩阵和压缩矩阵哪一种压缩存储后会失去随机存取的功能？为什么？答：稀疏矩阵在进行压缩存储后会失去随机存取的功能，因为非零元素的位置没有办法确定。

数据结构 第五章树答案

数据结构 第五章树答案

第五章 树(答案)一、选择题1、二叉树的第i 层最多有（ ）个结点。

A ．2i B. 2i C. 2i-1 D.2i -12.对于一棵满二叉树，高度为h ，共有n 个结点，其中有m 个叶子结点，则（ ）A ．n=h+m B.h+m=2n C.m=h-1 D.n=2h -1 3.在一棵二叉树中，共有16个度为2的结点，则其共有（ ）个叶子结点。

A ．15 B.16 C.17 D.184. 一棵完全二叉树中根结点的编号为1，而且编号为23的结点有左孩子但没有右孩子，则此树中共有（ ）个结点。

A ．24 B.45 C.46 D.47 5.下述编码那一组不是前缀码（ ）A ．00,01,10,11 B.0,1,00,11 C.0,10,110,111 D.1,01,001,000 6.某二叉树的中序序列和后序序列相同，则这棵二叉树必然是（ ）A ．空树B ．空树或任一结点均无左孩子的非空二叉树C ．空树或任一结点均无右孩子的非空二叉树D ．空树或仅有一个结点的二叉树7.设n,m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 前的条件是（ ）A ．n 在m 的右边 B.n 是m 的祖先C ．n 在m 的左边 D.n 是m 的子孙8、假定中根遍历二叉树的定义如下：若二叉树为非空二叉树，则中根遍历根的右子树；访问根结点；中根遍历根的左子树。

按此定义遍历下图所示的二叉树，遍历的结果为： A 、 DBEAFHGC A B 、 C GHFADBE B C C 、 E BDAFHGC E D FD 、 FHGCADBE GH9、文中出现的字母为A 、B 、C 、D 和E ，每个字母在电文中出现的次数分别为9、27、3、5和11。

按哈夫曼编码（构造时左小右大），则字母C 的编码应是：A 、10B 、0110C 、1110D 、1100 10、设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8 11．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D ．12. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）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-G13．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE14．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A ．9B ．11C ．15D ．不确定15．树的后根遍历序列等同于该树对应的二叉树的( ).A. 先序序列B. 中序序列C. 后序序列16．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。

《数据结构与算法设计》第5章 树

《数据结构与算法设计》第5章 树


5.2.2 二叉树的性质
➢ 满二叉树和完全二叉树
满二叉树是指深度为h且节点数取得最大值2h-1的二叉树。 如果一棵深度为h的二叉树，除第h层外，其他每层的节点数 都达到最大，且最后一层的节点自左而右连续分布，这样的二 叉树称为完全二叉树。
5.2.2 二叉树的性质
5.2.2 二叉树的性质
性质6 对含有n个节点的完全二叉树自上而下、同一层从左往右 对节点编号0,1,2,…,n-1，则节点之间存在以下关系： （1）若i=0，则节点i是根节点，无双亲；若i>0，则其双亲节 点的编号为i/2-1； （2）若2×i +1≤n，则i的左孩子编号为2×i+1； （3）若2×i+2≤n，则i的右孩子编号为2×i+2； （4）若i>1且为偶数，则节点i是其双亲的右孩子，且有编号为 i-1的左兄弟； （5）若i<n-1且为奇数，则节点i是其双亲的左孩子，且有编号 为i+1的右兄弟。
5.3.3 二叉树的二叉链表类模板定义
//根据二叉树的先序遍历序列和中序遍历序列创建以r为根的二叉树
void CreateBinaryTree(BTNode<DataType> * &r, DataType pre[], DataType
in[], int preStart, int preEnd, int inStart, int inEnd); int Height(BTNode<DataType> *r); //求以r为根的二叉树高度 //求以r为根的二叉树中叶子节点数目
5.1.2 树的术语
（9）节点的层次：从根节点开始，根为第一层，根的孩子为 第二层，根的孩子的孩子为第三层，依次类推，树中任一节 点所在的层次是其双亲节点所在的层次数加1。 （10）堂兄弟：双亲在同一层的节点互为堂兄弟。

《数据结构》第五章习题参考答案

《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。

( ×)2、二叉树的左右子树可任意交换。

（×）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。

（√）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。

（√）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

( ×)6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。

( √)7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

（×）8、度为2的树就是二叉树。

（×）二、单项选择题1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。

A．8 B．9 C．10 D．112．树的后根遍历序列等同于该树对应的二叉树的( B )。

A. 先序序列B. 中序序列C. 后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。

该二叉树根的右子树的根是：( C )A. EB. FC. GD. H04、在下述结论中，正确的是（ D ）。

①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐；②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。

A．①②③B．②③④C．①②④D．①④5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。

A．空或只有一个结点B．完全二叉树C．二叉排序树D．高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。

2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。

数据结构第五章


5.3.1 特殊矩阵
是指非零元素或零元素的分布有一定规律的矩阵。
1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij = aji 0≦i,j≦n-1 则称A为对称矩阵。
对称矩阵中的元素关于主对角线对称，故只 要存储矩阵中上三角或下三角中的元素，这样， 能节约近一半的存储空间。

2013-7-25 第4章 18
5.3 矩阵的压缩存储

在科学与工程计算问题中，矩阵是一种常用 的数学对象，在高级语言编制程序时，常将 一个矩阵描述为一个二维数组。 当矩阵中的非零元素呈某种规律分布或者矩 阵中出现大量的零元素的情况下，会占用许 多单元去存储重复的非零元素或零元素，这 对高阶矩阵会造成极大的浪费。 为了节省存储空间，我们可以对这类矩阵进 行压缩存储：
5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的， 因此用一维内存来表示多维数组，就必 须按某种次序将数组元素排成一列序列 ，然后将这个线性序列存放在存储器中 。 又由于对数组一般不做插入和删除 操作，也就是说，数组一旦建立，结构 中的元素个数和元素间的关系就不再发 生变化。因此，一般都是采用顺序存储 的方法来表示数组。
即为多个相同的非零元素只分配一个存储空间； 对零元素不分配空间。


课堂讨论： 1. 什么是压缩存储？ 若多个数据元素的值都相同，则只分配一个元素值的 存储空间，且零元素不占存储空间。 2. 所有二维数组（矩阵）都能压缩吗？ 未必，要看矩阵是否具备以上压缩条件。 3. 什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵， 稀疏矩阵等。 4. 什么叫稀疏矩阵？ 矩阵中非零元素的个数较少（一般小于5%）
通常有两种顺序存储方式：
⑴行优先顺序——将数组元素按行排列，第i+1个行 向量紧接在第i个行向量后面。以二维数组为例，按 行优先顺序存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存 储的。 ⑵列优先顺序——将数组元素按列向量排列，第j+1 个列向量紧接在第j个列向量之后，A的m*n个元素按 列优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。

数据结构第五章参考答案

习题51.填空题（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________）。

答案：129（2）3个结点可构成（___________）棵不同形态的二叉树。

答案：5（3）设树的度为5，其中度为1~5的结点数分别为6、5、4、3、2个，则该树共有（___________）个叶子。

答案：31（4）在结点个数为n（n>1）的各棵普通树中，高度最小的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。

高度最大的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。

答案：2 n-1 1 n 1 n-1（5）深度为k的二叉树，至多有（___________）个结点。

答案：2k-1（6）（7）有n个结点并且其高度为n的二叉树的数目是（___________）。

答案：2n-1（8）设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（___________），最小结点数为（___________）。

答案：2k+1-1 k+1（9）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT （X）的编号为（）。

答案：24（10）已知一棵完全二叉树中共有768个结点，则该树中共有（___________）个叶子结点。

答案：384（11）（12）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（___________）。

答案：68（13）深度为8（根的层次号为1）的满二叉树有（___________）个叶子结点。

答案：128（14）一棵二叉树的前序遍历是FCABED，中序遍历是ACBFED，则后序遍历是（___________）。

答案：ABCDEF（15）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为（___________），该二叉树对应的树林包括（___________）棵树。

数据结构课后习题答案第五章数组与广义表

第五章数组与广义表一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000。

计算：1、数组A的体积（即存储量）；2、数组A的最后一个元素a57的第一个字节的地址；3、按行存储时，元素a14的第一个字节的地址；4、按列存储时，元素a47的第一个字节的地址；答案：1、（6*8）*6=2882、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。

问下列元素的存储地址是什么？（1）a0000(2)a1111(3)a3125 (4)a8247答案：（1）100（2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776(3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784(4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m 充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。

试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。

答：K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i=(i-1)(n+(n-i+2))/2+j-i所以f1(i)=(n+1/2)i-1/2i2f2(j)=jc=-(n+1)九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成∑aii运算的优缺点。

（对角线求和）解：1、二维数组For(i=1;i<=n;i++)S=s+a[i][i];时间复杂度：O（n）2、for(i=1;i<=m.tu;i++)If(a.data[k].i==a.data[k].j) s=s+a.data[k].value;时间复杂度：O（n2）二十一、当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。

数据结构 第5章_递归


2 m=Fibona(2)+Fibona(1); 1 return(m);
(13)
1
(15)
S3
(8) 2
m=Fibona(2)+Fibona(1);
(9)
(10)
1
(14)
return(1)
return(m);
return(1)
return(1)
(4)
return(1)
(5) 1
(6)
(7) 1 Fibona(5)的执行过程
退出
5.3 递归程序到非递归程序的转换
采用递归方式实现问题的算法程序具有结构清 晰、可读性好、易于理解等优点，但递归程序较之 非递归程序无论是空间需求还是时间需求都更高， 因此在希望节省存储空间和追求执行效率的情况下， 人们更希望使用非递归方式实现问题的算法程序； 另外，有些高级程序设计语言没有提供递归的 机制和手段，对于某些具有递归性质的问题（简称 递归问题）无法使用递归方式加以解决，必须使用 非递归方式实现。因此，本小节主要研究递归程序 到非递归程序的转换方法。
退出
例5 采用非递归方式实现求正整数n的阶乘值。 仍使用Fact(n)表示n的阶乘值。要求解Fact(n) 的值，可以考虑i从0开始，依次取1,2,……，一直到n， 分别求Fact(i)的值，且保证求解Fact(i)时总是以前 面已有的求解结果为基础；当i=n 时，Fact(i)的值即 为所求的Fact(n)的值。
退出
排列问题
设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。
设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加 上前缀得到的排列。R的全排列可归纳定义如下：

数据结构第五章 数组和广义表


5.3.1
特殊矩阵
1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij = aji 1≤i,j≤n 则称A为对称矩阵。 a11 1 5 1 3 7 a21 a 22 5 0 8 0 0 a31 a32 a33 1 8 9 2 6 ……………….. 3 0 2 5 1 an 1 a n 2 a n 3 …a n n 7 0 6 1 3
第5章
数组和广义表
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
5.4 广义表的定义
5.1 数组的定义
数组-----线性表的扩展 A =(a0,a1,a2,…，an-1)
a00 a10 ┇ Am×n= ai0 ┇ am-1,0 a01 … a0j … a11 … a1j … ┇ ai2 … aij … ┇ am-1,2 … am-1,j … a0,n-1 a1,n-1 ai,n-1 am-1,n-1 α0 α1 ┇ Am×n= α i ┇ α m-1
Assign( &A, e, index1, ..., indexn) 赋值操作 初始条件：A是n维数组,e为元素变量,随后是n个下标值。 操作结果：若下标不超界,则将e的值赋给所指定的A的元 素,并返回OK。 对于数组来说一旦维数确定了，每个元素的下标确定了, 那么整个数组就确定了，这样的一个数组结构除了能改变 某元素的值，其他的不能再改变。
5.2 数组的顺序表示和实现
数组类型特点: 1) 只有引用型操作，没有加工型操作; 2) 数组是多维的结构，而存储空间是一个一维的结构。 有两种顺序映象的方式。
有两种顺序映像方法： 1）以行序为主序(行优先，先行后列)：先存储行号较小 的元素，行号相同者先存储列号较小的元素；
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

基本操作： （1） InitArray(A, n, bound1, …, boundn)： 若维数n和各维 的长度合法，则构造相应的数组A，并返回TRUE。 （2） DestroyArray（A）： 销毁数组A。 （3） GetValue（A，e, index1, …, indexn）： 若下标合法， 则用e返回数组A中由index1, …, indexn所指定的元素的值。
图5.9 带状矩阵的压缩形式
2.确定非零元素在一维数组空间中的位置
Loc［i , j］ = Loc［1, 1］+前i-1行非零元素个数+第i行中aij前非零元素个数；

前i-1行元素个数=3×（i-1）-1（因为第1行只有2个非零元素）； 第i行中aij前非零元素个数=j-i+1，其中
-1 (j<i) j-i= 0 (j=i) 1 (j>i) 由此得到 Loc［i, j］=Loc［1, 1］+3(i-1)-1+j-i+1
Loc[ j1 , j2 ,, jn ] Loc[c1 , c2 ,cn ] ai ( ji ci )
i 1
n
其中
ai 1 (d k ck 1)
k i 1
n
(1≤i≤n)。
5.3 特殊矩阵的压缩存储
5.3.1 三角矩阵
三角矩阵大体分为三类：下三角矩阵、上三角矩阵和对称矩阵。对于
Loc［j1, j2, j3］=Loc［c1, c2, c3］+α1×(j1-c1)+α2×(j2-c2)+α3(j3-
c3)=Loc［c1, c2, c3］+∑αi×(ji-ci)（1 Nhomakorabeai≤3）
由公式可知Loc［j1, j2, j3］与j1, j2, j3呈线性关系。 对于ｎ维数组A(c1∶d1, c2∶d2 ，…, cn∶dn)，我们只要把 上式推广，就可以容易地得到ｎ维数组中任意元素aj1j2…jn的 存储地址的计算公式:
a242，a342
以上的存放规则可推广到多维数组的情况。总之，知道了 多维数组的维数，以及每维的上下界，就可以方便地将多维数 组按顺序存储结构存放在计算机中了。同时，根据数组的下标， 可以计算出其在存储器中的位置。因此，数组的顺序存储是一 种随机存取的结构。
以二维数组Am×n 为例，假设每个元素只占一个存储单元，
教学重点与教学难点：
三角矩阵的压缩存储； 稀疏矩阵的压缩存储及其转置运算。
5.1 数组的定义和运算
图5.1 Am×n的二维数组
图5.2 矩阵Am×n看成n个列向量的线性表
图5.3 矩阵Am×n看成m个行向量的线性表
以上我们以二维数组为例介绍了数组的结构特性，实际 上数组是一组有固定个数的元素的集合。也就是说，一旦定
第5章 数组和广义表
5.1 数组的定义和运算
5.2 数组的顺序存储和实现
5.3 特殊矩阵的压缩存储
5.4 广义表
教学目的与要求： 掌握三角矩阵的概念及其在计算机中的存储方法； 掌握稀疏矩阵的概念及其在计算机中的存储方法； 掌握稀疏矩阵的运算，如转置等； 了解本章内容在数据结构中的作用，及其在数值分析 中的应用。
m
n
r
n m
k －1
图5.5 三维数组看成r个m×n的二维数组
j－1
假定每个元素占一个存储单元，采用以行为主序的方法存 放，即行下标r变化最慢， 纵下标n变化最快。 首元素a111的地
址为Loc［1, 1, 1］，求任意元素aijk的地址。
显然 ， ai11 的 地 址为 Loc［ i, 1, 1］=Loc［1, 1, 1］+(i1)×m×n， 因为在该元素之前， 有ｉ-１个ｍ×ｎ的二维数组。 由ai11 的地址和二维数组的地址计算公式，不难得到三维数组 任意元素aijk的地址：
为主显然，二维数组Am×n以行为主的存储序列为：
a11, a12, …，a1n, a21, a22, …, a2n, …, am1, am2, …, amn
而以列为主的存储序列为：
a11, a21, …，am1，a12, a22, …, am2, …, a1n, a2n, …, amn
假设有一个3×4×2的三维数组A ，共有24个元素，其
Loc［i, j］=Loc［1, 1］+前i-1行非零元素个数+第i行中aij 前非零元素个数前。i-1行元素个数=1+2+3+4+…+（i-1）=i(i1)/2，第i行中aij前非零元素个数=j-1，所以有 Loc［i, j］=Loc［1, 1］+i(i-1)/2+j-1 同样，对于上三角矩阵，也可以将其压缩存储到一个大小 为n(n+1)/2的一维数组C中。其中元素aij(i<j)在数组C中的存储 位置为：
义了数组的维数和每一维的上下限，数组中元素的个数就固
定了。 例如二维数组A3×4，它有3行、4列，即由12个元素组 成。由于这个性质，使得对数组的操作不像对线性表的操作 那样可以在表中任意一个合法的位置插入或删除一个元素。 对于数组的操作一般只有两类：
(1） 获得特定位置的元素值；
(2） 修改特定位置的元素值。
根据计算公式，可以方便地求得aij的地址是Loc［i, j］。如果 每个元素占size个存储单元，则任意元素aij的地址计算公式为： Loc［i, j］=Loc［1, 1］ + (n×(i-1)+j-1)×size 三维数组A（1..r , 1..m , 1..n）可以看成是r个m×n的二维数 组， 如图5.5所示。
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-1
2. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组 T[1..N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1
第1行： 1个 第2行： 2个 第3行： 3个 … … 第n行： n个 1+2+3+4+5+…+n=n(n+1)/2
所以可压缩存储到一个大小为n(n+1)/2的一维数组C中，如图5.7 所示。
Loc(1,1)
Loc(i,j)
图5.7 三角矩阵的压缩形式
下三角矩阵中元素aij(i>j)在一维数组A中的位置为(设每个元素占一个字节）：
0 0 12 9 0 0 0 0 3 0 0 0 M 0 0 24 0 0 18 0 0 15 0 0 7
0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 67 0 0
6 1 1 3
1 2 3 4 5 6 7 8
Loc［i, j, k］=Loc［1, 1, 1］+(i-1)×m×n+(j-1)×n+(k-1)
其中1≤i≤ｒ，1≤j≤ｍ， 1≤k≤ｎ。
如果将三维数组推广到一般情况，即：用j1 、j2 、j3 代替数
组下标i、j、k， 并且j1、j2、j3的下限为c1、c2、c3，上限分别 为d1、 d2、d3，每个元素占一个存储单元，则三维数组中任意
3. 假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元
素A9,9在B中的存储位置k=_______。（注：矩阵元素下标从1开始）【北京工商大
学 2001 】
5.3.2 带状矩阵
图5.8 带状矩阵A 三对角带状矩阵有如下特点：
i=1, j=1, 2;
当 1<i<n, j=i-1, i, i+1; i=n, j=n-1, n;
时，aij非零，其它元素均为零。
1.确定存储该矩阵所需的一维向量空间的大小 在这里我们假设每个非零元素所占空间的大小为1个单元。 从图中观
察得知，三对角带状矩阵中，除了第一行和最后一行只有2个非零元素外，
其余各行均有3个非零元素。由此得到， 所需一维向量空间的大小为2+2+3 （n-2）=3n-2，如图5.9所示。
一个n阶矩阵A来说，若当i<j时，有aij=0，则称此矩阵为下三角矩阵；若 当i>j时，有aij=0，则称此矩阵为上三角矩阵；若矩阵中的所有元素均满足
aij=aji，则称此矩阵为对称矩阵。
图5.6 下三角矩阵A
对于下三角矩阵的压缩存储，只存储下三角的非零元素，对于零元素
则不存。我们按“行序为主序”进行存储，得到的序列是a11, a21, a22, a31, a32, a33, …, an1, an2, …, ann。由于下三角矩阵的元素个数为n(n+1)/2，即：
（下标从1开始）采用以行为主序的方法存放，即行下标变
化最慢，纵下标变化最快，则顺序为： a111，a112，a121，a122， …，a331，a332，a341，a342 采用以纵为主序的方法存放， 即纵下标变化最慢， 行下 标变化最快， 则顺序为：
a111 ，a211 ，a311 ，a121 ，a221 ，a321，…，a132，a232 ，a332 ，a142 ，
“以行为主”存放数组，下标从1开始，首元素a11 的地址为 Loc［1, 1］，求任意元素aij的地址。aij是排在第i行，第j列， 并且前面的第i-1行有n×（i-1）个元素，第ｉ行第j个元素前 面还有ｊ-１个元素。由此得到如下地址计算公式： Loc［i, j］=Loc［1, 1］+n×(i-1)+(j-1)
3 4