第 2 章 作业题 已完成

本文格式为Word版，下载可任意编辑——第2章作业题已完成数据结构第2章

班级：15工19姓名：张雨学号：20230202355

一、判断题。

1、线性表的特点是每个元素都有一个前驱和一个后继。(×)2、取一维数组的第i个元素的时间同i的大小有关。(×)

3、单链表结点有两个域：数据域和指向下一个结点地址的指针域。（√）4、双链表结点有两个指针域：指向前、后结点地址的指针。（√）

5、在单链表中的第i个位置插入一个新结点，无需从头查找该结点。（×）6、线性表的链表存储方式任何状况下都优于顺序存储方式。（×）二、选择题。

1、线性表的顺序存储方式中，存储单元的地址（A）。

A、一定连续B、一定不连续C、不一定连续D、部分连续，部分不连续2、线性表的链式存储方式中，存储单元的地址（C）。

A、一定连续B、一定不连续C、不一定连续D、部分连续，部分不连续3、线性表的特点是（A）。

A、第一个元素只有一个后继元素，最终一个元素只有一个前驱元素，其它元素有且仅有前驱或后继；B、元素和元素之间是多对多关系；

C、一个元素可以有多个后继，但只有一个前驱；D、一个元素可以有多个前驱，但只有一个后继。4、数据结构在计算机内存中的表示是指(A)。

A、数据的存储结构B、数据结构C、数据的规律结构D、数据元素之间的关系5、线性表是具有n个（C）的有限序列。

A、表元素B、字符C、数据元素D、数据信息

6、若某线性表最常用的操作是存取任一指定序号的元素和在最终进行插入和删除运算，则利用（A）存储方式最节省时间。A、顺序表B、双链表C、带头结点的双循环链表D、单循环链表

7、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。

A、单链表B、单循环链表C、带尾指针的单循环链表(好插不好删)D、带头结点的双循环链表8、非空的循环单链表的头结点为head，后继域为next，其尾结点p满足（A）。A、p→next=headB、p→next=NULLC、p=NULLD、p=head

9、双向链表中有两个指针域，prior和next分别指向前趋及后继。完成在双循环链表结点p之后插入s的操作是（D）。A、p→next=s;s→prior=p;p→next→prior=s;s→next=p→next;B、p→next→prior=s;p→next=s;s→prior=p;s→next=p→next;C、s→prior=p;s→next=p→next;p→next=s;p→next→prior=s;D、s→prior=p;s→next=p→next;p→next→prior=s;p→next=s;

10、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s;C、p->next=s;p->next=s->next;D、p->next=s->next;p->next=s;

11、单链表中，指针p指向的结点的后继为q指向的结点，在指针为p的结点之后、q之前插入指针为s的结点，正确的操作是：（A、p->next=s;s=p;B、p=s;p=qC、p=q;s=p;D、s->next=q;p->next=s;

12、单链表中，指针p指向的结点的后继为q指向的结点，删除q指针的正确的操作是：（A）。A、p->next=q->next;free(q);B、p->next=q;free(q);C、free(p);D、free(q);

13、在双向链表存储结构中，prior和next分别指向前趋及后继，删除p所指的结点时需修改指针（A）。

第2章，第1页共4页D）。1

A、p->next->prior=p->prior；p->prior->next=p->next;B、p->next=p->next->next；p->next->prior=p;

C、p->prior->next=p；p->prior=p->prior->prior；D、p->prior=p->next->next；p->next=p->prior->prior;14、带附加头节点的单链表L为空表的条件是（B）。

A、L==NULLB、L->next==NULLC、L->next==NULLD、L->next==L15、不带附加头结点的单链表L为空表的条件是（A）。

A、L==NULLB、L->next==NULLC、L->next==NULLD、L->next==L16、以下哪项不是单链表的特点（B）。

A、存储空间可以连续，也可以不连续B、插入时，不用查找插入位置

C、插入时不用移动其他元素的存储位置D、删除时不用移动其他元素的存储位置17、删除在顺序存储方式的线性表中第i个元素，（C）。

A、需要从第一个元素可是查找第i个元素。B、不必移动顺序表中的元素。C、第i个元素之后的所有元素需要前移。D、第i个元素前移18、在顺序存储方式的线性表中的第i个位置插入一个元素（C）。

A、需要从第一个元素可是查找第i个元素。B、不必移动顺序表中的元素。

C、第i个位置后的元素后移，第i个位置插入元素。D、只需将插入的元素放在第i个位置。19、在（B）运算中，使用顺序表比链表好。

A、插入B、根据序号查找C、删除D、根据元素值查找

20、在非空的线性表中，有且只有一个直接前驱和一个直接后继的结点是（C）A、开始结点B、终端结点C、内部节点D、所有结点

21、在一个长度为n的顺序表中，假使要在第i个元素前插入一个元素，要后移（D）个元素。A、nB、n-1C、iD、n-i+1

22、在一个数组中查找第i个元素（i在有效范围内），则需要（B）。

A、从头开始查找B、无需查找，直接引用标号C、从尾部查找D、以上答案都不对23、在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行（B）操作与链表的长度有关。A、删除单链表中的第一个元素B、删除单链表中的最终一个元素C、在单链表第一个元素前插入一个新元素D、在单链表最终一个元素后插入一个新元素24、与单链表相比，双链表的优点之一是（D）。A、插入、删除操作更简单B、可以进行随机访问C、可以省略表头指针或表尾指针D、顺序访问相邻结点更灵活

25、指针p指向单链表的结点，输出该结点值的语句为（B），设结点值为整数类型。

A、printf(“%d〞,p->next);B、printf(“%d〞,p->data);C、printf(“%d〞,p);D、printf(“%c〞,p);三、算法分析题。1、简述以下算法的功能。

StatusA（LinkListL）

{if（L

//当前存储空间已满

m=L.length;

while(m>=0){

//找到x待查的位置

if(x=m-1;j--)

L.elem[j+1]=L.elem[j]；

//待插位置及之后的元素后移L.elem[m-1]=x;//将x放入第m个位置L.length++;

//修改表长

returnOK;

}

2、写算法实现删除单链表中值为x的元素，若删除成功输出“YES!〞；假使x不存在，则输出“NO!〞。

StatusLIistDelete(LinkList//初始化，p指向首元结点

while(p->next

if(!p)coutnext;//临时保存要被删除的结点p->next=q->next;//修改被删结点的前驱结点的指针deleteq;

//释放删除了的结点的空间coutdata=y;//新结点的数据域内放ys->next=NULL;//新结点的指针域置为空while(p)//未到达表尾{if(p->next->data==x)s->next=p->next;p->nexts;}//将新结点插入在值为x的结点前面if(!p)p->next=s;//在表中未找到值为x的结点，所以将新结点插入在表尾}

4、已知一个带头结点的单链表L，按结点值递增有序排列，试编写一个函数插入一个结点x后仍保持该链表的有序性。

StatusListInsert(LinkList//初始化p，使p指向头结点s=newLNode;//生成一个新的节点s->data=e;//新结点的数据域中存放es->next=NULL;//新结点的指针域置为空while（p）//没有到达表尾

if(p->next->data>=e)