《最新数据结构练习题 第二章线性表 习题及答案》由会员分享，可在线阅读，更多相关《最新数据结构练习题 第二章线性表 习题及答案（16页珍藏版）》请在金锄头文库上搜索。
1、最新数据结构练习题 第二章 线性表 习题及答案 第二章线性表 一名词解释 1.线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现 6. 建表 7.字符串 8.串 9.顺序串 10.链串 二、填空题 1.为了便于讨论，有时将含n(n=0)个结点的线性结构表示成(a1，a2,a n)，其中每个a i代表一个_。a1称为_结点，a n称为_结点，i称为a i在线性表中的_或_。对任意一对相邻结点a i、a i1(1=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点a i的存储地址为_。 10.以下为顺序表的插入运算，分析算法，请在_
2、处填上正确的语句。 Void insert_sqlist(sqlist L，datatype x，int i) /*将X插入到顺序表L的第i-1个位置*/ if( st = maxsize) error(“表满”)； if(i st+1)error(“非法位置”); for(j= st;j=i;j-)_; L.datai-1=x; st= st+1; 11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为_，量级是_。插入算法的平均时间复杂性为_，平均时间复杂性量级是_。 12.以下为顺序表的删除运算，分析算法，请在_处填上正确的语句。
3、void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/ if(i st)error(“非法位置”)； for(j=i+1;j= st;j+)_; st= st-1; 13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是_和_,其平均时间复杂性及其量级分别为_ 和_。 14.以下为顺序表的定位运算，分析算法，请在_处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否
4、则回传0*/ _; while(i st)&(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) /*求表head的长度*/ _; j=0; while(
6、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*
7、/ 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,dataty
8、pe 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!
9、=$) _; _; 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在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为_。 3
