第二章线性表 名词解释 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=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=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(iL.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=1) 个内存单元，其中，b 是顺序表的第一个存储结点的第一个单元的内存地址，那么，第 i 个 结点 ai 的存储地址为______。 10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 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.data[i-1]=x; L.last=L.last+1; } 11.对于顺序表的插入算法 insert_sqlist 来说，若以结点移动为标准操作，则插入算法 的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________， 平均时间复杂性量级是________。 12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。 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中查找第一值等于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.对于单链表表示法，以下说法错误的是 （ ） ①指向链表的第一个结点的指针，称为头指针
②单链表的每一个结点都被一个指针所指 ③任何结点只能通过指向它的指针才能引用 ④终端结点的指针域就为NULL ⑤尾指针变量具标识单链表的作用,故常用尾指针变量来命名单链表 14.有时为了叙述方便,可以对一些概念进行简称,以下说法错误的是 ①将“指针型变量”简称为“指针” ②将“头指针变量”称为“头指针” ③将“修改某指针型变量的值”称为“修改某指针” ④将“p中指针所指结点”称为“P值 15.设指针P指向双链表的某一结点,则双链表结构的对称性可用()式来刻画 Op>prior->next->==p->next->next ②p> prior-> prior->==p->next→> prior ③p>p 4p->next->next==p->prior->prior 16.以下说法错误的是() ①对循环链表来说,从表中任一结点出发都能通过前后操作而扫描整个循环链表 ②对单链表来说,只有从头结点开始才能扫描表中全部结点 ③双链表的特点是找结点的前趋和后继都很容易 ④对双链表来说,结点*P的存储位置既存放在其前趋结点的后继指针域中,也存放在它的 后继结点的前趋指针域中 17.在循环链表中,将头指针改设为尾指针(rear)后,其头结点和尾结点的存储位置分别 ①real和rear->next- ②rear-next和real ③rear->next->next和rear rear t rear->nex 18.以下说错误的是( ①对于线性表来说,定位运算在顺序表和单链表上的量级均为0(n) ②读表元运算在顺序表上只需常数时间0(1)便可实现,因此顺序表是一种随机存取结构 ③在链表上实现读表元运算的平均时间复杂性为0(1) ④链入、摘除操作在链表上的实现可在0(1)时间内完成 ⑤链入、摘除操作在顺序表上的实现,平均时间复杂性为0(n) 19.在串的基本运算中,属于加工型运算的有() ①EQAL(S,T)② LENGTH(S) ③ CoNCAT(S,T)④ REPLACE(S,T,R)⑤ DINDEX(S,T) 20.在串的基本运算中,属于引用型运算的有() ① ASSIGN(S,T)② INSErT(S1,i,S2) ③ DELETE(S,i,j)④ SUBSTR(S,i,j)⑤ REPLACE(S,T,R) 21.循环链表主要优点是 ①不再需要头指针了 ②已知某个结点的位置后,能够容易找到它的直接前趋 ③在进行插入、删除运算时,能更好地保证链表不断开 ④从表中任一结点出发都能扫描到整个链表 22,每种数据结构都具备三个基本操作:插入、删除和查找,这种说法() 6
6 ②单链表的每一个结点都被一个指针所指 ③任何结点只能通过指向它的指针才能引用 ④终端结点的指针域就为 NULL ⑤尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表 14．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是 （ ） ①将“指针型变量”简称为“指针” ②将“头指针变量”称为“头指针” ③将“修改某指针型变量的值”称为“修改某指针” ④将“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.以下说法错误的是 （ ） ①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 ②对单链表来说，只有从头结点开始才能扫描表中全部结点 ③双链表的特点是找结点的前趋和后继都很容易 ④对双链表来说，结点*P 的存储位置既存放在其前趋结点的后继指针域中，也存放在它的 后继结点的前趋指针域中。 17．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别 是 （ ） ①real 和 rear->next->next ②rear->next 和 real ③rear->next->next 和 rear ④rear 和 rear->next 18.以下说错误的是 ( ) ①对于线性表来说，定位运算在顺序表和单链表上的量级均为 O（n） ②读表元运算在顺序表上只需常数时间 O（1）便可实现，因此顺序表是一种随机存取结构 ③在链表上实现读表元运算的平均时间复杂性为 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．循环链表主要优点是 （ ） ①不再需要头指针了 ②已知某个结点的位置后，能够容易找到它的直接前趋 ③在进行插入、删除运算时，能更好地保证链表不断开 ④从表中任一结点出发都能扫描到整个链表 22，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法 （ ）
①正确 ②错误 23.以下说法错误的是() ①数据的物理结构是指数据在计算机内实际的存储形式 ②算法和程序没有区别,所以在数据结构中二者是通用的 ③对链表进行插人和删除操作时,不必移动结点 ④双链表中至多只有一个结点的后继指针为空 24.以下说法正确的是 ①线性结构的基本特征是:每个结点有且仅有一个直接前趋和一个直接后继 ②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要 低 ③在线性表的顺序存储结构中,插人和删除元素时,移动元素的个数与该元素位置有关 ④顺序存储的线性表的插人和删除操作不需要付出很大的代价,因为平均每次操只有近 半的元素需要移动 25.以下说法错误的是() ①求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构 实现的效率低 ②顺序存储的线性表可以随机存取 ③由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活 ④线性表的链式存储结构优于顺序存储结构 26.以下说法错误的是() ①线性表的元素可以是各种各样的,逻辑上相邻的元素在物理位置上不一定相邻 ②在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻 ③在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻 ④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 27.以下说法正确的是() ①在单链表中,任何两个元素的存储位置之间都有固定的联系,因为可以从头结点进行 查找任何一个元素 ②在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存 取的存储结构 ③顺序存储结构属于静态结构,链式结构属于动态结构 ④顺序存储方式只能用于存储线性结构 28.以下说法正确的是 ①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针 ③线性表的顺序存储结构优于链式存储结构 ④顺序存储结构属于静态结构,链式结构属于动态结构 29.下面关于线性表的叙述正确的是() ①线性表采用顺序存储,必须占用一片连续的存储单元 ②线性表采用顺序存储,便于进行插人和删除操作 ③线性表采用链接存储,不必占用一片连续的存储单元 ④线性表采用链接存储,不便于插人和删除操作 30.线性表L=(a1,a2,,a an),下列说法正确的是() ①每个元素都有一个直接前驱和直接后继 ②线性表中至少要有一个元素
7 ①正确 ②错误 23．以下说法错误的是 （ ） ①数据的物理结构是指数据在计算机内实际的存储形式 ②算法和程序没有区别，所以在数据结构中二者是通用的 ③对链表进行插人和删除操作时，不必移动结点 ④双链表中至多只有一个结点的后继指针为空 24．以下说法正确的是 ①线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继 ②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要 低 ③在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关 ④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近 一半的元素需要移动 25．以下说法错误的是 （ ） ①求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时 实现的效率低 ②顺序存储的线性表可以随机存取 ③由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 ④线性表的链式存储结构优于顺序存储结构 26．以下说法错误的是 （ ） ①线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻 ②在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 ③在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻 ④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 27．以下说法正确的是（ ） ①在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行 查找任何一个元素 ②在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存 取的存储结构 ③顺序存储结构属于静态结构，链式结构属于动态结构 ④顺序存储方式只能用于存储线性结构 28.以下说法正确的是（ ） ①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针 ③线性表的顺序存储结构优于链式存储结构 ④顺序存储结构属于静态结构，链式结构属于动态结构 29.下面关于线性表的叙述正确的是( ) ①线性表采用顺序存储，必须占用一片连续的存储单元 ②线性表采用顺序存储，便于进行插人和删除操作 ③线性表采用链接存储，不必占用一片连续的存储单元 ④线性表采用链接存储，不便于插人和删除操作 30.线性表 L=(a1,a2,...,ai,...,an),下列说法正确的是( ) ①每个元素都有一个直接前驱和直接后继 ②线性表中至少要有一个元素
③表中诸元素的排列顺序必须是由小到大或由大到小的 ④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后 31.线性表的逻辑顺序与存储顺序总是一致的,这种说法() ①正确 ②不正确 32.设p,q是指针,若p=q,则*=*q,这种说法() ①正确 ②不正确 33.线性表若采用链表存储结构时,要求内存中可用存储单元的地址() ①必需是联系的 ②部分地址必须是连续的 ③一定是不连续的④连续不连续都可以 34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为 p-rean ar=rear->next rear=rear->next free (rear) free(p) Brear=rear->next->next ④p=rear->next->next free (rear) rear->next->next=p->next free(p) 35.单链表中,增加头结点的目的是为了() ①使单链表至少有一个结点②标示表结点中首结点的位置 ③方便运算的实现 ④说明单链表是线性表的链式存储实现 36线性结构中的一个结点代表一个数据元素,通常要求同一线性结构的所有结点所代表的数 据元素具有相同的特性,这意味着 ①每个结点所代表的数据元素都一样。 ②每个结点所代表的数据元素包含的数据项的个数要相等 ③不仅数据元素包含的数据项的个数要相同,而且对应数据项的类型要一致 ④结点所代表的数据元素有同一特点 37.带头结点的单链表Head为空的判定条件是 ①Head=Nu1l ②Head>next=NULL ③Head->next=Head 38.非空的单循环链表L的尾结点*P,满足 P-next=NULL P=NULL P->next=L 39.双向链表结点结构如下: LLink data RLink 其中: LLink是指向前驱结点的指针域: data是存放数据元素的数据域 Rlink是指向后继结点的指针域 下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱,插入到此双向 链表中。不能正确完成要求的算法段是 ① Q->LLink=P-Link ②P- LLink=Q Q->Rlink=P Q->RInk=P P->LLink-Q P->LLink-Rlink=Q P->LLink->Glinka Q->LLink=P->LLink ③ Q->LLink=P-Link Q->Rlink=P
8 ③表中诸元素的排列顺序必须是由小到大或由大到小的 ④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后 继 31.线性表的逻辑顺序与存储顺序总是一致的，这种说法( ) ①正确 ②不正确 32.设 p,q 是指针,若 p=q,则*p=*q ,这种说法( ) ①正确 ②不正确 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. 单链表中，增加头结点的目的是为了 ( ) ①使单链表至少有一个结点 ②标示表结点中首结点的位置 ③方便运算的实现 ④说明单链表是线性表的链式存储实现 36 线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数 据元素具有相同的特性，这意味着 ① 每个结点所代表的数据元素都一样。 ② 每个结点所代表的数据元素包含的数据项的个数要相等 ③ 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 ④ 结点所代表的数据元素有同一特点 37．带头结点的单链表 Head 为空的判定条件是 ①Head=Null ②Head->next=NULL ③Head->next=Head 38.非空的单循环链表 L 的尾结点*P,满足 P->next=NULL P=NULL P->next=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;
>LLink-Rlink=Q ->LLink=Q 40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用() 存储方式最节省时间 ①顺序表 ②单链表 ③双链表 ④单循环链表 串是任意有限个 ①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 四、简答及应用 1.请用类C语言描述顺序表,并予以解释说明 请用类C语言描述单链表的类型定义,并予以解释说明 3.请用类C语言描述双链表的类型定义,并予以解释说明 4.请用类C语言描述顺序串的类型定义。 5.请用类C语言描述链串的类型定义 6.叙述以下概念的区别:头指针变量、头指针、头结点、首结点,并说明头指针变量和头结 点的作用。 7.有哪些链表可仅由一个尾指针来惟一确定,即从尾指针出发能访问到链表上任何一个结点 8.简述下列每对术语的区别: 空串和空格串;串变量和串常量;主串和子串;串变量的名字与串变量的值。 9.设有A B="mule",C="old",D="my",试计算下列运算的结果(注:A+B是 CONCAT(A,B) 的简写,A=”"的""含有两个空格) a)A+B (c)D+C+B (d) SUBSTR (B, 3, 2) (e) SUBSTR(C, 1, 0) (f) LENGTH (A) (g) LENGTH (D) (h)INDEX (B, D) (i)INDEX(C, d") (i) INSERT(D, 2, C) (k) INSERT(B, 1, A) (1)DELETE (B, 2, 2) (m) DELETE (B, 2. 0) 10.已知:S="(xyz)*",T="(x+z)*y"。试利用连接、求子串和置换等基本运算,将S转换为T。 五、算法设计 1.设A=(a,a,a, an)和B=(b,b,..,b)是两个线性表(假定所含数据元素均为 整数)。若n=m且a:=b;(i=1,,,n),则称A=B;若a=b;(i )且a1B。是编写一个比较A和B的算法,当A<B,A书或AB是分别输 出-1,0或者1。 2,试编写在无头结点的单链表上实现线性表基本运算 LOCATE(L,Xx、 INSERT(L,X,i和 DELETE(L,ⅱ)的算法,并和在带头结点的单链表上实现相的算法进行比较。 3.试编写在不带头结点的单链表上实现线性表基本运算 LENGTH(L)的算法 4.假设有两个按数据元素值递增有序排列的线性表A和B,均以单链表作存储结构。编写算 9
9 P->LLink->Rlink=Q; P->LLink=Q; 40.若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用（ ） 存储方式最节省时间。 ①顺序表 ②单链表 ③双链表 ④单循环链表 41．串是任意有限个 ①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 四、简答及应用 1． 请用类 C 语言描述顺序表，并予以解释说明。 2． 请用类 C 语言描述单链表的类型定义，并予以解释说明。 3． 请用类 C 语言描述双链表的类型定义，并予以解释说明。 4． 请用类 C 语言描述顺序串的类型定义。 5． 请用类 C 语言描述链串的类型定义。 6.叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结 点的作用。 7．有哪些链表可仅由一个尾指针来惟一确定，即从尾指针出发能访问到链表上任何一个结点。 8．简述下列每对术语的区别： 空串和空格串;串变量和串常量;主串和子串;串变量的名字与串变量的值。 9．设有 A=” ”,B="mule"，C="old"，D="my",试计算下列运算的结果(注:A+B是CONCAT（A,B） 的简写,A=" "的 " "含有两个空格)。 (a) A+B (b) B+A (c) D+C+B (d) SUBSTR(B,3,2) (e) SUBSTR(C,1,0) (f) LENGTH(A) (g) LENGTH(D) (h) INDEX(B,D) (i) INDEX(C,"d") (j) INSERT(D,2,C) (k) INSERT(B,1,A) (l) DELETE(B,2,2) (m) DELETE(B,2,0) 10.已知:S="(xyz)*",T="(x+z)*y"。试利用连接、求子串和置换等基本运算，将 S 转换为 T。 五、算法设计 1． 设 A=（a1,a2,a3,......an）和 B=(b1,b2,.. .,bm)是两个线性表（假定所含数据元素均为 整数）。若 n=m 且 ai=bi(i=1,.. .,n),则称 A=B;若 ai=bi(i=1,.. .,j)且 aj+1B。是编写一个比较 A 和 B 的算法，当 AB 是分别输 出-1，0 或者 1。 2，试编写在无头结点的单链表上实现线性表基本运算 LOCATE(L,X)、INSERT(L,X，i)和 DELETE(L,i)的算法，并和在带头结点的单链表上实现相的算法进行比较。 3．试编写在不带头结点的单链表上实现线性表基本运算 LENGTH(L)的算法。 4．假设有两个按数据元素值递增有序排列的线性表 A 和 B，均以单链表作存储结构。编写算
法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许值相同)排列的线性表 C,并要求利用原表(即A表和B表的)结点空间存放表C 5.设有线性表A=(a,a,,,,a)和B=(b,b,.,b).试写合并A、B为线性表C的算法, 使得: j(al, bl,,am, bm, bm+l, bn)= mn 假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储结构并利 用单链表A、B的结点空间 6,设线性表存放在向量A[ arrslze]的前 plenum分量中,且递增有序。试写一算法,将X插 入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂性。 7.已知单链表L中的结点是按值非递减有序排列的,试写一算法将值为x的结点插入表L 中,使得L仍然有序。 8,试分别以顺序表和单链表作存储结构,各写一个实现线性表的就地(即使用尽可能少的附 加空间)逆置的算法,在原表的存储空间内将线性表(a1,a,,.,an)逆置为(an,,,a,a1) 9.假设分别以两个元素值递增有序的线性表A、B表示两个集合(即同一线性表中的元素各不 相同),现要求构成一个新的线性表C,C表示集合A与B的交,且C中元素也递增有序。试 分别以顺序表和单链表为存储结构,填写实现上述运算的算法。 0,已知A、B和C为三个元素值递增有序的线性表,现要求对表A作如下运算:删去那些 既在表B中出现又在表C中出现的元素。试分别以两种存储结构(一处种顺序结构,一种链式 的)编写实现上述运算的算法 1.假设在长度大于1的循环链表中,既无头结点也无头指针。s为指向链表中某个结点的 指针,试编写算法删除结点*s的前趋结点 12.已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写 算法,构造三个循环链表,使每个循环链表中只含同一类的字符,且利用原表中的结点空间 作为这三个表的结点空间(头结点可另辟空间)。 13.( Josephus环)任给正整数n、k,按下述方法可得排列1,2,……,n的一个置换:将数字 ,2,,..,n环形排列(如图算法设计题13.所示),按顺时针方向从1开始计数:计满 时输出该为之上的数字(并从环中删去该数字),然后从下一个数字开始继续计数,直到环中 所有数字均被输出为止。例如,n=10,k=3时,输出的置换是3,6,9,2,7,1,8,5,10, n-1 算法设计题13.图 4。试编写一算法,对输人的任意正整数n、k,输出相应的置换 4·在双链表上实现线性表的下列基本运算(a)初始化:(b)定位(c)插入(d)删除。 15·设有一双链表,每个结点中除有 prior、data和next三个域外,还有一个访问频度域 freq,在链表被起用之前,其值均初始化为零。每当在双链表上进行一次 LOCATEL,X)运算 时,令元素值为X的结点中freq域的值增1,并使此链表中结点保持按访问频度递减的顺序 排列,以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的 LOCATE运算的算法。 16·若X和Y是用结点大小为1单链表表示的串,设计一个算法找出X中第一个不在y中出
10 法将 A 表和 B 表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表 C，并要求利用原表(即 A 表和 B 表的)结点空间存放表 C。 5．设有线性表 A=(a1,a2,.. .,am)和 B=(b1,b2,.. .,bn).试写合并 A、B 为线性表 C 的算法， 使得： C= + + = (a1,b1,...,an,bn,an 1,...,am) m n; (a1,b1,...,am,bm,bm 1,bn) m n; 当 当 假设 A、B 均以单链表为存储结构(并且 m、n 显示保存)。要求 C 也以单链表为存储结构并利 用单链表 A、B 的结点空间。 6，设线性表存放在向量 A[arrsize]的前 elenum 分量中，且递增有序。试写一算法，将 X 插 入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。 7．已知单链表 L 中的结点是按值非递减有序排列的，试写一算法将值为 x 的结点插入表 L 中，使得 L 仍然有序。 8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附 加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2,.. .,an)逆置为(an,.. .,a2,a1)。 9．假设分别以两个元素值递增有序的线性表 A、B 表示两个集合(即同一线性表中的元素各不 相同)，现要求构成一个新的线性表 C，C 表示集合 A 与 B 的交，且 C 中元素也递增有序。试 分别以顺序表和单链表为存储结构，填写实现上述运算的算法。 10，已知 A、B 和 C 为三个元素值递增有序的线性表，现要求对表 A 作如下运算： 删去那些 既在表 B 中出现又在表 C 中出现的元素。试分别以两种存储结构(一处种顺序结构，一种链式 的)编写实现上述运算的算法。 11．假设在长度大于 1 的循环链表中，既无头结点也无头指针。s 为指向链表中某个结点的 指针，试编写算法删除结点*s 的前趋结点。 12．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写 算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间 作为这三个表的结点空间(头结点可另辟空间)。 13.(Josephus 环)任给正整数 n、k，按下述方法可得排列 1，2，……,n 的一个置换:将数字 1，2，.. .,n 环形排列(如图算法设计题 13.所示)，按顺时针方向从 1 开始 计数；计满 K 时输出该为之上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中 所有数字均被输出为止。例如，n=10,k=3 时，输出的置换是 3，6，9，2，7，1，8，5，10， 4。试编写一算法，对输人的任意正整数 n、k，输出相应的置换 14·在双链表上实现线性表的下列基本运算(a)初始化； (b)定位(c)插入(d)删除。 15·设有一双链表，每个结点中除有 prior、data 和 next 三个域外，还有一个访问频度域 freq，在链表被起用之前，其值均初始化为零。每当在双链表上进行一次 LOCATEL，X)运算 时，令元素值为 X 的结点中 freq 域的值增 1，并使此链表中结点保持按访问频度递减的顺序 排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的 LOCATE 运算的算法。 16·若 X 和 Y 是用结点大小为 1 单链表表示的串，设计一个算法找出 X 中第一个不在 y 中出
