【计算机类职业资格】数据结构与算法练习试卷2-1及答案解析.doc

1、数据结构与算法练习试卷 2-1 及答案解析(总分：24.00，做题时间：90 分钟)一、填空题(总题数：12，分数：24.00)1.填空题（每空）请将每一个空的正确答案写在答题卡上。（分数：2.00）_2.数据结构包括的三个方面的内容是：数据的 1，数据的存储结构，数据的运算。（分数：2.00）填空项 1:_3.按后根次序遍历树或树林，等同于按 1 次序周游对应的二叉树。（分数：2.00）填空项 1:_4.在顺序表(8，11，15，19，25，26，30，33，42，48，50)中，用二分法查找关键码值 20，需做的关键码比较次数为 1。（分数：2.00）填空项 1:_5.设有关键码序列(17

2、8，3，25，16，1，13，19，18，4，6，24)，要按关键码值递增的次序排序，用初始增量为 4 的希尔排序法，一趟扫描后的结果是 1。（分数：2.00）填空项 1:_6.如果对于给定的一组权值，所构造出的二叉树的带权路径长度最小，则该树称为 1。（分数：2.00）填空项 1:_7.设 F 是由 T1、T2 和 T3 三棵树组成的森林，与 F 对应的二叉树为 B，已知 T1、T2 和 T3 的节点个数分别n1、n2 和 n3，则二叉树 B 的根节点的左子树和右子树中的节点个数分别为 n2+n1-1 和 1。（分数：2.00）填空项 1:_8.设有两个散列函数 H1(K)=K mod 1

3、3 和 H2(K)=K mod 11+1，散列表为了0.12，用双重散列法(又称二次散列法)解决冲突。函数 H1 用来计算散列地址，当发生冲突时，H2 作为计算下一个探测地址的地址增量。假定某一时刻散列表 T 的状态为：下一个被插入的关键码为 42，其插入位置是 1。 （分数：2.00）填空项 1:_9.程序 for i:=1 to n do for j:=1 to n do Ai, j:=0; 的算法复杂性为 1（分数：2.00）填空项 1:_10.二叉树的先序遍历序列等同于该二叉树所对应的树林的 1 遍历序列。（分数：2.00）填空项 1:_11.设散列表为 Table0.m-1，初始状态

4、为空，用线性探测法解决冲突，将 n(nm)个不同的关键码插入散列表中，如果这 n 个关键码的散列地址都相同，则探测的次数是 1。（分数：2.00）填空项 1:_12.某链表如下所示。 （分数：2.00）填空项 1:_数据结构与算法练习试卷 2-1 答案解析(总分：24.00，做题时间：90 分钟)一、填空题(总题数：12，分数：24.00)1.填空题（每空）请将每一个空的正确答案写在答题卡上。（分数：2.00）_解析：2.数据结构包括的三个方面的内容是：数据的 1，数据的存储结构，数据的运算。（分数：2.00）填空项 1:_ （正确答案：正确答案：逻辑结构）解析：3.按后根次序遍历树或树林，等

5、同于按 1 次序周游对应的二叉树。（分数：2.00）填空项 1:_ （正确答案：正确答案：对称序）解析：4.在顺序表(8，11，15，19，25，26，30，33，42，48，50)中，用二分法查找关键码值 20，需做的关键码比较次数为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：4）解析：5.设有关键码序列(17，8，3，25，16，1，13，19，18，4，6，24)，要按关键码值递增的次序排序，用初始增量为 4 的希尔排序法，一趟扫描后的结果是 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：16，1，3，19，17，4，6，24，18，8，13，25）解析：

6、6.如果对于给定的一组权值，所构造出的二叉树的带权路径长度最小，则该树称为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：最优二叉树/霍夫曼树）解析：7.设 F 是由 T1、T2 和 T3 三棵树组成的森林，与 F 对应的二叉树为 B，已知 T1、T2 和 T3 的节点个数分别n1、n2 和 n3，则二叉树 B 的根节点的左子树和右子树中的节点个数分别为 n2+n1-1 和 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：n3）解析：8.设有两个散列函数 H1(K)=K mod 13 和 H2(K)=K mod 11+1，散列表为了0.12，用双重散列法(又称二次散列

7、法)解决冲突。函数 H1 用来计算散列地址，当发生冲突时，H2 作为计算下一个探测地址的地址增量。假定某一时刻散列表 T 的状态为：下一个被插入的关键码为 42，其插入位置是 1。 （分数：2.00）填空项 1:_ （正确答案：正确答案：0）解析：9.程序 for i:=1 to n do for j:=1 to n do Ai, j:=0; 的算法复杂性为 1（分数：2.00）填空项 1:_ （正确答案：正确答案：O(n 2 )）解析：10.二叉树的先序遍历序列等同于该二叉树所对应的树林的 1 遍历序列。（分数：2.00）填空项 1:_ （正确答案：正确答案：先根）解析：11.设散列表为 Table0.m-1，初始状态为空，用线性探测法解决冲突，将 n(nm)个不同的关键码插入散列表中，如果这 n 个关键码的散列地址都相同，则探测的次数是 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：n(n+1)/2）解析：12.某链表如下所示。 （分数：2.00）填空项 1:_ （正确答案：正确答案：p.link:=p1.link.link）解析：