数据结构与算法作业

《数据结构与算法作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构与算法》作业说明：1、题号形式:每题都以【sn，cha，sec】开头，sn表明本题的题目序号，每道题都有唯一的序号；cha表示内容所在的章；sec表示内容所在的节。如【17，2，1】表示序号17的题来自第2章第1节。2、题型：1)填空题:1-802)分析计算作图题：序号1-30题（选自《数据结构题集》—严蔚敏等编）3、内容取舍：根据本学期上课课件中的内容，未上课章节的练习可舍弃。4、必做题或选做题：第四章和第五章不考，所以可以选做。1)填空题：序号1-80题【1，1，2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在　　一对多　　　关系，图形结构中

2、元素之间存在　多对多　　　　关系。【2，1，2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。【3，1，2】数据结构的三要素是①逻辑结构，物理结构，操作，，③操作。【4，1，2】数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是①__，R是②___。【5，1，2】存储结构可根据数据元素在机器中的位置是否一定连续分为数据元素的有限集合，K上关系的有限集_。【6，1，4】度量算法效率可通过时间复杂度___来进行。【7，1，4】算法的五个重要特性是确定性、　　可行性　　、　有穷性　　、　　　　、输入和输出。【8，1，4】设n为正整数，则下面程序段的时间复

3、杂度是O(n)___。i=1；k=0；while(i

4、){for(j=i;j<=n;j++)@k++;//语句的频度是________n(n+1)/2_____________________。}【11，1，4】按增长率由大到小排列下列函数的结果是____n2__nlog2nn_n1/2__log2n___log2(log2n),______________________。。log2(log2n),nlog2n,n2,n1/2,log2n,n【12，2，1】当线性表的规模比较大，难以估计其存储规模时，一般以采用动态链表的存储结构为好。【13，2，1】线性表(a1，a2，…，an)有两种存储结构：顺序存储结构和链式存储结

5、构，请就这两种存储结构完成下列填充：_顺序___存储密度较大；___顺序___存储利用率较高；_顺序____可以随机存取；_链式__不可以随机存取；___链式__插入和删除操作比较方便。【14，2，2】从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动30n-i个元素。【15，2，3】带头结点的双链表L为空的条件是L->next=L或L->prior=L。【16，2，3】带头结点的单链表Head为空的条件是____Head->next=NULL________。【17，2，3】非空单循环链表L中*p是尾结点的条件是______p->next=L____

6、______。【18，2，3】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=__p->next______;和p->next=__s_______的操作。【19，2，3】在一个单链表中的指针p所指结点之前插入一个由指针s所指结点，可执行以下操作序列：s->next=p->next；____;p->next=s;t=p->data;p->data=___s->data;_____;_____;s->data=t;【20，2，3】在一个单链表中删除p所指结点时，应执行以下操作：q=p->next;p->data=p->n

7、ext->data;p->next=p->next->next_;free(q);【21，2，3】在单链表中，删除指针P所指结点的后继结点的语句是P->next=P->next->next;___。【22，2，3】带头结点的单循环链表Head的判空条件是__Head->next==Head;___；不带头结点的单循环链表的判空条件是___Head==NULL;__。_。【23，2，3】删除带头结点的单循环链表Head的第一个结点的操作是_Head->next=Head->next->next;__；删除不带头结点的单循环链表的第一个结点的操作是__H