《数据结构2264》23春在线作业2答卷

《数据结构2264》22秋在线作业2-00001试卷总分:100得分:100一、单选题(共25道试题,共50分)1.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。A.11B.35C.19D.53答案:B2.一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是（）。A.231B.321C.312D.123答案:C3.带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（）。A.head==NULB.head->next==NULLC.head!=NULLD.head->next==head答案:D4.一散列表长度m为100，采用除留余数法构造散列函数，即H（）=K%P（）,，为使散列函数具有较好的性能，P的选择应是（）。A.99B.100C.97D.93答案:C5.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（）。A.m-n-1B.n+1C.m-n+1D.m-n答案:D6.在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（）。A.插入B.删除C.排序D.查找答案:D7.对于线性表（）进行散列存储时，若选用H（）=K%9作为散列函数，则散列地址为1的元素有（）个。A.1B.2C.3D.4答案:D8.k层（）二叉树的结点总数最多为（）。A.2k-1B.2K+1C.2K-1D.2k-1答案:A9.树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据答案:C10.采用开放定址法处理散列表的冲突时，其平均查找长度（）。A.低于链接法处理冲突B.高于链接法处理冲突C.与链接法处理冲突相同D.高于二分查找答案:B11.中缀表达式2+X*（）的后缀形式是（）。A.3YX2+*+B.Y3+X*2+C.2XY3*++D.2XY3+*+答案:D12.如表r有100000个元素，前99999个元素递增有序，则采用（）方法比较次数较少。A.直接插入排序B.快速排序C.归并排序D.选择排序答案:A13.对n个记录进行堆排序，所需要的辅助存储空间为（）。A.O（1og2nB.O（n）C.O（1）D.O（n2）答案:C14.含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为（）。A.3B.4C.5D.6答案:A15.对一个算法的评价，不包括如下（）方面的内容。A.健壮性和可读性B.并行性C.正确性D.时空复杂度答案:B16.下面关于广义表的叙述中，不正确的是（）。A.广义表可以是一个多层次的结构B.广义表至少有一个元素C.广义表可以被其他广义表所共享D.广义表可以是一个递归表答案:B17.对关键字序列（）进行增量为3的一趟希尔排序的结果为（）。A.(19,23,56,34,78,67,88,92)B.(23,56,78,66,88,92,19,34)C.(19,23,34,56,67,78,88,92)D.(19,23,67,56,34,78,92,88)答案:D18.对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（）。A.24B.5C.98D.99答案:A19.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表答案:D20.设Huffman树的叶子结点数为m，则结点总数为（）。A.2mB.2m-1C.2m+1D.m+1答案:B21.若有序表为（），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）。A.f,c,bB.f,d,bC.g,c,bD.g,d,b答案:A22.队列的特点是（）。A.先进后出B.先进先出C.任意位置进出D.前面都不正确答案:B23.下列关于数据结构的叙述中，正确的是（）。A.数组是不同类型值的集合B.递归算法的程序结构比迭代算法的程序结构更为精炼C.树是一种线性结构D.用一维数组存储一棵完全二叉树是有效的存储方法答案:D24.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（）。A.iB.i+1C.n-iD.n-i+1答案:C25.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（）语句序列。A.p=q;p->next=q;B.p->next=q;q->next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;答案:D二、多选题(共4道试题,共20分)26.对一个算法的评价，主要包括如下（）方面的内容。A.健壮性和可读性B.并行性C.正确性D.时空复杂度E.界面友好性答案:ACD27.以下哪些是队列的基本运算？（）A.在队列第i个元素之后插入一个元素B.从队头删除一个元素C.判断一个队列是否为空D.读取队头元素的值E.将队列中的元素排序答案:BCD28.下述（）是顺序存储方式的优点。A.存储密度大B.插入和删除运算方便C.获取符合某种条件的元素方便D.查找运算速度快E.可以很方便地存取第i个元素答案:AE29.以下序列中，是堆（）的有（）。A.{15,26,38,49,27,51,39,62}B.{15,23,71,94,72,68,26,73}C.{15,27,26,49,38,62,39,51}D.{15,23,26,68,94,72,71,73}E.{94,72,73,26,71,23,68,15}答案:ACDE三、判断题(共15道试题,共30分)30.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。答案:正确31.快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。答案:正确32.栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。答案:正确33.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。答案:错误34.用字符数组存储长度为n的字符串，数组长度至少为n+1。答案:正确35.一个广义表（）,（）,c),（）)))的表尾是（）,c),（）))。答案:错误36.线性表若采用链式存储表示,在删除时不需要移动元素。答案:正确37.线性表的长度是线性表所占用的存储空间的大小。答案:错误38.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。答案:正确39.若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。答案:错误40.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。答案:错误41.图G的某一最小