数据结构试卷(三)一、 选择题(每题 2 分,共 20 分)1. 设某数据结构的二元组形式表示为 A=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>},则数据结构 A 是( B )。A. 线性结构B. 树形结构C. 物理结构D. 图形结构2. 下面程序的时间复杂度为( B )。1i = 12s = 03while i<=n:4 i += 15 t = 16for j in range(1,i):7 t = t * j8 s = s + tA. O(n)2B. O(n )3C. O(n )4D. O(n )3. 设指针变量 p 指向单链表中的结点 A,若删除单链表中的结点 A,则需要修改指针的操作序列为( A )。A. q=p.next; p.data=q.data; p.next=q.next;B. q=p.next; q.data=p.data; p.next=q.next;C. q=p.next; p.next=q.next;D. q=p.next; p.data=q.data;4. 设有 n 个待排序的记录关键字,在堆排序中需要( A )个辅助记录单元。A. 1B. nC. nlog2n2D. n5. 设一组记录关键字为(20,15,14,18,21,36,40,10),则以 20 为基准记录的一趟快速排序结束后的结果为( A )。A. 10,15,14,18,20,36,40,21B. 10,15,14,18,20,40,36,21C. 10,15,14,20,18,40,36,21D. 15,10,14,18,20,36,40,216. 设二叉排序树中有 n 个结点,则二叉排序树的平均查找长度为( B )。A. O(1)B. O(log2n)C. O(n)2D. O(n )7. 设无向图 G 中有 n 个顶点、e 条边,则其对应的邻接表中的表头结点和表结点的个数分别为( D )。A. n、eB. e、nC. 2n、eD. n、2e8. 设某强连通图中有 n 个顶点,则该强连通图中至少有( C )条边。A. n(n-1)B. n+1C. nD. n(n+1)9. 设有 5000 个待排序的记录关键字,如果需要用最快的方法选出其中最小的10 个记录关键字,则用下列( B )方法可以达到此目的。A. 快速排序B. 堆排序C. 归并排序D. 插入排序10. 下列 4 种排序中( D )的空间复杂度最大。A. 插入排序B. 冒泡排序C. 堆排序D. 归并排序二、 填空题(每空 1 分,共 20 分)1. 数据的物理结构主要包括 顺序存储结构 和 链式存储结构 两种情况。2. 设一棵完全二叉树中有 500 个结点,则该二叉树的深度为____9_____; 若用二叉链表作为该完全二叉树的存储结构,则共有_____501____个空指针域。3. 设输入序列为(1,2,3),则经过栈的作用后可...