搜索
一、选择题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、一棵二叉树的第层最多有个结点；一棵有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值用折半法查找线性表，在查找不成功的情况下至多需比较（）次9、一个无序序列可以通过构造一棵二叉排序树树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。10、在散列存储中，装填因子ａ的值越大，则；ａ的值越小，则.。发生冲突的可能性就越大；发生冲突的可能性就越小；二、简答题1数据结构的存储方式有哪几种？常用的存储表示方法有四种:1、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。2、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。3、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。4、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。2算法的时间复杂度仅与问题的规模相关吗?【解析】算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。3、设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1)i=1;k=0;while(in){k=k+10*i;i++;}（1）分析：i=1;//1k=0;//1while(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;do{k=k+10*i;i++;}while(in);（2）分析：i=0;//1k=0;//1do{//nk=k+10*i;//ni++;//n}while(in);//n由以上列出的各语句的频度，可得该程序段的时间消耗：T(n)=1+1+n+n+n+n=4n+2可表示为T(n)=O(n)(3)i=1;j=0;while(i+j=n){if(ij)j++;elsei++;}分析：通过分析以上程序段，可将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得：yn^0.5-1所以，该程序段的执行时间为：向下取整(n^0.5-1)4、设三个函数f,g,h分别为f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn请判断下列关系是否成立：(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n1.5)(4)h(n)=O(nlgn)通俗地说，就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。即：O(f(n))=n3O(g(n))=n3O(h(n))=n1.5答：●（1）成立。●（2）成立。●（3）成立。●（4）不成立。5何时选用顺序表、何时选用链表作为线性表的存储结构为宜?6在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?7为什么在单循环链表中设置尾指针比设置头指针更好?尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-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之后保持该顺序表仍然递增有序排列算法如下：voidInsertIncreaseList(Seqlist*L,Datatypex){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到之间的所有元素，要求以较高的效率实现。voidDeleteList(LinkListL,DataTypemin,DataTypemax){ListNode*p,*q,*s;p=L;while(p-next&&p-next-data=min)//找比min大的前一个元素位置p=p-next;q=p-next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结while(q&&q-datamax){s=q;q=q-next;free(s);//删除结点，释放空间}p-next=q;//将*p结点的直接后继指针指向*q结点12、下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。13、已知一个线性表有n（n≤30）个元素，其中每个元素的数据占8个字节。假设一个指针的大小为4个字节。如果采用有30个元素的数组存储，那么当数组中有效元素个数n满足什么条件时，数组的存储效率比不带头结点的单链表更高。数组总的空间240个字节，数组的效率为8n/240；链表的总空间为12n，效率为8n/12n。故可得：n〉2013顺序队列一般应该组织成为循环队列的形式，而且一般队列头或为队列尾其中之一虚指一位，满队列时实际上数组中还有一个空闲位置。请分析这样设置的理由。有利于判断队列是空还是满。因为队列有n+2种状态：空，1个元素，2个元素，…,n个元素，满。但实际上rear只有n种可能的取值，故必须寻求其他途径解决队空和队满。当然也有其他方法。14队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请分析对于循环单链