第二章线性表
一．名词解释
1.线性结构
2.数据结构的顺序实现
3.顺序表
4.链表
5.数据结构的链接实现
6. 建表
7.字符串
8.串
9.顺序串 10.链串
二、填空题
1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a
1，a
2
,……a
n
)，其中每
个a
i 代表一个______。a
1
称为______结点，a
n
称为______结点，i称为a
i
在线性表中的________
或______。对任意一对相邻结点a
i 、a
i┼1
(1<=i i 称为a i┼1 的直接______a i┼1 称为a i 的直 接______。 2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为______或______。 3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______. 4.所有结点按1对1的邻接关系构成的整体就是______结构。 5.线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称______. 6.表长为O的线性表称为______ 7.线性表典型的基本运算包括:______、______、______、______、______、______等六种。 8.顺序表的特点是______。 9.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点a i 的存储地址为______。 10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 Void insert_sqlist(sqlist L，datatype x，int i) /*将X插入到顺序表L的第i-1个位置*/ { if( https://www.doczj.com/doc/f29759620.html,st == maxsize) error(“表满”)； if((i<1)||(i>https://www.doczj.com/doc/f29759620.html,st+1))error(“非法位置”); for(j=https://www.doczj.com/doc/f29759620.html,st;j>=i;j--)______; L.data[i-1]=x; https://www.doczj.com/doc/f29759620.html,st=https://www.doczj.com/doc/f29759620.html,st+1; } 11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________，平均时间复杂性量级是________。 12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/ {if((i<1)||(i>https://www.doczj.com/doc/f29759620.html,st))error(“非法位置”)； for(j=i+1;j=https://www.doczj.com/doc/f29759620.html,st;j++)________; https://www.doczj.com/doc/f29759620.html,st=https://www.doczj.com/doc/f29759620.html,st-1; } 13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________ 和________。 14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ {________; while((i≤https://www.doczj.com/doc/f29759620.html,st)&&(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*/ { 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.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 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->data是一个数据元素，p->next的值是一个指针 11.单链表的一个存储结点包含（） ①数据域或指针域 ②指针域或链域 ③指针域和链域 ④数据域和链域 12.对于单链表表示法，以下说法错误的是（） ①数据域用于存储线性表的一个数据元素 ②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 ③所有数据通过指针的链接而组织成单链表 ④NULL称为空指针，它不指向任何结点，只起标志作用 13.对于单链表表示法，以下说法错误的是（） ①指向链表的第一个结点的指针，称为头指针 ②单链表的每一个结点都被一个指针所指 ③任何结点只能通过指向它的指针才能引用 ④终端结点的指针域就为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=(a 1,a 2 ,...,a i ,...,a n ),下列说法正确的是( ) ①每个元素都有一个直接前驱和直接后继 ②线性表中至少要有一个元素 ③表中诸元素的排列顺序必须是由小到大或由大到小的 ④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 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是指向后继结点的指针域。 下面给出的算法段是要把一个新结点*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．请用类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=（a 1,a 2 ,a 3 ,......a n ）和B=(b 1 ,b 2 ,.. .,b m )是两个线性表（假定所含数据元素均为 整数）。若n=m且a i =b i (i=1,.. .,n),则称A=B;若a i =b i (i=1,.. .,j)且a j+1 j+1 （j 称A 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 1,a 2,.. .,a m )和B=(b 1,b 2,.. .,b n ).试写合并A 、B 为线性表C 的算法，使得： C=???>+<=+n; m )am ,...,1an ,bn ,an ,...,1b ,1a (;n m )bn ,1bm ,bm ,am ,...,1b ,1a (当当 假设A 、B 均以单链表为存储结构(并且m 、n 显示保存)。要求C 也以单链表为存储结构并利用单链表A 、B 的结点空间。 6，设线性表存放在向量A[arrsize]的前elenum 分量中，且递增有序。试写一算法，将X 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。 7．已知单链表L 中的结点是按值非递减有序排列的，试写一算法将值为x 的结点插入表L 中，使得L 仍然有序。 8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a 1，a 2,.. .,a n )逆置为(a n ,.. .,a 2,a 1)。 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 中出 现的字符。 17．在顺序串上实现串的判等运算EQUAL(S,T)。 18．在链串上实现判等运算EQUAL(S,T)。 19．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。 20．用串的其他运算构造串的子串定位运算index。 第2章线性表 一、选择题 1. 链表不具备的特点是（）。 A．可随机访问任意结点 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件是（）。 ==NULL B. head->next==NULL >next==head !=NULL 3.带头结点的单链表head为空的判定条件是（）。 ==NULL B. head->next==NULL >next==head !=NULL 4．带头结点的双循环链表L为空表的条件是（）。 A．L==NULL B．L->next->==NULL C．L->prior==NULL >next==L 5.非空的循环链表head的尾结点（由P所指向）满足（）。 A．p->next==NULL B．p==NULL C．p->next==head ==head 6.在循环双链表的p所指结点之前插入s所指结点的操作是（）。 A．p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior; B．p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior; C．s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s; D. s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。 A．单链表 B．给出表头指针的单循环链表 C．双链表 D. 带头结点的双循环链表 8.某线性表最常用的操作是在最后一个结点之后插入一个节点或删除第一个结点，故采用（）存储方式最节省运算时间。 A．单链表 B．仅有头结点的单循环链表 C．双链表 D. 仅有尾指针的单循环链表 9.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（）。 A．单链表 B．静态链表 C．线性链表 D. 顺序存储结构 10.如果最常用的操作是取第i个结点及前驱，则采用（）存储方式最节省时间。 A．单链表 B．双链表 C.单循环链表 D.顺序表 11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。 A．O(1) B．O(n) C．O(n*n) D. O(nlog2n) 12.在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行()操作与链表的长度有关。A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 13.设线性表有n个元素，以下算法中，()在顺序表上实现比在链表上实现效率更高。A．输出第i(0<=i<=n-1)个元素值 B．交换第0个元素与第1个元素的值 C. 顺序输出这n个元素的值 D.输出与给定值x相等的元素在线性表中的序号 14.设线性表有2n个元素，算法()，在单链表上实现比在顺序表上实现效率更高。 A．删除所有值为x的元素 B．在最后一个元素的后面插入一个新元素 C. 顺序输出前k个元素 D.交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1) 实验一线性表的基本操作 一、实验目的与基本要求 1．掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。 2．了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。 3．掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4．掌握运用C语言上机调试线性表的基本方法。 二、实验条件 1．硬件：一台微机 2．软件：操作系统和C语言系统 三、实验方法 确定存储结构后，上机调试实现线性表的基本运算。 四、实验内容 1．建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 2．建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。 3．假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4．假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。 五、附源程序及算法程序流程图 1.源程序 （1）源程序(实验要求1和3) #include 数据结构练习题1 指导老师：常璐璐 姓名：邢莉彬 学校：滨州学院 院系：信息工程学院软件技术 填空题 1. 对于一个n个结点的单链表，在表头插入元素的时间复杂度为_____O(1)_____，在表尾插入元素的时间复杂度为_____O(n)_____。 2. 删除非空线性链表中由q所指的链结点（其直接前驱结点由r指出）的动作时执行语句___r->link=q->link_______和______free(q)____。 结点结构为 typedef struct Node{ int value; node * link; }node; 3. 非空线性链表中，若要在由p所指的链结点后面插入新结点q，则应执行语句____ q->link=p->link;______和_____ p->link=q;_____。 结点结构为 typedef struct Node{ int value; node* link; }node; 4. 线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____(n-1)/2_____。 5. 在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动_____ n-i+1_____ 个元素。 6.在具有n个链结点的链表中查找一个链结点的时间复杂度为O(_______n___)。 7. 线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为_____O（n）_____；而在链式存储方式下，插入和删除操作的时间复杂度都是____O(1)______ 。 8. 若某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第10个元素的存储地址为____136______。 选择题 1. 对于一个带头结点的单链表，头指针为head，判定该表为空的条件是________B__。 A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL 2. 将长度为m的线性链表链接在长度为n的线性链表之后的过程的时间复杂度若采用大O形式表示，则应该是______B____。 A．O(m) B．O(n) C．O(m+n) D．O(m-n) 3.在包含1000个数据元素的线性表中，实现如下4个操作所需要的执行时间最长的是______A____ 。 第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior; 7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是。 A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q; B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next; C、q－＞prior=p; q－＞next=p－＞next; p－＞next－＞prior=q; p－＞next=q; D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q; 8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用 第二章线性表 1、描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。 2、对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i 个结点a i ； (2)定位到第i 个结点的前驱a i-1； (3)定位到尾结点； (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点；(2)在P 结点前插入S 结点；(3)在表首插入S 结点；(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && j 4、设计算法：在顺序表中删除值为e 的元素，删除成功，返回1；否则，返回0。 5、设计一个算法，将一个带头节点的数据域依次为a 1，a 2，…，a n （n ≥3）的单链表的所有节点逆置，即第一个节点的数据域变为a n ，…，最后一个节点的数据域为a 1。（注意：先用自然语言描述算法基本思想，然后用类C++语言描述） int Sqlist 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 第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. 下面的叙述不正确的是（） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 7. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 8. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 9．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i） B．O（1） C．O（n） D．O（i-1） 10．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 11．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、判断 1. 链表中的头结点仅起到标识的作用。( ) 2. 顺序存储结构的主要缺点是不利于插入或删除操作。( ) 3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 5. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 6．集合与线性表的区别在于是否按关键字排序。( ) 7. 线性表的特点是每个元素都有一个前驱和一个后继。( ) 第二章线性表 2.1 填空题 (1)一半插入或删除的位置 (2)静态动态 (3)一定不一定 (4)头指针头结点的next 前一个元素的next 2.2 选择题 (1)A (2) DA GKHDA EL IAF IFA(IDA) (3)D (4)D (5) D 2.3 头指针：在带头结点的链表中，头指针存储头结点的地址；在不带头结点的链表中，头指针存放第一个元素结点的地址； 头结点：为了操作方便，在第一个元素结点前申请一个结点，其指针域存放第一个元素结点的地址，数据域可以什么都不放； 首元素结点：第一个元素的结点。 2.4已知顺序表L递增有序，写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 void InserList(SeqList *L,ElemType x) { int i=L->last; if(L->last>=MAXSIZE-1) return FALSE; //顺序表已满 while(i>=0 && L->elem[i]>x) { L->elem[i+1]=L->elem[i]; i--; } L->elem[i+1]=x; L->last++; } 2.5 删除顺序表中从i开始的k个元素 int DelList(SeqList *L,int i,int k) { int j,l; if(i<=0||i>L->last) {printf("The Initial Position is Error!"); return 0;} if(k<=0) return 1; /*No Need to Delete*/ if(i+k-2>=L->last) L->last=L->last-k; /*modify the length*/ 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 一、单选题（每题2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？(B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（ D ）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（A）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（D ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为____O(1)_____，在表尾插入元素的时间复杂度为____O n________。 《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求： 线性表 一、选择题 1.线性表是（ A ） A．一个有限序列，可以为空B．一个有限序列，不可以为空 C．一个无限序列，可以为空D．一个无限序列，不可以为空 2.一维数组与线性表的特征是（ C ）。 A．前者长度固定，后者长度可变B．两者长度均固定 C．后者长度固定，前者长度可变D．两者长度均可变 3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( B ). A．当前结点所在地址域B．指针域 C．空指针域D．空闲域 4.用链表表示线性表的优点是（ B ）。 A．便于随机存取 B．便于进行插入和删除操作 C．占用的存储空间较顺序表少 D．元素的物理顺序与逻辑顺序相同 5.在具有 n 个结点的单链表中，实现__A _的操作，其算法的时间复杂度都是O（n）。 A．遍历链表和求链表的第i个结点 B．在地址为P的结点之后插入一个结点 C．删除开始结点 D．删除地址为P的结点的后继结点 6.下面关于线性表的叙述中，错误的是（ B ）。 A．线性表采用顺序存储必须占用一片连续的存储单元 B．线性表采用顺序存储便于进行插入和删除操作 C．线性表采用链式存储不必占用一片连续的存储单元 D．线性表采用链式存储便于进行插入和删除操作 7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。现要将指针 q 指向的新结点插入到指针 p 指 向的结点之后，下面的操作序列中正确的是（ C ）。 A . q = p->next; p->next = q->next ; B . p->next = q->next; q = p->next ; C . q->next = p->next; p->next = q ; D . p->next = q; q->next = p->next ; 第二章线性表习题 判断题 1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（） 选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) （A）110 （B）108 （C）100 （D）120 3. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 （A）64 （B）63 （C）63.5 （D）7 4.线性表采用链式存储结构时，其地址（）。 (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（） （A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s; （C）s->next=p->next;p=s; （D）p->next=s;s->next=p; 6.在一个单链表中，若删除p所指结点的后续结点，则执行（） （A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next; （C）p->next=p->next; （D）p =p->next->next; 7.下列有关线性表的叙述中，正确的是（） （A）线性表中的元素之间隔是线性关系 （B）线性表中至少有一个元素 （C）线性表中任何一个元素有且仅有一个直接前趋 （D）线性表中任何一个元素有且仅有一个直接后继 8.线性表是具有n个（）的有限序列（n≠0) （A）表元素（B）字符（C）数据元素（D）数据项 填空题 1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：( ) 。 2.顺序表中逻辑上相邻的元素物理位置(一定 )相邻，单链表中逻辑上相邻的元素物理位置( )相邻。 《数据结构》第二章练习题 1.单项选择题 2.1链表不具备的特点是（） A 可随机访问任一结点 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与其长度成正比 2.2 不带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.3带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.4 带头结点的双循环链表L为空的条件是（） A L==NULL B l->next->==NULL C L->prior==NULL D L->next==L 2.5 非空的循环单链表head尾结点（由P所指向）满足（) A P->next==NULL B P==NULL C P->next==head D P==head 2.6在双循环链表中的P所指结点之前插入s所指结点的操作是（） A p->prior=s;s->next=p;p->prior>next=s;s->prior=p->prior; B p->prior=s;p->prior>next=s;s->next=p;s->prior=p->prior; C s->next=p;s->prior=p->prior; p->prior=s;p->right->next=s; D s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 2.7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间 A 单链表 B 给出表头指针的单循环链表 C 双链表 D 带头结点的双循环链表 2.8某线性表最常用的操作时在最后一个结点之后插入一个结点或删除第一个结点，故采用（）存储方式最节省运算时间 A 单链表B仅有头结点的单循环链表 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node 一、判断题 1. 线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2. 顺序存储的线性表可以按序号随机存取。(TRUE) 3.顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。TRUE) 4.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。(TRUE) 5，在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(FALSE ) 6.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。(TRUE) 7.线性表的链式存储结构优于顺序存储结构。(FALSE ) 8. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。(TRUE) 9.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。(TRUE) 10.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(FALSE ) 二．选择题 11．线性表是()。 (A)一个有限序列，可以为空； (B)一个有限序列，不能为空； (C)一个无限序列，可以为空； (D)一个无序序列，不能为空。答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A)n/2(B)(n+1)/2(C)(n–1)/2(D)n答：A 13．线性表采用链式存储时，其地址()。 (A)必须是连续的；(B)部分地址必须是连续的；(C)一定是不连续的；(D)连续与否均可以。答：D 14．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同答：C 15.单链表中，增加一个头结点的目的是为了（）。 第二章测试试题 班级：学号：姓名：成绩： 一、选择题（每小题5分） 1.线性表是( A )。 A一个有限序列，可以为空；B一个有限序列，不能为空； C一个无限序列，可以为空；D一个无序序列，不能为空。 2.用链表表示线性表的优点是（C）。 A便于随机存取 B花费的存储空间较顺序存储少 C便于插入和删除 D数据元素的物理顺序与逻辑顺序相同 3.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表 4.带头结点的单链表head为空的判定条件是（B ）。 A.head==NULL; B.head->next==NULL; C.head->next==head; D.head!=NULL; 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（C ）。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s; s->next=q; 二、填空题（每小题5分） 1．给定有n个结点的向量，建立一个单链表的时间复杂度_______。建立一个有序单链表的时间复杂度_______。 2．从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。 3．在一个长度为n的线性表（采用顺序存储结构）中删除第i个元素(1≤i≤n)时，需向前移动____个元素。 4．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_____存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。5．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的个元素。 三、算法设计题（每小题25分） 1．设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，允许在原表的存储空间外再增加一个附加的工作单元。 2．已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA 和HB中，编写一个函数求出这两个集合的并集C，并要求集合C的链表的结点仍依元素值递增有序存放。（注意：并集不是归并） 试卷一 一、单选题（每题 2 分，共20分） 1. 对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 7. 若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 二、填空题（每空1分，共28分） 1. 数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。 2. 队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0_____________。 4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 7. 二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为数据结构第二章试题
C语言数据结构线性表的基本操作实验报告
数据结构线性表习题1
第2章线性表习题解析(答)
数据结构第二章线性表测试题
数据结构_实验1_线性表的基本操作
数据结构练习题-线性表
DS第二章-课后习题答案
数据结构实验一题目一线性表实验报告
数据结构试题及答案
数据结构线性表实验报告
数据结构-线性表-习题
第二章 线性表习题
数据结构第二章练习题 - 副本
《数据结构》实验一 线性表及其应用
数据结构_线性表练习题
第二章线性表测试题
数据结构试题及答案修2
相关主题
文本预览