数据结构第一二章题目.docx
- 文档编号:18093220
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:53
- 大小:71.23KB
数据结构第一二章题目.docx
《数据结构第一二章题目.docx》由会员分享,可在线阅读,更多相关《数据结构第一二章题目.docx(53页珍藏版)》请在冰点文库上搜索。
数据结构第一二章题目
(02)1.对一个算法的评价不包括如下(B)方面的内容。
A健壮性和可读性B并行性C正确性D时空复杂度
2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行(A)。
A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;
C.p->next=HL;p=HL;D.HL=p;p->next=HL
3.对线性表,在下列哪种情况下应当采用链表表示?
(B)
A.经常需要随机地存取元素B.经常需要进行插入和删除操作入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变
4.在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的的概率都相等)为(C)。
AnBn/2C(n+1)/2D(n-1)/2
5.算法指的是(D)
A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列
(二)填空题1.通常从四个方面评价算法的质量:
_______、_______、_______和_______。
2.一种抽象数据类型包括______________和____________两个部分。
3.在一个带头结点的单循环链表中,p指向尾结点的直接前驱,则指向头结点的指针head可用p表示为head=。
4.设线性表中有,n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为度为___________,在链式存储结构上实现顺序查找的平均时间复杂度为__________
5.设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为_____________________________________(设结点中的两个指针域分别为llink和rlink)
(三)程序设计1.设计在单链表中删除值相同的多余结点的算法
(四)程序填空下面程序段的功能是利用从尾部插入的方法建立单链表的算法,请在下划线处填上正确的内容。
typedefstructnode
{intdata;
structnode*next;
}lklist;
voidlklistcreate(_____________*&head)
{for(i=1;i<=n;i++)
{p=(lklist*)malloc(sizeof(lklist));
scanf(“%d”,&(p->data));p->next=0;
if(i==1)head=q=p;
else{q->next=p;
____________;
}
}
}
(04)
(1)数据结构在计算机内存中的表示是指(A)
A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系
(2)在长度为n的(A)上,删除第一个元素,其算法的时间复杂度为O(n)。
A.只有表头指针的不带表头结点的循环单链表
B.只有表尾指针的不带表头结点的循环单链表
C.只有表尾指针的带表头结点的循环单链表
D.只有表头指针的带表头结点的循环单链表
(3)在一个长度为n(n>1)的单链表上,设有头和尾两个指针,执行(B)操作与链表长度有关。
A.删除单链表中的第一个元素B.删除单链表中的最后一个元素
C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素
二、填空题
(1)数据逻辑结构包括______、______、_______和______四种类型。
(2)算法的5个重要特性是_______、_______、_______输入和输出。
(3)线性结构中元素之间存在_______关系,树形结构中元素之间存在_______关系,图形结构中元素之间存在_______关系。
(4)在一个单链表中删除p所指结点时,应执行以下操作:
P->data=p->next->data;
p->next=______;
free(q);
三、判断题
(1)算法可以用不同的语言描述,如果用C语言或PASCAL语言等高级语言来描述,则算法实现上就是程序了。
()
四、算法设计
(1)已知由一个线性链表表示的线性表中含有三类字符的数据元素(如:
字母字符、数字字符和其他字符),试编写算法将该线性表分割为三个循环链表,其中每个循环链表表示的线性表中均只含一类字符。
(05)1、下面程序段的时间复杂度为(C)
for(inti=0;i for(intj=0;j A.O(m2)B.O(n2)C.O(m*n)D.O(m+n) 2、带头结点的单链表head为空的判定条件是(B) A.head==NULLB.head->next==NULLC.head->next==headD.head! =NULL 3、在循环双列表的p所指结点之前插入s所指结点的操作是(D) A.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior; B.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior; C.s->next=p;s->prior=p->prior;p->prior=s;p->prior->next=s; D.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 4、算法分析的目的是( C),算法分析的两个主要方面是(A )。 (1)A.找出数据结构的合理性B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进D.分析算法的易读性和文档性 (2)A.空间复杂度和时间复杂度B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 5、在一个长度为n(n>1)的单链表上,设有头和尾两个指针,执行(B)个操作与链表长度有关A.删除单链表的第一个元素B.删除单链表中的最后一个元素 C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个元素 2、填空题1、算法的5个重要特性是____、____、____、输入和输出。 2、在线性结构中,第一个结点_____前驱结点,其余每个结点有且只有____个前驱结点;最后一个结点______后续结点,其余每个结点有且只有_____个后续结点。 3、线性表是由n(n≥0)个_________组成的有限序列。 4、单链表中逻辑上相邻的结点而在物理位置上_______相邻。 5、在单链表中,除了表头结点外,任意结点的存储位置由其直接_结点的指针域的值所指示。 三、算法设计题试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。 (06)一: 选择题1.数据结构中,与所使用的计算机无关的是数据的(C) A.存储结构B.物理结构C.逻辑结构D.物理与存储结构 2.算法分析的两个主要方面是(A)A.时间复杂性和空间复杂性B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 3.链式存储结构所占存储空间(A) A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针 B.只有一部分,存放结点值C.只有一部分,存储表示结点间关系的指针 D.分两部分,一部分存放结点值,另一部分存放结点所占单元数 1、向一个有127个元素的顺序表中插入一个新元素,并保持原来顺序不变,平均要移动(B)个元素。 A.8B.63.5C.63D.7 二: 填空题数据结构被形式地定义为(D,R),其中D是____的有限集合,R是D上的____。 1.数据的操作最常用的有五种,分别是________,____________,_________,_________,___________。 2.在单链表中设置头结点的作用是_____。 3.在单链表中,除了首元结点(或称第一个数据元素结点)外,其他结点的存储位置由____________指示。 4.在有n个结点的单链表中,要删除已知结点*p,需找到它的___,其时间复杂度为_______。 3.简答题1.解释以下三个名词的差别: 头指针,头结点,首元结点。 2.试描述一般数据类型和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 4.算法设计已知线性表中的元素以值递增有序排列,并以单链表作存储结构,试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同),同时释放被删结点空间。 (07)1.算法的计算量的大小称为计算的(B)。 A.效率B.复杂性C.现实性D.难度 2.计算机算法指的是(C),它必须具备(B)这三个特性。 (1)A.计算方法B.排序方法C.解决问题的步骤序列D.调度方法 (2)A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性D.易读性、稳定、安全性 3.下面关于算法说法正确的是(D)。 A.算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性(基本运算执行有限次)是指指令不能有二义性D.以上几个都是错误的 4.从逻辑上可以把数据结构分为(C)两大类。 A.动态结构、静态结构B.顺序结构、链式结构 C.线性结构、非线性结构D.初等结构、构造型结构 5在下面的程序段中,对x的赋值语句的频度为(C) FORi: =1TOnDOFORj: =1TOnDOx: =x+1; A.O(2n)B.O(n)C.O(n2)D.O(log2n) 6.程序段FORi: =n-1DOWNTO1DOFORj: =1TOiDOIFA[j]>A[j+1]THENA[j]与A[j+1]对换;其中n为正整数,则最后一行的语句频度在最坏情况下是(C)。 A.O(n)B.O(nlogn)C.O(n3)D.O(n2) 7.以下哪个数据结构不是多型数据类型(D) A.栈B.广义表C.有向图D.字符串(始终是字符型的,不会存在其他类型) 8.以下数据结构中,(A)是非线性数据结构A.树B.字符串C.队D.栈 二、填空题 (1)1.对于给定的n个元素,可以构造出的逻辑结构有_____,_____,___,______和_______四种。 (2).数据结构中评价算法的两个重要指标是________和_______。 (3).一个算法具有5个特性: ______、______、____,______、________。 (4).下面程序段的时间复杂度为______。 sum=1;for(i=0;sum 三、名词解释 (1)时间复杂度 (2)频度(3)健壮性(4)数据元素 (08)一.选择题 1.算法的时间复杂度取决于(C)。 A.问题的规模B.待处理数据的初态C.A和B 2.计算机算法指的是(C),它必须具备(B)这三个特性。 (1)A.计算方法B.排序方法C.解决问题的步骤序列D.调度方法 (2)A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性D.易读性、稳定性、安全性 3.一个算法应该是(B)。 A.程序B.问题求解步骤的描述C.要满足五个基本特征D.aandc 4.从逻辑上可以把数据结构分为(C)两大类。 A.动态结构、静态结构B.顺序结构、链式结构 C.线性结构、非线性结构D.初等结构、构造型结构 5.在下面的程序段中,对x的赋值语句的频度为(C) FORi: =1TOnDO FORj: =1TOnDO x: =x+1; A.O(2n)B.O(n)C.O(n2)D.O(log2n) 6.下述哪一条是顺序存储结构的优点? (A)A.存储密度大B.插入运算方便 C.删除运算方便D.可方便地用于各种逻辑结构的存储表示 7.下面关于线性表的叙述中,错误的是哪一个? (B) A.线性表采用顺序存储,必须占用一片连续的存储单元。 B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,不必占用一片连续的存储单元。 D.线性表采用链接存储,便于插入和删除操作。 8.线性表是具有n个(C)的有限序列(n>0)。 A.表元素B.字符C.数据元素D.数据项E.信息项 9.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(A)存储方式最节省时间。 A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表 10.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用(D)存储方式最节省运算时间。 A.单链表B.仅有头指针的单循环链表 C.双链表D.仅有尾指针的单循循环 11.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用(D)最节省时间。 A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表 12.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。 则采用(D)存储方式最节省运算时间。 A.单链表B.双链表C.单循环链表D.带头结点的双循环链表 13.静态链表中指针表示的是(C). A.内存地址B.数组下标C.下一元素地址D.左、右孩子地址 14.链表不具有的特点是(B) A.插入、删除不需要移动元素B.可随机访问任一元素 C.不必事先估计存储空间D.所需空间与线性长度成正比 15.下面的叙述不正确的是(BC) A.线性表在链式存储时,查找第i个元素的时间同i的值成正比 B.线性表在链式存储时,查找第i个元素的时间同i的值无关 C.线性表在顺序存储时,查找第i个元素的时间同i的值成正比 D.线性表在顺序存储时,查找第i个元素的时间同i的值无关 16.在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是(C)注: 双向链表的结点结构为(llink,data,rlink)。 供选择的答案: A.p↑.llink: =q;q↑.rlink: =p;p↑.llink↑.rlink: =q;q↑.llink: =q; B.p↑.llink: =q;p↑.llink↑.rlink: =q;q↑.rlink: =p;q↑.llink: =p↑.llink; C.q↑.rlink: =p;q↑.llink: =p↑.llink;p↑.llink↑.rlink: =q;p↑.llink: =q; D.q↑.llink: =p↑.llink;q↑.rlink: =p;p↑.llink: =q;p↑.llink: =q; 17.在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为: rlink(p)←q;llink(p)←llink(q);llink(q)←p;(B) A.rlink(q)←pB.rlink(llink(q))←pC.rlink(llink(p))←pD.rlink(rlink(p))←p 18.双向链表中有两个指针域,llink和rlink分别指向前趋及后继,设p指向链表中的一个结点,现要求删去p所指结点,则正确的删除是(D)(链中结点数大于2,p不是第一个结点)A.p^.llink^.rlink: =p^.llink;p^.llink^.rlink: =p^.rlink;dispose(p); B.dispose(p);p^.llink^.rlink: =p^.llink;p^.llink^,rlink: =p^.rlink; C.p^.llink^.rlink: =p^.llink;dispose(p);p^.llink^.rlink: =p^.rlink; D.以上A,B,C都不对。 二填空题1.数据的逻辑结构哪四类_______,________,___________,__________. 2.数据的逻辑结构是指___________. 3.一个数据结构在计算机中____________称为存储结构 4.抽象数据类型的定义仅取决于它的一组________,而与_________无关,即不论其内部结构如何变化,只要它的________不变,都不影响其外部使用。 5.数据结构中评价算法的两个重要指标是___________. 6.数据结构是研讨数据的_______和_________,以及它们之间的相互关系,并对与这种结构定义相应的_________,设计出相应的____________. 7.对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个,单链表为_______个。 8.循环单链表的最大优点是: ________。 9.已知指针p指向单链表L中的某结点,则删除其后继结点的语句是: ________ 10.带头结点的双循环链表L中只有一个元素结点的条件是: _________. 11.在单链表L中,指针p所指结点有后继结点的条件是: ____________. 12.带头结点的双循环链表L为空表的条件是: __________. 13.在单链表p结点之后插入s结点的操作是: __________. 14.请在下列算法的横线上填入适当的语句. FUNCTIONinclusion(ha,hb: linklisttp): boolean; {以ha和hb为头指针的单链表分别表示有序表A和B,本算法判别表A是否包含在表B内,若是,则返回“true”,否则返回“false”} BEGIN pa: =ha^.next;pb: =hb^.next;_________; WHILE__________DO IFpa^.data=pb^.dataTHEN__________ELSE_____________;_________; END; 15.完善算法: 已知单链表结点类型为: TYPEptr=^node; node=RECORD data: integer;next: ptr END; 过程create建立以head为头指针的单链表。 PROCEDUREcreate(_______); VARp,q: ptr;k: integer; BEGIN new(head);q: =head;read(k); WHILEk>0DO BEGIN __________;___________;____________;___________; read(k) END; q^.next: =NIL; 三.计算题1.写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。 结点结构为: (llink,data,rlink) 2.已知L是一个数据类型linkedlist的单循环链表,pa和pb是指向L中结点的指针。 简述下列程序段的功能。 TYPElinkedlist=↑node; node=RECORD data: datatype;next: linkedlist END; PROCMp(pa,pb: linkedlist); PROCsubp(s,q: linkedlist); p: =s; WHILEp↑.next<>qDOp: =p↑.next; p↑.next: =s ENDP; subp(pa,pb); subp(pb,pa); ENDP; 3.假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。 请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表,并要求利用原来两个单链表的结点存放归并后的单链表。 (09)1.数据结构是一门研究非数值计算的程序设计问题中计算机的__①_A_以及它们之间的___②B_和运算等的科学。 A.数据元素B.计算方法C.逻辑存储D.数据映像 A.结构B.关系C.运算D.算法 1.数据结构在计算机内存中的表示是指__A__。 A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系 3.不带头结点的单链表head为空的判定条件是_A__。 A.head==NULLB.head->next==NULLC.head->next==headD.head! =NULL 4.在循环双链表的p所指结点之前插入s所指结点的操作是__D__。 A.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior; B.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior; C.s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s; D.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 5.在一个长度为n的顺序表中向第i个元素(0 A、n-iB、n-i+1C、n-i-1D、i 1.顺序存储的长度为n的线性表,在任何位置上插入和删除操作的时间复杂度基本上都一样。 插入一个元素大约移动表中的()个元素,删除一个元素时大约移动表中的()个元素。 2、在线性表的顺序存储方式中,元素之间的逻辑关系是通过()来体现的;在链式存储方式,元素之间的逻辑关系是通过()体现的。 3、对于一个长度为n的单链表,在已知的p结点后面插入一个新结点的时间复杂度为(),在p结点之前插入一个新结点的时间复杂度为(),在给定值为e的结点之后插入一个新结点的时间复杂度为()。 4、在双向链表中,每个结点包含两个指针域,一个指向()结点,另一个指向)结点。 5、对于循环链表来讲,逐个访问各个结点的结束判断条件是() 1、编写在两种存储方式下,删除线性表中多余的值相同元素的算法. 2、编写一个统计单循环链表的结点个数的算法。 (10)1.已知,L是一个不带头结点的单链表,p指向其中的一个结点,选择合适的语句实现在p结点的后面插入s结点的操作(B)。 A、p->next=s;s->next=p->next;B、s->next=p->next;p->next=s; C、p->next=s;s->next=p;D、s->next=p;p->next=s; 2.在一个长度为n的顺序表中向第i个元素(0 A、n-iB、n-i+1C、n-i-1D、i 3.链表是一种采用(B)存储结构存储的线性表.(A)顺序(B)链式(C)星式(D)网状 4.线
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第一 题目
![提示](https://static.bingdoc.com/images/bang_tan.gif)