天津大学《数据结构》2021-2022学年期末试卷

天津大学2021-2022学年第二学期期末考试《数据结构》试卷(A卷)姓名学号题三四五六合计号得分一、选择题(30分)1.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()。(A)O)(B)O(nlogzn)(C)O(1)(D)O(n2)2.设一棵二叉树的深度为k,则该二叉树中最多有()个结点。(A)2k-1(B)2(C)2(D)213.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为()。(A)n(B)e(C)2n(D)2e4.在二叉排序树中插人一个结点的时间复杂度为()。(A)O1)(B)O(n)(C)O(log2n)(D)O(n)5.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（)条有向边。(A)n(B)n-1(C)m(D)m-16.设一组初始记录关键字序列为(345,253,674,924,627，则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。(A)3(B)4(C)5(D)87.设用链表作为栈的存储结构则退栈操作()。(A)必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(①)对栈不作任何判别8.下列四种排序中()的空间复杂度最大。(A)快速排序(B)冒泡排序(C)希尔排序(D)堆9.设某二叉树中度数为0的结点数为N,度数为1的结点数为N,度数为2的结点数为N2,则下列等式成立的是()(A)No=N+1 (B)No=N+N2(C)N=N+1(D)No=2N+l10.设有序顺序表中有个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过()。(A)log2n+1(B)log2n-1(C)logzn(D)logz(n+1)二、填空题(42分)1.设有个无序的记录关键字，则直接插人排序的时间复杂度为快速排序的平均时间复杂度为2.设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为(设结点中的两个指针域分别为link和rink)。3.根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为4.深度为k的完全二叉树中最少有个结点。5.设初始记录关键字序列为(K,K2,…,K),则用筛选法思想建堆必须从第个元素开始进行筛选。