第二章线性表 名词解释 1.线性结构2.数据结构的顺序实现3.顺序表4.链表5.数据结构的链接实现 6.建表 7.字符串 8.串 顺序串10.链串 、填空题 1.为了便于讨论,有时将含n(n>=0)个结点的线性结构表示成(a1,a,…an),其中每 个a;代表一个 a1称为结点,a称为结点,i称为a1在线性表中的 或。对任意一对相邻结点a;、a+1(1<=i<mn),a;称为a+的直接 a+称为a;的直 2.为了满足运算的封闭性,通常允许一种逻辑结构出现不含任何结点的情况。不含任何 结点的线性结构记为或 线性结构的基本特征是:若至少含有一个结点,则除起始结点没有直接外,其他 结点有且仅有一个直接;除终端结点没有直接_外,其它结点有且仅有一个直接 4.所有结点按1对1的邻接关系构成的整体就是 结构。 5线性表的逻辑结构是 结构。其所含结点的个数称为线性表的 简称 6.表长为0的线性表称为 7.线性表典型的基本运算包括 等六 种。 顺序表的特点是 9.顺序表的类型定义可经编译转换为机器级。假定每个 datatype类型的变量占用k(k>=1) 个内存单元,其中,b是顺序表的第一个存储结点的第一个单元的内存地址,那么,第i个 结点a1的存储地址为 10.以下为顺序表的插入运算,分析算法,请在 处填上正确的语句 Void insert sqlist(sqlist L, datatype x, int i) 将X插入到顺序表L的第i-1个位置*/ if(L.last== mansize) error(“表满”) if(i<1)|(iL.1ast+1)eror(“非法位置”) for(j=L last: j>=i; j-) L data[i-1 L, last=L. last+1 11.对于顺序表的插入算法 insert sqlist来说,若以结点移动为标准操作,则插入算法 的最坏时间复杂性为 量级是 插入算法的平均时间复杂性为 平均时间复杂性量级是 12.以下为顺序表的删除运算,分析算法,请在 处填上正确的语句。 void delete sqlist( sqlist l,inti)/删除顺序表L中的第i-1个位置上的结点* if(i<1)|(i>L.1ast)eror(“非法位置”) for(j=i+1: j=L last: j++) L last=L. last-1 13.对于顺序表的删除算法 delete sqlist来说,若以结点移动为标准操作,最坏情况时 间复杂性及其量级分别是 和 ,其平均时间复杂性及其量级分别为
1 第二章 线性表 一．名词解释 1. 线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现 6. 建表 7.字符串 8.串 9.顺序串 10.链串 二、填空题 1.为了便于讨论，有时将含 n(n>=0)个结点的线性结构表示成(a1，a2,……an)，其中每 个ai 代表一个______。a1 称为______结点，an 称为______结点，i称为ai 在线性表中的________ 或______。对任意一对相邻结点 ai、ai┼1(1<=i<n),ai 称为 ai┼1 的直接______ai┼1 称为 ai 的直 接______。 2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何 结点的线性结构记为______或______。 3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他 结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接 ______. 4.所有结点按 1 对 1 的邻接关系构成的整体就是______结构。 5.线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称 ______. 6.表长为 O 的线性表称为______ 7.线性表典型的基本运算包括:______、______、______、______、______、______等六 种。 8.顺序表的特点是______。 9.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用k(k>=1) 个内存单元，其中，b 是顺序表的第一个存储结点的第一个单元的内存地址，那么，第 i 个 结点 ai 的存储地址为______。 10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 Void insert_sqlist(sqlist L，datatype x，int i) /*将 X 插入到顺序表 L 的第 i-1 个位置*/ { if( L.last == maxsize) error(“表满”)； if((i<1)||(i>L.last+1))error(“非法位置”); for(j=L.last;j>=i;j--)______; L.data[i-1]=x; L.last=L.last+1; } 11.对于顺序表的插入算法 insert_sqlist 来说，若以结点移动为标准操作，则插入算法 的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________， 平均时间复杂性量级是________。 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.last=L.last-1; } 13.对于顺序表的删除算法 delete_sqlist 来说，若以结点移动为标准操作，最坏情况时 间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________
14.以下为顺序表的定位运算,分析算法,请在 处填上正确的语句 int locate sqlist(sqlist L, datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号;否则回传0*/ while((isL. last)&&(Ldata[i-1!=X))i++ return(i) else return(O) 5.对于顺序表的定位算法,若以取结点值与参数X的比较为标准操作,平均时间复杂性 量级为 。求表长和读表元算法的时间复杂性为 16.在顺序表上,求表长运算 LENGTH(L)可通过输出实现,读表元运算 GET(L,i)可通过输出实现 17.线性表的常见链式存储结构有 和 18.单链表表示法的基本思想是用 表示结点间的逻辑关系。 19.所有结点通过指针的链接而组织成 20.为了便于实现各种运算,通常在单链表的第一个结点之前增设一个类型相同的结点 称为 其它结点称为 21.在单链表中,表结点中的第一个和最后一个分别称为 和 头结点的 数据域可以不存储 也可以存放一个 或 22.单链表 INITIATE(L)的功能是建立一个空表。空表由 组成 23. INITIATE O的功能是建立一个空表。请在 处填上正确的语句。 lklist initiate lklisto /*建立一个空表*/ return(t) 24.以下为求单链表表长的运算,分析算法,请在 处填上正确的语句。 int length lklist(lklist head) /*求表head的长度* while(p->next! =NULL return (j) /*回传表长*/ 25.以下为单链表按序号査找的运算,分析算法,请在处填上正确的语句 pointer find lklist(lklist head, int i) i p=head; j=0 while i p=p->next; j++ I f(i=j) return(p);
2 和________。 14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表 L 中查找第一值等于 X 的结点。若找到回传该结点序号；否则回传 0*/ {________; while((i≤L.last)&&(L.data[i-1]!=X))i++; if(________)return(i); else return(0); } 15.对于顺序表的定位算法，若以取结点值与参数 X 的比较为标准操作，平均时间复杂性 量级为________。求表长和读表元算法的时间复杂性为________。 16.在顺序表上，求表长运算 LENGTH（L）可通过输出________实现，读表元运算 GET（L，i）可通过输出________实现。 17.线性表的常见链式存储结构有________、________和________。 18.单链表表示法的基本思想是用________表示结点间的逻辑关系。 19.所有结点通过指针的链接而组织成________。 20.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点， 称为________，其它结点称为________。 21.在单链表中，表结点中的第一个和最后一个分别称为________和________。头结点的 数据域可以不存储________，也可以存放一个________或________。 22.单链表 INITIATE（L）的功能是建立一个空表。空表由一个________和一个________ 组成。 23.INITIATE()的功能是建立一个空表。请在________处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/ {________________; ________________; return(t); } 24.以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head) /*求表 head 的长度*/ {________; 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中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ while( )p=p->next: j++: I f(p->data=x) return(j) else return(O) 27.以下为单链表的删除运算,分析算法,请在处填上正确的语句 void delete lklist(lklist head, int i) i p=find lklist(head, i-1) p->next→p->next free(g) else error(不存在第i个结点") 28.以下为单链表的插入运算,分析算法,请在处填上正确的语句 void insert lklist(lklist head, datatype x, int i) /*在表head的第i个位置上插入一个以x为值的新结点* i p=find lklist(head, i-1) f(p=NUL) error("不存在第i个位置〃) else I s->next= p-onext-s 29.以下为单链表的建表算法,分析算法,请在处填上正确的语句。 Iklist create lklistlo /*通过调用 initiate_ krist和 insert lklist算法实现的建表算法。假定$是结束标志* I ininiate lklist(head) scanf(%f, &x while(x!=rS,) scant return (head) 该建表算法的时间复杂性约等于 ,其量级为 3
3 else return(NULL); } 26.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。 int locate_lklist(lklist head,datatype x) /*求表 head 中第一个值等于 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_lklist(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; scanf(“%f”,&x); while(x!=’$’) {________________; ________________; scanf(“%f”,&x); } return(head); } 该建表算法的时间复杂性约等于____________，其量级为____________
30.以下为单链表的建表算法,分析算法,请在处填上正确的语句 Iklist create lklist2O /*直接实现的建表算法。*/ I head=malloc (size) scanf(%f", &x) while(x!=IS g=malloc(size) p>nextg scanf("%f", &x) return(head) 此算法的量级为 31.除单链表之外,线性表的链式存储结构还有 32.循环链表与单链表的区别仅仅在于其尾结点的链域值不是 ,而是一个指向 的指针。 33.在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点,这样构成的链 表中有两个方向不同的链,称为 4.C语言规定,字符串常量按处理,它的值在程序的执行过程中是不能改变的 而串变量与其他变量不一样,不能由语句对其赋值 35.含零个字符的串称为串,用表示。其他串称为串。任何串中所 的个数称为该串的长度 36.当且仅当两个串的相等并且各个对应位置上的字符都时,这两个串相 等。一个串中任意个连续字符组成的序列称为该串的串,该串称为它所有子串的 37.串的顺序存储有两种方法:一种是每个单元只存一个字符,称为格式,另 种是每个单元存放多个字符,称为 格式 38.通常将链串中每个存储结点所存储的字符个数称为 当结点大小大于1时 链串的最后一个结点的各个数据域不一定总能全被字符占满,此时,应在这些未用的数据域 里补上 三、单向选择题 1.对于线性表基本运算,以下结果是正确的是 ①初始化 INITIATE(L),引用型运算,其作用是建立一个空表L=Φ ②求表长 LENGTH①L),引用型运算,其结果是线性表L的长度 ③读表元GET①L,ⅱ),引用型运算。若1<=i<= LENGTH(L),其结果是线性表L的第i个结点; 否则,结果为0 ④定位L0CATE(L,X),引用型运算.若L中存在一个或多个值与X相等的结点,运算结果 为这些结点的序号的最大值:否则运算结果为0 ⑤插入 INSERT(L,X,i,加工型运算。其作用是在线性表L的第i+1个位置上增加一个以X 为值的新结点 ⑥删除 DELETE(L,i),引用型运算.其作用是撤销线性表L的第i个结点Ai
4 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．除单链表之外，线性表的链式存储结构还有_________和_________等。 32．循环链表与单链表的区别仅仅在于其尾结点的链域值不是_________，而是一个指向 _________的指针。 33．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链 表中有两个方向不同的链，称为______。 34．C 语言规定，字符串常量按______处理，它的值在程序的执行过程中是不能改变的。 而串变量与其他变量不一样，不能由______语句对其赋值。 35．含零个字符的串称为______串，用______表示。其他串称为______串。任何串中所 含______的个数称为该串的长度。 36．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相 等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______ 串。 37．串的顺序存储有两种方法：一种是每个单元只存一个字符，称为______格式，另一 种是每个单元存放多个字符，称为______格式。 38．通常将链串中每个存储结点所存储的字符个数称为______。当结点大小大于 1 时， 链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域 里补上______。 三、单向选择题 1．对于线性表基本运算，以下结果是正确的是 ( ) ①初始化 INITIATE(L)，引用型运算，其作用是建立一个空表 L=Ф . ② 求表长 LENGTH(L)，引用型运算，其结果是线性表 L 的长度 ③读表元 GET(L,i), 引用型运算。若 1<=i<=LENGTH(L),其结果是线性表 L 的第 i 个结点； 否则，结果为 0 ④定位 LOCATE(L,X), 引用型运算.若 L 中存在一个或多个值与 X 相等的结点，运算结果 为这些结点的序号的最大值；否则运算结果为 0 ⑤插入 INSERT(L,X,i),加工型运算。其作用是在线性表 L 的第 i+1 个位置上增加一个以 X 为值的新结点 ⑥删除 DELETE(L,i), 引用型运算.其作用是撤销线性表 L 的第 i 个结点 Ai
2线性结构中的一个结点代表一个 ①数据元素 ②数据项 ③数据 ④数据结构 3.顺序表的一个存储结点仅仅存储线性表的一个 ①数据元素 ②数据项 ③数据 ④数据结构 4.顺序表是线性表的 ①链式存储结构②顺序存储结构③索引存储结构④散列存储结构 5.对于顺序表,以下说法错误的是 ①顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址 ②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 ③顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 ④顺序表的特点是:逻辑上相邻的元素,存储在物理位置也相邻的单元中 6.对顺序表上的插入、删除算法的时间复杂性分析来说,通常以()为标准操作 ①条件判断 ②结点移动 ③算术表达式④赋值语句 7.对于顺序表的优缺点,以下说法错误的是 ①无需为表示结点间的逻辑关系而增加额外的存储空间 ②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便 ④由于顺序表要求占用连续的空间,存储分配只能预先进行(静态分配) ⑤容易造成一部分空间长期闲置而得不到充分利用 8.指针的全部作用就是 ①指向某常量 ②指向某变量 ③指向某结点 ④存储某数据 9.除了(),其它任何指针都不能在算法中作为常量出现,也无法显示。 ①头指针 ②尾指针 ③指针型变量 ④空指针 10.单链表表示法的基本思想是指针P表示结点间的逻辑关系,则以下说法错误的是( ①任何指针都不能用打印语句输出一个指针型变量的值 ②如果要引用(如访问)p所指结点,只需写出p(以后跟域名)即可 ③若想修改变量p的值(比如让P指向另一个结点),则应直接对p赋值 ④对于一个指针型变量P的值。只需知道它指的是哪个结点 ⑤结点*p是由两个域组成的记录,p>data是一个数据元素,p->next的值是一个指针 11.单链表的一个存储结点包含 ①数据域或指针域 ②指针域或链域 ③指针域和链域 ④数据域和链域 12.对于单链表表示法,以下说法错误的是 ①数据域用于存储线性表的一个数据元素 ②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 ③所有数据通过指针的链接而组织成单链表 ④NUL称为空指针,它不指向任何结点,只起标志作用 13.对于单链表表示法,以下说法错误的是 ①指向链表的第一个结点的指针,称为头指针
5 2.线性结构中的一个结点代表一个 （ ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构 3．顺序表的一个存储结点仅仅存储线性表的一个 （ ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构 4．顺序表是线性表的 （ ） ①链式存储结构 ②顺序存储结构 ③ 索引存储结构 ④ 散列存储结构 5.对于顺序表，以下说法错误的是 （ ） ①顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 ②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 ③顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 ④顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作 ①条件判断 ②结点移动 ③算术表达式 ④赋值语句 7.对于顺序表的优缺点，以下说法错误的是 （ ） ①无需为表示结点间的逻辑关系而增加额外的存储空间 ②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便 ④由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配) ⑤容易造成一部分空间长期闲置而得不到充分利用 8.指针的全部作用就是 （ ） ①指向某常量 ② 指向某变量 ③指向某结点 ④存储某数据 9.除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。 ①头指针 ②尾指针 ③指针型变量 ④空指针 10.单链表表示法的基本思想是指针 P 表示结点间的逻辑关系，则以下说法错误的是（ ） ①任何指针都不能用打印语句输出一个指针型变量的值 ②如果要引用(如访问)p 所指结点，只需写出 p(以后跟域名)即可 ③若想修改变量 p 的值(比如让 P 指向另一个结点)，则应直接对 p 赋值 ④对于一个指针型变量 P 的值。只需知道它指的是哪个结点 ⑤结点*ｐ是由两个域组成的记录，p->data 是一个数据元素，p->next 的值是一个指针 11.单链表的一个存储结点包含 （ ） ①数据域或指针域 ②指针域或链域 ③指针域和链域 ④数据域和链域 12.对于单链表表示法，以下说法错误的是 （ ） ①数据域用于存储线性表的一个数据元素 ②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 ③所有数据通过指针的链接而组织成单链表 ④NULL 称为空指针，它不指向任何结点，只起标志作用 13.对于单链表表示法，以下说法错误的是 （ ） ①指向链表的第一个结点的指针，称为头指针