1. 您所在位置：首页 > 给排水规范 > 设计规范 > 数据结构复习题参考答案.doc

数据结构复习题参考答案.doc 9页

  • 80.00 KB
  • 2022-04-22 11:41:59 发布

数据结构复习题参考答案.doc

  • 9页
  • 当前文档由用户上传发布，收益归属用户
  1. 1、本文档共5页，可阅读全部内容。
  2. 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
  3. 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
  4. 文档侵权举报电话：19940600175。
'数据结构总复习第一部分课后习题第一章课后习题P161、2、5、6、9第三章课后习题P662、3第四章课后习题P881第五章课后习题P1021、2第六章课后习题P134-1351、3、16、18完成P137实验二构造哈夫曼编码第七章课后习题P1771、2、4、8、10第二部分综合习题一、单项选择题1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（C）A.栈B.队列C.树D.图2.下面程序段的时间复杂度为（B）for(i=0;inext==headB.p->next->next==headC.p->next==NULLD.p==head第9页共9页 4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（D）A.SXSSXXXXB.SXXSXSSXC.SXSXXSSXD.SSSXXSXX5.两个字符串相等的条件是（D）A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（D）A.0B.1C.48D.497．算法分析的目的是：（C）（A）找出数据结构的合理性（B）研究算法中输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性8．用链表表示线性表的优点是：（C）（A）便于随机存取（B）花费的存储空间比顺序表少（C）便于插入和删除（D）数据元素的物理顺序与逻辑顺序相同9．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxsize为数组的最大长度，队满的条件是：（D）（A）front=rear（B）rear=maxsize（C）rear=front（D）（rear+1）%maxsize=front10．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为：（A）（A）CDBGFEA（B）CDBFGEA（C）CDBAGFE（D）BCDAGFE11．执行下列程序段，执行S的次数（S这段程序的时间复杂度）是：（D）for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)第9页共9页 S;（A）n2（B）n2/2（C）n(n+1)（D）n(n+1)/212．以下数据结构中哪一个是非线性结构的是：（D）（A）队列（B）栈（C）线性表（D）图13.设有6个结点的无向图，该图至少有多少条边才能确保是一个连通图：（A）（A）5（B）6（C）7（D）814．树形结构数据元素之间的关系是：（C）（A）一对一关系（B）多对多关系（C）一对多关系（D）多对一关系15．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是：（C）（A）edcba（B）decba（C）dceab（D）abcde16．静态查找和动态查找的根本区别在于：（B）（A）它们的逻辑结构不一样（B）施加在其上的操作不同（C）所包含的数据元素的类型不一样（D）存储的实现不一样17．关键路径是AOE网中：（A）（A）从源点到终点的最长路径（B）从源点到终点的最短路径（C）最长的回路（D）最短的回路18．采用折半查找方法进行查找，数据文件为，且限于；（A）（A）有序表顺序存储结构（B）有序表链式存储结构（C）随机表顺序存储结构（D）随机表链式存储结构19．一个高度为h的完全二叉树共有n个结点，其中m个叶子结点，则下列式子成立的是（D）（A）n=h+m（B）h+m=2n（C）m=h-1（D）n=2m-120．下列说法中不正确的是：（C）（A）数组时一种线性结构（B）数组是一种定长的线性结构（C）除了插入和删除操作外，数组的基本操作还有存取、修改、检索和排序等第9页共9页 （D）数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作21．设无向图G有n个顶点e条边，则该无向图中所有顶点的度之和为：（D）（A）n（B）e（C）2n（D）2eABCDEF22．对下面的无向图进行广度优先搜索后所得到的顶点访问序列，正确的是：（A）（A）ABDEFC（B）ABFEDC（C）ADCBEF（D）ADCBFE23.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（D）存储方式最节省时间。A单链表B双链表C单向循环D顺序表24.串是任意有限个（C）A符号构成的序列B符号构成的集合C字符构成的序列D字符构成的集合25.设矩阵A（aij，l≤i,j≤10）的元素满足：aij≠0(i≥j,l≤i,j≤10)aij=0(inext=P->next，P->next=s两步操作1、10.下面程序段的时间复杂度是O（n2）。For(i=0;inext=NULL_____。15.树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和双亲表示法______.三、解答题1、数据与数据元素有何区别？凡能被计算机存储、加工的对象通称为数据。数据元素是数据的基本单位，在程序中作为一个整体而加以考虑和处理。换句话说，数据元素被当作运算的基本单位，并且通常具有完整确定的实际意义。根据需要，数据元素又被称为元素、结点、顶点或记录。第9页共9页 在很多情况下，数据元素又是由数据项组成的，但数据项通常不肯有完整确定的实际意义，或不被当作一个整体对待。在有些场合下，数据项又称为字段或域。它是数据的不可分割的最小标识单位。从某种意义上说，数据，数据元素和数据实际反映了数据组织的三个层次，数据可由若干个数据元素构成，而数据元素又可由若干个数据项构成。2、逻辑结构与存储结构是什么关系?逻辑结构反映数据元素之间的逻辑关系，而存储结构是数据结构在计算机中的表示，它包括数据元素的表示及其关系的表示。3有一组键值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出每趟的结果。5、设有无向图G，从顶点1出发，（1）给出该图的邻接矩阵和邻接表；（2）分别用普里姆算法和克鲁斯卡尔算法构造最小生成树的产生过程。1243563626164511第9页共9页 5、设栈S1的入栈序列为1234（每个数字为13个元素），则不可能得到出栈序列3142。但可通过增设栈S2来实现。例如，按下图中的箭头指示，依次经过栈S1和S2，便可得到序列3142。如果用H1和H2分别表示栈S1和S2的进栈操作，用P1和P2分别表示两个栈的出栈操作，则得到3142的一个操作步骤为　　H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2请仿照上例写出利用两个栈从1234得到4213的操作步骤。第9页共9页 6、假设某字符串由{a,b,c,d,e,f,g,h}中的字母构成（叶子结点），这8个字母出现的次数分别为4次，6次、8次、2次、10次、14次、20次，16次（权值）（1）构造哈夫曼树；（2）为这8个字母设计哈夫曼编码。第9页共9页'

您可能关注的文档

相关文档

最近下载