东师《数据结构》2023年春学期在线作业1【标准答案】

数据结构19春在线作业1-0003

试卷总分:100 得分:100

一、单选题 (共 20 道试题,共 60 分)

1.算法的计算量的巨细称为计算的（）。

A.功率

B.杂乱性

C.实际性

D.难度



2.若对n阶对称矩阵A按行优先次序将其下三角形的元素（包含主对角线上的一切元素）顺次寄存于一维数组B [1..n(n+1)/2 ] 中，则在B中断定aij ( i < j）的方位k的关系为 () 。

A.i*(i-1)/2+j

B.j*(j-1)/2+i

C.i*(i+1)/2+j

D.j*(j+1)/2+i



3.设二维数组A[0..m-1][0..n-1]按行优先次序存储且每个元素占c个单元，则元素A[i][j]的地址为 ()。

A.LOC(A[0][0]) + (j*m+i)*c

B.LOC(A[0][0]) + (i*n+j)*c

C.LOC(A[0][0]) + [(j-1)*m+i-1]*c

D.LOC(A[0][0]) + [(i-1)*n+j-1]*c



4.( ) 的遍历仍需求栈的撑持。

A.前序头绪二叉树

B.中序头绪二叉树

C.后序头绪二叉树

D.前三种均需求



5.若X是中序头绪二叉树中一个有右后代的结点，且X不为根，则X的中序后继为 ( )。

A.X的双亲

B.X的右子树中最左下的结点

C.X的左子树中最右下的结点

D.X的右子树中最左下的叶结点



6.下面的排序方法中，辅助空间为O( n ) 的是 ()。

A.希尔排序

B.堆排序

C.挑选排序

D.归并排序



7.鄙人述几种排序方法中，辅助空间需求最多的是 ()。

A.直接刺进排序

B.疾速排序

C.直接挑选排序

D.归并排序



8.非线性结构的逻辑特征是一个结构能够有 ( )。

A.一个前驱和一个后继

B.多个前驱和一个后继

C.一个前驱和多个后继

D.多个前驱和多个后继



9.用ISAM安排文件合适于 ()。

A.磁带

B.磁盘

C.光盘

D.外存储器



10.设有n个结点的二叉排序树，关于成功的查找，最多的对比次数为()。

A.Ο( 1 )

B.Ο(log2n)

C.Ο(n)

D.Ο(nlog2n)



11.下列排序算法中，其间 () 是安稳的。

A.堆排序，起泡排序

B.疾速排序，堆排序

C.归并排序，起泡排序

D.直接挑选排序，归并排序



12.在具有n个结点的彻底二叉树中，若设根结点的编号为1，则编号为i(i>1)的结点的双亲结点的编号是 ( )。

A.2i

B.2i+1

C.?i/2?

D.不存在



13.设有n个结点的AVL树，其均匀查找长度为 ()。

A.Ο( 1 )

B.Ο(log2n)

C.Ο(n)

D.Ο(nlog2n)



14.若一组记载的排序码为 { 46,79,56,38,40,84 }，则使用堆排序的方法树立的初始堆为 ( )。

A.79,46,56,38,40,84

B.84,79,56,38,40,46

C.84,79,56,46,40,38

D.84,56,79,40,46,38



15.设有一个10阶的对称矩阵A，选用紧缩存储方法，以行序为主存储，a11为榜首个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为 ()。

A.112

B.132

C.118

D.140



16.串是一种特别的线性表，其特别性表现在 ( )。

A.能够次序存储

B.数据元素是一个字符

C.能够连接存储

D.数据元素能够是多个字符



17.次序表中逻辑上相邻的结点其物理方位也 ( )。

A.必定相邻

B.不用相邻

C.按某种规律摆放

D.无要求



18.静态链表中的指针表明的是()。

A.内存地址

B.数组下标

C.下一元素地址

D.左、右后代地址



19.引进头绪二叉树的意图是 ( )。

A.加速查找结点的前驱或后继的速度

B.为了能便利地找到双亲

C.为了能在二叉树中便利地进行刺进与删去

D.使二叉树的遍历成果仅有



20.下列描绘中正确的是 ( )。

A.线性表的逻辑次序与存储次序老是共同的

B.每种数据结构都具有查找、刺进和删去三种根本运算

C.数据结构本质上包含逻辑结构和存储结构两方面的内容

D.挑选适宜的数据结构是处理应用疑问的要害过程



二、判别题 (共 20 道试题,共 40 分)

21.数据结构的运算(操作)是界说在数据的逻辑结构之上的。



22.关于刺进、删去运算来说，连接存储结构必定优于次序存储结构。



23.堆是满二叉树。



24.树形结构中元素之间存在一对多的关系。



25.在用堆排序算法排序时，假如要进行增序排序，则需求选用“大根堆”。



26.疾速排序总比简略的排序方法快。



27.在图G的最小生成树T中，能够会有某条边的权值超越未选边的权值。



28.最好二叉排序树是AVL树 ( 平衡二叉排序树 ) 。



29.无向图的邻接矩阵必定是对称矩阵，有向图的邻接矩阵必定对错对称矩阵。



30.N个结点的二叉排序树有多种，其间树的高度为最小的二叉排序树是最好的。



31.二叉树只能用二叉链表表明。



32.一般运用行列来处理函数或过程的调用。



33.广义表中的元素或许是一个不可以切割的原子，或许是一个非空的广义表。



34.寄存在磁盘、磁带上的文件，既能够是次序文件，也能够是索引结构或其他结构类型的文件。



35.在任何状况下，归并排序都比直接刺进排序快。



36.二叉树结点的前序遍历序列与后序遍历序列能够仅有地断定该棵二叉树。



37.堆排序是安稳的排序方法。



38.连通重量是无向图中的极大连通子图。



39.哈夫曼树是带权 ( 外部 ) 途径长度最短的树，途径上权值较大的结点离根较近。



40.为了便利的刺进和删去数据，能够运用双向链表来寄存数据。