东北师范大学22春“计算机科学与技术”《数据结构》综合作业三辅导答案4

书山有路勤为径，学海无涯苦作舟！ 住在富人区的她东北师范大学22春“计算机科学与技术”数据结构综合作业三辅导答案一.综合考核(共50题)1.设散列地址空间为0m-1，key为关键字，用p去除key，将得到的余数作为key的散列地址，即h(key)=key%p。为了减少发生冲突的频率，一般取p为()。A.小于等于m的最大奇数B.小于等于m的最大偶数C.小于等于m的最大素数D.小于等于m的最大合数参考答案：C2.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。A.逆拓扑有序B.拓扑有序C.无序的D.部分有序的参考答案：A3.(101，88，46，70，34，39，45，58，66，10)是堆。()A.错误B.正确参考答案：B4.对一棵二叉树进行层次次序遍历时，应借助于一个栈。()A.错误B.正确参考答案：A5.已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为()。A.LOC(a0)+(i-1)*cB.LOC(a0)+i*cC.LOC(a0)-i*cD.LOC(a0)+(i+1)*c参考答案：B6.若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。()A.正确B.错误参考答案：A7.在完全二叉树中，若一个结点没有左子女，则它必是树叶。()A.错误B.正确参考答案：B8.广义表A=(a，b，(c，d)，(e，(f，g)，则式子head(tai(head(tail(tail(A)的值为()。A.(g)B.(d)C.cD.d参考答案：D9.空串与空格串是相同的。()A.错误B.正确参考答案：A10.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是()。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C11.归并排序的辅助存储空间代价为O(1)。()A.正确B.错误参考答案：B12.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行()。A.p-next=s; s-next=q;B.s-next=p-next; p-next=s;C.p-next=s-next; s-next=p;D.q-next=s; s-next=p;参考答案：D13.最佳二叉排序树是AVL树(平衡二叉排序树)。()A.正确B.错误参考答案：A14.在排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为()。A.直接选择排序B.冒泡排序C.直接插入排序D.希尔排序参考答案：C15.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?()A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A16.在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为()。A.希尔排序B.插入排序C.归并排序D.选择排序参考答案：D17.当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。()A.错误B.正确参考答案：A18.链接存储结构属静态存储方式。()A.正确B.错误参考答案：B19.对无序表用折半查找比顺序查找快。()A.正确B.错误参考答案：B20.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。()A.错误B.正确参考答案：B21.一个有向图的邻接表和逆邻接表中结点的个数可能不等。()A.正确B.错误参考答案：B22.二叉树在线索化后，仍不能有效求解的问题是()。A.后序线索二叉树中求后序后继B.前序线索二叉树中求前序后继C.中序线索二叉树中求中序后继D.中序线索二叉树中求中序前驱参考答案：A23.判断线索二叉树中某结点p有右子女的条件是()。A.p-rtag=1B.p-rtag=0C.p-lchild!=NULLD.p!=NULL参考答案：B24.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测?()A.k-1次B.k次C.k+1次D.k(k+1)/2次参考答案：D25.快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。()A.错误B.正确参考答案：A26.下列说法不正确的是()。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度优先遍历和广度优先遍历C.图的深度优先遍历不适用于有向图D.图的深度优先遍历是一个递归过程参考答案：C27.链表中的表头结点仅起到标识的作用。()A.错误B.正确参考答案：A28.堆是完全二叉树。()A.错误B.正确参考答案：B29.在一个图中，所有顶点的度数之和等于图的边数的几倍()。A.1/2B.1C.2D.4参考答案：C30.任何一个递归过程都可以转换成非递归过程。()A.正确B.错误参考答案：A31.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是()。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A32.直接选择排序算法对n个记录排序，在最好情况下的时间复杂度为O(n)。()A.错误B.正确参考答案：A33.算法分析的两个主要方面是()。A.正确性与健壮性B.时间复杂度与空间复杂度C.数据复杂性与程序复杂性D.可读性与可用性参考答案：B34.在待排数据基本有序的情况下，快速排序效果最好。()A.错误B.正确参考答案：A35.所谓取广义表的表尾就是返回广义表中最后一个元素。()A.错误B.正确参考答案：A36.在指定结点之前插入新结点时，双链表比单链表更方便。()A.正确B.错误参考答案：A37.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序()。A.稍有改变B.发生改变C.不能确定D.不发生改变参考答案：D38.在指定结点之后插入新结点时，双链表比单链表更方便。()A.正确B.错误参考答案：B39.四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是()。A.YB.XC.VD.U参考答案：C40.设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为()。A.h+1B.2h-1C.2hD.2h+1参考答案：D41.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。()A.正确B.错误参考答案：B42.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。A.nB.(n-1)/2C.n/2D.(n+1)/2参考答案：D43.二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。()A.错误B.正确参考答案：B44.数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是()。A.线性表B.树形结构C.广义表D.图结构参考答案：A45.二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。()A.错误B.正确参考答案：A46.递归过程的实现需用到()。A.线性表B.链表C.栈D.队列参考答案：C47.n个结点的线索二叉树上含有的线索数为()。A.n-1B.n+1C.nD.2n参考答案：B48.一个算法应该是()。A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C参考答案：B49.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。()A.错误B.正确参考答案：B50.分块查找要求表中的结点()。A.全部无序B.块之间无序C.全部有序D.块之间有序参考答案：D