数据结构1-4章习题答案.doc

一、名词解释 抽象数据类型、数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵 二、填空 1、抽象数据类型是由一组 数据结构 和在该组数据结构上的一组 操作 所组成。 2、在定义某种数据结构时，其数据域的数据类型可分为 简单类型 和 结构体类型 两种，为增强其通用性，应将其再定义为 通用数据 类型。 3、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为 1：N 、 M：N 。 4、数据结构简单地说是指 数据 以及相互之间的 联系 。 5、算法应具备以下5个特性： 有穷性 、 正确性 、 可行性 、输入和输出。 6、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n的含义是 处理问题的样本量 。 7、对于一个以顺序实现的循环队列Q[m]，队首、队尾指针分别为f和r，其盘空的条件是 f=r ，盘满的条件是 (r+1)%m=f 。 8、循环链表的主要优点是 最大限度的利用空间 。 9、链表对于数据元素的插入和删除不需要移动结点，只需改变相关结点的 指针 域的值。 10、在一个链式栈中，若栈顶指针等于NULL，则为 空栈 。 11、主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的 返回地址 地址。 12、某算法在求解一个10阶方程组时，运算次数是500，求解一个30阶方程组时，运算次数是4500，则该算法的时间复杂度为 O（N2） 。 三、选择题 1、对一个线性表的存取操作很少，而插入和删除操作较多时应采用 B 存储结构。 A．顺序存储 B.链式存储 C. 索引存储 D.散列式存储 2、对一个线性表的随机存取操作较多时，应采用 B 存储结构。 A.静态顺序存储 B. 动态顺序存储 C. 动态链接存储 D. 静态链接存储 3、对一个顺序存储结构的栈，栈满的判断条件是（ D ） A.S.top= =-1 B.S.top= =0 C.S.top= =MaxSize D. S.top= =MaxSize-1 4、若循环队列有 n个顺序存储单元，front、rear分别为队首和队尾指针则判断队满的条件是(C) A. (front+1)%n= =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front 5、下列是顺序存储线性表排序的算法 void Sort(List L) { int i,j; ElemType x; for(i=1;iL.size;i++) { x=L.list[i]; for(j=i-1;j=0;j--) if(xL.list[j]) L.list[j+1]=L.list[j]; else break; L.list[j+1]=x; }; } 问：此算法的时间复杂性为： B A. O(n) B.(n2) C. (n*i) D. (n*j) 四、简答题 1、简述线性表的顺序存储和链接存储实现的异同。 答：（参考答案） 2、举例说明顺序存储的栈在元素出栈和进栈时栈顶指针的变化。 3、说明顺序存储的队列，在解决队满与队空的判断条件时，为什么将队首指针指向第一个元素之前？这样解决后存储容量有什么变化？ 4、举例说明栈与递归算法之间的关系。 答：（参考答案） 要点1：栈只能在栈顶操作； 要点2：递归算法是解决一个问题时，是通过解决与它具有相同解法的子问题而得到的； 要点3：在进行递归调用时，计算机系统自动建立栈，用于存储递归调用参数（下例中的）n和返回地址（下例中的r）,进栈； 要点4：当在一定条件下结束递归调用时，系统按照栈中存储的系数和返回地址逐步返回（出栈）到最初调用处，并得到最终结果。 例：求f(n)=n! f(n)=1 n=0 f(n)=n*f(n-1) n0 当 n=3时 进栈 退栈 n f(n) 0 f(0)=1 1 1 1*f(1-1) 1*1=1 2 2*f(2-1) 2*1=2 3 3*f(3-1) 3*2=6 五、算法分析