北大“数据结构”上机考试复习题总结
数据结构练习题1
1.编一C程序，它能根据读入的数据构造有向图G，并输出G的邻接矩阵和DFS 遍历序列（从V0开始），图的输入形式为n Vi0 Vj0 Vi1 Vj1 Vi2 Vj2……Vim Vjm -1 -1（-1，-1为输入结束标记），它们都是整数，且100>n>0，其余的值都>=0且 （注：程序的可执行文件名必须是e1.exe，存于你的账号或其debug目录下。） 2. 编一C程序，它能读入两组整数（每组整数都以-9999为结束标记，个数都不大于1000），并以从小到大的次序输出既在第一组整数中而且不在第二组整数中的所有整数（同一个整数不能输出两次）。（输入时，两个相邻的整数用空格隔开）。 （注：程序的可执行文件名必须是e2.exe，存于你的账号或其debug目录下。） 数据结构练习题2 1.编一C程序，它能读入两组整数（每组整数都是66个整数），它们分别是下三角矩阵A和下三角矩阵B的按行优先排列的元素（A和B的其它元素均为零）。计算并输出矩阵A与B的乘积。 （注：程序的可执行文件名必须是e1.exe，存于你的账号或其debug目录下。）#include #include void main（） { int i，j，k1，k2，c[66]，s，k，count=0，flag=0； int a[66]； int b[66]； printf（“请输入66个数到a中：\n”）； for（i=0；i<66；i++） scanf（“%d”，&a[i]）； printf（“请输入66个数到b中：\n”）；for（i=0；i<66；i++） scanf（“%d”，&b[i]）； for（i=0；i<11；i++）{ for（k=0；k<11；k++） {s=0； for（j=0；j<11&&i>=j；j++） k1=i*（i+1）/2+j； if（j>=k） k2=j*（j+1）/2+i； else continue； s+=a[k1]*b[k2]； flag=1； } if（flag） { c[count++]=s； flag=0； } } for（i=0；i<66；i++） printf（“%d”，c[i]）； } 2.编一C程序，它能对输入的一串整数（不多于1000个，以-9999为结束标记）到数组a中，再对a的元素进行直接插入排序（从小到大排序），输出排序结果和所用关键字比较次数。（输入时，两个相邻的整数用空格隔开）。 （注：程序的可执行文件名必须是e2.exe，存于你的账号或其debug目录下。） #include #include void main（） { int i，j，k1，k2，c[66]，s，k，count=0，flag=0； int a[66]； int b[66]； printf（“请输入66个数到a中：\n”）； for（i=0；i<66；i++） scanf（“%d”，&a[i]）； printf（“请输入66个数到b中：\n”）； for（i=0；i<66；i++） scanf（“%d”，&b[i]）； for（i=0；i<11；i++）{ for（k=0；k<11；k++） {s=0； for（j=0；j<11&&i>=j；j++）k1=i*（i+1）/2+j； if（j>=k） k2=j*（j+1）/2+i； else continue； s+=a[k1]*b[k2]； flag=1； } if（flag） { c[count++]=s； flag=0； } } for（i=0；i<66；i++） printf（“%d”，c[i]）； } 数据结构练习题3 1. 编一C程序，它能根据输入的二叉树前序和中序序列来构造该二叉树，并能输出该二叉树的后序序列和该二叉树叶的结点的个数以及该二叉树高度。（输入次序是：表示前序序列的字符串、表示中序序列的字符串）。 （注：程序的可执行文件名必须是e1.exe，存于你的账号或其debug目录下。） #include #include #include void exit（int）； #define MAX 100 typedef struct node{ char d； struct node *lchild，*rchild； }Tnode； void MKTree（char pre[]，int pres，int pree，char in[]，int is，int ie，Tnode **r） { int i； if（pres>pree||is>ie） *r=NULL； else{ *r=malloc（sizeof（Tnode））； for（i=is；i<=ie；i++） if（pre[pres]==in[i]） { MKTree（pre，pres+1，pres+i-is，in，is，is+i-1，&（*r）->lchild）；MKTree（pre，pres+i+is+1，pree，in，is+i+1，ie，&（*r）->rchild）；break； } } } void postorder（Tnode *r） { if（r） { postorder（r->lchild）； postorder（r->rchild）； printf（“%c”，r->d）； } } int num（Tnode *r） { if（r==NULL） return 0； else if（r->lchild==NULL&&r->rchild==NULL）return 1； else return num（r->lchild）+num（r->rchild）；} int height（Tnode *r） { int h1，h2； if（r==NULL） return 0； else { h1=height（r->lchild）； h2=height（r->rchild）； return 1+（h1>h2）？h1：h2； } } void main（） { Tnode *r； char pre[MAX]，in[MAX]； printf（“input preorder and inorder \n”）； gets（pre）； gets（in）； MKTree（pre，0，strlen（pre）-1，in，0，strlen（in）-1，&r）； printf（“The postorder is as follow：\n”）； postorder（r）； printf（“\n there are %d leaves in the tree\n”，num（r））； printf（“h=%d\n”，height（r））； } 2.编一C程序，它能读入一串（n个）整数（以-9999为结束标记），并判断第1个整数在后（n-1）个整数中出现的次数，再输出该次数。（输入时，两个相邻的整数用空格隔开）。 （注：程序的可执行文件名必须是e2.exe，存于你的账号或其debug目录下。）数据结构练习题4 1. 编一C程序，它能根据输入的二叉树中序和后序序列来构造该二叉树，并能输出该二叉树的前序序列和该二叉树的度为2的结点的个数并能判断该二叉树是否为二叉排序树（若是输出Yes；否则输出No）。（输入次序是：表示中序序列的字母串、表示后序序列的字母串）。 （注：程序的可执行文件名必须是e1.exe，存于你的账号或其debug目录下。） #include #include #include void exit（int）； #define MAX 100 typedef struct node{ char d； struct node *lchild，*rchild； }Tnode； void MKTree（char in[]，int is，int ie，char post[]，int posts，int poste，Tnode **r）{ int i； if（is *r=NULL； else{ *r=malloc（sizeof（Tnode））； （*r）->d=post[poste]； for（i=is；i<=ie；i++） if（post[poste]==in[i]） { MKTree（in，is，i-1，post，posts，posts+i-is-1，&（*r）->lchild）； MKTree（in，i+1，ie，post，posts+i-is，poste-1，&（*r）->rchild）； break； } if（i>ie）{ printf（“Error：input contain an error ！\n”）；exit（9）； } } } void BST（char in[]，int is，int ie） { int i； if（is==ie） printf（“yes\n”）； else { for（i=is；i<=ie；i++） { if（in[i] continue； else break； } if（i==ie） printf（“YES\n”）； else printf（“NO\n”）； } } void preorder（Tnode *r） { if（r） { printf（“%c”，r->d）； preorder（r->lchild）； preorder（r->rchild）； } } int seconde（Tnode *r） { if（r==NULL） return 0； else if（（r->lchild）！=NULL&&（r->rchild）！=NULL）return 1； else return seconde（r->lchild）+seconde（r->rchild）； } void main（） { Tnode *r； char post[MAX]，in[MAX]； printf（“input inorder and postorder ！\n”）； gets（in）； gets（post）； MKTree（in，0，strlen（in）-1，post，0，strlen（post）-1，&r）； printf（“the preorder is as follo ws：\n”）； preorder（r）； printf（“\n there are %d seconde in the tree \n”，seconde（r））； printf（“if the tree is BST：\n”）； BST（in，0，strlen（in）-1）； } 2.编一C程序，它能读入一串整数（以-9999为结束标记），再以与输入次序相反的次序输出这串整数（输入、出时，两个相邻的整数用空格隔开）。 （注：程序的可执行文件名必须是e2.exe，存于你的账号或其debug目录下。） #include #define max 10000 main（） { int a[max]； int n=0，i，d； printf（“please enten tne number：\n”）； do{ scanf（“%d”，&d）； if（d==-9999） break； n++； a[n]=d； }while（9）； for（i=n；i>0；i——） printf（“%4d”，a[i]）； printf（“\n”）； } 数据结构练习题5 1. 编一C程序，它能读入一个大写英文字母串（字母个数不多于100，字母两两不同），并构造以这些字母为关键字的二叉排序树，再输出该二叉排序树的后序序列和页结点个数。 （注：程序的可执行文件名必须是e1.exe，存于你的账号或其debug目录下，否则无成绩） 2. 编一C程序，它能读入两组整数（每组整数都以-9999为结束标记，-9999不算在内。个数都不大于1000），并以从小到大的次序输出既在第一组整数中也在第二组整数中的所有整数（同一个整数不能输出两次）。（输入时，两个相邻的整数用空格隔开）。 （注：程序的可执行文件名必须是e2.exe，存于你的账号或其debug目录下，否则无成绩） #include void paixu（int r[]，int n） { int i，j，k； int exchange； for（i=0；i<=n；i++） { exchange=0； for（j=n-1；j>=i；j——） if（r[j+1] { k=r[j+1]； r[j+1]=r[j]； r[j]=k； exchange=1； } if（！exchange） break； } } int jiaoji（int m[]，int n[]，int l[]，int countaa，int countbb）{ int w，x，y； int i=0，j=0，k=0； for（w=0；w<=countaa；w++） { for（x=w+1；x<=countaa；x++） { if（m[w]==m[x]） { countaa——； for（y=x；y<=countaa；y++） { m[y]=m[y+1]； } x——； } } } while（i<=countaa） { for（j=0；j<=countbb；j++） { if（m[i]==n[i]） { l[k]=m[i]； k++； break； } } i++； } return k； } void main（） { int a[1000]，b[1000]，c[2000]； int excange=0，i，countA，countB，countC；printf（“请输入数组a：\n”）； for（i=0；i<=1000；i++） { scanf（“%d”，&a[i]）； if（a[i]==-9999） break； } countA=i-1； paixu（a，countA）； printf（“请输入数组b：\n”）； for（i=0；i<=1000；i++） { scanf（“%d”，&b[i]）； if（b[i]==-9999） break； } countB=i-1； paixu（b，countB）； countC=jiaoji（a，b，c，countA，countB）；printf（“\n\n”）； for（i=0；i<=countC-1；i++） printf（“%d”，c[i]）； printf（“\n”）； 填空题 1.文件可按其记录的类型不同而分成两类，即( 操作系统文件 )和( 数据库 )文件。 2.数据库文件按记录中关键字的多少可分成( 单关键字文件 )和( 多关键字文件 )两种文件。 3.文件由( 记录 )组成，记录由( 数据项 )组成。 4.从用户观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE中数据库文件那样的文件组织结构，称为( 数据库 )文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为( 文本 )文件。 从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即( 顺序组织 )、 ( 随机组织 )、( 链组织 )。 B+树适用于组织( 随机组织 )的索引结构， m阶B+树每个结点至多有( m ) 除根结点外每个结点至少有( (m/2)向上取整 )个儿子，根结点至少有( 2 )个儿子，有k个儿子的结点必有( k )个关键码。 5.物理记录之间的次序由指针相链表示的顺序文件称为( 串联文件) 6.顺序文件中，要存取第I个记录，必须先存取( 第I-1 )个记录。 7.索引顺序文件既可以顺序存取，也可以( 随机 )存取。 8.建立索引文件的目的的( 提高查找速度 )。 9.索引顺序文件是最常用的文件组织之一，通常用( 树 )结构来组织索引。 10.倒排文件的主在优点在于( 检索记录块 )。 11.检索是为了在文件中满足一定条件的记录而设置的操作。检索可以按( 关 键字 )检索，也可以按( 记录号 ) 检索； 按( 记录号 ) 检索又可以有( 顺序 ) 检索和( 直接 ) 检索。 12.哈希检索的技术的关键是( 构造哈希函数 )和( 解决冲突的方法 )。结构来组织索引。 13.VSAM系统是由( 索引集 )、( 顺序集 ) 、( 数据集 )构成的。 14.VSAM( 虚拟存储存取方法 )文件的优点是：动态地( 分配和释放存储空间 ) ，不需要文件进行( 重组 ) ，并能较快地( 对插入的记录 ) 进行查找。 一～五章选择题 一 1.学习数据结构的主要目的是( C )。 A．处理数据计算问题 B．研究程序设计技巧 C．选取合适数据结构，写出更有效的算法 D．是计算机硬件课程的基础2.数据结构是一门研究非数值计算的程序设计问题中计算机的逻辑存储以及 它们之间的( B )和运算的科学。 A．结构 B．关系 C．运算 D．算法 3.在计算机中存储一个数据元素的位串称为 ( A ) 。 A. 结点 B. 数据项 C. 数据字段 D. 字符串 4.算法指的是( C ) A.计算机程序 B.排序算法 C.解决问题的有限运算序列 D.解决问题的计算方法 5.( D )是数据不可分割的最小单位。 A．数据结构 B．数据对象 C．数据元素 D．数据项 6.数据结构有 ( D ) 种基本逻辑结构。 A. 1 B. 2 C. 3 D. 4 7.在数据结构中，从逻辑上可以把数据结构分成( C )。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 8.通常所说的时间复杂度是指( B )。 《数据结构》期末考试试题及答案 (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)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 一、单选题（共 10 道试题，共 50 分。）V 1. SQL Server中，保存着每个数据库对象的信息的系统表是（）。 A. sysdatabases B. Syscolumns C. Sysobjects D. Syslogs 满分：5 分 2. 在存在下列关键字的SQL语句中，不可能出现Where子句的是（）。 A. Update B. Delete C. Insert D. Alter 满分：5 分 3. 在查询语句的Where子句中，如果出现了“age Between 30 and 40”,这个表达式等同于（）。 A. age>=30 and age<=40 B. age>=30 or age<=40 C. age>30 and age<40 D. age>30 or age<40 满分：5 分 4. 如果要在一管理职工工资的表中限制工资的输入围，应使用（）约束。 A. PDRIMARY KEY B. FOREIGN KEY C. unique D. check 满分：5 分 5. 记录数据库事务操作信息的文件是（）。 A. 数据文件 B. 索引文件 C. 辅助数据文件 D. 日志文件 满分：5 分 6. 要查询XSH数据库CP表中产品名含有“冰箱”的产品情况，可用（）命令。 A. SELECT * FROM CP WHERE 产品名称LIKE ‘冰箱’ B. SELECT * FROM XSH WHERE 产品名称LIKE ‘冰箱’ C. SELECT * FROM CP WHERE 产品名称LIKE ‘%冰箱%’ D. SELECT * FROM CP WHERE 产品名称=‘冰箱’ 满分：5 分 7. 储蓄所有多个储户，储户能够在多个储蓄所存取款，储蓄所与储户之间是（）。 A. 一对一的联系 B. 一对多的联系 C. 多对一的联系 D. 多对多的联系 满分：5 分 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 《数据结构》期末考试题型及分值 （1）简答题6题*5分=30分简要回答要点 （2）分析题6题*5分=30分给出结果 （3）设计题1题*10分=10分设计思想及结果 （4）编程题1题*10分=10分完整代码 （5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度} 考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构） 二、非线性表（集合-树-图）} 2.抽象数据类型数据对象-数据关系-基本操作 3.算法性质-要求（设计）-效率（度量） 4.实例查找：高效查找算法 排序：高效的排序算法 分析题考试题目参考 （1）1-2-3-4-5-6顺序建BBST （2）6-5-4-3-2-1顺序建BBST 简答题实例 设计题： （1） （2） 数据结构试卷（一） 三、计算题（每题6分，共24分） 1. 在如下数组A 中链接存储了一个线性表，表头指针为A[0].next ，试写出该线性表。 A01234567 dat a 60 50 78 90 34 40 nex t 3 5 7 2 0 4 1 线性表为：（78，50，40，60，34，90）??????? ?????????01110 10 1 11101 11010101110 2. 请画出下图的邻接矩阵和邻接表。 3. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。见图12 图12 图11 四、阅读算法（每题7分，共14分） 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 作业参考答案 一、（带头结点）多项式乘法C= A×B： void PoｌyAdd ( list &C,liｓｔR) ／／R为单个结 点 { p=C; while(（!p-＞ｎeｘt) &＆(p->nexｔ-＞eｘp>Ｒ->eｘp)) p=p－>ｎｅｘt； ｉf (（p->next) ｜｜(ｐ->neｘt->ｅｘp<Ｒ-＞eｘp)) {R－＞nｅxt=ｐ->ｎeｘｔ;p->neｘｔ=Ｒ;} ｅlse { ｐ-＞nｅxt－＞inf +=R->inｆ;delｅte R; if （！p－>neｘｔ-＞iｎｆ) { R=ｐ-＞nｅxt；p－>next=R->ｎext;deleｔe R; ｝ } } ｖoｉｄPｏlｙMul （lｉst A, lｉst B，lｉst &C ） ｛ C=new sｔｒuct nｏｄe; Ｃ-＞neｘt=ＮUＬL；q=B->next; Wｈｉｌe (q ） { p＝A->neｘｔ; whiｌｅ（p ) { ｒ= new struct node；r->ｅxｐ= p->ｅxp ＋ｑ－>exp； r-＞ｉnf ＝ｐ-＞inf* q－>iｎf; PolyAｄd(C，r）； p=p-＞next; ｝ q=q－>ｎext; ｝ } 二、梵塔的移动次数: 已知移动次数迭代公式为：M ( ｎ)= 2M (n－1 ) + 1 初值为: Ｍ( 0 ) ＝0 则：M （n）＝ 2 （2M （n-2 ) + 1) + 1 =4M( n-2 )+ 3 = 8Ｍ(n－3 )+ 7 =２i M ( n-i ) + 2i– 1 若n＝ｉ，则Ｍ（n-ｎ) ＝0,故：M ( n ) =2ｎM( ｎ-n）+2n–1 =2n– 1 所以,梵塔的移动次数为2ｎ– 1次。 三、简化的背包问题： ｖoid Pacｋ( int ｍ, int i, ｉnt t ）// 初始值为:１１t ｛ for (k=i; k<＝ｎ; k＋＋) { soｌutiｏｎ[m] = ｗeighｔ[k]; if( t == weigｈｔ[k]) ｛ for ( j=1; ｊ<=m；j+＋) cout<＜ｓolutｉon［j]；coｕt< 试题六 一、单项选择题 （本大题共10小题，每小题2分，共20分) 在每小题列出的四个备选项中只有一个是符合题目要 求的，错选、多选或未选均无分。 1. DB 、DBMS 和DBS 三者之间的关系是（ ）。 A ．D B 包括DBMS 和DBS B ．DBS 包括DB 和DBMS C ．DBMS 包括DB 和DBS D ．不能相互包括 2. 对数据库物理存储方式的描述称为（ ） A ．外模式 B ．内模式 C ．概念模式 D ．逻辑模式 3. 在数据库三级模式间引入二级映象的主要作用是（ ） 得 分 (考 生 答 题 不 得 超 过 此 线) A．提高数据与程序的独立性B．提高数据与程序的安全性 C．保持数据与程序的一致性D．提高数据与程序的可移植性 4. 视图是一个“虚表”，视图的构造基于（） A．基本表B．视图 C．基本表或视图D．数据字典 5．关系代数中的π运算符对应SELECT语句中的以下哪个子句？（）A．SELECT B．FROM C．WHERE D．GROUP BY 6．公司中有多个部门和多名职员，每个职员只能属于一个部门，一个部门可以有多名职员，从职员到部门的联系类型是（） A．多对多 B．一对一 C．多对一 D．一对多 7．如何构造出一个合适的数据逻辑结构是（）主要解决的问题。 A．关系系统查询优化B．数据字典 C．关系数据库规范化理论D．关系数据库查询 8. 将E-R模型转换成关系模型，属于数据库的（）。 A. 需求分析 B. 概念设计 C. 逻辑设计 D. 物理设计 9．事务日志的用途是（） A. 事务处理 B. 完整性约束 C. 数据恢复 D. 安全性控制 10．如果事务T已在数据R上加了X锁，则其他事务在数据R上（） A. 只可加X锁 B. 只可加S锁 C. 可加S锁或X锁 D. 不能加任何锁 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（） 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则采用的排序方法是（） 1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 2019 数据库期末复习内容 1.选择题 （ 1）（数据库）是存储在计算机内结构化的数据的集合 （ 2）下述关于数据系统正确的描述是（数据库系统减少了数据冗余）。 （ 3）数据库（ DB）、与数据库系统（ DBS）和数据库管理系统（DBMS）之间的关系是（DBS 包含 DB 和 DBMS ）。（ 4）数据库管理系统的工作不包括（为定义的确据库提供操作系统）。 （ 5）用于对现实世界进行描述的工具是（数据模型）。 （ 6）在数据库的三级模式结构中，描述数据库中全局逻辑结构和特征的是（模式）。 （ 7） E-R图用来建立数据库的（概念模型）。 （ 8）下列模型中不能直接描述实体间多对多的联系的是（关系模型）。 （ 9）数据模型的三个要素是（数据结构、数据操作、完整性约束） （ 10）数据库的设计人员和用户之间沟通信息的桥梁是（实体联系图）。 （11）数据的独立性分为（逻辑独立性和物理独立性）。 （12）数据库通常是根据（数据模型）来分类的。 （ 13）关系数据库系统能实现专门的关系运算，包括（选择、投影、连接、除）。 （14）在关系模型中，下述关于关键字的说法正确的是（可以由一个或多个其值能唯一标识该关系模式中任何元组 的属性组成）。 （ 15）被称为关系的两个不变性，由关系数据库系统自动支持的是（实体完整性和参照完整性）。 （ 16）在关系中不能出现相同元组的约束是通过（主码）来实现。 （ 17）下列数据模型中，数据独立性最高的是（关系模型）. （18）规范化理论是关系数据库进行逻辑设计的理论依据。根据这个理论，关系数据库中的关系必须满足：每一属 性都是（不可分解的）。 （19）关系数据库规范化是为解决关系数据库中（插入异常、删除异常和数据冗余）问题而引入的。 （ 20）在关系数据库中，任何二元关系模式的最高范式必定是（BCNF） （ 21）若属性X 函数依赖于属性Y 时，则属性X 与属性 Y 之间的关系是（多对一）。 （ 22）设有关系模式：部门（部门代码，部门名称，部门成员，部门经理）由于其中（部门成员）属性存在， 使该关系不属于第一范式。 （ 23）若关系模式R 中的属性都是主属性，则R 最高属于（3NF）。 （ 24）若要彻底消除插入异常和删除异常，关系模式最低要属于（BCNF）。 （ 25）关系模式分解的无损连接和保持函数依赖两个特性之间的联系是（没有必然联系）。 （ 26）关系模式中数据依赖的存在，可能会导致成立蕴涵后者数据插入异常，这是指（该插入的数据未被插入）。（ 27）设要对关系模式R（学号，姓名，课程代码，课程名，课程成绩）进行分解，将其规范化到3NF，下列（ B）是正确的规范化结果。（学号，姓名）R2（课程代码，课程名）R3 （学号，课程代码，课程成绩） （ 28）有如下关系R（是 BCNF）。 （ 29）对用户访问数据库的权限加以限定是为了保护数据库的（安全性）。 （ 30）下面（可移植性）不是数据库系统必须提供的数据控制功能。 （ 31）数据库系统中，对存取权限定义为（授权）。 （ 32）在数据库的安全性控制中，为了保证用户只能存取他有权存取的数据，在授权的定义中，数据对象的（范围越小），授权子系统就越灵活。 （ 33）数据库安全性遭到破坏的情况属于（非法用户读取数据库中的数据）。 （ 34）数据库的（完整性）是指数据的正确性和相容性。 （ 35）数据完整性保护中的约束条件是指（值的约束和结构的约束）。 （ 36）实体完整性和参照完整性属于（静态关系约束）。 （ 37）数据类型、取值范围、空值约束属于（静态列级约束）。 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 北邮算法与数据结构习题参考答案 作业参考答案 一、（带头结点）多项式乘法 C = A×B： void PolyAdd ( list &C, list R) // R 为单个结点 { p=C; while ((！p->next) && (p->next->exp>R->exp)) p=p->next; if ((p->next) || (p->next->exp 数据库原理综合习题答案 1.1名词解释 (1) DB：即数据库（Database),是统一管理的相关数据的集合。DB能为各种用户共享，具有最小冗余度，数据间联系密切，而又有较高的数据独立性。 (2) DBMS：即数据库管理系统（Database Management System)，是位于用户与操作系统之间的一层数据管理软件，为用户或应用程序提供访问DB的方法，包括DB的建立、查询、更新及各种数据控制。DBMS总是基于某种数据模型，可以分为层次型、网状型、关系型、面向对象型DBMS。 (3) DBS：即数据库系统（Database System),是实现有组织地、动态地存储大量关联数据，方便多用户访问的计算机软件、硬件和数据资源组成的系统，即采用了数据库技术的计算机系统。 (4) 1：1联系：如果实体集E1中的每个实体最多只能和实体集E2中的一个实体有联系，反之亦然，那么实体集E1对E2的联系称为“一对一联系”，记为“1：1”。 (5) 1：N联系：如果实体集E1中每个实体与实体集E2中任意个（零个或多个）实体有联系，而E2中每个实体至多和E1中的一个实体有联系，那么E1对E2的联系是“一对多联系”，记为“1：N”。 (6) M：N联系：如果实体集E1中每个实体与实体集E2中任意个（零个或多个）实体有联系，反之亦然，那么E1对E2的联系是“多对多联系”，记为“M：N”。 (7) 数据模型：模型是对现实世界的抽象。在数据库技术中，表示实体类型及实体类型间联系的模型称为“数据模型”。它可分为两种类型：概念数据模型和结构数据模型。 (6) 概念数据模型：是独门于计算机系统的模型，完全不涉及信息在系统中的表示，只是用来描述某个特定组织所关心的信息结构。 (9) 结构数据模型：是直接面向数据库的逻辑结构，是现实世界的第二层抽象。这类模型涉及到计算机系统和数据库管理系统，所以称为“结构数据模型”。结构数据模型应包含：数据结构、数据操作、数据完整性约束三部分。它主要有：层次、网状、关系三种模型。 (10) 层次模型：用树型结构表示实体类型及实体间联系的数据模型。 (11) 网状模型：用有向图结构表示实体类型及实体间联系的数据模型。 (12) 关系模型：是目前最流行的数据库模型。其主要特征是用二维表格结构表达实体集，用外鍵表示实体间联系。关系模型是由若干个关系模式组成的集合。 (13) 概念模式：是数据库中全部数据的整体逻辑结构的描述。它由若干个概念记录类型组成。概念模式不仅要描述概念记录类型，还要描述记录间的联系、操作、数据的完整性、安全性等要求。 (14) 外模式：是用户与数据库系统的接口，是用户用到的那部分数据的描述。 (15) 内模式：是数据库在物理存储方面的描述，定义所有的内部记录类型、索引和文件的组成方式，以及数据控制方面的细节。 (16) 模式/内模式映象：这个映象存在于概念级和内部级之间，用于定义概念模式和内模式间的对应性，即概念记录和内部记录间的对应性。此映象一般在内模式中描述。 (17) 外模式/模式映象：这人映象存在于外部级和概念级之间，用于定义外模式和概念模式间的对应性，即外部记录和内部记录间的对应性。此映象都是在外模式中描述。 (18) 数据独立性：在数据库技术中，数据独立性是指应用程序和数据之间相互独立，不受影响。数据独立性分成物理数据独立性和逻辑数据独立性两级。 (19) 物理数据独立性：如果数据库的内模式要进行修改，即数据库的存储设备和存储方法有所变化，那么模式/内模式映象也要进行相应的修改，使概念模式尽可能保持不变。也就是对模式的修改尽量不影响概念模式。 自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 数据结构复习要点带答案 算法的五大特性：（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。 算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列；算法分析的目的是（分析算法的效率以求改 进），算法分析的两个主要方面是（空间性能和时间性能）。 1.算法质量的标准：时间复杂度是测量一个算法优劣的重要标准。 时间复杂度的计算：设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1)），若为n*log25n，则表示成数量级的形式为（Ο(nlog2n)）。 【分析】：用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2.数据、数据元素、数据项的关系：（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体 进行考虑和处理；（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。 【分析】数据结构指的是数据元素以及数据元素之间的关系。 3.设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。 试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1-3所示，它是一种图结构。 4.栈的特性：栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一段叫做栈顶，另一 端叫做栈底，不含任何数据元素的栈叫做空栈。（栈）可作为实现递归函数调用的一种数据结构。 【分析】递归函数的调用和返回正好符合后进先出性。 栈的特点是先进后出，即：进去的早，出来的晚！ 54321进栈，5在栈底，1在栈顶！ 出一次栈，则栈顶的1先出来，2成为新的栈顶。 ABCD入栈，D成为新的栈顶。 全部出栈：D C B A 2 3 4 5 综上，所有元素退栈顺序为：1 D C B A 2 3 4 5 5.入栈：template sql数据库期末考试题及答案 一、单选题(共10道试题，共50分。)1. SQL Server中，保存着每个数据库对象的信息的系统表是 (C)。 A. sysdatabases B. Syscolu mns C. Sysobjects D. Syslogs 2. 在存在下列关键字的SQL语句中，不可能出现Where子句的是(D )。 A. Update B. Delete C. I nsert D. Alter 3. 在查询语句的Where子句中，如果出现了" age Between 30 and 40 ” ,这个表达式等同于( A) A. age>=30 and age<=40 B. age>=30 or age<=40 C. age>30 and age<40 D. age>30 or age<40 4. 如果要在一张管理职工工资的表中限制工资的输入范围，应使用( D )约束。 A. PDRIMARY KEY B. FOREIGN KEY C. uni que D. check 5. 记录数据库事务操作信息的文件是( D )。 A.数据文件 B.索引文件 C.辅助数据文件 D.日志文件 6. 要查询XSH数据库CP表中产品名含有“冰箱”的产品情况，可用( C)命令。 A. SELECT * FROM CP WHERE 产品名称LIKE '冰箱’ B. SELECT * FROM XSH WHERE 产品名称LIKE '冰箱’ C. SELECT * FROM CP WHERE 产品名称LIKE '淋箱% D. SELECT * FROM CP WHERE 产品名称='冰箱’ 7. 储蓄所有多个储户，储户能够在多个储蓄所存取款，储蓄所与储户之间是( D )。 A. 一对一的联系 B. 一对多的联系 C.多对一的联系 D.多对多的联系 8. SQL的聚集函数COUN T SUM AVG MAX MIN不允许出现在查询语句的( D)子句之中。 A. SELECT B. HAVING C. GROUP BY- HAVING D. WHERE 9. 列值为空值(NULL)则说明这一列(C)。 A.数值为0 B. 数值为空格 C.数值是未知的 D. 不存在 10. 数据库的数据一般存放在(D )中。 A.内存 B. CPU C. 寄存器 D. 磁盘 SQL Server数据库试题十及答案 一、单项选择题(每题2分，共15题) 1. SQL Server 2000 是一个(C )的数据库系统。 (A)网状型 (B)层次型(C)关系型(D)以上都不是 2. DTS是一个简称，它的全称是(B )。 A.数据运输系统 B.数据传输服务 C.数据库传输系统 D.数据库运输服务 3. SQL Server 2000 采用的身份验证模式有( D)。 (A)仅Windows身份验证模式(B)仅SQL Server身份验证模式 (C)仅混合模式(D) Windows身份验证模式和混合模式 4. SQL语言按照用途可以分为三类，下面选项中哪一种不是的：(C) (A) DML (B) DCL (C) DQL (D) DDL 5. 在SELECT语句的WHER子句的条件表达式中，可以匹配0个到多个字符的通配符是(B ) (A) * (B) % (C) - (D) ? 6. SQL Server提供的单行注释语句是使用( B)开始的一行内容。 (A) “/* ”( B) “-- ”( C) “{”( D) “/” 7. 以下那种类型能作为变量的数据类型( C)。 (A) text (B) ntext (C) table ( D) image 8.下面不属于数据定义功能的SQL语句是：(C)数据结构复习题总结
数据结构期末考试试题及答案
sql数据库期末考试题及答案
(完整版)非常实用的数据结构知识点总结
数据结构期末考试复习总结,DOC
北邮算法与数据结构习题参考标准答案
数据库期末考试复习题及答案共有套卷子
数据结构复习要点(整理版).docx
《数据结构》期末考试题带答案(99%能过)
数据结构 期末考试复习题及答案
大学数据库考试复习总结计划试卷试题带答案.doc
数据结构复习提纲(整理)
北邮算法与数据结构习题参考答案
数据库原理与应用期末复习总结含试题及其答案
2021年自考02331数据结构重点总结最终修订
数据结构期末复习总结超详细1
sql数据库期末考试题及答案
相关主题
文本预览