北京工业大学《896数据结构》真题答案2016-2017

可编辑修改精选全文完整版国家开放大学(中央广播电视大学)2015年秋季学期“开放本科”期末考试数据结构(本)试题2016年1月一、单项选择题(每小题2分，共30分)1.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。

该矩阵A有( )列。

A.8 C.7B.9 D.10答案：102.子串“acd”在主串“abdcacdefac”中的位置是( )。

A.3 C.7B.5 D.1答案：53.序列12，16，8，4按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的不可能输出序列是( )。

(进栈、出栈可以交替进行)。

A.16，12，8，4B.4，8，12，16C.8，4，16，12D.16，12，4，8答案：B.4，8，12，164.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，对该队列进行出队操作，并把结点的值保存在变量e中，其运算为( )。

A.e=f->data；r=r->nextB.e=f->data；r->next=rC.e=f->data；f=f->nextD.e=f一>data；f一>next=f答案：C.e=f->data；f=f->next5.数据的逻辑结构在计算机内存中的表示是( )。

A.给相关变量分配存储单元C.数据的逻辑结构B.数据的存储结构D.算法的具体体现答案：数据的存储结构6.以下说法正确的是( )。

A.线性表的链式存储结构必须占用连续的存储空间B.一种逻辑结构可以有不同的存储结构C.一种逻辑结构只能有唯一的存储结构D.线性表的顺序存储结构不必占用连续的存储空间答案：一种逻辑结构可以有不同的存储结构7.在一个单链表中要删除p所指结点的后继结点，可执行q=p一>next；和( )。

A.p一>next=q->nextB.p=q->nextC.p->next=qD.p->next=q答案：A.p一>next=q->next8.在数据结构和算法中，与所使用的计算机有关的是( )。

2017版北京理工大学《889数据结构》全套考研资料我们是布丁考研网北理工考研团队，是在读学长。

我们亲身经历过北理工考研，录取后把自己当年考研时用过的资料重新整理，从本校的研招办拿到了最新的真题，同时新添加很多高参考价值的内部复习资料，保证资料的真实性，希望能帮助大家成功考入北理工。

此外，我们还提供学长一对一个性化辅导服务，适合二战、在职、基础或本科不好的同学，可在短时间内快速把握重点和考点。

有任何考北理工相关的疑问，也可以咨询我们，学长会提供免费的解答。

更多信息，请关注布丁考研网。

以下为本科目的资料清单（有实物图及预览，货真价实）：2017年北理工《数据结构》全套资料包含：一、北京理工大学《数据结构》历年考研真题2016年北理工《数据结构》考研真题2015年北理工《数据结构》考研真题2014年北理工《数据结构》考研真题2013年北理工《数据结构》考研真题2008年北理工《数据结构》考研真题2007年北理工《数据结构》考研真题2006年北理工《数据结构》考研真题2005年北理工《数据结构》考研真题2004年北理工《数据结构》考研真题2003年北理工《数据结构》考研真题二、北京理工大学889《数据结构》考研经验总结。

注意了：北理工889数据结构是近几年开始的科目，以前都是跟其他科目综合考试，2008年之后真题为回忆版，请大家了解好了再买，这些都是纯真题，买后不能退款。

三、北理工《数据结构》期末试题10套及答案。

...四、北理工《数据结构》考研复习提纲。

五、北理工《数据结构》考研题库及答案。

六、、严蔚敏《数据结构》全套教学视频48课时。

（电子版）七、、严蔚敏《数据结构》课后习题答案。

以下为截图及预览：2007年真题2016年真题课后习题及答案课后习题及答案2期中期末试卷期中期末试卷答案。

第一章概论一、选择题1、研究数据结构就是研究（D ）。

A. 数据的逻辑结构B。

数据的存储结构C. 数据的逻辑结构和存储结构D。

数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A。

空间复杂度和时间复杂度 B. 正确性和简单性C。

可读性和文档性D。

数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A。

图B。

树C。

广义表D。

栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、( B )等5个特性。

A. 可执行性、可移植性和可扩充性B。

可执行性、有穷性和确定性C。

确定性、有穷性和稳定性 D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C )。

for(i=0；i<m;i++）for(j=0;j〈n；j++）a[i］[j]=i＊j；A. O(m2) B。

O（n2) C。

O（m*n) D. O（m+n)6、算法是（D ）。

A。

计算机程序 B. 解决问题的计算方法C。

排序算法 D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8），其时间复杂度表示( C ）。

A。

O（n） B. O（nlog2n) C。

O（n2） D. O （log2n)8、下面程序段的时间复杂度为（ C ）.i=1；while(i<=n）i=i*3；A. O(n）B。

O(3n) C。

O(log3n) D. O(n3）9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B。

关系C。

运算D。

算法10、下面程序段的时间复杂度是（A ）。

i=s=0；while（s<n)｛i++；s+=i;}A. O(n) B。

O（n2）C。

O（log2n）D。

O(n3)11、抽象数据类型的三个组成部分分别为（A）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（)。

2013年北京理工大学一、选择题。

（每小题2分，共40分）1．数据结构在计算机中的表示称为______。

A．物理结构B．逻辑结构C．虚拟结构D．抽象结构2．数据结构对外的接口主要是通过______体现的。

A．数据对象B．数据关系C．基本操作D．数据元素3．设N是描述问题规模的非负整数，下面程序片段的时间复杂度是______。

x=N；while（x＞0）x=x/2；A．O(log2N) B．O(N) C．O(Nlog2N) D．O(N2)4．线性链表中一个结点所占用的空间______。

A．必须连续B．部分地址必须连续C．不一定连续D．连续与否无所谓5．将长度为m的单链表接在长度为n的单链表的后面，算法的时间复杂度为______。

A．O(n) B．O(1) C．O(m) D．O(m+n)6．设顺序表长度为n，从表中删除元素的概率相等。

则在平均情况下，从表中删除一个元素需要移动的元素个数是______。

A．(n－1)/2 B．n/2 C．n(n－1)/2 D．n(n+1)/27．在单链表中，增加一个头结点的目的是______。

A．方便运算的实现B．用于标识单链表C．使单链表至少有一个结点D．用于标识起始点的位置8．写出链栈的类型定义如下：9．一个栈的输入序列为a b c d e f，则下列序列中不可能的输出序列是______。

A．b c d a f e B．f e d c b aC．f e d c a b D．e d c b f a10．若一个栈以向量V[0..n－1]存储，设栈空时，栈顶指针top为n，则下面x进栈的正确操作是______。

A．top=top+1；V[top]=x；B．V[top]=x；top=top+1；C．top=top－1；V[top]=x；D．V[top]=x；top=top－1；11．一个队列的入队序列是a b c d e f，则队列的输出序列是______。

A．a b c d e f B．f e d c b aC．f e d c a b D．e d c b f a12．下列更适合表示队列的链表结构是______。

注意事项：1、下面关于串的叙述中，哪一个是不正确的？（ ）A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0 3、以下数据结构中，（ ）是非线性数据结构。

A ．树B ．字符串C ．队列D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

B ．线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，不必占用一片连续的存储单元。

D ．线性表采用链接存储，便于插入和删除操作。

5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。

A ．(rear-front+m)%mB ．rear-front+1C ．(front-rear+m)%mD ．(rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。

A ．p->next=s; s->next=p->next;B ．s->next=p->next; p->next=s;C ．p->next=s; p->next=s->next;D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。

A ．1，2，4，3B ．2，1，3，4C ．1，4，3，2D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。

A ．a 和(b,c),d,e B ．（a ）和(b,c),d,eC ．a 和 ((b,c)，d,e)D ．(a) 和((b,c)，d,e)9、栈和队都是（ ）A ．顺序存储的线性结构B ．链式存储的非线性结构C ．限制存取点的线性结构D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。

一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 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. 3.对线性表，在下列哪种情况下应当采用链表表示？(B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（D）。

A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D）参数。

A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A）。

A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（D）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的联系。

当结点之间存在M对N（M：N）的联系时，称这种结构为_图_。

北京工业大学2013回忆版试题首先题型：DS选择10分，一个一分，填空10个一个2分共20分，第三题为解答40分，4个题，第四题2个题一个15分。

C3个程序，读程序写结果，并指出程序的不足之处一个10分空30分算法描述题用文字描述的20分，要求写出程序一、数据结构(100分)选择题10分，10个题考的知识顺序可呢不一样，选项也可能顺序不一样,（忘了，记不清了，都是很基础的，希望其他的人补上吧）1. 下列排序算法那个是稳定的a，简单b快速c堆排序d冒泡（d）记住口诀吧，自己想的（简单希尔快速堆，或者杰西快堆，不稳定）2. 堆排序是急于什么来排序的a插入b选择c归并d3. 抽象数据结构的定义4.填空20分，10个题（其他的网了）1. 算法可行性的定义2. 快速排序的时候为什么需要事先将所有的数重新洗牌打乱顺序3. 迷宫算法为什么用栈保存走过的路径4. 对应的一个二叉树的线序ADBCFGECFMI中序DBCFGEACFIM请问对应的数有几颗，（中序中前边的那些字母顺序网了太多了，但不影响做题，A 右边的那4个字母应该是对的）5. 一个M*N矩阵，用行压缩存储，第一个存在了Loc（0,0），每个站L个单元，求aij的存储位置解答题第一题、某本数据结构的课本的目录是1．XXXXXX1.1XXXXXX1.2XXXXXX2．XXXXXX2.1XXXXXXX2.2XXXXXX……可以写出他的广义表表示为（1（1.1,1.2），2（2.1,2.2），……）（1）广义表的子表个代表目录的什么（2）广义表的广度深度个代表目录的什么（3）为广义表设计数据结构第二题（1）树经常转化为二叉树来进行操作，为什么（2）数的子孙节点转化成二叉树之间是什么关系（用例子说明）（3）数的兄弟节点在转化成二叉树的节点之间是什么关系（用例子说明）第三题对于一个有向图的邻接矩阵，（1）画出对应的有向图（2）写出3条从节点1到节点7的路径，以及路径长度（3）按照dijkstra算法思想，写出节点1到7的最短路径记忆路径长度第四题对于归并排序，当子快长度小于给定一个阙值时，（1）小于给定一个阙值时为什么用直接插入排序更好？（2）对于直接插入排序以及快速排序，从时间复杂度以及空间复杂度角度分析，用那个好？（还是基于归并排序）算法题（30分，一个15分）第一个给定一个二叉排序数，要求将二叉排序数的各个节点的数按从高到底的顺序插入到链表里比如：二叉树的中序序列为（1,2,4,6,8）则对应链表（8,6,4,2,1）题给了二差排序树的结构体，以及链表的结构体，假设链表头结点已给出了Int Convert(Bitree t,LinkList&H)第二个：现在手机GPS越来越普及了，输入对应的起点终点就可以看到从哪到哪的最短路径，以及最短时间（1）.问若对数据进行处理（还是设计来）需要事先知道那些数据（2）请对这设计数据结构二．C语言部分（50分）一．3个程序，根据程序写出结构来，并指出程序的不合理的地方一个10分二．一个算法描述题：（记得不是很清楚了，有个大体思路）大体思路如下：输入若干文本行，保存于line里，并用buf输出相应的行号与内容步骤1.n=0，x=1，i=0；2．Gets（lines）3．n = strlen(lines);4.if(n=0) 执行第7步（这里应该是执行第13步，可能有些小的步骤掉了，凑不出13步了）5.if(n>x)清空buf，X=n；将line里面的内容以及行号保存到buf6if（n=x）将line里面的内容以及行号保存到buf7 将buf里的内容输出1，描述算法的功能2，设计算法风华哥，我也来凑个热闹，提供个版本供大家参考：（2013北工大学硕&部分专硕考题情况）C语言：50分DS数据结构：100分总体来说不太难。

数据结构习题集含答案目录目录 (1)选择题 (2)第一章绪论 (2)第二章线性表 (4)第三章栈和队列 (6)第四章串 (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图 (11)第八章查找 (13)第九章排序 (14)简答题 (19)第一章绪论 (19)第二章线性表 (24)第三章栈和队列 (26)第四章串 (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图 (36)第八章查找 (38)第九章排序 (39)编程题 (41)第一章绪论 (41)第二章线性表 (41)第三章栈和队列 (52)第四章串 (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图 (52)第八章查找 (52)第九章排序 (57)选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的？(A ）A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（D ）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素,90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素,90分是数据元素4.*数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（C )A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（A )。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000二、3（20/8分）】A．效率 B.复杂性 C.现实性 D.难度2. 算法的时间复杂度取决于（）【中科院计算所1998二、1（2分）】A．问题的规模 B.待处理数据的初态 C. A 和 B3.计算机算法指的是（ 1），它必须具备（ 2）这三个特性。

(1) A．计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法(2) A ．可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D.易读性、稳定性、安全性【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（ 4 分）】4．一个算法应该是（）。

【中山大学1998二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和 C.5. 下面关于算法说法错误的是（）【南京理工大学2000一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000一、 2（ 1.5分）】(1 ）算法原地工作的含义是指不需要任何额外的辅助空间（ 2）在相同的规模n 下，复杂度 O(n) 的算法在时间上总是优于复杂度nO(2 ) 的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A． (1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学1996 一、4（ 2 分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学2000二、 1（2分）】A．循环队列 B.链表 C.哈希表 D.栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001一、 1（2分）】A．广义表 B.二叉树 C.稀疏矩阵 D.串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001一、 2（2 分）】A ．栈 B.哈希表 C.线索树 D.双向链表11．在下面的程序段中，对 x 的赋值语句的频度为（）【北京工商大学2001一、10（ 3 分）】FOR i:=1TOn DOFOR j:=1TOn DOx:=x+1;A． O(2n)B． O(n)C． O(n2)D． O(logn 2 )12．程序段FOR i:=n-1DOWNTO1DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与 A[j+1]对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（）A. O （ n）B. O(nlogn)C. O(n 3)D. O(n 2)【南京理工大学 1998 一、 1(2 分 ) 】13．以下哪个数据结构不是多型数据类型（）【中山大学1999一、 3（ 1 分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999一、 4】A．树B．字符串C．队D．栈15.下列数据中，（）是非线性数据结构。

《数据结构》试卷及答案1．算法分析的目的是( c )。

A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2．（ b ）是具有相同特性数据元素的集合，是数据的子集。

A.数据符号B.数据对象C.数据D.数据结构3．用链表表示线性表的优点是( C )。

A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同4．输入序列为（A,B,C,D）不可能的输出有（d）。

A.(A,B,C,D)B. (D,C,B,A)C. (A,C,D,B) D . (C,A,B,D)5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( b )。

A. front=maxSizeB. (rear+1)%maxSize=frontC. rear=maxSizeD. rear=front6．设有串t='I am a good student '，那么Substr(t,6,6)=（D）包含第六个A. studentB. a good sC. goodD. a good7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（ B ）。

A.23B.33C.18D. 408．已知广义表 LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（C）。

A. Gethead(Gethead(LS))B. Gettail(Gethead(LS))C. Gethead(Gethead(Gettail(LS)))D. Gethead(Gettail(LS))9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为(A ) 。

AB EC D FA. CDBGFEAB. CDBFGEA GC. CDBAGFED. BCDAGFE10．下列存储形式中，(c ) 不是树的存储形式。

2022年北京工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.92、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12116、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。

2017《数据结构》期末考试一试题及答案《数据结构》期末考试一试题及答案1..................................... .. (2)试题1答案............................................. ............................................... (7)《数据结构》期末考试一试题及答案2..................................... .. (9)试题2答案............................................. ............................................... (14)《数据结构》期末考试一试题及答案3..................................... (16)试题3答案............................................. ............................................... (21)第1页共23页《数据结构》期末考试一试题及答案 1一、单项选择题（每题2分，共20分）1. 栈和行列的共同特色是( )。

A.只同意在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点用链接方式储存的行列，在进行插入运算时().A.仅改正头指针B.头、尾指针都要改正C.仅改正尾指针D.头、尾指针可能都要改正以下数据结构中哪一个是非线性结构？()A.行列B.栈C.线性表D.二叉树4.设有一个二维数组A[m][n]，假定A[0][0]寄存地点在644(10)，A[2][2]寄存地点在676(10)，每个元素占一个空间，问A[3][3](10)寄存在什么地点？脚注(10)表示用10进制表示。

一、单项选择题(1)一个算法应该是〔〕。

A)程序B)问题求解步骤的描述C)要满足五个根本属性D)A和C(2)算法指的是〔〕。

A)计算机程序B)解决问题的计算方法C)排序算法D)解决问题的有限运算序列。

(3)与数据元素本身的形式、内容、相对位置、个数无关的是数据的〔〕。

A)存储结构B)逻辑结构C)算法D)操作(4)从逻辑上可以把数据结构分为〔〕两大类。

A)动态结构、静态结构B)顺序结构、链式结构C)线性结构、非线性结构D)初等结构、构造型结构以下表达中正确的选项是()。

A〕一个逻辑数据结构只能有一种存储结构B〕数据的逻辑结构属于线性结构，存储结构属于非线性结构C〕一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D〕一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率(6) 数据的根本单位是〔〕A)数据项B)数据类型C)数据元素(7)以下程序的时间复杂度为〔〕i=0；s=0；while〔s<n〕{i++；s=s+i；}A)O〔n〕B)O〔2n〕C)O〔n〕(8)以下程序段的渐进时间复杂度为〔〕。

for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)A[i][j]=i* j;A〕O(m2)B〕O(n2)C 〕O(m*n)程序段如下：sum=0；for(i=1;i<=n;i++)for(j=1;j<=n;j++) sum++；数据变量D)O〔n2〕D〕(m+n)其中n为正整数，那么最后一行的语句频度在最坏情况下是〔〕。

A〕O(n〕B)O(nlogn)C)O(n3)D)O(n2)(10 )在下面的程序段中，对x的赋值语句的频度为〔〕。

for(i=1;i>=n;i++)for(j=1;j>=n;j++)x:=x+1;A)O(2n)B)O(n)C)O(n2)D)O(log2n)(11)程序段for(i:=n-1;i<=1;i--〕for(j:=1;j>=i;j++ )if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}其中n为正整数，那么最后一行的语句频度在最坏情况下是〔〕。