算法与数据结构一----大题答案
21题：简述折半查找的思想和过程
折半查找的基本思想是：对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。
折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。
22题：请用类C 语言描述链串的类型定义。
typedefstruct node
{
elemtype data;
elemtype code;
struct node *next;
}Lnode;
23题：顺序查找事件为O （n) ，二分查找事件为O （l
不同的查找方法使用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找方法效率高，而且也不是在所有情况下都可以采用。
24题：对于给定的一组键值：83，40
归并排序
关键字
83 40 63 13 84 35 96 57 39 79 61 15
第一趟排序后
[40 83] [13 63] [35 84] [57 96] [39 79] [15 61] 第二趟排序后
[13 40 63 83] [35 57 84 96] [15 39 61 79]
第三趟排序后
[13 35 40 57 63 83 84 96] [15 39 61 79] 第四趟排序后
13 15 35 39 40 57 61 63 79 83 84 96
快速排序
关键字
83 40 63 13 84 35 96 57 39 79 61 15
第一趟排序后
[15 40 63 13 61 35 79 57 39] 83 [96 84] 第二趟排序后
[13] 15 [63 40 61 35 79 57 39] 83 84 [96]
第三趟排序后
13 15 [39 40 61 35 57] 63 [79] 83 84 96
第四趟排序后
13 15 [35] 39 [61 40 57] 63 79 83 84 96
第五趟排序后
13 15 35 39 [57 40] 61 63 79 83 84 96
第六趟排序后
13 15 35 39 40 [57] 61 63 79 83 84 96
第七趟排序后
13 15 35 39 40 57 61 63 79 83 84 96
算法与数据结构二----大题答案
21题：假设用于通信的电
哈夫曼编码
根据上图可得编码表：
a:1001
b:01
c:10111
d:1010
e:11
f:10110
g:00
h:1000
22题：设有编码为1234
1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 23题：简述二次探测法解决
二次探查采用的形式如下：
h(k,i)=(h’(k)+c1i+c2i)modm
其中h ’是一个辅助散列函数，c1和c2为辅助常数，i=0,1,…m-1。处事的探查位置为T[h’(k)],后续的探查位置要在此基础上加上一个偏移量，该偏移量是以二次的方式依赖于探查号i 的。如果两个关键字的初始探查位置是相同的，那么他们的后续二次探查的序列也是相同的。这种性质会导致一种程度较轻的群集现象，成为二次群集。简单地说就是遇到冲突, 就以n^2,n=1,2,...的序列探查, 如果找到首个没有冲突的位置, 就插入, 否则继续探查。
24题：已知数据序列12,5,9
折半查找的基本思想是：对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。
数字电路一----大题答案
21题：分析下列时序电路，写出驱动方程
22题：将函数化简为最简与或表达式：
F 2( A,B,C,D）=∑m (0,1,2,4,5,9)+∑
d (7,8,10,11,12,13)
=【∑m (0,1,4,5,9)+∑d(8,12,13)】+【∑m (0,2)+∑d (8,10)】
=C’+B’D’
23题用最少的D 触发器和与非门：
算法与数据结构一----大题答案
21题：简述折半查找的思想和过程
折半查找的基本思想是：对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。
折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。
22题：请用类C 语言描述链串的类型定义。
typedefstruct node
{
elemtype data;
elemtype code;
struct node *next;
}Lnode;
23题：顺序查找事件为O （n) ，二分查找事件为O （l
不同的查找方法使用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找方法效率高，而且也不是在所有情况下都可以采用。
24题：对于给定的一组键值：83，40
归并排序
关键字
83 40 63 13 84 35 96 57 39 79 61 15
第一趟排序后
[40 83] [13 63] [35 84] [57 96] [39 79] [15 61] 第二趟排序后
[13 40 63 83] [35 57 84 96] [15 39 61 79]
第三趟排序后
[13 35 40 57 63 83 84 96] [15 39 61 79] 第四趟排序后
13 15 35 39 40 57 61 63 79 83 84 96
快速排序
关键字
83 40 63 13 84 35 96 57 39 79 61 15
第一趟排序后
[15 40 63 13 61 35 79 57 39] 83 [96 84] 第二趟排序后
[13] 15 [63 40 61 35 79 57 39] 83 84 [96]
第三趟排序后
13 15 [39 40 61 35 57] 63 [79] 83 84 96
第四趟排序后
13 15 [35] 39 [61 40 57] 63 79 83 84 96
第五趟排序后
13 15 35 39 [57 40] 61 63 79 83 84 96
第六趟排序后
13 15 35 39 40 [57] 61 63 79 83 84 96
第七趟排序后
13 15 35 39 40 57 61 63 79 83 84 96
算法与数据结构二----大题答案
21题：假设用于通信的电
哈夫曼编码
根据上图可得编码表：
a:1001
b:01
c:10111
d:1010
e:11
f:10110
g:00
h:1000
22题：设有编码为1234
1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 23题：简述二次探测法解决
二次探查采用的形式如下：
h(k,i)=(h’(k)+c1i+c2i)modm
其中h ’是一个辅助散列函数，c1和c2为辅助常数，i=0,1,…m-1。处事的探查位置为T[h’(k)],后续的探查位置要在此基础上加上一个偏移量，该偏移量是以二次的方式依赖于探查号i 的。如果两个关键字的初始探查位置是相同的，那么他们的后续二次探查的序列也是相同的。这种性质会导致一种程度较轻的群集现象，成为二次群集。简单地说就是遇到冲突, 就以n^2,n=1,2,...的序列探查, 如果找到首个没有冲突的位置, 就插入, 否则继续探查。
24题：已知数据序列12,5,9
折半查找的基本思想是：对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到查找范围为空而查不到为止。折半查找的过程实际上死先确定待查找元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。
数字电路一----大题答案
21题：分析下列时序电路，写出驱动方程
22题：将函数化简为最简与或表达式：
F 2( A,B,C,D）=∑m (0,1,2,4,5,9)+∑
d (7,8,10,11,12,13)
=【∑m (0,1,4,5,9)+∑d(8,12,13)】+【∑m (0,2)+∑d (8,10)】
=C’+B’D’
23题用最少的D 触发器和与非门：