东大18春学期《数据结构Ⅱ》在线作业2

《东大18春学期《数据结构Ⅱ》在线作业2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东大18春学期《数据结构Ⅱ》在线作业21、D2、B3、B4、A5、B一、单选题共20题，100分1、对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为A1，2，3B9，5，2，3C9，5，3D9，4，2，3正确答案是：D2、算法分析的目的是A辨别数据结构的合理性B评价算法的效率C研究算法中输入与输出的关系D鉴别算法的可读性正确答案是：B3、在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系A不一定相同B都相同C都不相同D互为逆序正确答案是：B4、用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为A5B6C8D9正确答案是：A5、在

2、关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为A4，4，3B4，3，3C3，4，4D．3，3，4正确答案是：B6、在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是A1B2C3D5正确答案是：C7、抽象数据类型的三个组成部分分别为A数据对象、数据关系和基本操作B数据元素、逻辑结构和存储结构C数据项、数据元素和数据类型D数据元素、数据结构和数据类型正确答案是：A8、用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为An-1BnCn

3、+lD2n正确答案是：C9、BFS算法可用来解决单源最短路径问题的条件是当各边上的权值A均相等B均互不相等C不一定相等D任意值正确答案是：A10、一个具有1025个结点的二叉树的高h为A11B10C11至1025之间D10至1024之间正确答案是：C11、以下数据结构中，属于线性结构的是A广义表B二叉树C稀疏矩阵D串正确答案是：A12、下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是A堆排序B冒泡排序C直接选择排序D快速排序正确答案是：A13、树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是A树的后根遍历与其对应的二叉树的后根遍历相同B树

4、的后根遍历与其对应的二叉树的中根遍历相同C树的先根遍历与其对应的二叉树的中根遍历相同D以上都不对正确答案是：B14、数据元素及其关系在计算机存储器内的表示，称为数据的A逻辑结构B存储结构C线性结构D非线性结构正确答案是：B15、下面关于数据结构正确的说法是A一种数据类型B数据的存储结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合正确答案是：D16、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是A队列B栈C线性表D有序表正确答案是：A17、若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序

5、列是A1234B4132C4231D4213正确答案是：C18、已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到AP=″SCIENCE″BP=″STUDY″CS=″SCIENCE″DS=″STUDY″正确答案是：A19、若是有向图的一条边，则称Avi邻接于vjBvj邻接于viCvi和vj相互邻接Dvi与vj不相邻接正确答案是：B20、算法的时间复杂度主要取决于A问题的规模B待处理数据的初态C难度DA和B

6、正确答案是：A