东师14秋《数据结构（高起专）》在线作业答案
东师《数据结构（高起专）》2014秋第一次在线作业试卷总分：100 测试时间：--
一、单选题（共20道试题，共60分。）
1.在下面的叙述中，正确的是 ( )。
A. 树的先根遍历序列与其对应的二叉树的前序遍历序列相同
B. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的后序遍历序列相同
D. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
满分：3分
2.在具有n个结点的完全二叉树中，若设根结点的编号为1，则编号为i(i>1)的结点的双亲结点的编号是 ( )。
A. 2i
B. 2i+1
C. i/2
D. 不存在
满分：3分
3.算法的计算量的大小称为计算的（）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
满分：3分
4.某二叉树结点的前序序列为ECBAD，中序序列为EBCDA，则该二叉树结点的后序序列为 ( )。
A. ABCED
B. DECAB
C. DEABC
D. BDACE
满分：3分
5.一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是：( )。
A. 不确定
B. 0
C. 1
D. 2
满分：3分
6.如果BT是由有序树T转换而来的二叉树，那么T中结点的后根序列就是BT中结点的 ( ) 序列。
A. 前序
B. 中序
C. 后序
D. 层次次序
满分：3分
7.head指向的带表头结点的单链表为空的判定条件是 ( )。
A. head = = NULL
B. head->next = = head
C. head ! = NULL
D. head->next = = NULL
满分：3分
8.引入线索二叉树的目的是 ( )。
A. 加快查找结点的前驱或后继的速度
B. 为了能方便地找到双亲
C. 为了能在二叉树中方便地进行插入与删除
D. 使二叉树的遍历结果唯一
满分：3分
9.四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是 ( )。
A. U
B. V
C. X
D. Y
满分：3分
10.单链表的存储密度 ( )。
A. 大于1
B. 等于1
C. 小于1
D. 不能确定
满分：3分
11.在队列中存取数据的原则是 ( )。
A. 先进先出
B. 后进先出
C. 先进后出
D. 随意进出
满分：3分
12.设F是一个森林， B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有 ( ) 个。
A. n-1
B. n
C. n +1
D. n+2
满分：3分
13.插入、删除只能在同一端进行的线性表，称为 ( )。
A. 队列
B. 循环队列
C. 栈
D. 循环栈
满分：3分
14.若设根结点的层数为0，则具有37个结点的完全二叉树的深度(或高度)为 ( )。
A. 4
B. 5
C. 6
D. 7
满分：3分
15.在栈中存取数据的原则是 ( )。
A. 先进先出
B. 后进先出
C. 后进后出
D. 随意进出
满分：3分
16.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是 ( )。
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左子女
D. 任一结点无右子女
满分：3分
17.数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是 ( )
A. 线性表
B. 广义表
C. 树形结构
D. 图结构
满分：3分
18.有m个叶结点的哈夫曼树所具有的结点数为 ( )。
A. m
B. m+1
C. 2m-1
D. 2m
满分：3分
19.head指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。
A. p->next = = NULL
B. p = = NULL
C. p->next = = head
D. p = = head
满分：3分
20.设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A. 求子串
B. 求串长
C. 联接
D. 模式匹配
满分：3分
二、判断题（共20道试题，共40分。）
1.取顺序表的第i个元素的时间与i的大小无关。
A. 错误
B. 正确
满分：2分
2.任何一棵二叉树都可以不用栈实现前序线索二叉树的前序遍历。
A. 错误
B. 正确
满分：2分
3.一棵哈夫曼树的带权 ( 外部 ) 路径长度等于其中所有分支结点的权值之和。
A. 错误
B. 正确
满分：2分
4.在中序线索二叉树中，每一非空的线索均指向其祖先结点。
A. 错误
B. 正确
满分：2分
5.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
A. 错误
B. 正确
满分：2分
6.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A. 错误
B. 正确
满分：2分
7.二叉树中每个结点至多有两个子结点，而对一般的树则无此限制。因此，二叉树是树的特殊情形。
A. 错误
B. 正确
满分：2分
8.二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。
A. 错误
B. 正确
满分：2分
9.当一棵具有m个叶结点的二叉树的 WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。
A. 错误
B. 正确
满分：2分
10.两个栈共用静态存储空间，对接使用方式减少了空间溢出的可能性。
A. 错误
B. 正确
满分：2分
11.二叉树的后序遍历序列中，任意一个结点均处在其子女结点( 若存在 )的后面。
A. 错误
B. 正确
满分：2分
12.在指定结点之前插入新结点时，双链表比单链表更方便。
A. 错误
B. 正确
满分：2分
13.串是一种数据对象和操作都特殊的线性表。
A. 错误
B. 正确
满分：2分
14.链表中的表头指针与表头结点起到不同的作用。
A. 错误
B. 正确
满分：2分
15.若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列1, 5, 4, 6, 2, 3。
A. 错误
B. 正确
满分：2分
16.在完全二叉树中，若一个结点没有左子女，则它必是树叶。
A. 错误
B. 正确
满分：2分
17.二叉树中序线索化后，不存在空指针域。
A. 错误
B. 正确
满分：2分
18.数据的逻辑结构是指数据的各数据项之间的逻辑关系。
A. 错误
B. 正确
满分：2分
19.对于任何数据结构，链接存储结构一定优于顺序存储结构。
A. 错误
B. 正确
满分：2分
20.链接存储结构属动态存储方式。
A. 错误
B. 正确
2014秋第二次在线作业
试卷总分：100 测试时间：--
一、单选题（共20道试题，共60分。）
1.下列哪一种图的邻接矩阵是对称矩阵？ ()
A. 有向图
B. 无向图
C. AOV 网
D. AOE 网
满分：3分
2.下面哪些方法可以判断出一个有向图是否有环（回路） ()
A. 广(宽)度优先遍历
B. 拓扑排序
C. 求最短路径
D. 求关键路径
满分：3分
3.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 ()。
A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
满分：3分
4.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A. 附加文件
B. 按关键字大小排序
C. 按记录输入先后排序
D. 连续排序
满分：3分
5.采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
满分：3分
6.快速排序算法在下述哪种情况下效率最高 ()。
A. 被排序的数据已完全有序
B. 被排序的数据中含有多个相同的排序码
C. 被排序的数据已基本有序
D. 被排序的数据完全无序
满分：3分
7.采用邻接表存储的图的深度优先遍历类似于二叉树的 ()。
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
满分：3分
8.若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列()。
A. 存在
B. 不存在
C. 不一定存在
D. 可能不存在
满分：3分
9.排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
B. 直接选择
C. 冒泡
D. 归并
满分：3分
10.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
A. 直接插入排序
B. 冒泡排序
C. 快速排序
D. 直接选择排序
满分：3分
11.若要求尽可能快地对序列进行稳定的排序，则应选 () 。
A. 快速排序
B. 归并排序
C. 起泡排序
D. 希尔排序
满分：3分
12.求顶点间的最短路径问题，考虑的是下面的哪一种图 ()。
A. 无向图
B. 有向图
C. 带权的无向图
D. 带权的有向图
满分：3分
13.设二维数组A按行优先顺序存储且每个元素占c个单元，则元素A的地址为 ()。
A. LOC(A) + (j*m+i)*c
B. LOC(A) + (i*n+j)*c
C. LOC(A) + [(j-1)*m+i-1]*c
D. LOC(A) + [(i-1)*n+j-1]*c
满分：3分
14.ISAM是索引顺序存取方法，该方法是专为下面的哪一种设备设计的 ()。
A. 磁带
B. 磁盘
C. 光盘
D. 外存储器
满分：3分
15.在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A. 1/2
B. 1
C. 2
D. 4
满分：3分
16.B+ 树应用在 () 文件系统中。
A. ISAM
B. VSAM
C. 顺序
D. 散列
满分：3分
17.广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
A. ( g )
B. ( d )
C. c
D. d
满分：3分
18.在下述几种排序方法中，不稳定的排序方法是 ()。
A. 直接插入排序
B. 冒泡排序
C. 直接选择排序
D. 归并排序
满分：3分
19.在查找过程中，仅进行查找操作，没有引起表本身的改动，这种查找则称为 ()。
A. 静态查找
B. 动态查找
C. 内查找
D. 外查找
满分：3分
20.下列排序算法中，其中 () 是稳定的。
A. 堆排序，起泡排序
B. 快速排序，堆排序
C. 归并排序，起泡排序
D. 直接选择排序，归并排序
满分：3分
二、判断题（共20道试题，共40分。）
1.有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素个数的一半。
A. 错误
B. 正确
满分：2分
2.堆排序是稳定的排序方法。
A. 错误
B. 正确
满分：2分
3.哈希函数越复杂越好，因为这样随机性好，冲突概率小。
A. 错误
B. 正确
满分：2分
4.在待排数据基本有序的情况下，快速排序效果最好。
A. 错误
B. 正确
满分：2分
5.在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
A. 错误
B. 正确
满分：2分
6.存放在磁盘、磁带上的文件，既可以是顺序文件，也可以是索引结构或其他结构类型的文件。
A. 错误
B. 正确
满分：2分
7.对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。
A. 错误
B. 正确
满分：2分
8.若一个广义表的表头为空表，则此广义表亦为空表。
A. 错误
B. 正确
满分：2分
9.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大
A. 错误
B. 正确
满分：2分
10.一个有向图的邻接表和逆邻接表中结点的个数可能不等。
A. 错误
B. 正确
满分：2分
11.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
A. 错误
B. 正确
满分：2分
12.倒排文件的优点是维护简单。
A. 错误
B. 正确
满分：2分
13.无向图的邻接矩阵可用一维数组存储。
A. 错误
B. 正确
满分：2分
14.哈希表(散列表)的结点中只包含数据元素自身的信息，不包含任何指针。
A. 错误
B. 正确
满分：2分
15.( 101, 88, 46, 70, 34, 39, 45, 58, 66, 10）是堆。
A. 错误
B. 正确
满分：2分
16.带权的连通无向图的最小(代价)生成树必是唯一的。
A. 错误
B. 正确
满分：2分
17.快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
A. 错误
B. 正确
满分：2分
18.在待排序记录已经有序时，快速排序算法的时间复杂度为O(nlog2n )。
A. 错误
B. 正确
满分：2分
19.二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点X的值；其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。
A. 错误
B. 正确
满分：2分
20.广义表的取表尾运算，其结果仍是一个广义表。
A. 错误
B. 正确
满分：2分
页:
[1]