910数据结构（2013年真题）

算法设计题

问题1

已知元素数据类型为整数的顺序表SL=（a1,a2,…,am,b1,b2,…,bn），试设计算法将SL中元素的两部分互换为（b1,b2,…,bn,a1,a2,…,am）。要求：不能使用额外的数组空间。
（1）用文字给出你的算法思想；
（2）用C语言写出算法的实现。

在这里插入代码片
1

问题2

对二叉链表存储的非空二叉树，从右向左依次释放所有叶子结点，释放的同时，把结点值存放到一个数组中。要求：
（1）用文字写出实现上述过程的基本思想；
（2）用C语言写出算法的实现。

在这里插入代码片
1

选择题错题整理

1.某算法的时间复杂度是O(n^2)，表明该算法（）。B
A.问题规模是n^2
B.问题规模与n^2成正比
C.执行时间等于n^2
D.执行时间与n^2成正比

2.当使用大小为n的一维数组顺序存储一个栈时，假定top==n表示栈空，则向该栈压入一个元素时，首先应执行（）语句修改top指针。B
A.top++
B.top–
C.top=0
D.top=n

5.一个深度为k且只有k个结点的二叉树按照完全二叉树顺序存储的方式存储在一个一维数组A[n]中，那么n应至少是（）。C
A.2k
B.2k-1
C.2^k - 1
D.2^k
分析：

7.（）算法可以求出无向图的所有连通分量。A
A.广度优先遍历
B.拓扑排序
C.求最短路径
D.求关键路径
分析：

10.下述几种排序算法中，平均查找长度最小的是（）。C
A.插入排序
B.选择排序
C.快速排序
D.归并排序

简答题

1.内存中一篇连续空间（不妨假设地址从0到m-1）提供给两个栈S1与S2使用，怎样分配这部分存储空间，使得对任一个栈仅当这部分空间全满时才发生上溢。

2.试说明一棵二叉树无论进行前序、中序或后序遍历，其叶子结点的相对次序都不会发生改变。

3.有4个顶点A、B、C、D的无向连通图。按广度优先和深度优先搜索遍历结果都为A、B、C、D，画出所有可能的结构图。

4.如果有一组关键字，以不同的次序输入后建立起来的二叉排序树是否相同？当中序遍历这些二叉排序树时，其遍历的结果是否相同？为什么？

5.现有一文件含有10000个记录，其中只有少量次序不对，且它们距离正确位置不远，如果以比较和移动此时作度量，将其进行排序的最好方法是什么？