1.从逻辑结构和内存存储两个方面解释数组和链表的区别。 2.列出8个最常见的数据结构 3.下列代码的时间复杂度为____Count = 0; for (i= 1;i<=n;i*=2) for (j= 1;j<=n;j*++) Count++; 4.编写一个递归函数DigitSum (int n)，输入一个非负整数，返回组成它的数字之和。例如1245，结果12 向

1. 数组和链表都是数据结构，但它们的逻辑结构和内存存储方式不同。数组是一种顺序存储结构，它可以在一段连续的内存空间中存储相同类型的元素，元素的存储位置是连续的。数组的访问速度快，但是它的大小是固定的，插入、删除元素时需要移动其他元素，效率较低。链表是一种链式存储结构，它由若干个结点组成，每个结点包含数据和指向下一个结点的指针。链表的大小可以动态改变，插入、删除元素时只需要改变指针的指向，效率较高。但是链表的访问速度相对数组较慢，因为它的元素存储位置是不连续的。

2. 最常见的数据结构有：数组、链表、栈、队列、树、图、堆、哈希表。

3. 时间复杂度为O(n*logn)。外层循环的次数是log以2为底n的对数，内层循环的次数是n，所以总的时间复杂度为O(n*logn)。

4. 递归函数DigitSum的实现代码如下：

int DigitSum(int n) {
if (n < 10) {
return n;
} else {
return DigitSum(n / 10) + n % 10;
}
}

函数的输入为非负整数n，如果n小于10，则直接返回n。否则，将n除以10得到n的高位数字，再将n对10取余得到n的个位数字，然后将高位数字和个位数字相加，递归调用DigitSum函数，直到n小于10为止。最终的返回值就是n的各个数字之和。