数据结构习题 答案 全真模拟题 试题.docx
- 文档编号:11098678
- 上传时间:2023-05-29
- 格式:DOCX
- 页数:259
- 大小:484.08KB
数据结构习题 答案 全真模拟题 试题.docx
《数据结构习题 答案 全真模拟题 试题.docx》由会员分享,可在线阅读,更多相关《数据结构习题 答案 全真模拟题 试题.docx(259页珍藏版)》请在冰点文库上搜索。
数据结构习题答案全真模拟题试题
第一章概论
一、名词解释
数据表示2.数据处理3.数据4.数据元素5.逻辑关系6.逻辑结构7.结构
8.运算9.基本运算10.存储结构11.顺序存储结构12.链式存储结构
13.索引存储结构14.散列存储结构15.算法16.运行终止的程序可执行部分
17.伪语言算法18.非形式算法19.时空性能20.时间复杂性21.数据结构
二、填空题
1.计算机专业人员必须完成的两项基本任务是:
_________和__________。
2.数据在计算机存储器中的存在形式称为_________。
3.概括地说,数据结构课程的主要内容包括:
数据的__________、定义在_________、数据的__________的实现。
此外,该课程还要考虑各种结构和实现方法的__________。
4.由一种__________结构和一组__________构成的整体是实际问题的一种数学模型,这种数学模型的建立、选择和实现是数据结构的核心问题。
5.存储结构是逻辑结构的__________实现。
6.数据表示任务是逐步完成的,即数据表示形式的变化过程是__________->__________->__________。
7.数据处理任务也是逐步完成的,即转化过程是__________->__________->__________。
8.从数据结构的观点看,通常所说的"数据"应分成三个不同的层次,即__________、__________和__________。
9.根据需要,数据元素又被称为__________、__________、__________或__________。
10.在有些场合下,数据项又称为__________或__________,它是数据的不可分割的最小标识单位。
11.从某种意义上说,数据、数据元素和数据项实际反映了数据组织的三个层次,数据
可由若干个__________构成,数据元素可由若干个__________构成。
12.根据数据元素之间关系的不同特性,通常有__________、_________、__________、__________四类基本逻辑结构,它们反映了四类基本的数据组织形式。
13.根据操作的效果,可将运算分成以下两种基本类型:
①__________型运算,其操作改变了原逻辑结构的“值”,如结点个数、某些结点的内容等;
②__________型运算,其操作不改变原逻辑结构,只从中提取某些信息作为运算的结果。
14.将以某种逻辑结构S为操作对象的运算称为“__________”,简称“__________”。
15.一般地,可能存在同一逻辑结构S上的两个运算A和B,A的实现需要或可以利用B,而B的实现不需要利用A。
在这种情况下,称A可以“__________”为B。
16.存储实现的基本目标是建立数据的__________。
17.一般地,一个存储结构包括__________、__________、__________三个主要部分。
18.通常,存储结点之间可以有__________、__________、__________、_________四种关联方式,称为四种基本存储方式。
19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑
结构S中数据元素之间的逻辑关系。
由此得到的存储结构,称为____________________或__________。
20.一个运算的实现是指一个完成该运算功能的__________。
运算实现的核心是处
理步骤的规定,即___________。
21.任何算法都必须用某种语言加以描述。
根据描述算法的语言的不同,可将算法分
为:
___________、___________、___________三类。
22.数据结构课程着重评论算法的___________,又称为“___________”。
23.通常从___________、___________、___________、___________等几方面评价算法的(包括程序)的质量。
24.一个算法的时空性能是指该算法的___________和______________________,前者是算法包含的___________,后者是算法需要的___________。
25.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量:
1根据该类问题的特点合理地选择一种或几种操作作为“___________”;
2确定每个算法在给定输入下共执行了多少次___________,并将此次数规定为该算法在给定输入下的___________。
26.通常,一个算法在不同输入下的计算量是不同的。
则可用以下两种方式来确定一个算法的计算量:
1以算法在所有输入下的计算量的最大值作为算法的计算量,这种计算量称为算法的________或___________。
2以算法在所有输入下的计算量的加权平均值作为算法的计算量,这种计算量称为算法的___________或___________。
27.最坏情况时间复杂性和平均时间复杂性统称为___________或___________。
28.在一般情况下,一个算法的时间复杂性是___________的函数。
29.一个算法的输入规模或问题的规模是指___________。
30.常见时间复杂性的量级有:
常数阶O(___________)、对数阶O(___________)、线性阶O(___________)、平方阶O(___________)、和指数阶O(___________)。
通常认为,具有指数阶量级的算法是___________,而量级低于平方阶的算法是___________的。
31.数据结构的基本任务是数据结构的___________和___________。
32.数据结构的课程的主要内容可以概括为:
___________、___________、___________和___________。
33.___________与数据元素本身的内容和形式无关。
34.从逻辑关系上讲,数据结构主要分为两大类,它们是___________和___________。
35.程序段“for(i=l;i<=n;i++){k++;for(j=1;j<=n;j++)l+=k;}”的时间复杂度T(n)=___________。
36.程序段“i=1;while(i<=n)i=i*2;”的时间复杂度T(n)=___________。
三、单项选择题
1.以下说法错误的是
①用数字式计算机解决问题的实质是对数据的加工处理
②程序设计的实质是数据处理
③数据的逻辑结构是数据的组织形式,基本运算规定了数据的基本操作方式
④运算实现是完成运算功能的算法,或这些算法的设计
⑤数据处理方式总是与数据某种相应的表示形式相联系,反之亦然
2.根据数据元素之间关系的不同特性,以下四类基本的逻辑结构反映了四类基本的
数据组织形式。
以下解释错误的是()
①集合中任何两个结点之间都有逻辑关系但组织形式松散
②线性结构中结点按逻辑关系依次排列形成一条"锁链"
③树形结构具有分支、层次特性,其形态有点像自然界中的树
④图状结构中的各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接
3.关于逻辑结构,以下说法错误的是()
①逻辑结构与数据元素本身的形成、内容无关
②逻辑结构与数据元素的相对位置有关
③逻辑结构与所含结点个数无关
④一些表面上很不相同的数据可以有相同的逻辑结构
⑤逻辑结构是数据组织的某种"本质性"的东西
4.根据操作的效果,可将运算分成加工型运算、引用型运算两种基本类型。
对于表格
处理中的五种功能以下解释错误的是()
①查找引用型运算,功能是找出满足某种条件的结点在s(线形结构)中的位置
②读取引用型运算功能是读出s(线形结构)中某指定位置结点的内容
③插入引用型运算,功能是在s(线形结构)的某指定位置上增加一个新结点
④删除加工型运算,功能是撤消s(线形结构)某指定位置上的结点
⑤更新加工型运算,功能是修改s(线形结构)中某指定结点的内容
5.一般地,一个存储结构包括以下三个主要部分。
以下说法错误的是()
①存储结点每个存储结点可以存放一个或一个以上的数据元素
②数据元素之间关联方式的表示也就是逻辑结构的机内表示
③附加设施,如为便于运算实现而设置的“哑结点”等等
6.一般地,一个存储结构包括以下三个主要部分。
以下说法错误的是
①每个存储结点只能存放一个数据元素()
②数据元素之间的关联方式可由存储结点之间的关联方式直接表达
③一种存储结构可以在两个级别上讨论。
其一是机器级,其二是语言级
④语言级描述可经编译自动转换成机器级因此也可以看成是一种机内表示
7.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质
量。
以下解释错误的是()
①正确性算法应能正确地实现预定的功能(即处理要求)
②易读性算法应易于阅读和理解以便于调试修改和扩充
③健壮性当环境发生变化时,算法能适当地做出反应或进行处理,不会产生不需要的运行结果
④高效性即达到所需要的时间性能
8.对于数据结构课程的主要内容,以下解释正确的是()
①数据结构的定义,包括逻辑结构、存储结构和基本运算集
②数据结构的实现,包括存储实现、运算实现和基本运算集
③数据结构的评价和选择,包括逻辑结构的选择、基本运算集的选择和存储
选择
9,与数据元素本身的形式、内容、相对位置、个数无关的是数据的()
①存储结构②存储实现③逻辑结构④运算实现10顺序存储结构()
①仅适合于静态查找表的存储
②仅适合于动态查找表的存储
③既适合静态又适合动态查找表的存储
④既不适合静态又不适合动态查找表的存储
11.算法的时间复杂度,都要以通过算法中执行频度最高的语句的执行次数来确定这种
观点()
①正确②错误
12以下说法正确的是()
①所谓数据的逻辑结构指的是数据元素之间的逻辑关系。
②逻辑结构与数据元素本身的内容和形式无关
③顺序文件只适合于存放在磁带上,索引文件只能存放在磁盘上
④基于某种逻辑结构之上的运算,其实现是惟一的
13以下说法正确的是()
①数据元素是数据的最小单位
②数据项是数据的基本单位
③数据结构是带有结构的各数据项的集合
④数据结构是带有结构的数据元素的集合
14以下说法错误的是()
①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体
②数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要而建立的③数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域
④数据项是数据的基本单位
15通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着()
①数据元素具有同一特点
②不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致
③每个数据元素都一样
④数据元素所包含的数据项的个数要相等
四、简答及应用
1数据与数据元素有何区别?
2·为什么说数据元素之间的逻辑关系是数据内部组织的主要方面?
3·逻辑结构与存储结构是什么关系?
4·运算与运算的实现是什么关系?
有哪些相同点和不同点?
5,类C语言与标准C语言的主要区别是什么?
五、算法设计
1、设计求解下列问题的类C语言算法,并分析其最坏情况时间复杂性及其量级。
(1)在数组A[1..n]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输出0作为标志。
(2)找出数组A[1..n]中元素的最大值和次最大值(本小题以数组元素的比较为标准操作)。
第二章线性表
一.名词解释
1.线性结构2.数据结构的顺序实现3.顺序表4.链表5.数据结构的链接实现
6.建表7.字符串8.串9.顺序串10.链串
二、填空题
1.为了便于讨论,有时将含n(n>=0)个结点的线性结构表示成(a1,a2,……an),其中每个ai代表一个______。
a1称为______结点,an称为______结点,i称为ai在线性表中的________或______。
对任意一对相邻结点ai、ai┼1(1<=i 2.为了满足运算的封闭性,通常允许一种逻辑结构出现不含任何结点的情况。 不含任何结点的线性结构记为______或______。 3.线性结构的基本特征是: 若至少含有一个结点,则除起始结点没有直接______外,其他结点有且仅有一个直接______;除终端结点没有直接______外,其它结点有且仅有一个直接______. 4.所有结点按1对1的邻接关系构成的整体就是______结构。 5.线性表的逻辑结构是______结构。 其所含结点的个数称为线性表的______,简称______. 6.表长为O的线性表称为______ 7.线性表典型的基本运算包括: ______、______、______、______、______、______等六种。 8.顺序表的特点是______。 9.顺序表的类型定义可经编译转换为机器级。 假定每个datatype类型的变量占用k(k>=1)个内存单元,其中,b是顺序表的第一个存储结点的第一个单元的内存地址,那么,第i个结点ai的存储地址为______。 10.以下为顺序表的插入运算,分析算法,请在______处填上正确的语句。 Voidinsert_sqlist(sqlistL,datatypex,inti) /*将X插入到顺序表L的第i-1个位置*/ {if(L.last==maxsize)error(“表满”); if((i<1)||(i>L.last+1))error(“非法位置”); for(j=L.last;j>=i;j--)______; L.data[i-1]=x; L.last=L.last+1; } 11.对于顺序表的插入算法insert_sqlist来说,若以结点移动为标准操作,则插入算法的最坏时间复杂性为________,量级是________。 插入算法的平均时间复杂性为________,平均时间复杂性量级是________。 12.以下为顺序表的删除运算,分析算法,请在________处填上正确的语句。 voiddelete_sqlist(sqlistL,inti)/*删除顺序表L中的第i-1个位置上的结点*/ {if((i<1)||(i>L.last))error(“非法位置”); for(j=i+1;j=L.last;j++)________; L.last=L.last-1; } 13.对于顺序表的删除算法delete_sqlist来说,若以结点移动为标准操作,最坏情况时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________和________。 14.以下为顺序表的定位运算,分析算法,请在________处填上正确的语句。 intlocate_sqlist(sqlistL,datatypeX) /*在顺序表L中查找第一值等于X的结点。 若找到回传该结点序号;否则回传0*/ {________; while((i≤L.last)&&(L.data[i-1]! =X))i++; if(________)return(i); elsereturn(0); } 15.对于顺序表的定位算法,若以取结点值与参数X的比较为标准操作,平均时间复杂性量级为________。 求表长和读表元算法的时间复杂性为________。 16.在顺序表上,求表长运算LENGTH(L)可通过输出________实现,读表元运算 GET(L,i)可通过输出________实现。 17.线性表的常见链式存储结构有________、________和________。 18.单链表表示法的基本思想是用________表示结点间的逻辑关系。 19.所有结点通过指针的链接而组织成________。 20.为了便于实现各种运算,通常在单链表的第一个结点之前增设一个类型相同的结点,称为________,其它结点称为________。 21.在单链表中,表结点中的第一个和最后一个分别称为________和________。 头结点的数据域可以不存储________,也可以存放一个________或________。 22.单链表INITIATE(L)的功能是建立一个空表。 空表由一个________和一个________组成。 23.INITIATE()的功能是建立一个空表。 请在________处填上正确的语句。 lklistinitiate_lklist()/*建立一个空表*/ {________________; ________________; return(t); } 24.以下为求单链表表长的运算,分析算法,请在________处填上正确的语句。 intlength_lklist(lklisthead)/*求表head的长度*/ {________; j=0; while(p->next! =NULL) {________________; j++; } return(j);/*回传表长*/ } 25.以下为单链表按序号查找的运算,分析算法,请在____处填上正确的语句。 pointerfind_lklist(lklisthead,inti) {p=head;j=0; while(________________) {p=p->next;j++;} if(i==j)return(p); elsereturn(NULL); } 26.以下为单链表的定位运算,分析算法,请在____处填上正确的语句。 intlocate_lklist(lklisthead,datatypex) /*求表head中第一个值等于x的结点的序号。 不存在这种结点时结果为0*/ {p=head;j=0; while(________________________________){p=p->next;j++;} if(p->data==x)return(j); elsereturn(0); } 27.以下为单链表的删除运算,分析算法,请在____处填上正确的语句。 voiddelete_lklist(lklisthead,inti) {p=find_lklist(head,i-1); if(____________________________) {q=________________; p->next=p->next; free(q); } elseerror(“不存在第i个结点”) } 28.以下为单链表的插入运算,分析算法,请在____处填上正确的语句。 voidinsert_lklist(lklisthead,datatypex,inti) /*在表head的第i个位置上插入一个以x为值的新结点*/ {p=find_lklist(head,i-1); if(p==NULL)error(“不存在第i个位置”); else{s=________________;s->data=x; s->next=________________; p->next=s; } } 29.以下为单链表的建表算法,分析算法,请在____处填上正确的语句。 lklistcreate_lklist1() /*通过调用initiate_lklist和insert_lklist算法实现的建表算法。 假定$是结束标志*/ {ininiate_lklist(head); i=1; scanf(“%f”,&x); while(x! =’$’) {________________; ________________; scanf(“%f”,&x); } return(head); } 该建表算法的时间复杂性约等于____________,其量级为____________。 30.以下为单链表的建表算法,分析算法,请在____处填上正确的语句。 lklistcreate_lklist2()/*直接实现的建表算法。 */ {head=malloc(size); p=head; scanf(“%f”,&x); while(x! =’$’) {q=malloc(size); q->data=x; p->next=q; ________________; scanf(“%f”,&x); } ________________; return(head); } 此算法的量级为________________。 31.除单链表之外,线性表的链式存储结构还有_________和_________等。 32.循环链表与单链表的区别仅仅在于其尾结点的链域值不是_________,而是一个指向_________的指针。 33.在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点,这样构成的链表中有两个方向不同的链,称为______。 34.C语言规定,字符串常量按______处理,它的值在程序的执行过程中是不能改变的。 而串变量与其他变量不一样,不能由______语句对其赋值。 35.含零个字符的串称为______串,用______表示。 其他串称为______串。 任何串中所含______的个数称为该串的长度。 36.当且仅当两个串的______相等并且各个对应位置上的字符都______时,这两个串相等。 一个串中任意个连续字符组成的序列称为该串的______串,该串称为它所有子串的______串。 37.串的顺序存储有两种方法: 一种是每个单元只存一个字符,称为______格式,另一种是每个单元存放多个字符,称为______格式。 38.通常将链串中每个存储结点所存储的字符个数称为______。 当结点大小大于1时,链串的最后一个结点的各个数据域不一定总能全被字符占满,此时,应在这些未用的数据域里补上______。 三、单向选择题 1.对于线性表基本运算,以下结果是正确的是() ①初始化INITIATE(L),引用型运算,其作用是建立一个空表L=Ф .②求表长LENGTH(L),引用型运算,其结果是线性表L的长度 ③读表元GET(L,i),引用型运算。 若1<=i<=LENGTH(L),其结果是线性表L的第i个结点; 否则,结果为0 ④定位LOCATE(L,X),引用型运算.若L中存在一个或多个值与X相等的结点,运算结果为这些结点的序号的最大值;否则运算结果为0 ⑤插入INSERT(L,X,i),加工型运算。 其作用是在线性表L的第i+1个位置上增加一个以X为值的新结点 ⑥删除DELETE(L,i),引用型运算.其作用是撤销线性表L的第i个结点Ai 2.线性结构中的一个结点代表一个() ①数据元素②数据项③数据④数据结构 3.顺序表的一个存储结点仅仅存储线性表的一个() ①数据元素②数据项③数据④数据结构 4.顺序表是线性表的() ①链式存储结构②顺序存储结构③索引存储结构④散列存储
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构习题 答案 全真模拟题 试题 数据结构 习题 模拟