数据结构习题集和答案

《数据结构习题集和答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论1、填空题1.常见的数据结构有集合，_线性__结构，__树形___结构，__图形__结构等四种。2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。2、选择题1.算法的计算量的大小称为计算的（B）。A．效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于（C）A．问题的规模B.待处理数据的初态C.A和BD.以上都不对3.计算机算法指的是（1）（c

2、），它必须具备（2）（B）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4.下面关于算法说法错误的是（D）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的3、应用题1、给出以下算法的时间复杂度.voidfun(intn){inti=1,k=100;while(i

3、。2、给出以下算法的时间复杂度.voidfun2(intn){inti=1,k=100;while(inext=p->next_____________；②____p->next=s___________________；4.在单向链表

4、中，若要删除某个结点p，一般要找到__p的前趋__结点，才能实现该操作。2、选择题1.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A。(A)n   (B)2n－1   (C)2n   (D)n-12.在单链表中，如果在结点p之后插入一个新结点s，其操作为A。（A）s->next=p->next;p->next=s;（B）p->next=s;s->next=p->next;（C）s->next=p;p->next=s->next;（D）p->next=s;s->next=p;3.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复

5、杂度为(  C )。(1≤i≤n)A．O(0)   B．O(1)   C.O(n)   D．O(n2)4.若长度为n的线性表采用顺序存储结构，在其第i个位置前插入一个新元素需要移动的元素个数为(  B )。(1≤i≤n+1)A．n-i  B．n-i+1   C.i   D．n-i-13、判断题1.线性表中每一个元素都有一个前驱和一个后继。（×）2.在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×)3.顺序存储方式的优点是存储密度大，插入、删除运算效率高。(×)4、程序设计题1、单链表的结点结构定义如下：structLinkNode{LinkNode*next;in

6、tdata;};请根据述函数的功能写程序。voidInsert(LinkNode*h,LinkNode*s){//h指向链表的头结点（即使链表中没有元素，头结点也存在。）//链表中元素已经递增有序//函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序LinkNode*p,*q;//q指向p的前驱q=h;p=h->next;while(p){if(p->data>s->data){//寻找到插入点位置，插入sq->next=s;s->next=p;return;}else{q=p;(1分)p=p->next;(1分)}}//当表中没有比s大的结点时，插入到表尾s-

7、>next=q->next;(2分)q->next=s;(2分)}第3章栈和队列1、填空题1.栈和队列在本质上都是___线性表__________。2.栈的操作特点是__后进先出_。队列的操作特点是_先进先出__。2、选择题1.消除递归不一定需要使用栈，此说法___A____。A.正确   B.错误2.用单循环链表表示队列，正确的说法是B。(A)可设一个头指针使入队、出队都方便；(B)可设一个尾指针使入队、出队都方便；(C)必须设头尾指针才能使入队、出队都方便；(D)无论如何,只可能使入队方便。3、判断题1.栈的特