发布时间 : 星期一 文章软件技术基础总复习题及参考答案更新完毕开始阅读71408392fe4733687f21aa38
参考答案：
(1) A (2) B,E,G,D (3) 2,3 (4) E,F (5) A
8、 已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写
出直接插入排序每趟的结果。
参考答案：
插入排序的每趟的结果 初始值健值序列 [12]
i=2 [5 i=3 [5 i=4 [5 i=5 [5 i=6 [5 i=7 [5
5 9 20 6 31 24
12] 9 20 6 31 24 9 12] 20 6 31 24 9 12 20] 6 31 24 6 9 12 20] 31 24 6 9 12 20 31] 24 6 9 12 20 24 31]
（1 分） （1 分） （1 分） （1 分） （1 分） （1 分）
9、 一棵二叉树的结点数据采用顺序存储结构，存储于数组 t 中，如下图所示，画
出该二叉树的链式存储表示形式。
参考答案：
10、 写出以下有向图邻接矩阵，并写出有向图各顶点的入度和出度。
V1 V3 V2 V4
参考答案：
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 0
V1：ID=2，OD=2 V2：ID=1，OD=1 V3：ID=1，OD=2 V4：ID=2，OD=1
11、 己知序列｛503，87，512，61，908，170，897，275，653，462｝，请给出采用
快速排序法对该序列作升序排序时的每一趟的结果。
参考答案：
采用快速排序法排序的各趟的结果如下：
初始：503，87，512，61，908，170，897，275，653，462 第 1 趟：462，87. 275，61，170. 503，897. 908，653，512 第 2 趟：170, 87, 275，61，462，503，897. 908，653，512 第 3 趟：61，87，170. 275，462，503，897，908，653，512 第 4 趟：61，87. 170, 275，462，503，897, 908. 653，512 第 5 趟：61，87, 170, 275，462, 503，897. 908. 653，512 第 6 趟：61，87, 170, 275，462, 503，897, 908, 653，512 第 7 趟：61，87，170, 275，462，503，512，653，897, 908 第 8 趟：61，87, 170, 275，462, 503，512, 653，897, 908 第 9 趟：61，87，170, 275，462, 503，512，653，897, 908 第 10 趟：61，87，170, 275，462, 503，512, 653，897, 908
12、 写出下图的邻接矩阵、邻接表及深度优先搜索和广度优先搜索路径。
参考答案：
V1 V2 V3 V4 V5
V1 V2 V3 V4 V5
0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0
V1
V2 V1 V1 V2 V3
V3
∧
V2
V4 ∧ V4 V3 V4 ∧
V5 ∧ V5 ∧
V3 V4 V5
V1 V3 V5 V1 V3 V5 V2
V4 V2 V4 深度优先搜索 广度优先搜索
13、 阅读下列程序，说明完成的功能
void exam(SeqStack S, int m) {
SeqStack T; int i； IniStack(T);
while(!Stackempty (S))
if ((i=pop(S))!=m) push(T,i); while (!Stackempty(T)) { i=pop（T）; push(S,i); } }
参考答案：
程序段的功能是将一个非空栈中值等于 m 的元素全部删除
14、 已知一个图的顶点为 A、B、C、D，其邻接矩阵的上三角元素全为 0（包括主
对 角线元素），其他元素均为 1。请画出该图，并给出其邻接表。
参考答案：
15、 设某商业集团关于商店销售商品的数据库中有三个基本表： 商店 SHOP（S#，SNAME，AREA，MGR_NAME） 其属性是商店编号，商店名称，区域名，经理姓名。 销售 SALE（S#，G#， QUANTITY） 其属性是商店编号，商品编号，销售数量。 商品 GOODS（G#，GNAME，PRICE） 其属性是商品编号，商品名称，单价。
（1）试写出下列查询的关系代数表达式、SELECT 语句表达形式； 检索销售“冰箱”的商店的编号和商店名称。 （2）试写出下列操作的 SQL 语句： 从 SALE 表中，把“开开商店”中销售单价高于 1000 元的商品的销售元组 全部
删除。
参考答案：
（1）关系代数表达式：πS#，SNAME（σGNAME='冰箱'（SHOP?SALE?GOODS））
SQL 语句如下： SELECT A.S#，SNAME