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

《数据结构第二章作业及答案.ppt》由会员分享，可在线阅读，更多相关《数据结构第二章作业及答案.ppt（15页珍藏版）》请在装配图网上搜索。

1、1,数据结构第二章作业及答案 一 、选择题 1下述哪一条是顺序存储结构的优点？ A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示 2下面关于线性表的叙述中，错误的是哪一个？ A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 3线性表是具有n个（ ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

2、A顺序表 B双向链表 C带头结点的双向循环链表 D循环链表,2,5利用双向链表作线性表的存储结构的优点是什么？ 便于进行插入和删除的操作 B. 提高按关系查找数据元素的速度 C. 节省空间 D. 便于销毁结构释放空间 6链表不具有的特点是： A插入、删除不需要移动元素 B不必事先估计存储空间 C可随机访问任一元素 D所需空间与线性长度成正比 7非空的循环链表head的尾结点指针p满足： Ap =head Bp-next=NILL Cp=NILL D p-next= head 8. 对于一个头指针为head的带头结点的线性链表，判定该表为空表的条件是： Ahead=NULL Bhead!=NUL

3、L Cheadnext=head Dheadnext=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; B s-next=

4、p-next; p-next=s; Cp-next=s; p-next=s-next; D p-next=s-next; p-next=s; 请将选择题答案写在下面括号内： 1【 】2【 】3【 】4【 】 5【 】 6【 】7【 】8【 】9【 】10【 】,4,二、顺序表和线性链表的特点分别是什么? 三、请写出顺序表的类型定义SqList, 解释各变量和常量的含义,并给出初始化操作、插入操作和删除操作的算法的类C语言描述。(其中插入和删除操作还要求给出算法操作步骤的文字描述。) (1) Status InitList_Sq(SqList /线性表存储空间基址 int length; /当前

5、线性表长度 int listsize; /当前分配的线性表存储空间大小 / (以sizeof(ElemType)为单位)SqList; 其中： SqList ：类型名， SqList类型的变量是结构变量，它的三个域分别是： *elem：存放线性表元素的一维数组基址；其存储空间在初始化操作 (建空表)时动态分配； length：存放线性表的表长； listsize：用于存放当前分配 (存放线性表元素)的存储空间的大小。,8,解答(续): (1) 初始化操作算法(算法2.3 )： Status InitList_Sq(SqList /InitList_Sq,9,解答(续): (2) 插入操作基本步

6、骤: 1) 若i不合法或表L已满，算法结束并返回 ERROR；否则转2) 2) 将第i个元素及之后的所有元素均后移一个位置 3) 将新元素写入空出的位置； 4) 表长+1,10,解答(续): 插入操作算法(算法2.4 )： Status ListInsert_Sq(SqList /ListInsert_Sq,11,解答(续): (3) 删除算法的主要步骤: 1) 若i 不合法或表L空，算法结束，并返回ERROR；否则转2） 2) 将第i个元素赋值给e; 3) 将第i个元素之后的元素(不包括第i个元素)依次向前移动一个位置; 4) 表长-1,12,解答(续): 删除操作算法(算法2.5 )： S

7、tatus ListDelete_Sq(SqList /ListDelete_Sq,13,解答(续): 四、线性链表的结点类型定义及指向结点的指针类型定义 typedef struct LNode ElemType data; struct LNode *next;LNode, *LinkList; 逆序创建带头结点的单链表的算法操作如下： (1)建立一个“空表”； (2)输入数据元素an， 建立结点并插入； (3)输入数据元素an-1， 建立结点并插入； (4)依次类推，直至输入a1为止。,14,解答(续): 逆序创建带头结点的单链表的算法的类C语言描述如下： void CreateList

8、_L(LinkList L, int n) / 逆序输入 n 个数据元素，建立带头结点的单链表 L = (LinkList) malloc (sizeof (LNode); L-next = NULL; / 先建立一个带头结点的单链表 for (i = n; i 0; -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);,