数据结构（含实训）——c语言版（习题案例库）

《数据结构（含实训）——c语言版（习题案例库）》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构(含实训)一语言版一、填空题1.在双链表中要删除已知结点*s,其时间复杂度为0(1)2.循环队列用数组data[max]存放其元素值，已知其头、尾指针分别是和rear,则当前队列中元素的个数是一(m+rear・front)%m。3.具有12个结点的完全二叉树的叶结点冇6个。4.在任何一棵二叉树屮，度为0的结点nO和度为2的结点n2之间的关系是_n0=n2+l。5.己知完全二义树的第4层有4个结点，则其叶子结点数是6。6.在仅有尾指针rear指示的单循环链表rear屮，在表尾插入-个结点s的语句序列是s・>next=rea「>next;rear->next=s。7.栈

2、顶的位置是随着一入栈出栈操作而变化的。8.数据结构一般包括三个方而的内容:数据的逻辑结构、数据的存储结构及对数据的运算。9.假设以S和X分别表示进栈和岀栈操作，则对输入序列1,2,3,4,5进行一系列栈操作SSXSXSSXXXZ后，得到的输出序列为bceda。10.数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关,是独立于计算机的。11.在带头结点的双链表head中，指针p所指结点是开始结点的条件是p・>prior==head。12.在选择排序、堆排序、快速排序、直接插入排序中，稳定的排序方法是宜接插入排序。13.在具有n个结点的双链表中做插入、删除运算，平均时

3、间复杂度为am。14.队列的队尾位置随着入队而变化。15.快速排序在最坏情况卜的时间复杂度是Q(n!)。16.n(n>0)个顶点连通无向图的生成树恰有n・l条边。17.在一个长度为n的顺序表中第i个元素(1WiWn+1)之前插入一个元索时，需向后移动n・i+l个元素。18.在只有•个数据元素的情况下,链队列的出队操作需要修改尾指针。19.数据结构是相互之间存在一种或多种特定关系的数据元索的集合，它包括三方面的内容，分别是数据的逻辑结构、数据的物理结构和数据的运算。20.在双循环链表中，若要在指针p所指结点Z前插入指针s所指的结点，则需执行下列语句：s->prior=D->p

4、rior;p->prior->next=s;s->next=p;ffp->prior=s;。21.从栈顶指针为top的链栈中删除一个结点，并将被删除的结点的值保存在x中，•其操作步骤为x=top->data；top=top->next；o22.用数组A[m]来存放循环队列q的元素,且它的头、尾指针分别为front和rear,队列满足条件(q->rcar+1)%m=q->front,则队列中当前的元索个数为m-1o0A・11B02C03D14E2s->prior=p；23.深度为6的二叉树最多有鱼个结点。24.右图为某树的静态双亲表示，则结点D、E的双亲结点分别为B和C。25

5、.已知指针p指向双向链表中的一个结点(非首结点、非尾结点),则将结点s插入在p结点的玄接后继位置的语句是s・>next=D・>next；s->next->prior=s；p->next=s；1.一个二叉树中，度为2的结点有3个，则叶结点有生个。2.顺序栈s存储在数组s->data[max]中，对s进行出栈操作，执行的语句序列是x=s・>data

6、~s・>topl;s・>top—;。3.以卜-运算实现在循坏队列屮的初始化操作voidinitqueue(seqqueue*q){q・>fi*ont=0;q・>rear=0;}4.若二叉树的一个叶了是某了树的中序遍历序列中的第一个结

7、点，则它必是该了树的后根遍历序列中的筆二个结点。5.对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的左子树上继续查找。6.数据的逻输结构与数据元素木身的内容和形式无关。7.程序段“fbr(i=l;i<=n;i卄){k++；for(j=l;j<=n;j++)x=x+k;}"的时间复杂度)=0(()。8.已知带表头结点的单链表L,指针p指向L链表屮的一个结点(非首结点、非尾结点),贝IJ：删除结点D的直接后继结点的语句是D・>next二D・>next・>next；删除首结点的语句是L=L->nexto9.二叉树通常有顺序存储结构和链式存储结构两种

8、。10.二义树在二叉链表表示方式下，p指向二叉树的根结点，经运算s=p；while(s->rchild)s=s->rchild后,s指针指向右了树最右结点。11.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是血)。二、选择题1.下列算法的时间复杂度是(B)。fbr(i=l;i<=n;i4-+)c[i]=i；A、0(1)B>O(n)C、O(log2n)D、O(nlog2n)2.在表长为n的顺序表上做插入运算，平均要移动的结点数为(B)oA、nn/2C>n/3D、n/43.在一个单链表中，若P所指结点不