1-4章习题答案.doc

一、名词解释（见教材）数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵二、填空1、数据的逻辑结构被分为_集合结构_、_线性结构_、_树形结构_、_图形结构_4种。2、数据的存储结构被分为_顺序结构_、链接结构_、索引结构_、和_散列结构_4种。3、在定义某种数据结构时，其数据域的数据类型可分为 简单类型 和 结构体类型 两种，为增强其通用性，应将其再定义为 通用数据 类型。4、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为 1：N 、 M：N 。5、数据结构简单地说是指 数据 以及相互之间的 联系 。6、算法应具备以下5个特性： 有穷性 、 正确性 、 可行性 、输入和输出。7、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n的含义是 处理问题的样本量 。 8、对于一个单链表，在表头插入结点的时间复杂度为 O(1) ，在表尾插入元素的时间复杂度为 O(n) 。9、 在表长为n的顺序表中，在等概率情况下，插入和删除一个元素平均需移动 表长的一半（即n/2 ） 个元素，具体移动元素的个数与表长（n） 和 该元素在表中的位置 有关。10、顺序表的定义如下：typedef int ElemType;struct ListElemType *list;int size;int MaxSize;其中ElemType的含义是：通用数据 类型；size的含义是：顺序表中元素的个数。11、 设单链表中指针p 指向结点A，q指针指向其后继结点。若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为p-next=q-next;。12、栈的运算规则为 后进先出 ，队列的运算规则为 先进先出 。13、一个函数调用了自身，这是 递归 调用。14、非零元素个数远远少于零元素个数的矩阵称为 稀疏矩阵 。15、顺序存储的稀疏矩阵采用三元组线性表存储，定义如下：struct Tripleint row,col;ElemType val;struct SMatrixint m,n,t;struct Triple sm11;其中row的含义是：非零元素所在的 行 ；t的含义是：非零元素的个数。三、选择题1、顺序表物理结构中的存储单元（ A ）。A. 一定是连续的 B. 一定是不连续的 C. 不一定是连续的 D. 经删除操作后不连续2、对一个线性表的存取操作很少，而插入和删除操作较多时应采用 B 数据结构。A线性表 B. 队列 C. 图 D. 树3、对一个线性表的随机存取操作较多时，应采用 B 存储结构。A.静态顺序存储 B. 动态顺序存储 C. 动态链接存储 D. 静态链接存储4、 顺序表适用于（ A ） 的场合。A. 频繁查询 B. 频繁插入与删除C. 问题规模较小 D. 问题规模较大5、 链表不具有的特点是（A ）。A 可随机访问任一元素 B. 插入、删除不需要移动元素C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比6、栈的插入和删除操作在（ A ）进行。 A栈顶 B栈底 C栈顶或栈底 D任意位置7、向一个顺序栈S（栈顶指针为top）中插入元素x时，首先要（ B ）。 AS-stackS-top=x;BS-top+;CS -top-;Dx= S-stackS-top;8、对一个顺序存储结构的栈，栈满的判断条件是（ D ） A.S.top= =-1 B.S.top= =0 C.S.top= =MaxSize D. S.top= =MaxSize-19、若循环队列有 n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队满的条件是(C) A. front = =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front10、若循环队列有 n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队空的条件是(A) A. front = =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front11、队的插入操作在（ C ）进行。A队首 B队首或队尾 C队尾 D任意位置12、下面程序段的时间复杂度为（ C ）。for (int i=0;im;i+)for (int j=0;jn;j+)aij=i*j;AO(m2) B. O(n2) CO(mn) D. O(m+n)13、一个求从1到正整数n之间所有正整数之和的单循环语句的时间复杂度为（ B ）。AO(1) B. O(n) CO (n2) D. O(n3)14、下列是顺序存储线性表排序的算法void Sort(List& L)int i,j;ElemType x;for(i=1;i=0;j-)if(xL.listj)L.listj+1=L.listj;elsebreak;L.listj+1=x;问：此算法的时间复杂性为： B A. O(n) B.(n2) C. (n*i) D. (n*j)15、下面程序段的时间复杂度为（ B ）。for (int i=1;i=n;i+) for (int j=1;j0当 n=3时进栈退栈nf(n)0f(0)=1111*f(1-1)1*1=122*f(2-1)2*1=233*f(3-1)3*2=6五、基本要求：1、写出顺序表定义2、写出链表结点定义3、写出堆栈定义4、写出循环顺序队列定义5、写出链队定义六、算法分析以下有一组算法，请根据各算法的不同，回答不同的问题。算法1：/利用数组a排序void sort (int a,int n)int i,j,k,t;for(i=0;in-1;i=i+1)j=i;for(k=i+1;kaj) j=k;t=ai;ai=aj;aj=t;问题1：此算法的时间复杂度为： O(n2) 。问题2：此算法属于： A. 。 A. 直接选择排序 B. 直接插入排序算法2：int FindList(struct List *L,ElemType x)int i;for( i=0;isize;i+)if(L-listi=x)x=L-listi;return i;return -1;问题1、算法适用的数据结构 ？问题2、算法功能？ 问题3、算法返回？ 问题4、算法有无健壮性？若有，是哪（些）语句？ 问题5、算法的关键语句是哪（些）语句？ 问题6、算法的时间复杂度大O（）？算法3：/在链表的表尾插入一个元素void InsertLastList(struct sNode* HL, ElemType x)struct sNode* newp;newp=malloc(sizeof(struct sNode);if(newp=NULL)printf(Memory allocation failare!n);exit(1);newp-data=x;newp-next=NULL;if(*HL=NULL)*HL=newp;elsestruct sNode* p=*HL;while(p-next!=NULL)p=p-next;p-next=newp;问题1、算法适用的数据结构 ？问题2、算法功能？ 问题3、算法返回？ 问题4、算法有无健壮性？若有，是哪（些）语句？ 问题5、算法的关键语句是哪（些）语句？ 问题6、算法的时间复杂度大O（）？算法4：/根据数据结构的类型的定义分析算法typedef int ElemType;struct StackSqint MaxSize;ElemType *stack;int top; void Push(struct StackSq* S, ElemType x)if( ) againMalloc(S);S-top+;S-stackS-top=x; 问题1：根据此算法定义的数据结构的类型，此算法的功能是 向顺序栈中推入一个元素 。问题2：if语句中的条件应为： B. 。 A. S.top= =S.MaxSize B. S.top= =S.MaxSize-11算法5：ElemType OutQueue(struct QueueSq *Q)if(Q-front=Q-rear)printf(Queue is empty!n);exit(1);Q-front=(Q-front+1)%Q-MaxSize;return Q-queueQ-front;问题1、算法适用的数据结构 ？问题2、算法功能？ 问题3、算法返回？ 问题4、算法有无健壮性？若有，是哪（些）语句？ 问题5、算法的关键语句是哪（些）语句？ 问题6、算法的时间复杂度大O（）？七、分析题1、有一个顺序存储的栈，最大存储空间MaxSize=5，栈顶指针top，现有A、B、C、D四个元素。要求1：写出顺序存储栈结构定义。要求2：画出 初始化状态。要求3：画出以上四个元素依次进栈后的状态。要求4：在要求3的基础上，画出三个元素出栈后，又有E、F二个元素进栈，画出队首、队尾指针位置。要求5：以下是从栈中删除元素，并将被删除的元素值由函数返回的算法，请填写算法中缺失的语句。答1：typedef char ElemType;struct StackElemType *stack ;int top;int MaxSize;答2：01234Top=-1答3：01234 ABCDtop答4：01234 56789 DE F top答5：ElemType Pop(Stack& S)if(S.top=-1)cerrStack is empty!endl;exit(1);ElemType temp=S.stackS.top;S.top-;return temp;2、有一个顺序存储的循环队列，最大存储空间为5，假设队首指针指向队首元素的前一个位置，队尾指针指向队尾元素，现队列中已有A、B、C、三个元素。要求1：已有顺序存储队列结构的定义，请填写定义中缺失的语句。要求2：填写出初始化算法语句。要求3：画出经初始化后，以上三个元素依次进队后，队首、队尾指针位置。要求4：画出以上三个元素依次出队后，元素D、E依次进队后队首、队尾指针位置。要求5：以下是向队列中插入元素的算法，在不考虑扩充空间的前提下，请填写算法中缺失的语句或语句缺失的部分。答1：Typedef int ElemType;struct Queue int MaxSize; int front , rear;ElemType *queue;答2：void InitQueue(Queue& Q) Q.front = Q.rear =0 ;答3：01234ABC frontrear答4：01234EDrear Front答5：void QInsert(Queue& Q, const ElemType& item)int k=(Q.rear+1)%QueueMaxSize;if(k= =Q.front)cerrQueue overflow!ch)switch(ch)case:case:case(:Push(a,ch);/A： 字符进栈 break;case:if(Peek(a)=)/B： 读栈顶元素进行判断 Pop(a);/ C： 栈顶元素出栈 elsereturn 0;break;case:if( D： Peek(a)= )Pop(a);elsereturn 0;break;case):i