数据结构练习题含答案.docx
- 文档编号:12318513
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:39
- 大小:282.83KB
数据结构练习题含答案.docx
《数据结构练习题含答案.docx》由会员分享,可在线阅读,更多相关《数据结构练习题含答案.docx(39页珍藏版)》请在冰点文库上搜索。
数据结构练习题含答案
数据结构练习题(含答案)
数据结构练习题
习题1绪论
1.1单项选择题
1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。
①A.操作对象 B.计算方法 C.逻辑结构 D.数据映象
②A.存储结构B.关系C.运算D.算法
2.数据结构DS(DataStruct)可以被形式地定义为DS=(D,R),其中D是①的有限集合,R是D上的②有限集合。
①A.算法B.数据元素C.数据操作D.数据对象
②A.操作B.映象C.存储D.关系
3.在数据结构中,从逻辑上可以把数据结构分成。
A.动态结构和静态结构B.紧凑结构和非紧凑结构
C.线性结构和非线性结构D.内部结构和外部结构
4.算法分析的目的是①,算法分析的两个主要方面是②。
①A.找出数据结构的合理性B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进D.分析算法的易懂
i=1;
while(i<=n)
i=i*2;
1.3算法设计题
1.试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值.
2.试写一算法,求出n个数据中的最大值。
写出最大语句频度,该算法的时间复杂度。
习题答案
1.11.C,A2.B,D3.C4.C,A5.C,B
1.21.线性结构、树形结构、图形结构,非线性结构
2.没有、1、没有、1
3.前驱、1、后续、任意多个
4.任意多个
5.一对一、一对多、多对多
6.有穷性、确定性、可行性、输入、输出
7.最大语句频度:
n2,时间复杂度:
.O(n2)
8.最大语句频度:
n(n+1)/2,时间复杂度:
.O(n2)
9.最大语句频度:
n3,时间复杂度:
.O(n3)
10.最大语句频度:
n
,时间复杂度:
.O(n
)
11.最大语句频度:
log2n,时间复杂度:
.O(log2n)
习题2线性表
2.1单项选择题
1.一个向量(即一批地址连续的存储单元)第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是____。
A.110B.108C.100D.120
2.线性表的顺序存储结构是一种___的存储结构,而链式存储结构是一种___的存储结构。
A.随机存取B.索引存取C.顺序存取D.散列存取
3.线性表的逻辑顺序与存储顺序总是一致的,这种说法___。
A.正确B.不正确
4.线性表若采用链式存储结构时,要求内存中可用存储单元的地址___。
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续或不连续都可以
5.在以下的叙述中,正确的是___。
A.线性表的顺序存储结构优于链表存储结构
B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D.线性表的链表存储结构优于顺序存储结构
6.每种数据结构都具备三个基本运算:
插入、删除和查找,这种说法___。
A.正确B.不正确
7.不带头结点的单链表head为空的判定条件是____。
A.head==NULLB.head->next==NULL
C.head->next==headD.head!
=NULL
8.带头结点的单链表head为空的判定条件是____。
A.head==NULLB.head->next==NULL
C.head->next==headD.head!
=NULL
9.非空的循环单链表head的尾结点(由p所指向)满足____。
A.p->next==NULLB.p==NULL
C.p->next==headD.p==head
10.在双向循环链表的p所指结点之后插入s所指结点的操作是____。
A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;
C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;
D.s->left=p;s->right=p->right;p->right->left=s;p->right=s;
11.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点,则执行____。
A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;
B.q->next=s;s->next=p;C.p->next=s;s->next=q;
12.在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行____。
A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;
C.s->next=p->next;p=s;C.p->next=s;s->next=p;
13.在一个单链表中,若删除p所指结点的后续结点,则执行____。
A.p->next=p->next->next;B.p=p->next;p->next=p->next->next;
C.p->next=p->next;D.p=p->next->next;
14.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较____个结点。
A.nB.n/2C.(n-1)/2D.(n+1)/2
15.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。
A.O
(1)B.O(n)C.O(n2)D.O(nlog2n)
16.给定有n个元素的向量,建立一个有序单链表的时间复杂度是____。
A.O
(1))B.O(n)C.O(n2)D.O(n*log2n)
2.2填空题(将正确的答案填在相应的空中)
1.单链表可以做____的链接存储表示。
2.在双链表中,每个结点有两个指针域,一个指向______,另一个指向_____。
3.在一个单链表中p所指结点之前插入一个s(值为e)所指结点时,可执行如下操作:
q=head;
while(q->next!
=p)q=q->next;
s=newNode;s->data=e;
q->next=;//填空
s->next=;//填空
4.在一个单链表中删除p所指结点的后继结点时,应执行以下操作:
q=p->next;
p->next=____;//填空
delete;//填空
5.在一个单链表中p所指结点之后插入一个s所指结点时,应执行s->next=____和p->next=____的操作。
6.对于一个具有n个结点的单链表,在已知p所指结点后插入一个新结点的时间复杂度是____;在给定值为x的结点后插入一个新结点的时间复杂度是____。
2.3算法设计题:
1.设顺序表va中的数据元数递增有序。
试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。
StatusInsert_SqList(SqList&va,intx)
{
if(va.length+1>maxsize)returnERROR;
va.length++;
for(i=va.length-1;va.elem[i]>x&&i>=0;i--)
va.elem[i+1]=va.elem[i];
va.elem[i+1]=x;
returnOK;
}
2.试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,….an)逆置为(an,an-1,….,a1)。
voidreverse(inta[],intsize)
{
inti,j,tmp;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 练习题 答案