【免费】数据结构复习资料资源-CSDN文库

数据结构

需积分: 0 21 浏览量 2012-12-18 09:56:54 上传评论收藏 842KB DOC 举报

资源推荐

资源详情

资源评论

第二章线性表

二、填空题

为了便于讨论，有时将含 个结点的线性结构表示成



，







，其中每个 



代表一个结点。



称为起始

结点，



称为终端结点， 称为 



在线性表中的序号或位置。对任意一对相邻结点 



、







称为





的直接前趋



称为 



的直接后趋。

为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为（）或。

线性结构的基本特征是若至少含有一个结点，则除起始结点没有直接 后趋外，其他结点有且仅有一个直接前趋除

终端结点没有直接后趋外，其它结点有且仅有一个直接前趋

所有结点按  对  的邻接关系构成的整体就是线性结构。

线性表的逻辑结构是线性结构。其所含结点的个数称为线性表的长度，简称表长

表长为  的线性表称为空表

线性表典型的基本运算包括插入、删除 （Ｌ，Ｘ，ｉ）、、、、等六种。

顺序表的特点是逻辑结构中相邻的节点在物理结构中乃相邻。

顺序表的类型定义可经编译转换为机器级。假定每个 !!"#$ 类型的变量占用 %%个内存单元，其中，& 是顺序表的第一

个存储结点的第一个单元的内存地址，那么，第  个结点 



的存储地址为&'%(（)）。

以下为顺序表的插入运算，分析算法，请在*+ !,-).+ !,-.处填上正确的语句。

/0 *1$2!1341!1341!*+， !!"#$*5，!*

6(将 7 插入到顺序表 + 的第 ) 个位置(6

8*9*+41!**:51;$*$2202<表满”；

9==+41!'$2202<非法位置”

902-+41!--))

+ !,).5

+41!+41!'

11.对于顺序表的插入算法 insert_sqlist 来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为 ____N____，量级是

_o(n)_______。插入算法的平均时间复杂性为__(n-1/)2______，平均时间复杂性量级是__o(n)______。

12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。

void delete_sqlist(sqlist L,int i) /*删除顺序表 L 中的第 i-1 个位置上的结点*/

{if((i<1)||(i>L.last))error(<非法位置”)；

for(j=i+1;j<L.last;j++)___L.data[i-2] = L.data[i-1]_____;

L.last=L.last-1;

}

13.对于顺序表的删除算法 delete_sqlist 来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是_n-1_______和__

_o(n)_____,其平均时间复杂性及其量级分别为___(n-1)/2_____和__o(n)______。

14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。

int locate_sqlist(sqlist L,datatype X)

/*在顺序表 L 中查找第一值等于 X 的结点。若找到回传该结点序号；否则回传 0*/

{____int i =0____;

while((i?L.last)&&(L.data[i-1]!=X))i++;

if(__i<=L.last______)return(i);

else return(0);

}

15.对于顺序表的定位算法，若以取结点值与参数 X 的比较为标准操作，平均时间复杂性量级为___o(n)_____。求表长和读表元算法

的时间复杂性为___O(1)_____。

16.在顺序表上，求表长运算 LENGTH（L）可通过输出___L.last_____实现，读表元运算

GET（L，i）可通过输出____L.data[i-1]____实现。

17.线性表的常见链式存储结构有___单链表_____、__双链表______和__循环链表______。

18.单链表表示法的基本思想是用___指针_____表示结点间的逻辑关系。



19.所有结点通过指针的链接而组织成___单链表_____。

20.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为 ___头结点_____，其它结点称为_表结

点_______。

21.在单链表中，表结点中的第一个和最后一个分别称为___首结点_____和__尾结点______。头结点的数据域可以不存储_任何信息

特殊标志_______，也可以存放一个________或________。

22.单链表 INITIATE（L）的功能是建立一个空表。空表由一个________和一个________组成。

@的功能是建立一个空表。请在处填上正确的语句。

****4%41!*!!$4%41!***********************6(建立一个空表(6

8!**:440A4%41!

*!)$5!**B++

**2$!C2!

以下为求单链表表长的运算，分析算法，请在 处填上正确的语句。

****!*4$D!E4%41!4%41!*E$ ************6(求表 E$ 的长度(6

****84%41!*#**E$ 

-

FE4$#)$5!GB++

****8#**#)$5!

*****-''

2$!C2-******************************6(回传表长(6

以下为单链表按序号查找的运算，分析算法，请在处填上正确的语句。

**#0!$2*H 4%41!4%41!*E$ !*

****8*#E$ -

******FE4$-II#)$5!GB++

********8*##)$5!*-''*>

**********9-*2$!C2#

**********$41$*2$!C2B++

以下为单链表的定位运算，分析算法，请在处填上正确的语句。

****!*40A!$4%41!4%41!*E$  !!"#$*5

****6(求表 E$ 中第一个值等于 5 的结点的序号。不存在这种结点时结果为 (6

***8*#E$ -

FE4$#)$5!GB++II#) !G58##)$5!-''>

9*#) !5*2$!C2-

$41$************2$!C2

以下为单链表的删除运算，分析算法，请在处填上正确的语句。

****J0 * $4$!$4%41!4%41!*E$ !*

8*#H 4%41!E$ )

**9#GB++II#)$5!GB++

****8*3#)$5!

******#)$5!3)$5!

******92$$3

****>

****$41$*$2202<不存在第  个结点”



以下为单链表的插入运算，分析算法，请在处填上正确的语句。

****J0 *1$2!4%41!4%41!*E$  !!"#$*5!*

****6(在表 E$ 的第  个位置上插入一个以 5 为值的新结点(6

***8*#H 4%41!E$ )

9#B++$2202<不存在第  个位置”；

$41$*81:440A4%41!1) !5

*******1)$5!#)$5!

*******#)$5!1

******>

以下为单链表的建表算法，分析算法，请在处填上正确的语句。

****4%41!**A2$!$4%41!

**6(通过调用 !!$4%41! 和 1$2!4%41! 算法实现的建表算法。假定K是结束标志(6

***8*!$4%41!E$ 



1A9<L9MI5

FE4$5GNKN

**81$2!4%41!E$ 5

***''

*****1A9<L9MI5

2$!C2E$ 

****该建表算法的时间复杂性约等于)6，其量级为0。

以下为单链表的建表算法，分析算法，请在处填上正确的语句。

****4%41!*A2$!$4%41!************6(直接实现的建表算法。(6

8*E$ :440A1;$

**#E$ 

**1A9<L9MI5

**FE4$5GNKN

****8*3:440A1;$

*******3) !5

*******#)$5!3

******#*3

*******1A9<L9MI5

****>

**#)$5!**B++

**2$!C2E$ 

***此算法的量级为0。

．除单链表之外，线性表的链式存储结构还有单项循环链表和双项循环链表等。

．循环链表与单链表的区别仅仅在于其尾结点的链域值不是B++，而是一个指向头结点的指针。

．在单链表中若在每个结点中增加一个指针域所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为双链表

。

．O 语言规定，字符串常量按字符串处理，它的值在程序的执行过程中是不能改变的。而串变量与其他变量不一样，不能

由赋值语句对其赋值。

．含零个字符的串称为空串，用表示。其他串称为非空串。任何串中所含字符的个数称为该串的长度。

．当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串相等。一个串中任意个连续字符组成



的序列称为该串的子串，该串称为它所有子串的主串。

．串的顺序存储有两种方法：一种是每个单元只存一个字符，称为 格式，另一种是每个单元存放多个字符，称为格

式。

．通常将链串中每个存储结点所存储的字符个数称为。当结点大小大于  时，链串的最后一个结点的各个数据域不一定总

能全被字符占满，此时，应在这些未用的数据域里补上。

三、单向选择题

*．对于线性表基本运算，以下结果是正确的是 ***

***P 初始化 @+，引用型运算，其作用是建立一个空表 +Q

**R*求表长 +ST+，引用型运算，其结果是线性表 + 的长度空

***U 读表元 S+*引用型运算。若 +ST+其结果是线性表 + 的第  个结点；

***否则，结果为 

***V 定位 +O@+7*引用型运算若 + 中存在一个或多个值与 7 相等的结点，运算结果为这些结点的序号的最大值；否则运算结果为



***W 插入 X+7加工型运算。其作用是在线性表 + 的第 ' 个位置上增加一个以 7 为值的新结点

***Y 删除 Z++*引用型运算其作用是撤销线性表 + 的第  个结点 @

线性结构中的一个结点代表一个（）

**P*数据元素 ② 数据项 ③ 数据 ④ 数据结构

．顺序表的一个存储结点仅仅存储线性表的一个（）

**P*数据元素 ② 数据项 ③ 数据 ④ 数据结构

．顺序表是线性表的（）

**P 链式存储结构 ②顺序存储结构 ③ 索引存储结构 ④ 散列存储结构

对于顺序表，以下说法错误的是（）

**P 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址

**R 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列

**U 顺序表的特点是逻辑结构中相邻的结点在存储结构中仍相邻

**V 顺序表的特点是逻辑上相邻的元素，存储在物理位置也相邻的单元中

对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作

**P 条件判断 ②结点移动

**U 算术表达式 ④赋值语句

对于顺序表的优缺点，以下说法错误的是（）

**P 无需为表示结点间的逻辑关系而增加额外的存储空间

**R 可以方便地随机存取表中的任一结点

**U 插人和删除运算较方便

**V 由于顺序表要求占用连续的空间，存储分配只能预先进行静态分配

**W 容易造成一部分空间长期闲置而得不到充分利用

指针的全部作用就是（）

**P 指向某常量 ② 指向某变量

**U 指向某结点 ④存储某数据

除了*****，其它任何指针都不能在算法中作为常量出现，也无法显示。

**P 头指针 ②尾指针

**U 指针型变量 ④空指针

单链表表示法的基本思想是指针 [ 表示结点间的逻辑关系，则以下说法错误的是（　　　）

**P 任何指针都不能用打印语句输出一个指针型变量的值

**R 如果要引用如访问# 所指结点，只需写出 #以后跟域名即可

**U 若想修改变量 # 的值比如让 [ 指向另一个结点，则应直接对 # 赋值

**V 对于一个指针型变量 [ 的值。只需知道它指的是哪个结点

**W 结点(ｐ是由两个域组成的记录，#) ! 是一个数据元素，#)$5! 的值是一个指针

单链表的一个存储结点包含　　　　　　　　　　　　　（　　　　）



**P 数据域或指针域

**R 指针域或链域

**U 指针域和链域

**V 数据域和链域

对于单链表表示法，以下说法错误的是　　　　　　　　　（　　　　）

**P 数据域用于存储线性表的一个数据元素

**R 指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针

**U 所有数据通过指针的链接而组织成单链表

**VB++ 称为空指针，它不指向任何  结点，只起标志作用

对于单链表表示法，以下说法错误的是　　　　　　　　　　（　）

**P 指向链表的第一个结点的指针，称为头指针

**R 单链表的每一个结点都被一个指针所指

**U 任何结点只能通过指向它的指针才能引用

V 终端结点的指针域就为 B++

W 尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表

．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（**）

P 将“指针型变量”简称为“指针”

R 将“头指针变量”称为“头指针”

U 将“修改某指针型变量的值”称为“修改某指针”

V 将“# 中指针所指结点”称为“[ 值”

．设指针 [ 指向双链表的某一结点，则双链表结构的对称性可用（ *）式来刻画

 #)#202)$5!)#)$5!)$5!

 #)#202)#202)#)$5!)#202

 #)#202)$5!)#)$5!)#202

 #)$5!)$5!#)#202)#202

以下说法错误的是（*）

P 对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表

R 对单链表来说，只有从头结点开始才能扫描表中全部结点

U 双链表的特点是找结点的前趋和后继都很容易

V 对双链表来说，结点([ 的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。

．在循环链表中，将头指针改设为尾指针（2$2）后，其头结点和尾结点的存储位置分别是（**）

P2$4 和 2$2)$5!)$5!

R2$2)$5!*和 2$4

U2$2)$5!)$5! 和 2$2

V2$2 和 2$2)$5!

以下说错误的是 ***

P 对于线性表来说，定位运算在顺序表和单链表上的量级均为 （）

R 读表元运算在顺序表上只需常数时间 （）便可实现，因此顺序表是一种随机存取结构

U 在链表上实现读表元运算的平均时间复杂性为 （）

V 链入、摘除操作在链表上的实现可在 （）时间内完成

W 链入、摘除操作在顺序表上的实现，平均时间复杂性为 （）

．在串的基本运算中，属于加工型运算的有（）

P\@+****R+ST

UOO@**VX[+@OX**WZ7

*在串的基本运算中，属于引用型运算的有（）

P@S****RX

UZ+-**VB]X-**WX[+@OX

．循环链表主要优点是（ *）



剩余39页未读，继续阅读

评论收藏

内容反馈

yaoyaoqing

粉丝: 0
资源: 2

数据结构复习资料

数据结构复习资料 数据结构 复习 资料

数据结构复习资料及试卷（c++版）

数据结构复习资料数据结构复习资料

数据结构 复习资料

数据结构复习资料.docx

西工大组原和数据结构复习资料

专升本-数据结构复习资料.rar

华中科技大学数据结构复习资料

数据结构复习资料 C++

数据结构最新的考试复习资料

Qt上位机软件串口通讯，视频源码，免费下载

代码随想录算法PDF.rar

张玉生《C语言程序设计》双色版 C语言程序设计理论教材习题参考答案.pdf

cloud compare用户手册（中文+英文）

CRC8/CRC16/CRC32常见几个标准的算法及C语言实现

STM32F4 ADC采样FFT运算测试代码

第十二届蓝桥杯大赛模拟赛（第三期）.pdf

Qt Qss三套样式文件 qss.zip

C++读取excel数据

点云粗配准算法

2021csp-j初赛试题及答案.docx

基于STM32F103+ADS1292的心率实时显示（串口助手），心电图波形

C++语言程序设计第五版郑莉

点云完全配准算法比较

Halcon实战视频教程，超人视觉，初级和高级版视频，无密码高清

【C++】开发软件资料集.zip

通俗易懂的校园导航系统

STM32F103开发的无刷直流电机控制FOC

STM32（基于HAL库）驱动0.96寸OLED屏幕（四脚且中英文皆可显示）

最新资源

数据结构复习资料数据结构复习资料

数据结构复习资料