东北大学16春学期《数据结构Ⅰ》在线作业参考答案..doc

东北大学16春学期《数据结构Ⅰ》在线作业参考答案 一、单选题：1. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素， 再加入两个元素后，rear和front的值分别为???????????(满分:5)????A. 1和 5?????B. 2和4?????C.??4和2????D.??5和1?2. 为便于判别有向图中是否存在回路，可借助于??????????(满分:5)????A.??广度优先有哪些信誉好的足球投注网站算法????B.??最小生成树算法??????C. 最短路径算法?????D. 拓扑排序算法3. 连通网的最小生成树是其所有生成树中??????????(满分:5)????A. 顶点集最小的生成树????B.??边集最小的生成树?????C.??顶点权值之和最小的生成树?????D. 边的权值之和最小的生成树4. 上溢现象通常出现在??????????(满分:5)????A. 顺序栈的入栈操作过程中????B. 顺序栈的出栈操作过程中????C. 链栈的入栈操作过程中????D. 链栈的出栈操作过程中5. ALV树是一种平衡的二叉排序树，树中任一结点的??????????(满分:5)????A.??左、右子树的高度均相同??????B.??左、右子树高度差的绝对值不超过1?????C. 左子树的高度均大于右子树的高度?????D.??左子树的高度均小于右子树的高度6. ISAM文件的周期性整理是为了空出??????????(满分:5)????A. 磁道索引????B. 柱面索引?????C. 柱面基本区????D. 柱面溢出区7. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t 到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到???????????(满分:5)????A. P=″SCIENCE″????B.??P=″STUDY″?????C.??S=″SCIENCE″????D.??S=″STUDY″8. 链栈与顺序栈相比，比较明显的优点是??????????(满分:5)????A. 插入操作更加方便????B.??删除操作更加方便????C. 不会出现下溢的情况????D.??不会出现上溢的情况9. 当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为??????????(满分:5)????A. A．左子树的叶子结点?????B. B．左子树的分支结点?????C. C．右子树的叶子结点?????D. D．右子树的分支结点10. 高度为5的完全二叉树中含有的结点数至少为???????????(满分:5)????A. 16????B. 17????C. 31????D. 3211. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为??????????(满分:5)????A. 0????B. 1????C. 48????D. 4912. 快速排序在最坏情况下的时间复杂度是??????????(满分:5)????A. O(n2log2n)?????B. O(n2)????C. O(nlog2n)????D. O(log2n)13. for（i=0；i；i++） for（j=0；j；j++）c［i］［j］=0；for（i=0；i；i++）for（j=0；j；j++）for（k=0；k；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］； 上列程序的时间复杂度为??????????(满分:5)????A.??O（m+n×t）????B.??O（m+n+t）?????C.??O（m×n×t）????D.??O（m×t+n）14. 根据数据元素的关键字直接计算出该元素存储地址的存储方法是??????????(满分:5)????A.??顺序存储方法????B. 链式存储方法?????C.??索引存储方法????D. 散列存储方法15. 在计算机内实现递归算法时所需的辅助数据结构是??????????(满分:5)????A. 栈?????B. 队列????C. 树????D. 图16. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的???????????(满分:5)????A. 1/2倍????B.??1倍??????C. 2倍????D. 3倍17. 一棵完全二叉树上有1001个结点，