网院作业 发表于 2017-9-25 10:39:15

天津大学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中有14个元素,则采用二分法查找元素A的过程中比较 元素的顺序为(    )。          (满分:2.5)
    A. A,A,A,A
    B. A,A,A,A
    C. A,A,A,A
    D. A,A ,A,A
39.任何一个无向连通图的最小生成树(    )。          (满分:2.5)
    A. 只有一棵
    B. 有一棵或多棵
    C. 一定有多棵
    D. 可能不存在
40.组成数据的基本单位是(    )。          (满分:2.5)
    A. 数据项
    B. 数据类型
    C. 数据元素
    D. 数据变量
更多学习资料请登录www.openhelp100.com

页: [1]
查看完整版本: 天津大学17秋《数据结构》在线作业二(答案)