江苏大学2006年《数据结构》考研专业课真题试卷

数据结构考研真题和答案数据结构是计算机科学中的重要基础课程，对于计算机专业的学生而言，掌握好数据结构非常关键。

考研阶段，数据结构也是一个必考科目。

本文将介绍一些常见的数据结构考研真题以及详细的答案解析，希望能帮助同学们更好地备考。

1. 简述线性表的定义，举例说明线性表的应用场景。

线性表是数据结构中最基本的一种结构，它是由相同数据类型的有限个数据元素组成的序列。

线性表的特点是存储结构唯一，数据元素之间是一对一的关系。

在实际应用中，线性表常用来表示一组某种类型的数据集合，例如存储学生的学号信息、存储职工的工号信息等。

2. 解释栈的特点及其应用场景。

栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作，表的另一端称为栈顶。

栈的插入操作称为入栈，删除操作称为出栈。

栈的特点是后进先出（LIFO），即最后插入的元素最先被删除。

栈在实际应用中有很多场景，例如函数调用栈、表达式求值、撤销操作等。

3. 什么是队列？请给出队列的一个实际应用案例。

队列也是一种特殊的线性表，它的特点是只允许在表的一端进行插入操作，而在另一端进行删除操作。

队列的插入操作称为入队，删除操作称为出队。

队列的特点是先进先出（FIFO），即最先插入的元素最先被删除。

队列在实际应用中有很多场景，例如排队、任务调度、消息队列等。

4. 什么是树结构？请简要介绍树结构的一些应用。

树是一种非线性的数据结构，它由n（n>=1）个有限节点组成一个具有层次关系的集合。

树的特点是一个节点可以有多个子节点，但是只能有一个父节点，除根节点外，每个节点可以有多个子节点。

树结构在实际应用中广泛存在，例如文件系统、组织结构、网络拓扑等。

5. 解释二叉树的定义，并给出一种常见的二叉树结构。

二叉树是一种特殊的树结构，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的定义为一个有限的节点集合，该集合可以为空，如果非空则必须满足：（1）有且仅有一个称为根的节点；（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、下面程序段的时间复杂度是（）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（）。

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

数据构造习题集含答案目录目录 (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.某班级的学生成绩表中查得X三同学的各科成绩记录，其中数据构造考了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〕。

苏州大学2014年硕士研究生入学考试初试试题科目代码：872 科目名称：数据结构与操作系统满分：150分注意：①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上；③本试题纸须同答题纸一并交回。

一、数据结构部分注意：算法可以用类C、类C++、类JAVA或类PASCAL等语言编写，并请写出类型说明。

1.判断，若错，改正。

15分(1) 在一个图中，所有顶点度数之和等于所有边的总数。

(2) 快排在被排序的数据已经基本有序的情况下最易发挥长处。

(3) 求子串的定位操作成为串的模式匹配。

2.Dijkstra用途，思想，验证其正确性，及图的数据结构。

3.将数的质因数分解并按递减顺序写成一个有序单链表。

如：2100->7.5.5.3.2.24.二叉链的二叉树，递归，验证是否严格二叉。

（无度为1的结点）5.顺序表，整数，长为n，尽可能高效求得第n/4个元素。

二、操作系统部分6、判断，若错，改正。

15分(1)任何操作系统中，系统资源分配最小单位为线程。

(2)死锁的进程必然至少一个互斥资源。

(3)虚拟存储器大小为内外存之和。

(4)文件访问效率有两个，物理结构和逻辑结构。

(5)spooling可以减少进程上下文切换次数。

7、从文件逻辑结构，物理结构和文件目录三方面入手，举实例说明如何提高存取速度（还是效率？就那个意思！）。

8、资源共享，创建和结束三方面说明进程和它创建的子进程，进程和他创建的线程之间的关系。

9、分页存储（二级页表），页表存于内存：(1) 一次访问内存200NS，求访问一个内存单元多少时间。

(2) 若三级页表，多少时间？(3) 引入联想寄存器，90%的页表项可在快表中命中，则一次访存时间？（假设一次快表10NS）(4) 若虚拟存储，页面命中率80%，缺页处理5万NS/次，则一个内存单元多少时间？(5) 采用虚拟存储，命中率80%，缺页时有10%需要置换(不用置换的缺页处理4万NS/次，否则8万NS/次)，同问。

数据结构试题库及答案第一章概论一、选择题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(log 3n)D. O(n 3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ ）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（ ）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n 2)C. O(log 2n)D. O(n 3)11、抽象数据类型的三个组成部分分别为（ ）。

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

06数据结构（50分）一、单选题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填写在题干后面的括号内。

每小题1分，共10分）1.数据的基本单位是（）A.数据项B.数据类型C.数据对象D.数据元素2.若频繁的对线性表进行插入和删除操作，则该线性表应该采用_______存储结构。

（）A.顺序B.链式C.散列D.任意3.若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的出栈次序是（）A.7，5，3，9B.9，7，5，3C.7，5，9，3D.9，5，7，34.下面的说法中，正确的是（）A.字符串的长度指串中包含的字母的个数B.字符串的长度指串中包含的不同字符的个数C.一个字符串不能说是其自身的一个子串D.若T包含在S中，则T一定是S的一个子串5.广义表（（a，b），（c，d））的表尾是（）A.dB.c，dC.（c，d）D.（（c，d））6.n个顶点的连通图，其生成树有_______条边。

（）A.n-1B.nC.n+1D.不确定7.若一棵二叉树有8个度为2的结点，则该二叉树的叶节点个数为（）A.7B.8C.9D.不确定8.在有n个节点的二叉链表中有_______个空链域。

（）A.n+1B.nC.n-1D.不确定9.在等概率的情况下，采用顺序插查找法查找长度为n的线性表，平均查找长度为（）A.nB.n/2C.(n+1)/2D.(n-1)/210.下列排序方法中，排序的比较次数与序列的初始排列状态无关的是（）A.选择排序B.插入排序C.冒泡排序D.快速排序二、填空题（本大题共10小题，每小题1分，共10分）1.假定一个顺序队列的队首和队尾分别为f和r，则判断队空的条件为__________________。

2.在顺序存储的线性表中插入或删除一个元素平均约移动表中__________________的元素。

3.设有一个二维数组A[5][4]，按行序优先存储，A[0][0]的存储地址是10，每个数组元素占2个字节，则A[3][2]的存储地址是______________。

江 苏 大 学 试 题（2008 -2009 学年第2 学期）课程名称 数据结构（A ） 开课学院 理学院使用班级 数学071信计071 考试日期 2009-6-3 题号 一 二 三 四 五 六 七 八 总分 核查人签名 得 分 阅卷教师一．选择题 (每题2分，共计20分；每题仅有一个正确答案) 1. 下述哪一条是顺序存储结构的优点？（ ）A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双向链表 C．带头结点的单链表 D．单循环链表 3. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )A. 1和5B. 2和4C. 4和2D. 5和1 4. 下面关于串的叙述中，哪一个是不正确的？（ ）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储5. 有一个100×90的元素值为整型的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组顺序表表示该矩阵时，所需的字节总数是（ ）。

A. 60 B. 66 C. 18000 D. 33 6. 设一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ ）A． 4321 B. 2341 C. 1234 D. 21347. 在单链表的指针为p的结点之后插入指针为s的结点，正确的操作是（ ）A. p->next=s;s->next=p->next;B. p->next=s->next;p->next=s;C. p->next=s;p->next=s->next;D. s->next=p->next;p->next=s; 8. 二叉树的第I层上最多含有结点数为（ ）A．2I B． 2I-1-1 C． 2I-1 D．2I-1学生所在学院 专业、班级 学号 姓名江 苏 大 学 试 题 第2页9. 当一个有n个顶点的有向图用邻接矩阵A表示时，顶点Vi的出度是（ ）A ．B ．C ．D ．n i=1A[i,j]∑n j=1A[i,j]∑n i=1A[j,i]∑n ni=1j=1A[i,j]A[j,i]+∑∑10. 下面给出的四种排序法中,( )排序法是不稳定的排序法。

[考研类试卷]计算机专业基础综合数据结构（排序）历年真题试卷汇编9一、综合题1 如果只要找出一个具有n个元素的集合的第k(1≤k≤n)个最小元素，你所学过的排序方法中哪种最适合?给出实现的思想。

【北方交通大学1998六(10分)】2 设结点个数为n，请问采用堆排序法进行排序，其时间复杂性是多少?请以大O 形式给出，并给出证明。

【上海交通大学2004四(10分)】2 已知待排序的序列为(503，87，512，6l，908，170，897，275，653，462)，试完成下列各题。

3 根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。

4 输出最小值后，如何得到次小值(并画出相应结果图)。

【同济大学2001二(10分)】4 试将关键字序列(56，塾，55，67，46，58，18，88)5 调整成一个初始大顶堆，用二叉树形式说明调整过程；6 简要说明如何从初始大顶堆开始进行排序。

【华中科技大学2007四、24(10分)】7 一组记录的关键字为(50，79，8，56，32，41，85)，给出利用重建堆方法建立的初始堆(堆顶最大)，并给出堆排序的过程。

【吉林大学2007二、5(4分)】8 已知序列{503，87，512，61，908，170，897，275，653，462)将其调整为堆(大堆顶，即K i≥K2i，K i≥K2i+1)。

【中国海洋大学2006一、4(8分)】9 给定关键字序列(20，18，9，86，72，12，27，40)。

试将该序列建成小根堆。

10 判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。

①100，90，80，60，85，75，20，25，10，70，65，50②100，70，50，20，90，75，60，25，10，85，65，80【复旦大学1997二(8分)】11 全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

数据结构试题库及答案第一章 概论一、选择题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(m 2)B. O(n 2)C. O(m*n)D. O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog 2n+n 2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog 2n)C. O(n 2)D. O(log 2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log 3n)D. O(n 3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ ）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（ ）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n 2)C. O(log 2n)D. O(n 3)11、抽象数据类型的三个组成部分分别为（ ）。

计算机专业基础综合数据结构（集合）历年真题试卷汇编1(总分：82.00，做题时间：90分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。

(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。

【华中科技大学2007四、25(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(2)ASL 成功 =(6*1+2*3+5+7)／10=24／10(3)ASL 失败=(4+3+2+1+2+1+1+2+1+9+8)／11=34／1 1。

计算方法参见上面58题(3)。

)解析：2.采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。

(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。

【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(2)装填因子=9／13=0．7 (3)ASL SUCC =11／9 (4)ASL UNSUCC =29／13)解析：3.设散列表长度为14i为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，用拉链法处理冲突，要求：(1)构造散列表；(2)求出在等概率情况下，查找成功的平均查找长度。

考研数据结构试题（含答案）我以⼀名⼤学⽣的⼈格尊严保证，在本场考试中，⾃觉遵守考试纪律，服从考试管理，决不作弊或帮助别⼈作弊！签名：学院专业学号级班··················密···················封·····················线··················命题⼈签字：系主任签字：审核院长签字：共印份数：第1页共6页聊城⼤学计算机学院2012—2013学年第1学期期末考试2011级《数据结构》试题（闭卷B卷）⼀、单项选择题（共15题，每题2分，共30分）1.研究数据结构就是研究（D ）。

A．数据的逻辑结构B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其基本操作2.在数据结构中，从逻辑上可以把数据结构分为（C ）。

A．动态结构和静态结构B．紧凑结构和⾮紧凑结构C．线性结构和⾮线性结构D．内部结构和外部结构3.算法分析的两个主要⽅⾯是（A ）。

A．空间复杂度和时间复杂度B．正确性和简单性C．可读性和⽂档性D．数据复杂性和程序复杂性4.下⾯程序段的时间复杂度是（ C ）。

（完整版）数据结构试题及答案《数据结构》自考复习思考试题○10一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合C. 类型的有限集合D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )A. n-i+1B. iC. i+1D. n-i3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( )A. head==NULLB. head->next==NULLC. head!=NULLD. head->next==head4. 引起循环队列队头位置发生变化的操作是( )A. 出队B. 入队C. 取队头元素D. 取队尾元素5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( )A. 2，4，3，1，5，6B. 3，2，4，1，6，5C. 4，3，2，1，5，6D. 2，3，5，1，6，46. 字符串通常采用的两种存储方式是( )A. 散列存储和索引存储B. 索引存储和链式存储C. 顺序存储和链式存储D. 散列存储和顺序存储7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为( )A. mB. n-mC. n-m+1D. n8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为( )A. 429B. 432.C. 435D. 4389. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )A. (e,f)B. ((e,f))C. (f)D. ( )10. 下列图示的顺序存储结构表示的二叉树是( )11. n个顶点的强连通图中至少含有( )A. n-1条有向边B. n条有向边C. n(n-1)/2条有向边D. n(n-1)条有向边12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为( )A. (19，23，56，34，78，67，88，92)B. (23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92)D. (19，23，67，56，34，78，92，88)13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( ) A. 4 B. 5C. 8D. 914. 由同一关键字集合构造的各棵二叉排序树( )A. 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同.D. 其形态均相同，平均查找长度也都相同15. ISAM文件和VSAM文件的区别之一是( )A. 前者是索引顺序文件，后者是索引非顺序文件B. 前者只能进行顺序存取，后者只能进行随机存取C. 前者建立静态索引结构，后者建立动态索引结构D. 前者的存储介质是磁盘，后者的存储介质不是磁盘二、填空题(本大题共10小题，每空2分，共20分)16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。

计算机专业基础综合数据结构（线性表）历年真题试卷汇编5(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.线性表是一个( )。

【电子科技大学2010一、1(2分)】【江苏大学2005一、1(2分)】（分数：2.00）A.有限序列，可以为空√B.有限序列，不能为空C.无限序列，可以为空D.无限序列，不能为空解析：2.线性表的顺序存储结构是一种( )。

【北京理工大学2006五、3(1分)】（分数：2.00）A.随机存取的存储结构√B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构解析：3.(多选)在下列叙述中， ( )是错误的。

【华中科技大学2006一、1(2分)】（分数：2.00）A.线性表的逻辑顺序与物理顺序总是一致的√B.二叉树的顺序存储结构比链式存储结构节省存储空间√C.二叉树的度小于等于2D.每种数据结构都具有两种基本运算(操作)：插入、删除元素(结点) √解析：4.能在O(1)时间内访问线性表的第i个元素的结构是( )。

【电子科技大学2011一、2(2分)】（分数：2.00）A.顺序表√B.单链表C.单向循环链表D.双向链表解析：5.下面关于线性表的叙述中，错误的是哪一个?( )【北方交通大学2001一、14(2分)】（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作√C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作解析：6.线性表是具有n个( )的有限序列(n>0)。

【清华大学1998一、4(2分)】（分数：2.00）A.表元素B.字符C.数据元素√D.数据项E.信息项解析：7.单链表中，增加一个头结点的目的是( )。

【厦门大学2003一、1(2分)】（分数：2.00）A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现√D.说明单链表是线性表的链式存储解析：8.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( )存储方式最节省时间。

第一章概论一、选择题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个方面评价算法的质量，以下解释错误的是（）。

2006级(嵌入式软件与系统、计算机应用方向)《数据结构》期终考试试卷学号姓名一、单项选择题(每题1分，共15分)1.在计算机科学中，算法指的是( )A. 计算机程序B. 描述问题的方法C. 解决问题的有限步骤序列D. 排序算法2.在数据结构中，可用存储顺序代表逻辑顺序的数据结构为( )A. 顺序结构B. 二叉排序树C. 链式结构D. Hash表3.在数据结构中，按逻辑结构可把数据结构分为( )A. 静态结构和动态结构B. 线性结构和非线性结构C. 顺序结构和链式结构D. 内部结构和外部结构4.对链式存储的正确描述是( )A. 结点之间是连续存储的B. 结点内单元是连续存储的C. 各结点类型可以不一致D. 各结点的地址由小到大5.在下列关于“串”的陈述中，正确的说明是( )A. 串中元素只能是字母B. 串的长度必须大于零C. 串是一种特殊的线性表D. 空串就是空白串6.设A[n][n]为一个对称矩阵，数组下标从[0][0]开始。

为了节省存储，将其下三角部分按行存放在一维数组B[0..m-1]，m=n(n+1)/2，对下三角部分中任一元素a ij(i≥j)，它在一维数组B 的下标k值是( )A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j7.对一个满二叉树中，若把它存储到一维数组中(数组下标从0开始)，则元素下标为k的右儿子下标是( ) (不考虑数组下标越界的问题)A. ⎣k/2⎦B. ⎡k/2⎤C. 2k+1D. 2k+28.已知一棵二叉树的后序和中序序列分别是dabec和debac，则先序序列是( )A. acbedB. decabC. cedbaD. deabc9.对一个含n个顶点和e条边的无向图(无环)，其邻接矩阵中零元素的个数为( )A. eB. 2eC. n2 - eD. n2 - 2e10.假设一个有n个顶点和e条弧的有向图用邻接矩阵表示，则删除与某个顶点v i相关的所有弧的时间复杂度是( )A. O(n)B. O(e)C. O(n+e)D. O(n×e)11.下面关于栈特征的错误描述是( )A. FILOB. FIFOC. 数据可用数组或链表存储D. 弹出数据时，要先检验栈空12.下面关于队列特征的正确描述是( )A. FILOB. FIFOC. 只能用数组来实现队列D. 循环队列不受存储空间限制13.下列排序算法中，时间复杂度最差的是( )A. 选择排序B. 桶(基数)排序C. 快速排序D. 堆排序14. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为 ( )A. 顺序存储结构B. 链式存储结构C. 散列存储结构D. 索引存储结构 15. 在一个顺序存储的有序序列中查找指定的关键字，其时间复杂度的下界是 ( )A. O (log n )B. O (n log n )C. O (n )D. O (1) 二、已知一个无向图的顶点集为{ a , b , c , d , e , f }，其邻接矩阵如下所示(0-无边,1-有边)。