数据结构练习题
说明：除题中另有说明外，本书均采用下面的存储结构及操作
二叉链表的C语言存储描述如下单向链表的存储
typedef struct BiTNode typedef struct LNode
{char data；//元素信息{ElemType data；
struct BiTNode *lchild，rchild；struct LNode *next；
}BiTNode，*BiTree；}LNode，*LinkList；
邻接表的C语言存储描述如下基本操作如下
typedef struct Arc InitStack(S)
{int adj；//顶点序号StackEmpty(S)
struct Arc *next；Push(S，e)
}ArcNode，*ARC；//表结点Pop(S，e)
typedef struct Vnode{ //头结点InitQueue（Q）
char data；//元素信息QueueEmpty（Q）
ARC *first；Enqueue（Q，x）
}Graph[N]；//N为顶点的实际个数DelQueue（Q，x）
一、判断正误
1、线性表采用链式存储，则链表中结点总数一定等于元素总数。
2、栈是一种后进先出的线性表，因此，元素的进栈序列和出栈序列不可能相同。
3、无论采用何种存储结构，队列的入队、出队次序一定相同。
4、由三个不同关键字构造的二叉排序树的基本形态共有五种。
5、若非空二叉树的先序、中序遍历序列相同，则必为仅有一个根的二叉树。
6、二叉链表存储的二叉树中结点总数为n，则空指针域总数必为n+1。
7、n(>0)个权值作为叶子构造的哈夫曼树中结点总数为2n-1。
8、森林的后序遍历与它对应的二叉树的中序遍历相同。
9、折半查找的平均查找效率高于顺序查找，因此，查找某一元素时，折半查找所需与关键字的比较次数一定少于顺序查找。
10、二叉排序树的中序遍历序列按关键字递增有序。
11、有向图的邻接表的第i个链表中表结点总数为该顶点的度。
12、顺序表，链表，二叉链表，邻接表，散列表均为存储结构。
13、选取散列函数时，冲突越少越好。
14、冒泡，直接插入，归并，基数排序均为稳定排序。
15、快速排序最坏的时间复杂度为O（N*logN）。
16、不稳定排序后，相同关键字元素的相对位置一定发生改变。
17、直接插入排序适用于元素个数较少或初始序列基本有序情况。
18、对称矩阵压缩存储后不具备随机存取的特点。
19、在考虑存储结构的前提下，有向图的拓扑排序序列一定唯一。
20、折半查找要求元素必须按关键字有序，且只能采用顺序存储结构。
二、填空题
数据的基本单位是_____，数据结构常见的逻辑结构有_____，存储结构有____。
数据结构的逻辑结构可视为一个二元组Data_Structure=（D，S），其中D是_____，S是_____。数据结构的抽象数据类型ADT是指一个数学模型及定义在该模型上的一组操作。它可用三元组（D，S，P）表示，其中D是数据对象，S是_____，P是_____
设计一个好的算法应达到的目标是正确性、_____、_____和高效率低存储量。算法时间效率、
空间效率的度量分别称为_____、_____。
5、顺序表、链表分别通过_____、_____体现元素的前驱、后继的逻辑关系。
6、在表长为n的顺序表中插入、删除元素时，在等概率条件下平均移动元素的次数分别为_____、_____，具体移动的元素个数与_____有关。
7、已知L为头指针的带头结点的单循环链表（指针域为next），a．若R为尾指针，则满足的条件为______，b．若该表为空表，则满足的条件是______。
8、已知五个元素ABCDE的进栈次序为ABCDE，a．若C为第一个出栈元素，则下一个出栈的元素可能是_____；b．能否得到出栈序列CDBEA______、CEDAB______？
9、若三个元素ABC的进栈次序为ABC，则借助栈一共可以得到______中出栈序列？
10、已知顺序存储的循环队列中，f，r分别为队头、队尾指针，MAX为队列中存储单元的最大个数。若当队列中仅有一个空闲单元时视为队满，则队空、队满条件分别为_____、_____；一般情况下，队列中元素个数可表示为_____ 。
11、广义表A=((a，(b)，c)，(d)，(e，f，g))的表长为_____，深度为_____，利用取表头、表尾运算表示原子e的表达式为_____。
12、广义表中元素既可以是单原子，也可以是_____，广义表的两个基本操作是_____和_____。
13、10个结点二叉树至多有_____个叶子，最低高度为_____。
14、83个结点的完全二叉树高度为_____，其中叶子个数为_____，一度结点个数为_____。
15、n(n>0)个结点的完全二叉树叶子个数为_____，一度结点个数为_____。
16、高度为5的BST树结点总数至多，至少为_____，_____。
17、n个叶子的哈夫曼树最高高度为_____，结点总数为_____。
18、从本质上而言，森林的孩子兄弟链表与它转换所对应的二叉树的_____存储结构一致。
19、n个顶点的无向、有向完全图的边数分别是_____、_____，n个顶点的强连通图至少有_____条边。
20、无向网的最小生成树的构造算法是_____和_____；n个顶点的无向网构造的最小生成树中边的条数为_____。
21、构造散列表要解决的两个问题是_____；若将关键字序列的散列地址定位在100至110之间，则散列函数可表示为H（key）=_____。
22、从理论上讲，散列查找的算法效率为_____，但实际应用时，常常因为_____使查找速度有所降低。
23、若关键字序列为正序，则直接插入、冒泡、简单选择、归并、快速、堆排序中排序效率最高的是_____和_____，此时时间复杂度为__________。
24、希尔排序每趟的排序方法是_____，平均时间复杂度为_________；快速排序的平均时间复杂度为_______，最坏时间复杂度为________。
25、排序时所需与关键字的比较次数仅与元素个数有关而与关键字的初始序列无关的排序方法是_____，若关键字个数为n个，则第一趟的比较次数为_____。
26、写出三种不稳定的排序方法的名称_____、_____和_____。
27、n个元素进行起泡排序时，最好情况下只需进行_____次比较和____次交换，最坏情况需进行_____次比较和_____次交换。
三、综合题
1、已知线性链表中结点的数据域、指针域依次为data、next，写出在表中删除*p结点的语句（设该结点存在后继）及*p结点前插入*s结点语句。
2、简述顺序表、链表的各自特点。
3、简述链式存储中头结点、头指针；结点、元素的区别。
4、n阶矩阵Aij（1≤i，j≤n）或Aij（0≤i，j≤n-1）的上三角(不含对角线)为常数C，下三
角无规律，设计压缩存储方案。
5、画出广义表A=((a，(b)，c)，(d)，(e，f))的链式存储结构。
6、画出由三个结点构造的二叉树的基本形态。
7、已知一棵度为5的树中1度，2度，．．．，5度结点的个数依次为1，2，．．．，5，则叶子个数为多少？
8、证明任意一棵二叉树中叶子数等于两度结点数加1。
9、已知字符Ａ，Ｂ，．．．，G的权值依次为(5，7，8，10，9，20，30)，设计各个字符的Huffman 编码，画出Huffman树的存储结构，并计算WPL值。
10、已知二叉树的先序，中序遍历序列分别为EFHBDGAC，FHDBEAGC，画出二叉树的逻辑结构，顺序存储结构和中序线索二叉树的逻辑结构图示。
11、已知某二叉树由八个字符A--H组成，先序，中序，后序遍历序列分别为___AC___E___GH；C___DB___GHF；___DA___FEB，画出二叉树的逻辑结构和后序线索二叉树的存储结构。提示：每个空白处至少缺少一个字符。
12、已知森林的逻辑结构如图1所示，画出它的孩子兄弟链表存储结构及其转换的二叉树的逻辑结构。
13、已知无向网如图2所示，画出根据PRIM算法构造的最小生成树步骤图示。
14、画出图3所示无向图的邻接表，以它为基础写出深度、广度优先遍历序列及画出深度、广度优先生成树（从结点A开始）。
15、画出图4所示有向图的邻接矩阵，邻接表，并以该邻接表为基础，写出它的深度、广度优先遍历序列、拓扑排序序列（其中拓扑排序要求标示出入度为0的顶点进栈、出栈的先后次序）。
16、分别画出关键字序列(34，23，56，32，27，30，58，89，56)构造的BST树、A VL树的逻辑结构，并分别计算等概率成功查找条件下的ASL值；设a1、a2、a3是不同的关键字且a1 17、画出对13个有序关键字进行折半查找的折半查找树。 18、已知散列函数为除余法(余数为7)，关键字序列为(49，10，16，40，79，28，18，83) ，分别采用下列冲突处理方法构造散列表，并计算等概率成功查找条件下的ASL值。 1）链地址法2）线性探测法（表长为11）；3）二次探测再散列法（表长为25）。 19、已知关键字序列为(34，17，56，32，45，50，89，19，20，41)，分别写出以下各排序方法每趟排序的结果，并指出它们的稳定性。1）直接插入2）二路归并3）快速4）堆排序5）冒泡6）简单选择7）基数8）希尔。 20、解释下列概念： 头指针，头结点，数据结构，Huffman树，BST树，A VL树，不稳定排序，散列表。 21、用C语言描述下列存储结构：双向链表，循环队列，二叉链表，线索链表，邻接表。 22、已知关键字序列{52，41，95，21，14，28，82，29}，画出构造的3阶B-树。 23、对称矩阵 1 0 0 2 0 3 0 0 A= 0 0 0 5 行列下标i，j满足：1≤i，j≤4 0 5 0 1 2）若将视为稀疏矩阵，画出三元组表。 四、算法填空 判断带头结点的单向链表中结点数据值(整型)是否对称的算法如下，对称返回1，否则返回0。PUSH(S，x)，POP(S，x)分别代表为进栈，出栈函数 int xyx(LinkList L) {LinkList p，q； int n，n1，i，x； p=L->next；q=p；n=0； while (q) {n++；q=q->next；} n1=__________； for(i=1；i<=n1；i++){PUSH(S，p->data)；__________；} if(________) p=p->next； while(p){ POP(S，x)； if（p->data!=x）break； p=p->next； } if(________)return(1)；else return(0)； } 2、删除L单链表中最大元素结点的算法。 void delmax(LinkList &L) {LinkList p，q，r；int m； r=L；p=L->next； if (p) {m=p->data； ________； p=p->next； while(p) {if (_________){___________；m=p->data；} __________； p=p->next； } q=r->next； ___________ free(q)； } } 3、将二叉树bt的各个结点左右子树互换算法，ADDQ(Q，bt)，DELQ(Q)，EMPTY(Q)分别代表入队、出队、判队空函数（10分） void EXCHANGE(BiTree &bt) {Tree p，q； if (bt) {ADDQ(Q，bt)； while(!EMPTY(Q)) {p=DELQ(Q)； if(p->lchild)__________； if(p->rchild)__________； q=________； p->rchild=_________； ________=q； } } } 4、将带头结点的单链表中所有的奇数放在链表的前面，偶数放在后面。 void change(LinkList &L) {LinkList p，q； p=L->next； if(p) while(__________ ) if (__________){q=p->next；p->next=q->next； __________；L->next=q； } else________； } 4、设算术表达式右字符串exp表示，可以包含三种括号：“（）”，“[ ]”，“{ }”它 们可以任意次序嵌套使用，实现算法填空，判定表达式中括号是否匹配 int f(char exp) {int legal=1； SqStack s； InitStack(&s)； for (int I=0；legal&&exp[I]!=’\0’；I++) {switch(exp[ I]) {case ‘(‘：_________ ；break； case ‘[‘：_________ ；break； case ‘{‘：_________；break； case ‘)’： case ‘]’： case ‘}’：if(StackEmpty(s)||exp[I]!= _________ )legal=0； }//switch }//for return legal&&_________； }//f 5、说明该算法的功能，若输入数据为ABCDEFG回车，画出该算法所得到的存储结构。void Unknown(LinkList &head){ LinkList head，s； char ch； head=(ListNode *)malloc(sizeof(ListNode))； head->next=NULL； printf("输入数据以回车键结束！\n")； while((ch=getchar())!='\n'){ s=(ListNode *)malloc(sizeof(ListNode))； s->data=ch； s->next=head->next； head->next=s； } } 6、说明该算法的功能；若输入数据为AB#CD##E##F##回车，画出该算法所得到的存储结 构。 void Unknown(BiTree &T) {char ch； if （（ch=getchar（））==' #'）T=NULL； else{T=(BinTree)malloc(sizeof(BinTNode))； T->data=ch； Unknown(T->lchild)； Unknown(T->rchild)； } } 8、完善下面实现有向图的拓扑排序算法，并说明该算法中栈的作用。 int TopologiSort(Graph G)//拓扑排序成功返回1，否则返回0 {int i，count=0； SqStack S； int ind [MAX]；//存储各顶点的入度 ArcNode *p； FindIndegree(G，ind)；//计算各个顶点的入度 InitStack(S)； for(i=0；i if(!ind[i]) ______________； printf("\nTopological Sort is \n")； while(___________) {Pop(&S，&i)； if (count==0) printf("%c"，G[i].data)； else printf("-->%c"，G.[i].data)； count++； for(p=_____________；p；p=__________) if (!--ind[p->adj])//若入度为零 _______________； } if (_____________)return(0)；else return(1)； } 五、算法设计 1、已知两个带头结点的单向链表Ａ＝（a，b，．．．，c）；Ｂ＝（d，ｅ，．．．，ｆ），设计算法将它们合并为一个单向循环链表Ａ＝（a，b，．．．，c，ｆ，．．．ｅ，ｄ）。 2、实现把N个正整数中的所有奇数排列在偶数之前，分别用顺序结构、单向链表、双向循环链表实现。 3、已知单向链表L中元素为正整数，设计算法删除所有偶数。 4、已知单向循环链表L，结点有三个域：prior，data，next，其中next为后继指针，data 为数据域，prior初值为NULL，写出将其改成双向循环链表的算法。 5、已知无头结点单向循环链表表长大于1，指针s指向表中某结点，写出删除*s前驱的算法。 6、写出把单向链表L逆置算法。1）不允许申请空间；2）不允许破坏原表结构。 7、在非递减有序单向链表L中插入元素e，使序列仍有序的算法InsertList(LinkList L，ElemType e)。 类似题目：某百货公司仓库中的电视机的价格和数量信息，按其价格从低到高存储在一个带头结点的单循环链表中。结点由价格（cost）、数量（num）和链指针（next）三个域组成，现新到m台价格为c的电视机需要入库，试编写修改循环链表中存储的电视机信息的算法，并进行算法效率分析。 8、写出把两个非递减有序链表A，B合并成一个非递增（或非递减）有序链表C的算法MergeList（LinkList A，LinkList B，LinkKList &C）。 9、设计算法DivideList（LinkList &A，LinkList &B，int i）实现将一个单向链表Ａ＝（a，b，．．．，c，d，．．．ｅ，f）分解为两个链表A、B，其中Ａ＝（a，b，．．．，c）；Ｂ＝（f，．．．，e，d）；c为表中第i个元素。 10、把一个正整数单向链表A分解成两个链表A，B，其中A表全为奇数，B表为偶数。 11、约瑟夫（Joseph）问题：编号为1，2，3，．．．，n的n个人按顺时针围成一圈，从第s 个人开始按顺时针报数（报数依次为1，2，3，．．．），报数为m的人出队，再从下一个开始继续按上述原则报数，设计算法输出出队序列。 12、判断双向链表中元素是否对称，若对称返回1否则返回0。 13、L为头指针的双向循环链表，每个结点除了有prior，data，next域外，还增加一个访问频度域freq。初始freq值为0，每当对链表进行一次LOCATE（L，x）操作，被访问结点（元素值为x）的访问频度增1，同时调整结点次序，使其按访问频度非递增次序排列以便提高查找效率，设计该算法LOCATE（L，x）。 14、已知带头结点的双向链表表示队列，最后一个结点为队尾，仅设头指针L，写出元素e 入队的算法。（若表示栈，第一个元素结点为栈顶元素，写出元素e入栈算法。） 15、已知无头结点的单向循环链表表示栈，仅设尾指针R，写出元素e入队的算法。 16、分别写出计算链式存储的广义表中原子的个数和深度算法。 17、分别实现以三元组存储结构的稀疏矩阵的转置、相加算法。 18、设计将二叉链表中各个结点的左右孩子互换算法。 19、设计先序/中序遍历二叉树的非递归算法（思考题：求二叉树的叶子个数的非递归算法）。 20、写出求二叉树的高度算法。 21、先序线索二叉树的先序遍历算法。 22、中序线索二叉树的中序遍历算法。 23、以线索链表为存储结构，写出在后序线索链表中查找*p的后序前驱算法。 24、以线索链表为存储结构，已知中序线索树中某结点*p，写出将*s结点作为*p的右孩子 或左孩子插入的算法。 25、借助队列实现二叉树的层次遍历。 26、计算孩子兄弟链表存储的森林中叶子个数。 27、已知N个结点的某二叉树的先序、中序遍历序列存储于两个数组A，B中，写出建立该二叉树的二叉链表算法。 28、写出建立一个有向图的邻接表的算法。 29、在有向图的邻接表的基础上计算各顶点的度。 30、以邻接表为存储结构实现输出有向图的拓扑排序序列。 31、采用邻接表存储实现无向图的深度优先非递归遍历。 应用或变形题目：判断以邻接表为存储结构的无向图中任意两顶点间是否存在路径，若存在，输出路径上的顶点序列；输出无向图中连通分量个数及各连通分量的顶点序列。 32、采用邻接表存储实现无向图的广度优先遍历。 33、采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。 34、已知BST树root的某结点*p的左右子树均非空，写出删除该结点的算法。 35、已知N个整型关键字序列存于向量A[1．．N]中，写出建立BST树的非递归算法。 36、已知散列表长度为m，散列函数为H（x），冲突处理方法为拉链法，设计算法输入一组关键字，建立散列表，要求同义词结点按递增排列。 37、已知散列表长度为m，散列函数为H（x），冲突处理方法为线性探测法，设计算法输入一组关键字（个数小于m）建立散列表。 38、写出以链表为存储结构的直接插入排序算法，注意：表中元素个数未知。 39、写出以链表为存储结构的简单选择排序算法。 40、写出以链表为存储结构的冒泡排序算法。 41、利用栈结构写出快速排序的非递归算法，要求打印每趟排序结果。 42、写出折半插入排序算法(即确定元素的插入位置时采用折半的方法)。 43、编写双向起泡排序算法，即扫描方向交替进行。 44、表达式a+b*（c—d）—e/f可以表示为二叉树结构，运用后序遍历二叉树规则，写出对表达式求值算法 45、设P为某二叉排序树中一结点的指针，且P结点的左右子树均存在，写出删除指针P 结点的算法DELTP（p）。 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ①栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ②循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ①栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ③栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ④循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ②栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ⑤栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ⑥循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ③栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ⑦栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ⑧循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ④栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ⑨栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ⑩循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ⑤栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ?栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ?循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ⑥栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ?栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ?循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ⑦栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ?栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ?循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ⑧栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ?栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ?循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ⑨栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： ?栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 ?循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ⑩栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 数据结构题集（C语言版）清华大学出版社2007年 实验项目： 实验一、栈和循环队列 ㈠、实验内容： 21栈 掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。 本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所 有栈里的元素四个功能。 22循环队列 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具 有初始化一个队列、入队、出队、显示队列的所有元素、队列长度 五个功能。 ㈡、实验代码 ?栈 程序代码： #include #include #define Stack_Size 6 #define ERROR 0 #define OK 1 typedef int SElemType; typedef struct SNode { SElemType data; struct SNode *next; 数据结构实验 实验内容和目的： 掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。 试题一 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请 将其代码填写在题后的括号内。错选、多选或未选均无分。1. 数据库系统的核心是（ B ） A．数据库B．数据库管理系统 C．数据模型D．软件工具 2.下列四项中，不属于数据库系统的特点的是（C ） A．数据结构化B．数据由DBMS统一管理和控制 C．数据冗余度大D．数据独立性高 3.概念模型是现实世界的第一层抽象，这一类模型中最著名的模型是（ D ） 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．车次B．日期 C．车次+日期D．车次+情况摘要 8.己知关系R和S，R∩S等价于（ B ） A. (R-S)-S B. S-(S-R) C.(S-R)-R D. S-(R-S) 9．学校数据库中有学生和宿舍两个关系： 学生（学号，姓名）和宿舍（楼名，房间号，床位号，学号） 假设有的学生不住宿，床位也可能空闲。如果要列出所有学生住宿和宿舍分配的情况， 包括没有住宿的学生和空闲的床位，则应执行（ A ） A. 全外联接 B. 左外联接 《数据库原理与应用》 一．单项选择题（每题1分，共20分） 1.目前市场上常见的DBMS 90%以上都是基于（ C ）数据模型的。 A．层次B．网状C．关系D．面向对象 2.E-R图是在数据库设计中用来表示（ A ）的一种常用方法。 A．概念模型B．逻辑模型C．物理模型D．面向对象模型 3.（ C ）是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。 A．外模式B．内模式C．模式D．概念模式 4.（ B ）也称存储模式，是数据库物理结构和存储方式的描述，是数据在数据库内部的表示方式。 A．外模式B．内模式C．模式D．概念模式 5．数据库的概念模型独立于（ A ）。 A．具体的机器和DBMS B．E-R图C．信息世界D．现实世界 6.在数据库中存储的是（ C ）。 A．数据B．数据库模型C．数据以及数据之间的联系D．信息 7．规范化理论是关系数据库进行逻辑设计的理论依据，根据这个理论，关系数据库中的关系必须满足：其每一个属性都是（ B ）。 A．互不相关的B．不可分解的C．长度可变得D．互相关联的 8.在数据模型中有“型”和“值（或实例）”两个对应的概念。其中数据库的模式是一个（ D ）的概念，是一个相对（）的概念，而数据库在某一时刻的状态则是一个（）的概念，是一个相对（）的概念。 A．型；变化；值；不变B．值；不变；型；变化 C．值；变化；型；不变D．型；不变；值；变化 9.关系表A的属性个数为5，元组个数为10；关系表B的属性个数为6，元组个数为20. 则A与B的笛卡尔积A×B的属性有（ D ）个，元组个数有（）个。 A．30；200B．11；30 C．30；30D．11；200 10.父亲和子女的亲生关系属于（ B ）的关系。 A．1：1B．1：n C．m：n D．不一定 11.在SQL语言中，删除关系表中的一个属性列，要用动词（ D ），删除关系表中的一行或多行元组，要用动词（）。 A．delete，delete B．drop，drop C．delete，drop D．drop，delete 12.在SQL语言中，为关系模式增加一个属性要用动词（B）,为关系表增加一行或多行元组要用动词（）。 A．insert，insert B．add，insert C．insert，add D．add，add 13.实体完整性约束和SQL语言中的（ A ）相对应。 A．primary key B．foreign key C．check D．都不是 14.参照完整性约束和SQL语言中的（ B ）相对应。 A．primary key B．foreign key C．check D．都不是 15.在我们的学生-课程数据库中，SC表上建立了两个外码约束，被参照表是Student表和Course表，则最适当的说法是： A．Student表中的学生号Sno不能随意取值B．Course表中的课程号Cno不能随意取值 C．SC表中学生号Sno不能随便D．SC表中学生号Sno、课程号Cno均不能随意取值 16.如果在学生-课程数据库中的SC表上建立了参照完整性约束： Foreign Key （Sno）References Student（Sno）， Foreign Key （Cno）References Course（Cno）， 则（ D ）操作可能会违背该完整性约束。 A．在Student表上增加一行记录B．在Course表上增加一行记录 C．在SC表上删除一行记录D．更新SC表上的记录 17.关系R（X，Y，Z），函数依赖集FD={Y→Z，XZ→Y}，则关系R是（ C ）。 A．1NF B．2NF C．3NF D．BCNF 18、表之间一对多关系是指_B_____。 A．一张表与多张表之间的关系B．一张表中的一个记录对应另一张表中的多个记录 C．一张表中的一个记录对应多张表中的一个记录D．一张表中的一个记录对应多张表中的多个记录 19、SQL的SELECT语句中，“HAVING条件表达式”用来筛选满足条件的（D） A．列B．行C．关系D．分组 20、SQL语言中INSERT、DELETE、UPDA TE实现哪类功能 D 。 A．数据查询B．数据控制C．数据定义D．数据操纵 二．填空题（每空1分，共18分）： 1.从历史发展看来，数据管理技术经历了人工管理、文件管理和数据库管理三个阶段。 2.在SQL语言中，用符号—代表单个字符，用符号% 代表0到多个字符。 3.在SQL语言中，为了使查询的结果表中不包含完全相同的两个元组，应在select的后面加上关键词distinct 。 4、在SQL语句中，与表达式“工资BETWEEN 1210 AND 1240”功能相同的表达式是工资>=1210 and 工资<=1240 。 第 1 页/共 4 页 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 .没有共同点 A1、以下（）内存区不属于SGA。 A．PGA B．日志缓冲区C．数据缓冲区D．共享池 D2、（）模式存储数据库中数据字典的表和视图。 A．DBA B．SCOTT C．SYSTEM D．SYS C3、在Oracle中创建用户时，若未提及DEFAULT TABLESPACE 关键字，则Oracle就将（）表空间分配给用户作为默认表空间。 A．HR B．SCOTT C．SYSTEM D．SYS A4、（）服务监听并按受来自客户端应用程序的连接请求。 A．OracleHOME_NAMETNSListener B．OracleServiceSID C．OracleHOME_NAMEAgent D．OracleHOME_NAMEHTTPServer B5、（）函数通常用来计算累计排名、移动平均数和报表聚合等。 A．汇总B．分析C．分组D．单行 B6、（）SQL语句将为计算列SAL*12生成别名Annual Salary A．SELECT ename,sal*12 …Annual Salary? FROM emp; B．SELECT ename,sal*12 “Annual Salary” FROM emp; C．SELECT ename,sal*12 AS Annual Salary FROM emp; D．SELECT ename,sal*12 AS INITCAP(“Annual Salary”) FROM emp; B7、锁用于提供( )。 A．改进的性能 B．数据的完整性和一致性 C．可用性和易于维护 D．用户安全 C8、( )锁用于锁定表，允许其他用户查询表中的行和锁定表，但不允许插入、更新和删除行。 A．行共享B．行排他C．共享D．排他 B9、带有( )子句的SELECT语句可以在表的一行或多行上放置排他锁。 A．FOR INSERT B．FOR UPDATE C．FOR DELETE D．FOR REFRESH C10、使用( )命令可以在已分区表的第一个分区之前添加新分区。 A．添加分区B．截断分区 C．拆分分区D．不能在第一个分区前添加分区 C11、( )分区允许用户明确地控制无序行到分区的映射。 A．散列B．范围C．列表D．复合 C12、可以使用（）伪列来访问序列。 A．CURRVAL和NEXTVAL B．NEXTVAL和PREVAL C．CACHE和NOCACHE D．MAXVALUE和MINVALUE A13、带有错误的视图可使用（）选项来创建。 A．FORCE B．WITH CHECK OPTION C．CREATE VIEW WITH ERROR 数据库期末考试试题及答案 一、选择题(每题1分，共20分) 1(在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。 在这几个阶段中，数据独立性最高的是( A )阶段。 A. 数据库系统 B. 文件系统 C. 人工管理 D.数据项管理 2(数据库三级视图，反映了三种不同角度看待数据库的观点，用户眼中的数据库称为(D)。 A. 存储视图 B. 概念视图 C. 内部视图 D. 外部视图 3(数据库的概念模型独立于(A)。 A. 具体的机器和DBMS B. E-R图 C. 信息世界 D. 现实世界 4(数据库中，数据的物理独立性是指(C)。 A. 数据库与数据库管理系统的相互独立 B. 用户程序与DBMS的相互独立 C. 用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的 D. 应用程序与数据库中数据的逻辑结构相互独立 5(关系模式的任何属性(A)。 A. 不可再分 B. 可再分 C. 命名在该关系模式中可以不惟一 D.以上都不是 6(下面的两个关系中，职工号和设备号分别为职工关系和设备关系的关键字: 职工(职工号，职工名，部门号，职务，工资) 设备(设备号，职工号，设备名，数量) 两个关系的属性中，存在一个外关键字为( C )。 A. 职工关系的“职工号” B. 职工关系的“设备号” C. 设备关系的“职工号” D. 设备关系的“设备号” 7(以下四个叙述中，哪一个不是对关系模式进行规范化的主要目的( C )。 A. 减少数据冗余 B. 解决更新异常问题 C. 加快查询速度 D. 提高存储空间效率 8(关系模式中各级范式之间的关系为( A )。 A. B. C. D. 9(保护数据库，防止未经授权或不合法的使用造成的数据泄漏、非法更改或破坏。这是指 数据的( A )。 A. 安全性 B.完整性 C.并发控制 D.恢复 10(事务的原子性是指( B )。 A. 事务一旦提交，对数据库的改变是永久的 B. 事务中包括的所有操作要么都做，要么都不做 C. 一个事务内部的操作及使用的数据对并发的其他事务是隔离的 D. 事务必须使数据库从一个一致性状态变到另一个一致性状态 11(下列哪些运算是关系代数的基本运算( D )。 A. 交、并、差 B. 投影、选取、除、联结 C. 联结、自然联结、笛卡尔乘积 D. 投影、选取、笛卡尔乘积、差运算 12(现实世界“特征” 术语, 对应于数据世界的( D )。 A(属性 B. 联系 C. 记录 D. 数据项 13(关系模型中3NF是指( A )。 A.满足2NF且不存在传递依赖现象 B.满足2NF且不存在部分依赖现象 一、单选题（共 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 分 数据库期末考试试题 ━━━━━━━━━━━━━━━ 一、填空共30题（共计30分） ━━━━━━━━━━━━━━━ 第1题（分）题号:2385 ORDER BY 子句实现的是【1】. 答案： =======(答案1)======= 排序 第2题（分）题号:2374 如果列上有约束,要删除该列,应先删除【1】 答案： =======(答案1)======= 相应的约束 第3题（分）题号:2394 在每次访问视图时,视图都是从【1】中提取所包含的行和列. 答案： =======(答案1)======= 基表 第4题（分）题号:2372 1.在增加数据文件时,如果用户没有指明文件组,则系统将该数据文件增加到【1】文件组.答案： =======(答案1)======= 主 第5题（分）题号:2371 查看XSCJ数据库信息的存储过程命令是【1】 答案： =======(答案1)======= sp_helpdb 第6题（分）题号:2392 创建视图定义的T-SQL语句的系统存储过程是【1】. 答案： =======(答案1)======= sp_helptext 第7题（分）题号:2379 1.表的外键约束实现的是数据的【1】完整性. 答案： =======(答案1)======= 参照 第8题（分）题号:2390 要进行模糊匹配查询,需要使用【1】关键字来设置查询条件. 答案： =======(答案1)======= LIKE 第9题（分）题号:2380 定义标识列的关键字是【1】. 答案： =======(答案1)======= identity 第10题（分）题号:2383 在进行多表查询是,必须设置【1】条件. 答案： =======(答案1)======= 连接 第11题（分）题号:2363 联系两个表的关键字称为【1】 答案： =======(答案1)======= 外键 第12题（分）题号:2382 用【1】字句可以实现选择行的运算. 答案： 浙江工业大学 《数据库原理及应用》 一、填空题 1、SELECT Name,Tele FROM Person 的作用是。 2、数据独立性是指数据与应用程序之间不存在相互依赖关系，分为 和。 3、用树型结构表示实体类型及实体间联系的数据模型称为层次模 型。 4、提供数据库定义、数据装入、数据操纵、数据控制和DB维护功能的软件称为 _ 数据管理系统 _。 5、在关系代数中专门的关系运算包括、、、除等。 6、关系数据库的第一范式保证列的原子 性。 7、一个数据库由若干个表组成，关系的元组称为，属性称为。 8 久性。 9、数据字典通常包括数据项、数据结构、数据流、数据存储和处理过程5个部分。 10、并发操作带来的数据不一致性包括三类：丢失覆盖修改、 不可重复读、 读”脏数据。 11、管理信息系统的四种结构模式为：单机模式、、 和。 12、数据管理技术经历了：人工管理阶段、文件管理阶段以及数据库系统阶段 三个发展阶段。 14、实体之间的联系按照联系方式的不同可分为一对一或1:1 、 一对多或1：n 、___ 多对多或m:n 。 15、E-R图中包括__实体、____ 属性和联系三种基 本图素。 16、数据模型由三部分组成：模型结构、数据操作、数据约束条件 。 17、事务必须具有的四个性质是：原子性、一致性、隔离性和持久 性。 18、基本的封锁类型有排它锁和共享锁两种。 19、DB并发操作通常会带来三类问题，它们是丢失修改、不一致分析和读脏数据。 20、数据库系统可能发生的故障有：事务内部的故障系统故障、和介质故障等。计算机病毒 21、按转储时间来分，数据转储可分为静态转储和动态转储两种方式。 22、列举三种管理信息系统开发的方法：结构化开发方法、__原型方 法_ _____、 面向对象方法。 23、一个学生可以同时借阅多本图书，一本图书只能由一个学生借阅，学生和图书之间的联系为一对多联系。 二、判断题 1、关系中允许有重复的元组，但是不允许有重复的属性名。（） 2、关系代数的运算对象是关系，但运算结果不是关系。（） 3、连接操作可以多个表之间进行，也可以在一个表内进行。（） 4、触发器是一种很有效的保证数据库完整性的手段。（） 5、对于关系R、S，如果R-S的元组数是0，则说明R中包含了S的所有元组。 （）6、设关系R、S的元组数分别是20、30，则R和S连接的元组数不可能超过50。 （） 7、数据库中的每一个基本表与外部存储器上一个物理文件对应。（） 8、一个数据库可以有多个外模式和多个内模式。（） 9、概念模型向关系模型转换时，实体间的n：m联系可以有两种转换方法，一 数据库程序设计试题 1一、判断题（每题1分，共10分） 1、DB、DBMS、DBS三者之间的关系是DBS包括DB和DBMS。( ) 2、数据库的概念结构与支持其的DB的DBMS有关。( ) 3、下列式子R∩S=R—（R—S）成立。( ) 4、数据存储结构改变时逻辑结构不变，相应的程序也不变，这是数据库系统的逻辑独立 性。（） 5、关系数据库基本结构是三维表。( ) 6、在嵌入式SQL语句中，主语句向SQL语句提供参数，主要用游标来实现。( ) 7、规范化的投影分解是唯一的。( ) 8、不包含在任何一个候选码中的属性叫做非主属性。( ) 9、在 Transact-SQL 语句的WHERE子句中，完全可以用IN子查询来代替OR逻辑表达式。 （ ) 10、封锁粒度越大，可以同时进行的并发操作越大，系统的并发程度越高。（） 二、填空题(每空0.5分，共10分) 1、两个实体间的联系有联系，联系和联系。 2、select命令中，表达条件表达式用where子句，分组用子句，排序用 子句。 3、数据库运行过程中可能发生的故障有、和三类。 4、在“学生-选课-课程”数据库中的三个关系如下： S(S#，SNAME，SEX，AGE)，SC(S#，C#，GRADE)，C(C#，CNAME，TEACHER)。 现要查找选修“数据库技术”这门课程的学生姓名和成绩，可使用如下的SQL语句：SELECT SNAME,GRADE FROM S,SC,C WHERE CNAME= 数据库技术AND S.S#=SC.S# AND。 5、管理、开发和使用数据库系统的用户主要有、、 。 6、关系模型中可以有三类完整性约束：、 和。 7、并发操作带来数据不一致性包括三类：丢失修改、和。 8、事务应该具有四个属性：原子性、、隔离性和持续性。 9、数据库运行过程中可能发生的故障有事务故障、和三类。 10、在“学生-选课-课程”数据库中的三个关系如下：S(S#，SNAME，SEX，AGE)，SC(S#，C#，GRADE)，C(C#，CNAME，TEACHER)。 现要查找选修“数据库技术”这门课程的学生姓名和成绩，可使用如下的SQL语句：SELECT SNAME,GRADE FROM S,SC,C WHERE CNAME= ‘数据库技术’AND S.S#=SC.S# AND。 11、数据库设计包括、、逻辑结构设计、物理结构设计、数据库实施、数据库运行和维护。 12、MS SQL Server提供多个图形化工具，其中用来启动、停止和暂停SQL Server的图形 化工具称为_________。 13 、SELECT语句中进行查询 , 若希望查询的结果不出现重复元组 , 应在SELECT子 句中使用____________保留字。 14、如果一个关系不满足2NF，则该关系一定也不满足__________(在1NF、2NF、3NF 范围内)。 15、数据库的物理设计主要考虑三方面的问题：______、分配存储空间、实现存取路径。 三、单选题(每题1分，共20 分) 1、在SQL中，关系模式称为（） A、视图 B、对象 C、关系表 D、存储文件 2、要保证数据库逻辑数据独立性，需要修改的是( ) 2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答：C。 9. 以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80, 77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20} 一、单选题（共10 道试题，共50 分。） 1. SQL Server中，保存着每个数据库对象的信息的系统表是（C）。 A. sysdatabases B. Syscolumns C. Sysobjects D. Syslogs 2. 在存在下列关键字的SQL语句中，不可能出现Where子句的是（D）。 A. Update B. Delete C. Insert 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. unique 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的聚集函数COUNT、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. 磁盘 二、判断题（共10 道试题，共50 分。）V 1. 如果定义视图的FROM子句包括多张表，并且视图中列来自多张表，则不能用DML语句通过视图操纵数据。 A. 错误 B. 正确 2. 在sysdatabases中，还记录着存储过程中每个参数的信息。A A. 错误 B. 正确 3. 在SELECT语句中，当使用ORDER BY子句时，一定要使用GROUP BY 子句。A A. 错误 B. 正确 4. 由于索引是独立的，删除表时，与该表相关的索引并不被删除。A A. 错误 B. 正确 5. 日志文件用于存放恢复数据库用的所有日志信息，每个数据库至少拥有一个日志文件，也可以拥有多个日志文件，扩展名ldf B A. 错误 B. 正确 6. 使用INSERT命令一次只能插入一行数据。A A. 错误 B. 正确 一、选择题（每题1分，共20分） 1．在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个阶段中，数据独立性最高的是（ A ）阶段。 A. 数据库系统 B. 文件系统 C. 人工管理 D.数据项管理 2．数据库三级视图，反映了三种不同角度看待数据库的观点，用户眼中的数据库称为（D）。 A. 存储视图 B. 概念视图 C. 内部视图 D. 外部视图 3．数据库的概念模型独立于（A）。 A.具体的机器和DBMS B. E-R图 C. 信息世界 D. 现实世界 4．数据库中，数据的物理独立性是指（C）。 A. 数据库与数据库管理系统的相互独立 B. 用户程序与DBMS的相互独立 C. 用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的 D. 应用程序与数据库中数据的逻辑结构相互独立 5．关系模式的任何属性（A）。 A. 不可再分 B. 可再分 C. 命名在该关系模式中可以不惟一 D.以上都不是 6．下面的两个关系中，职工号和设备号分别为职工关系和设备关系的关键字： 职工（职工号，职工名，部门号，职务，工资） 设备（设备号，职工号，设备名，数量） 两个关系的属性中，存在一个外关键字为（ C ）。 A. 职工关系的“职工号” B. 职工关系的“设备号” C. 设备关系的“职工号” D. 设备关系的“设备号” 7．以下四个叙述中，哪一个不是对关系模式进行规X化的主要目的（ C ）。 A. 减少数据冗余 B. 解决更新异常问题 C. 加快查询速度 D. 提高存储空间效率 8．关系模式中各级X式之间的关系为（ A ）。 A. B. C. D. 9．保护数据库，防止未经授权或不合法的使用造成的数据泄漏、非法更改或破坏。这是指数据的（ A ）。 A. 安全性 B.完整性 C.并发控制 D.恢复 10．事务的原子性是指（ B ）。 A. 事务一旦提交，对数据库的改变是永久的 B. 事务中包括的所有操作要么都做，要么都不做 C. 一个事务内部的操作及使用的数据对并发的其他事务是隔离的 D. 事务必须使数据库从一个一致性状态变到另一个一致性状态 11．下列哪些运算是关系代数的基本运算（ D ）。 A. 交、并、差 B. 投影、选取、除、联结 C. 联结、自然联结、笛卡尔乘积 D. 投影、选取、笛卡尔乘积、差运算 《数据结构》试题（100分） （供2005级信息管理与信息系统本科专业使用） 学号： 姓名： 座号： 系别： 年级： 专业： 总分合计人： 复核人： 说明：本试卷分为两部分，第I 卷（选择题和判断题）必须在“答题卡”上按规定要求填、涂；第II 卷直接在试卷上作答。不按规定答题、填涂，一律无效。 第I 卷 一、试题类型：单项选择题（每小题2分，共40分） （类型说明：在每小题列出的四个选项中只有一个选项是符合题目要求的，请选出正确选项并在“答题卡”的相应位置上涂黑。多涂、少涂、错误均无分。） 1. 算法分析的两个主要方面是： （ ） （A) 空间复杂性和时间复杂性 （B) 正确性和简明性 （C) 可读性和文档性 （D) 数据复杂性和程序复杂性 2. 计算机算法指的是： （ ） （A) 计算方法 （B) 排序方法 （C) 解决问题的有限运算序列 （D) 调度方法 3． 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为：（ ） （A ）存储结构 （B ）逻辑结构 （C ）顺序存储结构 （D ）链式存储结构 4.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。 （ ） （A ）110 （B ）108 （C ）100 （D ）120 5. 链接存储的存储结构所占存储空间： （ ） （A ）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B ）只有一部分，存放结点值 （C ） 只有一部分，存储表示结点间关系的指针 （D ） 分两部分，一部分存放结点值，另一部分存放结点所占单元数 6. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （ ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 江西农业大学2013—2014学年第一学期期末考试试卷（A ） 课程名称：数据库原理及应用 开课单位：软件学院 考试方式：闭卷 使用专业：软件工程 考试日期： 考试时间：120分钟 卷和答题纸交给监考老师。 一大题：选择题（共10小题，每小题2分，共20分） 1、在数据库中，下列说法（ ）是不正确的。 A. 数据库避免了一切数据的重复 B. 若系统是完全可以控制的，则系统可确保更新时的一致性 C. 数据库中的数据可以共享 D. 数据库减少了数据冗余 2、对数据库物理存储方式的描述称为（ ） A ．外模式 （子模式、用户模式） B ．内模式 C ．概念模式 D ．逻辑模式（模式） 3、在数据库三级模式间引入二级映象的主要作用是（ ） A ．提高数据与程序的独立性 B ．提高数据与程序的安全性 C ．保持数据与程序的一致性 D ．提高数据与程序的可移植性 4、概念模型最常用的描述方法是（ ）。 A. E-R 模型 B. 关系模型 C. 层次模型 D. 网状模型 5、图是一个“虚表”，视图的构造基于（ ） A ．基本表 B ．视图 C ．基本表或视图 D ．数据字典 6、关系代数中的笛卡尔积运算对应SELECT 语句中的以下哪个子句？ （ ） A ．SELECT B ．FROM C ．WHERE D ．GROUP BY 7、关系运算中花费时间可能最长的运算是（ ） A. 投影 B. 选择 C. 笛卡尔积 D. 除 8、事务日志的用途是（ ） A. 事务处理 B. 完整性约束 C. 数据恢复 D. 安全性控制 9、用于实现数据存取安全性的SQL 语句是（ ） A. CREATE TABLE B. COMMIT C. GRANT 和REVOKE D. ROLLBACK 10、如果事务T 已在数据R 上加了X 锁，则其他事务在数据R 上（ ） A.只可加X 锁 B. 只可加S 锁 C. 可加S 锁或X 锁 D. 不能加任何锁 二大题：填空题（共5小题，每空1分，共10分） 1、数据管理技术经历了_______、_______和_______三个阶段。 2、自然连接运算是由_______、_______和_______运算组成。 院系： 专业班级： 姓名： 学号： 装 订 线 数据结构复习题 一、单选题(每小题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}； 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)数据库期末复习试卷及答案一
数据库期中试卷及参考答案
2017年数据结构期末考试题及答案A
中南大学oracle数据库期末考试试题及答案
数据库期末考试试题及答案
sql数据库期末考试题及答案
数据库期末考试试题及答案
数据库期末试卷
数据库期末试卷和答案
数据结构期末考试试题含答案
sql数据库期末考试题及答案
数据库期末考试试题及答案
数据结构期末考试试题答案详解
数据结构期末考试试题及答案资料
数据库期末试卷A(含答案)
大学数据结构期末考试试题(有答案)
sql数据库期末考试题及答案
相关主题
文本预览