一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分）
GDOU-B-11-112广东海洋大学学生实验报告书（学生用表） 实验名称实验1数据库及其对象创建与管理课程名称数据库原理及应用课程号 16732201 学院(系) 信息学院专业信息管理与信息系统班级信管1111 学生姓名陈梓哲学号201111671106 实验地点海安A705 实验日期2013/10/16
实验一数据库及其对象的创建与管理 一、实验目的 1、掌握用SSMS或Transact-SQL语句创建、查看、修改、删除数据库的方法； 2、掌握数据库的备份和恢复方法； 3、掌握数据库的分离和附加方法； 4、掌握用SSMS或Transact-SQL语句创建、修改、删除表及向其添加数据的方法。 二、实验要求 1、实验前做好上机实验的准备，针对实验内容，认真复习与本次实验有关的知识，完 成实验内容的预习准备工作； 2、能认真独立完成实训内容； 3、实验后做好实验总结，根据实验情况完成总结报告。 三、实验内容 1、用SSMS在“对象资源管理器”中完成如下任务： （1） 参数参数值 数据库名Student 逻辑数据文件名Student_dat 操作系统数据文件名D:\ Student_dat.mdf 数据文件的初始大小10MB 数据文件的最大大小100MB 数据文件增长幅度10% 日志逻辑文件名Student_log 操作系统日志文件名D:\ Student_log.ldf 日志文件初始大小5MB 日志文件增长幅度10
（2）再修改学生课程数据库Student的主数据文件的大小，使其扩大两倍，然后查看扩大后的数据库属性。 2、用SSMS，在数据库Student中： （1）创建如下四个表，并设置相关的约束条件: 列名说明数据类型约束 Sno 学号整形主键 Sname 姓名字符（10）非空，唯一 Ssex 性别字符（2）取‘男’或‘女’ Sage 年龄短整形 Sdept 院系字符（20）可取空，默认‘计算机系’ 列名说明数据类型约束 Cno 课程号字符（4）主键 Cname 课程名字符（10）非空 Tno 教师号整形非空 列名说明数据类型约束 Sno 学号整形外键 Cno 课程号字符（4）外键 Grade 成绩整数取0～100 列名说明数据类型约束 Tno 教师号整形主键 Tname 教师名字符（10） S Course SC
数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（.C ）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i 管理信息系统模拟试卷 一、单项选择题（共20题，每小题1分，共20分） 1、管理信息系统概念的正确描述之一是( )。 A、由计算机、网络等组成的应用系统 B、由计算机、数据库等组成的信息处理系统 C、由计算机、人等组成的能进行管理信息加工处理的社会技术系统 D、由计算机、数学模型等组成的管理决策系统 2、绘制信息系统流程图的基础是（）。 A、数据关系图 B、数据流程图 C、数据结构图 D、功能结构图 3、系统分析报告的主要作用是（）。 A、系统规划的依据 B、系统实施的依据 C、系统设计的依据 D、系统评价的依据 4、按照数据的动态特性划分，具有随机变动属性的数据应放在（）中。 A、处理文件 B、主文件 C、周转文件 D、后备文件 5、决策支持系统支持（）。 A、结构化和半结构化决策 B、结构化和非结构化决策 C、半结构化非结构化决策 D、半结构化与风险型决策 6、用于管理信息系统规划的方法很多。把企业目标转化为信息系统战略的规划方法属 于（）。 A、U/C矩阵法 B、关键成功因素法CSF） C、战略目标集转化法 D、企业系统规划法（BSP） 7、在MIS的系统实施过程中程序设计的主要依据是（）。 A、数据流程图 B、系统流程图 C、程序设计说明书 D、决策表与决策树 8、数据流程图的组成不包括( )。 A、数据存储 B、外部实体 C、处理 D、输入 9、数据字典的内容不包括（）。 A、数据流 B、处理逻辑 C、数据管理机构 D、数据存储 10、管理信息按管理活动的层次，通常分为三级：( )。 A、计划级、控制级、操作级 B、高层决策级、中层决策级、基层作业级 C、战略级、战术级、作业级 D、战略级、战术级、策略级 11、应用软件系统开发的发展趋势是采用（）的方式。 A、自行开发 B、委托开发 C、购买软件包 D、合作开发 12、在系统流程图中符号“”表示( )。 A、人工操作 B、脱机操作 C、脱机存储 D、手工输入 数据结构试卷带答案 问题说明 部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我 （1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材 （2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题 （3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6 （4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外，注意课堂中讲的指针名和操作方法 （12）第4套填空题第6题答案错，设哈夫曼树中共有99个结点，则该树中有____50_____个叶子结点；若采用二叉链表作为存储结构，则该树中有__100___个空指针域。 （13）第5套选择第8题答案应为A:设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法，没法作 （15）第6套选择第5题应选B，实际是任意结点至多只有一个孩子：设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是(B) 高度等于其结点数 （16）第7套填空1题问题本身错，设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；___p->right_______=s；s->right->left=s；（设结点中的两个指针域分别为left和right）。（17）第8套填空题第8题答案错 （18）第7套选择第3题题目错，应以60为基准关键字，答案为C．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字60为基准而得到的一趟快速排序结果是（）。 (C) 42，40，55，60，80，85 （17）第6套填空9题．快速排序算法的空间复杂度平均情况下为_O(logn)_，最坏的情况下为_O(n)_。(18)第9套填空第3题，题目说循环队列有m个元素实际指循环队列总长为m，此外，该题关于队头和队尾指针的约定不同于教材 （19）第9套填空第4题答案错，9个元素冒泡排序，第一趟比较次数为8，最多8趟 广东海洋大学 2015 —— 2016 学年第二学期 《 数据结构与算法 》课程试题 课程号： 19232502 √ 考试 √ A 卷 √ 闭卷 □ 考查 □ B 卷 □ 开卷 一、 单项选择题（每小题2分，共20分） 1. 以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 2. 判断一个循环队列Q （最多n 个元素）为满的条件是（ ）。 A. Q->rear= =Q->front B. Q->rear= =Q->front+1 C. Q->front= =(Q->rear+1) % n D. Q->front= =(Q->rear-1)% n 3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ ）等5个特性. A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 4．线性表Ｌ在（ ）情况下适用于使用链式结构实现. A ．需经常修改Ｌ中的结点值 B. 需不断对Ｌ进行删除插入 C. Ｌ中含有大量的结点 D. Ｌ中结点结构复杂 5. 设指针变量p 指向单链表中结点A ，若删除单链表中结点A ，则需要修改指针的操作序列为（ ）. A. q=p->next ；p->data=q->data ；p->next=q->next ；delete q ； B. q=p->next ；q->data=p->data ；p->next=q->next ；delete q ； C. q=p->next ；p->next=q->next ；delete q ； D. q=p->next ；p->data=q->data ；delete q ； 班 级 ： 姓名： 学号： 试题共 6 页 加白纸 1 张 密 封 线 GDOU-B-11-302 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 广东海洋大学信息学院课程设计报告 设计题目公交换乘 课程名称数据结构 姓名（学号） 联系电话 专业名称 所在班级 指导教师 教师职称 起止时间 评定成绩 一、课程设计的主要内容 公交换乘在一个城市的公共交通系统设计中占据着极其重要的地位，公交换乘的过程将直接影响居民出行时间的长短，公交换乘的过程如下：指定一起始公交站点与目的公交站点，依据参考因素，例如：换乘路线的路径最短、耗费时间最短、所需车资最少等，经过分析处理得到可达目的站点换乘次数最少的乘车方案，具体可分为： （1）零次换乘起始站点和目的站点之间存在可直达的公交线路，即出行居民无需转乘就可以直接到达目的站点，这也是较为理想的方案。 （2）一次换乘起始站点和目的站点之间没有公交车直接往返，即两站点之间不存在可直达的公交线路，则出行居民需要在途经的某个站点下车，然后转乘另一线路公交车才能达到目的站点。 （3）多次换乘在起始站点和目的站点之间没有可直达的公交线路，出行居民需要经过一次以上的转乘才能达到目的站点，则得到多次换乘方案。多次换乘方案可通过一次换乘的递归计算得到，一般情况下，超过两次转乘的方案对于出行居民来说是难以接受的，本课程设计只要求计算零次和一次换乘方案，对于一次以上的公交换乘不作要求。 二、功能和结构设计 1、功能设计 在这里通过主函数显示程序的主页版，上面是湛江的公交线路图 在这里输入出发站点的名字，回车确定！ 在这里输入最终站点的名字！ 输入错误会提醒重新输入！ 输入要查询的起点和终点 0次换乘，输出查询结果： 按y或Y，可以继续查询！ 输入出发点和终点，一次换乘的结果如下： 2、结构设计 设计一个实现公交换乘的算法：指定任一起始站点和目的站点，依据算法得到所有可达目的站点的的公交线路，包括中间站点的换乘方法以及该公交线路所经过的公交站点。 1．分析公交站点和公交线路的数据属性，并依据公交换乘的功能要求，确定算法设计方案； 2．设计公交站点信息以及公交线路信息的存储结构； 3．设计公交换乘算法，并画出程序流程图； 4．使用C++程序设计语言编写实现公交换乘的程序； 三、流程图和算法设计 实验四数据的完整性、安全性 一、实验目的 1．掌握数据安全性和完整性的概念，以及如何保证数据库中数据安全及完整性。 2．掌握SQL Server中有关用户、角色及操作权限的管理方法． 3．学会创建和使用规则、缺省。 二、实验内容 1 数据库的安全性实验，通过SSMS设置SQL Server的安全认证模式．实现对SQL Server 的用户和角色管理，设置和管理数据操作权限． 2数据库的完整性实验。使用Transact-SQL设计规则、缺省、约束和触发器。 三、实验要求 1．数据的完整性实验 ⑴用SQL语句创建一学生成绩数据库(XSCJ)，包括学生(XSQK)、课程(KC)和成绩表(XS_KC)： 学生情况表（XSQK） 列名数据类型长度是否允许为空值 学号Char 6 N 姓名Char 8 N 性别Bit 1 N 出生日期smalldatetime 2 专业名Char 10 所在系Char 10 联系电话char 11 Y 课程表（KC） 列名数据类型长度是否允许为空值课程号Char 3 N 课程名Char 20 N 教师Char 10 开课学期Tinyint 1 学时Tinyint 1 学分Tinyint 1 N 成绩表（XS_KC） 列名数据类型长度是否允许为空值学号Char 6 N 课程号成绩Char Smallint 3 2 N ⑵数据的实体完整性实验 用SSMS分别将学生情况表（XSQK）的学号字段、课程表（KC）的课程号字段设置为主健 ②用T－SQL语句将成绩表（XS_KC）的学号、课程号字段设置为主健 ⑶数据的参照完整性实验 ①用SSMS为成绩表（XS_KC）创建外键FK_ XSQK_ID，外键FK_ XSQK_ID参照学生情况表（XSQK）表的学号 ②用T－SQL语句成绩表（XS_KC）创建外键FK_ KC_ID，外键FK_ KC _ID参照课程表（KC）表的课程号 ⑷数据的用户定义完整性实验 用T－SQL语句为学生情况表（XSQK）的姓名列创建一个唯一约束 ②用SSMS为学生情况表（XSQK）的性别列创建一个检查约束，使得性别的值为男或女 《数据结构》试卷B 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈 只能在插入和删除元素；对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除 运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间 的和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中，队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查 找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。 （）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）5.线性表的逻辑顺序与存储顺序总是一致的 （）6. 栈和队列是一种非线性数据结构。 （）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 广东海洋大学2008——2009学年第一学期 《数据结构》课程试题 一、填空题（10?2’=20分） 1、数据元素是（ ）的基本单位，在程序中通常作为一个（ ）进行处理。 2、数据结构是指相互间存在一定关系的（ ）的集合。 3、插入一个元素，线性表的长度（ ）1。 4、栈的操作特点是（ ）。 5、已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF 和DGEBHFCA ，则该二叉树的前序序列是（ ）。 6、对于含有n 个顶点和e 条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（ ）。 7、对于包含５０个关键码的３阶B-树，其最小高度为（ ），最大高度为（ ）。 8、在插入和选择排序中，若初始数据基本正序，则选择（ ），若初始数据基本反序，则最好选择（ ）。 9、.在有n 个结点的无向图中，其边数最多为（ ）。 10、在串S="structure"中，以t 为首字符的子串有（ ）个。 二、选择题（10?2’=20分） 1、算法分析的两个主要方面是（ ）。 A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 2、.顺序表是线性表的 （ ） A.链式存储结构 B.顺序存储结构 C. 索引存储结构 D. 散列存储结构 3、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。 A ．插入 B ．删除 C ．排序 D ．定位 4、在一个单链表HL 中，若要在指针q 所指结点的后面插入一个由指针p 所指向的结点，则执行（ ）。 A. q->next=p->next; p->next=q; B. p->next=q->next; q=p; C. q->next=p->next; p->next=q; D. p->next=q->next; q->next=p; 5、设循环队列中数组的下标范围是1～n ，其头尾指针分别为f 和r ，则其元素班 级 ： 姓名： 学号： 试题共 页 加 白纸 张 密 封 线 GDOU-B-11-302 1、若学生选课库的关系模式为： 学生（学号，姓名，性别，年龄，所在系）； 课程（课程号，课程名，先行课）； 选课（学号，课程号，成绩）. ①求选修了课程号为“C2”课程的学生学号。 π学号（σ课程号= ‘C2’（选课）） ②求选修了课程号为“C2”课的学生学号和姓名。 π学号，姓名（σ课程号= ‘C2’（学生选课）） ③求没有选修课程号为“C2”课程的学生学号。 π学号（学生）-π学号（σ课程号= ‘C2’（选课）） ④求既选修“C2”课程，又选修“C3”课程的学生学号。 π学号(σ课程号= ‘C2’ (选课)) ∩ π学号(σ课程号= ‘C3‘ (选课) ) ⑤求选修课程号为“C2”或“C3”课程的学生学号。 π学号(σ课程号=‘C2‘ (选课))∪π学号(σ课程号=’C3‘ (选课)) ⑥求选修了全部课程的学生学号。 π学号，课程号(选课)÷ π课程号(课程) ⑦一个学号为“98002”的学生所学过的所有课程可能也被其他学生选修，求这些学生的学号和姓名。 π学号,姓名((π学号，课程号(选课)÷π课程号(σ学号= ‘98002’(选课) ) 学生) 2．设有一个SPJ数据库，包括S，P，J，SPJ四个关系模式： 1）求供应工程J1零件的供应商号码SNO： πSno(σJno=‘J1’（SPJ）) 2）求供应工程J1零件P1的供应商号码SNO： πSno(σJno=‘J1’∧Pno=‘P1‘(SPJ)) 3）求供应工程J1零件为红色的供应商号码SNO： πSno(σJno=‘J1‘（σCOLOR=’红‘（P） SPJ）) 4）求没有使用天津供应商生产的红色零件的工程号JNO： πJno(SPJ)-πJNO（σcity=‘天津’∧Color=‘红‘（S SPJ P） 5）求至少用了供应商S1所供应的全部零件的工程号JNO： πJno，Pno(SPJ)÷ πPno（σSno=‘S1‘（SPJ）） 3.查询至少选修了一门其直接先行课为5号课程的课程的学生姓名。πSname(σCpno='5'(Course SC Student)) 数据结构试题（含答案） 1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称非线性结构 2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有 1 个后续结点。 4．线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没． 6．数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点，其余每个结点的后续结点可以任意多个。 7．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8．评估一个算法的优劣，通常从时间复杂度和空间复杂度两个方面考察。 9．算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 11．在单链表中，要删除某一指定的结点，必须找到该结点的前驱结点。 12．在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。13．在顺序表中插入或删除一个数据元素，需要平均移动 n 个数据元素，移动数据元素的个数与位置有关 14．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用顺序存储结构 15．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。 16．顺序存储结构是通过下标表示元素之间的关系的；链式存储结构是通过指针表示元素之间的关系的 17．带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18．栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循后进先出的原则。19．空串是零个字符的串，其长度等于零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。 20．组成串的数据元素只能是单个字符。 21．一个子串”str”在主串”datastructure”中的位置是 5 。 22．字符串中任意个连续字符构成的部分称为该串的子串。 23．二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要 540个字节；M的第8列和第5行共占108个字节24．稀疏矩阵一般的压缩存储方法有两种，即三元组表和十字链表。 25．广义表（（a），（（b），c），（（（d））））的长度是 3 ，深度是 4 。 26．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有n0＝ n2+1 。 27．在有n个结点的二叉链表中，空链域的个数为__n+1__。 28．一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29．深度为5的二叉树至多有 31 个结点。 30．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为69 。 一、判断题： 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算：插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。（） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（） 9、栈和队列逻辑上都是线性表。（） 10、单链表从任何一个结点出发，都能访问到所有结点（） 11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（） 12、快速排序是排序算法中最快的一种。（） 13、多维数组是向量的推广。（） 14、一般树和二叉树的结点数目都可以为0。（） 15、直接选择排序是一种不稳定的排序方法。（） 16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（） 17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（） 18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（） 19、堆栈在数据中的存储原则是先进先出。（） 20、队列在数据中的存储原则是后进先出。（） 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（） 22、哈夫曼树一定是满二叉树。（） 23、程序是用计算机语言表述的算法。（） 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（） 25、用一组地址连续的存储单元存放的元素一定构成线性表。（） 26、堆栈、队列和数组的逻辑结构都是线性表结构。（） 27、给定一组权值，可以唯一构造出一棵哈夫曼树。（） 28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（） 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,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为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。 关于公布2005年度广东省高校精品课程的通知 粤教高[2005]193号 各有关高等学校： 根据《教育部关于启动高等学校教学质量与教学改革工程精品课程建设工作的通知》（教高[2003]1号）和我厅《关于开展2005年度广东省高校精品课程评选工作的通知》（粤教高［2005］77号）等文件要求，我厅组织评选了2005年度广东省高校精品课程，共70门。经公示无异议，现予以公布。 各高校要充分利用国家级和省级高校精品课程资源，进一步发挥优秀教学资源的示范和辐射作用，带动课程建设上水平、上台阶。同时，要进一步做好下一阶段精品课程的规划与建设工作，不断改进和提高课程建设工作质量。 学校对入选国家级和省级的精品课程，要给予扶持并提供必要的帮助。已获国家或省高校精品课程项目的学校，要提供条件保证国家和省高校精品课程上网运行并免费开放。同时，要按教育部规定要求不断完善和更新其内容，提高精品课程质量。未经著作权人许可任何人不得将国家和省高校精品课程内容用作以营利为目的的活动。 我厅将按照《教育部办公厅关于<国家精品课程建设工作实施办法>补充规定的通知》(教高厅[2004]13号)精神和参照《国家精品课程建设工作实施办法》的要求，对广东省高校精品课程网上运行情况实行监督并进行滚动建设。 有关我省高校精品课程的资助将按照《广东省高等院校学科与专业建设专项资金管理暂行办法》（粤财教[2004]145号）要求执行。 附件：2005年度广东省高校精品课程名单 广东省教育厅 二○○五年十二月二十日附件：2005年度广东省高校精品课程名单（排名不分先后） 中山大学：行政管理学、基础会计学、信息资源共享、理论物理导论、地理信息系统、综合化学实验、中国近代史、药理学、医学统计学； 华南理工大学：制浆造纸原理与工程、机械制造技术基础、计算机应用基础、建筑历史、工业微生物学； 暨南大学：基础会计学、统计学原理、生理学、外国文学史、新闻事业经营管理、流行病学； 华南农业大学：植物营养学、兽医药理学、农科数学； 南方医科大学：生物化学、病理学、儿科学、流行病学、护理学基础、内科学； 广州中医药大学：中医妇科学、伤寒论； 华南师范大学：金融学、植物生理学、高等代数、健美操、课程与教学论； 广东工业大学：工程测量、电力电子技术； 广东外语外贸大学：当代英国概况，英语语音(English Pronunciation for Communication)； 汕头大学：临床基本技能； 广东商学院：市场营销学、初级财务会计学； 广东海洋大学：食品微生物学； 广东药学院：药剂学； 广州体育学院：运动生物化学； 湛江师范学院：文学写作； 广东警官学院：经济犯罪案件侦查； 广州民航职业技术学院：低频电子线路、飞机系统与附件； 广东轻工职业技术学院：平面广告设计； 数据结构试题及答案 一、选择题（每小题2分，共20分），每个题的备选答案中，只有一个是正确的，请将答案填写在试题的括号中。 1、对顺序存储的线性表，设其长度为20，在任何位置上插入或删除操作都是 等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 A．10 B．9 C．11 D．12 2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 3、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（ B ）语句修改top指针。 A．top++ B．top-- C．top = 0 D．top 4、设入栈顺序为A，B，C，D，E，则出栈序列不可能是（ C ）。A．EDCBA B．ABCDE C．ADEBC D．ABDEC 5、已知关键字序列（46, 79, 56, 38, 40, 84），采用快速排序（以位于最左位 置的关键字为基准）得到的第一次划分结果为：（ A ） A．{ 40, 38, 46, 56, 79, 84 } B．{ 38, 46, 79, 56, 40, 84 } C．{ 38, 46, 56, 79, 40, 84 } D．{ 40, 38, 46, 79, 56, 84 } 6、一个有n个顶点和n条边的无向图一定是（ C ）。 A．不连通的 B．连通的 C．有环的 D．无环的 7、在一棵具有n个结点的二叉树的第i层上，最多具有（ B ）个结点。 A．2i B．2i-1 C．2i+1 D．2n 8、对线性表采用折半查找法，该线性表必须（ B ）。 A．采用顺序存储结构B．采用顺序存储结构，且元素按值有序 C．采用链式存储结构 D．采用链式存储结构，且元素按值有序 9、在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ C ）。A．?(n-1)/2? B．?n/2? C．?n/2? D．?n/2? -1 10、在一个无向图中，所有顶点的度数之和等于所有边数的 ( D ) 倍。 A．3 B．1/2 C．1 D．2 二、填空题（每小题2分，共20分），请将正确的结果，填写在试题的横线上。 1、带头结点的循环链表L为空的条件是。 2、序列A={12, 70, 33, 65, 24, 56}给出对应于序列A的大顶堆HA（以线性数 组表示）。 3、每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________ 排序。 4、设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front = = Q.rear，则队列的长度 为。 5、已知数组A[0..11][0..8]按行优先存储，每个元素占有5个存储单元，且 A[0][0]的地址为1000（十进制），则A[6][7]的地址为________________。 6、已知广义表A=(a，()，(b，(c)))，则其深度为。 7、在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6 个，则叶子结点数为__ ____个。广东海洋大学管理信息系统模拟试卷(一)
数据结构试卷带答案
数据结构试卷2016A
数据结构试题及答案
数据结构试题(含答案)
广东海洋大学数据结构课程设计——公交换乘系统(C++)
广东海洋大学数据库实验报告
数据结构试卷B卷(含答案)
数据结构试题3
广东海洋大学数据库第二章作业
数据结构试题(含答案)
数据结构试题及答案
数据结构试卷及答案压缩版
关于公布2005年度广东省高校精品课程的通知
数据结构试题及答案.docx
相关主题
文本预览