东北师范大学23春“计算机科学与技术”《数据结构》考试高频考点参考题库含答案

长风破浪会有时，直挂云帆济沧海。东北师范大学23春“计算机科学与技术”《数据结构》考试高频考点参考题库带答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.完全二叉树一定存在度为1的结点。()A.正确B.错误2.数组是同类型值的集合。()A.错误B.正确3.任何一个递归过程都可以转换成非递归过程。()A.正确B.错误4.“堆积”问题是由于()引起的。A.同义词之间发生冲突B.散列函数C.不同的同义词子表结合在一起D.散列表“溢出”5.数据的逻辑结构是指数据的各数据项之间的逻辑关系。()A.正确B.错误6.设散列地址空间为0~m-1，key为关键字，用p去除key，将得到的余数作为key的散列地址，即h(key)=key%p。为了减少发生冲突的频率，一般取p为()。A.小于等于m的最大奇数B.小于等于m的最大偶数C.小于等于m的最大素数D.小于等于m的最大合数7.一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是()。A.不确定B.2C.1D.08.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是()。A.堆排序B.堆排序C.堆排序>归并排序>快速排序D.堆排序>快速排序>归并排序9.n个结点的线索二叉树上含有的线索数为()。A.n-1B.n+1C.nD.2n10.链表中的表头指针与表头结点起到相同的作用。()A.错误B.正确11.无向图的邻接矩阵可用一维数组存储。()A.正确B.错误12.二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。()A.错误B.正确13.若要求尽可能快地对序列进行稳定的排序，则应选()。A.快速排序B.归并排序C.起泡排序D.希尔排序14.有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是()。A.60B.66C.18000D.3315.链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。()A.正确B.错误第II卷一.综合考核(共15题)1.任何无向图都存在生成树。()A.错误B.正确2.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用()的方法可降低所需的代价。A.附加文件B.按关键字大小排序C.按记录输入先后排序D.连续排序3.求图的最小(代价)生成树问题，考虑的是下面的哪一种图?()A.有向图B.无向图C.带权的有向图D.带权的无向图4.串是一种特殊的线性表，其特殊性体现在()。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储5.分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。()A.正确B.错误6.下列说法不正确的是()。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度优先遍历和广度优先遍历C.图的深度优先遍历不适用于有向图D.图的深度优先遍历是一个递归过程7.当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。()A.错误B.正确8.在一个图中，所有顶点的度数之和等于图的边数的几倍()。A.1/2B.1C.2D.49.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。()A.错误B.正确10.若哈希表(散列表)的负载因子l，则可避免冲突的产生。()A.正确B.错误11.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。()A.错误B.正确12.对一棵二叉树进行层次次序遍历时，应借助于一个栈。()A.错误B.正确13.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?()A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序14.稀疏矩阵压缩存储后，必会失去随机存取功能。()A.正确B.错误15.一个算法应该是()。A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C第III卷一.综合考核(共15题)1.非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。()A.错误B.正确2.插入、删除只能在同一端进行的线性表，称为()。A.队列B.栈C.循环队列D.循环栈3.对于3个结点a、b、c，可构成不同的二叉树的棵数为()。A.32B.30C.28D.244.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为()。A.nB.(n-1)/2C.n/2D.(n+1)/25.四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是()。A.YB.XC.VD.U6.有n个顶点的有向图的边数最多为()。A.nB.n(n-1)C.n(n-1)/2D.2n7.最小生成树问题是构造带权连通图(网)的最小代价生成树。()A.正确B.错误8.head指向的带表头结点的单链表为空的判定条件是()。A.head->next==headB.head->next==NULLC.head==NULLD.head!=NULL9.二维以上的数组其实是一种特殊的广义表。()A.错误B.正确10.必须把一般的树转换成二叉树后才能进行存储。()A.错误B.正确11.需要借助于一个栈来实现DFS算法。()A.错误B.正确12.最小生成树问题是构造带权连通图(网)的最小代价生成树。()A.错误B.正确13.二叉树在中序线索化后，仍不能有效求解的问题是()。A.求指定结点的前序后继B.求指定结点的中序前驱C.求指定结点的中序后继D.求指定结点的后序后继14.设二维数组A[0..m-1][0..n-1]按行优先顺序存储且每个元素占c个单元，则元素A[i][j]的地址为()。A.LOC(A[0][0])+(j*m+i)*cB.LOC(A[0][0])+[(j-1)*m+i-1]*cC.LOC(A[0][0])+(i*n+j)*cD.LOC(A[0][0])+[(i-1)*n+j-1]*c15.()的遍历仍需要栈的支持。A.前序线索二叉树B.中序线索二叉树C.后序线索二叉树D.前三种均需要第I卷参考答案一.综合考核1.参考答案：B2.参考答案：A3.参考答案：A4.参考答案：C5.参考答案：B6.参考答案：C7.参考答案：C8.参考答案：A9.参考答案：B10.参考答案：A11.参考答案：A12.参考答案：A13.参考答案：B14.参考答案：A15.参考答案：A第II卷参考答案一.综合考核1.参考答案：A2.参考答案：A3.参考答案：D4.参考答案：A5.参考答案：A6.参考答案：C7.参考答案：A8.参考答案：C9.参考答案：A10.参考答案：B11.参考答案：B12.参考答案：A13.参考答案：A14.参