算法与数据课后题答案.docVIP

一、选择题 1、 下列关于数据和逻辑结构的叙述中，哪一个是不正确的（ ）。 A ) 数据的逻辑结构是数据间关系的描述 B) 数据的逻辑结构抽象反映数据元素间的逻辑关系 C) 数据的逻辑结构具体反映数据在计算机中的存储方式 D) 数据的逻辑结构分为线性结构和非线性结构2、 以下关于数据的存储结构的叙述中哪一条是正确的（ ）。 A) 数据的存储结构是数据间关系的抽象描述 B) 数据的存储结构是逻辑结构在计算机存储器中的实现 C) 数据的存储结构分为线性结构和非线性结构 D) 数据的存储结构对数据运算的具体实现没有影响3、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 B . （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、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。（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、在一个长度为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、散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法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，最大高度为：335、一个高度为h的满m叉树，第k层最多有（ ）个结点，整棵树最多有（ ）个结点。第k层最多有 mk-1,整棵树最多有(mk-1)/m-16、一个图的表示法是唯一的，而表示法是不唯一的。7、在有n个顶点的有向图中，每个顶点的度最大可达8、设线性表（a1，a2，a500）元素的值由小到大排列，对一个给定的k值用折半法查找线性表，在查找不成功的情况下至多需比较 （ log2n+1 ）次9、一个无序序列可以通过构造一棵 二叉排序树 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。10、在散列存储中，装填因子的值越大，则；的值越小，则.。 发生冲突的可能性就越大；发生冲突的可能性就越小；二、简答题 1 数据结构的存储方式有哪几种？ 常用的存储表示方法有四种 : 1 、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 2 、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构 , 通常借助于程序语言的指针类型描述。 3 、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（ Dense Index ）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。 4 、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。2 算法的时间复杂度仅与问题的规模相关吗 ? 【解析】 算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。3、设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0;while(in) k=k+10*i;i+;（1）分析：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 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在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?下面分别讨论三种链表的情况。1. 单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。3. 单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。9、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。10、已知一个顺序表L，其中的元素递增有序，设计一个算法插入一个元素x之后保持该顺序表仍然递增有序排列算法如下： void InsertIncreaseList( Seqlist *L , Datatype x ) if ( L-length=ListSize)Error(“overflow); for ( i=L - length ; i0 & L-data i-1 x ; i-)L-data i =L-data i-1 ; / 比较并移动元素L-data i =x;L - length+; 11、设计算法，从给定的顺序表L中删除元素值在min到max(minmax)之间的所有元素，要求以较高的效率实现。void DeleteList ( LinkList L, DataType min , DataType max )ListNode *p , *q , *s;p=L;while( p-next & p-next-data next;q=p-next;/p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结while(q &q-datanext; free(s);/删除结点，释放空间 p-next=q;/将*p结点的直接后继指针指向*q结点12、下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。13、已知一个线性表有n（n30）个元素，其中每个元素的数据占8个字节。假设一个指针的大小为4个字节。如果采用有30个元素的数组存储，那么当数组中有效元素个数n满足什么条件时，数组的存储效率比不带头结点的单链表更高。数组总的空间240个字节，数组的效率为8n/240；链表的总空间为12n，效率为8n/12n。故可得：n2013顺序队列一般应该组织成为循环队列的形式，而且一般队列头或为队列尾其中之一虚指一位，满队列时实际上数组中还有一个空闲位置。请分析这样设置的理由。有利于判断队列是空还是满。因为队列有n+2种状态：空，1个元素， 2个元素，, n个元素，满。但实际上rear只有n种可能的取值，故必须寻求其他途径解决队空和队满。当然也有其他方法。14队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请分析对于循环单链表实现的队列，用那种方案更合适设置尾指针。因为是循环单链表，设置尾指针，可以在O(1)的时间内找到头；如果只设置头指针，要在O(n)时间内找到尾。设置尾指针，入队和出队的时间复杂度均为O(1)，设置头指针，出队O(1)，入队O(n)。15、假设一个单循环链表，其结点含有三个域pre,data和link。其中data为数据域;pre为指针域，它的值为空指针(NULL)；link为指针域，指向后继结点。设计算法，将此表改为双向循环链表设s为指向循环链表某一结点的指针，p,q中间结点；指针s在搜索过程中保持不变，作为结束条件，每执行一次就将指针p赋给q所指节电的pre，并修改p,q，保持p在后，q在前。doulink(s:dLinkList) /非空表 p=s; do q=p-next; q-pre=p; p=q; while(p!=s); 16、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。队满条件： Q.quelen= MAX_QUEUE;入队:设Q.rear指向队尾元素if(Q.quelen!= MAX_QUEUE) Q.rear= (Q.rear+1)% MAX_QUEUEQ.dataQ.rear=x;Q.quelen+;出队：设Q.rear指向队尾元素if(Q.quelen!=0) /队列非空 front=(Q.rear+ MAX_QUEUE- Q.quelen)%MAX_MAXSIZE; Q.quelen-; return(front); 17、请说明一棵二叉树进行先序、中序和后序遍历，其叶结点的次序是否会发生变化？为什么？解答：二叉树中叶结点必在某结点的左或右子树中，三种遍历方法对左右子树的遍历都是按先左后右的原则进行。所以在三种遍历序列中叶结点的相对次序是不会发生变化的。18、给定14各字母，假设它们的权都相等。采用HUFFMAN编码，则每个字母的平均代码长度是多少？（12*4+2*3）/14=54/14=3.857 19、有7个带权结点，其权值分别为4，7，8，2，5，16，30，以它们为叶子结点构造一颗哈夫曼树（要求按每个结点的左子树根结点的权值小于或等于右子树根结点的权值的次序构造），并计算出其带权路径长度WPL。可得带权路径长度：WPL=(2+4)5+(5+7+8)4+162+301=1