数据结构第二章作业及答案.ppt

1,数据结构第二章作业及答案一、选择题1下述哪一条是顺序存储结构的优点？A存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有n个（）的有限序列（n0）。A表元素B字符C数据元素D数据项4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A顺序表B双向链表C带头结点的双向循环链表D循环链表,2,5利用双向链表作线性表的存储结构的优点是什么？便于进行插入和删除的操作B.提高按关系查找数据元素的速度C.节省空间D.便于销毁结构释放空间6链表不具有的特点是：A插入、删除不需要移动元素B不必事先估计存储空间C可随机访问任一元素D所需空间与线性长度成正比7非空的循环链表head的尾结点指针p满足：Ap=headBp-next=NILLCp=NILLDp-next=head8.对于一个头指针为head的带头结点的线性链表，判定该表为空表的条件是：Ahead=NULLBhead!=NULLCheadnext=headDheadnext=NULL,3,9设线性链表中结点的结构为（data,next）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？s-next=p-next;p-next=s;B.q-next=s;s-next=p;p-next=s-next;s-next=p;p-next=s;s-next=q;10在线性链表指针为p的结点之后插入指针为s的结点，正确的操作是：Ap-next=s;s-next=p-next;Bs-next=p-next;p-next=s;Cp-next=s;p-next=s-next;Dp-next=s-next;p-next=s;请将选择题答案写在下面括号内：1【】2【】3【】4【】5【】6【】7【】8【】9【】10【】,4,二、顺序表和线性链表的特点分别是什么?三、请写出顺序表的类型定义SqList,解释各变量和常量的含义,并给出初始化操作、插入操作和删除操作的算法的类C语言描述。(其中插入和删除操作还要求给出算法操作步骤的文字描述。)(1)StatusInitList_Sq(SqList/线性表存储空间基址intlength;/当前线性表长度intlistsize;/当前分配的线性表存储空间大小/(以sizeof(ElemType)为单位)SqList;其中：SqList：类型名，SqList类型的变量是结构变量，它的三个域分别是：*elem：存放线性表元素的一维数组基址；其存储空间在初始化操作(建空表)时动态分配；length：存放线性表的表长；listsize：用于存放当前分配(存放线性表元素)的存储空间的大小。,8,解答(续):(1)初始化操作算法(算法2.3)：StatusInitList_Sq(SqList/InitList_Sq,9,解答(续):(2)插入操作基本步骤:1)若i不合法或表L已满，算法结束并返回ERROR；否则转2)2)将第i个元素及之后的所有元素均后移一个位置3)将新元素写入空出的位置；4)表长+1,10,解答(续):插入操作算法(算法2.4)：StatusListInsert_Sq(SqList/ListInsert_Sq,11,解答(续):(3)删除算法的主要步骤:1)若i不合法或表L空，算法结束，并返回ERROR；否则转2）2)将第i个元素赋值给e;3)将第i个元素之后的元素(不包括第i个元素)依次向前移动一个位置;4)表长-1,12,解答(续):删除操作算法(算法2.5)：StatusListDelete_Sq(SqList/ListDelete_Sq,13,解答(续):四、线性链表的结点类型定义及指向结点的指针类型定义typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;逆序创建带头结点的单链表的算法操作如下：(1)建立一个“空表”；(2)输入数据元素an，建立结点并插入；(3)输入数据元素an-1，建立结点并插入；(4)依次类推，直至输入a1为止。,14,解答(续):逆序创建带头结点的单链表的算法的类C语言描述如下：voidCreateList_L(LinkListL,intn)/逆序输入n个数据元素，建立带头结点的单链表L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(/插入/CreateList_L,15,解答(续):五、解：(此处图略)(1)sprior=qprior;(2)qpriornext=s;(3)snext=q;(4)qprior=s;六、解：(此处图略)(1)p=qprior;(2)ppriornext=q;(3)qprior=pprior;(4)free(p);,