模拟试题一
一、判断题（下列各题，你认为正确的，请在前面的括号内打√，错误的打×。每题1分，共10分）
（√）1．数据的存储结构是数据的逻辑结构的存储映像。
（√）2．用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。
（×）3．非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后继。
（√）4．树的最大特点是一对多的层次结构。
（√）5．队列的特点是先进先出。
（×）6．图的最小生成树是惟一的。
（）7．线性表是广义表的特殊形式。
（√）8．由后序遍历序列和中序遍历序列能惟一确定一棵二叉树。
（×）9．散列表是一种链式存储结构。
（×）10．快速排序并非在任何情况下都比其他排序方法速度快。
二、填空题（每空2分，共20分）
1．数据的存储结构的4种形式为链接存储顺序存储、散列存储和索引存储。
2．所有插入和删除都在表的一端进行的线性表称为队
列。
3．有n个结点的完全二叉树（空二叉树的深度为0），其深度h= 「log2n」+1 。
4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F
和R，入队时，队尾指针的变化可以表示为R= （R+1）%M 。
5．散列法既是一种查找方法，又是一种存储方法。
6．n个顶点的有向完全图具有 n*（n-1）条弧。
7．n个元素的顺序查找（检索）的平均查找长度为(n+1)/2 。
三、单选题（本题的每一备选答案中，只有一个是正确的，请把
你认为正确的答案填入括号内，多选不给分，每小题3分，共15分）1．若进栈序列为1，2，3，4，则不可能得到的出栈序列是（ C ）。
A）3，2，1，4 B）3，2，4，1
C）4，2，3，1 D）2，3，4，1
2．对于图1所示的二叉树，其后序序列为（C ）。
A）ABDECFG B）DBEAFCG
C）DEBFGCA D）GFCEBDA
3．对于图2所示的AOV网，不能出现的拓扑序列为（ A ）。
A）1 2 3 4 5 B）1 2 4 3 5
C）2 4 1 3 5 D）2 1 4 3 5
图1 图2
4．深度为k的完全二叉树所含叶结点的个数最多为（ B）。
A）2k B） 2k-1C）k D） 2k
5．衡量查找算法效率的主要标准是（ C ）。
A）元素个数B）所需的存储量
C）平均查找长度D）算法难易程度
四、应用题（25分）
1．给定B树如图3所示，画出将14插入到B树后的情形。（3分）
图3
2．对图4进行如下操作：
（1）写出其邻接矩阵。（2分）
（2）按Kruskal算法求其最小生成树，并写出相应的边集数组
图4
|0 12 ∞ 5 ∞∞|
|12 0 8 ∞10 ∞|
|∞8 0 ∞∞3|
|5 ∞∞0 6 ∞|
|∞10 ∞ 6 0 11|
|∞∞ 3 ∞11 0|
3．请画出后序序列和中序序列相同的二叉树的所有形态。（3分）1：只有左子树
2：一个结点
3:空树
4．散列函数为H(k)=k%7，散列表的地址为0～6，用线性探查法解决冲突，建立散列表ht。给定关键字序列为{32,13,49,55,22,38,21}。
要求：（1）构造散列表（只画出表，不写算法）。（5分）
位置： 0 1 2 3 4 5 6
关键字： 49 55 22 38 32 21 13
比较次数：1 3 2 1 1 6 1
（2）求出平均查找长度。（2分）
WPL=(1+3+2+1+1+6+1)/7=15/7
5．用直接选择排序法对下列关键字进行排序，请写出每一趟排序的结果。（6分）
68 45 20 90 15 10 50
第一趟：10 45 20 90 15 68 50
第二趟：10 15 20 90 45 68 50
第三趟：10 15 20 90 45 68 50
第四趟：10 15 20 45 90 68 50
第五趟：10 15 20 45 50 68 90
第六趟：10 15 20 45 50 68 90
五、算法设计（在下列算法的横线上填上适当的表达式、语句或运算符。每空3分，共30分）
1．在带头结点的head单链表的结点a之后插入新元素x。
class node
{ public:
elemtype data;
node *next;
};
void lkinsert (node *head, elemtype x)
{ node *s, *p;
s=_new node；________
s->data=__x；_______;
p=head->next;
while (p!=NULL) &&( p->data!=a )
__p=p-〉next_______;
if (p==NULL)
cout<<"不存在结点a";
else {___s->next=p->next______;
___p->next=s______;
}
}
2．快速排序
void qksort (int R[ ], int p, int q) //按递<对R[p]～R[q] 进行
快速排序
{ int i=p, j=q;
R[ 0 ]=R [i ]; //R[0]作临时单元
while (__i { while (j>i )&&( R[ j ] _=>___R[ 0 ]) j--; if (j>i) { R[ i ]=R[ j ]; i++;} while (i if (i }; R[ i ]= ___R[0]______; i++; j--; if (j>p) qksort(R,p,j); if (i } 模拟试题三 一、判断题（下列各题，你认为正确的，请在前面的括号内打√，错误的打×。每题1分，共10分） （）1．数据是计算机加工处理的对象。 （）2．数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。 （）3．线性表是由n≥0个相同类型元素组成的有限序列。 （）4．栈是一种后进先出的线性表。 （）5．从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点。 （）6．单链表设置头结点的目的是为了简化运算。 （）7．深度为h（空二叉树的深度为0）的二叉树，最多有2h-1个结点。 （）8．图G由两个集合V(G)和E(G)所组成，其中顶点集V(G)可以为空集，而边集E(G)不能为空。 （）9．散列法是一种对关键字进行运算的查找方法和存储方法。 （）10．快速排序在任何情况下都是速度最快的一种排序方法。 二、填空题（每空2分，共20分） 1．数据元素之间存在的相互关系称为。 2．数据结构从逻辑上分为结构和结构。 3．线性表的顺序存储结构称为。 4．所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为。 5．深度为h（空二叉树的深度为0）的二叉树，最少有个结点。 6．折半查找要求待查表为表。 7．n个记录按其关键字大小递增或递减的次序排列起来的过程称为。 8．用链表存储数据时，不仅要存储数据元素的，还要存储元素之间的相互。 三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案填入括号内，多选不给分，每小题3分，共15分）1．与线性表的链接存储相符的特性是（）。 A）插入和删除操作灵活B）需要连续存储空间 C）便于随机访问D）存储密度大 2．若进队序列为1，2，3，4，则出队序列是（）。 A）4，3，2，1 B）1，2，3，4 C）1，3，2，4 D）3，2，4，1 3．已知广义表A=((a,b),(c,d))，则head(A)等于（）。 A）（a,b）B）((a,b)) C）a,b D）a 4．n个结点的二叉树，若用二叉链表作为存储结构，则非空闲的左、右孩子链域为（）。 A）n B）2n C）n-1 D）n+1 5．6个顶点的连通图的深度优先生成树，其边数为（）。 A）6 B）5 C）7 D）4 四、应用题（共25分） 1．给定B树如下，画出将19插入到B树后的情形。（4分） 2．对于给定的5个实数W={8,5,13,2,6}，试构造Huffman树，并求出该树的最小带权路径长度。（7分） 3．对于下面所给的图，进行如下操作： （1）画出其邻接表。（4分） （2）写出从V1出发的深度优先搜索序列。（3分） 4．给定有序表D={15,17,18,22,35,51,60,88,93}，用折半查找法在D中查找18。现要求： （1）试用图示法表示查找过程。（4分） （2）求出其成功的平均查找长度ASL。（3分） 五、算法设计（在下列算法的横线上填上适当的语句或表达式。每空3分，共30分） 1．直接选择排序 void selectsort (int R[ ] , int n ) // 按递增序对R[ 0 ]～R[n-1] 进行直接选择排序 { int i, j, k, temp ; for (i=0; i<= ; i++) { k=i ; for (j= ; j<=n-1; j++) if (R[ j ] R[ k ] ) k=j; if ( ) { temp=R[ i ]; R[ i ] = ; R[ k ]=temp; } } } 2．中序遍历二叉树。设二叉树用二叉链表表示，以t为根指针，二叉链表结点的类型为node；栈s的元素类型为指向node的指针类型，栈容量m足够大。中序遍历的非递归算法如下： struct node {char data; node *lc,*rc; }; void preorder (node *t) { node *s[m] ，*p=t ; int top =- 1; //置栈空 do { while (p!=NULL) { s[++top] = ; ; } if (top!= -1) ｛p=s[top- -]; ; ; } } while (( ) || ( p ! =NULL )); } 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 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. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 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 数据结构期末考试题及标准答案 ————————————————————————————————作者：————————————————————————————————日期： 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）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 管理信息系统模拟试卷 一、单项选择题（共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、手工输入 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.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（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 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 广东海洋大学 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.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7. 广东海洋大学信息学院课程设计报告 设计题目公交换乘 课程名称数据结构 姓名（学号） 联系电话 专业名称 所在班级 指导教师 教师职称 起止时间 评定成绩 一、课程设计的主要内容 公交换乘在一个城市的公共交通系统设计中占据着极其重要的地位，公交换乘的过程将直接影响居民出行时间的长短，公交换乘的过程如下：指定一起始公交站点与目的公交站点，依据参考因素，例如：换乘路线的路径最短、耗费时间最短、所需车资最少等，经过分析处理得到可达目的站点换乘次数最少的乘车方案，具体可分为： （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）的性别列创建一个检查约束，使得性别的值为男或女 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。 for(i=n-1；i>=0；i--) for(j=0；j 广东海洋大学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)) 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 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. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 数据结构复习题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序； 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2．已知一个带权图的顶点集V和边集G分别为： V＝{0，1，2，3，4，5}； 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j “数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 关于公布2005年度广东省高校精品课程的通知 粤教高[2005]193号 各有关高等学校： 根据《教育部关于启动高等学校教学质量与教学改革工程精品课程建设工作的通知》（教高[2003]1号）和我厅《关于开展2005年度广东省高校精品课程评选工作的通知》（粤教高［2005］77号）等文件要求，我厅组织评选了2005年度广东省高校精品课程，共70门。经公示无异议，现予以公布。 各高校要充分利用国家级和省级高校精品课程资源，进一步发挥优秀教学资源的示范和辐射作用，带动课程建设上水平、上台阶。同时，要进一步做好下一阶段精品课程的规划与建设工作，不断改进和提高课程建设工作质量。 学校对入选国家级和省级的精品课程，要给予扶持并提供必要的帮助。已获国家或省高校精品课程项目的学校，要提供条件保证国家和省高校精品课程上网运行并免费开放。同时，要按教育部规定要求不断完善和更新其内容，提高精品课程质量。未经著作权人许可任何人不得将国家和省高校精品课程内容用作以营利为目的的活动。 我厅将按照《教育部办公厅关于<国家精品课程建设工作实施办法>补充规定的通知》(教高厅[2004]13号)精神和参照《国家精品课程建设工作实施办法》的要求，对广东省高校精品课程网上运行情况实行监督并进行滚动建设。 有关我省高校精品课程的资助将按照《广东省高等院校学科与专业建设专项资金管理暂行办法》（粤财教[2004]145号）要求执行。 附件：2005年度广东省高校精品课程名单 广东省教育厅 二○○五年十二月二十日附件：2005年度广东省高校精品课程名单（排名不分先后） 中山大学：行政管理学、基础会计学、信息资源共享、理论物理导论、地理信息系统、综合化学实验、中国近代史、药理学、医学统计学； 华南理工大学：制浆造纸原理与工程、机械制造技术基础、计算机应用基础、建筑历史、工业微生物学； 暨南大学：基础会计学、统计学原理、生理学、外国文学史、新闻事业经营管理、流行病学； 华南农业大学：植物营养学、兽医药理学、农科数学； 南方医科大学：生物化学、病理学、儿科学、流行病学、护理学基础、内科学； 广州中医药大学：中医妇科学、伤寒论； 华南师范大学：金融学、植物生理学、高等代数、健美操、课程与教学论； 广东工业大学：工程测量、电力电子技术； 广东外语外贸大学：当代英国概况，英语语音(English Pronunciation for Communication)； 汕头大学：临床基本技能； 广东商学院：市场营销学、初级财务会计学； 广东海洋大学：食品微生物学； 广东药学院：药剂学； 广州体育学院：运动生物化学； 湛江师范学院：文学写作； 广东警官学院：经济犯罪案件侦查； 广州民航职业技术学院：低频电子线路、飞机系统与附件； 广东轻工职业技术学院：平面广告设计；2017年数据结构期末考试题及答案A
广东海洋大学数据库实验一报告
数据结构期末考试题及标准答案
广东海洋大学管理信息系统模拟试卷(一)
《数据结构》期末考试题及答案
数据结构试卷2016A
数据结构复习资料,java数据结构期末考试
2017数据结构期末考试试题及答案
广东海洋大学数据结构课程设计——公交换乘系统(C++)
广东海洋大学数据库实验报告
数据结构期末考试试题及答案
数据结构试题3
广东海洋大学数据库第二章作业
《数据结构》期末考试试卷
大学数据结构期末考试试题(有答案)
数据结构期末考试试题及答案
大学数据结构期末考试题(有答案)
关于公布2005年度广东省高校精品课程的通知
相关主题
文本预览