青岛理工大学数据结构复习题2期末试题及参考答案

2022年青岛理工大学软件工程专业《数据库原理》科目期末试卷B（有答案）一、填空题1、数据管理技术经历了______________、______________和______________3个阶段。

2、关系数据库中基于数学的两类运算是______________和______________。

3、关系代数运算中，基本的运算是______________、______________、______________、______________和______________。

4、在SELECT命令中进行查询，若希望查询的结果不出现重复元组，应在SEL ECT语句中使用______保留字。

5、关系系统的查询优化既是关系数据库管理系统实现的关键技术，又是关系系统的优点。

因为，用户只要提出______，不必指出 ______。

6、数据的安全性是指____________。

7、设在SQL Server 2000环境下，对“销售数据库”进行的备份操作序列如下图所示。

①出现故障后，为尽可能减少数据丢失，需要利用备份数据进行恢复。

首先应该进行的恢复操作是恢复_____，第二个应该进行的恢复操作是恢复_____。

②假设这些备份操作均是在BK设备上完成的，并且该备份设备只用于这些备份操作，请补全下述恢复数据库完全备份的语句RESTORE_____FROM BKWITH FILE＝1，_____；8、已知系（系编号，系名称，系主任，电话，地点）和学生（学号，姓名，性别，入学日期，专业，系编号）两个关系，系关系的主码是______________，系关系的外码是______________，学生关系的主码是______________，外码是______________。

9、数据库恢复是将数据库从______状态恢复到______的功能。

10、关系模型由______________、______________和______________组成。

一、单项选择题（在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

）1.C++对C语言作了很多改进，即从面向过程变成为面向对象的主要原因是（）A.增加了一些新的运算符B.允许函数重载，并允许设置缺省参数C.规定函数说明符必须用原型D.引进了类和对象的概念2•下列符号不能组成标识符的是（）A.连接符B.下划线C.大小写字母D.数字字符3.类型修饰符unsigned不能修饰（）A.charB. intC. long intD. float4.在int a=3,int *p=&a；中，*p 的值是（）A.变量a的地址值B.无意义C.变量p的地址值D.35•下列关于指针的操作中，错误的是（）A.两个同类型的指针可以进行比较运算B.可以用一个空指针赋给某个指针C.一个指针可以加上两个整数之差D.两个同类型的指针可以相加6•重载函数在调用时选择的依据中，错误的是（）A.函数的参数B.参数的类型C.函数的名字D.函数的类型7.—个函数功能不太复杂，但要求被频繁调用，选用（）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.删除对象创建的所有对象13•类的析构函数是在（）调用的。

A.类创建时B.创建对象时C.删除对象时D.不自动调用14.在（）情况下适宜采用inline定义内联函数。

A.函数体含有循环语句B.函数体含有递归语句C.函数代码少、频繁调用D.函数代码多、不常调用15•如果类A被说明成类B的友元，贝!］（）A.类A的成员即类:B的成员B.类B的成员即类A的成员C.类A的成员函数不得访问类:B的成员D.类B不一定是类A的友元16•在类中声明转换函数时不能指定（）A.参数B.访问权限C.操作D.标识符17•在公有继承的情况下，基类成员在派生类中的访问权限（）A.受限制 B.保持不变18.C++类体系中，不能被派生类继承的有()A.转换函数B.构造函数C.虚函数D.静态成员函数19•假定AB为一个类，则执行ABx；语句时将自动调用该类的() A.有参构造函数 B.无参构造函数C.拷贝构造函数D.赋值构造函数20.C++语言建立类族是通过()A.类的嵌套B.类的继承C.虚函数D.抽象类答案如下：l. D 2.A 3.D 4.D 5.D6.A 7.A &C 9.D 10.C11.C 12.C 13.D 14.C 15.D16.C17.B 18.C 19.B 20.B二•下面的每小题有一个或多个答案是正确的，请选出正确选项并将其填入相应括号内。

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。

数据结构期末考试试题(含答案)C.{100,98,85,77,80,60,82,40,20,10,66} 答：C。

10.在哈夫曼编码中，若有n个字符，其权值分别为w1，w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编码的平均长度为a。

A.∑(wi/2li)B.∑(wi/li)C.∑(wi/2li-1)D.∑(wi/li-1)答：A。

2005-2006学年第二学期“数据结构”考试试题（A）要求：所有的题目的解答均写在答题纸上。

每张答题纸上需写清楚姓名、班号和学号，并在上面写上题目的序号。

一、单项选择题（每小题2分，共20分）1.数据的运算效率与采用何种存储结构有关。

因此，选项A是正确答案。

2.链表不具备的特点是可随机访问任一结点。

参见本节要点3.因此，选项A是正确答案。

3.在顺序表中删除一个元素的时间复杂度为O(n)。

因此，选项C是正确答案。

4.具有随机存取功能的线性表存储结构是顺序表。

因此，选项D是正确答案。

5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是dceab。

因此，选项C是正确答案。

6.循环队列qu的队空条件是qu.rear==qu.front。

因此，选项D是正确答案。

7.两个串相等必有串长度相等且串中各位置字符均对应相等。

因此，选项B是正确答案。

8.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是21,32,46,40,80,69,90,94.因此，选项C是正确答案。

9.以下序列不是堆（大根或小根）的是{100,98,85,77,80,60,82,40,20,10,66}。

因此，选项C是正确答案。

10.在哈夫曼编码中，若有n个字符，其权值分别为w1，w2，…，wn，编码长度分别为l1，l2，…，ln，则哈夫曼编码的平均长度为∑(wi/2li)。

因此，选项A是正确答案。

C。

{10.20.40.60.66.77.80.82.85.98.100}D。

“数据结构”期末考试试题一、单选题(每小题2分，共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。

A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． 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．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

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．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。

1.数据的最小单位是（）。

A．数据项B．数据类型C．数据元素D．数据变量2.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。

编号为49的结点X的双亲编号为（）A.24B.25C.23D.无法确定3.一个具有n个顶点的无向完全图的边数为（）A.n(n+1)/2B.n(n-1)/2C.n(n-1)D.n(n+1)4. 设二维数组A[6][10],每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是（）A. 1000B. 860C. 1140D.12005.关键路径是事件结点网络中（）A.最短的回路B.最长的回路C.从开始结点到完成结点的最短路径D.从开始结点到完成结点的最长路径6.判断一个循环队列Q（最多元素为m）为满队列的条件是（）A.Q->front==Q->rearB. Q->front!=Q->rearC. Q->front==(Q->rear+1)%mD. Q->front!=(Q->rear+1)%m7. 栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点8. 广义表((a),a)的表尾是（）。

A.aB.((a),a)C.(a)D.（（a））9.下面程序段的时间复杂度为（）for (int i=0;i<n;i++)for (int j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)10.设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。

若想删除链表第一个结点（首元结点），则应执行下列哪一个操作（）A.s=rear; rear=rear->link; delete s;B.rear=rear->link; delete rear;C.rear=rear->link->link; delete rear; D s=rear->link->link; rear->link->link=s->link; delete s;11.输入序列为ABC，可以变为CBA时，经过的栈操作为（）A. push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop12.已知一个图，若从顶点a 出发按深度优先进行遍历，则可能得到的一种顶点序列为（）(1) A.abecdf B.acfebd C.aebcfd D.aedfcb(2) A.abcedf B.abcefd C.aebcfd D.acfdeb二、填空题（每空2 分，共16分）1.数据的逻辑结构被分为两大类。

2022年青岛理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈3、线性表的顺序存储结构是一种（）。

A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。

《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪种数据结构是线性结构？A. 栈B. 树C. 队列D. 图答案：A2. 在计算机科学中，什么是最基本的数据结构？A. 数组B. 链表C. 栈D. 树答案：C3. 下列哪种操作的时间复杂度是O(1)?A. 在链表中插入元素B. 在数组中查找元素C. 在树中删除节点D. 在图中寻找最短路径答案：B4. 下列哪种数据结构常常用于实现栈和队列？A. 数组B. 链表C. 树D. 图答案：A5. 下列哪种数据结构是有序的？A. 栈B. 队列C. 链表D. 图答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种后进先出（____）的数据结构。

答案：线性表2. 队列是一种先进先出（____）的数据结构。

答案：线性表3. 链表是一种____数据结构，由一系列节点组成。

答案：非线性4. 二叉树是一种特殊的树，它的每个节点最多有两个____。

答案：子节点5. 哈希表是通过____函数将关键字映射到表中的位置来访问数据。

答案：哈希三、判断题（每题2分，共20分）1. 树是一种线性结构。

（）答案：错误2. 链表的插入和删除操作时间复杂度都是O(1)。

（）答案：错误3. 图是一种线性结构。

（）答案：错误4. 哈希表是一种基于顺序结构的的数据结构。

（）答案：错误5. 在数据结构中，时间复杂度O(n)表示算法随着输入规模的增加而线性增长。

（）答案：正确四、简答题（每题10分，共30分）1. 请简述栈和队列的特点和应用场景。

答案：栈是一种后进先出（LIFO）的数据结构，应用场景包括函数调用栈、表达式求值等。

队列是一种先进先出（FIFO）的数据结构，应用场景包括任务队列、缓冲区等。

2. 请简述链表的优缺点。

答案：链表的优点包括动态扩容、插入和删除操作时间复杂度为O(1)、可以方便地实现各种复杂数据结构。

缺点包括占用内存空间较大、不如数组支持随机访问。

2022年青岛理工大学信息管理与信息系统专业《数据库概论》科目期末试卷B（有答案）一、填空题1、数据模型是由______________、______________和______________三部分组成。

2、安全性控制的一般方法有____________、____________、____________、和____________视图的保护五级安全措施。

3、如图所示的关系R的候选码为；R中的函数依赖有；R属于范式。

一个关系R4、某事务从账户A转出资金并向账户B转入资金，此操作要么全做，要么全不做，为了保证该操作的完整，需要利用到事务性质中的_____性。

5、“为哪些表，在哪些字段上，建立什么样的索引”这一设计内容应该属于数据库设计中的______阶段。

6、在SQL Server 2000中，新建了一个SQL Server身份验证模式的登录账户LOG，现希望LOG在数据库服务器上具有全部的操作权限，下述语句是为LOG授权的语句，请补全该语句。

EXEC sp_addsrvrolemember‘LOG’，_____；7、数据库系统在运行过程中，可能会发生各种故障，其故障对数据库的影响总结起来有两类：______和______。

8、在SQL语言中，为了数据库的安全性，设置了对数据的存取进行控制的语句，对用户授权使用____________语句，收回所授的权限使用____________语句。

9、关系代数运算中，基本的运算是______________、______________、______________、______________和______________。

10、____________和____________一起组成了安全性子系统。

二、判断题11、在一个关系中，不同的列可以对应同一个域，但必须具有不同的列名。

（）12、文件系统的缺点是数据不能长期存储。

（）13、一个关系中不可能出现两个完全相同的元组是由实体完整性规则确定的。