华中科技大学计算机学院数据结构(计算机专业)答案

《数据结构》试卷 (A 卷)2010 —2011 年度第二学期计算机学院 班级______ 学号___________ 姓名_________考试时间：2011年 月 日 考试形式：闭卷一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分) 1．对于栈的进栈和出栈运算，采用______存储结构时运算效率最高。

A ．单链表B ．容量足够大的顺序表C ．单向循环链表D ．双向循环链表2．链式队列和顺序队列比较，具有_____这个优势。

A ．进队操作方便B ．出队操作方便C ．通常不会出现满队列情况D ．求队列元素个数方便 3．下列关于串的叙述中，正确的是_____。

A ．2个串的长度相等，则2个串相等B ．空串至少包一个空格C ．替换操作可以实现字符的删除D ．一个串的长度至少是1 4．二叉树在线索化后，下列问题中相对难解决的是____。

A ．先根线索二叉树中求先根后继B ．中根线索二叉树中求中根前趋C ．中根线索二叉树中求中根后继D ．后根线索二叉树中求后根后继5．对序列（30，26，18，16，5，66）进行2遍 ________排序后得到序列（5，16，18，26，30，66）。

A ．选择B ．冒泡C ．插入D ．归并6．在下列排序算法中，_______算法可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终的位置上。

A ．堆排序B ．快速排序C ．冒泡排序D ．插入排序 7．由4个结点可以组成______棵不同形态的二叉树。

A ．10B ．12C ．14D ．168．对包含n 个元素的散列表进行检索，平均查找长度为____。

A ．O(logn) B ．O(n) C ．O(nlogn) D ．不直接依赖于n 9．广义表 ((a,(b),c),((),(d)),(((((e)),f))),())的长度是____。

A ．2B ．3C ．4D ．510．对某无向图进行一次深度优先搜索遍历，如果能访问到所有的顶点，则该无向图一定是________。

2022年华中科技大学计算机科学与技术专业《数据库原理》科目期末试卷B（有答案）一、填空题1、DBMS的完整性控制机制应具备三个功能：定义功能，即______；检查功能，即______；最后若发现用户的操作请求使数据违背了完整性约束条件，则采取一定的动作来保证数据的完整性。

2、主题在数据仓库中由一系列实现。

一个主题之下表的划分可按______、______数据所属时间段进行划分，主题在数据仓库中可用______方式进行存储，如果主题存储量大，为了提高处理效率可采用______方式进行存储。

3、在设计局部E-R图时，由于各个子系统分别有不同的应用，而且往往是由不同的设计人员设计，所以各个局部E-R图之间难免有不一致的地方，称为冲突。

这些冲突主要有______、______和______3类。

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

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

5、在RDBMS中，通过某种代价模型计算各种查询的执行代价。

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

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

6、设某数据库中有商品表（商品号，商品名，商品类别，价格）。

现要创建一个视图，该视图包含全部商品类别及每类商品的平均价格。

请补全如下语句： CREATE VIEW V1（商品类别，平均价格）AS SELECT商品类别，_____FROM商品表GROUP BY商品类别；7、在SQL语言中，为了数据库的安全性，设置了对数据的存取进行控制的语句，对用户授权使用____________语句，收回所授的权限使用____________语句。

8、在一个关系R中，若每个数据项都是不可再分割的，那么R一定属于______。

9、设在SQL Server 2000环境下，对“销售数据库”进行的备份操作序列如下图所示。

2022年华中科技大学计算机科学与技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、在一个文件被用户进程首次打开的过程中，操作系统需做的是（）A.将文件内容读到内存中B.将文件控制块读到内存中C.修改文件控制块中的读写权限D.将文件的数据缓冲区首指针返回给用户进程2、在系统内存中设置磁盘缓冲区的主要11的是（）。

A.减少磁盘1/0次数，B.减少平均寻道时间C.提高磁盘数据可靠性D.实现设备无关性3、若系统中有n个进程，则在阻塞队列中进程的个数最多为（）？Α. n B.n-1 C.n-2 D.14、一个正在访问临界资源的进程由于申请等待1/0操作而被中断时，它（）。

A.允许其他进程进入与该进程相关的临界区B.不允许其他进程进入临界区C.允许其他进程抢占处理器，但不能进入该进程的临界区D.不允许任何进程抢占处理器5、在操作系统中，一方面每个进程具有独立性，另一方面进程之间具有相互制约性。

对于任何两个并发进程，它们（）。

A.必定无关B.必定相关C.可能相关D.可能相同6、（）存储管理方式提供一维地址结构。

A.分段B.分页C.分段和段页式D.以上都不对7、若用8个字（字长32位，H字号从0开始计数）组成的位示图管理内存，用户归还一个块号为100的内存块时，它对应位示图的位置为（）（注意：位号也从0开始）。

A.字号为3，位号为5B.字号为4，位号为4C.字号为3，位号为4D.字号为4，位号为58、假设4个作业到达系统的时刻和运行时间见表。

系统在t=2时开始作业调度。

若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是（）。

A.J2、J3B.J1、J4C.J2、J4D.J1、J39、下列选项中，会导致用户进程从用户态切换到内核态的操作是（）I.整数除以零 II.sin函数调用 III.read系统调用A.仅I、IIB.仅I、IIIC.仅II、IIID. I、II和II10、系统将数据从磁盘读到内存的过程包括以下操作：① DMA控制器发出中断请求②初始化DMA控制器并启动磁盘③从磁盘传输一块数据到内存缓冲区④执行“DMA结束”中断服务程序正确的执行顺序是（）：A.③①②④B.②③①④C.②①③④D.①②③④11、在采用SPOOLing技术的系统中，用户暂时未能打印的数据首先会被送到（）存储起来。

2018年华中科技大学834计算机专业基础综合（数据结构、计算机网络）考研真题（回忆版）数据结构部分一、选择题（共10道，一个2分，共20分）1．数据结构的逻辑结构分类是哪两种？2．给定一颗完全二叉树的结点数，求其中的叶节点个数3．一个有n个结点的图构成一个邻接矩阵几乘几的矩阵4～10暂缺二、简答题（共5道题，前四个15分，最后一个10分，今年没有编程题，也就是都是算法和推演，不用写代码，都是根据要求写结果和原理）1．给了8个左右的数字的一个集合，比如{75，63，43…}，要求一次读取一个，输出成一个二叉排序树，写出结果，并且求等概率情况下的平均查找长度。

2．给了一个包含有ABCDEFGH这几个点的二叉树的先序和中序排列，要求画出原二叉树。

3．一个指令集合{I1，I2，I3…}，对应给出了每个指令对应的发生概率大小{0.03，0.03，0.15，0.15，0.3，0.4}（这个数字印象比较深基本差不多），让求出用此集合构成的哈夫曼树。

求出他们的一个组织，并且求出每个指令的哈夫曼编码。

4．给出了一个由ABCDEFGHLM点组成的的无向带权图，让求出最小生成树（这里题干没有写用哪种算法）。

5．给定了一个树，转化成对应的二叉树，大概有8个点左右。

计算机网络部分一、选择题（共10道，一个1分，共10分）1．IPV4和IPV6的特征对比，选出一个错误的2．TCP拥塞控制中慢开始算法的特征，选出一个错误的3～10暂缺二、填空题（共10道，一个1分，共10分）1．IEEE802.11用的协议是_____2．CDMA2000采用的编码方式是_____3．移动IP的基本工作过程（给了其中3个步骤，填另一个）4．信道划分的三种方式（给了其中2个，填另一个）5～10暂缺三、简答题（共7道，共40分）1．主机A向主机B先后发两个报文，给出了每个报文的字节数，然后分别问了第一个先到的情况下和第二个报文先到的情况下各自的确认号，源，目的。

线性表的顺序存储结构是一种（）的存储结构。

选择一项：A. 随机存取B. 顺序存取C. Hash存取D. 索引存取反馈正确答案是：随机存取题目2获得2.00分中的2.00分标记题目设单链表中指针p指向结点A，q指向新元素结点，若要A之后插入一个新元素，则所需修改指针的操作为（）。

选择一项：A. p->next=q->next，q->next=pB. p->next=p，q->next=p->nextC. p->next=q，q->next=p->nextD. q->next=p->next，p->next=q反馈正确答案是：q->next=p->next，p->next=q题目3获得2.00分中的2.00分标记题目在关键字序列（149，138，165，197，176，113，127）中采用最低位优先排序(LSD)基数排序，第一趟之后所得结果为（）。

选择一项：A. 113，127，138，149，165，176，197B. 128，149，165，197，113，127，176C. 149，138，165，197，176，113，127D. 128，149，165，197，113，176，127反馈正确答案是：128，149，165，197，113，176，127题目4获得2.00分中的0.00分标记题目4个顶点的有向完全图有（）个弧。

选择一项：A. 12B. 10C. 8D. 6反馈正确答案是：12题目5获得2.00分中的2.00分标记题目数据元素的存储结构，通常采用（）。

选择一项：A. 链式结构B. 顺序结构C. 散列结构D. 顺序和链式组合结构反馈正确答案是：顺序结构题目6获得2.00分中的2.00分标记题目栈和队列的共同点是（）。

选择一项：A. 进出原则都是后进先出B. 都是插入删除操作受限的线性表C. 不允许在任意端点处插入和删除元素D. 进出原则都是先进先出反馈正确答案是：都是插入删除操作受限的线性表题目7获得2.00分中的2.00分标记题目串通常采用块链存储的优点是（）。

2022年华中科技大学数据科学与大数据技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、假定下列指令已装入指令寄存器，则执行时不可能导致CPU从用户态变为内核态（系统态）的是（）。

A.DIV R0，R1；（R0）/（R1）→ROB.INT n；产生软中断C.NOT RO；寄存器R0的内容取非D.MOV RO，addr；把地址 addr处的内存数据放入寄存器RO中2、用户程序在口态下使用特权指令引起的中断属于（）。

A.硬件故障中断B.程序中断C.外部中断D.访管中断3、有若干并发进程均将一个共享变量count的值加1一次，那么有关count中的值的说法正确的是（）。

I.肯定有不正确的结果II.肯定有正确的结果，III.若控制这些并发进程互斥执行count加1操作，count中的值正确A. I和IIIB.II和IIIC.IIID. I、II和III的说法均不正确4、若系统中有n个进程，则在阻塞队列中进程的个数最多为（）？Α. n B.n-1 C.n-2 D.15、系统中有3个不同的临界资源R1，R2和R3，被4个进程pl，p2，p3 及p4共享。

各进程对资源的需求为：pl申请RI和R2，p2申请R2和R3，p3申请R1和R3，p4申请R2。

若系统出现死锁，则处于死锁状态的进程数至少是（）。

A.1B.2C.3D.46、I/O交通管制程序的主要功能是管理（）的状态信息。

A.设备、控制器和通道B.主存、控制器和通道C.CPU、主存和通道D.主存、辅存和通道7、用户程序发出磁盘1/0请求后，系统的正确处理流程是（）A.用户程序→系统调用处理程序→中断处理程序→设备驱动程序B.用户程序→系统调用处理程序→设备驱动程序→中断处理程序C.用户程序→设备驱动程序→系统调用处理程序→中断处理程序D.用户程序→设备驱动程序→中断处理程序→系统调用处理程序8、操作系统为了管理文件，设计了文件控制块（FCB），文件控制块的建立是（）.A.在调用create（）时B.在调用open（）时C.在调用read（）时D.在调用write（）9、下列文件物理结构中，适合随机访问且易于文件扩展的是（）。

数据结构（C语言版）（第2版）习题解析揭安全李云清杨庆红编著江西师范大学计算机信息工程学院联系方式：*****************2012年12月第1章绪论1.1什么是数据结构？【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。

1.2 数据结构涉及哪几个方面？【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集合。

1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不一样，它们是否可以认作是同一个数据结构？为什么？【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，所以它们是两种不同的数据结构。

1.4 线性结构的特点是什么？非线性结构的特点是什么？【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结点，其他的每一个结点有且仅有一个前驱和一个后继结点。

而非线性结构则没有这个特点，元素之间的关系可以是一对多的或多对多的。

1.5 数据结构的存储方式有哪几种？【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。

1.6 算法有哪些特点？它和程序的主要区别是什么？【答】：算法具有（1）有穷性（2）确定性（3）0个或多个输入（4）1个或多个输出（5）可行性等特征。

程序是算法的一种描述方式，通过程序可以在计算机上实现算法。

1.7 抽象数据类型的是什么？它有什么特点？【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。

抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。

对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。

2022年华中科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-12、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序3、算法的计算量的大小称为计算的（）。

A.效率B.复杂性C.现实性D.难度4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、已知关键字序列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、已知字符串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＝28、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。

A.二叉排序树B.哈夫曼树C.AVL树D.堆9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、下列二叉排序树中查找效率最高的是（）。

2022年华中科技大学数据科学与大数据技术专业《计算机系统结构》科目期末试卷B(有答案）一、选择题1、最能确保提高虚拟存贮器访主存的命中率的改进途径是( )A.增大辅存容量B.采用FIFO替换算法并增大页面C.改用LRU替换算法并增大页面D.改用LRU替换算法并增大页面数2、计算机系统多级层次中，从下层到上层，各级相对顺序正确的应当是（）。

A.汇编语言机器级，操作系统机器级，高级语言机器级B.微程序机器级，传统机器语言机器级，汇编语言机器级C.传统机器语言机器级，高级语言机器级，汇编语言机器级D.汇编语言机器级，应用语言机器级，高级语言机器级3、下列关于虚拟存贮器的说法，比较正确的应当是( )A.访主存命中率随页面大小增大而提高B.访主存命中率随主存容量增加而提高C.更换替换算法能提高命中率D.在主存命中率低时，改用堆栈型替换算法，并增大主存容量，可提高命中率4、"从中间开始"设计的"中间"目前多数是在( )。

A.传统机器语言级与操作系统机器级之间B.传统机器语言级与微程序机器级之间C.微程序机器级与汇编语言机器级之间D.操作系统机器级与汇编语言机器级之间5、非线性流水线是指( )A.一次运算中使用流水线中的多个功能段B.一次运算中要多次使用流水线中的某些功能段C.流水线中某些功能段在各次运算中的作用不同D.流水线的各个功能段在各种运算中有不同的组合6、块冲突概率最高的Cache地址映象方式是( )A.段相联B.组相联C.直接D.全相联7、对系统程序员不透明的应当是（）A.CACHE 存储器B.系列机各档不同的数据通路宽度C.指令缓冲寄存器D.虚拟存储器8、"一次重叠"中消除"指令相关"最好的方法是( )。

A.不准修改指令B.设相关专用通路C.推后分析下条指令D.推后执行下条指令9、除了分布处理、MPP和机群系统外，并行处理计算机按其基本结构特征可分为流水线计算机，阵列处理机，多处理机和（）四种不同的结构。

得 分《数据结构》考试题（闭卷） A 卷2019年5月）题 号 一 二 三 总分 题 分 40 40 40 120得 分一、 简答题 (8小题，每题5分，共40分)1.下面一段代码的时间复杂度是（）for( i = 0; i < N; i ++){for(j = N*N; j > i; j--){for(k = 0; k < N; k = 2*k)A += B} }（A ）O(N 2)（B ）O(N 3) （C ）O(N 4)（D ）O(log 2(N)*N 3)（E ）O(log 2(N)*N 2)答案：（D ）2.设num[ col ]存放稀疏矩阵三元组M 中第col 列中非0元素个数，cpos[ col ]存放M 中第col 列的第一个非0元素在转置后三元组中的位置。

写出下列三元组中num[ col ]和cpos[ col ]的值。

答案： col 1 2 3 4 5 6 num[ col ] 1 2 1 3 1 0 cpos[ col ]124589i j v 4 6 8 1 2 2 1 4 3 2 2 -12 4 3 3 3 4 3 4 5 3 5 -24 173. 已知KMP算法的模式串以1开头，由0,1构成，NEXT 函数为01112345678，请写出模式串。

答案：10010010011（或10010010010）4. 已知8个结点1,2,3,4,5,6,7,8构成的二叉树，其先序、中序、后序序列分别如下，其中有一些模糊不清，请画出该二叉树。

先序: _ 2 3 _ 5 _ 1 8中序: 3 _ 4 7 _ _ 1 8后序: _ 4 2 _ _ 1 5 7答案：5. 给定下面的广义表A=(a,b,c), B=((a,c),(b,c,d)), C=(a,C,d), D=(A,B,(a,c)),分别给出4个广义表的表头和表尾以及广义表的长度。

答案：A=(a,b,c) 表头：a，表尾：（b, c），表长=3B=((a,c),(b,c,d)) 表头：(a,c)，表尾：（（b, c, d）），表长=2C=(a,C,d), 表头：a，表尾：（C, d），表长=3D=(A,B,(a,c)) 表头：A，表尾：（B, （a, c））, 表长=36. 假设一个有序表中有23个元素，现进行折半查找，则平均查找长度是多少？答案：应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋8×5）＝89；ASL＝89/23=3.877. 已知一有向无环图如下，请给出其所有的拓扑排序序列。