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

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

1、www.vu8o.com------------------------------------------------------------------------------------------------------------------------------(单选题)1:除第一层外，满二叉树中每一层结点个数是上一层结点个数的A:1/2倍B:1倍C:2倍D:3倍正确答案:(单选题)2:假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为

2、A:n-1B:nC:n+1D:n+2正确答案:(单选题)3:用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是A:逆拓扑有序B:拓扑有序C:无序的D:A和B正确答案:(单选题)4:根据数据元素的关键字直接计算出该元素存储地址的存储方法是A:顺序存储方法B:链式存储方法C:索引存储方法D:散列存储方法正确答案:(单选题)5:一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为A:O(n)B:O(e)C:O(n+e)D:O(n2)正确答案:(单选

3、题)6:一个具有1025个结点的二叉树的高h为A:11B:10C:11至1025之间www.vu8o.com------------------------------------------------------------------------------------------------------------------------------D:10至1024之间正确答案:(单选题)7:链栈与顺序栈相比，比较明显的优点是A:插入操作更加方便B:删除操作更加方便C:不会出现下溢的情况D:不会出现上溢的情况正确答

4、案:(单选题)8:下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是A:堆排序B:冒泡排序C:直接选择排序D:快速排序正确答案:(单选题)9:算法的时间复杂度主要取决于A:问题的规模B:待处理数据的初态C:难度D:A和B正确答案:(单选题)10:下面的叙述不正确的是A:线性表在链式存储时，查找第i个元素的时间同i的值成正比B:线性表在链式存储时，查找第i个元素的时间同i的值无关C:线性表在顺序存储时，查找第i个元素的时间同i的值成反比D:线性表在顺序存储时，查找第i个元素的时间同i的值无关正确答案:(

5、单选题)11:在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用A:数据元素的相邻地址表示B:数据元素在表中的序号表示C:指向后继元素的指针表示D:数据元素的值表示正确答案:(单选题)12:三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为A:356B:358www.vu8o.com-----------------------------------------------------------------

6、-------------------------------------------------------------C:360D:362正确答案:(单选题)13:带行表的三元组表是稀疏矩阵的一种A:顺序存储结构B:链式存储结构C:索引存储结构D:散列存储结构正确答案:(单选题)14:执行下列程序段后，串X的值为S=〞abcdefgh〞;T=〞xyzw〞;substr(X,S,2,strlen(T));substr(Y,S,stelen(T),2);strcat(X,Y);A:〞cdefgh〞B:〞cdxyzw〞C:〞c

7、defxy〞D:〞cdefef〞正确答案:(单选题)15:若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是A:1234B:4132C:4231D:4213正确答案:(单选题)16:一棵具有n个结点的完全二叉树的树高度（深度）是A:?logn?+1B:logn+1C:?logn?D:logn-1正确答案:(单选题)17:当采用分块查找时，数据的组织方式为A:数据分成若干块，每块内数据有序B:数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的

8、数据组成索引块C:数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块www.vu8o.com------------------------------------------------------------------------------------------