河南理工大学数据
结构实验报告
篇一：《数据结构》第四章习题参考答案
《数据结构》第四章习题
一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）
1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。
2、串是一种数据对象和操作都特殊的线性表。
3、只包含空白字符的串称为空串（空白串）。
4、稀疏矩阵压缩存储后，必会（不会）失去随机存取功能。
5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。
6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数----------------精选公文范文----------------
1
---------------------------------精选公文范文--------------------------
组中
也经常使用。（ ×）
7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换（错 的），就完成了对该矩阵的转置运算。（×）
二、单项选择题
1．下面关于串的的叙述中，哪一个是不正确的？（ B ）
A．串是字符的有限序列 B．空串是由空格构成的串（空串是长度为零的串）
C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储
2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con返回x和y串的连接串，subs
返回串s的从序号i的字符开始的j个字符组成的子串，len返回中s的长度，则
----------------精选公文范文----------------
2
---------------------------------精选公文范文--------------------------
con),subs,2))的结果串是（ D ）。 A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG 3、串的长度是指（ B ）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数 三、填空题
1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储 _、__ 链式存储 _；两个串相等的
充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。 2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为
_O__。
3、模式串P=‘abaabcac’的next函数值序列为___。
----------------精选公文范文----------------
3
---------------------------------精选公文范文--------------------------
4、已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储
在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为__1340___。 四、综合题
1、KMP算法较Brute-Force算法有哪些改进? 解答
朴素的模式匹配（Brute－Force）时间复杂度是O（m*n），KMP算法有一定改进，时间复杂度达到O（m＋n）。KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。 2、课本P183 题 解答
A[2][2] = 644+2*n+2 = 676 A[3][3] = 644+3*n+3 = 692 3、课本P184 题 解答
----------------精选公文范文----------------
4
---------------------------------精选公文范文--------------------------
三元组表：row = 6, col = 7, terms = 9 {,,,,,,, }
行指针数组[0，3，4，6，-1，7]二元组{,,,,,,,, }
4、课本P184 题 解答
s: next[-1,0，0,1] t: next[-1,0,0,0,1,2,1] r: next[-1,0,0,0,0,1,1,2,0,1,2,3,1,2,1,1,0,0,1,0,0]
5、课本P184 题 解答略
篇二：河南理工大学数据库考试填空和简答
1 数据库系统一般由以下五个部分组成：数据库 数据库管理系统 数据库管理员 应用系统 和 用户。
1. 数据模型通常由 数据结构 数据操作 完整性约束 三部分组成。 2. 在数据库设计的几个阶段中， 数据库概念设计 是数据库设计的关----------------精选公文范文----------------
5
---------------------------------精选公文范文--------------------------
键。
3.数据恢复的基本原理用一个词来概括就 冗余。
4.完整性约束包括 试题完整性 参照完整性 和 用户定义完整性。 5.并发控制的主要技术是—封锁。 6.数据库的完整性是指数据的正确性和相容性。
7.数据独立性包括数据逻辑独立性和数据物理独立性。
8.数据依赖是指实体内部各属性值之间的相互依赖又相互制约的关系。 9.数据转储从转储的状态来分，可分为静态转储和动态转储：从备份的数据量来分，可分为海量转储和增量转储。 简答题
1.数据库系统的主要特点如下：1）数据结构化 2）数据共享性高，冗余度低，易扩充 3）数据独立性高 4）由 DBMS 统一管理和控制。与文件系统的根本区别是数据结构化。 2.基表是实际存在的表，拥有实际存----------------精选公文范文----------------
6
---------------------------------精选公文范文--------------------------
储的数据，在SQL中，一个关系对应一个基表。而视图是在基表或视图之上导出的，是个虚表，并没有实际存储的数据。基表是构成模式内容的基本单位，而视图是构成外模式内容的基本单位。它们的区别和联系：基表和视图一经定义，均可用于查询；他们之上都可再定义视图；基表一经删除，其上的视图也无所依存。
3:所谓事务是指用户定义的一个数据库操作薛烈，这些操作要么不做，要么全做，是一个不可分割的工作单位。 事务的四个特性：原子性，一致性，隔离性，持续性。
4所谓两端锁协议就是所有事务必须分两个阶段对数据项加锁和解锁。在对任何数据进行读写操作之前，首先要申请并获得对该数据的封锁。在释放一 个封锁之后，事务不再申请和获得任何其他封锁。
区别联系：一次封锁法要求每个事务必须一次将所有要使用的数据全部加----------------精选公文范文----------------
7
---------------------------------精选公文范文--------------------------
锁，它遵守两段锁协议，但两段锁协议并不要求事务必须一次将所有要使用 的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁。
5数据库运行中可能产生的故障有哪几类？哪些故障影响事物的正常执行？哪些故障破坏数据库的数据？ 答：数据库的运行中可能产生的故障有事务内部故障、系统故障、介质故障和计算机病毒入侵。其中事物内部故障、系统故障及病毒入侵会影响事务的正常执行；介质故障和计算机病毒入侵会破坏数据库数据。
6简述数据库设计的基本步骤。 答：数据库设计的基本步骤：需求分析；概念结构设计；逻辑结构设计；物理结构设计；数据库实施；数据库的运行和维护 篇三：《数据结构》第五章习题参考答案
《数据结构》第五章习题参考答案 一、判断题（在正确说法的题后括----------------精选公文范文----------------
8
---------------------------------精选公文范文--------------------------
号中打“√”，错误说法的题后括号中打“×”）
1、知道一颗树的先序序列和后序序列可唯一确定这颗树。 2、二叉树的左右子树可任意交换。（ ×）
3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。（√） 4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。（√） 5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。 6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。 7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（×） 8、度为2的树就是二叉树。（ × ）
二、单项选择题
1．具有10个叶结点的二叉树中有（B ）个度为2的结点。 A．8 B．9 C．10 D．11
2．树的后根遍历序列等同于该树对应的二叉树的。
----------------精选公文范文----------------
9
---------------------------------精选公文范文--------------------------
A. 先序序列B. 中序序列C. 后序序列
3、二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是： A. EB. F C. G D. H0
4、在下述结论中，正确的是（D ）。 ①具有n个结点的完全二叉树的深度k必为┌log2┐； ②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k且有2k-1个结点的二叉树称为满二叉树。 A．①②③B．②③④ C．①②④ D．①④
5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。 A．空或只有一个结点 B．完全二叉树
C．二叉排序树 D．高度等于其结点数
三、填空题 1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为个，其中----------------精选公文范文----------------
10
---------------------------------精选公文范文--------------------------
个用于指向孩子结点，个指针空闲着。 2、一棵深度为k的满二叉树有k-1______个叶子结点。
3、在完全二叉树中，编号为i和j的两个结点处于同一层的条件是「_2 2_。 ？4、某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二 叉树的总结点数为。（n=n0+n1+n2） 5、完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。
6、已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是___。 四、综合题
1、设二叉树采用二叉链表存储结构，结点的数据域data为字符类型。阅读下列算法，并回答问题：
（1）对于如图所示的二叉树，写出执行函数function的输出结果； （2）简述函数function的功能。 void function {
Stack S; BinTreeNode* p = ; ----------------精选公文范文----------------
11
---------------------------------精选公文范文--------------------------
BinTreeNode* q; if return; do { while { ; if p=p->leftChild; else p=p->rightChild; }
while && q= && q-> rightChild = =p){
p=; cout data; } if){
q=; p=q-> rightChild; } } while ); } 1
DBFGECA
函数function的功能是对二叉树进行后序遍历。
2、课本P246 题 解答
3、课本P246 题
解答结点个数为n时，深度最小的树的深度为2；它有n-1个叶结点，1个分支结点；深度最大的树的深度为n；它有1个叶结点，n-1个分支结点。 ----------------精选公文范文----------------
12
---------------------------------精选公文范文--------------------------
4、课本P246 题 解答
总结点数 n = n0 + n1 + n2 + ? + nm 总分支数 e = n-1 = n0 + n1 + n2 + ? + nm-1 = m*nm + *nm-1 + ? + 2*n2 + n1 m ?
则有 n0????ni??1 ? i?2 ?
5、课本P246 题 解答略 6、课本P246 题 解答
二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。
7、课本P246 题 （1）×（2）√（3）×（4）√ ----------------精选公文范文----------------
13
---------------------------------精选公文范文--------------------------
8、课本P246 题 （1）×（2）×（3）√（4）× 9、课本P247 题 解答略
10、课本P247 题 11、课本P248 题 12、课本P248 题 5-19答
WPL = （2+3）×5+6×4+（9+14+15）×3 +（16+17）×2 = 229 5-20 Huffman树 13、课本P248 题
各字母的Huffman编码： C1: 0110 C2: 10 C3: 0000 C4: 0111 C5: 001 C6: 010 C7: 11 C8: 0001
电文总码长=4×（3+4+5+6）+3×（10+11） +2×（25+36） =257 14、课本P248 题 解答
统计二叉树中叶结点个数
----------------精选公文范文----------------
14
---------------------------------精选公文范文--------------------------
int BinaryTree :: leaf { } if return 0;
else if return 1; else return leaf + leaf ;
交换每个结点的左子女和右子女 void BinaryTree :: exchange { BinTreeNode * temp; if { }
temp = ptr->leftChild;
ptr->leftChild = ptr->rightChild; ptr->rightChild = temp; exchange ; exchange ; }
15、课本P248 题 解答 template
void BinaryTree :: ConstructTree { //私有函数 : 将用T[n]顺序存储的完全二叉树, 以i为根的子树转换成为用二叉链表表示的 //以ptr为根的完全二叉树。利用引用型参数ptr将形参的值带回实参。
----------------精选公文范文----------------
15
---------------------------------精选公文范文--------------------------
if ptr = NULL; else {
ptr = new BinTreeNode ; //建立根结点 ConstructTree ; ConstructTree ; } } 16、课本P249 题 解答 template void BinaryTree::FullBinTree2Array{ Queue *> Q; BinTreeNode * p = GetRoot; ; int index = 0; }
while){ p = ; } T[index++]=p->data; if ; if ;
17、课本P250 题 /
/缩格文本显示树 template
void BinaryTree :: FormatDisplay { Stack * > S; ;
----------------精选公文范文----------------
16
因篇幅问题不能全部显示，请点此查看更多更全内容