《东师《数据结构》22春在线作业1-0004》由会员分享，可在线阅读，更多相关《东师《数据结构》22春在线作业1-0004（7页珍藏版）》请在金锄头文库上搜索。
1、东师数据结构22春在线作业1-0004试卷总分100 得分100一、单选题 (共 20 道试题,共 60 分)1.数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。A.直接选择排序B.冒泡排序C.直接插入排序D.堆排序答案C2.下面关于算法说法错误的是（）。A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的答案D3.判断线索二叉树中某结点p有左子女的条件是 ( )。A.p ! = NULLB.p-lchild !
2、 = NULLC.p-ltag = = 0D.p-ltag = = 1答案C4.采用邻接表存储的图的深度优先遍历类似于二叉树的 ()。A.前序遍历B.中序遍历C.后序遍历D.层次遍历答案A5.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。A.不发生改变B.发生改变C.稍有改变D.不能确定答案A6.对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是 ()。A.直接插入排序B.冒泡排序C.快速排序D.归并排序答案D7.有n个顶点的无向连通图的边数最少为 ()。A.n2B.n-1C.nD.n+1答案B8.设二叉树有n个结点且根结点的层数为0，则二叉树的高度为 (
3、 )。A.n-1B.log2(n+1) -1C.log2nD.不确定答案D9.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。A.直接插入排序B.冒泡排序C.快速排序D.直接选择排序答案D10.“堆积”问题是由于()引起的。A.同义词之间发生冲突B.散列函数C.不同的同义词子表结合在一起D.散列表“溢出”答案C11.数组A6,7 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5,5 的地址是 ()。A.1165B.1170C.1175D.1180答案C12.下列说法不正确的是 ()。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍
4、历的基本方法有两种：深度优先遍历和广度优先遍历C.图的深度优先遍历不适用于有向图D.图的深度优先遍历是一个递归过程答案C13.下述文件中适合于磁带存储的是 ()。A.顺序文件B.索引文件C.散列文件D.多关键字文件答案A14.递归过程的实现需用到 ( )。A.线性表B.链表C.栈D.队列答案C15.存放在外存中的数据的组织结构是 ()。A.数组B.表C.文件D.链表答案C16.从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行 ( )。A.x = top; top = top-next;B.top = top-next; x = top-data;C.x = top-dat
5、a;D.x = top-data; top = top-next;答案D17.若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列()。A.存在B.不存在C.不一定存在D.可能不存在答案A18.若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为 ( )。A.10B.16C.31D.32答案C19.AVL树中任一结点的平衡因子的绝对值都应小于等于 ()。A.0B.1C.2D.3答案B20.对于二维数组A44，数组的起始位置LOC(A00)=1000，元素长度为2，则LOC(A33)为()。A.1000B.1010C.1008D.1020答案D二、判断题 (共 20
6、道试题,共 40 分)21.完全二叉树的存储结构通常采用顺序存储结构。答案正确22.对n个记录的文件进行直接插入排序，最好情况下的执行时间是O(n)。答案正确23.在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。答案错误24.在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下面。答案错误25.对磁带机而言，ISAM是一种方便的文件组织方法。答案错误26.文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。答案正确27.二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。答案错误28.任何无向图都存
7、在生成树。答案错误29.广义表的取表尾运算，其结果仍是一个广义表。答案正确30.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。答案正确31.最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。答案正确32.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。答案正确33.程序一定是算法。答案错误34.堆是满二叉树。答案错误35.负载因子（装填因子）是哈希表(散列表)的一个重要参数，它反映哈希表的填满程度。答案正确36.两个栈共用静态存储空间，对接使用方式也存在空间溢出问题。答案正确37.数据的逻辑结构是指数据的各数据项之间的逻辑关系。答案错误38.带权的连通无向图的最小(代价)生成树必是唯一的。答案错误39.将森树转成二叉树，根结点没有左子树。答案错误40.哈希函数越复杂越好，因为这样随机性好，冲突概率小。答案错误
