数据结构-Python语言描述试卷三附答案

数据结构试卷（三）一、 选择题(每题 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），则经过栈的作用后可...