要求：说明算法的基本思想，主要变量和数据结构类型。可用PASCAL或C语言。 ~MQm_Rp!~
一. 判断题（ 10分）
^ J m Nv,}c 1. 设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次时，朴素的匹配（即子串定位函数）算法所花的时间可能更少。3X*r6wT A]'ce
2. 后序线索二叉树是不完善的，要对它进行遍历，还要使用栈。
}(@#n(Q vs 3. 采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。
Ud KX p"W-_.UZ 4. 插入和删除操作是数据结构中最基本的两种操作，所以这 N RQS l-F
两种操作在数组中也经常使用。 S}%Js7O{
5. 文件是记录的集合，每个记录由一个或多个数据项组成，#Vw ja)j-j3f-k7~
因而一个文件可看作由多个记录组成的数据结构。
y^ZG(b-D.KQ?*D 6. 堆排序所须的时间与待排序的记录个数无关。:B$l p rDq~~
7. 磁盘的优点是容量比磁带大。
u X&D.d)sCJ^ j,k 8. 用邻接矩阵A表示图，判定任意两顶点V1和V2之间是否
S(l){7Fc"X+bh 有长度为m的路径相连，只要检查Am的第I行，第j列
#]7JSp/B~$b 的元素是否为0即可。V"DC%P e\$vZ
-jUIoK A5]'f 9. 虽然信息项序列的顺序不一样，但依次生成的二叉排序树
&Bf;J8}|{/y{W 却是一样的。
/iI})UB L 10. 当待排序的元素很大时，为了交换元素的位置，移动元素
j(}^v&U 要占用较多的时间，这是影响时间复杂度的主要因素。
aB B R^'x \;z } ~|2gQ 二. 填空题（20分） TU-A F7q!\
1. 在磁带上的顺序文件中插入新的记录时，必须（ ）。
5V A&Z1z*n[JY3MK 2. 对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为（ ），利用Kruskal算法生成最小代价生成树其时间复杂度为（ ）。
0Ktw D1fhj 3. 哈夫曼树是（ ）。%d An5LO {%^l L
4. 所需读写的扇区旋转到磁头下方的所需时间称为（ ）。;OD@,I%P*k6uy&~5g%D;p7\
5. 快速排序在（ ）的情况下最易发挥其长处。\^,s \3i(C v w
6. 索引顺序文件是最常用的文件组职之一，通常用（ ）结构来组织索引。`3gl!y6}7Im
7. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用（ ）查找方法。)Aa`7Y Y&|1U{'{
8. 当广义表中的每个元素都是原子时，广义表便成了（ ）。
A|(X[v f'[W 9. 有向图G可拓扑排序的判别条件是（ ）。
jL+n5BZ ?L8C7? 三. 选择题 （18分）z ]C C9\h^
1. 某而茶树T有n各界点，设按某种顺序对T中的每个结点进行编号，编号为1，2，… ，n，且有如下性质：T重任一节点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按（ ）编号的。vWVo @[;uD
A． 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列
7U:{#v5db0O+{`/K D. 层次顺序
)f@/K8V r&h 2. 如果把某作业工程表示成网络的话, 则如图1所示,其中各箭头上的数字表示所需天数。 （1）事件5的最早完成时间是（ ）天。（2）事件4的最迟开始时间是（ ）天。（3）关键路径是（ ）。
g'u'W9{d"k1}9{+q A. 15 B. 19 C. 23 D. 27 E. 30 F. 32 G. 34
9^7T.cB3Bt&OC H. 125610 I. 147910
&`#AOzTk1Dg J. 1478910O(T,~f%a5kwh
9s Oys I9c)k#E.M
3. 动态存储管理系统中，通常可有（ ）种不同的分配策略。3r I&X8?V
A． 1 B. 2 C. 3 D. 4 E. 50?&XK;b dh(L3f
4. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =( )。Ix#k*[.[ga |
A． （a） b. A C. a D. (b) E. b F. (A)
.`*g"SP8F4~3D^ 四. 简答题 (每题6分, 共30分)
P0r4j ?"m 1. 一棵有n(n>0)个结点的d度树, 若用多重链表表示, 树中每个结点都有d个链域, 则在表示该树的多重链表中有多少个空链域? 为什么?+N ] d\+b8T{
2. 试提出三种判断一个图是否有圈的方法.c Y.Q0p Y4w q4w{ `
3. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么? m { nO/i0Q.c0p y j
4. 对一个有t个非零元素的Am*n 矩阵, 用B[0..t][1..3]的数组来表示，其中第0行的三个元素分别为m,n,t, 从第一行开始到最后一行， 每行表示一个非零元素；第一列为矩阵元素的行号， 第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作—确定任意一个元素A[j]在B中的位置并修改其值，应如何设计算法可以使时间得到改善？GQU/q9bG A5Gf
5. 在内排序的过程中，通常需要对待排序的关键字集合进行多遍扫描。采用不同排序方法，会产生不同的中间结果。设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键字按字母序的升序重新排列，请分别给出对该序列进行冒泡排序，初始步长为4的希尔排序，二路归并排序及以第一个元素为分界元素的快速排序的第一趟扫描的结果，并给出对该序列作堆排序时初始建堆的结果。 p.n^,\_
五. 算法设计题q#Z Z)V u"S
1. 试写一个判别给定二叉树是否为二叉排序树的算法。(12分)
-K#L TzWS\"xW 2. 求图的中心电的算法。设V是有向图G的一个顶点，我们把V的偏心度定义为：max(从w到v的最短距离/w是g中所有顶点)，如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。（10分） |
收藏
点赞!
反对!