[东北师范大学]《数据结构》20春在线作业1-3（答案100分）

skystar

-[东北师范大学]数据结构20春在线作业1
试卷总分:100    得分:100
第1题,数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
A、直接选择排序
B、冒泡排序
C、直接插入排序
D、堆排序
正确答案:


第2题,下面关于算法说法错误的是（）。
A、算法最终必须由计算机程序实现
B、为解决某问题的算法同为该问题编写的程序含义是相同的
C、算法的可行性是指指令不能有二义性
D、以上几个都是错误的
正确答案:


第3题,判断线索二叉树中某结点p有左子女的条件是 ( )。
A、p ! = NULL
B、p-lchild ! = NULL
C、p-ltag = = 0
D、p-ltag = = 1
正确答案:


第4题,采用邻接表存储的图的深度优先遍历类似于二叉树的 ()。
A、前序遍历
B、中序遍历
C、后序遍历
D、层次遍历
正确答案:


任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。
A、不发生改变
B、发生改变
C、稍有改变
D、不能确定
正确答案:


第6题,对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是 ()。
A、直接插入排序
B、冒泡排序
C、快速排序
D、归并排序
正确答案:


第7题,有n个顶点的无向连通图的边数最少为 ()。
A、n/2
B、n-1
C、n
D、n+1
正确答案:


第8题,设二叉树有n个结点且根结点的层数为0，则二叉树的高度为 ( )。
A、n-1
B、élog2(n+1)ù -1
C、?log2n?
D、不确定
正确答案:


第9题,在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
A、直接插入排序
B、冒泡排序
C、快速排序
D、直接选择排序
正确答案:


"堆积"问题是由于()引起的。
A、同义词之间发生冲突
B、散列函数
C、不同的同义词子表结合在一起
D、散列表"溢出"
正确答案:


第11题,数组A[6,7] 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5] 的地址是 ()。
A、1165
B、1170
C、1175
D、1180
正确答案:


下列说法不正确的是 ()。
A、图的遍历是从给定的源点出发每个顶点仅被访问一次
B、遍历的基本方法有两种：深度优先遍历和广度优先遍历
C、图的深度优先遍历不适用于有向图
D、图的深度优先遍历是一个递归过程
正确答案:


第13题,下述文件中适合于磁带存储的是 ()。
A、顺序文件
B、索引文件
C、散列文件
D、多关键字文件
正确答案:


第14题,递归过程的实现需用到 ( )。
A、线性表
B、链表
C、栈
D、队列
正确答案:


存放在外存中的数据的组织结构是 ()。
A、数组
B、表
C、文件
D、链表
正确答案:


第16题,从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行 ( )。
A、x = top; top = top-next;
B、top = top-next; x = top-data;
C、x = top-data;
D、x = top-data; top = top-next;
正确答案:


第17题,若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列()。
A、存在
B、不存在
C、不一定存在
D、可能不存在
正确答案:


第18题,若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为 ( )。
A、10
B、16
C、31
D、32
正确答案:


第19题,AVL树中任一结点的平衡因子的绝对值都应小于等于 ()。
A、0
B、1
C、2
D、3
正确答案:


对于二维数组A[4][4]，数组的起始位置LOC(A[0][0])=1000，元素长度为2，则LOC(A[3][3])为()。
A、1000
B、1010
C、1008
D、1020
正确答案:


第21题,完全二叉树的存储结构通常采用顺序存储结构。
A、错误
B、正确
正确答案:


第22题,对n个记录的文件进行直接插入排序，最好情况下的执行时间是O(n)。
A、错误
B、正确
正确答案:


第23题,在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
A、错误
B、正确
正确答案:


第24题,在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下面。
A、错误
B、正确
正确答案:


对磁带机而言，ISAM是一种方便的文件组织方法。
A、错误
B、正确
正确答案:


第26题,文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。
A、错误
B、正确
正确答案:


第27题,二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
A、错误
B、正确
正确答案:


第28题,任何无向图都存在生成树。
A、错误
B、正确
正确答案:


第29题,广义表的取表尾运算，其结果仍是一个广义表。
A、错误
B、正确
正确答案:


栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
A、错误
B、正确
正确答案:


第31题,最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
A、错误
B、正确
正确答案:


第32题,用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A、错误
B、正确
正确答案:


第33题,程序一定是算法。
A、错误
B、正确
正确答案:


第34题,堆是满二叉树。
A、错误
B、正确
正确答案:


第35题,负载因子（装填因子）是哈希表(散列表)的一个重要参数，它反映哈希表的填满程度。
A、错误
B、正确
正确答案:


第36题,两个栈共用静态存储空间，对接使用方式也存在空间溢出问题。
A、错误
B、正确
正确答案:


第37题,数据的逻辑结构是指数据的各数据项之间的逻辑关系。
A、错误
B、正确
正确答案:


第38题,带权的连通无向图的最小(代价)生成树必是唯一的。
A、错误
B、正确
正确答案:


第39题,将森树转成二叉树，根结点没有左子树。
A、错误
B、正确
正确答案:


第40题,哈希函数越复杂越好，因为这样随机性好，冲突概率小。
A、错误
B、正确
正确答案: