数据结构复习内容

《数据结构复习内容》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1.2习题1.2.1基础题单项选择题2．在数据结构中，数据的基本单位是_________。CA.数据项B.数据类型C.数据元素D.数据变量3．数据结构中数据元素之间的逻辑关系被称为______。DA.数据的存储结构B.数据的基本操作C.程序的算法D.数据的逻辑结构4．在数据结构中，与所使用计算机无关的是数据的_______。CA.存储结构B.逻辑和物理结构C.逻辑结构D.物理结构5．在链式存储结构中，数据之间的关系是通过________体现的。BA.数据在内存的相对位置B.指示数据元素的指针C.数据的存储地址D.指针7．计算算法的时间复杂度是属于一种___

2、____。BA.事前统计的方法B.事前分析估算的方法C.事后统计的方法D.事后分析估算的方法8．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_______。DA.n2B.nlognC.nD.logn9．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_______。DA.O(1)B.O(n)C.O(200n)D.O(nlog2n)31第二章2.2习题2.2.1基础题单项选择题1．链表不具有的特点是________。AA.可随机访问任一元素B.插入和删除时不需要移动元素C.

3、不必事先估计存储空间D.所需空间与线性表的长度正比3．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。CA.139B.140C.147D.1485．在线性链表存储结构下，插入操作算法。CA.需要判断是否表满B.需要判断是否表空C.不需要判断表满D.需要判断是否表空和表满7．在一个单链表中，若删除p所指结点的后继结点，则执行。AA.p->next=p->next->next;B.p->next=p->next;C.p=p->next->next;D.p=p->next;p->next=p->next

4、->next;9．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。BA.O(n)B.O(1)C.O(m)D.O(m+n)13．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。BA.单链表B.静态链表C.线性链表D.顺序存储方式填空题2．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。前驱5．在单链表中，指针p所指结点为最后一个结点的条件是。p->next==NULL7．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。19．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一

5、个元素时，需向后移动元素的个数是。n-i+110．在长度为n的顺序表中插入一个元素的时间复杂度为。O(n)2.1.3例题解析【例2-1】编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。实现本题功能的函数如下：31voidinverse(Lnode*h){s=h->next;if(s==NULL)return;q=NULL;p=s;while(p!=NULL){p=p->next;s->next=q;

6、/*逆转指针*/q=s;/*指针前移*/s=p;}h->next=q;/*头指针h的后继是p*/}【例2-2】编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c表尾。当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c表尾。设pa、pb分别指向两表当前结点，p指向c表的当前表尾结点。若设A中当前所指的元素为a，B中当前所指的元素为

7、b，则当前应插入到C中的元素c为例如：A=(3,5,8,11)B=(2,6,8,9,11,15,20)则C=(2,3,5,6,8,8,9,11,11,15,20)实现本题功能的函数如下：Lnode*hb(Lnode*pa,Lnode*pb){Lnode*p,*q,*pc;pc=(Lnode*)malloc(sizeof(Lnode));/*建立表c的头结点pc*/p=pc;/*p指向C表头结点*/while(pa!=NULL&&pb!=NULL){q=(Lnode*)malloc(sizeof(Lnode));/*建立新结点q*/if(pb->data

8、a->data)/*比较A、B表中当前结点的数据域值的大小*/{q