数据结构C++第二章练习

数据结构第二章练习

一、选择题

1. L是线性表，已知L.GetLen( )的值是4，经运算L.DelElem(3)后，L.GetLen( )的值是( )。 ①1②2③3④4 ;3

2. 线性表中，只有一个直接前驱和一个直接后继的是( )。 ①首元素②尾元素③中间的元素④所有的元素 ;3

3. 带头结点的单链表head为空表的判定条件是( )。

①head==NULL②head->next==NULL③head->next==head④head!=NULL ;2

4. 不带头结点的单链表head为空表的判定条件是( )。

①head==NULL②head->next==NULL③head->next==head④head!=NULL ;1

5. 非空的循环单链表head的尾结点p满足( )。

①p==NULL②p->next==NULL③p->next==head④p==head ;3

6. 线性表中各元素之间的关系是( )关系。 ①层次②网状③有序④集合 ;3

7. 在循环(单)链表的一个结点有( )个指针。 ①1②2③3④0 ;1

8. 在单链表的一个结点有( )个指针。 ①1②2③3④0 ;1

9. 在双向链表的一个结点有( )个指针。 ①1②2③3④0 ;2

10. 在一个单链表中，若要删除p所指结点的后继结点，则执行( )。 ①r=p->next;p->next=p->next->next;free(r);

②r=p->next;p=p->next;p->next=p->next->next;free(r); ③r=p->next;p->next=p->next;free(r); ④r=p->next;p=p->next->next;free(r); ;1

11. 判断指针p是否指向循环链表L(带头结点)的第1个元素的条件是( )。 ①p==L②p->next==L③L->next==p④p->next=NULL ;3

12. 在一个单链表中，若在p所指结点之后插入s所指结点，则执行( )。 ①s->next=p;p->next=s;②s->next=p->next;p->next=s; ③s->next=p->next;p=s;④p->next=s;s->next=p; ;2

13. 在一个单链表中，已知q是p的前驱结点，若要在q和p之间插入s所指结点，则执行( ①s->next=p->next;p->next=s;②p->next=s->next;s->next=p;

)。 ③q->next=s;s->next=p;④p->next=s;s->next=q; ;3

14. 假设双链表结点的类型如下： typedef struct linknode {

int data;//数据域

struct linknode *llink; //指向前驱结点的指针域 struct linknode *rlink; //指向后继结点的指针域 }bnode;

现将一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双向链表中，能正确完成此要求的语句段是( )。

①q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q; ②p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink; ③q->llink=p->llink;q->rlink=p;p->llink->rlink=q;p->llink=q; ④以上都不对; ;3

15. 在一个长度为n(n>1)的单链中，设有头和尾两个指针，执行( )操作与链表的长度有关。 ①删除单链表中的第一个元素②删除单链表中最后一个元素

③在单链表第一个元素前插入一个新元素④在单链表最后一个元素后插入一个新元素 ;2

16. 判断指针p是否指向循环链表L的最后1个元素的条件是( )。 ①p==L②p->next==L③L->next==p④p->next=NULL ;2

17. 单链表中设置头结点的作用是( )。

①插入和删除首元素时不必进行特殊处理②插入和删除最后一个元素时不必进行特殊处理③查找和修改首元素时不必进行特殊处理④查找和修改最后一个元素时不必进行特殊处理 ;1

二、填空题

1. 在线性表的顺序存储中，元素之间的逻辑关系是通过____决定的。 ;相邻位置;下标

2. 在线性表的链式存储中，元素之间的逻辑关系是通过____决定的。 ;指针;链接指针

3. 在一个单链表中，指针p所指结点为最后一个结点的条件是____。 ;p->next==NULL

4. 在一个单链表最后一个结点r之后插入结点s，则需执行的3条语句是：

_______;r=s;r->next=NULL; ;r->next=s

5. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是____。 ;O(1)

6. 对于一个具有n个结点的单链表，在值域为给定值的结点后插入一个新结点的时间复杂度是____。 ;O(n)

7. 单链表是____的链接存储表示。 ;线性表

8. 在单链表中，除首结点外，任一结点的存储位置都是由其____结点的____指示。 ;直接前驱;前驱 ;指针域;链域;next域;next

9. 在非空双向循环链表中，在结点q的前面插入结点p的过程如下：

p->prior=q->prior;p->next=q;q->prior->next=p;______; ;q->prior=p

10. 在双向链表中，每个结点有两个指针域，一个指向_____结点(首结点该域值为NULL)，另一个指向

_____结点(末结点该域值为NULL)。 ;前驱;上一;上一个 ;后继;下一;下一个;后续

三、判断题

1. 顺序表中逻辑上相邻的元素的物理位置不一定紧邻。[ ] ;0

2. 单链表中逻辑上相邻的元素的物理位置不一定紧邻。[ ] ;1

3. 单链表中可以从当前结点出发访问到任一结点。[ ] ;0

4. 双向链表中可以从当前结点出发访问到任一结点。[ ] ;1

5. 一个城市的设计和规划适合用线性表的顺序存储结构来描述。[ ] ;0

6. 一个城市的设计和规划适合用线性表的链式存储结构来描述。[ ] ;1

7. 对一个具有n个结点的单链表，若要在指定位置进行插入或删除操作，则其时间复杂度均为O(n)。

[ ] ;1

8. 对一个具有n个结点的循环单链表(带头结点)，若只在表头进行插入和删除操作，则其时间复杂度

均为O(1)。[ ] ;1

9. 对一个具有n个结点的循环单链表(带头结点)，若只在表尾进行插入和删除操作，则其时间复杂度

均为O(1)。[ ] ;0

10. 单链表在指定位置的插入和删除操作时间复杂度为O(n)，线性表的顺序存储结构的插入和删除操作

时间复杂度也是O(n)，因此，不管数据元素数据量有多大，线性表的链表存储方式和顺序存储方式在插入和删除操作方面效率都是一样。[ ] ;0

11. 线性表容量经常变化应该采用链式存储结构。[ ] ;1

12. 线性表元素很少进行插入或删除操作，但要求以最快的速度存取线性表的元素，采用链式存储结构。

[ ] ;0

13. 链表中元素的有序性是指逻辑上的有序性，物理上一般是无序的。[ ] ;1

14. 顺序表中元素的有序性不仅体现在逻辑上有序，而且在物理上也是有序的。[ ] ;1

四、编程题 1.

编写DispInc(…)函数，实现的功能是：

按递增次序输出单链表(带头结点)中各结点的数据元素值并释放结点所占的存储空间，然后在main()函数中调用该函数并输出该表验证。 如： 输入：

5 2 1 4 3 9 7 0 8 6 输出：

0,1,2,3,4,5,6,7,8,9, 空链表

请在/*【*/和/*】*/之间的空白处填入适当语句或式子。

头文件LinkList2.h定义的LinkList类含指向链表的头指针head，数据元素存于data、下一结点指针存于next、成员函数原型如下：

int GetLen( );/*求线性表长度*/

LNode &GetElem(int i);/*取第i个元素,i=1~n*/

LNode Locate(ElemType x);/*查找值为x元素(1~n),没找到返回值为0元素*/ int InsElem(int i,ElemType x);/*第i位置插入元素x,i=1~n*/ int DelElem(int i);/*删除线性表中第i个位置上的元素*/ void DispList( );/*链表元素输出*/ /***源程序***/

#include using namespace std; #include \LinkList2.h\/*【*/

/*】*/ void main() {

LinkList L;int i,x;//5 2 1 4 3 9 7 0 8 6 for(i=1;i<=10;i++){cin>>x;L.InsElem(i,x);} DispInc(L);L.DispList( ); }

①5 2 1 4 3 9 7 0 8 6;0,1,2,3,4,5,6,7,8,9, 空链表 ;10;2

②5 32 1 54 3 69 7 10 8 6;1,3,5,6,7,8,10,32,54,69, 空链表 ;10;8

③30;35;10;0 ④42;37;10;0

⑤17;null;10;0 ;10;5;10;0 参考答案：

void DispInc(LinkList &L) {

int i,j,k,N=L.GetLen( );int x,min; for(i=1;i<=N;i++) {

min=L.GetElem(1);k=1;/*取a1作为最小值*/

for(j=2;j<=L.GetLen( );j++)/*找最小值及其位置*/ {x=L.GetElem(j);if(x

编写DispInc(…)函数，实现的功能是：

按递增次序输出顺序表中各结点的数据元素值，然后删除所有数据元素，最后在main()函数中调用该函数并输出该表验证。 如： 输入：

5 2 1 4 3 9 7 0 8 6 输出：

0,1,2,3,4,5,6,7,8,9, 空链表

请在/*【*/和/*】*/之间的空白处填入适当语句或式子。

头文件sqList2.h定义sqList类的数据元素存于data[ ]、长度存于Length、函数原型如下： int GetLen( ); /*求线性表长度*/

ElemType &GetElem(int i);/*求线性表第i个元素的值,i=1~n*/

ElemType Locate(ElemType x);/*查找值为x元素的位置(1~n),没找到返回0*/ int InsElem(int i,ElemType x);/*第i位置插入元素x,i=1~n*/ int DelElem(int i);/*删除线性表中第i个位置上的元素*/ void DispList( );/*顺序表元素输出*/ /***源程序***/

#include using namespace std; #include \/*【*/

/*】*/ void main() {

本文来源：https://www.bwwdw.com/article/4g2d.html