专升本数据结构试题解析

第2部分习题解析第1章绪论1.1选择题1.算法的时间复杂度取决于（C）A）问题的规模B）待处理数据的初态C）A和B【答案】C2.计算机算法指的是解决问题的步骤序列，它必须具备（B）这三个特性。A）可执行性、可移植性、可扩充性B）可执行性、确定性、有穷性C）确定性、有穷性、稳定性D）易读性、稳定性、安全性【答案】B5．从逻辑上可以把数据结构分为（C）两大类。A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构【答案】C6．在下面的程序段中，对x的赋值的语句频度为（C）for(i=0;in;i++)for(j=0;jn;j++)x=x+1;A）O(2n)B）O(n)C．O(n2)D．O(log2n)【答案】C7．下面的程序段中，n为正整数，则最后一行的语句频度在最坏情况下是（D）for(i=n-1;i=1;i--)for(j=1;j=i;j++)if(A[j]A[j+1])A[j]与A[j+1]对换；A.O（n）B）O(nlog2n)C）O(n3)D）O(n2)【答案】D1.2填空题2.对于给定的n个元素,可以构造出的逻辑结构有_____________，_____________，_____________，_____________四种。【答案】（1）集合（2）线性结构（3）树形结构（4）图状结构或网状结构4．数据结构中评价算法的两个重要指标是_____________。【答案】算法的时间复杂度和空间复杂度。5.数据结构是研讨数据的_____________和_____________，以及它们之间的相互关系，并对与这种结构定义相应的_____________，设计出相应的_____________。【答案】（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。6．一个算法具有5个特性：_____________、_____________、_____________，有零个或多个输入、有一个或多个输出。【答案】（1）有穷性（2）确定性（3）可行性。9．已知如下程序段for(i=n;i0;i--){语句1}{x=x+1;{语句2}for(j=n;j=i;j--){语句3}y=y+1;{语句4}}语句1执行的频度为_____________；语句2执行的频度为_____________；语句3执行的频度为_____________；语句4执行的频度为_____________。【答案】（1）n+1（2）n（3）n(n+3)/2（4）n(n+1)/210．在下面的程序段中，对ｘ的赋值语句的频度为_____________（表示为n的函数）for(i=0;in;i++)for(j=0;ji;j++)for(k=0;kj;k++)ｘ=ｘ+delta;数据结构上机实验与习题解析亱店↘打烊oO-2-【答案】1+（1+2）+（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6，O(n3)11.下面程序段中带下划线的语句的执行次数的数量级是_____________。i=1;while(in)i=i*2;【答案】log2n12.计算机执行下面的语句时，语句s的执行次数为_____________。for(i=l;in-l;i++)for(j=n;j=i;j--)s;【答案】(n+3)(n-2)/213.下面程序段的时间复杂度为_____________。(n1)sum=1;for(i=0;sumn;i++)sum+=1;【答案】O(n)第2章线性表2.1选择题1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间A）顺序表B）带头结点的双循环链表C）单链表D）带尾结点的单循环链表【答案】A2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（）(1≤i≤n+1)。A）O(0)B）O(1)C）O(n)D）O(n2)【答案】C3．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）A）p-prior=q;q-next=p;p-prior-next=q;q-prior=p-prior;B）q-prior=p-prior;p-prior-next=q;q-next=p;p-prior=q-next;C）q-next=p;p-next=q;p-prior-next=q;q-next=p;D）p-prior-next=q;q-next=p;q-prior=p-prior;p-prior=q;【答案】D4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）A）O(nlog2n）B）O(1）C）O(n）D）O(n2）【答案】C5．在一个以h为头指针的单循环链中，p指针指向链尾结点的条件是（）A）p-next==NULLB）p-next==hC）p-next-next==hD）p-data==-1【答案】B6．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（）A）O(n)B）O(1)C）O(nlog2n)D）O(n2)【答案】A8．在双向链表存储结构中，删除p所指的结点时须修改指针（）A）p-prior-next=p-nextp-next-prior=p-prior;B）p-prior=p-prior-priorp-prior-next=p;C）p-next-prior=pp-next=p-next-nextD）p-next=p-prior-priorp-prior=p-next-next;【答案】A9．线性表采用链式存储时，其元素地址（）A）必须是连续的B）一定是不连续的C）部分地址是连续的D）连续与否均可【答案】D2.2填空题1．线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素第2部分习题解析亱店↘打烊oO-3-平均需要移动元素的个数是_____________。【答案】（n-1）/22．在单链表中设置头结点的作用是_____________。【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。3．线性表的顺序存储是通过_____________来反应元素之间的逻辑关系，而链式存储结构是通过_____________来反应元素之间的逻辑关系。【答案】（1）数据元素的前后顺序（2）元素中的指针4．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用_____________存储结构最节省时间，相反当经常进行插入和删除操作时，则采用_____________存储结构最节省时间。【答案】（1）顺序（2）链式5．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_____________，在给定值为x的结点后插入一个新结点的时间复杂度为_____________。【答案】（1）O(1)（2）O(n)7.对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____________个，单链表为_____________个。【答案】（1）4（2）28.循环单链表的最大优点是_____________。【答案】从任一结点出发都可访问到链表中每一个元素。9．若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时，可执行下列操作：s-next=_____________;p-next=s;t=p-data;p-data=_____________;s-data=_____________;【答案】（1）p-next（2）s-data（3）t10．某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11的（第12个）元素的存储地址为_____________。【答案】14411．带头结点的双循环链表L中只有一个元素结点的条件是_____________。【答案】L-next-next==L2.3判断题1．取线性表的第i个元素的时间同i的大小有关（）【答案】×2．线性表的特点是每个元素都有一个前驱和一个后继（）【答案】×3．顺序存储方式的优点是存储密度大，且插入、删除运算效率高（）【答案】×4．线性表采用链表存储时，结点的存储空间可以是不连续的（）【答案】√5．链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高（）【答案】√6．顺序存储方式只能用于存储线性结构（）【答案】×【解析】线性结构、树型结构和图状结构均可用顺序存储表示。9．顺序存储结构的主要缺点是不利于插入或删除操作（）【答案】√10．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（）【答案】×2.4程序设计题1．设顺序表va中的数据元素递增有序。试设计一个算法，将x插入到顺序表的适当位置上，以保持数据结构上机实验与习题解析亱店↘打烊oO-4-该表的有序性。【算法源代码】voidInsert_SqList(SqListva,intx)/*把x插入递增有序表va中*/{inti;if(va.lengthMAXSIZE)return;for(i=va.length-1;va.elem[i]x&&i=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;va.length++;}/*Insert_SqList*/2．设A=（a1，a2，…，am）和B=（b1，b2，…，bn）均为顺序表，试设计一个比较A，B大小的算法（请注意：在算法中，不要破坏原表A和B）。【算法分析】比较顺序表A和B，并用返回值表示结果，值为1，表示AB；值为-1，表示AB；值为0，表示A=B。1）当两个顺序表可以互相比较时，若对应元素不等，则返回值为1或-1；2）当两个顺序表可以互相比较的部分完全相同时，若表长也相同，则返回值为0；否则，哪个较长，哪个就较大【算法源代码】intListComp(SqListA,SqListB){for(i=1;i=A.length&&i=B.length;i++)if(A.elem[i]!=B.elem[i])returnA.elem[i]B.elem[i]?1:-1;if(A.length==B.length)return0;returnA.lengthB.length?1:-1;/*当两个顺序表可以互相比较的部分完全相同时，哪个较长，哪个就较大*/}/*ListComp*/3．已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试设计一个算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。【算法分析】1）单链表ha的头结点作为连接后的链表的头结点，即hc=ha；2）查找单链表ha的最后一个结点，由指针p指向，即p-next==NULL；3）将单链表hb的首元结点（非头结点）连接在p之后，即p-next=hb-next；4）回收单链表hb的头结点空间【算法源代码】voidListConcat(LinkListha,LinkListhb,LinkList*hc)/*把链表hb接在ha后面形成链表hc*/{*hc=ha;p=ha;/*由指针p指向ha的尾元结点*/p=p-next;p-next=hb-next;free(hb);}/*ListConcat*/4．试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT（L，i，b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。【算法分析】1）生成新结点存放元素b，由指针new指向