天津大学17秋《数据结构》在线作业二（答案）

《数据结构》在线作业二
一、单选题:【40道,总分:100分】


1.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为(    )。          (满分:2.5)
    A. 2i+1
    B. 2i
    C. i/2
    D. 2i-1
2.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有(    )个。          (满分:2.5)
    A. 4
    B. 5
    C. 6
    D. 7
3.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动(    )个元素。          (满分:2.5)
    A. n-i
    B. n+l -i
    C. n-1-i
    D. i
4.下面不正确的说法是(    )。          (满分:2.5)
    A. 在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小
    B. AOE网工程工期为关键活动上的权之和
    C. 在关键路径上的活动都是关键活动，而关键活动也必在关键路径上
    D. 以上都不对
5.具有4个顶点的无向完全图有(    )条边。          (满分:2.5)
    A. 6
    B. 12
    C. 16
    D. 20
6.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为(    )。          (满分:2.5)
    A. 5，3，4，6，1，2
    B. 3，2，5，6，4，1
    C. 3，1，2，5，4，6
    D. 1，5，4，6，2，3
7.下列程序段的时间复杂度为(    )。  i=0，s=0； while(s<n) {s=s+i；i++；}          (满分:2.5)
    A. O(n1/2)
    B. O(n1/3)
    C. O(n)
    D. O(n2 )
8.在一个具有n个顶点的无向图中，要连通全部顶点至少需要(    )条边。          (满分:2.5)
    A. n
    B. n+1
    C. n-1
    D. n/2
9.字符串的长度是指(    )。          (满分:2.5)
    A. 串中不同字符的个数
    B. 串中不同字母的个数
    C. 串中所含字符的个数
    D. 串中不同数字的个数
10.建立一个长度为n的有序单链表的时间复杂度为(    )          (满分:2.5)
    A. O(n)
    B. O(1)
    C. O(n2 )
    D. O(log2n)
11.设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是(    )。          (满分:2.5)
    A. n-i
    B. n-1-i
    C. n+l -i
    D. 不能确定
12.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是(    )。          (满分:2.5)
    A. 逆拓朴有序的
    B. 拓朴有序的
    C. 无序的
    D. 不确定的
13.设顺序表的长度为n，则顺序查找的平均比较次数为(    )。          (满分:2.5)
    A. n
    B. n/2
    C.(n+1)/2
    D.(n-1)/2
14.二叉排序树中左子树上所有结点的值均(    )根结点的值。          (满分:2.5)
    A. <
    B. >
    C. =
    D. !=
15.在二叉排序树中插入一个关键字值的平均时间复杂度为(    )。          (满分:2.5)
    A. O(n)
    B. O(1og2n)
    C. O(nlog2n)
    D. O(n2 )
16.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(    )倍。          (满分:2.5)
    A. 1/2
    B. 1
    C. 2
    D. 4
17.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为(    )。          (满分:2.5)
    A. top=top+1;
    B. top=top-1;
    C. top->next=top;
    D. top=top->next;
18.设一组初始记录关键字的长度为8，则最多经过(    )趟插入排序可以得到有序序列。          (满分:2.5)
    A. 6
    B. 7
    C. 8
    D. 9
19.把一棵树转换为二叉树后，这棵二叉树的形态是(    )。          (满分:2.5)
    A. 唯一的
    B. 有多种
    C. 有多种，但根结点都没有左孩子
    D. 有多种，但根结点都没有右孩子
20.具有6个顶点的无向图至少应有(    )条边才能确保是一个连通图。          (满分:2.5)
    A. 5
    B. 6
    C. 7
    D. 8
21.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过(    )次比较。          (满分:2.5)
    A. 1
    B. 2
    C. 3
    D. 4
22.设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择(    )。          (满分:2.5)
    A. 小于等于m的最大奇数
    B. 小于等于m的最大素数
    C. 小于等于m的最大偶数
    D. 小于等于m的最大合数
23.一个有n个顶点的无向图最多有(    )条边。          (满分:2.5)
    A. n
    B. n(n-1)
    C. n(n-1)/2
    D. 2n
24.数组的逻辑结构不同于下列(    )的逻辑结构。          (满分:2.5)
    A. 线性表
    B. 栈
    C. 队列
    D. 树
25.设有向无环图G中的有向边集合E={，，，}，则下列属于该有向图G的一种拓扑排序序列的是(    )。          (满分:2.5)
    A. 1，2，3，4
    B. 2，3，4，1
    C. 1，4，2，3
    D. 1，2，4，3
26.树最适合用来表示(    )。          (满分:2.5)
    A. 有序数据元素
    B. 无序数据元素
    C. 元素之间具有分支层次关系的数据
    D. 元素之间无联系的数据
27.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为(    )。          (满分:2.5)
    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；
28.解决散列法中出现的冲突问题常采用的方法是(    )。          (满分:2.5)
    A. 数字分析法、除余法、平方取中法
    B. 数字分析法、除余法、线性探测法
    C. 数字分析法、线性探测法、多重散列法
    D. 线性探测法、多重散列法、链地址法
29.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是(    )。          (满分:2.5)
    A. e/2
    B. e
    C. 2e
    D. n+e
30.用某种排序方法对线性表（ 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。则所采用的排序方法是(    )。          (满分:2.5)
    A. 选择排序
    B. 希尔排序
    C. 归并排序
    D. 快速排序
31.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论(    )是正确的。          (满分:2.5)
    A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
    B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
    C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
    D. 以上都不对
32.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为(    )。          (满分:2.5)
    A. 129
    B. 219
    C. 189
    D. 229
33.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用(    )排序法。          (满分:2.5)
    A. 起泡排序
    B. 快速排序
    C. 堆排序
    D. 基数排序
34.设完全无向图中有n个顶点，则该完全无向图中有(    )条边。          (满分:2.5)
    A. n(n-1)/2
    B. n(n-1)
    C. n(n+1)/2
    D.(n-1)/2
35.下列各种排序算法中平均时间复杂度为O(n2 )是(    )。          (满分:2.5)
    A. 快速排序
    B. 堆排序
    C. 归并排序
    D. 冒泡排序
36.有8个结点的无向图最多有(    )条边。          (满分:2.5)
    A. 14
    B. 28
    C. 56
    D. 112
37.采用线性探测法解决冲突问题，所产生的一系列后继散列地址(    )。          (满分:2.5)
    A. 必须大于等于原散列地址
    B. 必须小于等于原散列地址
    C. 可以大于或小于但不能等于原散列地址
    D. 地址大小没有具体限制
38.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较 元素的顺序为(    )。          (满分:2.5)
    A. A[1]，A[2]，A[3]，A[4]
    B. A[1]，A[14]，A[7]，A[4]
    C. A[7]，A[3]，A[5]，A[4]
    D. A[7]，A[5] ，A[3]，A[4]
39.任何一个无向连通图的最小生成树(    )。          (满分:2.5)
    A. 只有一棵
    B. 有一棵或多棵
    C. 一定有多棵
    D. 可能不存在
40.组成数据的基本单位是(    )。          (满分:2.5)
    A. 数据项
    B. 数据类型
    C. 数据元素
    D. 数据变量
更多学习资料请登录www.openhelp100.com