算法与数据结构试卷B

中国矿业大学2011-2012学年《数据结构》试卷（A卷）（考试时间：100分钟）一. 填空（每空2分，共40分）1. 数据结构式具有相同性质的数据元素的（1）。

2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。

3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。

4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。

如果该二叉树有10层，则共有 (7) 个节点。

5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。

6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。

7. 一棵二叉树为则后序序列为（12），中序序列为（13），先序序列为__（14）____。

8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。

9.。

一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。

10. 有n个结点的无向完全图的边数分别为_______(18)_______。

11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。

12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。

数据结构试卷B(总7页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--试题 B一、填空题（18小题，40个空，每空分，共20分）1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

2、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

3、在顺序表中插入或删除一个元素，需要平均移动，具体移动的元素个数与有关。

4、在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。

5、顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置相邻。

6、若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为。

7、求下列广义表操作的结果：（1） GetHead【((a,b),(c,d))】=== ; //头元素不必加括号（2） GetHead【GetTail【((a,b),(c,d))】】=== ;（3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;8、一棵具有２５７个结点的完全二叉树，它的深度为。

9、设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。

10、图有、等存储结构，遍历图有、等方法。

11、n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为；若采用邻接表存储，该算法的时间复杂度为。

12、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。

13、假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。

绪论一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：集合＿、线性结构＿、树型结构＿、图状结构＿。

2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：顺序存储＿、链式存储＿、索引存储＿、散列存储＿。

二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（B ）。

A、正确性B、有穷性C、确定性D、可行性2、算法的每一步必须有确切的定义，也就是说，对于每步需要执行的动作必须严格、清楚地给出规定，这是算法的（A）。

A、正确性B、有穷性C、确定性D、可行性3、算法原则上都是能够有机器或人所完成的。

整个算法好象是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作，这是算法的（D）A、正确性B、有穷性C、确定性D、可行性三、简单题1、什么是数据结构？什么是算法？两者有什么关系？什么是数据结构？数据结构是按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。

什么是算法？广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”两者有什么关系？算法与数据结构关系密切。

选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。

2、什么是复杂度和空间复杂度？时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。

3、数据的逻辑结构分几种？存储结构又有哪几种？数据的逻辑结构：结构定义中的“关系”，描述的是数据元素之间的逻辑关系；包括线性结构（线性表、栈、队、串、数组）和非线性结构（图形结构、树形结构）；数据的存储结构（物理结构）：数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系德表示。

有顺序存贮（向量存贮）、链式存贮、索引存贮、散列存贮。

线性表1、一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第5 个元素的地址是( B)。

算法与数据结构期末考试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构被称为：A. 链表B. 栈C. 队列D. 数组2. 快速排序算法的时间复杂度在最坏情况下是：A. O(n)B. O(n log n)C. O(n^2)D. O(log n)3. 哈希表解决冲突最常用的方法是：A. 链地址法B. 线性探测法C. 二次探测法D. 双重哈希法4. 二叉树的遍历方式不包括：A. 前序遍历B. 中序遍历C. 后序遍历D. 广度优先遍历5. 堆排序算法是基于：A. 链表B. 栈C. 队列D. 堆...（此处省略其他选择题）二、简答题（每题10分，共20分）1. 请简述二叉搜索树与普通二叉树的区别。

2. 什么是递归？请举例说明递归在算法中的应用。

三、编程题（每题15分，共30分）1. 编写一个函数，实现对链表的反转。

2. 编写一个函数，实现快速排序算法。

四、综合应用题（每题15分，共30分）1. 描述如何使用哈希表实现一个简单的数据库索引系统。

2. 假设你有一个数组，其中包含了一些重复的数值，请编写一个算法来找出数组中出现次数超过数组长度一半的数值。

五、论述题（每题15分，共15分）1. 论述动态规划与贪心算法的区别，并给出一个动态规划问题的例子。

六、附加题（10分，可选做）1. 请设计一个算法，用于检测一个字符串是否是回文。

如果字符串是回文，请返回True，否则返回False。

注意：本试卷中所有题目的答案必须以书面形式给出，编程题需要提供完整的代码实现。

祝各位考生考试顺利，取得优异成绩。

一、填空题（每空2分，共12分）1. 数据结构被形式地定义为（D, R ），其中D 是数据元素的有限集合，R 是D上的__数据元素之间的关系______ 有限集合。

2.向一个长度为n 的线性表中删除第i 个元素(1≤i ≤n)时，需向前移动___n-i_____个元素。

3. 假设以S 和X 代表进栈和出栈操作，则对输入序列a,b,c,d,e 进行一系列操作SSXSXSSXXX 之后，得到的输出序列为___bceda_____。

4. 已知循环队列的存储空间为数组A[21]，front 指向队头元素的前一个位置，rear 指向队尾元素，假设front 和rear 的值分别为8和3，则该队列的长度为___16_____。

5.在有序表A[0…17]中，采用折半查找法查找关键字等于A[7]的元素，需比较元素的下标依次为 8 3 5 6 7 。

6. 在堆排序、快速排序和归并排序方法中，稳定的排序方法是 归并排序 。

二、单项选择题（每小题2分，共40分）1. 数据结构中，与所使用的计算机无关的是数据的（ C ）结构。

A.存储B. 物理C. 逻辑D.物理和存储2. 算法分析的两个主要方面是（ A ）A. 空间复杂性和时间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性3.在n 个结点的顺序表中，算法的时间复杂度是O （1）的操作是（ A ）A.访问第i 个结点（1≤i ≤n ）和求第i 个结点的直接前驱（2≤i ≤n ）B.在第i 个结点后插入一个新结点（1≤i ≤n ）C.删除第i 个结点（1≤i ≤n ）D. 将n 个结点从小到大排序 4． 线性表Ｌ在（ B ）情况下适用于使用链式结构实现。

A.需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.Ｌ中含有大量的结点D.Ｌ中结点结构复杂 5. 经过以下栈运算后，x 的值是（ A ）InitStack(s); Push(s, 'a');Push(s, 'b');Pop(s,x);GetTop(s,x); A.a B.b C.1 D.06. 循环队列存储在数组A[0…m]中，则入队时的操作为（ D ）。

数据结构与算法同步训练模拟试题及答案解析(1/43)选择题第1题下列叙述中正确的是()。

A.循环队列是队列的一种链式存储结构B.循环队列是队列的一种顺序的存储结构C.循环队列是非线性结构D.循环队列是一种逻辑结构下一题(2/43)选择题第2题算法的有穷性是指()。

A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用上一题下一题(3/43)选择题第3题算法的空间复杂度是指()。

A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数上一题下一题(4/43)选择题第4题定义无符号整数类为UInt，下面可以作为类UInt实例化值的是()。

A.-369B.369C.0.369D.整数集合{1,2,3,4,5}上一题下一题(5/43)选择题第5题下列叙述正确的是()。

A.算法就是程序B.设计算法时只需要考虑数据结构的设计C.设计算法时只需要考虑结果的可靠性D.以上三种说法都不对上一题下一题(6/43)选择题第6题下列叙述中正确的是()。

A.有一个以上根结点的数据结构不一定是非线性结构B.只有一个根结点的数据结构不一定是线性结构C.循环链表是非线性结构D.双向链表是非线性结构上一题下一题(7/43)选择题第7题下列关于线性链表的叙述中，正确的是()。

A.各数据结点的存储空间可以不连续，但他们的存储顺序与逻辑顺序必须一致B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间不需连续C.进行插入数据与删除数据时，不需要异动表中的元素D.以上说法均不对上一题下一题(8/43)选择题第8题下列叙述中正确的是()。

A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间上一题下一题(9/43)选择题第9题下列叙述中正确的是()。

《算法与数据结构》课程期中试卷一、判断题（本大题共10小题。

每小题1分，共10分。

） （注意：将判断结果填入以下表格中。

对的打√，错的打×。

）1. 算法分析的目的是研究算法中输入和输出的关系。

（ 错 ）2. 可以随机访问任一元素是链表具有的特点。

（ 错）3. 用一维数组存储一棵完全二叉树是有效的存储方法。

（对 ）4. 在队列第i 个元素之后插入一个元素不是队列的基本运算。

（ 错 ）5. Tail （Tail （Head （((a,b),(c,d))）））= (b)。

（ ）6. 如果一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历下的最后一个结点。

（ 错）比如只有根节点和左子树的特殊情况。

7. 由权值分别为3, 8, 6, 2的叶子生成一棵哈夫曼树，它的带权路径长度为35。

（对 ） 带权路径长度=1*8+2*6+3*3+3*2=35（书P146）8. Head （Tail （Head （((a,b),(c,d))）））= (b)。

（ ）9. 数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。

（对 ）逻辑结构、存储结构和数据的操作（运算）三个方面10. 线性的数据结构可以顺序存储，也可以链接存储；非线性的数据结构只能链接存储。

（错 ） 比如完全二叉树。

二、单项选择题（本大题共15小题。

每小题2分，共30分。

）（注意：以下各题只有一个正确答案，请将选择的结果填入以下表格中。

） 1. 下面程序段的时间复杂度为________。

s=0；for (i=1；i<n ；i++) for (j=1；j<i ；j++) s += i*j ；A. O(1)B. O(logn)C. O(n)D. O(n 2)[D] 就是s= s +i*j ；运算次数 ，T=(1+2+3…………n)=n(n+1)/2,为n^22. 以下数据结构中哪一个是线性结构_ ___。

A. 有向图B. 线索二叉树C. 队列D. 二叉排序树[C]堆栈，线性表（循序表，链表），队列都是线性结构。

数据结构和算法选择题(总10页) -本页仅作为预览文档封面，使用时请删除本页-(1) 下面叙述正确的是______。

(C)A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对(2) 以下数据结构中不属于线性数据结构的是______。

(C)A. 队列B. 线性表C. 二叉树D. 栈(3) 在一棵二叉树上第5层的结点数最多是______。

(B)A. 8B. 16C. 32D. 15(4) 下面描述中，符合结构化程序设计风格的是______。

(A)A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B. 模块只有一个入口，可以有多个出口C. 注重提高程序的执行效率D. 不使用goto语句(5) 下面概念中，不属于面向对象方法的是______。

(D)A. 对象B. 继承C. 类D. 过程调用(6) 在结构化方法中，用数据流程图（DFD）作为描述工具的软件开发阶段是______。

(B)A. 可行性分析B. 需求分析C. 详细设计D. 程序编码(7) 在软件开发中，下面任务不属于设计阶段的是______。

(D)A. 数据结构设计B. 给出系统模块结构C. 定义模块算法D. 定义需求并建立系统模型(8) 数据库系统的核心是______。

(B)A. 数据模型B. 数据库管理系统C. 软件工具D. 数据库(9) 下列叙述中正确的是______。

(C)A. 数据库是一个独立的系统，不需要*作系统的支持B. 数据库设计是指设计数据库管理系统C. 数据库技术的根本目标是要解决数据共享的问题D. 数据库系统中，数据的物理结构必须与逻辑结构一致(10) 下列模式中，能够给出数据库物理存储结构与物理存取方法的是______。

(A)A. 内模式B. 外模式C. 概念模式D. 逻辑模式(11) 算法的时间复杂度是指______。

华东交通大学2012—2013学年第一学期考试卷试卷编号： （B ）卷数据结构 课程 课程类别：必考生注意事项：1、本试卷共5页，总分100分，考试时间120分钟。

2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。

一、选择题(每题2分，共20分)1、栈和队列的共同特点是( A )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2、用链接方式存储的队列，在进行插入运算时( D ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改 3、以下数据结构中哪一个是非线性结构？( D )A. 队列B. 栈C. 线性表D. 二叉树4、 设指针变量p 指向单链表中结点A ，若删除单链表中结点A ，则需要修改指针的操作序列为（ A ）。

(A) q=p->next ；p->data=q->data ；p->next=q->next ；free(q)； (B) q=p->next ；q->data=p->data ；p->next=q->next ；free(q)； (C) q=p->next ；p->next=q->next ；free(q)； (D) q=p->next ；p->data=q->data ；free(q)；5、 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A ［3］的比较序列的下标依次为( D )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，3承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。

专业 班级 学号 学生签名：6、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。

湖南机电职业技术学院成人教育《算法与数据结构》期末考试复习题作业一一、单选题(第1-25题每题4分)1.以下说法正确的是(A)数据项是数据的基本单位(B)数据元素是数据的最小单位(C)数据结构是带结构的数据项的集合(D)一些表面上很不相同的数据可以有相同的逻辑结构[参考答案：D]2.在决定选取何种存储结构时，一般不考虑(A)各结点的值如何(B)结点个数的多少(C)对数据有哪些运算(D)所用的编程语言实现这种结构是否方便[参考答案：A]3.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储(A)数据的处理方法(B)数据元素的类型(C)数据元素之间的关系(D)数据的存储方法[参考答案：C]4.在数据结构中，从逻辑上可以把数据结构分为(A)动态结构和静态结构(B)紧凑结构和非紧凑结构(C)线性结构和非线性结构(D)内部结构和外部结构[参考答案：C]5.存储稀疏矩阵通常采用（）(A)链接存储结构(B)顺序结构(C)二维数组(D)三元组线性表[参考答案：D]6.运算符放在连个运算对象后面的算术表达式称为（）(A)前缀表达式(B)中缀表达式(C)后缀表达式(D)波兰式[参考答案：C]7.在计算机中算术表达式的计算是通过（）来实现的(A)树(B)图(C)队列(D)栈[参考答案：D]8.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的(A)快速排序(B)堆排序(C)归并排序(D)插入排序[参考答案：B]9.设某强连通图中有n个顶点，则该强连通图中至少有（）条边(A)n(n-1)(B)n+1(C)n(D)n(n+1)[参考答案：C]10.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）(A)n，e(B)e，n(C)2n，e(D)n，2e[参考答案：D]11.如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用(A)只有表头指针没有表尾指针的循环单链表(B)只有表尾指针没有表头指针的循环单链表(C)非循环双链表(D)循环双链表[参考答案：B]12.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）(A)O(1)(B)O(log2n)(C)2(D)O(n)[参考答案：B]13.设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21。