东大18秋学期《数据结构Ⅰ》在线作业2辅导资料

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

1、东大18秋学期《数据结构Ⅰ》在线作业21、D2、A3、A4、D5、C一、单选题共20题，100分1、设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是AA，B，C，DBD，C，B，ACA，C，D，BDD，A，B，C正确答案是：D2、算法的时间复杂度主要取决于A问题的规模B待处理数据的初态C难度DA和B正确答案是：A3、文件中，主关键字能唯一标识A一个记录B一组记录C一个类型D一个文件正确答案是：A4、下列程序段for(i=1;i<=n;i++)A[i,j]=0;的时间复杂度是AO(1)BO(0)CO(1+n)DO(n)正确答案是：D5、二叉树中第5层上的

2、结点个数最多为A8B15C16D32正确答案是：C6、有关二叉树下列说法正确的是A二叉树的度为2B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2D二叉树中任何一个结点的度都为2正确答案是：B7、抽象数据类型的三个组成部分分别为A数据对象、数据关系和基本操作B数据元素、逻辑结构和存储结构C数据项、数据元素和数据类型D数据元素、数据结构和数据类型正确答案是：A8、对n个关键字的序列进行快速排序，平均情况下的空间复杂度为AO(1)BO(logn)CO(n)DO(nlogn)正确答案是：B9、用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为A5B6

3、C8D9正确答案是：A10、十字链表的三元组表是稀疏矩阵的一种A顺序存储结构B链式存储结构C索引存储结构D散列存储结构正确答案是：B11、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是AG中有弧BG中有一条从Vi到Vj的路径CG中没有弧DG中有一条从Vj到Vi的路径正确答案是：D12、如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为A插入排序B归并排序C冒泡排序D堆排序正确答案是：A13、在待排关键字序列基本有序的前提下，效率最高的排序方法是A直接插入排序B快速

4、排序C直接选择排序D归并排序正确答案是：A14、下面关于线性表的叙述中，错误的是A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。正确答案是：B15、在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是ALL型BLR型CRL型DRR型正确答案是：B16、下面说法错误的是(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂

5、度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A(1)B(1),(2)C(1),(4)D(3)正确答案是：C17、判定“带头结点的链队列为空”的条件是AQ.front==NULLBQ.rear==NULLCQ.front==Q.rearDQ.front!=Q.rear正确答案是：C18、按排序过程中依据的原则分类，快速排序属于A插入类的排序方法B选择类的排序方法C交换类的排序方法D.归并类的排序方法正确答案是：C19、设有一个顺序栈的入栈序列是a、b、c，

6、则3个元素都出栈的可能不同排列个数为A4B5C6D7正确答案是：B20、ISAM文件的周期性整理是为了空出A磁道索引B柱面索引C柱面基本区D柱面溢出区正确答案是：D