《算法与数据课后题答案》由会员分享，可在线阅读，更多相关《算法与数据课后题答案（6页珍藏版）》请在金锄头文库上搜索。
1、一、选择题 1、 下列关于数据和逻辑结构的叙述中，哪一个是不正确的（ ）。 A ) 数据的逻辑结构是数据间关系的描述 B) 数据的逻辑结构抽象反映数据元素间的逻辑关系 C) 数据的逻辑结构具体反映数据在计算机中的存储方式 D) 数据的逻辑结构分为线性结构和非线性结构2、 以下关于数据的存储结构的叙述中哪一条是正确的（ ）。 A) 数据的存储结构是数据间关系的抽象描述 B) 数据的存储结构是逻辑结构在计算机存储器中的实现 C) 数据的存储结构分为线性结构和非线性结构 D) 数据的存储结构对数据运算的具体实现没有影响3、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 B .
2、（A）正确 （B）错误4、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 (A)空或只有一个结点 (B) 完全二叉树(C)二叉排序树 (D) 高度等于其节点数5、深度为5的二叉树至多有 C 多少个结点.(A)16 (B)32 (C)31 (D)106、根据使用频率为5个字符设计的哈夫曼编码不可能是 C（A）111，110，10，01，00 （B）000，001，010，011，1（C）100，11，10，1，0 （D）001，000，01，11，107、一个n个顶点的无向图最多有条边。(A) n (B) n(n-1) (C) n(n-1)/2 (D) 2n8、在一个有向图中，所
3、有顶点的入度之和等于所有顶点的出度之和的倍。（A）1/2 （B）1 （C）2 （D）49、关键路径是事件结点网络中 。（A）从源点到汇点的最长路径 （B）最长的回路（C）从源点到汇点的最短路径 (D）最短的回路10、下面不正确的说法是 。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，将使整个工程提前完成C、所有关键活动都提前，则整个工程提前完成D、某些关键活动若提前完成，将使整个工程提前完成。11、采用顺序查找法查找长度为n的线性表时，则查找成功时的平均查找长度为 C 。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/212、在一个长度
4、为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为 B 。（A）35/12 （B）37/12 （C）39/12 （D）43/1213、查找效率最高的二叉排序树是 C 。 （A）所有结点的左子树都为空的二叉排序树 （B）所有结点的右子树都为空的二叉排序树 （C）平衡二叉树 （D）没有左子树的二叉排序树14、以下说法错误的是 B 。A、散列法存储的基本思想是由关键码值决定数据的存储地址B、散列表的结点中只包含数据元素自身的信息，不包含任何指针C、装填因子是散列法的一个重要参数，它反映了散列表的装填程度D、散列表的查找效率主要取决于散列表造表时选取的散列
5、函数和处理冲突的方法15、散列表的平均查找长度 A 。A.与处理冲突方法有关与表长无关 B.与处理冲突方法无关与表的长度有关C.与处理冲突方法有关且与表的长度有关 D.与处理冲突方法无关且与表的长度无关二、填空题1、树和二叉树的主要差别是，。（1）每个结点最多有两棵子树； （2）子树有左右之分2、深度为k的完全二叉树至少有个结点，至多有个结点。2k-1, 2k-1,3、一棵二叉树的第i(i1)层最多有 个结点；一棵有n（n0）个结点的满二叉树共有个叶子结点和个非叶子结点。 (n+1)/2,(n-1)/24、假设一棵二叉树的结点数为33个，则它的最小高度为（ ），最大高度为（ ）。 最小高度为：
6、6，最大高度为：335、一个高度为h的满m叉树，第k层最多有（ ）个结点，整棵树最多有（ ）个结点。第k层最多有 mk-1,整棵树最多有(mk-1)/m-16、一个图的表示法是唯一的，而表示法是不唯一的。7、在有n个顶点的有向图中，每个顶点的度最大可达8、设线性表（a1，a2，a500）元素的值由小到大排列，对一个给定的k值用折半法查找线性表，在查找不成功的情况下至多需比较 （ log2n+1 ）次9、一个无序序列可以通过构造一棵 二叉排序树 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。10、在散列存储中，装填因子的值越大，则；的值越小，则.。 发生冲突的可能性就越大；发生
7、冲突的可能性就越小；二、简答题 1 数据结构的存储方式有哪几种？ 常用的存储表示方法有四种 : 1 、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 2 、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构 , 通常借助于程序语言的指针类型描述。 3 、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表
8、中都有一个索引项，则该索引表称之为稠密索引（ Dense Index ）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。 4 、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。2 算法的时间复杂度仅与问题的规模相关吗 ? 【解析】 算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。3、设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0;while(in) k=k+10*i;i+;（1）
9、分析：i=1; /1k=0; /1 while(in) /n k=k+10*i; /n-1i+; /n-1由以上列出的各语句的频度，可得该程序段的时间消耗：T(n)=1+1+n+(n-1)+(n-1)=3n可表示为T(n)=O(n)(2) i=0; k=0;dok=k+10*i; i+;while(in);（2）分析：i=0; /1k=0; /1do /nk=k+10*i; /ni+; /nwhile(in);/n由以上列出的各语句的频度，可得该程序段的时间消耗：T(n)=1+1+n+n+n+n=4n+2可表示为T(n)=O(n)(3) i=1; j=0;while(i+jj) j+;else
10、 i+;分析：通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为：T(n)=O(n)(4)x=n; / n1while (x=(y+1)*(y+1)y+;分析：由x=n且x的值在程序中不变，又while的循环条件(x=(y+1)*(y+1)可知：当(y+1)*(y+1)刚超过n的值时退出循环。由(y+1)*(y+1)n得：ynext-next 和 rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。8在单链表、双链表和单循
11、环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?下面分别讨论三种链表的情况。1. 单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3. 单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。9、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。10、已知一个顺序表L，其中的元素递增有序，设计一个算法插入一个
