下载文档原格式
武汉理工大学数据库期末考试试题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，其数量级表示为_____。
一、计算( 每题参考分值5分)1、用一台60MHZ处理机执行标准测试程序，程序所含的混合指令数和每类指令的CPI如表所示，求有效CPI、MIPS 速率和程序的执行时间。
正确答案：解：总的指令数为：45000+35000+15000+15000=100000条，因此各类指令所占的比例分别是：整数运算为45%，数据传送为25%，浮点操作为15%，控制传送为15%。
有效CPI、MIPS速率和程序的执行时间分别计算如下：(1)有效CPI为：1×0.45+2×0.25+4×0.15+2×0.15=1.85CPI (2)MIPS速率为:1/1.85×60=32.43MIPS (3)程序的执行时间为：100000×1.85/(60×106)=0.003083s=3083us2、用一台50MHZ处理机执行标准测试程序，程序所含的混合指令数和每类指令的CPI如表所示，求有效CPI、MIPS 速率和程序的执行时间。
正确答案：解：总的指令数为：5000+3000+1000+1000=10000条，因此各类指令所占的比例分别是：整数运算为50%，数据传送为30%，浮点操作为10%，控制传送为10%。
有效CPI、MIPS速率和程序的执行时间分别计算如下：(1)有效CPI为：1×0.5+2×0.3+3×0.1+2×0.1=1.6CPI (2)MIPS速率为:1/1.6×50=31.325MIPS (3)程序的执行时间为：10000×1.6/(50×106)=0.00032s=320us3、用一台40MHZ处理机执行标准测试程序，程序所含的混合指令数和每类指令的CPI如表所示，求有效CPI、MIPS 速率和程序的执行时间。
正确答案：解：总的指令数为：45000+32000+15000+8000=100000条，因此各类指令所的比例分别是：整数运算为45%，数据传送为32%，浮点操作为15%，送为8%。
《852数据结构真题》2002年数据结构研究生入学考试试题一．选择题（30分，每空2分。
答案可能不唯一）1．算法在发生非法操作时可以作出处理的特性称为。
①正确性②可读性③键状性④可靠性2．指针p所指的元素是双向链表L的尾元素的条件是 A 。
若队列采用链式存储，则该链式队列 B 。
A：① p==L ② p==NULL ③ p->Llink==L ④p->Rlink==LB：①存在队满的情况②不存在队空的情况③入队之前必须判断队满否④出队之前必须判断队空否3．二叉排序树是：。
①中序遍历得到一升序序列的二叉树②每一分支结点的度均为2的二叉树③按层次从左到右顺序编号的二叉树④每一分支结点的值均小于其右子树上所有结点的值（若右子树存在），又大于其左子树上所有结点的值（若左子树存在）4．三对角矩阵a[1…n][1…n]以行为主序顺序存储，其存储始址是b，每个元素占一个存储单元，则元素a[i][j]的存储始址为。
①b+2*j+i-2 ② b+2*i+j-2 ③ b+2*j+i-3 ④ b+2*i+j-35．已知一棵二叉树的前序序列和中序序列分别是GFDBHCEA和DFHBGCAE，则该二叉树的后序序列为 A ，层次序列为 B ，若由森林转化得到的二叉树是非空的二叉树，则该二叉树是 C ，如果满足条件 D ，线索二叉树中结点p无右孩子。
A、B：① DBHFEACG ② GFCDBEHA ③ DHBFAECG ④ DFGBCEHAC：①根结点无右子树②根结点可能有左子树和右子树③根结点无左子树④各结点只有一个孩子D：①p->rchild==NULL ②p->rtag==1 p->rtag==0 ④p->rtag==NULL6.一个加权连通无向图的最小生成树可以使用 A 生成。
一项工程完工所需的最少时间等于某个 BA：① Hash算法② Dijstra算法③ prim算法④ Huffman算法B：① AOE网中源点到汇点事件最多的路径的长度②AOE网中源点到汇点的最长路径的长度③AOE网中源点到汇点的最短路径的长度④AOE网中源点到汇点活动最多的路径的长度7.用冒泡排序的方法对n个记录进行排序，第一趟共要比较 A对元素。
数据结构试题库及答案一、选择题1. 在数据结构中，线性结构的特点是：A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系答案：A2. 栈（Stack）是一种特殊的线性表，其特点是：A. 只能在一端进行插入和删除操作B. 可以在两端进行插入和删除操作C. 只能在一端进行插入操作，另一端进行删除操作D. 可以在任意位置进行插入和删除操作答案：A3. 在二叉树中，度为1的节点数目为2，度为0的节点数目也为2，该二叉树的节点总数是：A. 5B. 6C. 7D. 8答案：B二、简答题1. 请简述什么是哈希表，并说明其主要优点。
答案：哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。
其主要优点包括：平均情况下，查找、插入和删除操作的时间复杂度为O(1)，即常数时间内完成操作；空间效率高，能够存储大量数据。
2. 描述图的深度优先搜索（DFS）算法的基本思想。
答案：深度优先搜索算法的基本思想是从一个顶点开始，尽可能深地搜索图的分支。
搜索过程中使用一个栈来保存路径上的顶点。
当搜索到一个顶点时，先访问该顶点，然后依次搜索其所有未被访问过的邻接顶点。
如果当前顶点的所有邻接顶点都被访问过，则回溯到上一个顶点，继续搜索其他邻接顶点。
三、应用题1. 给定一个无向图，使用邻接表表示，请编写一个算法找出图中的所有连通分量。
答案：首先，创建一个访问过的顶点集合。
然后，从图中任意一个未被访问的顶点开始，执行深度优先搜索（DFS）。
每次DFS完成后，就找到了一个连通分量。
重复这个过程，直到所有顶点都被访问过，即可找到图中的所有连通分量。
2. 假设有一个数组，需要频繁地进行查找、插入和删除操作，请设计一个适合这种场景的数据结构，并说明其优势。
答案：对于这种场景，可以使用平衡二叉搜索树（如AVL树或红黑树）。
这些数据结构可以保证在最坏情况下，查找、插入和删除操作的时间复杂度为O(log n)。
2022年武昌理工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。
A.5B.6C.8D.92、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。
A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12116、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、设X是树T中的一个非根结点，B是T所对应的二叉树。
复习题集一判断题（×）1．线性表在物理存储空间中也一定是连续的。
（×）2．顺序存储方式只能用于存储线性结构。
（√）3．栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（√）4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（×）5．二叉树的度为2。
（√）6．若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）7．二叉树中每个结点的两棵子树的高度差等于1。
（√）8．用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（）9．在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。
（）10．计算机处理的对象可以分为数据和非数据两大类。
（）11．数据的逻辑结构与各数据元素在计算机中如何存储有关。
（）12．算法必须用程序语言来书写。
（）13．判断某个算法是否容易阅读是算法分析的任务之一。
（）14．顺序表是一种有序的线性表。
（）15．分配给顺序表的内存单元地址必须是连续的。
（）16．栈和队列具有相同的逻辑特性。
（）18．树形结构中每个结点至多有一个前驱。
（）19．在树形结构中，处于同一层上的各结点之间都存在兄弟关系。
（）20．如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。
（）21．如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。
（）22．顺序查找方法只能在顺序存储结构上进行。
（）23．折半查找可以在有序的双向链表上进行。
（）24．满二叉树中不存在度为1的结点。
（）25．完全二叉树中的每个结点或者没有孩子或者有两个孩子。
（）26．对n个元素知心快速排序，在进行第一次分组时，排序码的比较次数总是n-1次。
（）27．在有向图中，各顶点的入度之和等于各顶点的出度之和。
一、选择题（）1. 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：A) 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）C) 删除第i个结点（1≤i≤n）B) 在第i个结点后插入一个新结点（1≤i≤n）D) 将n个结点从小到大排序（C）2. 算法分析的目的是：A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性（A）3. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性B) 正确性和简明性C) 可读性和文档性D) 数据复杂性和程序复杂性（B）4. 计算机算法必须具备输入、输出和等5个特性。
数据结构（本科）武汉理工大学在线作业一、判断(共计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)。
（）B. 错误答案:【B】二、单选(共计60分,每题2.5分)17、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。
还来不及享受美丽的锦瑟华年，就已经到了白发迟暮，一生匆匆而过。
生命，就是这样匆匆，还来不及细细品味，就只剩下了回忆。
生命匆匆，累了就选择放下，别让自己煎熬痛苦，别让自己不堪重负。
放下该放下的，心才会释放重负，人生才能安然自如。
人生就是一个口袋，里面装的东西越多，前行的脚步就越沉重。
总觉得该得到的还没有得到，该拥有的却已经失去，苦苦追寻的依然渺茫无踪。
心累，有时候是为了生存，有时候是为了攀比。
只有放下羁绊前行脚步的重担，放下阴霾缭绕的负面情绪，才能感受到“柳暗花明又一村”的豁然开朗，领悟到“一蓑烟雨任平生”的超然物外。
人生太匆匆，累了，就放一放吧，何苦要执拗于一时的成败得失！
很多时候，我们用汗水滋养梦想，可是，梦想是丰满的，现实是骨感的。
每个人都渴望成功的鲜花围绕自己，可是，谁都不是常胜将军，都会猝不及防地遭遇人生的滑铁卢。
唉声叹气只会让自己裹足不前，一蹶不振只能让自己沉沦堕落。
如果真的不能承受其重，就放一放，重新审视前方的道路，选择更适合自己的方向。
有些东西，本就如同天上的浮云，即使竭尽全力，也未必能揽之入怀。
或者即使得到，也未必能提高幸福指数。
所以与其为得不到的东西惶惶终日，不如选择放下，为心减负，轻松前行。
一人难如百人愿,不是所有的人，都会欣赏和喜欢自己。
所以，我们不必曲意逢迎他人的目光，不用祈求得到所有人的温柔以待。
真正在意你的人，不会对你无情无义，不在意你的人，你不过是轻若鸿毛的可有可无。
做最好的自己，静静地守着一江春水的日子，让心云淡风轻，怡然自若。
人生本过客，何必千千结。
不是所有的相识都能地久天长，不是所有的情谊都能地老天荒。
有些人终究是走着走着就散了，成为我们生命中的过客。
爱过，恨过，都会装点我们原本苍白的人生，感谢曾经在我们生命中出现过的人。
如果无缘继续红尘相伴，就选择放下吧，给自己和对方都留一段美好的回忆和前行的空间。
鱼总是自由自在地在水中快乐游弋，是因为鱼只有七秒钟的记忆，只在一瞬间，鱼便忘记了所有的不愉快。
所以，忘记所有的不愉快，才能为美好的情绪留出空间，才能让心情灿然绽放。
林清玄说：一尘不染不是不再有尘埃，而是尘埃让它飞扬，我自做我的阳光。
是呀，世事喧嚣纷扰，放下纷扰，做一个阳光快乐的人，做自己快乐的主人！
还来不及享受美丽的锦瑟华年，就已经到了白发迟暮，一生匆匆而过。
生命，就是这样匆匆，还来不及细细品味，就只剩下了回忆。
