下载文档原格式
湖北文理学院 2011－2012 学年度下学期《数据结构与算法》试卷A专业：计算机科学与技术姓名： 学号： 班级：一、判断题（本题共10小题，每小题1分，共计10分）。
（正确的打√，错的打×）1、顺序循环队列Q 空的条件是：Q.front==Q.rear.( )2、关键路径是始点到终点最小长度的路径。
( )3、序列（5, 6, 7, 20, 15, 8, 9, 25, 22，13）是一个堆。
( )4、在插入排序和选择排序中，若原始记录已基本有序，则较适合选用选择排序。
( )5、顺序表是随机存取，存取操作的时间为O （1）。
( )6、已知一棵二叉树的先序序列和后序序列，一定能构造出该二叉树。
() 7、有向图用邻接矩阵表示后，顶点i 的出度等于邻接矩阵中第i 行的元素个数。
( ) 8、归并排序的时间性能不随记录序列中关键字的分布而改变（与初始状态无关）。
( ) 9、在数据结构中，数据的基本单位是数据项。
（）10、对任意一个图，从某顶点出发进行一次广度优先或深度优先遍历，可访问图的所有顶点。
( )二、填空题（本题共10小题，每小题 2 分，共计 20分）。
（请将正确答案填入空格内，答案是确定和唯一的）1、任意一棵具有n 个结点的二叉树，若它有m 个叶子，则该二叉树上度为1的结点数为_____个。
2、常用算法的描述方法有：自然语言 、 、 和流程图。
3、某二叉树的先根遍历序列为IJKLMNO ，中根遍历序列为JLKINMO ，则该二叉树中根结点的右孩子是 。
4、堆排序的时间复杂性为，空间复杂性为。
5、二维数组A[6，7]，按行优先存储，每个元素占2个字节,A基址为600,则元素A[4,5]的存储地址是。
6、对广义表C=（a,（b,c,d））的运算 Tail(Tail(Head((Tail(C))))的结果是。
7、设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为_________________________________________。
2011-2012学年第一学期期末考查《数据结构》试卷（答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1分，共10分）1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D）A.O(0)B.O(1)C.O(n)D.O(n2)2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D）A.543612B.453126C.346512D.2341563.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ）A.8B.9C.10D.114.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ）A. m-nB.m-n-1C.n+1D.m+n5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A.9B.11C.15D.不确定6.下列哪一个方法可以判断出一个有向图是否有环。
（A）A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。
A.73B.234C.235D.2368.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B）A.（100,80,90,60,120,110,130）B.（100, 120, 110,130,80, 60,90）C.（100,60,80,90,120,110,130）D.（100,80, 60,90, 120, 130,110）9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 2584 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ）A.选择排序B.起泡排序C.快速排序D.插入排序10.对线性表进行折半查找时，要求线性表必须（D）A.以顺序方式存储B.以顺序方式存储，且数据元素有序C.以链接方式存储D.以链接方式存储，且数据元素有序二、填空（每空1分，共15分）1.数据结构中评价算法的两个重要指标是时间复杂度、空间复杂度。
计算机专业基础综合数据结构（图）历年真题试卷汇编1(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：20，分数：40.00)1.下列关于无向连通图特性的叙述中，正确的是( )。
【2009年全国试题7(2分)】I．所有顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1（分数：2.00）A.只有I √B.只有ⅡC.I和ⅡD.I和Ⅲ解析：解析：无向图中一条边要连接两个顶点，因此顶点的度数之和必为偶数。
n个顶点的无向连通图至少需要n-1条边。
无向连通图并不要求“至少有一个顶点的度为1”。
2.若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是( )。
【2010年全国试题7(2分)】（分数：2.00）A.6B.15C.16 √D.21解析：解析：要保证n个顶点的无向图G在任何情况下都是连通的，则需要先由n-1个顶点组成完全图，从第n个顶点引一条到n-1任一顶点的边，则图肯定是连通的。
本题先由6个顶点组成完全图，需要6(6-1)／2=15条边，故按题目要求“需要的边数最少”是15+1=16。
3.对下图进行拓扑排序，可以得到不同拓扑序列的个数是( )。
【2010年全国试题8(2分)（分数：2.00）A.4B.3 √C.2D.1解析：4.下列关于图的叙述中，正确的是( )。
【2011年全国试题8(2分)】I．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路（分数：2.00）A.仅ⅡB.仅I、ⅡC.仅Ⅲ√D.仅I、Ⅲ解析：解析：图中第1个顶点和最后一个顶点相同的路径称为回路或环。
序列中所有顶点不重复出现的路径称为简单路径，邻接矩阵的大小只和顶点个数相关，存储稀疏图，用邻接表比邻接矩阵更省空间。
拓扑序列成功的前提是有向图中不存在回路。
5.对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是( )。
北京师范大学2011～2012学年第 1 学期期末考试试卷（A 卷）课程名称： 数据结构 任课教师姓名： 刘玉铭卷面总分： 100 分 考试时长： 100 分钟 考试类别：闭卷 院（系）: 数学科学学院 专 业： 年级: 2010 姓 名： 学 号：阅卷教师（签字)：一、 单项选择题(每题2分，共10题20分）1．以下那一个术语与数据的存储结构无关？ 。
A ．栈B ．哈希表C ．线索树D ．双向链表2．链表不具有的特点是 。
A ．插入、删除不需要移动元素B ．可随机访问任一元素C ．不必事先估计存储空间D ．所需空间与线性表长度成正比3．算术表达式a+b*(c+d/e ）转为后缀表达式后为 。
装订线A．ab+cde/* B．abcde/+＊+C．abcde/*++ D．abcde＊/++4．二维数组A[10][20］采用列优先的存储方法,若每个元素占2个存储单元，设A[0］[0］的地址为100，则元素A[7]［6］的存储地址为。
A．232B．234C．390D．3925．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点,则度为0 的结点个数是 .A．9B．11C．15D．不确定6．一棵二叉树中序序列为FE ABDC，后序序列为F BADC E，则层序序列为。
A。
ABCDEF B. EFCDBA C。
FECDAB D。
EFCDAB7．在有向图G 的拓扑序列中,若顶点Vi 在顶点Vj 之前,则下列情形不可能出现的是 .A．G 中有弧〈Vi,Vj>B．G 中有一条从Vi 到Vj 的路径C．G 中没有弧<Vi,Vj〉D．G 中有一条从Vj 到Vi 的路径8．对于二叉排序树，下面的说法是正确的。
A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合B．对二叉排序树进行层序遍历可得到有序序列C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/29．一组记录的关键字为{47、75、55、30、42、90}，则用快速排序方法并以第一个记录为支点得到的第一次划分结果是 .A. 30,42,47,55，75，90B. 42,30,47，75，55,90C. 42，30，47,55，75，90D. 42，30,47，90,55,7510．下述文件中适合于磁带存储的是。
湖北文理学院 2011－2012 学年度下学期《数据结构与算法》试卷B专业：计算机科学与技术姓名： 学号： 班级：一、判断题（本题共10小题，每小题1分，共计10分）。
（正确的打√，错的打×）1、空串和空格串是相同的。
( )2、数据的存储结构是数据及其逻辑结构在计算机中的物理表示。
( )3、大顶堆（最大堆）中，最大值一定为根结点。
( )4、栈是特殊的线性表，它的插入和删除分别在线性表的两端进行。
( )5、稀疏矩阵一般采用三元组顺序表方法压缩存储。
( )6、 若二叉排序树（搜索树）中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。
( )7、有向图用邻接表表示后，顶点i 的出度等于邻接表中顶点i 后链表的长度。
( ) 8、链接线性表是顺序存取的线性表。
( )9、哈希函数进行模除取余时，最好取素数进行模除。
（ ） 10、归并排序是一种稳定的排序算法。
（ ）二、填空题（本题共10小题，每小题 2 分，共计 20分）。
（请将正确答案填入空格内，答案是确定和唯一的）1、在数据结构中，从逻辑上可以把数据结构分成 和 。
2、限在表尾进行插入和删除操作的线性表称为 。
3、实现二分查找（对半搜索）的存储结构仅限于顺序存储结构，且其中元素排列必须是_______的。
4、在拓扑排序中，拓扑序列的第一个顶点必须是 的顶点。
5、在一个长度为n 的顺序表中删除第i 个元素，则需要移动 个元素。
6、二维数组A[6，7]，按列优先存储，每个元素占4个字节,A 基址为500,则元素A[4,6]的存储地址是 。
7、深度为k二叉树中最多可有个结点。
8、任意写出二叉树的两种存储结构，分别是和。
9、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数是。
10、快速排序平均时间复杂性为，平均空间复杂性。
三、选择题（本题共18小题，每小题 1分，共计 18 分）。
（从下列答案中选出一个正确答案，并将对应的字母填入括号内）1．线性表的顺序存储结构是一种( )的存储结构。
2011年——2012年第二学期《数据结构》期末试卷（A）一、选择题：（每小题2分，共30分）1、如果在表示树的孩子兄弟链中有6个空的左指针域，7个空的右指针域，5个结点左、右指针域都为空，则该树中树叶的个数（ B ）A、有7个B、有6个C、有5个D、不能确定2、数据结构是一门研究（ B ）的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。
A、数值计算B、非数值计算C、混合计算D、简单计算3、如果用孩子兄弟链来表示一棵具有n(n>1)个结点的树，则在二叉链表中（ B ）A、至少有n-1个非空的右指针域B、至少有2个空的右指针域C、至少有2个非空的左指针域D、至少有n-1个空的右指针值域4、数据结构在计算机内存中的表示是指（ A ）。
A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系5、计算机处理的对象之间通常存在着的一种最简单的线性关系，这类数学模型称（ A ）。
A、线性的数据结构B、图的数据结构C、格局D、树型数据结构6、算法的主要任务是分析（ D ）A、算法是否具有较好的可读性B、算法中是否存在语法错误C、算法的功能是否符合设计要求D、算法执行时间和问题规模之间的关系7、用孩子链存储结构表示树，其优点之一是（ D ）比较方便A、判断两个指定结点是不是兄弟B、找指定的结点双亲C、判断指定结点在第几层D、计算指定结点的度数8、线性表采用链式存储结构时，其地址（ D ）A、必须是连续的B、一定是不连续的C、部分地址必须是连续的D、连续与否均可以9、在一个单链表中，删除*p结点之后的一个结点操作是（ D ）A、p next=p;B、p next next=p next;C、p next next=p;D、p next=p next next；10、栈和队列的共同点是（ C ）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点11、元素ABCD依次进栈后，栈顶元素是（ D ）栈底元素是（A ）A、AB、BC、CD、D12、串是（ D ）A、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列13、串是一种特殊的线性体现在（ B ）A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符14、对于一棵具有n个结点，度为4的树来说，（ A ）。
计算机科学与工程学院集中性实践教学计划书( 2011-2012 学年第二学期课程名称:数据结构与算法课程设计专业:计算机科学与技术软件工程、网络工程班级:计算机科学与技术101-6软件工程101-4网络工程101-4课程负责人:李锡祚、王玲芬、李威指导教师分配情况:专业指导教师计算机科学与技术李威、李笑牛、张恒博、云健、刘爽、包书哲软件工程王玲芬、王鹏杰、王存睿、孙世昶、网络工程李锡祚、姜楠、王晓强、王波教学起止周:第1 至3 教学周一、教学目的与要求:数据结构与算法课程设计的目的是使同学们能够根据数据对象的特性,合理的组织数据并能综合运用数据结构与算法基本知识和程序设计基本知识解决实际问题,培养基本的、良好的程序设计技能。
二、主要阶段、内容、时间及地点安排(以天为单位计:阶段与内容第1阶段:指导教师布置设计任务并解析有关题目的设计指标和任务的具体内容,学生选择题目,明确问题描述和要求,查阅资料。
(1天;各班长或学习委员将本班的选题表交给辅导教师,一人一题,每道题的选择人数原则上不能超过3人,第一天课程设计结束后,每名学生都要确定题目。
第2阶段:明确题目要求、确定数据结构、设计算法,编写程序、调试程序、测试程序(11天;第一周,学生应明确题目要求、确定数据的逻辑结构和存储结构、实现基本操作的编码与调试、实现主菜单。
第二周,完成核心算法的设计、编码与调试。
第三周,完成剩余任务的编码与调试,准备足够的测试数据,对软件进行测试与调试。
第3阶段:完成设计任务,准备验收、答辩(1天;第4阶段:答辩(上机演示,回答教师提问(1天;第5阶段:撰写课程设计报告(2天。
地点与时间地点:金石滩校区图书馆时间:计算机科学与技术:课程设计上机时间表周一周二周三周四周五第一周上午、下午上午第2大节、下午第二周上午、下午上午第2大节、下午第三周上午、下午上午第2大节、下午(验收软件工程:课程设计上机时间表周一周二周三周四周五第一周上午、下午上午、下午下午第二周上午、下午上午、下午下午第三周上午、下午上午、下午下午(验收网络工程:课程设计上机时间表周一周二周三周四周五第一周上午、下午上午下午上午第二周上午、下午上午下午上午第三周上午、下午上午下午上午(验收注:上午8:30~11:10下午1:40~4:20三、课程设计题目及具体要求:1.成绩管理问题描述:给出n个学生的考试成绩表,成绩表包括学生的学号、姓名、考试成绩(高等数学、英语、物理,设计一个简单的成绩管理程序。
安徽大学2011—2012学年第2学期《 数据结构 》考试试卷（A 卷）（闭卷 时间120分钟）考场登记表序号一、填空题（每小题1分，共12分）1. 数据结构包含数据的 ___________、存储结构和数据的运算三方面的内容。
2. 带头结点的单循环链表Head 的判空条件是____________________。
3. 队列的操作特点是 。
4. 有一个10*10的对称矩阵A ，采用压缩存储方式，则需要 个元素的存储空间。
5. 广义表(a,b,c,d)的表尾是 。
6. 在一棵二叉树上第10层的结点数最多为 个。
7. 对于长度为18的顺序存储的有序表，若采用折半查找，则比较4次就查找到的元素共有_ _个。
8. 由权值为9,2,5,7的四个叶子结点构造的哈夫曼树的高度为 。
9. 假定一组记录为（46，79，56，25，76，38，100，40，80），对其进行快速排序的第一次划分（以46为枢轴记录）后，右区间内元素的个数为_ _。
10. 设有一个空栈，现有输入序列1，2，3，4，5，经过push ，push ，pop ，push ，pop ，push ，push 后，输出序列是 。
11. 在一个图中，所有顶点的度数之和等于所有边数的 倍。
12. 设哈希表长m=14，哈希函数为h(k)=k % 11，用二次探测再散列处理冲突。
表中已有4个记录，其存储地址分别为：h(15)=4，h(84)=7，h(38)=5，h(61)=6。
此时再插入关键字为49的记录，则其存储地址是。
二、单项选择题（每小题2分，共20分）院/系 年级 专业 姓名 学号答 题 勿 超 装 订 线 ------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------1. 下列函数中渐近时间复杂度最小的是（ ）。
A. 12()log 5000T n n n n =+B. 22()8000T n n n =-C. 2log 3()6000n T n n n =-D. 42()2log 7000T n n n n =- 2. 判断循环队列Q （空间大小为m ）为满的条件是（ ） 。
A. Q->front==Q->rear B. Q->front!=Q->rear C. Q->front==(Q->rear+1)%m D. Q->front!=(Q->rear+1)%m 3. 串是一种特殊的线性表，其特殊性体现在 （ ） 。
A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符4. 一维数组A 的起始地址为1000，每个元素占6个存储单元，则A 的第23个元素（假设该元素存在）的起始地址为（ ）。
A. 1023B. 1132C. 1022D. 1138 5. 下面的选项（ ）不是图1的拓扑有序序列。
图 1A. 1,5,6,2,3,4B. 5,6,1,2,3,4C. 1,2,5,6,3,4D. 5,1,2,6,3,46. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。
A. 所有的结点均无左孩子B. 所有的结点均无右孩子C. 只有一个叶子结点D. 是任意一棵二叉树7、在对n 个元素进行直接插入排序的过程中，共需要进行（ ）趟。
A. n B. n+1 C. n-1 D. 2n8. 两个栈s1和s2及一个输入序列ABCD ，每个输入元素只能选择其中一个栈入栈，则不可能的输出序列为（ ）。
A ． ABCD ； B. BADC ； C ．CABD D ．DABC答 题 勿 超 装 订 线 ------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------9. 在一个具有n 个结点的有序单链表中插入一个新结点使得链表仍然有序，其算法的时间复杂度为( )。
A. 2(log )O nB. O (1)C. O(n)D. 2()O n 10. 在下面四个排序算法中，（ B ）是稳定的排序算法。
A. 堆排序B. 直接插入排序C. 快速排序D. 希尔排序三、判断题（对的打 ，错的打 ，每小题1分，共10分）1. 由先序遍历序列和后序遍历序列可以唯一确定一棵二叉树。
（ ）2. 折半查找只能在有序的顺序表上进行而不能在有序链表上进行。
（ ）3. 任何一个有向图都可以构造出它的一个拓扑有序序列。
（ ）4. 所有插入排序类的排序方法都是稳定的。
（ ）5. 顺序查找法适用于存储结构为顺序或链接存储的线性表。
（ ）6. 数据元素是数据的最小单位。
（ ）7. 哈夫曼树中不含度为1 的结点。
（ ）8. 对于一个顺序栈作进栈运算时，应先判别栈是否为满；作退栈运算时，应先判别栈是否为空。
（ ）9. 空串和空格串是相同的。
（ ） 10. 在做稀疏矩阵的快速转置运算时，需要预先求得每一列的非零元的个数，以及每一列的第一个非零元在转置后矩阵中的位置。
（ ）四、简答题（每小题分值见题后，共35分）1. 由一棵空二叉树T 开始创建二叉排序树，假设依次向T 中插入的元素序列为{12，68，34 ，23，90，8}。
按要求回答：（10分）（1）请画出全部元素插入完成后得到的二叉排序树T 。
（2）假设查找概率相同，求查找成功时的平均查找长度。
（3）对于如上的6个数据元素，最好情况下二叉排序树的高度是多少？最坏情况下二叉排序树的高度又是多少？2. 已知一无向带权图如图2所示，请以e 为出发点按普里姆算法求其最小生成树。
（7分）图 23. 有一组记录（76，38，62，53，80，74，83，65，85），请完成下面要求：（9分） （1）将其调整成大顶堆，并写出该大顶堆的状态序列。
（2）在第一问的大顶堆基础上进行堆排序，写出前四次交换并重新调整成堆后得到的状态序列。
答 题 勿 超 装 订 线 ------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------4. 将图3所示的树转换为二叉树。
（5分）图35. 图的邻接矩阵如图4所示，分别写出从A点出发进行深度优先遍历和广度优先遍历得到的序列。
（4分）五、算法阅读题（每小题4分，共8分）int A(LinkList &L) { /*L是无表头结点的单链表*/if ( L&&L->next){Q=L; L=L->next; P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;}return 1;}2. 已知二叉树如图5所示，写出下面算法执行后输出的结点序列。
六、算法设计题（每小题15分，共15分）1. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
/*------队列的循环链表存储结构----*/ typedef struct node { ElemType data; struct node *next; }Node,*Link; //结点类型typedef struct { Link rear; }Que; //队列类型/*-----队列初始化-----*/ Status Init(Que &q) { }/*-------入队列---------*/Status EnQue(Que &q,ElemType x) { }/*-------出队列------*/Status DeQue(Que &q, ElemType &e) { }Status what(BiTree T){InitStack(S); p=T;while( p || !StackEmpty(S) ){ if(p){Push(S,p); p=p->lchild;} else{Pop(S,p); printf(p->data); p=p->rchild; } }图5T答 题 勿 超 装 订 线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------。
