复习题1

一、选择题1-1下列关于数据和逻辑结构的叙述中，哪一个是不正确的（）。A)数据的逻辑结构是数据间关系的描述B)数据的逻辑结构抽象反映数据元素间的逻辑关系C)数据的逻辑结构具体反映数据在计算机中的存储方式D)数据的逻辑结构分为线性结构和非线性结构C1-2以下关于数据的存储结构的叙述中哪一条是正确的（）。A)数据的存储结构是数据间关系的抽象描述B)数据的存储结构是逻辑结构在计算机存储器中的实现C)数据的存储结构分为线性结构和非线性结构D)数据的存储结构对数据运算的具体实现没有影响B二、简答题1-1数据结构的存储方式有哪几种？1-2算法的时间复杂度仅与问题的规模相关吗?1-1数据结构的存储方式有哪几种？【解析】常用的存储表示方法有四种:1、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。2、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。3、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。4、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。1-2算法的时间复杂度仅与问题的规模相关吗?【解析】算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。三、应用题:分析以下程序段的时间复杂度。inti，j，k；for（i=0；i〈n；i++〉//①for（j=0；j〈n；j++〉//②{c[i][j]=0；//③for（k=0；k〈n；k++〉//④c[i][j]=c[i][j]+a[i][k]+b[k][j]；//⑤}【解析】语句①的循环控制变量i要增加到n，测试到i=n成立才会终止，故它的频度为n+1；语句②作为语句①循环体内的语句应该执行n次，但语句②本身要执行n+1次，故语句②的频度是n（n+1）；同理可得语句③、④和⑤的频度分别是n2，n2（n+1）和n3。该程序段所有语句的频度之和为：T（n）=2n3+3n2+2n+1其复杂度为O（n3）。一、简答1何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?3为什么在单循环链表中设置尾指针比设置头指针更好?4在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?5下述算法的功能是什么?LinkListDemo(LinkListL){//L是无头结点单链表ListNode*Q,*P;if(L&&L-next){Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;}returnL;}//Demo6、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。二、下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。voidunion(LinkListLa,LinkListLb){/*本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中*/LinkListpre=La,q;LinkListpa=La-next;LinkListpb=Lb-next;free(Lb);while(pa&&pb){if(pa-datapb-data){pre=pa;pa=pa-next;}elseif(pa-datapb-data){(1);pre=pb;pb=pb-next;(2);}else{q=pb;pb=pb-next;free(q);}}if(pb)(3);}（1）pre-next=pb;（2）pre-next=pa;（3）pre-next=pb;三、已知一个线性表有n（n≤30）个元素，其中每个元素的数据占8个字节。假设一个指针的大小为4个字节。如果采用有30个元素的数组存储，那么当数组中有效元素个数n满足什么条件时，数组的存储效率比不带头结点的单链表更高。数组总的空间240个字节，数组的效率为8n/240；链表的总空间为12n，效率为8n/12n。故可得：n〉20四、画出执行下列各语句后各指针及链表的示意图。L=(LinkList)malloc(sizeof(Lnode));P=L;for(i=1;i=4;i++){p-next=(LinkList)malloc(sizeof(Lnode));p=p-next;P-data=i*2-1;}P-next=NULL;for(i=4;i=1;i--)InsertList(L,i+1,i*2);for(i=1;i=3;i++)DeleteList(L,i);2、顺序队列一般应该组织成为循环队列的形式，而且一般队列头或为队列尾其中之一虚指一位，满队列时实际上数组中还有一个空闲位置。请分析这样设置的理由。有利于判断队列是空还是满。因为队列有n+2种状态：空，1个元素，2个元素，…,n个元素，满。但实际上rear只有n种可能的取值，故必须寻求其他途径解决队空和队满。当然也有其他方法。3、队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请分析对于循环单链表实现的队列，用那种方案更合适。设置尾指针。因为是循环单链表，设置尾指针，可以在O(1)的时间内找到头；如果只设置头指针，要在O(n)时间内找到尾。设置尾指针，入队和出队的时间复杂度均为O(1)，设置头指针，出队O(1)，入队O(n)。一、单项选择题1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法（A）正确（B）错误2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是(A)空或只有一个结点(B)完全二叉树(C)二叉排序树(D)高度等于其节点数3、深度为5的二叉树至多有多少个结点(A)16(B)32(C)31(D)104、根据使用频率为5个字符设计的哈夫曼编码不可能是（A）111，110，10，01，00（B）000，001，010，011，1（C）100，11，10，1，0（D）001，000，01，11，10二、填空题1、树和二叉树的主要差别是，。2、深度为k的完全二叉树至少有个结点，至多有个结点。3、一棵二叉树的第i(i1)层最多有个结点；一棵有n（n0）个结点的满二叉树共有个叶子结点和个非叶子结点。1、（1）每个结点最多有两棵子树；（2）子树有左右之分2、2k-1,2k-1,3、2i-1,2log2n，n-2log2n1、一棵度为2的树与一棵二叉树有何区别？2、具有三个结点的树和具有三个结点的二叉树它们的所有不同形态有哪些？3、请说明一棵二叉树进行先序、中序和后序遍历，其叶结点的次序是否会发生变化？为什么？1、解答：度为2的树结点有两个分支，没有左右之分；一棵二叉树的结点也可有两个分支，但有左右之分，且左右不能交换。3.解答：二叉树中叶结点必在某结点的左或右子树中，三种遍历方法对左右子树的遍历都是按先左后右的原则进行。所以在三种遍历序列中叶结点的相对次序是不会发生变化的。4、假设一棵二叉树的结点数为33个，则它的最小高度为（），最大高度为（）。5、一个高度为h的满m叉树，第k层最多有（）个结点，整棵树最多有（）个结点。4、最小高度为：6，最大高度为：335、第k层最多有mk-1,整棵树最多有(mk-1)/(m-1)6、一个二叉树的对称序列和后序序列分别是DCBAEFG和DCBGFEA，请给出该二叉树的前序序列。6、ABCDEFG7有7个带权结点，其权值分别为4，7，8，2，5，16，30，以它们为叶子结点构造一颗哈夫曼树（要求按每个结点的左子树根结点的权值小于或等于右子树根结点的权值的次序构造），并计算出其带权路径长度WPL。可得带权路径长度：WPL=(2+4)×5+(5+7+8)×4+16×2+30×1=1721、一个n个顶点的无向图最多有条边。(A)n(B)n(n-1)(C)n(n-1)/2(D)2n2、（A）1/2（B）1（C）2（D）43.两种遍历算法。1、设线性表（a1，a2，…，a500）元素的值由小到大排列，对一个给定的k值用折半法查找线性表，在查找不成功的情况下至多需比较次1.log2n+12试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求。对长度为n的表来说，三种查找法在查找成功时的查找长度各是多少？查找要求:顺序查找法：表中元素可以任意存放,(n+1)/2折半查找法：有序存放log2(n+1)-1分块查找法：分块有序(n/s+s)/2+1,b为块数，s为块中记录数1.数据的基本单位是（C）A.数据项B.数据类型C.数据元素D.数据变量2.下列程序的时间复杂度为（C）i=0；s=0；while（sn）{i++；s=s+i；}A.O（）B.O（）C.O（n）D.O（n2）3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（D）A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（A）A.n-iB.n-i+1C.n-i-1D.i5.顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（C）A.s.elem［top］=e；B.s.elem［top+1］=e；s.top=s.top+1；s.top=s.top+1；C.s.top=s.top+1；D.s.top=s.top+1；s.elem［top+1］=e；s.elem［top］=e；6.循环队列sq中，用数组elem［0••25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（D）A.8B.16C.17D.188.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（A）A.3B.4C.5D.610.有n个结点的有向完全图的弧数是（C）A.n2B.2nC.n(n-1)D.2n(n+1)11.设图的邻接链表如题12图所示，则该图的边的数目是（B）A.4B.5C.10D.2012.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（B）A.1B.2C.3D.413.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（）A.选择排序B.快速排序C.冒泡排序D.插入排序14．数据结构是（D）A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合15．算法分析的目的是（B）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性16．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）A．插入B．删除C．排序D．定位17．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈