《数据结构》习题6

《数据结构》习题6 一、单项选择题

1. 算法的时间复杂度取决于____。
A. 问题的规模
B. 待处理数据的初始状态
C. A和B
D. 计算机的配置

2. 由n个无序的元素创建一个有序单链表的算法的时间复杂度是____。
A． O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n​)
B． O ( n ) O(n) O(n)
C． O ( n 2 ) O(n^2) O(n2)
D．A或C

3. 在____中将会用到栈结构。
A. 递归调用
B. 函数调用
C. 表达式求值
D.以上场景都有

4. 设循环队列的最大容量是N，front是头指针，rear是尾指针，则队空的判定条件为____。
A. (rear+1)%Nfront
B. rear+1front
C. rearfront==
D. rear=0，且front=0

5. 设二维数组A[3][5]，每个数组元素占用2个存储单元，若按列优先顺序进行存储，A[0][0]的存储地址为100，则A[2][3]的存储地址是____。
A. 122
B. 126
C. 114
D. 116

6. 在KMP算法中，串“ababaabab”的next数组值为____。
A. -1,0,0,1,2,3,1,2,3
B. -1,0,0,1,2,1,1,2,3
C. -1,0,0,1,2,3,4,1,2
D. -1,0,0,1,2,3,1,2,2

7. 在下列存储形式中，____不是m叉树（m>2）的存储形式？
A．双亲表示法
B．孩子链表表示法
C．孩子兄弟表示法
D．顺序存储表示法

8. 下面____算法适合用于构造一个稠密图的最小生成树。
A. Dijkstra算法
B. Prim算法
C. Floyd算法
D. Kruskal算法

9. ____方法可以判断一个有向图是否存在回路。
A. 求最小生成树
B. 拓扑排序
C. 求关键路径
D. 求最短路径

10. 已知图G的邻接表如图1所示，则从顶点V0出发进行深度优先遍历的结果是____。

A. 0,1,2,3,4
B. 0,1,2,4,3
C. 0,1,3,4,2
D. 0,1,4,2,3

11. 二分查找和二叉排序树查找的时间性能____。
A. 相同
B. 有时不同
C. 完全不同
D. 数量级都是O(log2n)

12. 关于m阶B-树说法错误的是____。
A. m阶B-树是一棵平衡的m叉树
B. B-树中的查找无论是否成功都必须找到最下层结点
C. 根结点最多含有m棵子树
D. 根结点至少含有2棵子树

13. 时间复杂度恒为 O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n​)且不受数据初始状态影响的排序算法是____。
A．归并排序
B．希尔排序
C．快速排序
D．简单选择排序

14. 有一种排序方法，它每一趟都将未排序序列中的一个元素，插入到已排序序列的合适位置，该排序方法是____。
A. 堆排序
B. 冒泡排序
C. 直接插入排序
D. 简单选择排序

15. 堆的形状是一棵____。
A. 满二叉树
B. 二叉判定树
C. 平衡二叉树
D. 完全二叉树

二、问答题

1. 有以下算法，分析执行fun(a,n,0)的时间复杂度。需要推导过程。

void fun(int a[], int n, int k) { // 数组a共有n个元素
    if (k == n - 1) 
    {
        for (int i = 0; i < n; i++)
            printf("% dn", a[i];
    }
    else 
    {
        for (int i = k; i < n; i++)
            a[i] = a[i] + i * i;
        fun(a, n, k + 1);
    }

• 设fun(a,n,k)的执行时间为 T 1 （ n , k ） T_1（n,k） T1​（n,k），则fun(a,n,0)的执行时间为 T ( n ) = T 1 ( n , 0 ) T(n)=T_1(n,0) T(n)=T1​(n,0)。由fun()算法可知：
  
  则 T ( n ) = T 1 ( n , 0 ) = n + T 1 ( n , 1 ) = n + ( n − 1 ) + T 1 ( n , 2 ) = … = n + ( n − 1 ) + … + 2 + T 1 ( n , n − 1 ) = + n = O ( n 2 ) T(n)=T_1(n,0)=n+T_1(n,1)=n+(n-1)+T_1(n,2)= …= n+(n-1)+…+2+T_1(n,n-1) = +n=O(n^2) T(n)=T1​(n,0)=n+T1​(n,1)=n+(n−1)+T1​(n,2)=…=n+(n−1)+…+2+T1​(n,n−1)=+n=O(n2)

2. 已知某二叉树的中序和后序遍历序列分别为BFDJGACHKEI和FJGDBKHIECA，请画出该二叉树，并给出该二叉树的先序遍历序列。

• 先序遍历序列为：ABDFGJCEHKI

3. 对于图2所示的带权有向图，若采用Dijkstra算法求从顶点a到其他顶点的最短路径和长度，第一条最短路径为：a->c，路径长度2，则求得的剩余最短路径依次是什么？（请按Dijkstra算法执行时产生最短路径的顺序，给出各最短路径及其长度）。

4. 设有一组关键字{32,13,49,24,38,21,4,12}，其哈希函数为：H(key)=key % 7，采用开放地址法的线性探查法解决冲突，试在0～9的哈希地址空间中对该关键字序列构造哈希表，并求等概率下查找成功和查找失败的平均查找长度。

5. 有一组关键字序列{66,89,8,123,9,44,55,37,200,127,98}：
（1）请将其调整成初始大根堆，并画出初始大根堆的树型表示。
（2）采用堆排序实现按关键字递增排序，请画出当有1个最大的关键字已放置到最终位置时，剩余关键字构成的大根堆。

三、算法设计题

1. 若一元稀疏多项式采用有序单链表进行存储，请给出一元稀疏多项式的存储结构，并基于此存储结构设计一个算法用于判断两个一元稀疏多项式是否相等。

2. 假设二叉排序树采用中序线索链表作为存储结构进行存储，请写出该线索链表的存储结构，并编写算法输出该二叉排序树中所有值在a，b之间的关键字，其中a < b，二叉排序树左子树结点的值小于根结点的值，右子树结点的值大于根结点的值，树中没有关键字相重的结点。