东师数据结构17春在线作业1满分答案1

满分：3分
正确答案:C
15.设有n个结点的最佳二叉排序树，对于成功的查找，最多的比较次数为()。
A. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
满分：3分
正确答案:B
16.最佳二叉排序树属于()的数据结构。
A.动态
B.静态
C.线性
D.无结构
满分：3分
正确答案:B
17.下面关于算法说法错误的是（）。
A.磁带
B.磁盘
C.光盘
D.外存储器
满分：3分
正确答案:B
7.广义表(( a , b , c , d ) )的表尾是()。
A. a
B. ( )
C. ( a , b , c , d )
D. ( b , c , d )
满分：3分
正确答案:B
8.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为()。
B.正确
满分：2分
正确答案:A
8.两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。
A.错误
B.正确
满分：2分
正确答案:B
9.在完全二叉树中，若一个结点没有左子女，则它必是树叶。
A.错误
B.正确
满分：2分
正确答案:B
10.中序遍历二叉链表存储的二叉树时，一般要用堆栈；中序遍历中序线索二叉树时，也必须使用堆栈。
A. 112
B. 132
C. 118
D. 140
满分：3分
正确答案:B
9.插入、删除只能在同一端进行的线性表，称为( )。
A.队列
B.循环队列
C.栈
D.循环栈
满分：3分
正确答案:C
10.散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值()。
A.同等概率
B.最大概率
C.最小概率
D.平均概率
满分：3分
正确答案:A
11.在线索二叉树中，p所指结点没有右子树的充要条件是( )。
A. p->rchild = = NULL
B. p->rtag = = 1
C. p->rtag = = 1且p->rchild = = NULL
D. p->rtag = = 0
满分：3分
正确答案:B
12.在下述几种排序方法中，不稳定的排序方法是()。
A.错误
B.正确
满分：2分
正确答案:A
14.文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。
A.错误
B.正确
满分：2分
正确答案:B
15.链表中的表头指针与表头结点起到相同的作用。
A.错误
B.正确
满分：2分
正确答案:A
16.对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
A. 0
B. 1
C. 2
D. 3
满分：3分
正确答案:D
4.线索二叉树是一种( )结构。
A.逻辑
B.物理
C.逻辑和存储
D.线性
满分：3分
正确答案:B
5.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关()。
A.直接插入排序
B.冒泡排序
C.快速排序
D.直接选择排序
满分：3分
正确答案:D
6. ISAM是索引顺序存取方法，该方法是专为下面的哪一种设备设计的()。
数据结构17春在线作业1
试卷总分:100得分:100
一、单选题(共20道试题,共60分)
1.在k叉树中，度为0的结点称为( )。
A.根
B.叶
C.祖先
D.子孙
满分：3分
正确答案:B
2.有n个顶点的有向图的边数Fra bibliotek多为()。A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
满分：3分
正确答案:B
3.设s1 = "abc"，则strlen(s1) = ( )。
A.错误
B.正确
满分：2分
正确答案:B
2. N个结点的二叉排序树有多种，其中树的高度为最小的二叉排序树是最佳的。
A.错误
B.正确
满分：2分
正确答案:B
3.当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。
A.错误
B.正确
满分：2分
正确答案:A
4.堆是满二叉树。
A.错误
B.正确
满分：2分
A.直接插入排序
B.冒泡排序
C.直接选择排序
D.归并排序
满分：3分
正确答案:C
13.采用邻接表存储的图的广度优先遍历类似于二叉树的()。
A.前序遍历
B.中序遍历
C.后序遍历
D.层次遍历
满分：3分
正确答案:D
14.折半查找要求结点()。
A.无序、顺序存储
B.无序、链接存储
C.有序、顺序存储
D.有序、链接存储
A.根
B.叶
C.祖先
D.子孙
满分：3分
正确答案:A
20.设二叉树有n个结点且根结点的层数为0，则二叉树的高度为( )。
A. n-1
B. élog2(n+1)ù -1
C. ?log2n?
D.不确定
满分：3分
正确答案:D
二、判断题(共20道试题,共40分)
1.最佳二叉排序树是AVL树(平衡二叉排序树)。
A.错误
B.正确
满分：2分
正确答案:A
11.有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和。
A.错误
B.正确
满分：2分
正确答案:A
12.对一棵二叉排序树按中序方法遍历得到的结点序列是从小到大的序列。
A.错误
B.正确
满分：2分
正确答案:B
13.若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列1, 5, 4, 6, 2, 3。
A.算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C.算法的可行性是指指令不能有二义性
D.以上几个都是错误的
满分：3分
正确答案:D
18.求顶点间的最短路径问题，考虑的是下面的哪一种图()。
A.无向图
B.有向图
C.带权的无向图
D.带权的有向图
满分：3分
正确答案:D
19.在k叉树中，无父母的结点称为( )。
正确答案:A
5.用链表( lchild-rchild表示法)存储的包含n个结点的二叉树，结点的2n个指针域中有n-1个空指针。
A.错误
B.正确
满分：2分
正确答案:A
6.折半插入排序所需比较次数与待排序记录的初始排列状态无关。
A.错误
B.正确
满分：2分
正确答案:B
7.对有序的单链表可以进行折半查找。
A.错误
A.错误
B.正确
满分：2分
正确答案:A
17.二叉树只能用二叉链表表示。
A.错误
B.正确
满分：2分
正确答案:A
18.有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素个数的一半。
A.错误
B.正确
满分：2分
正确答案:B
19.快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
A.错误
B.正确