东师数据结构17秋在线作业2（答案）

东师数据结构17秋在线作业2（答案）答案

数据结构17秋在线作业2
试卷总分:100    得分:0
一、 单选题 (共 20 道试题,共 60 分)
1.  head指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。
A. p->next = = NULL
B. p = = NULL
C. p->next = = head
D. p = = head
       满分：3  分



2.  设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为 ()。
A. 1和1
B. 1和3
C. 1和2
D. 2和3
       满分：3  分



3.  若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列()。
A. 存在
B. 不存在
C. 不一定存在
D. 可能不存在
       满分：3  分



4.  在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是 () 。
A. G中有弧＜Vi , Vj >
B. G中有一条从Vi到Vj 的路径
C. G中没有弧＜Vi , Vj >
D. G中有一条从Vj到Vi 的路径
       满分：3  分



5.  下列排序算法中，其中 () 是稳定的。
A. 堆排序，起泡排序
B. 快速排序，堆排序
C. 归并排序，起泡排序
D. 直接选择排序，归并排序
       满分：3  分



6.  倒排文件中倒排表是指 ()。
A. 主关键字索引
B. 次关键字索引
C. 物理顺序与逻辑顺序不一致
D. 多关键字索引
       满分：3  分



7.  对于二维数组A[4][4]，数组的起始位置LOC(A[0][0])=1000，元素长度为2，则LOC(A[3][3])为()。
A. 1000
B. 1010
C. 1008
D. 1020
       满分：3  分



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



9.  在一个单链表中，在p所指结点之后插入s所指结点，则执行 ( )。
A. s->next = p; p->next = s;
B. s->next = p->next; p->next = s;
C. s->next = p->next; p = s;
D. p->next = s; s->next = p->next;
       满分：3  分



10.  若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。
A. 根结点无右子树的二叉树
B. 根结点无左子树的二叉树
C. 根结点可能有左子树和必有右子树
D. 各结点只有一个子女的二叉树
       满分：3  分



11.  在线索二叉树中，p所指结点没有右子树的充要条件是 ( )。
A. p->rchild = = NULL
B. p->rtag = = 1
C. p->rtag = = 1且p->rchild = = NULL
D. p->rtag = = 0
       满分：3  分



12.  相对于顺序存储而言，链接存储的优点是 ( )。
A. 随机存取
B. 节省空间
C. 插入、删除操作方便
D. 结点间关系简单
       满分：3  分



13.  head指向的不带表头结点的单链表为空的判定条件是 ( )。
A. head = = NULL
B. head->next = = head
C. head ! = NULL
D. head->next = = NULL
       满分：3  分



14.  一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是：( )。
A. 不确定
B. 0
C. 1
D. 2
       满分：3  分



15.  ISAM是索引顺序存取方法，该方法是专为下面的哪一种设备设计的 ()。
A. 磁带
B. 磁盘
C. 光盘
D. 外存储器
       满分：3  分



16.  设有n个结点的二叉排序树，对于成功的查找，最少的比较次数为()。
A. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
       满分：3  分



17.  用折半查找法查找表的元素的速度比顺序查找法()。
A. 必定快
B. 必定慢
C. 相等
D. 不能确定
       满分：3  分



18.  有m个叶结点的哈夫曼树所具有的结点数为 ( )。
A. m
B. m+1
C. 2m-1
D. 2m
       满分：3  分



19.  就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
A. 堆排序＜快速排序＜归并排序
B. 堆排序＜归并排序＜快速排序
C. 堆排序＞归并排序＞快速排序
D. 堆排序＞快速排序＞归并排序
       满分：3  分



20.  顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A. 附加文件
B. 按关键字大小排序
C. 按记录输入先后排序
D. 连续排序
       满分：3  分



二、 判断题 (共 20 道试题,共 40 分)
1.  栈和队列都是限制存取点的线性结构。
A. 错误
B. 正确
       满分：2  分



2.  最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。
A. 错误
B. 正确
       满分：2  分



3.  二叉树中序线索化后，不存在空指针域。
A. 错误
B. 正确
       满分：2  分



4.  二叉树只能用二叉链表表示。
A. 错误
B. 正确
       满分：2  分



5.  完全二叉树肯定是平衡二叉排序树。
A. 错误
B. 正确
       满分：2  分



6.  取顺序表的第i个元素的时间与i的大小无关。
A. 错误
B. 正确
       满分：2  分



7.  对磁带机而言，ISAM是一种方便的文件组织方法。
A. 错误
B. 正确
       满分：2  分



8.  任何一个递归过程都可以转换成非递归过程。
A. 错误
B. 正确
       满分：2  分



9.  二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点X的值；其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。
A. 错误
B. 正确
       满分：2  分



10.  有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和。
A. 错误
B. 正确
       满分：2  分



11.  需要借助于一个栈来实现DFS算法。
A. 错误
B. 正确
       满分：2  分



12.  若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列1, 5, 4, 6, 2, 3。
A. 错误
B. 正确
       满分：2  分



13.  排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
A. 错误
B. 正确
       满分：2  分



14.  在指定结点之前插入新结点时，双链表比单链表更方便。
A. 错误
B. 正确
       满分：2  分



15.  将森树转成二叉树，根结点没有右子树。
A. 错误
B. 正确
       满分：2  分



16.  循环队列也存在空间溢出问题。
A. 错误
B. 正确
       满分：2  分



17.  邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。
A. 错误
B. 正确
       满分：2  分



18.  将一棵树转成二叉树，根结点没有左子树。
A. 错误
B. 正确
       满分：2  分



19.  无向图的邻接矩阵是对称的。
A. 错误
B. 正确
       满分：2  分



20.  存放在磁盘、磁带上的文件，既可以是顺序文件，也可以是索引结构或其他结构类型的文件。
A. 错误
B. 正确
       满分：2  分

东师数据结构17秋在线作业2（答案）历年真题如下：