(一)数据结构部分
当大街上遍地都是鲜血的时候，就是你最好的投资时机。
（一）数据结构部分
1.已知W=组数
且表示的邻接矩阵如下图所示
如下要求（1）画出有向图（2）画出邻接表
解：
1 2 3 4 5 6 7
1 0 1 1 1 0 0 0
2 0 0 1 0 0 1 0
3 0 0 0 1 1 1 0
4 0 0 0 0 1 0 0
5 0 0 0 0 0 1 1
6 1 1 0 0 0 0 1
7 0 0 0 0 0 0 0
aij=1代表Vi到Vj有一条有向边
有向图：
邻接表：
1 2 3 4
2 3 6
3 4 5 6
4 5
5 6 7
6 1 2 7
7
2. 3阶B-树如图所示
分别画出插入关键字20后和150后得到的B-树
B-树 结点树最小不能少于M/2（取整）
最大不到大于M
M为阶
插入20后 B-树为
3.给出一组关键字T=（12
2
16
30
8
28
4
10
20
6
18）写出用下列算法从小到大排序时第一趟结束时的顺序
（1）希尔排序（第一趟排序的增量为5）
（2）快速排序（轴元素为5）
解：
※希尔排序(增量为5表示位置间5为一组）
（12
2
10
20
6
18
4
16
30
8
28）
※快速排序（从后面找大的
从前面找小的）
（6
2
10
4
8
12
28
30
20
16
18）
4.画出和下列已知序列对应 的树T：树的先根次序
序访问序列为GFKDAIEBCHJ;后根次序访问序列为DIAEKFCJHBG
※先根序列：根→δ树→δ树
后根序列：α树→δ树→根
判断题
1.在具有头结点的链式存储结构中
头指针指向链表中的第一个数据结点（X）
2.在单链表中
要访问某个环节
只要知道该结点的指针即可
因此单链表是一种随机存取结构（X）
3.广义表是线性表的推广
是一类线性数据结构（X）
4.广义表中原子个数为广义表的长度（X）
5.二叉树中用树的前序遍历和中序遍历可以到处树的后序遍历（√）
6.哈夫曼树是带权路径长度最短的树
路径上树值较大的结点离根较近（√）
7.若连通图上各边权值均不相同
则该图的最小生成树是唯一的（√）
8.邻接表只能用于存储有向图
而邻接矩阵则可存储有向图和无向图（X）
9.AVL树是一棵二叉树
该树上任一结点的平衡因δ绝对值不大于1（√）
10.内排序的快速排序方法
在任何情况下均可得到最快的排序效果（X）
三、
设有一组关键字{9
01
23
14
55
20
84
27}
采用哈希函数：H（key）=keyMOD7
表长为10
用开
放地址法的二次探测散列方法1+i=（H(key)+di)MOD10(di=1平方
2平方
3平方...)解决冲突
要求：对该关键字序列结构哈希表
指出有哪些同义词
并计算查找成功的平均查找长度
※ki≠kj但H(ki）=H（kj）则ki和kj为同义词
同义词：9和23
14和84
20
55和27
查找成功时的平均查找长度为：
ASL=(1+1+1+2+3+4+1+2)/8=1.875
四、证明题：
1.有一非空树
其度为5
已知度为i的节点数为i个
其中1<=i<=5
证明其终端节点个数为41.
※证明：
若n为节点总数
ni为度i的节点数则
n=n0+n1+n2+n3+n4+n5 ①
令B为分支数目
B=n-1 ②
所有的分支是由度为1
2
3
4
5的节点所提供
故B=n-1=n1+2n2+3n3+4n4+5n5 ③
由①②③知
n0+n1+n2+n3+n4+n5-1=n1+2n2+3n3+4n4+5n5
n0=n2+2n3+3n4+4n5+1
∵n2=2
n3=3
n4=4
n4=5
∴n0=2+6+12+20+1=41
假设称正读和反读都相同的字符序列为"回文"
例如"abcba"是回文
"abcde"和"ababab"则不是回文
试写一个算法判别读入的一个"@"为结束符的字符序列是否为回文
※int palindrome_Test( )
{Initstack(s);InitQueue(Q);
while （c=getchar（）！="@"）
{push（s
c）; EnQueue(Q
c);
}
while(!stack Empty(s))
{pop(s
a);DeQueue(Q
b));
if(a!=b)return ERROR;
}
erturn OK;
}//palindiome-Test
五、试编写一个高效算法
查找未排序文件A(1...n)中得第k个最小的元素
注：第k个最小的元素；若M是A（1）
A(2)...A(n)中的第k个最小元素
则A(1)
A(2)
...A(n)中至少有k个元素小于等于M
并且最多有k-1个元素小于M
思想：调用一个快速排序以后
有p-1（p：轴元素位置）个元素小于等于轴元素
且n-p个元素大于等于轴元素
若k小于p则第k个最小元素在A(1
...p-1）中；若k=p
则A(p)就是第k个最小元素
若k>p
则A(1
..n）中的第k个最小元素就是A(p+1...n)中的第（k-p）个最小元素
PROCEDURE qpass（R）;listtype；lqw
hig：imteger；var div integer)
Begin
i=low;j=hig;x=R[I];
while t
R[i];=R[j];
while (i
END;
Procedure search_k(ls;listtype
l
h
k;iinbeger;var key;integer)
Begin
if L=h then key:=ls(l)
Else[qpass(ls
l
h
p)
if k<=p-1 then search-k(ls
l
p-1
k
key)
Else if k=p then key=ls(p)
Else search-k(ls
p+1
h
k-p
key)]
End
（二）软件工程部分
一. 判别下面描述是否正确
1. 软件就是所谓的程序.
2. 结构化分析与设计是软件工程学的一个重要思想.
3. 自顶向下逐步细化是结构化分析与设计的核心思想.
4. 信息隐蔽是指模块内部的数据与过程对其他模块隐藏起来.
5. 模块的耦合越弱
表明模块的独立性越差.
6. 模块的控制域与作用域是一样的.
7. 编码是软件开发时期最重要的阶段.
8. 软件测试是为了证明程
序的正确性.
9. 条件组合覆盖一定包含判定覆盖.
10.软件维护是可有可无的.
二. 选择填空
1．制定进度计划的常用工具有 （ ）
A PAD图 B Gantt图 C 结构图 D N_S图
2．在软件开发中
（ ）是指对将要开发的系统的开发成本进行估算
然后与可能取得的效益进行比较和权衡
A .成本-效益分析 B .可行性分析
C. 结构化分析 D. 软件需求分析
3．为了提高软件的可维护性或可靠性而对软件进行的修改称为（ ）
A. 校正性维护 B. 适应性维护
C. 完善性维护 D. 预防性维护
4．软件测试的目的是（ ）
A. 为了表明程序没有错误 B. 为了说明程序能正确地执行
C. 为了发现程序中的错误 D 为了评价程序的质量
5．在软件设计中详细描述处理过程常用的三种工具是（ ）
A. SA
SD
SP B .程序流程图
IPO
PAD
C. SA
SC
SD D. 图形
表格
语言
6．在下列四种模块的耦合性中
信息隐蔽性能最好的是（ ）
A. 控制耦合 B. 内容耦合
C. 标记耦合 D .数据耦合
7．结构化程序设计的核心是要求程序只由顺序、循环和（ ）三种结构组成
A 选择 B 单入口 C 单出口 D 有规则GOTO
8．ＲＵＭＢＡＮＧＨ等人提出的对象模型技术ＯＭＴ把分析时收集的信息构造在三类模型中
即对象模型、动态模型和（ ）
Ａ 信息模型 Ｂ 控制模型
Ｃ 功能模型 Ｄ 行为模型
9．动态模型的描述工具是（ ）
A 对象图 B 结构图 C 流程图 D 状态图
10．在结构测试用例设计中
有语句覆盖、条件覆盖、判定覆盖（即分支覆盖）、路径覆盖等
其中（ ） 是最强的覆盖准则
Ａ 语句覆盖 Ｂ 条件覆盖 Ｃ 判定覆盖 Ｄ 路径覆盖
三.
1．根据问题陈述
会画判定表
2．软件过程成熟度和软件维护相关概念
3．根据给定的程序描述
能写出条件组合覆盖测试用例：