16春天大《数据结构》在线作业.docx

16春天大数据结构在线作业 谋学网 数据结构在线作业二 一、单选题 1. 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树的根结点的左子树的结点数为。 . N1-1 . N2-1 . N2+N3 . N1+N3 正确答案： 2. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的。 . 先序遍历 . 中序遍历 . 后序遍历 . 按层遍历 正确答案： 3. 设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是。 . n-i . n-1-i . n+l -i . 不能确定 正确答案： 4. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。 . n . (n-1)的平方 . n-1 . n的平方 正确答案： 5. 二叉排序树可以得到一个从小到大的有序序列。 . 先序遍历 . 中序遍历 . 后序遍历 . 层次遍历 正确答案： 6. 快速排序方法在情况下最不利于发挥其长处。 . 要排序的数据量太大 . 要排序的数据中含有多个相同值 谋学网 . 要排序的数据已基本有序 . 要排序的数据个数为奇数 正确答案： 7. 设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列存储方式最节省运算时间。 . 单向链表 . 单向循环链表 . 双向链表 . 双向循环链表 正确答案： 8. 数组的逻辑结构不同于下列的逻辑结构。 . 线性表 . 栈 . 队列 . 树 正确答案： 9. 采用线性探测法解决冲突问题，所产生的一系列后继散列地址。 . 必须大于等于原散列地址 . 必须小于等于原散列地址 . 可以大于或小于但不能等于原散列地址 . 地址大小没有具体限制 正确答案： 10. 具有6个顶点的无向图至少应有条边才能确保是一个连通图。 . 5 . 6 . 7 . 8 正确答案： 11. 堆的形状是一棵。 . 二叉排序树 . 满二叉树 . 完全二叉树 . 平衡二叉树 正确答案： 12. 设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动个元素。 . n-i . n+l -i . n-1-i . i 正确答案： 13. 用某种排序方法对线性表进行排序时，元素序列的变化情况如下： 25，84，21，47，15，27，68，35，20； 20，15，21，25，47，27，68，35，84； 15，20，21，25，35，27，47，68，84； 15，20，21，25，27， 谋学网 35，47，68，84。则所采用的排序方法是。 . 选择排序 . 希尔排序 . 归并排序 . 快速排序 正确答案： 14. 设数据结构=(，R)，其中=1，2，3，4，R=r，r=<1，2>，<2，3>，<3，4>，<4，1>，则数据结构是。 . 线性结构 . 树型结构 . 图型结构 . 集合 正确答案： 15. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列的一端的方法，称为。 . 希尔排序 . 归并排序 . 插入排序 . 选择排序 正确答案： 16. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为。 . O(n) . O(nlog2n) . O(n2 ) . O(1og2n) 正确答案： 17. 设有向无环图G中的有向边集合=<1，2>，<2，3>，<3，4>，<1，4>，则下列属于该有向图G的一种拓扑排序序列的是。 . 1，2，3，4 . 2，3，4，1 . 1，4，2，3 . 1，2，4，3 正确答案： 18. 设一组初始记录关键字序列为(Q，H，Y，P，M，S，R，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是。 . F，H，P，M，Q，R，S，Y，X . P，S，Q，F，X，R，H，M，Y . ，R，F，Q，M，S，Y，P，H，X . H，Q，P，M，S，R，F，X，Y 正确答案： 19. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用。 . 求关键路径的方法 . 求最短路径的ijkstr方法 谋学网 . 宽度优先遍历算法 . 深度优先遍历算法 正确答案： 20. 把一棵树转换为二叉树后，这棵二叉树的形态是。 . 唯一的 . 有多种 . 有多种，但根结点都没有左孩子 . 有多种，但根结点都没有右孩子 正确答案： 21. 具有4个顶点的无向完全图有条边。 . 6 . 12 . 16 . 20 正确答案： 22. 两个字符串相等的充要条件是。 . 两个字符串的长度相等 . 两个字符串中对应位置上的字符相等 . 同时具备和两个条件 . 以上答案都不对 正确答案： 23. 在二叉排序树中插入一个关键字值的平均时间复杂度为。 . O(n) . O(1og2n) . O(nlog2n) . O(n2 ) 正确答案： 24. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 . 1/2 . 1 . 2 . 4 正确答案： 25. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是。 . 插入排序 . 选择排序 . 快速排序 . 归并排序 正确答案： 26. 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为。 . top=top+1; . top=top-1; . top->nxt=top; 谋学网 . top=top->nxt; 正确答案： 27. 散列表的平均查找长度。 . 与处理冲突方法有关而与表的长度无关 . 与处理冲突方法无关而与表的长度有关 . 与处理冲突方法有关而与表的长度有关 . 与处理冲突方法无关而与表的长度无关 正确答案： 28. 二叉树是非线性数据结构，所以。 . 它不能用顺序存储结构存储 . 它不能用链式存储结构存储 . 顺序存储结构和链式存储结构都能存储 . 顺序存储结构和链式存储结构都不能使用 正确答案： 29. 设有一个10阶的下三角矩阵，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则54地址与00的地址之差为。 . 10 . 19 . 28 . 55 正确答案： 30. 设完全无向图中有n个顶点，则该完全无向图中有条边。 . n(n-1)/2 . n(n-1) . n(n+1)/2 . (n-1)/2 正确答案： 31. 对线性表进行二分查找时，要求线性表必须。 . 以顺序方式存储 . 以链接方式存储 . 以顺序方式存储，且结点按关键字有序排序 . 以链接方式存储，且结点按关键字有序排序 正确答案： 32. 对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为。 . 从第0个元素往后查找该数据元素 . 从第1个元素往后查找该数据元素 . 从第n个元素往开始前查找该数据元素 . 与查找顺序无关 正确答案： 33. 设某棵二叉树的高度为10，则该二叉树上叶子结点最多有。 . 20 . 256 谋学网 . 512 . 1024 正确答案： 34. 不含任何结点的空树。 . 是一棵树 . 是一棵二叉树 . 是一棵树也是一棵二叉树 . 既不是树也不是二叉树 正确答案： 35. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为. . n . n/2 . (n+1)/2 . (n-1)/2 正确答案： 36. 一个有n个顶点的无向图最多有条边。 . n . n(n-1) . n(n-1)/2 . 2n 正确答案： 37. 设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为。 . 6 . 11 . 5 . 6.5 正确答案： 38. 下述几种排序方法中，要求内存量最大的是。 . 插入排序 . 选择排序 . 快速排序 . 归并排序 正确答案： 39. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为。 . 129 . 219 . 189 . 229 正确答案： 40. 设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为。 . 5，3，4，6，1，2 谋学网 . 3，2，5，6，4，1 . 3，1，2，5，4，6 . 1，5，4，6，2，3 正确答案：