2022年合肥工业大学计算机科学与技术专业《数据结构与算法》科目
期末试卷A（有答案）
一、选择题
1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序
B.堆排序
C.归并排序
D.直接插入排序
2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。
A.j=r[j].next
B.j=j+l
C.j=j->next
D.j=r[j]->next
3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。
A.单链表
B.双向链表
C.单循环链表
D.顺序表
4、下面关于串的叙述中，不正确的是（）。
A.串是字符的有限序列
B.空串是由空格构成的串
C.模式匹配是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。
A.（rear-front+m）%m
B.rear-front+1
C.rear-front-1
D.rear-front
6、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180
C．180，500，200，450 D．180，200，500，450
7、下列叙述中，不符合m阶B树定义要求的是（）。
A．根结点最多有m棵子树 B．所有叶结点都在同一层上
C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接
8、一个具有1025个结点的二叉树的高h为（）。
A.11
B.10
C.11至1025之间
D.10至1024之间
9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A.107
B.108
C.214
D.215
10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。
A.（100，80，90，60，120，110，130）
B.（100，120，110，130，80，60，90）
C.（100，60，80，90，20，110，130）
D.（100，80，60，90，120，130，110）
二、填空题
11、在有n个顶点的有向图中，每个顶点的度最大可达______。
12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间
的是______算法，最费时间的是______算法。
13、设单链表的结点结构为（data，next），next为指针域，已知指针px 指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y 插入结点x之后，则需
要执行以下语句：______
14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的
次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用
以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。
15、索引顺序文件既可以顺序存取，也可以______存取。
16、模式串P=‘abaabcac’的next函数值序列为______。
17、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储： a11=1），则a85
的地址为______。
18、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V， SUBSTR（S，INDEX（S，t），LEN（t）+1））； ASSIGN（m，’ww’），求REPLACE（S，V，m）
=______。
三、判断题
19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）
20、倒排文件是对次关键字建立索引。（）
21、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）
22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若 ai=n（1≤i≤n）则有：ai>ai+1>…>an。（）
23、深度为k的二叉树中结点总数小于等于2k-1。（）
24、树形结构中元素之间存在一对多的关系。（）
25、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）
26、在待排数据基本有序的情况下，快速排序效果最好。（）
27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）
28、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（）
四、简答题
29、阅读下面的算法，说明算法实现的功能。
30、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树。
（2）若查找元素54，需依次与哪些元素比较?
（3）若查找元素90，需依次与哪些元素比较?
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
31、设二叉树BT的存储结构如表：
其中BT为树根结点的指针，其值为6，Lchild、Rchild分别为结点的左、右孩子指针域data为结点的数据域。试完成下列各题：
（1）画出二叉树BT逻辑结构。
（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列。
（3）画出二叉树的后序线索树。
五、算法设计题
32、线性表中元素存放在向量A（1，…，l）中，元素是整型数。试写出递归算法求出A 中的最大和最小元素。
33、设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中（注：按层从上到下，由左到右）。
34、串以静态存储结构存储，结构如下所述，试实现串操作equal算法。
35、写出按后序序列遍历中序线索树的算法。
参考答案
一、选择题
1、【答案】C
2、【答案】A
3、【答案】D
4、【答案】B
5、【答案】A
6、【答案】A
7、【答案】D
8、【答案】C
9、【答案】B
10、【答案】C
二、填空题
11、【答案】2(n-1)
12、【答案】起泡；快速
13、【答案】py->next=px->next；px->next=py
14、【答案】（Q，A，C，S，Q，D，F，X，R，H，M ,Y）；（F，H，C，D，a，A，M，Q，R，S，Y，X）
15、【答案】随机
16、【答案】01122312
17、【答案】33
18、【答案】’xyxyxywwy’
三、判断题
19、【答案】×
20、【答案】√
21、【答案】√
22、【答案】×
23、【答案】√
24、【答案】√
25、【答案】×
26、【答案】×
27、【答案】√
28、【答案】√
四、简答题
29、答：本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2，head2最后一个结点的链域指向head1，head1为结果循环链表的指针。
30、答：（1）判定树如图所示：
（2）若查找元素54，需依次和元素30、63、42、54比较，查找成功。
（3）若查找元素90，需依次和元素30、63、87、95比较，查找失败。
（4）
31、答：（1）二叉树的逻辑结构如图所示：
（2）前序序列：A B C E D F H G I J 中序序列：E C B H F D J I G A
后序序列：E C H F J I G D B A
（3）二叉树的后序线索树如图所示：
五、算法设计题
32、答：算法如下：
33、答：算法如下：
34、答：算法如下：
35、答：算法如下：
2022年合肥工业大学计算机科学与技术专业《数据库原理》科目期末 试卷A（有答案） 一、填空题 1、数据的安全性是指____________。 2、某在SQL Server 2000数据库中有两张表：商品表（商品号，商品名，商品类别，成本价）和销售表（商品号，销售时间，销售数量，销售单价）。用户需统计指定年份每类商品的销售总数量和销售总利润，要求只列出销售总利润最多的前三类商品的商品类别、销售总数量和销售总利润。为了完成该统计操作，请按要求将下面的存储过程补充完整。 3、数据库系统在运行过程中，可能会发生各种故障，其故障对数据库的影响总结起来有两类：______和______。 4、完整性约束条件作用的对象有属性、______和______三种。 5、数据库内的数据是______的，只要有业务发生，数据就会更新，而数据仓库则是______的历史数据，只能定期添加和刷新。 6、在SQL语言中，为了数据库的安全性，设置了对数据的存取进行控制的语句，对用户授权使用____________语句，收回所授的权限使用____________语句。 7、使某个事务永远处于等待状态，得不到执行的现象称为______。有两个或两个以上的事务处于等待状态，每个事务都在等待其中另一个事务解除封锁，它才能继续下去，结果任何一个事务都无法执行，这种现象称为______。 8、在关系数据库的规范化理论中，在执行“分解”时，必须遵守规范化原则：保持原有的依赖关系和______。 9、在SQL Server 2000中，数据页的大小是8KB。某数据库表有1000行数据，每行需要5000字节空间，则此数据库表需要占用的数据页数为_____页。 10、数据库恢复是将数据库从______状态恢复到______的功能。
2022年河南科技学院计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A.N B.2N-1 C.2N D.N-1 2、下述文件中适合于磁带存储的是（）。 A.顺序文件 B.索引文件 C.哈希文件 D.多关键字文件 3、链表不具有的特点是（）。 A.插入、删除不需要移动元素 B.可随机访问任一元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比 4、动态存储管理系统中，通常可有（）种不同的分配策略。 A.1 B.2 C.3 D.4 5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。 A.（rear-front+m）%m B.rear-front+1 C.rear-front-1 D.rear-front 6、下列选项中，不能构成折半查找中关键字比较序列的是（）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450
7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空， 下列判断队空和队满的条件中，正确的是（）。 A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1） 8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中 有（）个叶子。 A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2 9、一个具有1025个结点的二叉树的高h为（）。 A.11 B.10 C.11至1025之间 D.10至1024之间 10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。 A.直接插入排序 B.起泡排序 C.简单选择排序 D.快速排序 二、填空题 11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 12、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 13、文件可按其记录的类型不同而分成两类，即______和______文件。 14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从 左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使
2022年西安工程大学计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 2、下列排序算法中，占用辅助空间最多的是（）。 A.归并排序 B.快速排序 C.希尔排序 D.堆排序 3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。 A.可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front D.（rear-1）MOD n=front 5、在下列表述中，正确的是（） A.含有一个或多个空格字符的串称为空格串 B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l 6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19 B．3，5，12，19，20，15，22，8，28 C．3，8，12，5，20，15，22，28，19 D．3，12，5，8，28，20，15，22，19 7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a， 则根结点的孩子结点（）。 A．只有e B．有e、b C．有e、c D．无法确定 8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。 A.直接插入排序 B.起泡排序 C.简单选择排序 D.快速排序 二、填空题 11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 12、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表 示方式的数目。例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1， 1+1+1+1+1。 ①以下是该函数的程序段，请将未完成的部分填入，使之完整。
2022年合肥工业大学计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。 A.j=r[j].next B.j=j+l C.j=j->next D.j=r[j]->next 3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。 A.单链表 B.双向链表 C.单循环链表 D.顺序表 4、下面关于串的叙述中，不正确的是（）。 A.串是字符的有限序列 B.空串是由空格构成的串 C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。 A.（rear-front+m）%m B.rear-front+1 C.rear-front-1 D.rear-front 6、下列选项中，不能构成折半查找中关键字比较序列的是（）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450
7、下列叙述中，不符合m阶B树定义要求的是（）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 8、一个具有1025个结点的二叉树的高h为（）。 A.11 B.10 C.11至1025之间 D.10至1024之间 9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。 A.107 B.108 C.214 D.215 10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。 A.（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90） C.（100，60，80，90，20，110，130） D.（100，80，60，90，120，130，110） 二、填空题 11、在有n个顶点的有向图中，每个顶点的度最大可达______。 12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间 的是______算法，最费时间的是______算法。 13、设单链表的结点结构为（data，next），next为指针域，已知指针px 指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y 插入结点x之后，则需 要执行以下语句：______ 14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的 次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用 以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。 15、索引顺序文件既可以顺序存取，也可以______存取。 16、模式串P=‘abaabcac’的next函数值序列为______。 17、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储： a11=1），则a85 的地址为______。
2022年合肥工业大学计算机科学与技术专业《操作系统》科目期末试 卷A（有答案） 一、选择题 1、通常对文件系统来说，文件名及属性可以集中在（）中以使查询。 A.目录 B.索引 C.字典 D.作业控制块 2、下列选项中，磁盘逻辑格式化程序所做的T作是（） I.对磁盘进行分区 II.建立文件系统的根目录 III.确定磁盘扇区校验码所占位数 IV.对保存空闲磁盘块信息的数据结构进行初始化， A. 仅II B.仅II、IV C.仅III，IV D.仅I、II、IV 3、若系统中有n个进程，则在阻塞队列中进程的个数最多为（）？ Α. n B.n-1 C.n-2 D.1 4、进程P1和P2均包含并发执行的线程，部分伪代码描述如下所 //进程P1 //进程P2 int x=0； int x=0； Thread1（） Thread3（） {int a； {int a： a=1； a=x； x+=1； x+=3；
Thread2（） Thread4（） { { int a： int b, a a=2； b=x； x+=2； x1=4； } } 下列选项中，需要互斥执行的操作是（）。 A. a=l与a=2 B. a=x与b=x C. x+=1与x+=2 D. x+=1与x+=3 5、使用TSL（TestandSetLock）指令实现进程互斥的伪代码如下所示。do { while（TSL（&lock））； criticalsection； lock=FALSE； }while（TRUE）； 下列与该实现机制相关的叙述中，正确的是（） A.退出临界区的进程负责唤醒阻塞态进程 B.等待进入临界区的进程不会主动放弃CPU C.上述伪代码满足“让权等待”的同步准则 D.while（TSL（&lock））语句应在关中断状态下执行 6、下列措施巾，能加快虚实地址转换的是（）
2022年合肥工业大学(宣城校区)计算机科学与技术专业《操作系统》 科目期末试卷A（有答案） 一、选择题 1、某文件系统的簇和磁盘扇区大小分别为1KB和512B。若一个文件的大小为1026B，则系统分配给该文件的磁盘空间大小是（）。 A.1026B B.1536B C.1538B D.2048B 2、如果文件采用直接存取方法，且文件大小不固定，则应采用（）物理结构。 A.直接 B.索引 C.随机 D.顺序 3、下面哪个特征是并发程序执行的特点（）。 A.程序执行的间断性 B.相通信的可能性 C.产生死锁的可能性 D.资源分配的动态性 4、作业8：00到达系统，估计运行时问为1h。若从10：00开始执行该作业，其响应比为（）。 A.2 B.1 C.3 D.0.5 5、下列关于进程和线程的叙述中，正确的是（） 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.SPOOLing D.虚拟存储
2022年泰山学院计算机科学与技术专业《数据结构与算法》科目期末 试卷A（有答案） 一、选择题 1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。 A.哈希函数 B.除余法中的质数 C.冲突处理 D.哈希函数和冲突处理 2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。 A.串 B.树 C.广义表 D.栈 3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表 4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛
6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、下列叙述中，不符合m阶B树定义要求的是（）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 8、一个具有1025个结点的二叉树的高h为（）。 A.11 B.10 C.11至1025之间 D.10至1024之间 9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡 A.LL B.LR C.RL D.RR 二、填空题 11、若用n表示图中顶点数目，则有______条边的无向图成为完全图。 12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。 13、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。 14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。 15、索引顺序文件既可以顺序存取，也可以______存取。
2022年大连工业大学计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 2、下列排序算法中，占用辅助空间最多的是（）。 A.归并排序 B.快速排序 C.希尔排序 D.堆排序 3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。 A.可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 4、下面关于串的叙述中，不正确的是（）。 A.串是字符的有限序列 B.空串是由空格构成的串 C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 5、在下列表述中，正确的是（） A.含有一个或多个空格字符的串称为空格串 B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l
6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行 匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别 （）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、下列选项中，不能构成折半查找中关键字比较序列的是（）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 8、一个具有1025个结点的二叉树的高h为（）。 A.11 B.10 C.11至1025之间 D.10至1024之间 9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中 有（）个叶子。 A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2 10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是 （）。 A.每次分区后，先处理较短的部分 B.每次分区后，先处理较长的部分 C.与算法每次分区后的处理顺序无关 D.以上三者都不对 二、填空题 11、在哈希函数H（key）=key%p中，p值最好取______。 12、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 13、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并 能较快地______进行查找。 14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、 ______、______、______。
2022年成都东软学院计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放 在已排序序列的合适位置，该排序方法称为（）排序法。 A.插入 B.选择 C.希尔 D.二路归并 2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 3、单链表中，增加一个头结点是为了（）。 A.使单链表至少有一个结点 B.标识表结点中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储 4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列 中的元素数是（）。 A.（rear-front+m）%m B.rear-front+1 C.rear-front-1 D.rear-front 5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。 A.h->next=s B.s->next=h C.s->next=h;h->next=s D.s->next=h-next;h->next=s 6、下列选项中，不能构成折半查找中关键字比较序列的是（）。 A．500，200，450，180 B．500，450，200，180
C．180，500，200，450 D．180，200，500，450 7、下列叙述中，不符合m阶B树定义要求的是（）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。 A.107 B.108 C.214 D.215 9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。 A.（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90） C.（100，60，80，90，20，110，130） D.（100，80，60，90，120，130，110） 二、填空题 11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
2022年池州学院计算机科学与技术专业《数据结构与算法》科目期末 试卷A（有答案） 一、选择题 1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。 A.串 B.树 C.广义表 D.栈 2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A.N B.2N-1 C.2N D.N-1 3、线性表的顺序存储结构是一种（）。 A.随机存取的存储结构 B.顺序存取的存储结构 C.索引存取的存储结构 D.Hash存取的存储结构 4、下列关于AOE网的叙述中，不正确的是（）。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动若提前完成，那么整个工程将会提前完成 5、已知串S='aaab'，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、下列选项中，不能构成折半查找中关键字比较序列的是（）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450
8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。 A.107 B.108 C.214 D.215 9、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定 10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡 A.LL B.LR C.RL D.RR 二、填空题 11、在有n个顶点的有向图中，每个顶点的度最大可达______。 12、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。 13、一个算法具有5个特性： ______、______、______、有零个或多个输入、有一个或多个输出。 14、文件由______组成；记录由______组成。 15、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。 16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
2022年沈阳工程学院计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿 链移动的操作为（）。 A.j=r[j].next B.j=j+l C.j=j->next D.j=r[j]->next 2、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的 排序方法是（）。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 3、单链表中，增加一个头结点是为了（）。 A.使单链表至少有一个结点 B.标识表结点中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储 4、下面关于串的叙述中，不正确的是（）。 A.串是字符的有限序列 B.空串是由空格构成的串 C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。 A.543612 B.453126 C.346521 D.234156 6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空， 下列判断队空和队满的条件中，正确的是（）。 A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M
2022年合肥工业大学计算机科学与技术专业《计算机系统结构》科目 期末试卷A（有答案） 一、选择题 1、在计算机系统的层次结构中，机器被定义为（）的集合体 A.能存储和执行相应语言程序的算法和数据结构 B.硬件和微程序（固件） C.软件和固件 D.软件和硬件 2、对机器语言程序员透明的是( )。 A.中断字 B.主存地址寄存器 C.通用寄存器 D.条件码 3、属计算机系统结构考虑的是（） A.主存采用MOS还是TTL B.主存采用多体交叉还是单体 C.主存容量和编址方式 D.主存频宽的确定 4、目前，MO由（）实现，M1用（）实现，M2至M5大多用（）实现。 A.软件，固件，硬件
B.固件，软件，硬件 C.硬件，软件，固件 D.硬件，固件，软件 5、推出系列机的新机器，不能更改的是（）。 A.原有指令的寻址方式和操作码 B.系统总线的组成 C.数据通路宽度 D.存储芯片的集成度 6、程序员编写程序时使用的地址是( )。 A.有效地址 B.逻辑地址 C.辅存实地址 D.主存地址 7、在流水机器中，全局性相关是指( )。 A.先写后读相关 B.先读后写相关 C.指令相关 D.由转移指令引起的相关 8、1TFLOPS计算机能力，1TBYTE/S的I/O带宽和（）称为计算机系统的3T性能目标。 A，1TBYTE 硬盘容量 B.1TBYTE 软盘容量 C.1TBYTE 主存容量 D.A和B
9、对系统程序员不透明的应当是（） A.CACHE 存储器 B.系列机各档不同的数据通路宽度 C.指令缓冲寄存器 D.虚拟存储器 10、多处理机的各自独立型操作系统（）。 A.要求管理程序不必是可再入的 B.适合于紧耦合多处理机 C.工作负荷较平衡 D.有较高的可靠性 11、高级语言程序经（）的（）成汇编语言程序。 A.编译程序，翻译 B.汇编程序，翻译 C.汇编程序，解释 D.编译程序，解释 12、对汇编语言程序员透明的是（） A.I/O方式中的DMA访问 B.浮点数据表示 C.访问方式保护 D.程序性中断
2022年五邑大学计算机科学与技术专业《数据结构与算法》科目期末 试卷A（有答案） 一、选择题 1、下列说法不正确的是（）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A.N B.2N-1 C.2N D.N-1 3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。 A.单链表 B.双向链表 C.单循环链表 D.顺序表 4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。 A.543612 B.453126 C.346521 D.234156 5、动态存储管理系统中，通常可有（）种不同的分配策略。 A.1 B.2 C.3 D.4 6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。 Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ
8、有n（n>0）个分支结点的满二叉树的深度是（）。 A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中 有（）个叶子。 A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2 10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。 A.1 B.4 C.3 D.2 二、填空题 11、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。
2022年哈尔滨工业大学计算机科学与技术专业《数据结构与算法》科 目期末试卷A（有答案） 一、选择题 1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。 A.5 B.6 C.8 D.9 2、将线性表的数据元素进行扩充，允许带结构的线性表是（）。 A.串 B.树 C.广义表 D.栈 3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则 采用（）存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 5、在下列表述中，正确的是（） A.含有一个或多个空格字符的串称为空格串 B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l 6、下列关于无向连通图特性的叙述中，正确的是（）。 Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ
7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。 A．只有e B．有e、b C．有e、c D．无法确定 8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。 A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆 9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。 A.（2，5，12，16）26（60，32，72） B.（5，16，2，12）28（60，32，72） C.（2，16，12，5）28（60，32，72） D.（5，16，2，12）28（32，60，72） 二、填空题 11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。 12、阅读下列程序，指出其功能，并写出空格处应填上的语句。
2022年河海大学计算机科学与技术专业《数据结构与算法》科目期末 试卷A（有答案） 一、选择题 1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。 A.5 B.6 C.8 D.9 2、下述文件中适合于磁带存储的是（）。 A.顺序文件 B.索引文件 C.哈希文件 D.多关键字文件 3、连续存储设计时，存储单元的地址（）。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。 A.h->next=s B.s->next=h C.s->next=h;h->next=s D.s->next=h-next;h->next=s 5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改
6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空， 下列判断队空和队满的条件中，正确的是（）。 A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1） 7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序 方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。 Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 8、一个具有1025个结点的二叉树的高h为（）。 A.11 B.10 C.11至1025之间 D.10至1024之间 9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按 其关键字有序（）。 A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆 10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。 A.选择排序 B.起泡排序 C.插入排序 D.堆排序 二、填空题 11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
2022年北京工业大学计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。 A.5 B.6 C.8 D.9 2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 3、连续存储设计时，存储单元的地址（）。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 4、在下列表述中，正确的是（） A.含有一个或多个空格字符的串称为空格串 B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l 5、已知串S='aaab'，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空， 下列判断队空和队满的条件中，正确的是（）。 A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）
2022年成都工业学院计算机科学与技术专业《数据结构与算法》科目 期末试卷A（有答案） 一、选择题 1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A.13 B.33 C.18 D.40 2、下列排序算法中，占用辅助空间最多的是（）。 A.归并排序 B.快速排序 C.希尔排序 D.堆排序 3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则 采用（）存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。 A.543612 B.453126 C.346521 D.234156 5、在下列表述中，正确的是（） A.含有一个或多个空格字符的串称为空格串 B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l 6、下列关于无向连通图特性的叙述中，正确的是（）。 Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 7、下列叙述中，不符合m阶B树定义要求的是（）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 8、有n（n>0）个分支结点的满二叉树的深度是（）。
A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 9、在下述结论中，正确的有（）。 ①只有一个结点的二叉树的度为0。 ②二叉树的度为2。 ③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.⑦③④ C.②④ D.①④ 10、下面关于B和B+树的叙述中，不正确的是（） A.B树和B+树都是平衡的多叉树 B.B树和B+树都可用于文件的索引结构 C.B树和B+树都能有效地支持顺序检索 D.B树和B+树都能有效地支持随机检索 二、填空题 11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 12、属于不稳定排序的有______。