东北师范大学22春“计算机科学与技术”《数据结构》离线作业（一）辅导答案36

《东北师范大学22春“计算机科学与技术”《数据结构》离线作业（一）辅导答案36》由会员分享，可在线阅读，更多相关《东北师范大学22春“计算机科学与技术”《数据结构》离线作业（一）辅导答案36（7页珍藏版）》请在装配图网上搜索。

1、书山有路勤为径，学海无涯苦作舟！ 住在富人区的她东北师范大学22春“计算机科学与技术”数据结构离线作业（一）辅导答案一.综合考核(共50题)1.广义表(a，b，c，d)的表头是()。A.aB.()C.(a，b，c，d)D.(b，c，d)参考答案：C2.在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为()。A.希尔排序B.插入排序C.归并排序D.选择排序参考答案：D3.非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。()A.错误B.正确参考答案：B4.设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所

2、包含的结点数至少为()。A.h+1B.2h-1C.2hD.2h+1参考答案：D5.下面哪些方法可以判断出一个有向图是否有环(回路)?()A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历参考答案：C6.链接存储结构属动态存储方式。()A.正确B.错误参考答案：A7.空串与空格串是相同的。()A.错误B.正确参考答案：A8.判断线索二叉树中某结点p有左子女的条件是()。A.p!=NULLB.p-lchild!=NULLC.p-ltag=0D.p-ltag=1参考答案：C9.设散列地址空间为0m-1，key为关键字，用p去除key，将得到的余数作为key的散列地址，即h(key)=ke

3、y%p。为了减少发生冲突的频率，一般取p为()。A.小于等于m的最大奇数B.小于等于m的最大偶数C.小于等于m的最大素数D.小于等于m的最大合数参考答案：C10.文件系统采用索引结构是为了节省存储空间。()A.错误B.正确参考答案：A11.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是()。A.堆排序B.堆排序C.堆排序归并排序快速排序D.堆排序快速排序归并排序参考答案：A12.head指向的带表头结点的单链表为空的判定条件是()。A.head-next=headB.head-next=NULLC.head=NULLD.head!=NULL参考答案：B13.结构的存储密度定义

4、为数据本身所占的存储量与整个结构所占的存储量之比。()A.正确B.错误参考答案：A14.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。A.nB.(n-1)/2C.n/2D.(n+1)/2参考答案：D15.对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。()A.错误B.正确参考答案：B16.在下面的叙述中，正确的是()。A.树的先根遍历序列与其对应的二叉树的前序遍历序列相同B.树的先根遍历序列与其对应的二叉树的中序遍历序列相同C.树的先根遍历序列与其对应的二叉树的后序遍历序列相同D.树的后根遍历序列与其对应的二叉树的后序遍历序列相同参考答案：A17.串是一种特殊

5、的线性表，其特殊性体现在()。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储参考答案：A18.下列描述中正确的是()。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容参考答案：A19.将一个A1.100，1.100的三对角矩阵，按行优先次序存入一维数组B1.298中，A中元素A66，65在数组B中的位置K为()。A.199B.197C.195D.193参考答案：C20.在执行某个排序算法过程中，出现了排序码朝着它最终排序位

6、置相反的方向移动，则该算法是不稳定的。()A.错误B.正确参考答案：A21.设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是()。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A22.AOV网的含义是以顶点表示活动的网。()A.正确B.错误参考答案：A23.二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。()A.错误B.正确参考答案：B24.有n个顶点的无向图的边数最多为()。A.nB.n(n-1)C.n(n-1)/2D.2n参考答案：C25.()的遍历仍需要栈的支持。A.前序线索二叉树B.中序线索二叉树C

7、.后序线索二叉树D.前三种均需要参考答案：C26.稀疏矩阵压缩存储后，必会失去随机存取功能。()A.正确B.错误参考答案：A27.程序一定是算法。()A.正确B.错误参考答案：B28.任何无向图都存在生成树。()A.错误B.正确参考答案：A29.当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。()A.错误B.正确参考答案：A30.快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。()A.错误B.正确参考答案：A31.最佳二叉排序树是AVL树(平衡二叉排序树)。()A.正确B.错误参考答案：A32.若要求尽可能快地对序列进行稳定的排序，则应选()。A.快速排序B.

8、归并排序C.起泡排序D.希尔排序参考答案：B33.一个队列的入队序列是a、b、c、d，则队列的输出序列是()。A.dcbaB.cbdaC.adcbD.abcd参考答案：D34.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是()。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C35.广义表运算式tail(a，b)，(c，d)的操作结果是()。A.dB.c，dC.(c，d)D.(c，d)参考答案：D36.在待排数据基本有序的情况下，快速排序效果最好。()A.错误B.正确参考答案：A37.对一棵二叉树进行层次次序遍历时，应借助于一个栈

9、。()A.错误B.正确参考答案：A38.连通分量是无向图中的极大连通子图。()A.错误B.正确参考答案：B39.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是()。A.O(log2n)B.O(1)C.O(n)D.O(nlog2n)参考答案：B40.将一棵树转成二叉树，根结点没有右子树。()A.错误B.正确参考答案：B41.无向图的邻接矩阵可用一维数组存储。()A.正确B.错误参考答案：A42.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。()A.正确B.错误参考答案：A43.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。()A.错误B.正确参考答案：B44.二叉

10、树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。()A.错误B.正确参考答案：A45.所谓取广义表的表尾就是返回广义表中最后一个元素。()A.错误B.正确参考答案：A46.一个算法应该是()。A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C参考答案：B47.用链表(lchild-rchild表示法)存储的包含n个结点的二叉树，结点的2n个指针域中有n+1个空指针。()A.错误B.正确参考答案：B48.在一个单链表中，已知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;参考答案：D49.假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测?()A.k-1次B.k次C.k+1次D.k(k+1)/2次参考答案：D50.栈和队列都是限制存取点的线性结构。()A.正确B.错误参考答案：A