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

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

1、东大18春学期《数据结构Ⅰ》在线作业31、C2、B3、A4、D5、A一、单选题共20题，100分1、除第一层外，满二叉树中每一层结点个数是上一层结点个数的A1/2倍B1倍C2倍D3倍正确答案是：C2、假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为An-1BnCn+1Dn+2正确答案是：B3、用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是A逆拓扑有序B拓扑有序C无序的DA和B正确答案是：A4、根据数据元素的关键字直接计

2、算出该元素存储地址的存储方法是A顺序存储方法B链式存储方法C索引存储方法D散列存储方法正确答案是：D5、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为AO(n)BO(e)CO(n+e)DO(n2)正确答案是：A6、一个具有1025个结点的二叉树的高h为A11B10C11至1025之间D10至1024之间正确答案是：C7、链栈与顺序栈相比，比较明显的优点是A插入操作更加方便B删除操作更加方便C不会出现下溢的情况D不会出现上溢的情况正确答案是：D8、下列排序算法中，时间复杂度不受数据初

3、始状态影响，恒为0(nlog2n)的是A堆排序B冒泡排序C直接选择排序D快速排序正确答案是：A9、算法的时间复杂度主要取决于A问题的规模B待处理数据的初态C难度DA和B正确答案是：A10、下面的叙述不正确的是A线性表在链式存储时，查找第i个元素的时间同i的值成正比B线性表在链式存储时，查找第i个元素的时间同i的值无关C线性表在顺序存储时，查找第i个元素的时间同i的值成反比D线性表在顺序存储时，查找第i个元素的时间同i的值无关正确答案是：D11、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用A数据元素的相邻地址表示B数据元素在

4、表中的序号表示C指向后继元素的指针表示D数据元素的值表示正确答案是：C12、三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为A356B358C360D362正确答案是：B13、带行表的三元组表是稀疏矩阵的一种A顺序存储结构B链式存储结构C索引存储结构D散列存储结构正确答案是：A14、执行下列程序段后，串X的值为S=〞abcdefgh〞;T=〞xyzw〞;substr(X,S,2,strlen(T));substr(Y,S,s

5、telen(T),2);strcat(X,Y);A〞cdefgh〞B〞cdxyzw〞C〞cdefxy〞D〞cdefef〞正确答案是：D15、若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是A1234B4132C4231D4213正确答案是：C16、一棵具有n个结点的完全二叉树的树高度（深度）是Aëlognû+1Blogn+1CëlognûDlogn-1正确答案是：A17、当采用分块查找时，数据的组织方式为A数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序

6、，但块间必须有序，每块内最大（或最小）的数据组成索引块C数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D数据分成若干块，每块（除最后一块外）中数据个数需相同正确答案是：B18、一个有向无环图的拓扑排序序列是A一定唯一的B一定不唯一的C不一定唯一的D都不对正确答案是：C19、通常将链串的结点大小设置为大于1是为了A提高串匹配效率B提高存储密度C便于插入操作D便于删除操作正确答案是：B20、设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是A(rear-front

7、)%m==1Bfront==rearC(rear-front)%m==m-1Dfront==(rear+1)%m正确答案是：B