西北工业大学21秋《数据结构》复习考核试题库答案参考套卷59

西北工业大学21秋数据结构复习考核试题库答案参考1. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A2. B+树应用在( )文件系统中。A.顺序B.散列C.VSAMD.ISAM参考答案：C3. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C4. 下面关于线性表的叙述错误的是( )。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现参考答案：D5. 在队列中，允许进行删除操作的一端称为队尾。( )A、错误B、正确参考答案：B6. 若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A7. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。( )A、错误B、正确参考答案：A8. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，8，列下标为j=1，2，10。设每个字符占一个字节，若按行先存储，元素A8，5的起始地址与A按列存储时起始地址相同的元素是( )。A.A8，5B.A3，10C.A5，8D.A0，9参考答案：B9. 栈下溢是指在栈空时进行出栈操作。( )A、错误B、正确参考答案：B10. 在指定结点之后插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：B11. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C12. 队列的修改是按先进先出的原则进行的。( )A、错误B、正确参考答案：B13. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( )。A、P=SCIENCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案：A14. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B15. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为( )。A、4B、5C、6D、7参考答案：B16. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案：A17. 线性表是具有n个( )的有限序列。A.字符B.数据元素C.数据项D.表元素参考答案：B18. 线性表(a1，a2，.，an)以链式方式存储，访问第i位置元素的时间复杂度为( )。A.O(0)B.O(1)C.O(n)D.O(n2)参考答案：C19. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表参考答案：C20. 在计算机内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A21. 设根结点层次为1，某二叉树的结点前序序列和后序序列正好相反，则该二叉树一定是( )。A.高度等于其结点数B.空或只有一个结点C.任一结点无左子女D.任一结点无右子女参考答案：A22. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )。A.n-1B.nC.n+lD.2n参考答案：C23. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。( )A、错误B、正确参考答案：B24. 设二维数组A0.m-10.n-1按行优先顺序存储且每个元素占c个单元，则元素Aij的地址为( )。A.LOC(A00)+(j*m+i)*cB.LOC(A00)+(j-1)*m+i-1*cC.LOC(A00)+(i*n+j)*cD.LOC(A00)+(i-1)*n+j-1*c参考答案：C25. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。( )A、错误B、正确参考答案：A26. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法参考答案：C27. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是( )。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子参考答案：B28. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B29. 归并排序是一种稳定的排序方法。( )A.正确B.错误参考答案：A30. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考答案：A31. 队列的修改是按照先进先出的原则进行的。( )A、错误B、正确参考答案：B32. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B33. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是( )。A.不确定B.2C.1D.0参考答案：C34. 基数排序需要进行关键字的比较。( )A.正确B.错误参考答案：B35. 对线性表进行二分查找时，要求线性表必须( )。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列参考答案：C36. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。( )A.正确B.错误参考答案：B37. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。A.9B.10C.11D.12参考答案：C38. 中序遍历二叉排序树可以得到一个有序的序列。( )A.正确B.错误参考答案：A39. 稀疏矩阵常用的压缩存储方法有两种，它们是( )。A.散列和十字链表B.二维数组和三维数组C.三元组和散列D.三元组和十字链表参考答案：D40. 插入、删除只能在同一端进行的线性表，称为( )。A.队列B.栈C.循环队列D.循环栈参考答案：B41. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B42. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C43. 最小生成树问题是构造带权连通图(网)的最小代价生成树。( )A.正确B.错误参考答案：A44. 对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为( )A.DBFEACB.DFEBCAC.BDFECAD.BDEFAC参考答案：B45. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。( )A、错误B、正确参考答案：A46. 深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-1参考答案：A47. 栈的插入和删除操作在( )进行。A.栈顶B.栈底C.任意位置D.指定位置参考答案：A48. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C49. 设有以下四种排序方法，则( )的空间复杂度最大。A.冒泡排序B.快速排序C.堆排序D.希尔排序参考答案：B50. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有( )A.n-1B.nC.n+1D.n+2参考答案：B