数据结构 练习题.doc

《数据结构 练习题.doc》由会员分享，可在线阅读，更多相关《数据结构 练习题.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 概述一、简答题 1简述以下术语的含义并说明它们之间的关系。 数据类型、数据结构、逻辑结构、存储结构2简述算法时间效率和空间效率的概念。3简述数据结构课程的目的和意义。 二、选择题 1以下数据结构中，逻辑结构属于线性结构的是 A）有向图B）链式栈C）二叉树 D）二叉排序树2下列与数据元素有关的叙述中错误的是A）数据元素是有独立含义的数据最小单位 B）数据元素是描述数据的基本单位C）数据元素可以称做结点 D）数据元素可以称做记录3设问题的规模为n，分析以下程序段：a=10; b=100;while (b0) a+; b- -; 以上程序段的算法时间复杂度是 A）O(1)B）O(n)C）O(

2、n2)D）O( )三、填空题 1数据结构包括的三方面内容分别是：数据的 1 、数据的 2 和数据的运算。2数据元素是数据的基本单位，在某些情况下也可以称为 1 、 2 和 3 。3数据逻辑结构的4种基本形态包括集合结构、 1 结构、 2 结构和 3 结构。4一个正确的算法应该具有5个特性：1 、 2 、3 、 4 和 5 。5数据的存储结构包括顺序、 1 、 2 和 3 四种。6一个数据结构在计算机中的映象称为 1 。7一个算法的效率主要是指该算法的 1 效率和 2 效率。8以下程序段的时间复杂度T（n）= 。 sum=0;for(i=0 ; in; i+) for( j=0; jn; j+)

3、 sum+=aij;printf(%dn,sum);四、算法及分析 1写出交换两个整型变量值的算法，并分析算法的时间复杂度。2写出求n的阶乘 的算法，并分析算法的时间复杂度。第2章 线性表一、简答题1在处理某个问题时，需要存储的数据总量不能确定，并经常需要进行数据的添加和删除操作，此时应选用哪种存储结构？为什么？2、简述头指针、头结点的区别，以及头指针和头结点的作用。二、选择题1以下链表结构中，从当前结点出发能够访问到任一结点的是 A）单向链表和双向链表B）双向链表和循环链表 C）单向链表和循环链表D）单向链表、双向链表和循环链表2线性表是具有n个 的有限序列。 A）数据项B）数据元素C）表元

4、素D）字符3若长度为n的线性表采用链式存储结构，访问其第i个元素的算法时间复杂度为 A）O(1)B）O(n)C）O(n2)D）O(log2n)4在长度为n的顺序表中，若要删除第i（1in）个元素，则需要向前移动的元素的次数为 A）iB）n-iC）n-i+1D）n-i-15在长度为n的顺序表中第i（1in）个位置上插入一个元素时，为留出插入位置所需移动元素的次数为 A）n-iB）iC）n-i+1D）n-i-16下述哪一条是顺序存储结构的优点？ A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示7若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运

5、算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表8. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=inext; do s=s+ 1 ; p=p-next; while ( p!= 2 ); return s;4. 带头结点的双循环链表L中只有一个数据结点的判定条件是：_。5. 在单链表L中，指针p所指结点有后继结点的判定条件是：_ 。6. 带头结点的单循环链表L为空表的条件是：_。7. 在单链表p结点之后插入s结点的操作是：_。四、算法设计*1有序顺序表、单链表的插入算法。设线性表有序（按由小到大的

6、顺序排列），分别编写顺序表、带有头结点的单链表的插入算法，使插入值为x的元素后线性表仍保持有序的算法。*2单链表的输出算法：输出带有头结点的单向链表中各结点的值。*3顺序表、单链表的删除算法：分别编写顺序表、带有头结点的单链表中删除所有值为x的结点的算法。4顺序表、单链表的逆置算法：分别实现顺序表、带有头结点的单链表的逆置操作。即将线性表（a1,a2,an）逆置为（an,a2,a1）。5顺序表、单链表的查找算法：分别实现顺序表、带有头结点的单链表中查找最后一个值为x的结点位置的算法。6写出求单链表、循环单链表表长的算法。7有序顺序表、有序单链表的归并算法。分别编写将两个有序顺序表、两个带有头结

7、点的单链表归并成一个有序线性表（按由小到大的顺序排列）的归并算法，要求尽量利用原来的存储空间。8. 设L为单链表的头结点地址，单链表中数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。9. 已知线性表（a1 a2 a3 an）按顺序存于内存中，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x x）变为（-x,-x,-xx,x,x），其中x0。第三章请设计算法：利用栈结构和栈的基本运算将一个十进制数转换成指定的k（k=29）进制数。第6章树例题分析与解答例6.1 设有一棵树的

8、度为3，其中度为1、2、3的结点个数分别为5、2、1、，则这棵树中叶子结点的个数为A）4 B）5 C）6 D）7【解答】设这棵树中叶子结点的个数为n0，根据已知，在这棵树中结点的总数n=5+2+1+ n0=8+ n0；此外，从树的性质又可知，度为1的结点有1个分?任?2的结点有2个分支，度为3的结点则有3个分支，因此这棵树的总的分支数为：1*5+2*2+3*1=12，而一棵有n个结点的树，只允许有n-1个分支存在，所以又有：n-1=12，即n=13，将n代入上式，则n0=5。所以，选项B是正确的。例6.2 一棵权值为1，2，3，4，5，6的哈夫曼树，如图6-1所示，其中方框为带权的叶子结点，圆

9、圈为非叶子结点。则该哈夫曼树的带权路径长度WPL，及权值为1的叶子结点的高度分别为A）51；5 B）72；5 C）51；4 D）72；4图6-1 例6.2附图哈夫曼树【解答】其中n表示叶子结点的数目，wi表示叶结点的权值，li表示根到叶结点之间的路径长度。因此有：WPL= (1+2)*4+3*3+ (4+5+6)*2=51。权值为1的叶结点的高度很明显为5。所以，本题的答案为选项A。例6.3 假设已知某二叉树的前序遍历序列和后序遍历序列，则根据已知条件一定能唯一地确定出一棵二叉树。请问这句话对吗？【解答】错。例如某二叉树的前序遍历序列为：AB；后序遍历序列为BA；根据条件可以画出如图6-2所示

10、的两棵不同的二叉树。因此已知前序和后序遍历序列，并不能唯一地确定出一棵二叉树。图6-2 例6.3附图6 自测习题1. 简答题1. *根据权值（1，2，3，4，5，6），构造哈夫曼树，并计算二叉树的带权路径长度。2. 请将下图6-1所示的森林转换成二叉树。图6-1 简答题2的附图森林3. *已知一棵二叉树的中序遍历序列为DHBEAIFCGJK，该二叉树的后序遍历序列是HDEBIFJKGCA，现请画出这棵二叉树。4. *给出图6-2所示的一棵二叉树的顺序存储结构、二叉链表和三叉链表存储结构。图6-2 简答题4的附图二叉树2. 判断题1. 由树转化为二叉树，其根结点的右子树总是空的。 （ ）2. 若

11、有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树的中序遍历序列中的第一个结点。 （ ）3. 若一个树叶是某二叉树的前序遍历序列中的最后一个结点，则它也一定是这棵二叉树的中序遍历序列中的最后一个结点。 （ ）4. 若一个树叶是某二叉树的中序遍历序列中的最后一个结点，则它也一定是这棵二叉树的前序遍历序列中的最后一个结点。 （ ）5. 在二叉树中，具有一个子女的父结点，在中序遍历序列中没有后继结点。而具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。（ ）6. 虽然已知二叉树的前序遍历和中序遍历序列，但还不能唯一确定出这棵二叉树，因为并不知道二叉树的

12、根结点是哪一个。 （ ）7. 在满二叉树中，存在度为1的结点。 （ ）8. 在任意一棵二叉树中，终端结点的个数等于度为的结点个数加。 （ ）9. 前序遍历序列与中序遍历序列完全相同的二叉树有：空二叉树或任一结点均无左子树的非空二叉树。 （ ）3.选择题1. 如果结点A是结点B的双亲，而且结点有个兄弟，则结点A的度是A）2 B）3 C）4 D）52. 设有一棵二叉树，其度结点有m个，度结点有n个，则该二叉树的结点总数为A）m+n B）2*m+n C）m+2*n D）m+2*n+13. 设有一棵二叉树，其先序遍历序列是：ABCDEFG，中序遍历序列是：CBDAFEG，则该二叉树的后序遍历序列是A）

13、CDBFGEA B）CDFGBEA C）CDBAFGE D）CDBFEGA4. 设有13个值，由它们组成一棵哈夫曼树，则该哈夫曼树中结点个数共有。A）13 B）12 C）26 D）255. 设电文中出现的字母为A、B、C、D和E，每个字母在电文中出现的次数分别为：6，23，3，5和12，按哈夫曼编码，则字母C的编码应是A）10 B）110 C）1110 D）11116. 已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是A）E B）F C）G D）J7. 设结点A有左孩子结点B，右孩子结点C，则在先序遍历、中序遍历、后序遍历这三种基本遍历序列

14、中B一定是C的A） 前驱 B）后继 C）相邻结点 D）不相邻结点4. 填空题1. 采用二叉链式存储结构，具有n个结点的二叉树中，一共有 1 个指针域，其中 2 个指针域为空。2. 一棵非空的二叉树，其第i层上最多有个结点。3. 满二叉树是一棵深度为k的且恰好有个结点的二叉树。4. 将一棵完全二叉树按层次编号，对任一编号为i的结点有：如该结点有左孩子，则其编号为 1 ；如该结点有右孩子，则其编号为 2 。5. 设一棵二叉树中只有叶子结点和左、右子树都非空的结点，如果叶子结点的个数是m，则左、右子树都非空的结点个数是6. 设有一棵树（如图6-3所示），请回答下列问题：根结点是1；叶子结点有2 ；的

15、双亲是3；的祖先是4；的孩子是5；的孩子是6；的子孙有7；的兄弟是8；的兄弟是9；结点的层数是10；树的深度是11；为根的子树深度是12；这棵树的度是13。图6-3 填空题6的附图7. 现有一表达式 ( a+b )*c-d / e，写出该表达式的波兰式1，以及逆波兰式2。4. 算法设计题*1 试编写一个递归算法，用于计算二叉树的叶子结点数。要求二叉树为链式存储结构。2 试编写一个求结点P的双亲的算法，要求二叉树为链式存储结构，且该二叉树中的结点值均不相同。若无结点P，则打印”No Point”；若结点P是根结点，则打印”No Parent”；若有结点P，则输出其双亲结点的值。3 试编写一个算法，用于找出结点数值为x的结点的所有祖先结点的数值。假定这棵二叉树各结点的数值都不相等，二叉树为链式存储结构。4 试编写一个按层次顺序遍历二叉树的算法，假定二叉树采用链式存储结构。5 试编写一个非递归的后序遍历算法，并计算该二叉树的所有结点个数。