数据结构习题

第一章

1. 可以用 抽象数据类型定义一个完整的数据结构；

   抽象数据类型（ADT）= 数据对象+数据关系+基本操作集

2. 树是 非线性数据结构；

   集合结构、树形结构、图形结构都是非线性的；

   线性结构：N个数据的有序集合

3. 属于逻辑结构的是 有序表；

   有序表指关键字有序的线性表 ，可以链式也可以顺序，仅描述元素之间的关系

4. 与数据的存储结构无关的是 栈；

   数据结构三要素：存储结构（顺序存储、链接存储、索引存储、散列存储）；逻辑结构（线性表，队列，栈）；数据的运算

   循环队列是一种用顺序表表示的特殊队列

5. 数据的逻辑结构独立于其存储结构；

6. 在存储数据时不仅要存储数据的值，还要 存储数据元素之间的关系

   储存数据时无需存储操作方法，存储数据结构时才需如此，其类型隐含于数据元素之中。

7. 链式存储设计时，结点内的存储单元地址一定连续

   各个不同节点的存储空间可以不连续，但节点内的存储单元地址则必须连续；

8. 对于两种不同的数据结构，逻辑结构或物理结构不一定相同。

   例如：二叉树和二叉排序树是两种不同的数据结构，两者均可以使用二叉树的逻辑结构和物理结构，但是建立树、插入节点、删除节点等操作是不同的；

9. 举例对相同的逻辑结构，同一种运算在不同存储方式实现，其运算效率不同；

   线性表即可以用顺序存储方式、也可以用链式存储方式；

   在顺序存储方式下，插入和删除时间复杂度为O（1）；

   在链式存储方式下，插入和删除时间复杂度为O（1）；

10. 程序是一组计算机能识别和执行的指令，算法是在有限时间内的解决问题完整的准确的一系列清晰指令。程序是算法在计算机上的特定的实现，程序不一定满足有穷性，而算法是有穷的确定的可行的输入输出

11. 算法的时间复杂度是O（n**2），该算法执行时间和n方成正比；

12. ```
    void fun(int n){

     int i=1;
     while(i<n){
         i=i*2;
     }
    

    }
    //求其时间复杂度
    log2（n）；

    
        计算时间复杂度方法
    
        - 找出最深层循环内的语句
        - 找出问题规模并确定关于n的函数式
    
    13. ```
        int fun(int n){
        	if  (n<=1) return 1;
        	return n*fun(n-1);
        }
        //求其时间复杂度
        O（n）；