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)解析: