数据库系统l试题库及答案-第2章-线性表(共13页).doc

《数据库系统l试题库及答案-第2章-线性表(共13页).doc》由会员分享，可在线阅读，更多相关《数据库系统l试题库及答案-第2章-线性表(共13页).doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第2章 线性表2.1知识点:线性表的逻辑结构一、填空题1. 线性表是一个有限序列，结点间的关系是 的。2. 线性表的存储方式分为 和 。3. 线性表中的数据元素可以是简单的数据类型，也可以由若干 组成。4. 每个操作在 层次上尚不能用具体的某种程序语言写出具体的算法，而算法只有在 确立之后才可以实现。二、选择题1. ( )线性表L=（a, a,a）,下列说法正确的是 （ ）。A 每个元素都有一个直接前驱和一个直接后继。B 线性表中至少要有一个元素。C 表中诸元素的排列顺序必须是由小到大或由大到小。D 除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直

2、接后继。2. ( )在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。 A插入 B删除 C排序 D定位3. ( )线性表是具有n 个（ ）的有限序列（n=0）。A表元素 B字符 C数据元素 D数据项 E信息项4. ( )以下不属于线性结构的是( )。 A栈 B.队列 C.串 D.二维数组 E.二叉树 三、判断题1. （ ）同一线性表的数据元素可以具有不同的特性。2. （ ）线性表的长度n就是表中数据元素的个数，当n=0时，称为空表。3. （ ）基本操作的实现可以在逻辑结构分析之后进行。2.2知识点：线性表的顺序存储结构一、填空题1. 在线性表的顺序存储结构中，元素间的逻辑关系是通

3、过 决定的。2. 在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 _有关。3. 向一个长度为n的顺序表的第i个元素(1in+1)之前插入一个元素时，需向后移动 个元素。4. 从一个长度为n的顺序表中删除第i个元素(1in)时，需向前移动 个元素。5. 在顺序表中访问任意一结点的时间复杂度均为 ，因此，顺序表也称为 的数据结构。6. 线性表的顺序存储是用一组 连续的空间单元实现数据元素的存储，逻辑上相邻的元素的物理位置 相邻。7. 向一个长度为n的顺序表中任意位置插入一个元素所需移动的平均次数为 。8. 从一个长度为n的顺序表中删除任意一个元素所需移动的平均次数为 。二、

4、选择题1. ( )1.数据在计算机存储器内表示时，物理地址与逻辑地址相同并连续，称之为( )。 A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构2. ( )顺序表第一个元素的存储地址是100，每个元素长度为2，则第5个元素的地址是( )。 A.110 B.108 C.100 D.1203. ( ) 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是( )。A. 访问第i个结点（1in）和求第i个结点的直接前驱（2in） B. 在第i个结点后插入一个新结点（1in）C. 删除第i个结点（1in）D. 将n个结点从小到大排序4. ( )若某线性表中最常用的操作是取第i 个元素和

5、找第i个元素的前驱元素，则采用( ) 存储方式最节省时间。 A.单链表 B.双链表 C.单向循环 D.顺序表5. ( )下述哪一条是顺序存储结构的优点（ ）。 A存储密度大 B插入运算方便 C删除运算方便 D按照序号定位 6. ( )若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（ ）（1=i=n+1）。AO（0） BO（1） CO（n） DO（n）三、判断题1. （ ）从长度为n的顺序表中删除任何一个元素，时间复杂度都是O(n)。2. （ ）顺序表中任意一个数据元素的地址都可以通过计算得到。3. （ ）存放顺序表的数据元素的地址空间可以连续也可以不连

6、续。4. （ ）在顺序表中按值进行查找的时间复杂度是O(n)。5. （ ）顺序存储方式的特点是存储密度大且插入和删除运算效率高。四、简答题1已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：void f30 （SqList &L） int i，j;for （i=j=0;i=0）if（i!=j）Lj=L.elemi;j+；L.length=j;（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30（&L）后的L状态；（2）简述算法f30的功能。四、算法设计题1.设计一个算法从一给定的有序顺序表L中删除元素值在x到y（xnext; p-data=q-da

7、ta; ; free（p）;9. 带头结点的单链表head为空的判定条件是 。10. 在一个单链表head中，已知p指向某个非终端节点，若要删除其后的一个结点则执行的运算是 。二、选择题1. （ ）链表是一种采用（ ）存储结构存储的线性表。 A.顺序 B.链式 C.星式 D.网状2. （ ）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以3. （ ）线性表在（ ）情况下适用于使用链式结构实现。 A.需经常修改中的结点值 B.需不断对进行删除插入 C.中含有大量的结点 D.中结点结构复杂4.

8、（ ）单链表的存储密度（ ）。 A.大于1 B.等于1 C.小于1 D.不能确定5. （ ）单链表不具备的特点是（ ）。 A.可随机访问任一节点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比6. （ ）设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执 行的三条语句是（ ）；r=s;r-next=null;。 A.r-next=s; B.s-next=r; C.s-next=null; D.s=r;7. ( ) 在一个单链表中,q为p的前驱结点，要删除p所指结点时，应执行以下操作（ ）。 A. q=p-next; B.p-next=q-

9、next; C.p-next=q; D.q-next=p-next8. （ ）完成在双循环链表结点p之后插入s的操作是（ ）。 A.p-next=s ; s-prior:=p; p-next-prior:=s ; s-next=p-next; B.p-next-prior=s; p-next=s; s-prior=p; s-next:=p-next; C.s-prior=p; s-next=p-next; p-next=s; p-next-prior=s ; D.s-prior=p; s-next=p-next; p-next-prior=s ; p-next=s;9. ( ) 某线性表中最常

10、用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采 用（ ）存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表10. ( )以下说法错误的是（ ）。A求表长、定位两种运算在采用顺序存储结构时的时间复杂度为O(n) B顺序存储的线性表可以随机存取 C由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活D线性表的链式存储结构优于顺序存储结构11. 在一个双链表中，删除p结点（非尾结点）之后的一个结点的操作是（ ）。Ap-next=p-next-next; p-next-next-prior=p;B. p-next-prior

11、=p;p-next=p-next-next;C. p-next=p-next-next; p-next-prior=p;D. p-next-next=p-next; p-next-prior=p;12. 在带头结点的循环单链表中，至少有一个结点的条件是（ ）,其尾结点p的条件是( )。 AL-next！=NULL B.L-next!=L C. p=NULL D. p-next=L 三、判断题1. （ ）线性表的逻辑顺序与存储顺序总是一致的。2. （ ）在单链表中存取某个元素，只要知道指向该元素的指针，因此单链表是随即存取的存储 结构。3. （ ）在顺序表中存取某个元素，需要按照顺序进行，因此顺

12、序表是顺序存取的存储结构。4. （ ）单链表从任何一个结点出发，都能访问到所有结点。四、简答题1.描述以下三个概念的区别：头指针.头结点.首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？2. 试比较线性表的两种存储结构的优缺点。在什么情况下用顺序表比链表好？五、算法设计题1试写一算法，对单链表实现就地逆置。2设计一个算法，求A和B两个单链表表示的集合的交集、并集和差集，单链表中的数据递增有序排列。要求分别按照共用原有空间和重新申请空间两种方案分别设计算法。3 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素

13、（ 若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。第2章 线性表2.1知识点:线性表的逻辑结构一、填空题1. 一对一 2. 顺序存储 链式存储 3. 数据项_ 4. 逻辑结构 存储结构二、选择题1. D 2. D 3C 4.E三、判断题1. 2. 3. 2.2知识点：线性表的顺序存储结构一、填空题1. 物理存储位置 2. 表中一半 表长和该元素在表中的位置 3. n-i+1 4. n-I 5. O(1) 随机存取6. 地址 必定 7.（n+1）/2 8.n/2 二、选择题1.C

14、2.B 3.A 4.D 5.AD 6.C三、判断题1. 2. 3. 4. 5. 四、答题1（1）（21，19，0，34，30） （2）功能是选出线性表中大于等于零的数。四、算法设计题1. void delete(SqList &L,ElemType x,ElemType y) int i=0,k=0; while(i=x &L.elemi=y) k+; /记录被删记录的个数 else L.elemi-k=L.elemi; /前移k个位置 i+; L.length=L.length-k;2. void move(SqList &L) int i=0,j=L.length-1; int temp;

15、 while(ij) /使得正数都在前半部分，负数都在后半部分 while(i0)i+; while(ij&L.elemj0)j-; if(ij) /交换L.elemi(负数)和L.elemj(正数) temp=L.elemi; L.elemi=L.elemj; L.elemj=temp; i=1; while(iL.length/2) /通过交换使得正负数相间 j=L.length-2; temp=L.elemi; L.elemi=L.elemj; L.elemj=temp; i=i+2; j=j-2; 3.交集:void intersection(SqList A,SqList B ,Sq

16、List &C) int i=0,j=0,k=0; while(iA.length&jB.length) if(A.elemiB.elemj) j+; else C.elemk=A.elemi; k+;i+;j+; /共同的元素 C.length=k;并集:void Union(SqList A,SqList B ,SqList &C) int i=0,j=0,k=0; while(iA.length&jB.length) if(A.elemiB.elemj) C.elemk=B.elemj;k+;j+; else C.elemk=A.elemi; k+;i+;j+; /共同的元素只放一个 w

17、hile(iA.len)C.elemk=A.elemi;k+;i+ while(jB.len)C.elemk=B.elemj;k+;j+ C.length=k;差集:void differnce(SqList A,SqList B ,SqList &C) int i=0,j=0,k=0; while(iA.length&jB.length) if(A.elemiB.elemj) j+; else i+;j+; /共同的元素只放一个 while(iA.length)C.elemk=A.elemi;k+;i+ C.length=k;4. void fun(SqList &L) int i=,j=L

18、.length-1; while(i=j)while(L.elemi=0) j-;if(ij) /L.elemi 和 L.elemj 交换 temp= L.elemi;L.elemi= L.elemj;L.elemj=temp; 5. merge(SqList &A ,int m,int n) int i=0,j=m,k; while(jA.length&iA.elemj-1) /整个表已经递增有序，退出循环 break;else if(A.elemj=i;k-) /将A.elemi及之后的元素后移 A.elemk+1= A.elemk； A.elemi=temp; /将A.elemj插入到i

19、处 i+; j+;else i+;本算法的时间复杂度为O(m*n) ，空间复杂度为O（1）。2.3知识点：线性表的链式存储结构一、填空题1. 链域的指针值 2. 其直接前驱结点的链域的值 3. 前驱结点的地址 O（n） 4. 前驱结点 后继结点 5. s-next=p-next; p-next=s; 6. O(1) O(n) 7. L-next=L 8. p-next=q-next; 9.head-next=NULL 10.q=p-next;p-next=q-next;free(q);二、选择题 1.B 2.D 3.B 4.C 5.A 6.A 7.D 8.D 9.D 10.D 11.C 12.

20、BD 三、判断题1. 2. 3. 4. 四、简答题1. 答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表.非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表.双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。 头结点headdatalink 头指针

21、首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。2. 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（nex

22、t; /p指向单链表第一个结点L-next=NULL; /形成空的单链表while(p) /采用头插入法将p结点插入到头结点的后面实现逆置q=p;p=p-next;q-next=L-next;L-next=q;return OK;2并集：LinkList Bingji(LinkList &Head1,LinkList &Head2,LinkList &Head3) LNode *p1=Head1-next; LNode *p2=Head2-next;LNode *p3=Head3=Head1;while(p1 & p2) if(p1-data data) p3-next =p1; p3=p3-

23、next ; p1=p1-next ; else if(p1-data p2-data) p3-next =p2; p3=p3-next ; p2=p2-next ; else p3-next = p1; p3=p3-next ; p1=p1-next ; q=p2; free(q); p2=p2-next ; p3-next =(p1)?p1:p2;free(Head2);return Head3; 交集：LinkList Jiaoji(LinkList &Head1,LinkList &Head2,LinkList &Head3) LinkList pa,pb,r,p; pa=Head1-

24、next;pb=Head2-next; r=Head3=Head1;while(pa&pb)if(pa-datadata) r-next =pa-next ; free(pa); pa=r-next ;elseif(pa-datapb-data)pb=pb-next;elser-next=pa; r=pa;pa=pa-next;while(pa) r-next =pa-next ;free(pa); pa=r-next ; while (Head2-next) /释放Head2链表所有的结点空间 p=Head2-next; Head2-next=p-next; free(p); return

25、Head3; 差集：LinkList Chaji(LinkList &Head1,LinkList &Head2,LinkList &Head3) LinkList pa,pb,r,p; pa=Head1-next;pb=Head2-next; r=Head3=Head1;while(pa&pb)if(pa-datadata) r-next=pa; r=r-next; pa=pa-next;elseif(pa-datapb-data)pb=pb-next;elser-next=pa-next; free(pa);pa=r-next; while (Head2-next) /释放Head2链表所有的结点空间 p=Head2-next; Head2-next=p-next; free(p); return Head3;3Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk)LinkList p,q,prev=NULL;if(minkmaxk)return ERROR;pre=L;p=pre-next; /pre是p的前驱，p是pre的后继while(p&p-datanext; /while while(p&p-datanext=p-next; free(p); p=pre-next;return OK;专心-专注-专业