东师数据结构20秋在线作业1[答案]满分答案
数据结构20秋在线作业1题目
试卷总分: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秋在线作业1[答案]多选题答案
二、判断题 (共 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.为了方便的插入和删除数据，可以使用双向链表来存放数据。
东师数据结构20秋在线作业1[答案]历年参考题目如下：
