数据结构作业答案解析

《数据结构作业答案解析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、WORD文档下载可编辑第一章单选题1、下列关于算法的基本特征，说法不正确的是（）。能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。算法的确定性是指算法中的每一个步骤必须是有明确的定义，不允许模棱两可。算法的有穷性是指算法必须能在有限的时间内做完。算法与提供情报无关。[D]教师批改：D2、算法的时间复杂度取决于（）。问题的规模待处理的数据的初态问题的难度A和B[D]教师批改：D3、下列选项中，不是算法基本特征的是（）。可行性有穷性确定性高效率[D]教师批改：D4、通常一个好的算法应达到的目

2、标中，不包括（）。正确性可读性技巧性健壮性[C]教师批改：C5、在一般的计算机系统中，基本的运算和操作不包括（）。语法处理算术运算关系运算数据传输[A]教师批改：A6、工程上常用的分治法是（）。列举法归纳法减半递推技术回溯法[C]教师批改：C多选题7、算法设计的要求包括（）。正确性可读性健壮性唯一性[ABC]教师批改：A，B，C8、算法的时间复杂度应该与（）无关。所使用的计算机程序设计语言基本运算的执行次数程序编制者[ABD]教师批改：A，B，D9、下列关于算法的描述中，不正确的有（）。算法即是计

3、算机程序算法是解决问题的计算方法算法是排序方法算法是解决问题的有限运算序列[ABC]教师批改：A，B，C填空题16、所谓算法是指（）。教师批改：解题方案的准确而完整的描述17、算法的基本特征有（）、（）、（）和（）教师批改：能行性、确定性、有穷性和拥有足够的情报。技术资料专业分享WORD文档下载可编辑18、一个算法通常由两种基本要素组成，它们是（）和（）。教师批改：算法中对数据的运算和操作。算法的控制结构。19、工程上常用的几种算法设计方法有列举法、（）、（）、（）、（）和回溯法。教师批改：归纳法

4、、递推、递归、减半递推技术。20、算法的复杂度主要包括（）复杂度和（）复杂度。教师批改：时间、空间综合题21、设给定3个整数a，b，c，试写出寻找这3个整数的中数的算法；并分析在平均情况与最坏情况下，该算法分别要做多少次比较？寻找这3个整数的中数的算法用C语言描述如下（中数m由函数值返回）：intmid(inta,intb,intc){intm;m=a;if(m>=b){if(m>=c){if(b>=c)m=b;elsem=c;}}else{if(m<=c){if(b>=c)m=c;elsem=b

5、;}}return(m);}假设a，b，c中的每一个数为中数的概率相等（均为1/3）。由于当a为中数时需要比较2次，b或c为中数时均需要比较3次，因此，在平均情况下上述算法所需要的比较次数为2*（1/3）+3*（1/3）+3*（1/3）=8/3即在平均情况下，上述算法需要比较8/3次。在最坏情况下，上述算法需要比较3次（当b或c为中数时）。第二章选择题1、下列排序方法中，哪一个是稳定的排序方法（）。归并排序稀尔排序堆排序快速排序[A]教师批改：A2、设输入序列为1，2，3，4，借助一个栈得到的输出

6、序列可以是（）。3，4，1，24，2，1，34，1，2，31，3，4，2[D]教师批改：D3、用数组A[m]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为（）。(rear+front)%m(rear-front+m)%m(rear-front)%m(rear-front+1)%m[D]教师批改：B4、对于下三角矩阵A，若采用一个一维数组B以行为主顺序存放压缩矩阵A，则A43存放在（）中.B7B8B9B10[C]教师批改：C5、深度为5的二叉树至多有（）个

7、结点。1632技术资料专业分享WORD文档下载可编辑3110[C]教师批改：C6、一个有n个顶点的无向图最多有（）条边。nn(n-1)n(n-1)/22n[C]教师批改：C7、下列说法不正确的是（）。线性表可以顺序存储线性表可以链式存储线性表在顺序存储下可以对分查找线性表在链式存储下可以对分查找[D]教师批改：D8、栈和队列的共同点是（）。都是先进后出都是先进先出只允许在端点处插入和删除元素没有共同点[C]教师批改：C9、若进栈序列为A、B、C、D(进栈过程可以出栈)，不可能得到的出栈序列是（）。

8、A、D、C、BB、C、D、AC、A、D、BC、D、B、A[C]教师批改：C10、在一个单链表中，若p结点不是最后一结点。在p结点之后插入s结点的正确操作是（）。s->next=p;p->next=s;s->next=p->next;p->next=s;s->next=p;p=p;p->next=s;s->next=p;[B]教师批改：B11、由3个结点可以构造出多少种不同的二叉树（）。2458[C]教师批改：C填空题27、若一棵完全二叉树共有100个结点，则其叶子结点数为（）。教师