天津大学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]