数据结构(习题三)

0 50 1 10 3 -30 1 20 3 -60 35
a[0] 0 0 50 a[1] 1 0 10 a[2] 1 2 20 a[3] 3 0 -30 a[4] 3 2 -60 a[5] 3 3 5
03 10 22 31
num
00 13 23 35
pos
0
TP3[处理三元组表]
3
FOR i ← 0 TO t-1 DO
20
A[4] 3
2
-60
A[5] 3 3
5
B[4] 2
3
-60
B[5] 3 3
5
算法的关键是求出A中元素在B中的位置
Bnubmer = 0
FOR i=0 TO Cols(A) DO
FOR j=0 TO t DO
IF col(A[j])=i Then
(row(B[Bnumber])=i
col(B[Bnumber])=row(A[j])
算法: TRANSPOSE(A. B)
TP1[初始化] /*声明A的转置矩阵B，使得B的行数等于 A的列数，B的列数等于A的行数，B中非 0元素的个数等于A中非0元素的个数*/ n←Rows(B)←Cols(A). Cols (B)←Rows(A). t←Count(B)← Count(A).
TP2
row(B[k]) ←col(A[i]).
val(B[k]) ← val(A[i]).
pos[p]← pos[p]+1 ).
a[0] 0 0 50 a[1] 1 0 10 a[2] 1 2 20 a[3] 3 0 -30 a[4] 3 2 -60 a[5] 3 3 5
0 0 50 0 1 10
2 1 20

《数据结构》习题库之三：判断题1. 程序就是算法，但算法不一定是程序。

（）2. 线性表只能采用顺序存储结构或者链式存储结构。

（）3. 线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。

（）4. 除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。

（）5. 稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。

（）6. 不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。

（）7. 确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。

（）8. 深度为h的非空二叉树的第i层最多有2i-1 个结点。

（）9. 满二叉树就是完全二叉树。

（）10. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。

（）11. 非空二叉排序树的任意一棵子树也是二叉排序树。

（）12. 对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。

（）13. 若有向图G=(V,E)的拓扑序列不唯一，则图中必须有两条弧和。

（）14. 散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。

（）15. 序列初始为逆序时，泡排序法所进行的元素之间的比较次数最多。

（）16. 算法一定要有输入和输出。

（）17. 算法分析的目的旨在分析算法的效率以求改进算法。

（）18. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。

（）19. 数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。

（）20. 线性链表中各个链结点之间的地址不一定要连续。

（）21. 若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。

（）22. 若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。

（）23. 若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。

（）24. 符号link(p)出现在表达式中表示p所指的那个结点的内容。

哈夫曼编码： a:11 b:101 c:010 d:1001 e:011 f:00 g:1000 2) 等长编码至少需要3 bit 哈夫曼编码WPL=0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4=2.61 压缩率=1-2.61/3=13% 4.程序设计题 1)创建一任意二叉树，统计某子树下值为奇数和偶数结点的个数。 #define INT #include"c1.h" #ifdef CHAR typedef char TElemType; TElemType Nil=' '; /* 字符型以空格符为空*/ #endif #ifdef INT typedef int TElemType; TElemType Nil=0; /* 整型以0为空*/ #endif #include"c6-2.h" #include"bo6-2.c" void GetLeafCounts(BiTree T,int *n,int *m) {
文档之家的所有文档均为用户上传分享文档之家仅负责分类整理如有任何问题可通过上方投诉通道反馈
数据结构习题三（答案）
数据结构习题(三) 学号________ 姓名_______ 课堂号(_________) 1.选择题 1)若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）A．9 B．11 C．15 D．不确定 2)设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林 F对应的二叉树根结点的右子树上的结点个数是（ D ） A．M1 B．M1+M2 C．M3 D．M2+M3 3)二叉树的第I层上最多含有结点数为（ C ） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 4)在一棵高度为k的满二叉树中，结点总数为（ C ） A．2k-1 B．2k C．2k-1 D．?log2k?+1 5)利用二叉链表存储树，则根结点的右指针是（ C ）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 6)已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果 为（ A ）。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 7)n个结点的线索二叉树上含有的线索数为（ C ） A．2n B．n－l C．n＋l D．n 8)由3 个结点可以构造出多少种不同的二叉树？（ D ） A．2 B．3 C．4 D．5 9)某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E。二叉树对应的森林 包括多少棵树（ B ） A．l B．2 C．3 D．概念上是错误的 10)设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针 域为空的结点有（ C ）个。 A． n-1 B．n C． n+1 D． n+2 11)下面几个符号串编码集合中，不是前缀编码的是（ B ）。 A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 2.填空题 12)树在计算机内的表示方式有__双亲表示法_，___孩子表示法___，___孩子兄弟表示法/ 二叉链表表示法_____。 13)在二叉树中，指针p所指结点为叶子结点的条件是_p->lchild==NULL && p->rchild==NULL________________。

int
data;
struct Lnode *next;
// 数据域 // 指针域
} LNode, *LinkList; LinkList la, lb； // 单链表的头指针 请用 la 和 lb 中的结点合并生成一个新的非 递增的有序单链表 lc。合并完成后，原来的 la 和 lb 成为空链表。
作者 (时间 2000年） 北京理工大学计算机科学工程系 秦怀青 email qinhq010@
正确且高效的算法如下： Status DeleteK（SqList &a ,int i, int k） {//设线性表元素从a.base[1]起存储,从第i个元素起
删除k个元素。
if ( i<1|| k< 0 || (i+k)>a.length) return ERROR;
for ( j=i+k;j<=a.length; ++j)
操作步骤
1) 建空表 Lc; 2) 依次从 La 或 Lb 中“摘取”元素值较小的
结点插入到 Lc 表中第一个结点之前直至其 中一个表变空为止; 3) 继续将 La 或 Lb 其中一个表的剩余结点插 入在 Lc 表的表头结点之后; 4) 释放 La 表和 Lb 表的表头结点。
作者 (时间 2000年） 北京理工大学计算机科学工程系 秦怀青 email qinhq010@
单链表中逻辑上相邻的元素的物理位置 不一定 紧邻。
（3）在单链表中，除了头结点外，任一结点的存储位置 由 该结点的直接前趋 指示。
（4）在单链表中设置头结点的作用是
在表的第一个元素结点之前插入新元素结点或删除 第一个元素结点不需修改头作指者 针(时间 2000年）