四川大学《数据结构2264》21秋在线作业1答卷

1、数据结构226421秋在线作业1-00001试卷总分:100 得分:100一、单选题 (共 25 道试题,共 50 分)对线性表进行二分法查找，其前提条件是（ ）。线性表以链接方式存储，并且按关键码值排好序线性表以顺序方式存储，并且按关键码值的检索频率排好序线性表以顺序方式存储，并且按关键码值排好序线性表以链接方式存储，并且按关键码值的检索频率排好序答案:C2.对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（ ）。2459899答案:A3.树最适合用来表示（ ）。有序数据元素无序数据元素元素之间具有分支层次关系的数据元素之间无联系的数据答案:C4.

2、设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。5678答案:A5.若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（ ）。图中每个顶点的入度图中每个顶点的出度图中每个顶点的度图中连通分量的数目答案:A6.对于关键字序列（ ）进行散列存储时，若选用H（ ）=K%7作为散列函数，则散列地址为0的元素有（ ）个。1234答案:D7.对关键字序列（ ）进行增量为3的一趟希尔排序的结果为（ ）。(19, 23, 56, 34, 78, 67, 88, 92)(23, 56, 78, 66, 88, 92, 19, 34)(19, 23, 34, 56, 67, 78, 88,

3、 92)(19, 23, 67, 56, 34, 78, 92, 88)答案:D8.若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为（ ）。1，2，39，5，2，39，5，39，4，2，3答案:D9.以下数据结构中哪一个是非线性结构？（ ）队列栈线性表二叉树答案:D10.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。m-n-1n+1m-n+1m-n答案:D11.二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087，A47的存储地址为1153，则

4、数组元素A67的存储地址为（ ）。1207120912111213答案:A12.如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。直接插入排序快速排序归并排序选择排序答案:A13.设Huffman树的叶子结点数为m，则结点总数为（ ）。2m2m-12m+1m+1答案:B14.带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（ ）。head= =NULhead-next= =NULLhead!=NULLhead-next= =head答案:D15.中缀表达式2+X*（ ）的后缀形式是（ ）。3 Y X 2 + * +Y 3 + X * 2 +

5、2 X Y 3 * + +2 X Y 3 + * +答案:D16.k层（ ）二叉树的结点总数最多为（ ）。2k-12K+12K-12k-1答案:A17.对线性表，在下列哪种情况下应当采用链表表示？（ ）经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间表中元素的个数不变答案:B18.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）。11351953答案:B19.在数据结构中，数据元素可由（ ）。实体域数据项字段答案:C20.数据的基本单位是（ ）。数据项数据类型数据元素数据变量答案:A21.AOV网是一种（ ）。有向图无向图无向无环图有

6、向无环图答案:D22.含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为（ ）。3456答案:A23.从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。O(n)O(1)O(log2n)O(n2)答案:C24.下列关于数据结构的叙述中，正确的是（ ）。数组是不同类型值的集合递归算法的程序结构比迭代算法的程序结构更为精炼树是一种线性结构用一维数组存储一棵完全二叉树是有效的存储方法答案:D25.若有序表为（ ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ ）。f,c,bf,d,bg,c,bg,d,b答案:A二、多选题 (共 4 道试题,共 20 分)26.以下哪些是

7、队列的基本运算？（ ）在队列第i个元素之后插入一个元素从队头删除一个元素判断一个队列是否为空读取队头元素的值将队列中的元素排序答案:BCD27.对一个算法的评价，主要包括如下（ ）方面的内容。健壮性和可读性并行性正确性时空复杂度界面友好性答案:ACD28.栈和队列的共同特点是（ ）。只允许在端点处插入和删除元素都是先进后出都是先进先出没有共同点都可以采用顺序存储方式和链式存储方式答案:AE29.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为（ ）。3，2，6，1，4，53，4，2，1，6，51，2，5，3，4，65，6，4，2，3，16，5，4，3，2，

8、1答案:ACD三、判断题 (共 15 道试题,共 30 分)30.在线性链表中删除某个结点时，只需将被删结点释放。答案:错误31.对任何用顶点表示活动的网络（ ）进行拓扑排序的结果都是唯一的。答案:错误32.进行折半搜索的表必须是顺序存储的有序表。答案:正确33.一个广义表（ ）,（ ）,c),（ ）) 的表尾是（ ）,c),（ ）)。答案:错误34.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。答案:错误35.若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。答案:错误36.为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。答案:正确37.二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。答案:错误38.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。答案:正确39.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。答案:正确40.线性表的长度是线性表所占用的存储空间的大小。答案:错误