西北工业大学23春“计算机科学与技术”《数据结构》考试历年高频难、易错点试题甄选答案附答案

长风破浪会有时，直挂云帆济沧海。西北工业大学23春“计算机科学与技术”《数据结构》考试历年高频难、易错点试题甄选答案附答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.设有向图G中顶点数为n，图G最多有()条边。A.nB.n-1C.n*(n-1)/2D.n*(n-1)2.散列表的平均查找长度()。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关且与表的长度有关D.与处理冲突方法无关且与表的长度无关3.若二叉树中度为2的结点有15个，度为1的结点有10个该树有()个结点。A.25B.30C.31D.414.树型结构最适合用来描述()。A.有序的数据元素B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据5.二叉树在线索化后，仍不能有效求解的问题是()。A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋D.后序线索二叉树中求后序后继6.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是()。A.堆排序B.冒泡排C.直接选择排序D.快速排序7.常采用下面几种方式解决散列法中出现的冲突问题：()A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法8.散列表的平均查找长度()。A.与处理冲突的方法有关而与表的长度无关B.与处理冲突的方法无关而与表的长度有关C.与处理冲突的方法有关且与表的长度有关D.与处理冲突的方法无关且与表的长度无关9.设有向图有n个顶点和e条边，进行拓扑排序时总的计算时间为()。A.O(loge)B.O(en)C.O(elogn)D.O(n+e)10.用一维数组存放的一棵完全二叉树ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列()。A.HIDJKEBLFGCAB.ABCDEFGHIJKLC.HDIBJEKALFCGD.ABCDEGFHJIKL11.数据结构中，从逻辑上可以把数据结构分成()。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非先性结构D.内部结构和外部结构12.广义表运算式tail[((a,b),(c,d))]的结果为()。A.c,dB.(c,d)C.((c,d))D.d,c13.快速排序算法在最好情况下的时间复杂度为()。A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)14.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序，A11为第一个元素，其存储地址为1，每个元素占1个地址空间，则A82的地址为()。A.13B.30C.18D.015.下列说法中不正确的是()。A.图的遍历过程中每一顶点仅被访问一次B.遍历图的基本方法有深度优先搜索和广度优先搜索两种C.图的深度优先搜索的方法不适用于有向图D.图的深度优先搜索是一个递归过程第II卷一.综合考核(共15题)1.设有向图有n个顶点和e条边，进行拓扑排序时总的计算时间为()。A.O(loge)B.O(en)C.O(elogn)D.O(ne)2.若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有()个结点。A.15B.16C.17D.343.线性表的顺序存储结构是一种()存取结构。A.随即存取B.顺序存取C.索引存取D.散列存取4.对于单链表形式的队列，队空的条件是()。A.F=R=nullB.F=RC.F≠null且R=nullD.R-F=15.一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为()。A.n*nB.n*(n+1)/2C.(n+1)*(n+1)/2D.(n-1)*n/26.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用()排序算法最节省时间。A.堆排序B.希尔排序C.快速排序D.直接选择排序7.深度为6的二叉树至多有结点数为()。A.16B.30C.63D.318.关键路径是事件结点网络中()。A.最短的回路B.最长的回路C.从开始结点到完成结点的最长路径D.从开始结点到完成结点的最短路径9.数据表A中有00个元素，如果仅要求求出其中最大的10个元素，则采用()排序。A.堆排序B.希尔排序C.快速排序D.直接选择排序10.在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该()。A.只有左子树上的所有结点B.只有左子树上的部分结点C.只有右子树上的所有结点D.只有右子树上的部分结点11.常采用下面几种方式解决散列法中出现的冲突问题()。A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法12.已知广义表a=((a,b,c),(d,e,f)),从a中取出原子e的运算是()。A.tail(head(a))B.b.head(tail(a))C.head(tail(tail(head(a))))D.head(tail(tail(a)))13.下列陈述中正确的是()。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分14.下述排序算法中，稳定的是()。A.直接选择排序B.表插入排序C.快速排序D.堆排序15.对有序表18，20，25，34，48，62，74，85用二分查找法查找85，所需的比较次数为()。A.1次B.2次C.3次D.4次第I卷参考答案一.综合考核1.参考答案：D2.参考答案：C3.参考答案：D4.参考答案：C5.参考答案：D6.参考答案：A7.参考答案：D8.参考答案：A9.参考答案：D10.参考答案：A11.参考答案：C12.参考答案：C13.参考答案：A14.参考答案：B15.参考答案：C第