武汉理工大学数据结构考试试题

武汉理工大学数据库期末考试试题06级武汉理工大学数据库期末考试试题06级武汉理工大学考试试题纸( B 卷)课程名称题号一二20 数据库与信息系统三15 四50 五六七专业班级信息0601-04 八九十总分100题分15备注: 学生不得在试题纸上答题(含填空题、选择题等客观题)一、填空题(每空1 分，共15 分)1. 数据库的数据模式由_____ 和____ 内模式三级模式构成。

2. E―R 模型的组成要素包括：实体、_____、联系。

3. 假设一个学生只属于一个班级，则班级和学生之间是____ 联系；学生可以同时修多门课程，学生和课程之间是____ 联系。

4. 关系模式的三类完整性约束分别是____、____ 和____ 约束。

5. SQL Server 主数据文件和事务日志文件默认的扩展名分别为____、____ 。

6.T-SQL 语言使用__create trigger__ 语句建立触发器。

7. 2NF 的关系模式转变为3NF 的关系模式，将是消除了非主属性对码的___传递函数依赖__ 。

8. 集合R 交S 的并表示为_____ 。

9.SQL 语句分为：数据定义语句、_数据操纵语言DML____ 和数据控制语句。

10.删除视图的SQL 命令是____DROP VIEW_ 。

二、单项选择题(本大题共20 小题，每小题 1 分，共20 分)1. DBMS 能实现对数据的查询、插入、修改和删除等操作，这种功能称为( A. 数据定义功能 B. 数据管理功能 C. 数据控制功能 D. 数据操纵功能 2. 下列四项中说法不正确的是( ) A. 数据库减少了数据冗余数据库减少了数据冗余 B. 数据库中的数据可以共享 C. 数据库避免了一切数据的重复 D. 数据库具有较高的数据独立性 3. ( )由数据结构、关系操作集合和完整性约束三部分组成。

A. 关系模型 B. 关系 C. 关系模式 D. 关系数据库 4. 在数据库的E-R 图中，方框表达的是( ) A. 属性 B. 实体C. 实体之间的联系D. 实体与属性之间的联系)武汉理工大学数据库期末考试试题06级5. 现有关系表：选课(学号，姓名，所在系，课程号，课程名，成绩)的主码是( ) A. 学号，课程号 B. 学号学号，C. 课程号 D. 姓名，课程名6. 在关系数据库中，表与表之间的联系是通过( )实现的。

武汉理工大学教务处试题标准答案及评分标准用纸课程名称数据结构（A 卷）一、判断题（每小题2分，共20分）1、对2、对3、错4、对5、对6、对7、错8、对9、错10、对装二、选择题（每小题3分，共15分）1、B2、C3、B4、A5、D三、填空题（每小题3分，共21分）1、n-12、p->prior->next=p->next; p->next->prior=p->prior;3、334、中序5、n(n-1)6、(n+1)/2 或3(n+1)/47、CEF四、应用题（（每小题9分，共36分）1、(1)将数组中的负数调到非负数之前……………3分(2)只需对数组扫描一遍即可，故时间复杂度为O(n) ……………6分(3)最坏情况下：负数都位于非负数之后，需将负数与非负数对换，故记录的最大移动次数为n /2 ……………9分订2、中序遍历：LDR 后序遍历：LRD ……………2分由中序遍历和后序遍历一致，则应该是LD，任一个结点没有右孩子……………5分………………………9分线3、32%7=4，13%7=6，49%7=0，55%7=6，22%7=1，38%7=3，21%7=0 ……………2分哈希表为：495522383221130123456……………5分查找32，13，49，38需比较一次，查找22需比较两次，查找55需比较3次，查找21需比较6次……………8分故平均查找长度为：（1*4+2*1+3*1+6*1）/7=15/7 ……………9分4、排序算法主要有简单排序、快速排序、堆排序、归并排序、基数排序。

…………1分(1)从平均性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。

……………3分(2)“简单排序”包括除希尔排序之外的所有插入排序，起泡排序和简单排序，其中直接插入排序最简单，当序列中的记录“基本有序”或n较小时，它是最佳排序方法，因此常将它和其他的排序方法，诸如快速排序、归并排序等结合在一起使用。

一、选择题（答案不唯一可多选，26分，每空2分）1．下列各项中属于逻辑结构的有。

A. 哈希表B. 有序表C. 单链表D. 顺序表2．由3个结点组成的二叉树的深度可能是。

A．1 B.2 C.3 D.43．将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][64]在B数组中的位置k等于。

A．198 B.197 C.196 D.1954．一棵满二叉树同时又是一棵。

A. 完全二叉树B. 二叉排序树C . 正则二叉树D. 平衡二叉树5．长度为n的顺序表，在任何位置上插入或删除一个元素的概率相等，插入一个元素时平均移动个元素，删除一个元素时平均移动个元素。

A．（n+1）/2 B.n/2 C.(n-1)/2 D.(n-2)/26. 用s表示入栈操作，*表示出栈操作，栈的初态、终态均为空，入栈和出栈的操作序列可表示成仅为由s 和*组成的序列。

下面的序列中合法的操作序列有。

A．s*ss*s** B.sss**s** C. s**s*ss* D.sss*s*s*7. 是特殊的线性表。

A．队列B.哈希表C.栈D.判定表8. 表长为25的哈希表，用除留余数法公式H(key)=key % p 或H(key)=key mod p，则p应取为宜。

A.23B.24C.25D.269．任一个有向图的拓扑序列。

A.可能不存在B.有一个C. 一定有多个D.有一个可多个10．在下列的排序方法中，方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。

A.快速排序B. 冒泡排序C.堆排序D. 插入排序11．若以{4,5,6,7,8}作为权值构造Huffmen树，则该树的带权路径长度为。

A.67B.68C.69D.7012．设head(L)、tail()分别为取广义表表头和表尾的操作，则从广义表L=((x,y,z),a,(u,v,w))中取出原子u 的运算为。

A.head(tail(tail(head(L))))B.tail(head(head(tail(L))))C.head(tail(head(taill(L))))D.head(head(tail(tail(L))))二、填空题（共32分，每空2分）13．在单链表中设置头结点和作用是__________________ 。

数据结构（本科）武汉理工大学在线作业一、判断(共计40分,每题2.5分)1、快速排序是排序算法中平均性能最好的一种排序。

（）A. 正确B. 错误答案:【A】2、调用一次深度优先遍历可以访问到图中的所有顶点。

（）A. 正确B. 错误答案:【B】3、对连通图进行深度优先遍历可以访问到该图中的所有顶点。

（）A. 正确B. 错误答案:【A】4、线性表中的所有元素都有一个前驱元素和后继元素。

（）A. 正确B. 错误答案:【B】5、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（）A. 正确B. 错误答案:【B】6、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。

（）A. 正确B. 错误答案:【A】7、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。

（）A. 正确B. 错误答案:【A】8、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

（）B. 错误答案:【A】9、子串“ABC”在主串“AABCABCD”中的位置为2。

( )A. 正确B. 错误答案:【A】10、非空的双向循环链表中任何结点的前驱指针均不为空。

（）A. 正确B. 错误答案:【A】11、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

（）A. 正确B. 错误答案:【A】12、线性表的顺序存储结构比链式存储结构更好。

（）A. 正确B. 错误答案:【B】13、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。

（）A. 正确B. 错误答案:【B】14、层次遍历初始堆可以得到一个有序的序列。

（）A. 正确B. 错误答案:【B】15、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

（）A. 正确B. 错误答案:【A】16、设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。

（）A. 正确B. 错误二、单选(共计60分,每题2.5分)17、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。

数据结构考试试题题库一、选择题1. 在数据结构中，线性表是按照什么顺序存储数据的？A. 随机B. 无序C. 有序D. 连续2. 栈（Stack）是一种遵循哪种原则的数据结构？A. 先进先出（FIFO）B. 先进后出（LIFO）C. 后进先出（LILO）D. 随机访问3. 哈希表（Hash Table）的主要优点是什么？A. 存储空间大B. 访问速度快C. 易于排序D. 易于扩展二、简答题1. 请简述数组和链表的区别。

2. 什么是二叉树？请描述二叉树的几种遍历方法。

三、计算题1. 给定一个单链表，编写一个算法来删除链表中的重复元素。

2. 假设有一个数组，其中包含n个元素，编写一个算法来找到数组中的第k小的元素。

四、应用题1. 描述如何使用队列来实现一个打印任务调度系统。

2. 请解释二叉搜索树（BST）的插入操作，并给出相应的算法实现。

五、编程题1. 编写一个C++函数，实现对一个给定的整数数组进行排序。

2. 编写一个Python函数，实现对一个二叉树进行层次遍历。

六、论述题1. 讨论图的两种存储结构：邻接矩阵和邻接表，并比较它们的优缺点。

2. 解释什么是递归，并给出一个使用递归解决实际问题的例子。

结束语数据结构的学习不仅仅是对概念的理解，更重要的是能够将这些概念应用到实际问题的解决中。

通过本题库的练习，希望能够加深你对数据结构的理解和应用能力。

请注意，这只是一个示例题库，实际的考试题库可能会包含更多的题目和不同的题型。

考生应根据具体的课程内容和考试要求来准备。

数据结构题库及答案详解一、选择题1. 在数据结构中，线性结构的特点是什么？A. 结构中存在唯一的开始结点和终端结点B. 结构中所有结点的前驱和后继都存在C. 结构中所有结点都只有一个直接前驱和一个直接后继D. 结构中存在多个开始结点和终端结点答案：C2. 栈是一种特殊的线性表，其特点是：A. 先进先出B. 先进后出C. 可以同时在两端进行插入和删除操作D. 只能在一端进行插入和删除操作答案：D3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根结点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根结点，最后遍历右子树C. 先遍历右子树，然后访问根结点，最后遍历左子树D. 先遍历左右子树，最后访问根结点答案：A二、填空题4. 在图的遍历中，______算法可以避免重复访问同一顶点。

5. 哈希表的冲突可以通过______方法来解决。

答案：4. 深度优先搜索（DFS）5. 链地址法或开放地址法三、简答题6. 简述排序算法中的快速排序算法的基本原理。

答案：快速排序算法是一种分治算法，它通过选择一个元素作为“基准”，然后将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。

然后对这两个子数组递归地应用快速排序算法。

7. 解释什么是递归，并给出一个递归函数的例子。

答案：递归是一种在函数中调用自身的编程技术。

递归函数必须有一个明确的终止条件，以避免无限递归。

例如，计算阶乘的递归函数如下：```int factorial(int n) {if (n == 0) return 1; // 终止条件return n * factorial(n - 1); // 递归调用}```四、编程题8. 编写一个函数，实现单链表的反转。

答案：```c// 假设ListNode是链表节点的定义ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;ListNode* next = NULL;while (curr != NULL) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转指针prev = curr; // 移动prevcurr = next; // 移动curr}return prev; // 新的头节点}```9. 给定一个整数数组，请实现一个函数来找到数组中的最长连续子序列的长度。

1. 不含任何结点的空树（ C ）。

A．是一棵树B. 是一棵二叉树C. 是一棵树也是一棵二叉树D. 既不是树也不是二叉树2. 如果结点A有3个兄弟，B是A的双亲，则B的度是（ D）A．1B. 2C. 3D. 43.二叉树是非线性数据结构，所以（ C）。

A．它不能用顺序存储结构存储B. 它不能用链式存储结构存储C. 顺序存储结构和链式存储结构都能存储D. 顺序存储结构和链式存储结构都不能使用4.由3 个结点可以构造出多少种不同的二叉树？（D ）。

A．2B. 3C. 4D. 55. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ D ）A．250B.500C. 254D. 5016．一个具有1025个结点的二叉树的高h为（ C ）。

A．10B．11C．11至1025之间D．10至1024之间7．把一棵树转换为二叉树后，这棵二叉树的形态是（A ）。

A．唯一的B. 有多种C. 有多种，但根结点都没有左孩子D. 有多种，但根结点都没有右孩子8．深度为h的满m叉树的第k层有（ A）个结点。

(1=<k=<h)A．m的k-1次方B. m的k次方减1C. m的h-1次方D. m的h次方减19．利用二叉链表存储树，则根结点的右指针是（ C ）A．指向最左孩子B. 指向最右孩子C. 空D. 非空10．具有n(n>0)个结点的完全二叉树的深度为（ C ）A．é以2为底n的对数向上取整ùB．以2为底n的对数向下取整C．以2为底n的对数向下取整+1D．以2为底n+1的对数向上取整11．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（C ）遍历实现编号。

A. 先序B. 中序C. 后序D. 从根开始按层次遍历12．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（C ）遍历方法最合适。

8．（）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶子结点”上。

3、填空（每小题2分，共14分）1．在单链表中，删除指针P所指结点的后继结点的语句是（）。

2．已知完全二叉树的第八层有8个结点，则其叶子结点数是（）。

3．有n个顶点的强连通有向图G至少有（）条弧。

4．求最短路径的DIJKSTRA算法的时间复杂度为（）。

5．在有序表A[1，20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元素的下标依次为（）。

6．直接选择排序算法所执行的元素交换次数最多为（）。

7．下列排序算法中，稳定的排序算法是（）（选择排序，堆排序，快速排序，直接插入排序）。

4、解答下列各题(38分)1．一棵二叉树的先序序列和中序序列分别如下，画出该二叉树。

(6分)先序序列ABCDEFGHIJ中序序列CBEDAGHFJI2．对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。

(8分)4， 5， 6， 7， 10， 12， 15， 18， 233．图G的邻接表如下，完成下列各题：(8分)(1)画出从顶点5出发进行广度遍历所生成的生成树。

(2)判断其中是否存在有向回路，若不存在，求出其拓扑序列。

13225436749859108611712899101011111212^4．对下列数据表，写出采用快速排序算法排序的每一趟的结果。

(8分)(60，20，31，1，5，44，55，61，200，30，80，150，4，29)5．已知哈希表地址空间为0．．8，哈希函数为H(k)=k % 7，采用线性探查法处理冲突。

将下面数据序列依次存入该散列表中，并求出在等概率下的平均查找长度。

(8分)100，20，21，35，3，78，99，450 1 2 3 4 5 6 7 85、算法设计(共30分)1．已知单循环链表L中至少有两个结点，每个结点的两个字段为data和next，其中字段data的类型为整型。

数据结构试卷（一）一、单选题（每题 2 分，共20分）1.栈和队列的共同特点是( A )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).k-1A．2k-1 B.2K+1 C.2K-1 D. 27.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：__ _、__ _____、______和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_____。