数据结构作业题集

《数据结构作业题集》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、DS作业1一判断题1.数据的机内表示称为数据的存储结构。（）2.算法就是程序。（）3.数据元索是数据的最小单位。（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（）二、选择题1.组成数据的基本单位是（）・A数据项B数据元索C数据类型D数据变量2.数据结构是研究数据的（）以及它们之间的相互关系.A理想结构，物理结构B理想结构，抽彖结构C物理结构，逻辑结构D抽象结构，逻辑结构3.算法分析的目的是（）・A找岀数据结构的合理性B研究算法屮的输入和输岀的关系C分析算法的效率以求改进D分析算

2、法的易懂性和文档性三、设n为正整数，求下列程序段的语句频度及时间复朵度1.i二l;k二0;do{k+二10*i;i++;}while（i<=n-l）;2.for（i二1;i<=n;i++）for（j=1;j<=ij++）1.数据在计算机存储器内表示时，物理地址连续，数据间的逻辑关系依靠其物理地址间的连续性来表达，称之为()•(A)存储结构(B)逻辑结构(C)顺序存储结构(D)链式存储结构2.在一个长度为n的顺序表的第i个元素(lWiWn+1)之前插入一个元素时，需向后移动个元索。3•向一个长度为n的顺序表中删除第i个元素(lWiWn)吋，需向前移动个元

3、素。1.线性表中的元素值按非递减有序排列，如果用顺序表进行存储，del函数用以实现删除线性表中、值介于a与bQWb)之间的所有元素。voiddel(elemtypelist[],intn,elemtypea,elemtypeb){inti二0,k二0；while(inext二二LD・L!=NULL2.在一个单链表小，已知P所指结点是q所指结点的前驱结点，若在qZ前插入结点s,要执行的操

4、作为3.有一单链表，其结点的元素值以非递减有序排列。delete函数可以实现删除该单链表屮元索值相同的多余结点，请将程序补充完整。(如:若原来线性表为L=(1,3,3,4,7,7,7,8)则新线性表为L=(l,3,4,7,8))voiddeletc(LinkListhead){Ahead为带头结点的单链表*/LinkListp,q;p=head->next;if(P){while(p->ncxt!=NULL)if()p=p-〉next;else{q二p->next;1、设有一顺序栈S,元素si,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺

5、序是s2,s3,s4,s6,s5,si,则栈的容量至少应该是()A・2B.3C.5D.62、设有一顺序栈已含3个元素，al,a2,a3,al在栈底，元素a4止等待进栈。那么下列4个序列中不可能出现的出栈序列是()A.a3,al,a4,a2B.a3,a2,a4,alC.a3,a4,a2,alD.a4,a3,a2,al3、假设火车调度站(如课本上图3.1所示)入口处有n节硬席或软席车厢(分别用H、S表示)等待调度，请写一个算法，实现对这n节车厢进行调度，使所有的软席车厢都被调整到硕席车厢之前。voidTrainarrange(char*train){p=t

6、rain;q二Irain;InitStack(s);while(*p){if(*p二二MT)else//把'S'调到前部p++；}while(!StackEmpty(s))1.设栈S和队列Q的初始状态为空，元索el,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,el则栈S的容量至少应该是o2.若用一个大小为6的数组來实现循坏队列，且当前rear和front的值分别为0和3,当从队列中删除一个元索，再加入两个元索后，rear的值为,front的值为o3.假设以带头节点的循环链表表示

7、队列，并且只设一•个指针指向队尾元素节点(不设头指针)，请实现相应队列的入队和出队算法。typedefstruetQNode{QElemTypedata;structQNode*ncxt;}CiLNode,*CiQueue;CiQueueQ；voidInitCiQueue(CiQueue&Q){//初始化循环链表表示的队列QQ=(CiLNode*)malloc(sizcof(CiLNode));Q->next=Q;}voidEnCiQueue(CiQueue&Q,intx){//把元素X插入循环链表表示的队列p=(CiLNode*)malloc(siz

8、eof(CiLNode));p~>data=x;&Q,intx)INFEASIBLE;Stat