数据结构第二章笔记整理

第2章 线性表 一 选择题

1．下述哪一条是顺序存储结构的优点？（ ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

2．下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表

6．设一

第2章 线性表

一、单项选择题

1．线性表是具有n个_________的有限序列。

A．表元素 B．字符 C．数据元素 D．数据项 2．线性表是_________。

A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 3．线性表采用链表存储时，其地址_________。

A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以 4．链表不具备的特点是_________。

A．可随机访问任一结点 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与其长度成正比 5．设线性表有n个元素，以下操作中，_________在顺序表上实现比在链表上实现效率更高。

A．输出第i(1≤i≤n)个元素值

B．交换第1个元素与第2个元素的值 C．顺序输出这n个元素的值

D．

数据结构第二章练习

一、选择题

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. 在双向链表的一个结点

习题2

1. 填空题

（1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操作。

答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s;

（2）表长为n的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（___________），删除一个元素需要移动元素的平均个数为（___________）。 答案：n/2 (n-1)/2

（3）表长为0的线性表称为（___________）。 答案：空表

（4）动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的（___________）和（___________）请求。 答案：申请 释放

（5）顺序表多采用（___________）实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为（___________）。而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为（___________）。因此，若线性表的操作主要是

数据结构与算法上机作业

第二章线性表

一、选择题

1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为。 A. O(log2n) B. O(1) C. O(n) D. O(n2) 2、以下关于线性表的说法中，不正确的是。 A. 线性表中的数据元素可以是数字、字符、结构等不同类型 B. 线性表中包含的数据元素个数不是任意的 C.线性表中的每一个结点都有且只有一个直接前驱和直接后继（单项链表） D.存在这样的线性表：表中各结点都没有直接前驱和直接后继（数组实现） 3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为。 A. O(1) B. O(n) C. O(n2) D. O(log2n)

4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 。 A. n B. (n-1)/2 C. n/2 D. (n+1)/2

已经有N个点了,再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动. i的取值服从1到N+1的平均分布,即概率是1/(N+1).

求期望得N/2,即平均要移动N/2个结点期望有计算公式，这里等于

(N+1

/*文件名:exp2-1.cpp*/ #include #include #define MaxSize 50 typedef char ElemType; typedef struct { ElemType data[MaxSize]; int length; } SqList;

extern void InitList(SqList *&L); extern void DestroyList(SqList *L); extern int ListEmpty(SqList *L); extern int ListLength(SqList *L); extern void DispList(SqList *L);

extern int GetElem(SqList *L,int i,ElemType &e); extern int LocateElem(SqList *L, ElemType e); extern int ListInsert(SqList *&L,int i,ElemType e); extern int ListDelete(SqList *&L,int i,ElemType &e); void main

02 线性表

【单选题】

1. 下列不属线性结构特点的是（C）。 Ａ、有且仅有一个数据元素无直接前驱 Ｂ、有且仅有一个数据元素无直接后继

Ｃ、有且仅有一个数据元素既无直接前驱又无直接后继

Ｄ、大多数据元素有且仅有一个直接前驱，有且仅有一个直接后继

2. 线性表是具有n个（C）的有限序列。

Ａ、信息项 Ｂ、字符 Ｃ、数据元素 Ｄ、数据项

3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 Ａ、正确 Ｂ、不正确

4. 在顺序表中，数据元素e1与其直接后继e2在存储位置上（A）。 Ａ、必相邻 Ｂ、必不相邻 Ｃ、可相邻可不相邻

5. 在长为n的顺序表中删除一个数据元素，平均需移动（D）个数据元素。 Ａ、n Ｂ、n-1 Ｃ、n/2 Ｄ、(n-1)/2

6. 在长为n的顺序表中插入一个数据元素，平均需移动（C）个数据元素。 Ａ、n Ｂ、n-1 Ｃ、n/2 Ｄ、(n-1)/2

7. 单链表是一种（B）存取的存储结构 Ａ、随机 Ｂ、顺序 Ｃ、索引 Ｄ、连续

8. 以下属于顺序存储结构优点的是（A）。

Ａ、存储密度大 Ｂ、插入运算方便 Ｃ、删除运算方便 Ｄ、可方便地用于各种逻辑结构的存储表示

9. 以下属单链表优点的是（C）。

Ａ、顺

数据结构练习 第二章 线性表

一、选择题

1. 下面关于线性表的叙述错误的是（ ）。

A.线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D. 线性表采用顺序存储便于插入和删除操作的实现 2. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

A.q=p->next；p->data=q->data；p->next=q->next；free(q)； B. q=p->next；q->data=p->data；p->next=q->next；free(q)； C. q=p->next；p->next=q->next；free(q)； D. q=p->next；p->data=q->data；free(q)；

3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。

A. O(n) B. O(nlog2n) C. O(1) D. O(n2)

4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为

1. 在Windows XP中，操作的特点是____。

A、 先选定操作对象，再选择操作命令

B、 先选定操作命令，再选择操作对象 C、 操作对象和操作命令需同时选择 D、 视具体情况而定

2. Windows XP是一个多任务操作系统，这是指____。

A、 可供多个用户同时使用

B、 在同一时间片中运行多个应用程序

C、 可运行很多种应用程序 D、 可同时管理多种资源

3. 以下关于操作系统的描述，不正确的是____。

A、 操作系统是最基本的系统软件

B、 操作系统与用户对话的界面必定是图形界面 C、 用户程序必须在操作系统的支持下才能运行

D、 操作系统直接运行在裸机之上，是对计算机硬件的第一次扩充 4. 操作系统是一种对____进行控制和管理的系统软件。

A、 应用程序 B、 全部硬件资源 C、 全部软件资源

D、 所有计算机资源 5. 操作系统的主体是____。

A、 数据 B、 程序 C、 内存 D、 CPU

6. Windows XP中同时按下Ctrl＋Alt＋Del三个键将____。

A、 立即重新热启动计算机 B、 进入任务管理器 C、 进行各个任务之间的切换 D、 切换至Linux状态

7. 在Windows XP中

第2章 线性表

一 选择题

1．下述哪一条是顺序存储结构的优点？（ ）【北方交通大学 2001 一、4（2分）】 A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

2．下面关于线性表的叙述中，错误的是哪一个？（ ）【北方交通大学 2001 一、14（2分）】

A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ ）的有限序列（n>0）。 【清华大学 1998 一、4（2分）】 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。【哈尔滨工业大学 2001 二、1（2分）】

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第