《东大16秋学期《数据结构Ⅱ》在线作业1 辅导资料》由会员分享，可在线阅读，更多相关《东大16秋学期《数据结构Ⅱ》在线作业1 辅导资料（6页珍藏版）》请在金锄头文库上搜索。
1、 谋学网 16 秋学期数据结构在线作业 1 一、单选题（共 20 道试题，共 100 分。 ）1. 数据元素及其关系在计算机存储器内的表示，称为数据的. 逻辑结构 . 存储结构 . 线性结构 . 非线性结构正确答案：2. 对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素 5 为基准的一次划分的结果为. （1，2，3，4，5，6，7，8） . （1，4，3，2，5，7，8，6）. （2，1，4，3，5，7，8，6） . （8，7，6，5，4，3，2，1）正确答案：3. 在分块索引的在顺序表中查找，算法中采用的最佳技术是. 穷举法 . 贪心法 . 分治法 . 分支限界法正
2、确答案：4. 谋学网 已知一棵完全二叉树有 64 个叶子结点，则该树可能达到的最大深度为. 7. 8. 9. 10正确答案：5. 在一个单链表中，若删除*p 结点的后继结点，则执行操作. q=p-nxt;p-nxt=q-nxt;r(q); . p=p-nxt;p-nxt=p-nxt-nxt;r(p); . p-nxt=q-nxt;r(p-nxt); . p=p-nxt-nxt;r(p-nxt); 正确答案：6. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是. 有向完全图 . 连通图 . 强连通图 . 有向无环图正确答案：7. 在具有 n 个结点的有序单链表中插入一个新结点并使链表
3、仍然有序的时间复杂度是. O(1) . O(n) . O(nlogn) . O(n2)正确答案：8. 设 p 指向单链表中的一个结点，s 指向待插入的结点，则下述程序段的功能是s - nxt = p - nxt; p - nxt = s;t = p - t; p - t = s - t; s -t = t; 谋学网 . 结点 p 与结点 s 的数据域互换. 在 p 所指结点的元素之前插入元素. 在 p 所指结点的元素之后插入元素 . 在结点 p 之前插入结点 s正确答案：9. 链栈与顺序栈相比，比较明显的优点是. 插入操作更加方便 . 删除操作更加方便. 不会出现下溢的情况 . 不会出现上溢的
4、情况正确答案：10. 在长度为 n 的顺序表中删除第 i 个元素(1in)时，元素移动的次数为. n-i+1 . i . i+1 . n-i正确答案：11. 数据的不可分割的最小标识单位是. 数据项 . 数据记录 . 数据元素 . 数据变量正确答案：12. 倒排文件的主要优点是. 便于进行插入和删除运算 . 便于进行文件的恢复 谋学网 . 便于进行多关键字查询 . 节省存储空间正确答案：13. 导致栈上溢的操作是. 栈满时执行的出栈 . 栈满时执行的入栈. 栈空时执行的出栈 . 栈空时执行的入栈正确答案：14. 队列和栈的主要区别是. 逻辑结构不同 . 存储结构不同 . 所包含的运算个数不同
5、. 限定插入和删除的位置不同正确答案：15. 若要在 O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向. 各自的头结点 . 各自的尾结点 . 各自的第一个元素结点 . 一个表的头结点，另一个表的尾结点正确答案：16. 若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是. 2，4，3，1，5，6 . 3，2，4，1，6，5 谋学网 . 4，3，2，1，5，6 . 2，3，5，1，6，4正确答案：17. 连通图是指图中任意两个顶点之间. 都连通的无向图 . 都不连通的无向图 . 都连通的有向图 . 都不连通的有向图正确
6、答案：18. 若度为 m 的哈夫曼树中，其叶结点个数为 n，则非叶结点的个数为. n-1 . ?n/m?-1 . (n-1)/(m-1) . n/(m-1)-1 正确答案：19. S 算法可用来解决单源最短路径问题的条件是当各边上的权值. 均相等 . 均互不相等 . 不一定相等 . 任意值正确答案：20. 下面的叙述不正确的是. 线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比. 线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关 谋学网 . 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成反比. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关正确答案：
