天大17秋《数据结构》在线作业12答案
《数据结构》在线作业一一、单选题:【40道,总分:100分】
1.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A的起始地址为( )。 (满分:2.5)
A. SA+141 B. SA+180
C. SA+222 D. SA+225
2.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为( )。 (满分:2.5)
A. O(1) B. O(log2n)
C. O(n4) D. O(n2 )
3.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 (满分:2.5)
A. 15
B. 16
C. 17
D. 47
4.下面关于线性表的叙述错误的是( )。 (满分:2.5)
A. 线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
5.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 (满分:2.5)
A. 5
B. 6
C. 7
D. 8
6.设某完全无向图中有n个顶点，则该完全无向图中有( )条边。 (满分:2.5)
A. n(n-1)/2
B. n(n-1)
C. n2
D. n2 -1
7.下列四种排序中( )的空间复杂度最大。 (满分:2.5)
A. 插入排序
B. 冒泡排序
C. 堆排序
D. 归并排序
8.判定一个顺序栈ST（最多元素为m0）为栈满的条件是( )。 (满分:2.5)
A. top！=0
B. top= =0
C. top！=m0
D. top= =m0-1
9.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是( )。 (满分:2.5)
A. N0=N1+1
B. N0=Nl+N2
C. N0=N2+1
D. N0=2N1+l
10.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为( )。 (满分:2.5)
A. O(n)
B. O(nlog2n)
C. O(1)
D. O(n2 )
11.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过( )。 (满分:2.5)
A. log2n+1
B. log2n-1
C. log2n
D. log2(n+1)
12.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为( )。 (满分:2.5)
A. i
B. n=i
C. n-i+1
D. 不确定
13.在一非空二叉树的中序遍历序列中，根结点的右边( )。 (满分:2.5)
A. 只有右子树上的所有结点
B. 只有右子树上的部分结点
C. 只有左子树上的部分结点
D. 只有左子树上的所有结点
14.判定一个循环队列QU（最多元素为m0）为空的条件是( )。 (满分:2.5)
A. rear - front= =m0
B. rear-front-1= =m0
C. front= = rear
D. front= = rear+1
15.设顺序循环队列Q的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为( )。 (满分:2.5)
A. R-F
B. F-R
C.(R-F+M)％M
D.(F-R+M)％M
16.在以下的叙述中，正确的是( )。 (满分:2.5)
A. 线性表的顺序存储结构优于链表存储结构
B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D. 线性表的链表存储结构优于顺序存储结构
17.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。 (满分:2.5)
A. 正确
B. 错误
18.串是一中特殊的线性表，其特殊性体现在( )。 (满分:2.5)
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符
19.数据结构是一门研究非数值计算的程序设计问题中,数据元素的( )、数据信息在计算机中的存储结构以及一组相关的运算等的课程。 (满分:2.5)
A. 操作对象
B. 计算方法
C. 逻辑结构
D. 数据映象
20.设串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是( )。 (满分:2.5)
A. BCDEF
B. BCDEFG
C. BCPQRST
D. BCDEFEF
21.二叉树的第k层的结点数最多为( ). (满分:2.5)
A. 2k-1
B. 2K+1
C. 2K-1
D. 2k-1
22.按照二叉树的定义，具有3个结点的不同形状的二叉树有( )种。 (满分:2.5)
A. 3
B. 4
C. 5
D. 6
23.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为( )。 (满分:2.5)
A. q=p->next；p->data=q->data；p->next=q->next；free(q)；
B. q=p->next；q->data=p->data；p->next=q->next；free(q)；
C. q=p->next；p->next=q->next；free(q)；
D. q=p->next；p->data=q->data；free(q)
24.具有五层结点的二叉平衡树至少有( )个结点。 (满分:2.5)
A. 10
B. 12
C. 15
D. 17
25.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较( )个结点。 (满分:2.5)
A. n
B. n/2
C.(n-1)/2
D.(n+1)/2
26.以下叙述中正确的是( )。 (满分:2.5)
A. 串是一种特殊的线性表
B. 串的长度必须大于零
C. 串中无素只能是字母
D. 空串就是空白串
27.在一棵具有5层的满二叉树中结点数为( ) (满分:2.5)
A. 33
B. 32
C. 31
D. 31
28.非空的循环单链表head的尾结点（由p所指向）满足( )。 (满分:2.5)
A. p->next= =NULL
B. p= =NULL
C. p->next= =head
D. p= =head
29.设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。 (满分:2.5)
A. 10，15，14，18，20，36，40，21
B. 10，15，14，18，20，40，36，21
C. 10，15，14，20，18，40，36，2l
D. 15，10，14，18，20，36，40，21
30.设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。 (满分:2.5)
A. 9
B. 10
C. 11
D. 12
31.判定一个顺序栈ST（最多元素为m0）为空的条件是( )。 (满分:2.5)
A. top!=0
B. top= =0
C. top!=m0
D. top= =m0-1
32.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是( )。 (满分:2.5)
A. a在b的右方
B. a在b的左方
C. a是b的祖先
D. a是b的子孙
33.设有两个串p和q，求q在p中首次出现的位置的运算称作( )。 (满分:2.5)
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
34.数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是( )有限集合，R是D上的关系有限集合。 (满分:2.5)
A. 算法
B. 数据元素
C. 数据操作
D. 数据对象
35.设一棵二叉树的深度为k，则该二叉树中最多有( )个结点。 (满分:2.5)
A. 2k-1
B. 2k
C. 2k-1
D. 2k -1
36.哈希表中的冲突可以通过改变哈希函数完全避免。 (满分:2.5)
A. 正确
B. 错误
37.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。 (满分:2.5)
A. s->next=p;p->next=s;
B. s->next=p->next;p->next=s;
C. s->next=p->next;p=s;
D. p->next=s;s->next=p;
38.设某强连通图中有n个顶点，则该强连通图中至少有( )条边。 (满分:2.5)
A. n(n-1)
B. n+1
C. n
D. n(n+1)
39.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。 (满分:2.5)
A. 2m-1
B. 2m
C. 2m+1
D. 4m
40.对一个满二叉树，m个树叶，n个结点，深度为h，则( )。 (满分:2.5)
A. n=h+m
B. h+m=2n
C. m=h-1
D. n=2的h次方-1
《数据结构》在线作业二
一、单选题:【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. 数据变量
页:
[1]