东大21秋《数据结构Ⅱ》在线作业3-答案

1、数据结构在线平时作业3试卷总分:100 得分:100一、单选题 (共 20 道试题,共 100 分)1.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为O(n)O(e)O(n+e)O(n2)提示：本题为课程辅导试题，请参考课本完成！：A2.索引非顺序文件的特点是主文件无序，索引表有序主文件有序，索引表无序主文件有序，索引表有序主文件无序，索引表无序提示：本题为课程辅导试题，请参考课本完成！：A3.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A11的存储地址为420，A33的存储地址为446，则A55的存储地址为470471472

2、473提示：本题为课程辅导试题，请参考课本完成！：C4.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是p=p-next;p-next=p-next-next;p-next=p;p=p-next-next;提示：本题为课程辅导试题，请参考课本完成！：B5.引入二叉线索树的目的是加快查找结点的前驱或后继的速度为了能在二叉树中方便的进行插入与删除为了能方便的找到双亲使二叉树的遍历结果唯一提示：本题为课程辅导试题，请参考课本完成！：A6.一棵树高为K的完全二叉树至少的结点是2k 12k-1 12k-12k提示：本题为课程辅导试题，请参考课本完成！：C7.下列查找算法中，平均查找长度

3、与元素个数n不直接相关的查找方法是分块查找顺序查找二分查找散列查找提示：本题为课程辅导试题，请参考课本完成！：D8.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是1234提示：本题为课程辅导试题，请参考课本完成！：B9.已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为561617提示：本题为课程辅导试题，请参考课本完成！：C10.在长度为n的顺序表中删除第i个元素(1in)时，元素移动的次数为n-i+1ii+1n-i提示：本题为课程辅导试题，请参考课本完成！：D1

4、1.从逻辑上可以把数据结构分为两大类，即动态结构、静态结构顺序结构、链式结构线性结构、非线性结构初等结构、构造型结构提示：本题为课程辅导试题，请参考课本完成！：C12.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用深度优先搜索算法广度优先搜索算法求最小生成树的prim算法拓扑排序算法提示：本题为课程辅导试题，请参考课本完成！：B13.为便于判别有向图中是否存在回路，可借助于广度优先搜索算法最小生成树算法最短路径算法拓扑排序算法提示：本题为课程辅导试题，请参考课本完成！：D14.队列和栈的主要区别是逻辑结构不同存储结构不同所包含的运算个数不同限定插入和删除的位置不同提示：本题为课程辅

5、导试题，请参考课本完成！：D15.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=head,则p指向头结点p指向尾结点p的直接后继是头结点P的直接后继是尾结点提示：本题为课程辅导试题，请参考课本完成！：D16.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上操作的有限集合映象的有限集合类型的有限集合关系的有限集合提示：本题为课程辅导试题，请参考课本完成！：D17.通常将链串的结点大小设置为大于1是为了提高串匹配效率提高存储密度便于插入操作便于删除操作提示：本题为课程辅导试题，请参考课本完成！：B18.对长度为n的关键字序列进行堆排序的空间复杂度为O（log2n）O（1）O（n）O（n*log2n）提示：本题为课程辅导试题，请参考课本完成！：B19.在一个带权连通图G中，权值最小的边一定包含在G的最小生成树中深度优先生成树中广度优先生成树中深度优先生成森林中提示：本题为课程辅导试题，请参考课本完成！：A20.假设以数组Am存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为