自考02142《数据结构导论》真题及（2022.4）自考02142《数据结构导论》真题及答案解析（2022.4）1.[单选题]下列几种时间复杂度中，阶数最小的是（）A.O(log2n)B.O(n)C.O(n2)D.O(1)2.[单选题]栈和队列的共同特点是（）A.都是线性表B.先进先出C.后进先出D.只能插入操作3.[单选题]假设一个10x10的上三角矩阵A按照列优先顺序压缩在一维数组B中，则B数组的大小应为（）A.50B.55C.100D.1014.[单选题]一个栈的入栈序列是a，b，c，d，e，则栈可能的输出序列是（）A.edcab1B.deabcC.abcdeD.dceab5.[单选题]假定一个顺序存储的循环队列的队头和队尾指针分别为f和r，则判断队空的条件为（）A.f==NULLB.f==rC.r+1==fD.f+1==r6.[单选题]如果结点A有2个兄弟结点，结点B为A的双亲，则结点B的度为（）A.2B.3C.4D.57.[单选题]二叉树的中序遍历中，结点P排在结点Q之前的条件是在二叉树中（）A.P在Q的左边B.P在Q的右边C.P是Q的祖先D.P是Q的子孙8.[单选题]二又树的第k层的结点数最多为（）2A.2k-1B.2k+1C.2k-1D.2k+19.[单选题]A是7X4的二维数组，按行优先方式顺序存储元素A[0][0]的存储地址为1000，若每个元素占2个字节，则元素A[3][3]的存储地址为（）A.1026B.1028C.1030D.103210.[单选题]在表长为n的顺序表上做删除运算，其平均时间复杂度为（）A.O(1)B.O(n)C.O(nlog2n)D.O(n/2)11.[单选题]在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A.eB.2eC.n2-e3D.n2-2e12.[单选题]设顺序表的长度为n，则插入算法的平均移动次数约为（）A.nB.n/2C.n-1D.(n-1)/213.[单选题]设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134)，则用二分查找算法查找关键字90需要比较的关键字个数为（）A.1B.2C.3D.414.[单选题]以下排序方法中，稳定的是（）A.直接插入排序和快速排序B.快速排序和冒泡排序C.直接选择排序和冒泡排序D.冒泡排序和直接插入排序15.[单选题]对n个记录的文件进行快速排序，所需要的辅助存储空间的空间复杂度为（）A.O(1)B.O(n)4C.O(1og2n)D.O(n2)16.[填空题]1976年瑞士计算机科学家NiklausWirth曾提出一个著名公式：程序=数据结构+____。17.[填空题]简单地说，数据结构是计算机____数据和存储数据的方式。18.[填空题]线性表中结点个数n称为____。19.[填空题]线性表上的插入和删除运算限定在表的某一端进行的数损结构是____。20.[填空题]对稀疏矩阵进行压缩存储的目的是节省____。21.[填空题]一个具有n个顶点的有向完全图的弧数为=____.22.[填空题]构造最小生成树的算法有两种:Prim算法和____算法。23.[填空题]一棵树的结点个数最少为____。24.[填空题]有K个叶子结点的哈夫曼树，其结点的总数为____。25.[填空题]由二又树的后序序列和____序列，可以唯一确定一棵二又树。26.[填空题]二分查找算法的平均时间复杂度为____。27.[填空题]若待排序的序列中存在多个记录具有相同的健值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是____的。28.[填空题]在最坏情况下，即对几乎已是排好序的输入序列，快速排序算法的效率较低，此时其时间复杂度近似为____。529.[案例题]有一个整数序列。其输入顺序为20，30，90，-10，45，78，试利用栈将其输出序列改变为30，-10，45，90，78，20，写出该整数序列进栈和出栈的操作步骤。（用push(x)表示x进栈，pop(x)表示x出栈）30.[案例题]分别写出题30图所示的二叉树的先序遍历、中序遍历和后序遍历三种访问方式的结点访问序列。31.[案例题]