东大18秋学期《数据结构Ⅰ》在线作业2.doc

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

1、优选(单选题)1:设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A:A，B，C，DB:D，C，B，AC:A，C，D，BD:D，A，B，C正确答案：(单选题)2:算法的时间复杂度主要取决于A:问题的规模B:待处理数据的初态C:难度D:A和B正确答案：(单选题)3:文件中，主关键字能唯一标识A:一个记录B:一组记录C:一个类型D:一个文件正确答案：(单选题)4:14/14优选下列程序段for(i=1;i<=n;i++)A[i,j]=0;的时间复杂度是A:O(1)B:O(0)C:O(1+n)D:O(n)正确答案：(单选题)5:二叉

2、树中第5层上的结点个数最多为A:8B:15C:16D:32正确答案：(单选题)6:有关二叉树下列说法正确的是A:二叉树的度为2B:一棵二叉树的度可以小于2C:二叉树中至少有一个结点的度为2D:二叉树中任何一个结点的度都为2正确答案：(单选题)7:抽象数据类型的三个组成部分分别为14/14优选A:数据对象、数据关系和基本操作B:数据元素、逻辑结构和存储结构C:数据项、数据元素和数据类型D:数据元素、数据结构和数据类型正确答案：(单选题)8:对n个关键字的序列进行快速排序，平均情况下的空间复杂度为A:O(1)B:O(logn)C:O(n)D:O(nlog

3、n)正确答案：(单选题)9:用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为A:5B:6C:8D:9正确答案：(单选题)10:十字链表的三元组表是稀疏矩阵的一种A:顺序存储结构14/14优选B:链式存储结构C:索引存储结构D:散列存储结构正确答案：(单选题)11:在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是A:G中有弧B:G中有一条从Vi到Vj的路径C:G中没有弧D:G中有一条从Vj到Vi的路径正确答案：(单选题)12:如果在排序过程中，每次均将一个待排序的记录按关键

4、字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为A:插入排序B:归并排序C:冒泡排序D:堆排序正确答案：(单选题)13:在待排关键字序列基本有序的前提下，效率最高的排序方法是A:直接插入排序14/14优选B:快速排序C:直接选择排序D:归并排序正确答案：(单选题)14:下面关于线性表的叙述中，错误的是A:线性表采用顺序存储，必须占用一片连续的存储单元。B:线性表采用顺序存储，便于进行插入和删除操作。C:线性表采用存储，不必占用一片连续的存储单元。D:线性表采用存储，便于插入和删除操作。正确答案：(单选题)15:在平衡二叉树中插入一个结点后

5、引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是A:LL型B:LR型C:RL型D:RR型正确答案：(单选题)16:下面说法错误的是(1）算法原地工作的含义是指不需要任何额外的辅助空间14/14优选（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A:(1)B:(1),(2)C:(1),(4)D:(3)正确答案：(单选题)17:判定“带头结

6、点的链队列为空”的条件是A:Q.front==NULLB:Q.rear==NULLC:Q.front==Q.rearD:Q.front!=Q.rear正确答案：(单选题)18:按排序过程中依据的原则分类，快速排序属于A:插入类的排序方法B:选择类的排序方法C:交换类的排序方法D:.归并类的排序方法正确答案：14/14优选(单选题)19:设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为A:4B:5C:6D:7正确答案：(单选题)20:ISAM文件的周期性整理是为了空出A:磁道索引B:柱面索引C:柱面基本区D:柱面溢出区正确答案

7、：(单选题)1:设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A:A，B，C，DB:D，C，B，AC:A，C，D，BD:D，A，B，C正确答案：(单选题)2:14/14优选算法的时间复杂度主要取决于A:问题的规模B:待处理数据的初态C:难度D:A和B正确答案：(单选题)3:文件中，主关键字能唯一标识A:一个记录B:一组记录C:一个类型D:一个文件正确答案：(单选题)4:下列程序段for(i=1;i<=n;i++)A[i,j]=0;的时间复杂度是A:O(1)B:O(0)C:O(1+n)D:O(n)正确答案：(单选题)5:二叉树

8、中第5层上的结点个数最多为14/14优选A:8B:15C:16D:32正确答案：(单选题)6:有关二叉树下列