东北师范大学2022年3月“计算机科学与技术”《数据结构》平时作业一（答案参考）试卷号：15

书山有路勤为径，学海无涯苦作舟！ 住在富人区的她东北师范大学2022年3月“计算机科学与技术”数据结构平时作业一（答案参考）一.综合考核(共45题)1.数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。()A.正确B.错误参考答案：A2.在下面的叙述中，正确的是()。A.树的先根遍历序列与其对应的二叉树的前序遍历序列相同B.树的先根遍历序列与其对应的二叉树的中序遍历序列相同C.树的先根遍历序列与其对应的二叉树的后序遍历序列相同D.树的后根遍历序列与其对应的二叉树的后序遍历序列相同参考答案：A3.健壮的算法不会因非法的输人数据而出现莫名其妙的状态。()A.正确B.错误参考答案：A4.判断线索二叉树中某结点p有右子女的条件是()。A.p-rtag=1B.p-rtag=0C.p-lchild!=NULLD.p!=NULL参考答案：B5.有n个顶点的有向图的边数最多为()。A.nB.n(n-1)C.n(n-1)/2D.2n参考答案：B6.链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。()A.正确B.错误参考答案：A7.AOV网的含义是以顶点表示活动的网。()A.正确B.错误参考答案：A8.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是()。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C9.最小生成树问题是构造带权连通图(网)的最小代价生成树。()A.正确B.错误参考答案：A10.广义表(a，b，c，d)的表头是()。A.aB.()C.(a，b，c，d)D.(b，c，d)参考答案：C11.“堆积”问题是由于()引起的。A.同义词之间发生冲突B.散列函数C.不同的同义词子表结合在一起D.散列表“溢出”参考答案：C12.在待排数据基本有序的情况下，快速排序效果最好。()A.错误B.正确参考答案：A13.任何无向图都存在生成树。()A.错误B.正确参考答案：A14.在指定结点之后插入新结点时，双链表比单链表更方便。()A.正确B.错误参考答案：B15.在一个图中，所有顶点的度数之和等于图的边数的几倍()。A.1/2B.1C.2D.4参考答案：C16.有n个顶点的无向图的边数最多为()。A.nB.n(n-1)C.n(n-1)/2D.2n参考答案：C17.在下列情况中，可称为二叉树的是()。A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树参考答案：B18.广义表运算式tail(a，b)，(c，d)的操作结果是()。A.dB.c，dC.(c，d)D.(c，d)参考答案：D19.串是一种数据对象和操作都特殊的线性表。()A.错误B.正确参考答案：B20.需要借助于一个栈来实现DFS算法。()A.错误B.正确参考答案：B21.将一棵树转成二叉树，根结点没有右子树。()A.错误B.正确参考答案：B22.二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。()A.正确B.错误参考答案：B23.无向图的邻接矩阵可用一维数组存储。()A.正确B.错误参考答案：A24.下面关于串的叙述中，哪一个是不正确的?()A.空串是由空格构成的串B.模式匹配是串的一种重要运算C.串是字符的有限序列D.串既可以采用顺序存储，也可以采用链式存储参考答案：A25.空串与空格串是相同的。()A.错误B.正确参考答案：A26.设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为()。A.h+1B.2h-1C.2hD.2h+1参考答案：D27.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。()A.正确B.错误参考答案：A28.下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序?()A.堆B.哈夫曼树C.二叉排序树D.AVL树参考答案：A29.四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是()。A.YB.XC.VD.U参考答案：C30.在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。()A.正确B.错误参考答案：A31.下面关于串的叙述中，哪一个是不正确的?()A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储参考答案：B32.取顺序表的第i个元素的时间与i的大小无关。()A.正确B.错误参考答案：A33.若要求尽可能快地对序列进行稳定的排序，则应选()。A.快速排序B.归并排序C.起泡排序D.希尔排序参考答案：B34.当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。()A.错误B.正确参考答案：A35.数组是同类型值的集合。()A.正确B.错误参考答案：B36.B+树应用在()文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C37.在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。()A.错误B.正确参考答案：A38.一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是()。A.不确定B.2C.1D.0参考答案：C39.快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。()A.错误B.正确参考答案：A40.链表中的表头结点仅起到标识的作用。()A.错误B.正确参考答案：A41.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。A.nB.(n-1)/2C.n/2D.(n+1)/2参考答案：D42.数据的逻辑结构是指数据的各数据项之间的逻辑关系。()A.正确B.错误参考答案：B43.串是一种特殊的线性表，其特殊性体现在()。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储参考答案：A44.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?()A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A45.一个有向无环图的拓扑排序序列()是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B