北京工业大学计算机896数据结构考研真题答案2
- 格式：pdf
- 大小：512.07 KB
- 文档页数：11
D A B C 【参考解答】 如果在遍历过程中遇到同一条遍历路径上已经访问过的顶点， 则表明图中存在 回路。
const int VEX_MAX = 100; // 图中最大顶点数 int visited[VEX_MAX]; // 同一条遍历路径上顶点的访问标志 // 从顶点v出发深度优先搜索图G，判断图中是否存在回路 bool existCyclePath(Graph G, int v) { // 访问顶点v visited[v] = 1; // 置访问标志 // 遍历v的邻接点w for(w=FirstAdjVex(G,v); w!=NULL; w=NextAdjVex(G,v,w)) { // 如果w已访问过，必存在回路，直接返回（无需继续遍历） if(visited[w]) return true;
// 将 n 个红、白、蓝元素（分别用1、2、3表示）组成的序列 // 按照红、白、蓝的顺序排列 void Arrange(int a, int n) { int i = 0; // 从前向后保存红色（1）元素 int j = n-1; // 从后向前保存蓝色（3）元素 int k = 1; while(k<=j) { if(a[k]==1) { int t=a[k]; a[k]=a[i]; a[i]=t; // 交换a[k]和a[i] i++; k++; // 注意：这里k++防止i==k时陷入死循环 } else if(a[k]==3) { int t=a[k]; a[k]=a[j]; a[j]=t; // 交换a[k]和a[j] j--; } else {
// 对顺序表L.r[1..n]冒泡非递减排序 // 一旦待排序列有序排序过程立即停止 void BubbleSort(SqList& L) { for(int i=1; i<L.length; i++) {
}
}
Hale Waihona Puke bool changed = false; // 一趟排序中是否发生交换 for(int j=1; j<L.length-i+1; j++) if(L.r[j].key > L.r[j+1].key) { // 比较关键字，逆序则交换 L.r[0] = L.r[j]; L.r[j] = L.r[j+1]; L.r[j+1] = L.r[0]; changed = true; // 置发生交换的标志 } if(!changed) break; // 没有交换发生，表明已经有序，停止排序
2、利用图的遍历判断连通图中是否存在回路。 【解析】与图的路径相关的问题，一般采用深度优先搜索。 但是，这个题目本身似乎有些问题。 （1）如果这个连通图是无向图，只要图中有边存在，那么像 A-B-A 这样的回路必然存在， 所以这似乎已经不是个问题了。 （2） 如果这个图是一个强连通图，则必然存在经过所有顶点的一条路径，也必然存在回路， 所以也不能算是问题了。 只能认为题目中所说的是弱连通图 （即如果将有向图中的弧当成边 ， 则改图一定是连通图） 。 对于弱连通图，还要注意下面几个问题： （1）从图中某个顶点出发，可能存在遍历不到的顶点（如下图中顶点 F）。所以，即使从 某个顶点出发，遍历过程中没有发现回路，也不能断定整个图中没有回路，有必要从不同的 顶点开始遍历。 （2）也不能单纯地认为，在遍历过程中遇到已经访问过的顶点，就表明图中存在回路。比 如，假如去掉下图中的弧 EB，并且从 A 开始深度优先遍历，如果遍历序列为 ABCEFGD，那么， 在访问完 D 之后，遇到了已经访问过的顶点 E，但这并不意味着图（已删除弧 EB）中存在回 路。所以在设置访问标志的方式上要进行修改，即：访问顶点时设置访问标志，当从该顶点 遍历完成返回时要清除访问标志，其目的是，让设置访问标志的顶点仅出现在一条路径中， 从而保证一旦遇到访问过的顶点，必然存在回路。
E
F
G
}
} // 已遍历完v的所有邻接点，未发现回路，从顶点v返回 visited[v] = 0; // 清除访问标志 return false; // 未发现回路
// 如果从w出发，发现回路，则返回（无需继续遍历） if(existCyclePath(G, w)) return true;
【补充】 往届学生问过这个题目， 参见教学网站上的另一种解答 （用邻接矩阵实现） （提示： Ctrl+单击链接，校园网内可以访问教学网站） 。 3、稀疏一元多项式。 【解析】本题以稀疏一元多项式为应用背景，考查数据结构、存储结构设计相关知识。多项 式可以看作是线性结构， 可以用线性表来表示， 由于稀疏多项式的特殊性， 考虑空间利用率， 可以选择链表作为存储结构。多项式的运算通常都是按指数大小顺序处理，所以，具体地， 可以采用按指数排序的单链表作为存储结构。链表中每个结点表示一元多项式中的一个项， 每一项都要包含系数和指数， 从而可以用一个链表表示一个一元多项式。 其存储结构定义应 包括结点（项）的定义和链表（多项式）的定义。 当然，完全可以参考课本第二章给出的同样的例子加以解答，但是，本试题绝不是要求背诵 课本内容，应根据所学知识独立地进行设计，课本上的内容仅仅当做一种模糊的提示。 另外，考试过程中时间紧张，对于各种符号和名称不必过于纠结，只要简化地给出即可。比 如：系数 coefficient，指数 exponent，多项式 polynomial，都可以简化给出，系数用 coeff 或 c，指数用 exp 或 e，多项式用 Poly 甚至 P，都不是什么大问题。 【参考解答】一元多项式可以看作现行结构，故采用线性表作为数据结构。由于稀疏一元多 项式中存在很多零元，所以适合采用链表作为存储结构，以提高空间利用率。一元多项式的 运算通常按照各项指数的大小顺序处理， 所以， 可以采用按指数升序排列的单链表作为存储 结构。定义如下：
}
}
}
k++;
【补充】 对于数据结构， 最简单就是用数组表示线性表。 如果非要复杂一点， 可以用顺序表。 【参考解答】设红、白、蓝分别用 1、2、3 表示。序列为线性结构，故采用线性表作为数据 结构，针对该问题特点选择顺序表作为线性表的存储结构。算法如下：
// 顺序表最大容量 const int MAX_SIZE = 1024; // 顺序表结构 typedef struct { int elem[MAX_SIZE]; int length; } SqList; // 将 n 个红、白、蓝元素（分别用1、2、3表示）组成的序列 // 按照红、白、蓝的顺序排列 void Arrange(SqList &L) { int i = 0; // 从前向后保存红色（1）元素 int j = L.length-1; // 从后向前保存蓝色（3）元素 int k = 1; while(k<=j) { if(L.elem[k]==1) { int t=L.elem[k]; L.elem[k]=L.elem[i]; L.elem[i]=t; // 交换[k]和[i] i++; k++; // 注意：这里k++防止i==k时陷入死循环 } else if(L.elem[k]==3) { int t=L.elem[k]; L.elem[k]=L.elem[j]; L.elem[j]=t; // 交换[k]和[j] j--; } else { k++; } } }
// 一元多项式的项，作为链表数据元素 typedef struct ItemType { double coef; // 系数 int exp; // 指数 } ItemType, ElemType; // 单链表 typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; // 一元多项式类型 typedef LinkList Polynomial;
2012 年算法设计 1、调整序列，负整数在前，正整数在后。 【解析】算法思路非常类似快速排序一趟划分算法，只不过，为了区分正整数和负整数，应 该让序列中的元素与 0 比较。 另外，题目对时间复杂度和空间复杂度都有要求。因此，不能采用一般的排序算法。 【参考解答】
// 调整顺序表L中的元素，使负整数在前，正整数在后
2011 年算法设计 1、冒泡排序。 【解析】本题考查冒泡排序，采用顺序表作为存储结构。要做到一旦发现待排记录有序就立 即停止排序，只要在每趟排序过程中检查是否有交换发生，如果某一趟排序结束后，没有发 生交换，则可以断定待排记录已经有序，则可以结束排序。 本题难度不大，但要特别注意以下细节： （1）待排记录用顺序表存储，且 r[0]空闲，这意味 着待排序列为 L.r[1..n]（n 代表 L.length） ； （2）题目给定了数据结构，在算法中必须使用该 数据结构。如比较记录的大小时，应该比较记录的关键字 key。 （3）排序过程中，不要造成 下标越界。 如： i 从 1 循环到 n-1， 表示最多需要 n-1 趟排序， 内层循环中 j 要从 1 循环到 n-i， 相当于 j<n-i+1，才能保证不会出现下标越界。可以用边界值验证法加以验证。如当 i=1 时， 内循环中 j 取 1 到 n-1，这样才能保证下面 j+1 最大为 n，从而保证 r[j+1]不会下标越界。 【参考解答】
2. 荷兰国旗问题。 【解析】思路类似快速排序的一趟划分算法。要想按红白蓝顺序排列，只要扫描整个序列， 遇到红色交换到前面，遇到蓝色交换到后面，设置两个变量，分别记录前面和后面两个子序 列的位置。 （也可以想象在序列的前后两端各有一个栈。 ） [i,k] =323132311332= [j] [k]==3 交换[k][j], j-[i,k]= 22313231133= [j] 3 [k]==2 跳过：k++ [i] =2 [k]= 2313231133= [j] 3 [k]==2 跳过：k++ [i] =22 [k]=313231133= [j]3 [k]==3 交换[k][j], j-[i] =22 [k]=31323113= [j] 33 [k]==3 交换[k][j], j-[i] =22 [k]=3132311= [j]333 [k]==3 交换[k][j], j-[i] =22 [k]=113231= [j]3333 [k]==1 交换[k][i], i++, k++ (这里 k++防止 i==k 时死循环) 1[i] =22 [k]=13231= [j]3333 [k]==1 交换[k][i], i++, k++ 11[i] =22 [k]=3231= [j]3333 [k]==3 交换[k][j], j-11[i] =22 [k]=123= [j]33333 [k]==1 交换[k][i], i++, k++ 111[i] =2 2[k]=23= [j]33333 [k]==2 跳过：k++ 111[i] =222[k]=3= [j]33333 [k]==3 交换[k][j], j-- (k==j 时还要继续循环) 111[i] =222= [j] [k]=333333 k>j 结束 【参考解答】设红、白、蓝分别用 1、2、3 表示。序列为线性结构，故采用线性表作为数据 结构，针对该问题选择 n 个元素的数组作为线性表的存储结构。算法如下：
