下载文档原格式
2015年华中科技大学887数据结构与算法分析真题（回忆版）一．名词解释1.1（二叉树结点的）平衡因子1.2有向完全图1.3空间复杂度1.4（图的）广度优先搜索1.5二叉搜索树二．选择题2.1函数形式是⎪⎩⎪⎨⎧-=+-<=其他如果如果，)),1((12%,1)2(00)(n A A n n A n n A ，那么函数的时间复杂度是__________。
)(.A n O )log (.B n n O )(.C 2n O 记不清了.D2.2以下排序方法中时间复杂度比较稳定的是_______。
冒泡排序.A 选择排序.B 记不清了.C 归并排序.D2.3后续表达式求值。
2.4在长度为n 的数组中进行查找，成功查找的时间复杂度是________。
2.A n 21.B -n 21.C +n2.5题目给出的时间复杂度形式类似23log )(n n n n n n O ++=，则时间复杂度为_______。
三．大题3.1给出二叉树的中序遍历和后序遍历，试画出二叉树。
3.2给出九个数，用这九个数构成一颗哈夫曼树，并给出每一个数的哈夫曼编码。
3.3给出八个数，运用数组将这八个数构造成一个小根堆，并写出构造过程。
3.4有向图中共有0V 到6V 七个节点，运用Dijkstra 算法求出从0V 到其余点的最短路径，并写出过程。
3.5假设数组][a 中的元素增序排列并且每个元素的值均不相同，试设计算法确定是否存点点i 使得i i a =][，并给出算法的时间复杂度。
四．算法设计4.1运用函数)*(__int root BTNode leaves of number 设计算法计算二叉树中叶子结点的个数。
4.2在一个数组中如果j i <并且][][j A i A >，则称i 和j 为一对逆序对，请设计算法计算数组][n A 中的逆序对数，要求算法的时间复杂度为)log (n n O 。
2015年考研必备资料2015年考研计算机数据结构试题及答案目录2015年考研计算机数据结构试题及答案（1） (2)2015年考研计算机数据结构试题（1） (2)2015年考研计算机数据结构试题答案（1） (5)2015年考研计算机数据结构试题及答案（2） (6)2015年考研计算机数据结构试题（2） (6)2015年考研计算机数据结构试题答案（2） (9)2015年考研计算机数据结构试题及答案（3） (11)2015年考研计算机数据结构试题（3） (11)2015年考研计算机数据结构试题答案（3） (13)2015年考研计算机数据结构试题及答案（4） (15)2015年考研计算机数据结构试题（4） (15)2015年考研计算机数据结构试题答案（4） (17)2015年考研计算机数据结构试题及答案（5） (19)2015年考研计算机数据结构试题（5） (19)2015年考研计算机数据结构试题答案（5） (21)2015年考研计算机数据结构试题及答案（1）2015年考研计算机数据结构试题（1）一、选择题(24分)1.下列程序段的时间复杂度为( )。
i=0，s=0; while (s(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列( )存储方式最节省运算时间。
(A) 单向链表 (B) 单向循环链表(C) 双向链表 (D) 双向循环链表3.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。
(A) s->next=p->next;p->next=-s; (B) q->next=s; s->next=p;(C) p->next=s->next;s->next=p; (D) p->next=s;s->next=q;4.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。
习题1 参考答案1至8题答案略。
9.（1）【解】该逻辑结构为线性结构，其图形表示如下：（2）【解】该逻辑结构为树型结构，其图形表示如下：（3）【解】该逻辑结构为图型结构，其图形表示如下：（4）【解】该逻辑结构为线性结构，其图形表示如下：10.【解】该图书库存管理系统所要处理的数据对象为图书，所以该问题中涉及的数据元素为图书，设数据元素类型为bookType 类型。
每个数据元素应包含的数据项有图书编号、书名、作者、出版社、出版日期等。
可用一个表格（如下表）的形式表示图书间的逻辑关系，即该问题数学模型可采用简单的线性结构来表示。
根据问题需求功能目标，此模型的所需的主要处理操作有插入、删除、查找和修改等基本操作。
所以，现用抽象数据类型bookList 表示问题模型，其逻辑结构与基本操作的定义如下： （1）逻辑结构bookList=( D, {r} )D={b i | b i 为bookType 类型的元素，i=1,2,3, ....., n ，n ≥0} r ={ <bk i ,b i+1>| i=1,2,…, n -1, n ≥0 } （2）基本操作 ①初始化操作函数：InitBookList(&BL)。
……初始条件：图书表BL 不存在。
操作结果：构造一个空的图书表BL 。
②求图书表长度操作函数：bookListLength(BL)。
初始条件：图书表BL 已存在。
操作结果：返回图书表BL 中所包含的数据元素（图书）的个数。
③取图书表中元素操作函数：getBook(BL, i, &b)。
初始条件：图书表BL 已存在，且1≤i ≤bookListLength(BL)。
操作结果：用b 返回图书表BL 中的第i 个数据元素的值。
④按编号查找操作函数：locateById(BL, id)。
初始条件：图书表BL 已存在，id 是给定的一个图书编号。
操作结果：返回图书表BL 中图书编号为id 的数据元素的位序，若这样的数据元素不存在，则返回0。
线性表的顺序存储结构是一种（）的存储结构。
选择一项：A. 随机存取B. 顺序存取C. Hash存取D. 索引存取反馈正确答案是：随机存取题目2获得2.00分中的2.00分标记题目设单链表中指针p指向结点A，q指向新元素结点，若要A之后插入一个新元素，则所需修改指针的操作为（）。
选择一项：A. p->next=q->next，q->next=pB. p->next=p，q->next=p->nextC. p->next=q，q->next=p->nextD. q->next=p->next，p->next=q反馈正确答案是：q->next=p->next，p->next=q题目3获得2.00分中的2.00分标记题目在关键字序列（149，138，165，197，176，113，127）中采用最低位优先排序(LSD)基数排序，第一趟之后所得结果为（）。
选择一项：A. 113，127，138，149，165，176，197B. 128，149，165，197，113，127，176C. 149，138，165，197，176，113，127D. 128，149，165，197，113，176，127反馈正确答案是：128，149，165，197，113，176，127题目4获得2.00分中的0.00分标记题目4个顶点的有向完全图有（）个弧。
选择一项：A. 12B. 10C. 8D. 6反馈正确答案是：12题目5获得2.00分中的2.00分标记题目数据元素的存储结构，通常采用（）。
选择一项：A. 链式结构B. 顺序结构C. 散列结构D. 顺序和链式组合结构反馈正确答案是：顺序结构题目6获得2.00分中的2.00分标记题目栈和队列的共同点是（）。
选择一项：A. 进出原则都是后进先出B. 都是插入删除操作受限的线性表C. 不允许在任意端点处插入和删除元素D. 进出原则都是先进先出反馈正确答案是：都是插入删除操作受限的线性表题目7获得2.00分中的2.00分标记题目串通常采用块链存储的优点是（）。
2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改) 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)）的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)的全部内容。
2012年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上可以把数据结构分为 C 。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。
A．数据的存储结构B．数据结构C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C .A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便.6．以下说法正确的是 D 。
A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A .（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O(n2) 。
1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系与操作等的科学。
2.数据(data)是对客观事物的符号表示，在计算机科学中是指所有以输入到计算机中并被计算机程序处理的符号的总称。
3.数据元素(data element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑与处理。
4.数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。
5.数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。
6.根据数据结构之间关系的不同特性，通常有下列4类基本结构:集合、线性结构、树形结构、图状结构或网状结构。
7.抽象数据类型(ADT)：是指一个数学模型以及定义在该模型上的一组操作，有“数据抽象”与“数据封装”两个重要特性。
8.算法(algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，具有“有穷性”，“确定性”，“可行性”，“输入”，“输出”五个特性。
9.算法设计的要求：正确性、可读性、健壮性、效率与低存储需求。
10.一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。
1.线性表：是n个数据元素的有限序列，有顺序存储与链式存储两种表示形式。
2.线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，包括两个域，其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。
3.循环链表是另一种形式的链式存储结构。
它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
4.双向链表是指有两个指针域，其一指向直接后继，另一指向直接前趋。
栈是限定仅在表尾进行插入或删除操作的线性表。
华中师范大学网络学院《数据结构》试题库及答案一、选择题1 在数据结构中，从逻辑上可以把数据结构分成（）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和非内部结构2．算法分析的目的是（）；Ａ. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性3. 算法分析的两个主要方面是（）。
A. 空间复杂度和时间复杂度B. 正确性和简单性C．可读性和文档性 D. 数据复杂性和程序复杂性4．一个顺序表（即顺序存储的线性表）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．100 B．108 C．100 D．1205．在一个长度为n 的顺序表中，向第i个元素（1≤i≤n＋１）之前插入一个新元素时，需要向后移动（）个元素。
A.n-iB.n-i-1C.n-i+1D.i6．从一个长度为n 的顺序表中删除第i个元素（1≤i≤n＋１）时，需要向前移动（）个元素。
A.n-iB.n-i-1C.n-i-1D.i7．若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素的算法的时间复杂度是（）Ａ.O(n) B.O(n*n) C.O(nlog2n) D.O(log2n)8．线性表的存储结构是一种（）的存储结构A．随机存取B．顺序存取C．索引存取D．HASH存取9.线性表的链式存储结构是一种（）的存储结构。
A．随机存取B．顺序存取C．索引存取D．HASH存取10．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,则第12个元素的存储地址是（）A．112 B.144 C.148 D.41211．若频繁地对线性表进行插入和删除操作，该线性表应该采用（）存储结构。
A．散列 B.顺序 C.链式 D.任意12．线性表若采用链表存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不边疆的D．连续不连续都可以13．在非空线性链表中，在由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行（）A．q->next=p; p->next=q;B．q->next=p->next; p->next=q;C．q->next=p->next; p=q;D．p->next=q; q->next=p;14．若删除非空线性链表中由p所指链结点的直接后继结点的过程是依次执行( )A．r=p->next; p->next=r; call RET(r)B．r=p->next; p->next=r->next; call RET(r)C．r=p->next; p->next=r->next; call RET(p)D．p->next=p->next->next; call RET(p)15．删除一个双链表中结点p(非头结点和尾结点)的操作是( ).A. p->left->right=p->left;p->right->left=p->rightB. p->left->right=p->right;p->right->left=p->ieftC. p->left=NULL;p->right=NULLD. p->right->left=p;p->left->right=p16．在一个双链表中结点p之后插入一个结点s的操作是( )。
1、已知一颗二叉树的先序遍历：ABCDEFGHI ，中序遍历：DCEBAGIHF ，根据已知画出这颗二叉树，并写出它的后序遍历。
2、将如图所示的森林转换成二叉树。
3、假定用于通信的电文由8个字符A 、B 、C 、D 、E 、F 、G 、H 组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼树，求出每个字符的编码，计算出平均码长。
4、对于如图所示的带权无向图，用图示说明利用Kruskal 算法构造最小生成树的过程。
5、下图给出了一个具有15个活动、11个事件的工程的AOE 网，求关键路径。
C D E F G A B H I LJK3e 1f dc b a g 979 4 6 2 1 85 486、假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为HT[0..12]，若采用除留余数法（H= key MOD13）构造哈希函数和线性探测法处理冲突，试画出最后得到的哈希表，并求出在等概率且都成功的情况下的平均查找长度。
7、待排序列为（39，80，76，41，13，29，50，78，30，11，100，7，41，86），步长因子分别取5、3、1，给出采用希尔排序方法按关键字递增序排列时的每一趟结果。
参考答案：1、后序遍历：DECBIHGFAAB FC GD E HI2、3、哈夫曼树CDEFGABHILJK259 918433012 152757100哈夫曼编码：A:0011 B:01 C:0010 D:1010E:000 F:100 G:11 H:1011平均码长：(4*5+2*25+4*4+4*7+3*9+3*12+2*30+4*8)/100=2.694、利用Kruskal 算法构造最小生成树的过程如图ae f d c b g 初始状态 a e f d c b g 增加第2条边 1 1 a efd c bg 增加第1条边 1 3 a e f d c bg 增加第5条边21 413 a e f d c b g 增加第4条边 2 1 1 a e f d c b g 增加第3条边 2 1 13 a e f d c b g 增加第6条边 21 46 15、求解过程如下：6、元素 初始哈希地址最终哈希地址0 1 2 3 4 5 6 7 8 9 10 11 12 平均查找长度为14/107、解：排序过程如下：p=5 39 80 76 41 13 29 50 78 30 11 100 7 41 86子序列分别为{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}。
9. 1 一、选择题1、一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始 堆为（B ）。
A 、 79， 46， 56， 38， 40， 80B 、 84, 79， 56， 38, 40, 46C 、 84, 79, 56， 46， 40, 38D 、 84, 56， 79， 40, 46, 38 2、 排序趟数与序列原始状态（原始排列）有关的排序方法是（ACD ）方法。
A 、插入排序 B 、选择排序 C 、胃泡排序 D 、快速排序 3、 下列排序方法中，（B ）是稳定的排序方法。
A 、直接选择排序B 、二分法插入排序C 、希尔排序D 、快速排序4、 数据序列（8, 9，10, 4, 5, 6, 20，1，2）只能是下列排序算法中（C ）的两趟 排序后的结果。
A 、选择排序B 、冒泡排序C 、插入排序I ）、堆排序5、 对序列（15, 9, 7, 8, 20, -1，4）进行排序，进行一趟排序后，数据的排列变为（4, 9，-1，8，20, 7，15）,则采川的足（C ）排序。
A 、选择B 、快速C 、希尔D 、百泡6、 一组待排序记录的关键字为（46, 79, 56, 38, 40, 84），则利用快速排序，以第 一个记录为基准元素得到的一次划分结果为（C ）。
A 、（38, 40, 46, 56, 79, 84）B 、（40, 38, 46, 79, 56, 84）C 、（40, 38, 46, 56, 79, 84）D 、（40, 38, 46, 84, 56, 79）7、 用直接插入排序对下凼叫个序列进行排序（由小到大），元素比较次数最少的是（C ）0A 、94, 32, 40, 90, 80, 46, 21，69 C 、21, 32, 46, 40, 80, 69, 90, 94D 、90, 69, 80, 46, 21, 32, 94, 408、荇用冒泡排序对关键字序列（18,16, 14,12,10,8）进行从小到大的排序，所需进行 的关键字比较总次数是（B ）。
计算机专业基础综合数据结构（集合）历年真题试卷汇编4(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：20，分数：40.00)1.下列二叉排序树中，满足平衡二叉树定义的是( )。
【2009年全国试题4(2分)】（分数：2.00）√解析：2.下列叙述中，不符合m阶B树定义要求的是( )。
【2009年全国试题8(2分)】（分数：2.00）A.根结点最多有m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接√解析：解析：一棵m阶的B树的定义如下：或为空树，或为满足下列特性的m叉树： (1)树中每个结点至多有m棵子树； (2)若根结点不是叶子结点，则至少有两棵子树； (3)除根结点之外的所有非终端结点至少有[m／2]棵子树；(4)所有的非终端结点中包含下列信息数据(n，P0，P 0，P 1，K 2，P 2，…，K n，P n )，其中：K i (i=1，…，n)为关键字，且K i i+1(i=1，…，n一1)，P i(i=0，…，n)为指向子树根结点的指针，且指针P i-1所指子树中所有结点的关键字均小于K i(i=1，…，n)，P n所指子树中所有结点的关键字均大于K n，n(｜m／2｜—1≤n≤m一1)为关键字的个数； (5)所有叶子结点都出现在同一层次上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。
据此，选择答案D不符合B树定义，D描述的是B+树，B+树的叶结点本身按照关键字的大小，自小而大顺序链接。
3.在下图所示的平衡二叉树中，插入关键字48．舌得到一棵新平衡二叉树。
在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是( )。
【2010年全国试题4(2分)（分数：2.00）A.13、48B.24、48C.24、53 √D.24、90解析：解析：失去平衡的最小子树根结点是24，需做RL型调整。
复习题集一判断题（×）1．线性表在物理存储空间中也一定是连续的。
（×）2．顺序存储方式只能用于存储线性结构。
（√）3．栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（√）4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（×）5．二叉树的度为2。
（√）6．若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）7．二叉树中每个结点的两棵子树的高度差等于1。
（√）8．用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（×）9．在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。
（×）10．计算机处理的对象可以分为数据和非数据两大类。
[计算机处理的对象都是数据]（×）11．数据的逻辑结构与各数据元素在计算机中如何存储有关。
（×）12．算法必须用程序语言来书写。
（×）13．判断某个算法是否容易阅读是算法分析的任务之一。
（×）14．顺序表是一种有序的线性表。
[任何数据结构才用顺序存储都叫顺序表]（√）15．分配给顺序表的内存单元地址必须是连续的。
（√）16．栈和队列具有相同的逻辑特性。
[它们的逻辑结构都是线性表]（√）18．树形结构中每个结点至多有一个前驱。
（×）19．在树形结构中，处于同一层上的各结点之间都存在兄弟关系。
（×）20．如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。
（×）21．如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。
（×）22．顺序查找方法只能在顺序存储结构上进行。
（×）23．折半查找可以在有序的双向链表上进行。
（√）24．满二叉树中不存在度为1的结点。
数据结构（C++版）复习要点考试说明：考试时间为 120 分钟，总分 100 分。
考试题型为：一、单选题：（每小题 1分，本大题共 10 分）二、填空题：（每空 2 分，本大题共 20分）三、简答题 :（每小题 5分，本大题共 50 分）四、算法设计题 :（每小题 10分，本大题共 20 分）第一章绪论本章主要介绍了一些基本概念。
对于本章内容的掌握主要以概念为主。
主要知识要点1、理解数据、数据元素、数据项、数据对象、数据类型、数据结构的概念。
2、掌握如何用二元组来表示一个数据结构。
掌握数据的四类基本逻辑结构（集合、线性结构、树型结构、图状或网状结构）。
3、理解顺序存储方法和链式存储方法是怎样存储数据的。
4、时间复杂度和空间复杂度（给程序能写出复杂度），常用操作的时间复杂度。
例题：1.设某数据结构的二元组形式表示为A=（D，R）， D={01， 02，03，04， 05，06，07，08，09} ，R={r} ，r={＜01 ，02＞，＜01，03＞，＜01，04＞，＜02，05＞，＜02，06＞，＜03，07＞，＜03，08＞, ＜03, 09＞}，则数据结构 A是（D ）。
A．线性结构 B. 树型结构 C. 物理结构 D. 图型结构2.下面程序的时间复杂为（ B ）for （ i=1 , s=0； i＜=n ； i++ ） {t=1 ； for（j=1 ； j＜=i ；j++） t=t*j ；s=s+t ；}2 3 4A.O（n）B. O（n 2）C. O（n 3）D. O（n 4）3.数据的物理结构主要包括________ 顺序___和___链式______ 两种情况。
4.下面程序段的时间复杂度是 i=s=0; while（s＜n） { i++; s+=i; } 第一次执行完 s+=i, s = 1第二次 s = 3 = 1+2 第三次 s = 6 = 1+2+3 第四次 s = 10 = 1+2+3+4 第 k 次s=1+2+3+4+...+k == k*（k+1）/2那么当 k*（k+1）/2 ＞=n 的时候停止,即 k = 关于 n 的表达式是根号的 , n 1/2第二章线性表本章主要介绍了线性表的定义、存储方式的描述和基本运算以及实现算法。
