哈尔滨工业大学数据结构试题及答案
- 格式:doc
- 大小:665.56 KB
- 文档页数:40
[期末]2005数据结构与算法试卷试卷类型: 期末试卷年份: 05授课教师: 廖明宏有无答案: 无答案哈工大2005年春季学期数据结构与算法试卷一•填空题(每空1分,共10分)1・假定对线性表(3& 25,74,52,48)进行散列存储,采用H(K)=K %7作为散列函数,若分别采用线性探査法和链接法处理冲突,则对各自散列表进行査找的平均查找长度分别为______ 和_______ C2. _____________________________ 假定一组记录的排序码为(46, 79, 56, 3& 40, 80),对其进行归并排序的过程中, 第二趟归并后的结果为。
3. _____________________________ 在堆排丿了:的过程中,对任一分支结点进行调整运算的时间复杂度为. 整个堆排序过程的时间复杂度为。
4.有向图的邻接矩阵表示法中某一行非0元素的个数代表该顶点的,某一列非0元素的个数是该顶点的。
5. _________________________________________ 对于下面的带权图G3,若从顶点vO出发,则按照普里姆(Prim)算法生成的最小生成树中,依次得到的各条边为_____________________________________ 。
6.山带权为3, 9, 6, 2, 5的5个叶子结点构成一棵哈夫曼树,则带权路径长度为7.由三个结点构成的二义树,共有种不同结构。
二.选择题(每题1分,共10分)1 •快速分类在的情况下不利于发挥其长处.A.待分类的数据量太大B.待分类的数据相同值过多C.待分类的数据已基本有序D.待分类的数据值差过大.2•两路归并排序中,归并的趟数是。
A. 0(n)B. 0(log2n)C. 0(nlog2n)D. 0(n2)注意行为规范遵守考场纪律第1页,共6页3.对外部分类的K路平衡归并,采用败者树时,归并的效率与K OA.有关B•无关C•不能确定D.都不对4.对于一个索引顺序文件,索引表中的每个索引项对应主文件中的°A.—条记录B.多条记录C.所有记录D.三条以上记录5••若线性表采用顺序存储结构,每个元素占用4个存储单元,第一个元素的存储地址为100,则第12个元素的存储地址时。
2022年哈尔滨工业大学数据科学与大数据技术专业《操作系统》科目期末试卷A(有答案)一、选择题1、与早期的操作系统相比,采用微内核结构的操作系统具有很多优点,但是这些优点不,包括()。
A.提高了系统的可扩展性B.提高了操作系统的运行效率C.增强了系统的可靠性D.使操作系统的可移植性更好2、下列指令中,不能在用户态执行的是()A.trap指令B.跳转指令C.压栈指令D.关中断指令3、一次性分配所有资源的方法可以预防死锁的发生,这种方法破坏的是产生死锁的4个必要条件中的()。
A.互斥条件B.占有并请求C.不剥夺条件D.循环等待4、有若干并发进程均将一个共享变量count的值加1一次,那么有关count中的值的说法正确的是()。
I.肯定有不正确的结果II.肯定有正确的结果,III.若控制这些并发进程互斥执行count加1操作,count中的值正确A. I和IIIB.II和IIIC.IIID. I、II和III的说法均不正确5、一个进程被唤醒意味着()。
A.该进程可以重新占用CPUB.优先级变为最大C.PCB移到就绪队列之首D.进程变为运行态6、采用SPOOLing技术后,使得系统资源利用率()。
A.提高了B.有时提高,有时降低C.降低了D.提高了,但出错的可能性增人了7、采用SPOOLing技术将磁盘的一部分作为公共缓冲区以代替打印机,用户对打印机的操作实际上是对磁盘的存储操作,用以代替打印机的部分是()。
A.独占设备B.共享设备C.虚拟设备D.一般物理设备8、下列选项中,磁盘逻辑格式化程序所做的T作是()I.对磁盘进行分区II.建立文件系统的根目录III.确定磁盘扇区校验码所占位数IV.对保存空闲磁盘块信息的数据结构进行初始化,A. 仅IIB.仅II、IVC.仅III,IVD.仅I、II、IV9、一个磁盘的转速为7200r/min,每个磁道有160个扇区,每个扇区为512B.那么理想情况下,其数据传输率为()。
1. 判断题(共20分)------------------------------------------------------------------------------------------------------------ (1). 顺序存储的线性表可以随机存取。
()答案:是(2). 对于n个记录的集合进行归并排序,所需要的附加空间数是0(n)。
()答案:是(3). 矩阵压缩存储的方法是用三元组表存储矩阵元素。
()答案:否(4). 进栈操作push(x,s)作用于链接栈时,无须判满。
()答案:是(5). 在堆中执行insert与deletemin运算都只需o(log2n)时间。
( )答案:是(6). 在索引顺序表查找方法中,对索引顺序表可以使用顺序表查找方法,也可以使用二分查找方法。
()答案:是(7). 因为算法和程序没有区别,所以在数据结构中二者是通用的。
( )答案:否(8). 按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。
( )答案:是(9). 线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象。
()答案:否(10). 对于n个记录的集合进行冒泡排序,所需要的平均时间是O(n)。
()答案:否2. 选择题(共20分)------------------------------------------------------------------------------------------------------------ (1). 在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,那么度为0的结点数为__个。
A:4 B:5 C:6 D:7答案: C(2). 设关键字序列为:3,7,6,9,8,1,4,5,2。
进行排序的最小交换次数是__。
A:6 B:7 C:8 D:20答案:A(3). 在一个单链表中,若删除p所指结点的后继结点,则执行( )。
2021年哈尔滨工业大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A(有答案)一、选择题1、容量为64块的Cache采用组相联映射方式,字块大小为128个字,每4块为一组。
如果主存为4K块,且按字编址,那么主存地址和主存标记的位数分别为()。
A.16,6B.17,6C.18,8 D .19,82、根据存储内容来进行存取的存储器称为()。
A.双端口存储器B.相联存储器C.交叉存储器D.串行存储器3、关于浮点数在IEEE754标准中的规定,下列说法中错误的是()。
I.浮点数可以表示正无穷大和负无穷大两个值Ⅱ.如果需要,也允许使用非格式化的浮点数Ⅲ.对任何形式的浮点数都要求使用隐藏位技术IⅣ.对32位浮点数的阶码采用了偏移值为l27的移码表示,尾数用原码表示4、在补码加减交替除法中,参加操作的数和商符分别是()。
A.绝对值的补码在形成商值的过程中自动形成B.补码在形成商值的过程中自动形成C.补码由两数符号位“异或”形成D.绝对值的补码由两数符号位“异或”形成5、假设机器字长为16位,用定点补码小数表示时,一个字所能表示的范围是()。
A.0~(1-2-15)B.-(1-2-15)~(1-2-15)C.-1~1D.-1~(1-2-15)6、下列关于同步总线的说法中,正确的有()。
I.同步总线一般按最慢的部件来设置公共时钟II.同步总线一般不能很长III.同步总线一般采用应答方式进行通信IV.通常,CPU内部总线、处理器总线等采用同步总线A. I,IIB. I,II,IVC.III,IVD.II,III,IV7、下列有关总线定时的叙述中,错误的是()。
A.异步通信方式中,全互锁协议最慢B.异步通信方式中,非互锁协议的可靠性最差C.同步通信方式中,同步时钟信号可由各设备提供D.半同步通信方式中,握手信号的采样由同步时钟控制8、CPU中不包括()。
A.操作码译码器B.指令寄存器C.地址译码器D通用寄存器9、下列关于配备32位微处理器的计算机的说法中,正确的是()。
2019年哈尔滨工业大学854数据结构真题一、选择题1。
向栈内输入a1,2,3,4,5,6,输出顺序应该类似于a3,4,2,1,5,6这样的顺序,问栈的容量2。
高度为5的4阶b树,所含的关键字的最小数目是多少3。
以一个序列建立堆排序,例如46 39 54…,问建立的堆初始排序是哪个(这个比较狡猾没说是最大堆还是最小堆)4。
在拓扑排序中,v在u前面,则选项中哪一个是不可能的,有一个是有一条u到v的路径5。
prim算法求最小生成树,VT={1,2,3},ET={(1,2)(2,3)},接下来的最小代价边要从哪个序列里找6。
平衡二叉树问题,A是最低的不平衡点,A的左子树平衡度为1,右子树平衡度为0,A需如何调整成平衡二叉树7。
n个顶点组成无向图,各顶点的度中最大是多少8。
初始有序的哪种排序方法更好(冒泡)二、填空题1。
算法的时间复杂度不仅跟问题的规模有关,还跟实例的输入有关2。
使用2路归并n个数,需要次3。
给出后序序列,中序序列,求前序序列4。
kmp算法求串abaabc的next数组5。
给了5个数,求组成的哈夫曼树的wpl6。
哈希散列要解决和问题。
7。
散列表中散列函数hash=k mod 11,空间是14,给出了4个已知数的散列地址,问若使用拉链法处理冲突,则某一个数在表中的位置8。
快速排序不适合什么情况三、简答题1。
有n个人,m对朋友关系,朋友的朋友也是朋友,这样组成1个朋友圈,问怎么求有多少个朋友圈(实质就是无向图求连通分量)2。
一项工程,有11项项目,每个项目有完成所需时间及前置任务(或者10项,记得不是很准,那个图类似于哈工大的教材149页的图,其中试卷中a6的前置任务a6,这个应该是印错了,可能是a3)。
求:(1)使用合适模型表示(2)最少需多久完成整个项目,即求关键路径(3)给出如何求最少时间的方法四、算法题1。
构造一种特殊的队列结构,其中每个结点都有权值,每一次从队列中取出的节点都是最高优先权,设计算法输出(1)最小权值(2)插入一个数(3)删除最小权值,要求时间复杂度在log n以内2。
试卷一(哈尔滨工业大学)一、选择题(每题1分,共20分)1.在数据管理技术的发展过程中,数据独立性最高的是()阶段。
A. 数据库系统B. 文件系统C. 人工管理D. 数据项管理2. ()是存储在计算机内的有结构的数据集合。
A. 网络系统B. 数据库系统C. 操作系统D. 数据库3. 在数据库的三级模式结构中,描述数据库中全体数据的全局逻辑结构和特征的是()。
A. 外模式B. 内模式C. 存储模式D. 模式4. 作为关系数据系统,最小应具备的关系运算是()。
A. 排序、索引、统计B. 选择、投影、连接C. 关联、更新、排序D. 显示、打印、制表5. 在select语句中使用group by Sno时,Sno 必须出现在()子句中。
A. whereB. fromC. selectD. having6. 在where语句的条件表达式中,与零个或多个字符匹配的通配符是()。
A. *B. ?C. %D. _7. 对关系模式进行分解时,要求保持函数依赖,最高可以达到()。
A. 2NFB. 3NFC. BCNFD. 4NF8. 在关系模式R(U,F)中,Y∈XF+是X→Y是否成立的()。
A. 充分必要条件B. 必要条件C. 充分条件D. 既不充分也不必要条件9. 在关系数据库设计阶段中,完成关系模式设计的阶段是()。
A. 需求分析阶段B. 概念设计阶段C. 逻辑设计阶段D. 物理设计阶段10. 基本E-R图就是数据库的()。
A. 外模式B. 逻辑模式C. 内模式D. 概念模式11. 从数据流图构造E-R图时,选择实体一般应先考虑数据流图中的()。
A. 数据项B. 数据流C. 数据处理D. 数据存储12. 以下()不是当前常用的存取方法。
A. 索引方法B. 聚簇方法C. HASH方法D. 链表方法13. 事务一旦提交,对数据库的改变是永久的,这是事务的()。
A. 原子性B. 一致性C. 隔离性D. 持久性14. 并发控制要解决的根本问题是保持数据库状态的()。
2022年哈尔滨工业大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷B(有答案)一、选择题1、采用八体并行低位交叉存储器,设每个体的存储容量为32K×16位,存储周期为400ns,下述说法中正确的是()。
A.在400ns内,存储器可向CPU提供2位二进制信息B.在l00ns内,每个体可向CPU提供27位二进制信息C.在400ns内,存储器可向CPU提供2位二进制信息D.在100ns内,每个体可向CPU提供2位二进制信息2、假定编译器将赋值语句“x=x+3;”转换为指令“add xaddr,3”,其中xaddr是x对应的存储单元地址。
若执行该指令的计算机采用页式虚拟存储管理方式,并配有相应的TLB,且Cache使用直写(Write Trough)方式,则完成该指令功能需要访问主存的次数至少是()。
A.0B.1C.2D.343、十进制数-0.3125的8位移码编码为()。
A.D8HB.58HC.A8HD.28H4、下列为8位移码机器数[x]移,当求[-x]移时,()将会发生溢出。
A.11111111B.00000000C.10000000D.011l1l115、串行运算器结构简单,其运算规律是()。
A.由低位到高位先行进行进位运算B.由低位到高位先行进行借位运算C.由低位到高位逐位运算D.由高位到低位逐位运算6、在集中式总线控制中,响应时间最快的是()。
A.链式查询B.计数器定时查询C.独立请求D.分组链式查询7、某同步总线的时钟频率为100MHz,宽度为32位,地址/数据线复用,每传输一个地址或数据占用一个时钟周期。
若该总线支持突发(猝发)传输方式,则一次“主存写”总线事务传输128位数据所需要的时间至少是()。
A.20nsB.40nsC.50nsD.80ns8、某计算机主频为1.2GHz,其指令分为4类,它们在基准程序中所占比例及CPI如下表所示。
该机的MIPS数是()。
A.100B.200C.400D.6009、CPU中不包括()。
哈尔滨工业大学1999年数据结构考研试题(图2、3缺失)一. 名词分析(15分)1.广义表2.最小生成树3.散列表4.堆5.随机文件二. 试分别画出具有3个结点的树和3个结点的二元树的所有不同形态(同构的算一个)。
(6分)三. 本题给出一个子程序的框图,如图2,试填完完善此算法框图。
该子程序用来寻找第一个均出现在三个整数单向链表F1,F2,F3中的相同整数。
假定调用该子程序前,这三个整数链表已按从小到大的次序排序,单向链表的形式如下图1的例子所示。
(15分)(注:在图2中的框图中:found和exit均为布尔型的变量,可取值为true和false。
Val是整型变量,用来存放F1,F2,F3中无相同的整数found 的值为false,否则found的值为true。
F1^.link表示访问found结点的link域)。
四假设一株二元树,按其后根顺序的结点排序为:H,I,D,J,E,B,F,G,C,A而按中根顺序的结点排序为:H,D,I,B,E,J,A,C,F,G(1)试画出这株二元树。
(7分)(2)画出它的线索二元树。
(7分)五已知集合S={7,3,4,6,19,14,16,9,22,11},试按照自左而右的顺序依次取出S中的每个元素,逐步建立一株对应于S的二元查找树。
试画出所得到的二元查找树(不要求给算法)。
(8分)六本题给出的是将数组a的元素a1,a3…,an从大到小排序的子程序的框图,如图3,填空完善此算法框图。
该子程序采用改进的选择排序方法,该方法基本于以下思想:在选择第一大元过程中:a1与aj ( j = n , n –1…,2)逐个比较,若发现aj1>a1,则aj1与a1交换,交换后新的aj1有性质aj1>= at ( j1<t<n )。
若再有aj2 > ai ( j2 < j1 ),aj2与at (j2 < t <= n )。
如在挑选第一大元过程中,与a1交换的元素有k ( k >= 0 )个,依次为aj1,aj2,…,ajk,哈尔滨工业大学2001年数据结构考研试题考试科目:数据结构报考专业:计算机科学与技术一.填空(总分:10分,每一题2分)1.对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为________, 在给定为x的结点后插入一个新结点的时间复杂度为________。
2022年哈尔滨工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)一、选择题1、用有向无环图描述表达式(A+B)*((A+B)//A),至少需要顶点的数目为()。
A.5B.6C.8D.92、将线性表的数据元素进行扩充,允许带结构的线性表是()。
A.串B.树C.广义表D.栈3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时()。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、在下列表述中,正确的是()A.含有一个或多个空格字符的串称为空格串B.对n(n>0)个顶点的网,求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列关于无向连通图特性的叙述中,正确的是()。
Ⅰ.所有的顶点的度之和为偶数Ⅱ.边数大于顶点个数减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快速排序,从小到大一次划分结果为()。
1. 判断题判断题 (共20分) ------------------------------------------------------------------------------------------------------------ (1). 哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。
哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。
() 答案:是答案:是(2). 线性表的链式存储结构优于顺序行储结构。
线性表的链式存储结构优于顺序行储结构。
() 答案: 否答案:(3). 在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。
() 答案: 否答案:(4). 对于n个记录的集合进行归并排序,存最坏的情况下所需要的时间是0(n^2)。
() 答案: 否答案:(5). 由于磁带的价格比磁盘便宜,用磁带实现直接访问文件较为合理。
() 答案: 否答案:(6). 表中的每一个元素都有一个前驱和后继元素。
() 答案: 否答案:(7). 只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。
只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。
() 答案: 否答案:(8). 在索引顺序表查找方法中,对索引顺序表可以使用顺序表查找方法,也可以使用二分查找方法。
() 查找方法。
答案:是答案:是(9). 数据元素是数据的最小单位。
数据元素是数据的最小单位。
( ) 答案: 否答案:(10). 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。
() 答案: 否答案:2. 选择题选择题 (共20分) ------------------------------------------------------------------------------------------------------------ (1). 设一个数列的顺序为1,2,3,4,5,6,通过栈结构可以排成的顺序数列为__。
一、选择题1. 算法的计算量的大小称为计算的(B )。
【北京邮电大学2000 二、3 (20/8分)】A.效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于(C )【中科院计算所1998 二、1 (2分)】A.问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是(1),它必须具备(2)这三个特性。
(1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1(2分)【武汉交通科技大学1996 一、1(4分)】4.一个算法应该是()。
【中山大学1998 二、1(2分)】A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A 和C.5. 下面关于算法说法错误的是()【南京理工大学2000 一、1(1.5分)】A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是()【南京理工大学2000 一、2 (1.5分)】(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界(4)同一个算法,实现语言的级别越高,执行效率就越低A.(1) B.(1),(2) C.(1),(4) D.(3)7.从逻辑上可以把数据结构分为()两大类。
【武汉交通科技大学1996 一、4(2分)】A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构8.以下与数据的存储结构无关的术语是()。
【北方交通大学2000 二、1(2分)】A.循环队列 B. 链表 C. 哈希表 D. 栈9.以下数据结构中,哪一个是线性结构()?【北方交通大学2001 一、1(2分)】A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串10.以下那一个术语与数据的存储结构无关?()【北方交通大学2001 一、2(2分)】A.栈 B. 哈希表 C. 线索树 D. 双向链表11.在下面的程序段中,对x的赋值语句的频度为()【北京工商大学2001 一、10(3分)】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A.O(2n) B.O(n) C.O(n2) D.O(log2n)12.程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换;其中n为正整数,则最后一行的语句频度在最坏情况下是()A. O(n)B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13.以下哪个数据结构不是多型数据类型()【中山大学1999 一、3(1分)】A.栈B.广义表C.有向图D.字符串14.以下数据结构中,()是非线性数据结构【中山大学1999 一、4】A.树B.字符串C.队D.栈15. 下列数据中,()是非线性数据结构。
哈工大计算机科学与技术专业854考研真题I.数据结构一、选择题1.设n是描述问题规模非负整数, 下面程序片段时间复杂度是()。
Int x = n * n;While (x >= 1) {X = x / 2;}A.O(log2n)B.O(n)C.O(nlog2n)D.O(n1/2)2.需要分配一个较大存放空间而且插入和删除操作不需要移动, 元素满足以上特点线性表存放结构是()。
A.单向链表B.静态链表C.线性链表D.次序表3.已知字符串S为”ababcabcacbab”, 模式串T为”abcac”。
若采取KMP算法进行模式匹配,则需要()遍(趟匹配), 就能确定T是S子串。
A. 3B. 4C. 5D. 64.已知某棵二叉树前序序列是1,2,3,4, 则不可能为该二叉树中序序列是()。
A.1,2,3,4B.2,3,4,1C.1,4,3,2D.3,1,4,25.将森林F转换为对应二叉树T, F中任何一个没有右弟兄结点, 在T中()。
A.没有左子树B.没有右子树C.没有左子树和右子树D.以上都不对6.一个含有n个顶点和e条边无向图, 在其邻接矩阵存放结构中共有()个零元素。
A. eB.2eC.n2-2eD.n2-e7.在一棵高度为2和7阶B树中, 所含关键字个数最少是()。
A. 5B.7C.8D.148.设待排序元素个数为n, 则基于比较排序最坏情况下时间复杂度下界为()。
A.log2nB.nC.nlog2nD.n29.下面相关B树和B+树叙述中, 不正确是()。
A.B树和B+树都能有效地支持检索B.B树和B+树都能有效地支持次序检索C.B树和B+树都是平衡多路树D.B树和B+树都能够用于文件索引结构10.若待排序关键字序列在排序前已按其关键字递增次序排列, 则采取()方法比较次数最少。
A.插入排序B.快速排序C.堆排序D.选择排序二、填空题11.在一棵n个结点二叉树中, 全部结点空子树个数为11 。
2022年哈尔滨工业大学数据科学与大数据技术专业《数据库系统原理》科目期末试卷B(有答案)一、填空题1、在设计局部E-R图时,由于各个子系统分别有不同的应用,而且往往是由不同的设计人员设计,所以各个局部E-R图之间难免有不一致的地方,称为冲突。
这些冲突主要有______、______和______3类。
2、关系数据库中基于数学的两类运算是______________和______________。
3、从外部视图到子模式的数据结构的转换是由______________实现;模式与子模式之间的映象是由______________实现;存储模式与数据物理组织之间的映象是由______________实现。
4、设某数据库中有作者表(作者号,城市)和出版商表(出版商号,城市),请补全如下查询语句,使该查询语句能查询作者和出版商所在的全部不重复的城市。
SELECT城市FROM作者表_____SELECT城市FROM出版商表;5、在SELECT命令中,______子句用于选择满足给定条件的元组,使用______子句可按指定列的值分组,同时使用______子句可提取满足条件的组。
6、已知系(系编号,系名称,系主任,电话,地点)和学生(学号,姓名,性别,入学日期,专业,系编号)两个关系,系关系的主码是______________,系关系的外码是______________,学生关系的主码是______________,外码是______________。
7、安全性控制的一般方法有____________、____________、____________、和____________视图的保护五级安全措施。
8、数据库恢复是将数据库从______状态恢复到______的功能。
9、在SQL Server 2000中,某数据库用户User在此数据库中具有对T 表数据的查询和更改权限。
现要收回User对T表的数据更改权,下述是实现该功能的语句,请补全语句。
哈工大2004年硕士研究生入学考试试题《数据结构》答案及解析一、 填空题解答:1、()1%m n + 或 ()1mod m n +【备注】本题主要考查考生对循环队列的数组实现过程中 关于空对与满队的区分 ,同时还考查,如何利用数组来实现循环队列,即依赖于数学意义上的求模运算来实现。
2、 第一【备注】本题主要考查考生对二叉树中 关于前序、中序、后序遍历定义的理解,由教材中的理论可知,无论在上述三种遍历中的哪种方式中,在某子树中,同一层级上的左孩子一定在右孩子的前面首先被遍历。
因此,可以将该题抽象为或者简化为如下形式(这也是 二叉树的一般形式):由题意,显然答案如上。
3、 9、4、6、7、8【备注】本题主要考查考生对二分查找(即折半查找)算法的理解。
在二分算法中,需要注意的是,每次对low 、mid 、up 的选取(通过关键字进行比较即可得到)。
由教材中关于对二分查找算法的描述可知:()/2mid low up = + (注意这是两个整型数相加后与整数2作除法,其结果仍为整数,即对数学意义上的结果进行取整。
),下一次可能需要继续查找的区间为两种情况:[],1low mid − 或者 []1,mid up + 。
因此,可以得到本题的查找区间分别为:()117/29mid =+=、()18/24mid =+=、()58/26mid =+=、()78/27mid =+=、()88/28mid =+=4、N 和 2log N⎡⎤⎢⎥【备注】本题主要考查考生对快速排序算法的理解,同时还考察了考生对二分查找、二元查找树、二叉树、算法的最坏情况、算法的最好情况等知识点的理解。
该题有一定的难度。
由所学知识可知:快速排序算法的关键还是类似于二分的思想,那就是每次都将区间分割为三个集合(其中基准元本身单独构成了一个集合),然后依次递归下去。
显然,我们可以将这种剖分方式与二分查找对应起来,由二分查找可知,整个二分查找过程其实就是对应于一个二元查找树,其查找效率与相应的二元查找树的深度相关。
哈工大2009年春季学期数据结构与算法 试卷一、填空题(每空2分,共20分)1. 在 情况下,等长编码是最优前缀码。
2.设有两个算法在同一机器上运行,其执行时间分别为100n 2和2n ,要使前者快于后者,n 至少为 。
3.采用堆排序、快速排序、冒泡排序,对初态有序的表,最省时间的是_ 。
4. 设二叉树结点的先根序列为ABDECFGH ,中根序列为DEBAFCHG,则二叉树中叶结点是_________.5. 用下标从0开始的N 个元素的数组实现循环队列时,为实现下标变量m 加1后在数组有效下标范围内循环,可采用的表达式是m= 。
6. 由带权为3,9,4,2,5的5个叶子结点构成一棵哈夫曼树,则带权路径长度为 。
7. 对n 个记录的表进行选择排序,在最坏情况下所需要进行的关键字的比较次数为 。
8. 任意一个有n 个结点的二叉树,已知它有m 个叶结点,则度数为2的结点有 。
9. n 个顶点的连通图用邻接矩阵表示时,该矩阵至少有 个非零元素10. 举出两种磁带文件的分类方法: 。
二、选择题(每题1分,共10分)注意行为规范遵守考场纪律1.设一组初始记录关键字序列为(45,80,55,40,42,85),则以第一个记录关键字45为基准而得到一趟快速排序的结果是( )。
(A) 40,42,45,55,80,83(B) 42,40,45,80,85,88(C) 42,40,55,80,45,85(D) 42,40,45,85,55,802.数据的最小单位是( )。
(A) 数据项(B) 数据类型(C) 数据元素 (D) 数据变量3.关键路径是AOE网中( ) 。
A.从始点到终点的最短路径B.从始点到终点的最长路径C.从始点到终点的边数最多的路径D.从始点到终点的边数最少的路径4.下列说法正确的是()。
A.最小生成树也是哈夫曼树B.最小生成树是唯一的C.对于n 个顶点的连通无向图,Prim算法的时间复杂性为O(n2)D.Kruskal 算法比Prim算法更适合边稠密的图5.设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是( )。
数据结构试卷(一)一、单选题(每题2 分,共20分)1.栈和队列的共同特点是( )。
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层的结点数最多为( ).A.2k-1 B.2K+1 C.2K-1 D. 2k-17.若有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,其数量级表示为________。
3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J)),则树中所含的结点数为__________个,树的深度为___________,树的度为_________。
4.后缀算式9 2 3 +- 10 2 / -的值为__________。
中缀算式(3+4X)-2Y/3对应的后缀算式为_______________________________。
5.若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。
在这种存储结构中,n个结点的二叉树共有________个指针域,其中有________个指针域是存放了地址,有________________个指针是空指针。
6.对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有_______个和________个。
7.AOV网是一种___________________的图。
8.在一个具有n个顶点的无向完全图中,包含有________条边,在一个具有n个顶点的有向完全图中,包含有________条边。
9.假定一个线性表为(12,23,74,55,63,40),若按Key % 4条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
10.向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度___________。
11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为________,整个堆排序过程的时间复杂度为________。
12.在快速排序、堆排序、归并排序中,_________排序是稳定的。
三、计算题(每题6 分,共24分)1.在如下数组A中链接存储了一个线性表,表头指针为A [0].next,试写出该线性表。
A 0 1 2 3 4 5 6 7data 60 50 78 90 34 40next 3 5 7 2 0 4 12.请画出下图的邻接矩阵和邻接表。
3.已知一个图的顶点集V和边集E分别为:V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。
4.画出向小根堆中加入数据4, 2, 5, 8, 3时,每加入一个数据后堆的变化。
四、阅读算法(每题7分,共14分)1.LinkList mynote(LinkList L){//L是不带头结点的单链表的头指针if(L&&L->next){q=L;L=L->next;p=L;S1:while(p->next) p=p->next;S2:p->next=q;q->next=NULL;}return L;}请回答下列问题:(1)说明语句S1的功能;(2)说明语句组S2的功能;(3)设链表表示的线性表为(a1,a2, …,a n),写出算法执行后的返回值所表示的线性表。
2.void ABC(BTNode * BT){if BT {ABC (BT->left);ABC (BT->right);cout<<BT->data<<' ';}}该算法的功能是:五、算法填空(共8分)二叉搜索树的查找——递归算法:bool Find(BTreeNode* BST,ElemType& item){if (BST==NULL)return false; //查找失败else {if (item==BST->data){item=BST->data;//查找成功return ___________;}else if(item<BST->data)return Find(______________,item);else return Find(_______________,item);}//if}六、编写算法(共8分)统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x)数据结构试卷(二)一、选择题(24分)1.下面关于线性表的叙述错误的是()。
(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2.设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。
(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m3.设顺序循环队列Q[0:M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为()。
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M4.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为()。
(A) BADC (B) BCDA (C) CDAB (D) CBDA5.设某完全无向图中有n个顶点,则该完全无向图中有()条边。
(A) n(n-1)/2 (B) n(n-1) (C) n2(D) n2-16.设某棵二叉树中有2000个结点,则该二叉树的最小高度为()。
(A) 9 (B) 10 (C) 11 (D) 127.设某有向图中有n个顶点,则该有向图对应的邻接表中有()个表头结点。
(A) n-1 (B) n (C) n+1 (D) 2n-18.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为()。
(A) 2,3,5,8,6 (B) 3,2,5,8,6(C) 3,2,5,6,8 (D) 2,3,6,5,8二、填空题(24分)1.为了能有效地应用HASH查找技术,必须解决的两个问题是____________________和__________________________。
2.下面程序段的功能实现数据x进栈,要求在下划线处填上正确的语句。
typedef struct {int s[100]; int top;} sqstack;void push(sqstack &stack,int x){if (stack.top==m-1) printf(“overflow”);else {____________________;_________________;}}3.中序遍历二叉排序树所得到的序列是___________序列(填有序或无序)。
4.快速排序的最坏时间复杂度为___________,平均时间复杂度为__________。
5.设某棵二叉树中度数为0的结点数为N0,度数为1的结点数为N1,则该二叉树中度数为2的结点数为_________;若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有_______个空指针域。
6.设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=_______。
7.设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为___________________________。
8.已知一有向图的邻接表存储结构如下:从顶点1出发,DFS遍历的输出序列是,BFS遍历的输出序列是三、应用题(36分)1.设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
2.设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A 的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)。
3.设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二分查找,要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
4.设一棵树T中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。