天津大学18秋《数据结构》在线作业二参考

《数据结构》在线作业二

天大作业答案


一、单选题：
1. 对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。
    A. 静态查找表
    B. 动态查找表
    C. 静态查找表与动态查找表
    D. 两种表都不适合
    正确答案:——B——
2. 设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。
    A. 1，2，3，4
    B. 2，3，4，1
    C. 1，4，2，3
    D. 1，2，4，3
    正确答案:——A——
3. （）二叉排序树可以得到一个从小到大的有序序列。
    A. 先序遍历
    B. 中序遍历
    C. 后序遍历
    D. 层次遍历
    正确答案:——B——
4. 二叉树是非线性数据结构，所以（）。
    A. 它不能用顺序存储结构存储
    B. 它不能用链式存储结构存储
    C. 顺序存储结构和链式存储结构都能存储
    D. 顺序存储结构和链式存储结构都不能使用
    正确答案:————
5. 设完全无向图中有n个顶点，则该完全无向图中有（）条边。
    A. n(n-1)/2
    B. n(n-1)
    C. n(n+1)/2
    D. (n-1)/2
    正确答案:————
6. 在二叉排序树中插入一个关键字值的平均时间复杂度为（）。
    A. O(n)    奥鹏答案

    B. O(1og2n)
    C. O(nlog2n)
    D. O(n2)
    正确答案:————
7. 对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为（）。
    A. 从第0个元素往后查找该数据元素
    B. 从第1个元素往后查找该数据元素
    C. 从第n个元素往开始前查找该数据元素
    D. 与查找顺序无关
    正确答案:————
8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。
    A. 129
    B. 219
    C. 189
    D. 229
    正确答案:————
9. 采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。
    A. O（n2）
    B. O(nlog2n)
    C. O(n)
    D. O(log2n)
    正确答案:————
10. 设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
    A. n-i
    B. n+l-i
    C. n-1-i
    D. i
    正确答案:————
11. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。
    A. 希尔排序
    B. 归并排序
    C. 插入排序
    D. 选择排序
    正确答案:————
12. 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。
    A. N1-1
    B. N2-1
    C. N2+N3
    D. N1+N3
    正确答案:————
13. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。
    A. O(n)
    B. O(nlog2n)
    C. O(n2)
    D. O(1og2n)
    正确答案:————
14. 顺序查找法适合于存储结构为（）的线性表。
    A. 散列存储
    B. 顺序存储或链接存储
    C. 压缩存储
    D. 索引存储
    正确答案:————
15. 设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。
    A. n-i
    B. n-1-i
    C. n+l-i
    D. 不能确定
    正确答案:————
16. 用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴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。则所采用的排序方法是（）。
    A. 选择排序
    B. 希尔排序
    C. 归并排序
    D. 快速排序
    正确答案:————
17. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）.
    A. n
    B. n/2
    C. (n+1)/2
    D. (n-1)/2
    正确答案:————
18. 下列程序段的时间复杂度为（）。for(i=0；i<m；i++)for(j=0；j<t；j++)c[j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[j]=c[j]+a[k]*b[k][j]；
    A. O(m*n*t)
    B. O(m+n+t)
    C. O(m+n*t)
    D. O(m*t+n)
    正确答案:————
19. 对线性表进行二分查找时，要求线性表必须（）。
    A. 以顺序方式存储
    B. 以链接方式存储
    C. 以顺序方式存储，且结点按关键字有序排序
    D. 以链接方式存储，且结点按关键字有序排序
    正确答案:————
20. 二叉排序树中左子树上所有结点的值均（）根结点的值。
    A. <
    B. >
    C. =
    D. !=
    正确答案:————
21. 设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。
    A. aedfcb
    B. acfebd
    C. aebcfd
    D. aedfbc
    正确答案:————
22. 快速排序方法在（）情况下最不利于发挥其长处。
    A. 要排序的数据量太大
    B. 要排序的数据中含有多个相同值
    C. 要排序的数据已基本有序
    D. 要排序的数据个数为奇数
    正确答案:————
23. 一个有n个顶点的无向图最多有（）条边。
    A. n
    B. n(n-1)
    C. n(n-1)/2
    D. 2n
    正确答案:————
24. 设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。
    A. 1
    B. 2
    C. 3
    D. 4
    正确答案:————
25. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。
    A. n2
    B. n(n+1)
    C. n(n+1)/2
    D. n(n-1)/2
    正确答案:————
26. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。
    A. 先序遍历
    B. 中序遍历
    C. 后序遍历
    D. 按层遍历
    正确答案:————
27. 树最适合用来表示（）。
    A. 有序数据元素
    B. 无序数据元素
    C. 元素之间具有分支层次关系的数据
    D. 元素之间无联系的数据
    正确答案:————
28. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。
    A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
    B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
    C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
    D. 以上都不对
    正确答案:————
29. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是（）。
    A. e/2
    B. e
    C. 2e
    D. n+e
    正确答案:————
30. 设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。
    A. p->right=s；s->left=p；p->right->left=s；s->right=p->right；
    B. s->left=p；s->right=p->right；p->right=s；p->right->left=s；
    C. p->right=s；p->right->left=s；s->left=p；s->right=p->right；
    D. s->left=p；s->right=p->right；p->right->left=s；p->right=s；
    正确答案:————
31. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。
    A. 求关键路径的方法
    B. 求最短路径的Dijkstra方法
    C. 宽度优先遍历算法
    D. 深度优先遍历算法
    正确答案:————
32. 把一棵树转换为二叉树后，这棵二叉树的形态是（）。
    A. 唯一的
    B. 有多种
    C. 有多种，但根结点都没有左孩子
    D. 有多种，但根结点都没有右孩子
    正确答案:————
33. 关键路径是事件结点网络中（）。
    A. 从源点到汇点的最长路径
    B. 从源点到汇点的最短路径
    C. 最长的回路
    D. 最短的回路
    正确答案:————
34. 有8个结点的无向连通图最少有（）条边。
    A. 5
    B. 6
    C. 7
    D. 8
    正确答案:————
35. 在一个图中，所有顶点的度数之和等于所有边数的（）倍。
    A. 1/2
    B. 1
    C. 2
    D. 4
    正确答案:————
36. 采用线性探测法解决冲突问题，所产生的一系列后继散列地址（）。
    A. 必须大于等于原散列地址
    B. 必须小于等于原散列地址
    C. 可以大于或小于但不能等于原散列地址
    D. 地址大小没有具体限制
    正确答案:————
37. 散列表的平均查找长度（）。
    A. 与处理冲突方法有关而与表的长度无关
    B. 与处理冲突方法无关而与表的长度有关
    C. 与处理冲突方法有关而与表的长度有关
    D. 与处理冲突方法无关而与表的长度无关
    正确答案:————
38. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。
    A. 希尔排序
    B. 起泡排序
    C. 插入排序
    D. 选择排序
    正确答案:————
39. 一个有n个顶点的无向连通图，它所包含的连通分量个数为（）。
    A. 0
    B. 1
    C. n
    D. n+1
    正确答案:————
40. 设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。
    A. F，H，C，D，P，A，M，Q，R，S，Y，X
    B. P，A，C，S，Q，D，F，X，R，H，M，Y
    C. A，D，C，R，F，Q，M，S，Y，P，H，X
    D. H，C，Q，P，A，M，S，R，D，F，X，Y
    正确答案:————
奥鹏作业答案