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

数据结构c语言期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构和非线性结构的区别在于（）。

A. 结构中元素的个数B. 结构中是否包含子结构C. 结构中元素之间是否有一对一关系D. 结构中元素之间是否有一对多关系答案：C2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。

A. 存储密度高B. 存储密度低C. 插入和删除操作快D. 存储空间可以动态分配答案：A3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数为（）。

A. i-1B. n-iC. n-i+1D. n-i-1答案：B4. 栈的运算遵循（）原则。

A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：C5. 在二叉树的前序遍历中，访问顺序为（）。

A. 根-左-右B. 左-根-右C. 左-右-根D. 右-左-根答案：A6. 哈希表的冲突解决方法中，链地址法是（）。

A. 将所有元素存储在同一个存储单元B. 将所有元素存储在同一个链表中C. 将所有元素存储在同一个数组中D. 将所有元素存储在同一个链表的同一个位置答案：B7. 在图的遍历中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。

A. 遍历的顺序不同B. 遍历的起点不同C. 遍历的路径不同D. 遍历使用的存储结构不同答案：D8. 快速排序算法的时间复杂度为（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B9. 归并排序算法的时间复杂度为（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B10. 在二叉搜索树中，查找一个元素的时间复杂度为（）。

A. O(n)B. O(logn)C. O(n^2)D. O(1)答案：B二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的时间复杂度通常用______来描述。

答案：大O符号2. 线性表的两种基本操作是插入和______。

武汉理工大学数据库期末考试试题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．在单链表中设置头结点和作用是__________________ 。

《数据结构》期末考试试卷试题及答案一、选择题（每题5分，共20分）1. 下列哪个不是线性结构？A. 栈B. 队列C. 图D. 数组2. 下列哪个不是栈的基本操作？A. 入栈B. 出栈C. 查找D. 判断栈空3. 下列哪个不是队列的基本操作？A. 入队B. 出队C. 查找D. 判断队列空4. 下列哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 环二、填空题（每题5分，共20分）5. 栈是一种______结构的线性表，队列是一种______结构的线性表。

6. 图的顶点集记为V(G)，边集记为E(G)，则无向图G=(V(G),E(G))，有向图G=(______，______)。

7. 树的根结点的度为______，度为0的结点称为______。

8. 在二叉树中，一个结点的左子结点是指______的结点，右子结点是指______的结点。

三、简答题（每题10分，共30分）9. 简述线性表、栈、队列、图、树、二叉树的基本概念。

10. 简述二叉树的遍历方法。

11. 简述图的存储结构及其特点。

四、算法题（每题15分，共30分）12. 编写一个算法，实现栈的入栈操作。

13. 编写一个算法，实现队列的出队操作。

五、综合题（每题20分，共40分）14. 已知一个无向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<4,5>}，画出图G，并给出图G的邻接矩阵。

15. 已知一个二叉树，其前序遍历序列为ABDCE，中序遍历序列为DBACE，请画出该二叉树，并给出其后序遍历序列。

答案部分一、选择题答案1. C2. C3. C4. D二、填空题答案5. 后进先出先进先出6. V(G),E(G)7. 0 叶结点8. 左孩子右孩子三、简答题答案9. （1）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。

“数据结构”期末考试试题一、单选题(每小题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、3个结点可构成棵不同形态的树。

2、利用直接选择排序算法对n个记录进行排序，最坏的情况下，记录交换的次数为。

3、一个图的_______表示法是唯一的，而______表示法是不唯一的。

4、一棵深度为h的满二叉树上的结点总数为，一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。

5、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为，有左孩子的条件是，其左孩子编号为。

6、二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要________个字节；M的第8列和第5行共占___________个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的________元素的起始地址一致。

7、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。

8、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。

9、n个顶点的连通图的生成树有n-1条边。

10、通常数组只有______给定一组有定义的下标，存取相应的数据__和___给定一组有定义的下标，修改相应数据元素的值_____两种运算，因此常采用__顺序_______来存储数组。

11、3个节点可以构成 5 棵不同形态的二叉树。

12、对于一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度，即为∟log2n」+1，当它为一棵单支树时具有最大高度，即为n 。

13、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为，若一个结点编号为23，则其有右孩子的条件是。

14、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。

武汉理⼯⼤学数据库期末考试试题06级，B) ∪，D) ∩，武汉理⼯⼤学教务处试题标准答案及评分标准⽤纸课程名称数据库与信息系统（ B 卷）⼀、填空题（每空1分，共15分）1.外模式，模式（或逻辑模式）2．属性3. 1对多（1：N），多对多（M:N）4. 实体完整性约束，参照完整性约束，⾃定义完整性约束5. .mdf，.ldf6. CREATE TRIGGER7. 传递函数依赖8. R∩S9. 数据操纵语句10. DROP VIEW⼆、单项选择题（本⼤题共20⼩题，每⼩题1分，共20分）D,C,B,C,A,B,C,B,A,D,A,D,C,D,A,B,C,A,D,B三、简答题（每题5分，共15分）1.数据的4个特征：1) 数据有“型”和“值”之分。

2分2) 数据受数据类型和取值范围的约束。

1分3) 数据有定性表⽰和定量表⽰之分。

1分4) 数据应具有载体和多种表现形式。

1分2.需求分析阶段，概念结构设计阶段，逻辑结构设计阶段，数据库物理设计阶段，数据库实施阶段，数据库运⾏和维护阶段 5分3. 主语⾔通过主变量向SQL语句提供参数。

2分SQL语句当前的⼯作状态和运⾏环境数据要反馈给应⽤程序。

SQL将其执⾏信息送到通信区SQLCA 中，应⽤程序从SQLCA 中取出这些状态信息，并据此信息来控制应该执⾏的语句。

3分四、综合题1. 1）∏（课程名＝‘数据库’（学⽣∞选课∞课程））5分姓名，学号2）∏姓名，学号（课程名＝‘数据库’（学⽣∞选课∞课程））∩∏姓名，学号（课程名＝‘数据结构’（学⽣∞选课∞课程））5分3）∏姓名，学号（学⽣）－∏姓名，学号(课程名＝‘数据库’（学⽣∞选课∞课程））5分2.1）SELECT⼯程代号3分FROM供应零件WHERE供应商代码=’S1’；2）SELECT零件.零件名，供应零件.数量4分FROM零件, 供应零件WHERE零件. 零件代码=供应零件. 零件代码AND供应零件. ⼯程代码=’J2’；3）SELECT零件代号4分FROM供应商, 供应零件WHERE供应商. 供应商代码=供应零件. 供应商代码AND供应商. 所在城市=’上海’4）SELECT⼯程号码4分FROM⼯程WHERE NOT EXISTS （SELECT *FORM供应零件WHERE⼯程. ⼯程代码=供应零件. ⼯程代码AND供应商代码IN（SELECT供应商代码FROM供应商WHERE所在城市=’天津’））；3. 1）CREA TE DA TABASE 学⽣选课库5分ON PRIMARY（NAME=学⽣选课库，FILENAME=’C：\msSQL\data\学⽣选课. mdf’，SIZE=4MB，MAXSIZE=6MBFILEROWHT=2MB）GO2）CREA TE TABLE 课程（课程号CHAR（10）PRIMARY KEY CLUSTERED，3分课程名V ARCHAR（50），先⾏课V ARCHAR（50））GO3）CREA TE INDEX student ind ON学⽣（学号）3分GOCREA TE INDEX class ind ON 课程（课程号）GO4）CREA TE RULE value rule AS @V ALUE IN（’男’，’⼥’）3分GOCREA TE DEFAULT 性别缺省AS’男’GO5）CREA TE TRIGGER sc insert ON选课3分FOR INSERTAS IF（SELECT COUNT（*）FROM学⽣，inserted, 课程WHERE学⽣.学号=inserted. 学号AND课程. 课程号=inserted. 课程号）=0 ROLLBACK TRANSACTIONGO6）CREA TE TRIGGER delete all ON学⽣4分FOR DELETEAS DELETEFROM选课WHERE选课. 学号=deleted. 学号GO。

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，其数量级表示为_____。

2022年武汉理工大学信息管理与信息系统专业《数据库概论》科目期末试卷A（有答案）一、填空题1、在SELECT命令中，______子句用于选择满足给定条件的元组，使用______子句可按指定列的值分组，同时使用______子句可提取满足条件的组。

2、事务故障、系统故障的恢复是由______完成的，介质故障是由______完成的。

3、数据库内的数据是______的，只要有业务发生，数据就会更新，而数据仓库则是______的历史数据，只能定期添加和刷新。

4、从外部视图到子模式的数据结构的转换是由______________实现；模式与子模式之间的映象是由______________实现；存储模式与数据物理组织之间的映象是由______________实现。

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

6、使某个事务永远处于等待状态，得不到执行的现象称为______。

有两个或两个以上的事务处于等待状态，每个事务都在等待其中另一个事务解除封锁，它才能继续下去，结果任何一个事务都无法执行，这种现象称为______。

7、在SQL Server 2000中，某数据库用户User在此数据库中具有对T 表数据的查询和更改权限。

现要收回User对T表的数据更改权，下述是实现该功能的语句，请补全语句。

_____UPDATE ON T FROM User；8、在RDBMS中，通过某种代价模型计算各种查询的执行代价。

在集中式数据库中，查询的执行开销主要包括______和______代价。

在多用户数据库中，还应考虑查询的内存代价开销。

9、数据模型是由______________、______________和______________三部分组成。

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

一个关系R二、判断题11、在综合分E-R图时，会出现属性冲突，结构冲突，命名冲突。

复习题集一判断题（×）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个特性。

试题标准答案及评分标准用纸| 课程名称数据结构（B卷）一、填空题（每空2分，共20分）1．逻辑结构存储结构运算2. 单链表3. 队尾队首4. 顺序表5．直接插入排序、简单选择排序、起泡排序、快速排序、基数排序、归并排序、堆排序中任选2种6. 2h-1二、单选题（每小题1分，共10分）1.B2.C3. B4.C5. A6.C7.A8. C9. D 10.B三、问答题（每小题5分，共10分）1. 算法是解决给定问题的一种方法（策略），即为解决某一特定问题而由若干条指令组成的有穷序列。

（2分）算法分析的目的是研究算法执行时间随问题规模变化的情况（问题规模是一个和输入有关的量，如n），提高算法的效率。

（1分）算法分析主要涉及：时间复杂度和空间复杂度。

（2分）2.线性表（a1,a2,……,an）中每个元素都具有相同的类型，它有两种存储结构：顺序表和链表。

广义表（d1,d2,……,dn）中每个元素可以是原子，也可以是子表。

可以将广义表看作是线性表的推广。

由于原子和子表的类型不同，所以只能用链式存储结构。

四、图表计算题（每小题8分，共40分）3．构造的哈夫曼树如图所示：4．第一趟： 060,820,200,150,331,001,761,044,004,125,545,806,308,029 第二趟： 200,001,004,806,308,820,125,029,331,044,545,150,060,761 第三趟： 001,004,029,044,060,125,150,200,308,331,545,761,806,820 5．其拓扑序列如下：l 2 4 5 8 9 10 3 7 6 ll 12五、算法设计题（20分）略。

2022年武汉理工大学数据科学与大数据技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、假设5个进程P0、P1、P2、P3、P4共享3类资源R1、R2、R3.这些资源总数分别为18、6、22。

T0时刻的资源分配情况（见表），此时存在的一个安全序列是（）。

A. P0, P2, P4, P1, P3B. P1, P0, P3, P4, P2C. P2, P1, P0, P3, P4D. P3, P4, P2, P1, P02、操作系统提供给编程人员的接口是（）。

A.库函数B.高级语言C.系统调用D.子程序3、若一个信号量的初值为3，经过多次P、V操作之后当前值为-1，则表示等待进入临界区的进程数为（）A.1B.2C.3D.44、设有n个进程共用一个相同的程序段，若每次最多允许m个进程（mSn）同时进入，临界区，则信号量的初值为（）。

A.nB.mC.m-nD.-m5、中断扫描机构是（）扫描次中断寄存器。

A.每隔一个时间片B.每条指令执行周期内最后时刻C.每当进程释放CPUD.每产生一次中断6、在采用SPOOLing技术的系统中，用户暂时未能打印的数据首先会被送到（）存储起来。

A.磁盘固定区域B.内存固定区域C.终端D.打印机7、下列天于管道（Pipe）通信的叙述中，正确的是（）A.一个管道可实现双向数据传输B.管道的容量仅受磁盘容量大小限制C.进程对管道进行读操作和写操作都可能被阻塞D.一个管道只能有一个读进程或一个写进程对其操作8、文件系统采用两级索引分配方式。

若每个磁盘块的大小为1KB.每个盘块号占4B，则该系统中单个文件的最大长度是（）A.64MBB.128MBC.32MBD.都不对9、某文件系统中，针对每个文件，用户类别分为4类：安全管理员、文件上、文件主的伙伴、其他用户：访问权限分为5类：完全控制、执行、修改、读取、写入。

若文件控制块中用：进制位串表示文件权限，为表示不同类别用户对一个文件的访问权限，则描述文件权限的位数至少应为（）。

《数据结构B卷》期末考试试卷附答案一、名词解释(每题2分，共10分)1. 数据类型2. 线性表3. 队列4. 串5. 图二、判断正误(正确打√，错误划×，每题1分，共10分)1.算法必须有输入参数。

( )2.链表能够动态分配结点空间。

( )3.栈是一种先进先出的线性表。

( )4.二维数组能够实现随机存取。

( )5.在二叉树的第i层上至多有2i-1个结点(i≥1)。

( )6.在有向图中，<v1,v2>与<v2,v1>是两条不同的边。

( )7.邻接表只能用于有向图的存储。

（）8.有向图不能进行广度优先遍历( )9.平均查找长度ASL可作为衡量一个查找算法效率高低的标准。

( )10.所有的内部排序算法都是稳定的。

( )三、填空(每空2分，共10分)1.线性表、栈和队列都是( )结构。

2.栈是一种特殊的线性表，允许插入和删除运算的一端称为（）。

3.队列的出队操作总是在( )进行。

4.按存储结构不同，串可分为( )。

5.深度为k 的完全二叉树至少有( )个结点。

四、选择题(单选或多选)(每题2分，共30分)1.算法原则上都是能够由机器或人完成的。

整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。

这是算法的( )。

A. 正确性B. 有穷性C. 确定性D. 可行性2.设一棵二叉树中，度为2的结点数为9，则该二叉树的叶结点的数目为( )。

A．10 B. 11 C. 12 D. 不确定3.某二叉树结点的先根序列为E、A、C、B、D、G、F，对中根遍历的序列为A、B、C、D、E、F、G。

该二叉树结点的后根遍历的序列为( )A. [B 、D 、C 、A 、F 、G 、E]B. [B 、D 、C 、F 、A 、G 、E]C. [E 、G 、F 、A 、C 、D 、B]D. [E 、G 、A 、C 、D 、F 、B]4.关于队列的说法正确的是（）A. 先进先出B. 属于非线性结构C. 只能采用顺序存储D.属于散列结构5.用单链表表示的链式队列的队尾是在链表的( )位置A. 表尾B. 表头C. 表中D. 任意6.树的非叶子结点是（）。

2017《数据结构》期末考试一试题及答案《数据结构》期末考试一试题及答案1..................................... .. (2)试题1答案............................................. ............................................... (7)《数据结构》期末考试一试题及答案2..................................... .. (9)试题2答案............................................. ............................................... (14)《数据结构》期末考试一试题及答案3..................................... (16)试题3答案............................................. ............................................... (21)第1页共23页《数据结构》期末考试一试题及答案 1一、单项选择题（每题2分，共20分）1. 栈和行列的共同特色是( )。

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

一、判断(共计50分,每题2.5分)1、树T的每一对结点之间有且仅有一条道路可通。

A. 正确B. 错误错误:【A】2、在任何图中，奇数度的结点数必是偶数。

A. 正确B. 错误错误:【A】3、设〈G，∘〉是一个群.若存在从〈G，∘〉到〈H，*〉的满同态，则〈H，*〉也构成群。

A. 正确B. 错误错误:【A】4、不含有任何元素的集合，称为空集，记作F。

A. 正确B. 错误错误:【A】5、图中度为零的结点称为孤立结点。

A. 正确B. 错误错误:【A】6、具有条边的连通图最多具有个结点。

A. 正确B. 错误错误:【A】7、两个代数系统同构则两个集合元素间存在双射。

A. 正确B. 错误错误:【A】8、域是整环。

A. 正确B. 错误错误:【A】9、任何连通图G至少存在一棵生成树。

A. 正确错误:【A】10、一个代数系统的单位元、零元、逆元如存在，则必唯一。

A. 正确B. 错误错误:【A】11、设A、B为谓词公式，若A<->B是逻辑有效式，则称A和B是等值的，记作A=>B。

A. 正确B. 错误错误:【B】12、不同的生成树的基本割集可能不一样，但基本割集的个数是固定的。

A. 正确B. 错误错误:【A】13、在格〈L，∨，∧〉中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的。

A. 正确B. 错误错误:【A】14、设，则的幂集是。

A. 正确B. 错误错误:【A】15、只由一个孤立结点构成的图称为平凡图。

A. 正确B. 错误错误:【A】16、上的普遍关系的关系矩阵是全1矩阵，而恒等关系的关系矩阵是单位矩阵。

A. 正确B. 错误错误:【A】17、完全图Kn没有割集，它的连通性能是最好的。

A. 正确错误:【A】18、克鲁斯卡尔(Kruskal)算法可以求最小生成树。

A. 正确B. 错误错误:【A】19、一个从A到B的二元关系是有序偶的集合R，在每一个有序偶中，第一个元素取自A，第二个元素取自B。