1、数据结构练习题 第二章 线性表 习题及答案第二章 线性表 一名词解释 1. 线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现 6. 建表 7.字符串 8.串 9.顺序串 10.链串 二、填空题 1.为了便于讨论，有时将含n(n=0)个结点的线性结构表示成(a，a,a)，其中每n12个a代表一个_。a称为_结点，a称为_结点，i称为a在线性表中的_ii1n或_。对任意一对相邻结点a、a(1=i=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点a的存储地址为_。 i10.以下为顺序表的插入运算，分析算法，请在_处填上正确的语句。
2、 Void insert_sqlist(sqlist L，datatype x，int i) /*将X插入到顺序表L的第i-1个位置*/ if( L.last = maxsize) error(“表满”)； if(iL.last+1)error(“非法位置”); for(j=L.last;j=i;j-)_; L.datai-1=x; L.last=L.last+1; 11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为_，量级是_。插入算法的平均时间复杂性为_，平均时间复杂性量级是_。 12.以下为顺序表的删除运算，分析算法，请在_处填
3、上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/ if(iL.last)error(“非法位置”)； for(j=i+1;j=L.last;j+)_; L.last=L.last-1; 13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时_其平均时间复杂性及其量级分别为_,和_间复杂性及其量级分别是和_。 14.以下为顺序表的定位运算，分析算法，请在_处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一
4、值等于X的结点。若找到回传该结点序号；否则回传0*/ _; while(iL.last)&(L.datai-1!=X)i+; if(_)return(i); else return(0); 15.对于顺序表的定位算法，若以取结点值与参数X的比较为标准操作，平均时间复杂性量级为_。求表长和读表元算法的时间复杂性为_。 16.在顺序表上，求表长运算LENGTH（L）可通过输出_实现，读表元运算 GET（L，i）可通过输出_实现。 17.线性表的常见链式存储结构有_、_和_。 18.单链表表示法的基本思想是用_表示结点间的逻辑关系。 19.所有结点通过指针的链接而组织成_。 20.为了便于实现各种运
5、算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为_，其它结点称为_。 21.在单链表中，表结点中的第一个和最后一个分别称为_和_。头结点的数据域可以不存储_，也可以存放一个_或_。 22.单链表INITIATE（L）的功能是建立一个空表。空表由一个_和一个_组成。 23.INITIATE()的功能是建立一个空表。请在_处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/ _; _; return(t); 24.以下为求单链表表长的运算，分析算法，请在 _处填上正确的语句。 int length_lklist(lklist head) /*求表h
6、ead的长度*/ _; j=0; while(p-next!=NULL) _; j+; return(j); /*回传表长*/ 25.以下为单链表按序号查找的运算，分析算法，请在_处填上正确的语句。 pointer find_lklist(lklist head,int i) p=head;j=0; while(_) p=p-next; j+; if(i=j) return(p); else return(NULL); 26.以下为单链表的定位运算，分析算法，请在_处填上正确的语句。 int locate_lklist(lklist head,datatype x) /*求表head中第一个值
7、等于x的结点的序号。不存在这种结点时结果为0*/ p=head;j=0; while(_)p=p-next;j+; if (p-data=x) return(j); else return(0); 27.以下为单链表的删除运算，分析算法，请在_处填上正确的语句。 void delete_lklist(lklist head,int i) p=find_lklist(head,i-1); if(_) q=_; p-next=p-next; free(q); else error(“不存在第i个结点”) 28.以下为单链表的插入运算，分析算法，请在_处填上正确的语句。 void insert_lk
8、list(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ p=find_lklist(head,i-1); if(p=NULL)error(“不存在第i个位置”)； else s=_;s-data=x; s-next=_; p-next=s; 29.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_lklist1() /*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志*/ ininiate_lklist(head); i=1; s
9、canf(“%f”,&x); while(x!=$) _; _; scanf(“%f”,&x); return(head); 。_，其量级为_该建表算法的时间复杂性约等于 30.以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_lklist2() /*直接实现的建表算法。*/ head=malloc(size); p=head; scanf(“%f”,&x); while(x!=$) q=malloc(size); q-data=x; p-next=q; _; scanf(“%f”,&x); _; return(head); 此算法的量级为_。 31除单链
10、表之外，线性表的链式存储结构还有_和_等。 32循环链表与单链表的区别仅仅在于其尾结点的链域值不是_，而是一个指向_的指针。 33在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为_。 34C语言规定，字符串常量按_处理，它的值在程序的执行过程中是不能改变的。而串变量与其他变量不一样，不能由_语句对其赋值。 35含零个字符的串称为_串，用_表示。其他串称为_串。任何串中所含_的个数称为该串的长度。 36当且仅当两个串的_相等并且各个对应位置上的字符都_时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的_串，该串称为它所有子串的_串。
11、 37串的顺序存储有两种方法：一种是每个单元只存一个字符，称为_格式，另一种是每个单元存放多个字符，称为_格式。 38通常将链串中每个存储结点所存储的字符个数称为_。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上_。 三、单向选择题 1对于线性表基本运算，以下结果是正确的是 ( ) 初始化INITIATE(L)，引用型运算，其作用是建立一个空表L= . 求表长LENGTH(L)，引用型运算，其结果是线性表L的长度 读表元GET(L,i), 引用型运算。若1=idata是一个数据元素，p-next的值是一个指针 11.单链表的一个存储结
12、点包含 （ ） 数据域或指针域 指针域或链域 指针域和链域 数据域和链域 12.对于单链表表示法，以下说法错误的是 （ ） 数据域用于存储线性表的一个数据元素 指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 所有数据通过指针的链接而组织成单链表 NULL称为空指针，它不指向任何结点，只起标志作用 13.对于单链表表示法，以下说法错误的是 （ ） 指向链表的第一个结点的指针，称为头指针 单链表的每一个结点都被一个指针所指 任何结点只能通过指向它的指针才能引用 终端结点的指针域就为NULL 尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表 14有时为了叙述方便，可
13、以对一些概念进行简称，以下说法错误的是 （ ） 将“指针型变量”简称为“指针” 将“头指针变量”称为“头指针” 将“修改某指针型变量的值”称为“修改某指针” 将“p中指针所指结点”称为“P值” 15设指针P指向双链表的某一结点，则双链表结构的对称性可用（ ）式来刻画 p-prior-next-=p-next-next p-prior-prior-=p-next-prior p-prior-next-=p-next-prior p-next-next=p-prior-prior 16.以下说法错误的是 （ ） 对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 对单链表来说，只
14、有从头结点开始才能扫描表中全部结点 双链表的特点是找结点的前趋和后继都很容易 对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。 17在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是 （ ） real和rear-next-next rear-next 和real rear-next-next和rear rear和rear-next 18.以下说错误的是 ( ) 对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n） 读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构 在链表上
15、实现读表元运算的平均时间复杂性为O（1） 链入、摘除操作在链表上的实现可在O（1）时间内完成 链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n） 19在串的基本运算中，属于加工型运算的有 （ ） EQAL(S,T) LENGTH(S) CONCAT(S,T) REPLACE(S,T,R) INDEX(S,T) 20. 在串的基本运算中，属于引用型运算的有 （ ） ASSIGN(S,T) INSERT(S1,i,S2) DELETE(S,i,j) SUBSTR(S,i,j) REPLACE(S,T,R) 21循环链表主要优点是 （ ） 不再需要头指针了 已知某个结点的位置后，能够容易找到它
16、的直接前趋 在进行插入、删除运算时，能更好地保证链表不断开 从表中任一结点出发都能扫描到整个链表 ） （ 插入、删除和查找，这种说法:，每种数据结构都具备三个基本操作22正确 错误 23以下说法错误的是 （ ） 数据的物理结构是指数据在计算机内实际的存储形式 算法和程序没有区别，所以在数据结构中二者是通用的 对链表进行插人和删除操作时，不必移动结点 双链表中至多只有一个结点的后继指针为空 24以下说法正确的是 线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继 线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低 在线性表的顺序存储结构中，插人和删除元素时
17、，移动元素的个数与该元素位置有关 顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动 25以下说法错误的是 （ ） 求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 顺序存储的线性表可以随机存取 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 线性表的链式存储结构优于顺序存储结构 26以下说法错误的是 （ ） 线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一
18、定相邻 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 27以下说法正确的是（ ） 在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构 顺序存储结构属于静态结构，链式结构属于动态结构 顺序存储方式只能用于存储线性结构 28.以下说法正确的是（ ） 顺序存储方式的优点是存储密度大、且插入、删除运算效率高 链表的每个结点中都恰好包含一个指针 线性表的顺序存储结构优于链式存储结构 顺序存储结构属于静态结构，链式结构属于动态结构 29.下面关于线性表的叙
19、述正确的是( ) 线性表采用顺序存储，必须占用一片连续的存储单元 线性表采用顺序存储，便于进行插人和删除操作 线性表采用链接存储，不必占用一片连续的存储单元 线性表采用链接存储，不便于插人和删除操作 30.线性表L=(a,a,.,a,.,a),下列说法正确的是( ) n12i每个元素都有一个直接前驱和直接后继 线性表中至少要有一个元素表中诸元素的排列顺序必须是由小到大或由大到小的 除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 31.线性表的逻辑顺序与存储顺序总是一致的，这种说法( ) 正确 不正确 32.设p,q是指针,若p=q,则*p=*q ,这种说法( )
20、正确 不正确 33.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( ) 必需是联系的 部分地址必须是连续的 一定是不连续的 连续不连续都可以 34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( ) p=rear; rear=rear-next; rear=rear-next; free(rear); free(p) rear=rear-next-next; p=rear-next-next; free(rear); rear-next-next=p-next; free(p); 35. 单链表中，增加头结点的目的是为了 ( ) 使单链表至少有一个
21、结点 标示表结点中首结点的位置 方便运算的实现 说明单链表是线性表的链式存储实现 36线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着 每个结点所代表的数据元素都一样。 每个结点所代表的数据元素包含的数据项的个数要相等 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 结点所代表的数据元素有同一特点 37带头结点的单链表Head为空的判定条件是 Head=Null Head-next=NULL Head-next=Head 38.非空的单循环链表L的尾结点*P,满足 P-next=NULL P=NULL P-next=
22、L P=L. 39.双向链表结点结构如下： LLink data RLink 其中：LLink是指向前驱结点的指针域： data是存放数据元素的数据域； Rlink是指向后继结点的指针域。 下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是 Q-LLink=P-LLink; P-LLink=Q; Q-Rlink=P; Q-Rlink=P; P-LLink=Q; P-LLink-Rlink=Q; P-LLink-Rlink=Q; Q-LLink=P-LLink; Q-LLink=P-LLink; Q-Rlink=P; P-LLink-Rlink=Q; P-LLink=Q; 40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。 顺序表 单链表 双链表 单循环链表 41串是任意有限个 符号构成的集合 符号构成的序列 字符构成的集合 字符构成的序列 四、简答及应用 1 请用类C语言描述顺序表，并予以解释说明。 2 请用类C语言描述单链表的类型定义，并予以解释说明。 3 请用类C语言描述双链表的类型定义，并予以解释说明。 4
