东大16秋学期《数据结构Ⅱ》在线作业1 辅导资料.doc

谋学网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. 在分块索引的在顺序表中查找，算法中采用的最佳技术是. 穷举法 . 贪心法 . 分治法 . 分支限界法正确答案：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个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 . 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. 链栈与顺序栈相比，比较明显的优点是. 插入操作更加方便 . 删除操作更加方便. 不会出现下溢的情况 . 不会出现上溢的情况正确答案：10. 在长度为n的顺序表中删除第i个元素(1in)时，元素移动的次数为 . n-i+1 . i . i+1 . n-i正确答案：11. 数据的不可分割的最小标识单位是 . 数据项 . 数据记录 . 数据元素 . 数据变量正确答案：12. 倒排文件的主要优点是 . 便于进行插入和删除运算 . 便于进行文件的恢复 . 便于进行多关键字查询 . 节省存储空间正确答案：13. 导致栈上溢的操作是. 栈满时执行的出栈 . 栈满时执行的入栈. 栈空时执行的出栈 . 栈空时执行的入栈正确答案：14. 队列和栈的主要区别是 . 逻辑结构不同 . 存储结构不同 . 所包含的运算个数不同 . 限定插入和删除的位置不同正确答案：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. 连通图是指图中任意两个顶点之间 . 都连通的无向图 . 都不连通的无向图 . 都连通的有向图 . 都不连通的有向图正确答案：18. 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为. n-1 . ?n/m?-1 . (n-1)/(m-1) . n/(m-1)-1 正确答案：19. S算法可用来解决单源最短路径问题的条件是当各边上的权值. 均相等 . 均互不相等 . 不一定相等 . 任意值正确答案：20. 下面的叙述不正确的是 . 线性表在链式存储时，查找第i个元素的时间同i的值成正比. 线性