《数据结构》习题

《数据结构》习题一、单项选择题1．对矩阵进行压缩存储是为了（）A．节省存储空间B．提高运算速度C．便于运算D．方便存储2．链式栈与顺序栈相比，一个比较明显的优点是（）A．插入操作更加方便B．通常不会出现栈满的情况C．不会出现栈空的情况D．删除操作更加方便3．设输入序列为1，2，3，4，5，则借助一个队列可以得到的输出序列是（）A．3，4，1，2，5B．1，2，3，4，5C．2，3，4，1，5D．5，4，3，2，14.一个栈的输入序列是6,5,4,3,2,1,可能的输出序列是（）A．4,3,2,1,5,6B．3,6,2,1,5,4C．1,2,3,5,4,6D．5,4,1,3,2,65．设输入序列为A，B，C，D。借助一个栈可以得到的输出序列是（）A．A，C，D，BB．C，A，D，BC．D，C，A，BD．D，A，B，C6．将含100个结点的完全二叉树从根开始，每层从左到右依次对结点编号，根结点的编号为1，则编号为71的结点的双亲结点的编号为（）A．34B．35C．36D．无法确定7．已知完全二叉树有80个结点，则该二叉树有（）个度为1的结点。A．0B．1C．2D．不确定8．任何一个无向连通图的最小生成树（）A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在9．设图G用邻接表存储，对该图进行深度优先搜索遍历，则算法的时间复杂度为（）A．O(n)B．O(n+e)C．O(n2)D．O(n3)10．用n个键值构造一棵二叉排序树，最低高度为（）A．n/2B．nC．[㏒2n]D．[㏒2n]+111．如果以链表作为栈的存储结构，则执行出栈操作时（）A．必须判断栈是否满B．必须判断栈是否空C．判断栈元素的类型D．对栈不作任何判断12．设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）A．front=front+1B．front=(front+1)%mC．rear=(rear+1)%mD．front=(front+1)%(m+1)13．线性表的长度是指（）A．顺序存储方式下数组所占用的元素个数B．链表存储方式下的结点个数C．表中的元素个数D．所能存储的最大的结点个数14．设有一个无向图G＝(V，E)和G’=(V’，E’)，如果G’是G的生成树，则下面不正确的说法是（）A．G’为G的子图B．G’为G的连通分量C．G’为G的极小连通子图且V’=VD．G’是G的一个无环子图15．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（）A．一定都是同义词B．一定都不是同义词C．都相同D．不一定都是同义词16．在有序表A[20]中按二分查找方法查找A[13]依次比较的元素的下标是（）A．9，14，12，13B．9，15，12，13C．9，14，11，12，13D．10，15，12，1317．栈和队列都是（）A．顺序存储的线性表B．链式存储的线性表C．限制的线性表D．限制存储点的非线性结构18．向顺序栈中压入新元素时，应当（）A．先移动栈顶指针，再存入元素B．先存入元素，再移动栈顶指针C．先后次序无关紧要D．同时进行19．若树的先序序列和中序序列正好相同，则一定是一棵（）的二叉树。A．结点个数可能大于1且该树无左子树B．结点个数可能大于1且根结点无左孩子C．结点个数可能大于1且各结点均无左孩子D．其中任意一个结点的度不为220．下列算法中，在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的算法是()A．归并排序B．直接插入排序C．快速排序D．冒泡排序21．当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较元素的次数为（）A．n2B．n㏒2nC．㏒2nD．n-122．下列排序算法中，在最好情况下，时间复杂度为O(n)的算法是（）A．直接选择排序B．归并排序C．快速排序D．冒泡排序23．下列排序方法中，排序所花费时间不受数据初始排列特性影响的算法是（）A．直接插入排序B．冒泡排序C．直接选择排序D．快速排序24．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）A．直接选择排序B．直接插入排序C．快速排序D．起泡排序25．对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。A．8B．10C．15D．2526．在一个具有n个结点的双链表中插入一个新结点,则该操作的时间复杂性的量级为（）A．O(1)B．O(n)C．O(nlog2n)D．O(n2)27．二分查找法要求被查找的表是（）A．顺序表B．分块有序表C．顺序表且是按键值递增或递减次序排列D．不受上述任何限制28．若某线性表中最常用的操作是在最后一个元素之后插人一个元素和删除第1个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．仅有尾指针的单循环链表D．双链表29．在一个顺序存储的循环队列中，队头指针指向队头元素的（）A．前一个位置B．后一个位置C．队头元素位置D．队尾元素的前一个位置30．设循环队列用数组A[n]存储，头尾指针为front和rear,求解当前队列中元素个数的公式()A．rear-frontB．front-rearC．n-(front-rear)D．(n+rear-front)％n31．已知完全二叉树有100个结点，则该完全二叉树共有（）个叶子结点。A．37B．49C．50D．不确定32．下列存储形式中，（）不是树的存储形式。A．双亲表示法B．左子女右兄弟表示法C．广义表表示法D．顺序表示法33．在一棵具有5层的满二叉树中结点总数为（）A．31B．32C．33D．1634．设有100个数据元素，采用折半搜索时，最大比较次数为（）A．6B．7C．8D．1035．在顺序存储的线性表(a1,a2,...,an)中,删除任意一个结点时所需移动结点的平均次数为（）A．nB．n/2C．(n-1)/2D．(n+1)/236．下列说法不正确的是（）A．数据元素是数据的基本单位B．数据项是数据中不可分割的最小标识单位C．数据可由若干个数据元素构成D．数据项可由若干个数据元素构成37．为了方便在线性结构的数据中插入一个数据元素,则其数据结构宜采用（）方式A．顺序存储B．链式存储C．索引存储D．散列存储38．矩阵A5×6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5][5]的地址为（）A．1120B．1125C．1140D．114539．设矩阵A(aij，0≤i,j≤9)的元素满足：aij≠0(i≥j,0≤i,j≤9)aij=0(ij,0≤i,j≤9)现将A中所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占4个单元，则元素a[9，5]的地址为（）A．2384B．2380C．2204D．220040．若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（）。A．上三解矩阵B．稀疏矩阵C．对角矩阵D．对称矩阵41．设n阶方阵A是对称矩阵，为节省存储空间,将其下三角(包括对角线)以行序为主序存储在一维数组B[1..n(n+1)/2]中,则对任一上三角元素aij(ij,1≤i≤n,1≤j≤n),在一维数组B中的下标位置k是()A．i(i-1)/2+jB．j(j-1)/2+iC．i(j-1)/2+iD．j(i-1)/2+i42．对于静态表顺序查找算法，若在表头设置岗哨，则正确的查找方式为（）A．从第0个元素往后查找该数据元素B．从第1个元素往后查找该数据元素C．从第n个元素开始往前查找该数据元素D．与查找顺序无关43．常采用下面几种方式解决散列法中出现的冲突问题（）A．数字分析法、除余法、平方取中法B．数字分析法、除余法、线性探测法C．数字分析法、线性探测法、多重散列法D．线性探测法、多重散列法、链地址法44．若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（）A．归并排序B．直接插入排序C．直接选择排序D．快速排序45.中序遍历与后序遍历结果相同的二叉树为（）A．根节点无左孩子的二叉树B．根节点无右孩子的二叉树C．所有结点只有左子树的二叉树D．所有结点只有右子树的二叉树46.下列关于广义表的叙述中错误的是（）A．广义表是线性表的推广B．广义表至少有一个元素是子表C．广义表可以是自身的子表D．广义表可以是空表47.用快速排序算法对线性表排序,若选择表中第一个元素作为分界元素,则表中按（）分布时排序效率最高.A．已经有序B．部分有序C．完全有序D．逆序48．若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）A．S1的栈底位置为0，S2的栈底位置为n+1B．S1的栈底位置为0，S2的栈底位置为n/2C．S1的栈底位置为1，S2的栈底位置为nD．S1的栈底位置为1，S2的栈底位置为n/249．在有n个结点的二叉链表中，值为非空的链域的个数为（）A．n-1B．2n-1C．n+1D．2n+150．带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）A．第i行非∞的元素之和B．第i列非∞的元素之和C．第i行非∞且非0的元素个数D．第i列非∞且非0的元素个数51．在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）A．0(n)B．0(log2n)C．0(nlog2n)D．0(n2)52．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（）存储方式节省时间。A．单链表B．双链表C．单循环链表D．顺序表53．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）遍历实现编号。A．先序B．中序C．后序D．从根开始的层次遍历54．下列排序算法中，（）算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。A．堆排序B．冒泡排序C．快速排序D．SHELL排序55．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（）A．0B．1C．2D．不确定56．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（）个元素。A．n-iB．n-i+1C．n-i-1D．i57．假定一个顺序队列的队首和队尾指针分别为1和r，则判断队空的条件为（）A．f+1==rB．r＋1==fC．f==0D．f==r58．哈夫曼树的带权路径长度WPL等于（）A．除根以外的所有结点的权植之和B．所有结点权值之和C．各叶子结点的带权路径长度之和D．根结点的值59．一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}60．线性链表不具有的特点是（）A．随机访问B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比61．设有一个l0阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[n]中，A[0][0]存入B[0]中，则A[8][5]在B[n]中（）位置。A．32B．33C．41D．6562．设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶子结点，则B中右指针域为空的结点有（）个。A．n-1B．nC．n+lD．n+263．对有14个数据元素的有序表R[0-13]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为()。A．R[0]，R[1]，R[2]，R[3]B．R[0]，R[13]，R[2]，R[3]C．R[6]，R[2]，R[4]，R[3]D．R[6]，R[4]