|
|
21春学期《数据结构Ⅱ》在线平时作业1
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n3)
2.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
A..{25,36,48,72,23,40,79,82,16,35}
B..{25,36,48,72,16,23,40,79,82,35}
C..{25,36,48,72,16,23,35,40,79,82}
D..{16,23,25,35,36,40,48,72,79,82}
3.连通图是指图中任意两个顶点之间
A.都连通的雅向图
B.都不连通的雅向图
C.都连通的有向图
D.都不连通的有向图
答案:A
4.数据元素及其关系在计算机存储器内的表示，称为数据的
A.逻辑结构
B.存储结构
C.线性结构
D.非线性结构
5.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为
A.21
B.23
C.41
D.62
6.在待排关键字序列基本有序的前提下，效率最高的排序方法是
A.直接插入排序
B.快速排序
C.直接选择排序
D.归并排序
答案:A
7.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是
A.head(tail(LS))
B.tail(head(LS))
C.head(tail(head(tail(LS))))
D.head(tail(tail(head(LS))))
8.．用DFS遍历一个雅环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
A.逆拓扑有序
B.拓扑有序
C.雅序的
D.A和B
答案:A
9.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是
A.栈
B.队列
C.树
D.图
10.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系
A.不一定相同
B.都相同
C.都不相同
D.互为逆序
11.二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是
A.A[8，5]
B.A[3，10]
C.A[5，8]
D.A[0，9]
12.若要在单链表中的结点p之后插入一个结点s，则应执行的语句是
A.s->next=p->next; p->next=s;
B.p->next=s; s->next=p->next;
C.p->next=s->next; s->next=p;
D.s->next=p; p->next=s->next;
答案:A
13.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是
A.0
B.1
C.2
D.3
14.连通网的最小生成树是其所有生成树中
A.顶点集最小的生成树
B.边集最小的生成树
C.顶点权值之和最小的生成树
D.边的权值之和最小的生成树
15.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是
A.1234
B.4132
C.4231
D.4213
16.为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为
A.5
B.37
C.41
D.62
17.若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列
A.一定存在
B.一定不存在
C.不一定存在
D.不确定
答案:A
18.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是
A.顺序表
B.双链表
C.带头结点的双循环链表
D.单循环链表
答案:A
19.希尔排序的增量序列必须是
A.递增的
B.随机的
C.递减的
D.非递减的
20.对长度为n的关键字序列进行堆排序的空间复杂度为
A.O（log2n）
B.O（1）
C.O（n）
D.O（n*log2n）
21春学期《数据结构Ⅱ》在线平时作业2
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.下列程序段 for(i=1;i<=n;i++) A[I,j]=0; 的时间复杂度是
A.O(1)
B.O(0)
C.O(1+n)
D.O(n)
2.以下数据结构中，属于线性结构的是
A.广义表
B.二叉树
C.稀疏矩阵
D.串
答案:A
3.某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A.空或只有一个结点
B.高度等于其结点数
C.任一结点雅左孩子
D.任一结点雅右孩子
4.在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作
A.s->next=p->next;p->next=s;
B.s->next=p; q->next=s
C.q->next=s;s->next=p;
D.p->next=s;s->next=q;
5.在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用
A.数据元素的相邻地址表示
B.数据元素在表中的序号表示
C.指向后继元素的指针表示
D.数据元素的值表示
6.已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为
A.2
B.3
C.8
D.9
7.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为
A.1和 5
B.2和4
C.4和2
D.5和1
8.引入二叉线索树的目的是
A.加快查找结点的前驱或后继的速度
B.为了能在二叉树中方便的进行插入与删除
C.为了能方便的找到双亲
D.使二叉树的遍历结果唯一
答案:A
9.下面说法错误的是
(1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A.(1)
B.(1),(2)
C.(1),(4)
D.(3)
10.有关二叉树下列说法正确的是
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
11.按排序过程中依据的原则分类，快速排序属于
A.插入类的排序方法
B.选择类的排序方法
C.交换类的排序方法
D.归并类的排序方法
12.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是
A.10
B.11
C.12
D.15
答案:A
13.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A.4
B.5
C.8
D.9
14.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
A.O(n) O(n)
B.O(n) O(1)
C.O(1) O(n)
D.O(1) O(1)
15.判断两个串大小的基本准则是
A.两个串长度的大小
B.两个串中首字符的大小
C.两个串中大写字母的多少
D.对应的第一个不等字符的大小
16.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
A.DEBAFC
B.DEFBCA
C.DEBCFA
D.DEBFCA
17.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为
A.4，4，3
B.4，3，3
C.3，4，4
D.．3，3，4
18.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
A.层次遍历算法
B.前序遍历算法
C.中序遍历算法
D.后序遍历算法
19.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为
A.插入排序
B.归并排序
C.冒泡排序
D.堆排序
答案:A
20.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是
A.n
B.2n-1
C.2n
D.n-1
答案:A
21春学期《数据结构Ⅱ》在线平时作业3
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.深度为h的满m叉树的第k层的结点(1=<k=<h)数有
A.mk-1
B.mk-1
C.mh-1
D.mh-1
答案:A
2.数据结构中所定义的数据元素，是用于表示数据的
A.最小单位
B.最大单位
C.基本单位
D.不可分割的单位
3.希尔排序的增量序列必须是
A.递增的
B.随机的
C.递减的
D.非递减的
4.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为
A.4，4，3
B.4，3，3
C.3，4，4
D.．3，3，4
5.下列序列中，不构成堆的是
A.（1，2，5，3，4，6，7，8，9，10）
B.（10，5，8，4，2，6，7，1，3）
C.（10，9，8，7，3，5，4，6，2）
D.（1，2，3，4，10，9，8，7，6，5）
6.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
A.f,c,b
B.f,d,b
C.g,c,b
D.g,d,b
答案:A
7.在下列各种文件中，不能进行顺序查找的文件是
A.顺序文件
B.索引文件
C.散列文件
D.多重表文件
8.带行表的三元组表是稀疏矩阵的一种
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.散列存储结构
答案:A
9.在一个单链表中，若删除*p结点的后继结点，则执行操作
A.q=p->next;p->next=q->next;free(q);
B.p=p->next;p->next=p->next->next;free(p);
C.p->next=q->next;free(p->next);
D.p=p->next->next;free(p->next);
答案:A
10.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A.n-1
B.n
C.n+l
D.2n
11.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于
A.1.0
B.2.9
C.3.4
D.5.5
12.一个有向雅环图的拓扑排序序列是
A.一定唯一的
B.一定不唯一的
C.不一定唯一的
D.都不对
13.用有向雅环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为
A.5
B.6
C.8
D.9
答案:A
14.若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列
A.一定存在
B.一定不存在
C.不一定存在
D.不确定
答案:A
15.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A.1
B.2
C.3
D.5
16.数据的不可分割的最小标识单位是
A.数据项
B.数据记录
C.数据元素
D.数据变量
答案:A
17.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A.深度优先搜索算法
B.广度优先搜索算法
C.求最小生成树的prim算法
D.拓扑排序算法
18.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A.5
B.6
C.16
D.17
19.n个顶点的强连通图中至少含有
A.n-1条有向边
B.n条有向边
C.n(n-1)/2条有向边
D.n(n-1)条有向边
20.下列陈述中正确的是
A.二叉树是度为2的有序树
B.二叉树中结点只有一个孩子时雅左右之分
C.二叉树中必有度为2的结点
D.二叉树中最多只有两棵子树，并且有左右之分 |
上一篇：东北大学21春学期《计算机网络》在线平时作业123下一篇：[东北大学]21年6月考试《数据结构II X》考核作业
|
[复制链接]
发表于 2021-6-7 15:16:40
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
QQ登录
