数据结构与算法的习题

答案为网上下载，有错的跟我说声哈，有的没答案，自己看看，不会的跟我说一下发给老师。一、单项选择题：（本大题共20小题，每题2分，共30分）（说明：将答案写在试卷后面的答题纸上）分数评卷人1.计算机识别、存储和加工处理的对象被统称为(D)A.数据B.数据元素C.数据结构D.数据类型2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(B)A.O(1)B.O(n)C.O(nlogn)D.O(n2)3.队和栈的主要区别是(D)A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同4.链栈与顺序栈相比，比较明显的优点是(D)A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况5.下列说法中正确的是（D）二叉树中任何一个结点的度都为2二叉树的度为2任何一棵二叉树中至少有一个结点的度为2一棵二叉树的度可以小于26.在一非空二叉树的中序遍历序列中，根结点的右边（A）只有右子树上的所有结点只有右子树上的部分结点只有左子树上的所有结点只有左子树上的部分结点7.在一个具有N个顶点的无向完全图中，包含的边的总数是（A）N(N-1)/2N(N-1)N(N+1)N(N+1)/28.下面的程序在执行时，S语句共执行的（B）次。i=1;while(i<=n){for(j=i;j<n;j++){S;}i=i+1;}A.n(n+1)/2B.n(n-1)/2C.n!D.9.设二叉树有n个结点，则其深度为（D）A.n-1B.nC.5log2n+1D.不确定10.已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为（B）A.ACFKBDGB.GDBFKCAC.KCFAGDBD.ABCDFKG11.任何一个带权的无向连通图的最小生成树（B）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在12.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（D）A.acbedB.decabC.deabcD.cedba13.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数量是（C）个A.k+1B.2kC.2k-1D.2k+114.下面程序的时间复杂性是（B）For(i=1;i<=n;i++)For(j=1;j<=n;j++){a[i][j]=i*j;}A.O()B.O()C.O(m*n)D.O(m+n)15.含N个顶点的连通图中的任意一条简单路径，其长度不可能超过（C）A.1B.N/2C.N-1D.N16.下列说法正确的是（A）A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同17.对于一个具有N个结点和E条边的无向图，若采用邻接表示，则表头向量的大小是(A)A.NB.N+1C.N-ED.N-118.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用（D）A.求关键路径的方法B.求最短路径的Dijkstra方法C.广度优先遍历方法D.深度优先遍历方法19.一个队列的输入序列是1,2,3,4，则队列的输出序列是（B）A,4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,120.任何一个带权的无向连通图的最小生成树（B）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在得分评卷人复查人二、填空题（本大题共10小题，每小题1分，共10分）请在每小题的空格中填上正确答案。错填、不填均无分。（1）在线性表中插入或删除一个元素，需要平均移动n/2元素，具体移动的元素个数与插入或删除位置有关。（2）顺序表中逻辑上相邻的元素的物理位置要求紧邻，单链表中逻辑上相邻的元素物理位置不要求紧邻。（3）在单链表中，除了首元结点外，任意结点的存储位置由指针指示。（4）记录的存储结构是数据在物理存储器上的存储方式。（5）在非空队列中，头指针始终指向队首，而尾指针始终指向队尾。（6）N个顶点的连通图，至少有N-1条边。（7）对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为n/2，如果k不在表中，则需要进行n次比较后才能确定查找失败。(8)在二叉排序树中，其左子树中任何一个结点的关键字一定小于其右子树的各结点的关键字。（9）已知无向图G的结点数为n，边数为e，其邻接表表示中的表结点数与表头结点数之和为n+2e。（10）若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的第一个个结点。（11）有m个叶子结点(又称外结点)的哈夫曼树，其结点总数是2m-1。（12）如果一个图中有n条边，则此图的生成树含有n-1条边，所以生成树是图的边数最少的连通图（13）由权值为1，2，3，4，5，6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为51。（14）在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为null，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为空。（15）树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和双亲链表法。（16）无向图的邻接矩阵是对称的，并且主对角线上的元素的值为0。（17）在结点数目相同的二叉树中，完全二叉树的路径长度最短。（18）栈和队列均可视为特殊的线性表，所不同的在于对这二种特殊线性表插入和删除运算的限定不一样。16.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的____时间复杂度____。17.下面程序段的时间复杂度为_____O(n)______。sum=1；for（i=0；sum<n;i++）sum+=1；18.已知链表结点定义如下：typedefstructnode{chardata［16］；structnode*next;}LinkStrNode；如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是____80%__。19.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为_____99______。20.3个结点可以组成____5_______种不同树型的二叉树。21.用5个权值{3,2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___33________。22.若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为_2*m__________。23.影响排序效率的两个因素是关键字的____比较_______次数和记录的移动次数。24.对任一m阶的B树，每个结点中最多包含_____m-1__个关键字。25.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作__存储密度_____。datenext26.已知链栈的结点结构为栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为___p->next=top______和____top=p____。27.空串的长度是____1____；空格串的长度是____2____。28.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是__2______。得分评卷人复查人三、名词解释（本大题共4小题，每小题3分，共12分）（1）栈：栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。（2）树。树是有根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根（3）森林：森林是很多棵树组成的图（4）满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.。（5）数据：在计算机系统中，各种字母、数字符号的组合、语音、图形、图像等统称为数据，数据经过加工后就成为信息。。（6）数据对象：数据对象是对软件必须理解的复合信息的抽象。所谓复合信息是指具有一系列不同性质或属性的事物，仅有单个值的事物(例如，宽度)不是数据对象。。（7）数据结构：是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。。（8）算法：得分评卷人复查人四、简答题（本大题共4小题，每小题5分，共20分）简述算法的五个重要特性。1、有穷性：一个算法必须保证执行有限步之后结束； 2、确切性：算法的每一步骤必须有确切的定义； 3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5、可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成（2）算法设计的基本要求。1,正确性2，可读性3，健壮性4，效率与低存储量需求（3）试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别数据类型它只表示数据的范围以及允许做的操作。数据结构表示数据的逻辑结构和物理结构，以及针对不同物理结构的数据的操作是如何实现的，并分析实现算法的效率。简述二叉树的特点。二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的根结点，和最多2个子结点。（5）已知一棵度为k的树中有个度为1的结点，个度为2的结点，。。。个度为k的结点，问该树中有多少个叶子节点？（7）写出下列树的先根序列和后根序列答案：先根序列：ABCEIJFGKHD后根序列：BIJEFKGHCDA（8）已知如图所示的有向图，请给出该图的：每个顶点的入/出度邻接矩阵答案：得分评卷人复查人五、程序阅读题（本大题共4小题，每小题5分，共20分）（1）简述以下算法的功能：statusA(linkedlistL){if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=null;}returnok;}答案:将链表的头放到链表尾，原链表第二位元素置为头（2）写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain（）{stackS;charx,y;initstack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!stackempty(S)){pop(S,y);printf(y)

;};printf(x);}答案：输出：stack（3）简述以下算法的功能（栈和队列的元素类型均为int）voidalgo3(Queue&Q){stackS;intd;initstack(S);while(!Queueempty(Q)){dequeue(Q,d);push(S,d);}while(!stackempty(S)){pop(S,d);enqueue(Q,d);}}答案：功能：将队列Q中的元素依次放入栈s中，并再次放入队列Q中，实现了Q中元素的倒置（4）简述以下算法的功能（栈的元素类型SElemType为int）。statusalgo2（stackS,inte）{stackT;intd;initstack(T);while(!Stackempty(S)){pop(S,d);if(d!=e)push(T,d);}while(!Stackempty(T)){pop(T,d);push(S,d);}}答案：剔除栈s中值为e的所有元素（5）写出下列程序段的输出结果（队列中的元素类型qelemtype为char）voidmain(){QueueQ;initqueue(Q);charx=’e’,y=’c’;enqueue(Q,’h’)

;enqueue(Q,’r’)

;enqueue(Q,y)

;dequeue(Q,x)

;enqueue(Q,x)

;dequeue(Q,x)

;enqueue(Q,’a’)

;while(

!Queueempty(Q)){dequeue(Q,y)

;printf(y)

;}printf(x)

;}答案;得分评卷人复查人五、编程应用题（本大题共5小题，第39、40、41小题每小题6分，第42、43小题每小题10分，共38分）（1）试写一个算法，自大至小依次输出顺序读入的三个整数X,Y和Z的值。If(x<y)swap(x,y);If(x<z)swap(x,z);If(y<z)swap(y,z);Printf("%d%d%d",x,y,z);（2）试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。（3）试将下列递推过程改写为递归过程。voidditui(intn){inti;i=n;while(i>1)printf(i--);}解：voidrecursion(intn){If(n=1)Printf(n);Else{Recursion(n-1);Printf(n);}2．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG，画出该二叉树；3.编写一个计算二叉树的深度的算法4.请回答下列问题：(1)英文缩写DAG的中文含义是什么？无回路有向图(DirectedAcyclicGraph)(2)请给出下面DAG图的全部拓扑排序。习题参考答案一．选择题1.从逻辑上可以把数据结构分为（C)两大类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构2.在下面的程序段中，对x的斌值语句的频度为（C)。for(t＝1；k＜＝n;k＋＋）for（j=1;j＜＝n;j＋＋）x=x十1；A.O(2n)B.O(n)C.O(n2)．D.O（1og2n)3.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。A.一定连续B．一定不连续C.不一定连续D.部分连续，部分不连续4.下面关于算法说法正确的是（D）。A.算法的时间复杂度一般与算法的空间复杂度成正比B.解决某问题的算法可能有多种，但肯定采用相同的数据结构C.算法的可行性是指算法的指令不能有二义性D.同一个算法，实现语言的级别越高，执行效率就越低5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。A.正确性B.健壮性C.可读性D.可移植性二、判断题1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√）2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（×）3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×）4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×）5.算法必须有输出，但可以没有输人。（√）三、筒答题1．常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？【答】常见的四种逻辑结构：①集合结构：数据元素之间是“属于同一个集合”②线性结构：数据元素之间存在着一对一的关系③树结构：数据元素之间存在着一对多的关系④结构：数据元素之间存在着多对多的关系。常见的四种存储结构有：①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。②链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。2．简述算法和程序的区别。【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。3.试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算这3方面的内容。【解答】略。4.运算是数据结构的一个重要方面。试举例说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同，使得两个结构具有显著不同的特性。【解答】比如顺序栈和循环队列，二者的逻辑结构都是线性结构，都采用顺序存储方式存储，但它们的运算不同，栈限定元素的插入和删除在栈顶进行，队列限定元素在队尾插入、在队首删除，因此它们是截然不同的数据结构。5．分析下列程序段中带标号“＃’’语句的执行频度(n为正整数）。（1)j＝1；k=0;while（j<=n-1）{j＋＋；k＋=j;／*＃*／【解答】