专升本数据结构试题解析.doc
- 文档编号:5523781
- 上传时间:2023-05-08
- 格式:DOC
- 页数:73
- 大小:7.29MB
专升本数据结构试题解析.doc
《专升本数据结构试题解析.doc》由会员分享,可在线阅读,更多相关《专升本数据结构试题解析.doc(73页珍藏版)》请在冰点文库上搜索。
第2部分习题解析亱店↘打烊oO
第2部分习题解析
第1章绪论
1.1 选择题
1.算法的时间复杂度取决于( C )
A)问题的规模B)待处理数据的初态C)A和B
【答案】C
2.计算机算法指的是解决问题的步骤序列,它必须具备(B )这三个特性。
A)可执行性、可移植性、可扩充性 B)可执行性、确定性、有穷性
C)确定性、有穷性、稳定性 D)易读性、稳定性、安全性
【答案】B
5.从逻辑上可以把数据结构分为( C )两大类。
A)动态结构、静态结构 B)顺序结构、链式结构
C)线性结构、非线性结构 D)初等结构、构造型结构
【答案】C
6.在下面的程序段中,对x的赋值的语句频度为( C )
for(i=0;i for(j=0;j A)O(2n) B)O(n) C.O(n2) D.O(log2n) 【答案】C 7.下面的程序段中,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) 【答案】D 1.2 填空题 2.对于给定的n个元素,可以构造出的逻辑结构有_____________,_____________,_____________,_____________四种。 【答案】 (1)集合 (2)线性结构(3)树形结构(4)图状结构或网状结构 4.数据结构中评价算法的两个重要指标是_____________。 【答案】算法的时间复杂度和空间复杂度。 5.数据结构是研讨数据的_____________和_____________,以及它们之间的相互关系,并对与这种结构定义相应的_____________,设计出相应的_____________。 【答案】 (1)逻辑结构 (2)物理结构(3)操作(运算)(4)算法。 6.一个算法具有5个特性: _____________、_____________、_____________,有零个或多个输入、有一个或多个输出。 【答案】 (1)有穷性 (2)确定性 (3)可行性。 9.已知如下程序段 for(i=n;i>0;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)/2 10.在下面的程序段中,对x的赋值语句的频度为_____________(表示为n的函数) for(i=0;i>n;i++) for(j=0;j>i;j++) for(k=0;k>j;k++) x=x+delta; 【答案】1+(1+2)+(1+2+3)+…+(1+2+…+n)=n(n+1)(n+2)/6,O(n3) 11.下面程序段中带下划线的语句的执行次数的数量级是_____________。 i=1;while(i 【答案】log2n 12.计算机执行下面的语句时,语句s的执行次数为_____________。 for(i=l;i for(j=n;j>=i;j--)s; 【答案】(n+3)(n-2)/2 13.下面程序段的时间复杂度为_____________。 (n>1) sum=1; for(i=0;sum 【答案】O(n) 第2章线性表 2.1 选择题 1.对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素,则选择()最节省时间 A)顺序表 B)带头结点的双循环链表 C)单链表 D)带尾结点的单循环链表 【答案】A 2.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法时间复杂度为( )(1≤i≤n+1)。 A)O(0) B)O (1)C)O(n)D)O(n2) 【答案】C 3.双向链表中有两个指针域,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; 【答案】D 4.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是() A)O(nlog2n) B)O (1) C)O(n) D)O(n2) 【答案】C 5.在一个以h为头指针的单循环链中,p指针指向链尾结点的条件是() A)p->next==NULL B)p->next==h C)p->next->next==h D)p->data==-1 【答案】B 6.对于一个具有n个结点的线性表,建立其单链表的时间复杂度是( ) A)O(n)B)O (1)C)O(nlog2n)D)O(n2) 【答案】A 8.在双向链表存储结构中,删除p所指的结点时须修改指针( ) A)p->prior->next=p->next p->next->prior=p->prior; B)p->prior=p->prior->prior p->prior->next=p; C)p->next->prior=p p->next=p->next->next D)p->next=p->prior->prior p->prior=p->next->next; 【答案】A 9.线性表采用链式存储时,其元素地址( ) A)必须是连续的 B)一定是不连续的 C)部分地址是连续的 D)连续与否均可 【答案】D 2.2 填空题 1.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是_____________。 【答案】(n-1)/2 2.在单链表中设置头结点的作用是_____________。 【答案】主要是使插入和删除等操作统一,在第一个元素之前插入元素和删除第一个结点不必另作判断。 另外,不论链表是否为空,链表头指针不变。 3.线性表的顺序存储是通过_____________来反应元素之间的逻辑关系,而链式存储结构是通过_____________来反应元素之间的逻辑关系。 【答案】 (1)数据元素的前后顺序 (2)元素中的指针 4.当对一个线性表经常进行的是存取操作,而很少进行插入和删除操作时,则采用_____________存储结构最节省时间,相反当经常进行插入和删除操作时,则采用_____________存储结构最节省时间。 【答案】 (1)顺序 (2)链式 5.对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为_____________,在给定值为x的结点后插入一个新结点的时间复杂度为_____________。 【答案】 (1)O (1) (2)O(n) 7.对于双向链表,在两个结点之间插入一个新结点需修改的指针共_____________个,单链表为_____________个。 【答案】 (1)4 (2)2 8.循环单链表的最大优点是_____________。 【答案】从任一结点出发都可访问到链表中每一个元素。 9.若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时,可执行下列操作: s->next=_____________; p->next=s; t=p->data; p->data=_____________; s->data=_____________; 【答案】 (1)p->next (2)s->data (3)t 10.某线性表采用顺序存储结构,每个元素占据4个存储单元,首地址为100,则下标为11的(第12个)元素的存储地址为_____________。 【答案】144 11.带头结点的双循环链表L中只有一个元素结点的条件是_____________。 【答案】L->next->next==L 2.3 判断题 1.取线性表的第i个元素的时间同i的大小有关( ) 【答案】× 2.线性表的特点是每个元素都有一个前驱和一个后继( ) 【答案】× 3.顺序存储方式的优点是存储密度大,且插入、删除运算效率高( ) 【答案】× 4.线性表采用链表存储时,结点的存储空间可以是不连续的( ) 【答案】√ 5.链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存储结构中效率高( ) 【答案】√ 6.顺序存储方式只能用于存储线性结构( ) 【答案】× 【解析】线性结构、树型结构和图状结构均可用顺序存储表示。 9.顺序存储结构的主要缺点是不利于插入或删除操作( ) 【答案】√ 10.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好( ) 【答案】× 2.4 程序设计题 1.设顺序表va中的数据元素递增有序。 试设计一个算法,将x插入到顺序表的适当位置上,以保持该表的有序性。 【算法源代码】 voidInsert_SqList(SqListva,intx)/*把x插入递增有序表va中*/ {inti; if(va.length>MAXSIZE)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,表示A>B;值为-1,表示A 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.length>B.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指向; 2)将new插入在单链表的第i个元素的位置上: 若i==1,new插在链表首部;否则查找第i-1个结点,由指针p指向,然后将new插在p之后。 【算法源代码】 voidInsert(LinkList*L,inti,intb) {LinkListnew; new=(LinkList*)malloc(sizeof(LNode)); new->data=b; if(i==1) {/*插入在链表头部*/ New->next=*L; *L=new; } else {/*插入在第i个元素的位置*/ p=*L; while(--i>1)p=p->next; new->next=p->next;p->next=new; } }/*Insert*/ 5.已知线性表中的元素以值递增有序排列,并以单链表作存储结构。 试设计一个高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删结点空间(注意: mink和maxk是给定的两个参变量。 它们的值可以和表中的元素相同,也可以不同)。 【算法分析】 1)查找最后一个不大于mink的元素结点,由指针p指向; 2)如果还有比mink更大的元素,查找第一个不小于maxk的元素,由指针q指向; 3)p->next=q,即删除表中所有值大于mink且小于maxk的元素。 【算法源代码】 voidDelete_Between(LinkList*L,intmink,intmaxk) { p=*L; while(p->next->data<=mink)p=p->next;/*p是最后一个不大于mink的元素*/ if(p->next)/*如果还有比mink更大的元素*/ { q=p->next; while(q->data p->next=q; } }/*Delete_Between*/ 6.已知线性表中的元素以值递增有序排列,并以单链表作存储结构。 试设计一个高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同),同时释放被删结点空间。 【算法分析】 1)初始化指针p和q,分别指向链表中相邻的两个元素; 2)当p->next不为空时,做如下处理: ①若相邻两元素不相等时,p和q都向后推一步; ②否则,当相邻元素相等时,删除多余元素。 【算法源代码】 voidDelete_Equal(LinkList*L) { p=(*L)->next;q=p->next;/*p和q指向相邻的两个元素*/ while(p->next) { if(p->data! =q->data)/*若相邻两元素不相等时,p和q都向后推一步*/ { p=p->next; q=p->next; } else { while(q->data==p->data)/*当相邻元素相等时删除多余元素*/ { r=q; q=q->next; free(r); } p->next=q;p=q;q=p->next; }/*else*/ }/*while*/ }/*Delete_Equal*/ 7.试设计一个算法,对带头结点的单链表实现就地逆置。 【算法分析】 1)空表或长度为1的表,不做任何处理; 2)表长大于2时,做如下处理: ①首先将整个链表一分为二,即从链表的第一元素结点处断开; ②逐个地把剩余链表的当前元素q插入到链表的头部。 【算法源代码】 voidLinkList_reverse(LinkListL) {if(! L->next||! L->next->next)return; p=L->next;q=p->next;s=q->next; p->next=NULL;/*从链表的第一元素结点处断开*/ while(s->next) {q->next=p;p=q; q=s;s=s->next;/*把L的元素逐个插入新表表头*/ } q->next=p;s->next=q;L->next=s; }/*LinkList_reverse*/ 8.设线性表A=(a1,a2,…,am)和B=(b1,b2,…,bn),试设计一个按下列规则合并A,B为线性表C的算法,即使得 C=(a1,b1,…,am,bm,bm+1,…,bn)当m≤n时; 或者 C=(a1,b1,…,an,bn,an+1,…,am)当m>n时。 线性表A,B和C均以单链表作存储结构,且C表利用A表和B表中的结点空间构成。 注意: 单链表的长度值m和n均未显式存储。 【算法分析】 1)初始化指针p指向链表A的当前元素,指针q指向链表B的当前元素; 2)当链表A和B均为结束时,做如下处理: ①将B的元素插入 ②若A非空,将A的元素插入 ③指针p和q同时后移 【算法源代码】 voidmerge1(LinkListA,LinkListB,LinkList*C) {p=A->next;q=B->next;*C=A; while(p&&q) {s=p->next;p->next=q;/*将B的元素插入*/ if(s) {t=q->next; q->next=s;/*若A非空,将A的元素插入*/ } p=s;q=t;/*指针p和q同时后移*/ }/*while*/ }/*merge1*/ 9.假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,请设计一个算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即A表和B表)的结点空间构造C表。 【算法分析】按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素。 【算法源代码】 voidreverse_merge(LinkListA,LinkListB,LinkList*C) {LinkListpa,pb,pre; pa=A->next;pb=B->next;/*pa和pb分别指向A和B的当前元素*/ pre=NULL; while(pa||pb) {if(pa->data pb)/*将A的元素插入新表*/ {pc=pa;q=pa->next;pa->next=pre;pa=q;} else/*将B的元素插入新表*/ {pc=pb;q=pb->next;pb->next=pre;pb=q;} pre=pc; } *C=A; A->next=pc;/*构造新表头*/ }/*reverse_merge*/ 10.已知A,B和C为三个递增有序的线性表,现要求对A表作如下操作: 删去那些既在B表中出现又在C表中出现的元素。 试对顺序表编写实现上述操作的算法,并分析你的算法的时间复杂度(注意: 题中没有特别指明同一表中的元素值各不相同)。 【算法分析】先从B和C中找出共有元素,记为same,再在A中从当前位置开始,凡小于same的元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same。 【算法源代码】 voidSqList_Intersect_Delete(SqList*A,SqListB,SqListC) {i=0;j=0;k=0;m=0; /*i指示A中元素原来的位置,m为移动后的位置*/ while(i<(*A).length&&j {if(B.elem[j] elseif(B.elem[j]>C.elem[k])k++; else{ same=B.elem[j]; /*找到了相同元素same*/ while(B.elem[j]==same)j++; while(C.elem[k]==same)k++; /*j和k后移到新的元素*/ while(i<(*A).length&&(*A).elem[i] (*A).elem[m++]=(*A).elem[i++]; /*需保留的元素移动到新位置*/ while(i<(*A).length&&(*A).elem[i]==same)i++;/*跳过相同的元
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 试题 解析