三级数据库填空题答案文档格式.docx

三级数据库填空题答案文档格式.docx

《三级数据库填空题答案文档格式.docx》由会员分享，可在线阅读，更多相关《三级数据库填空题答案文档格式.docx（29页珍藏版）》请在冰点文库上搜索。

单钥加密体制和（双钥）加密体制。

19、输出设备的作用是将计算机内部二进制表示形式的信息转换成人们所需要的或其他设备能接受和识别的信息形式。

20、数据库管理系统应属于系统软件。

21、计算机是由运算器、控制器、（存储器）、输入设备和输出设备这五个主要功能部件组成的，它们被称为计算机的五大硬件。

22、计算机对外部设备的输入输出有四种控制方式:

通道方式、循环测试I／O方式、中断处理方式和（直接内存存取或DMA）方式。

23、按照网络所采用的传输技术，可以将计算机网络分成广播式网络和（点-点）式网络。

24、实存储器是计算机系统配置中的实际物理存储器，通常有三类：

主存储器，外存储器和（高速缓存）。

第2章数据结构与算法

1、已知一个待散列存储的线性表为（18,34,58,26,75,67,48,81），散列函数为h（k）=kmod11,若采用线性探查法解决冲突，则平均查找长度为（3/2）；

若采用链接法解决冲突，则平均查找长度为（3/2）。

2、将一个n阶三角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。

对于任意给定数组元素A[i][j]，它应是数组B中第（2i+j-3）行的元素。

3、二叉树是结点的有限集合，这个有限集合或者为空集，或者由一个根节点及两棵不相交的、分别称为根的左子树和右子树的（二叉树）组成。

4、串是由零个或多个（字符）组成的。

5、在一棵二叉树中，度为0的结点个数为N0，度为2的结点个数为N2，则有（N0=（N2+1））。

6、在树中，一个结点的直接子结点的个数为该结点的（度）。

7、在一个双链表中，包括头结点在内共有6个结点，则共有（10）个指针。

8、链表中元素的入栈顺序是ABCD，它的出栈顺序是（DCBA）。

9、按后根次序周游树或树林等同于按（对称）次序周游对应的二叉树。

10、设有字母序列{Q,D,F,X,A,P,B,N,Y,M,C,W},请写出按归并排序方法对该序列进行一趟扫描的结构是（{D,Q,F,X,A,P,B,N,M,Y,C,W}）。

11、设哈希函数h（k）=kmod7,哈希表的地址空间为0~6，对关键字序列（32，13，49，55，22，38，12）按线性探测法解决冲突，关键字12应存放在散列表中的地址是（5），查找关键字12需要比较的次数为（1次）。

12、散列法存储中处理碰撞的方法主要有两类：

拉链法和（开地址法）。

13、队列是限制插入只能在表的一段进行的线性表，其特点是（先进先出）。

14、设F是T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，一直T1、T2和T3的结点个数分别为n1、n2和n3，则二叉树B的根结点左子树和右子树中结点的个数分别为【n1-1】和【n2+n3】.

15、广义表和线性表的区别在于：

线性表的成分都是结构上不可分的单元素，而广义表的成分既可以是单元素，又可以是有结构的【表】。

16、某二叉树结点的对称序序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树对应的树林中高度最大的树的高度为【2】。

17、一个算法的时间复杂性通常用数量级形式表示，当一个算法的时间复杂性与问题的规模n无关时，则表示为【O

（1）】。

18、算法的时间复杂性是指该算法包含【简单操作次数】的多少，它是一个算法运行时间的相对度量；

一个算法的空间复杂性是指该算法在运行过程中临时占用的【存储空间】的大小。

19、若一颗二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为R，则左、右子树皆非空的结点个数是【R-1】。

20、完全二叉树最简单、最节省空间的方式，就是把所有结点按【层次次序】一次存放在一片连续的存储单元中。

21、对有14个结点的完全二叉树的结点以从上至下、从左至右的顺序进行编号后，序号最小的叶结点序号为【8】。

22、在堆排序和快速排序中，若原始记录接近正序和反序，则选用【堆排序】；

若原始记录无序，则最好选用【快速排序】。

23、数据结构包括三方面的内容：

数据的逻辑结构、数据的存储结构、数据的【运算或操作】。

24、若线性表的长度经常发生变化，那么该线性表应采用的存储结构是【链式存储结构】。

25、设有关键码序列（17，8，3，25，16，1，13，19，18，4，6，21），要按关键码值递增的次序排序，用初始增量为【4】的希尔排序法，一趟扫描后的结果是：

16，1，3，19，17，4，6，24，18，8，13，25.

26、若在一棵二叉排序树中叶结点的数目为6，那么树中度为2的结点数目为【5】。

27、对于给出的一组权w={5,6,8,12}，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为【61】。

28、设有二维数组A[1，…，10][1，…，12]，其每个元素占2个字节，数据按行优先顺序存储，第一个元素的存储地址为1000，则元素A[5][5]的存储地址为【1104】。

29、在双向链表中，每个结点都含有两个指针域，它们一个指向其前驱结点，另一个指向其【后继】结点。

30、在一个10阶的B-树上，每个非树根结点所含的关键字数目最多允许为【10】个，最少允许为【5】个。

31、设散列表的地址空间为0到18，散列函数为h（k）=kmod19，用线性探查法解决碰撞。

现从空的散列表开始，依次插入关键码值190，89,217,208,75，则最后一个关键码75的地址为【1】。

32、m阶B树的根结点至少有【2】颗子树。

33、对一组记录的关键码（54,36,72,15,40,38,91）进行堆排序时，初始化堆后，最后4个记录为【（15,36,38,54）】。

34、散列法存储中处理碰撞的方法主要有两类：

开地址法和【拉链法】。

35、在对一组记录（54,38,96,23,15,72,60,45,83）进行希尔排序时，假定取di+1=[di/2]，i≤t≤t+1,其中t=[log2n]，d0=n，d1=1，n为待排序记录的个数，则第二趟排序结束后，前四条记录为【（15,23,54,38）】。

36、设有一个二维数组A[1…6，1…4]，若数组的起始地址为200，并且数据元素以行序为主序存放在数组中，每个元素占用4个存储单元，那么元素A[3,4]的存储地址为【260】。

37、设待排序关键码序列为（25,18,9,33,67,82,53,95,12,70），要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟完成后关键码33被放到了第【9】个位置。

38、设根结点的层次为0，则高度为K的完全二叉树的最小结点数为（2k）。

39、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以很快的速度存取线性表的数据元素时，应采用（顺序）存储结构。

40、在散列文件中，因为散列函数不是一对一的关系，所以选择好的散列函数和（冲突处理方法）是散列文件的关键。

41、关系数据库规范化理论的研究中，在函数的范畴内，（BCNF）达到了最高的规范化程度。

42、假定在有序表A[1，…，20]上进行二分查找，则比较一次查询成功的结点数为【1】，比较三次查找成功的结点数为【4】。

43、用数组A[1，…，n]顺序存储完全二叉树的各结点，则当i>

0，且i<

=【（n-1）/2】时，结点A[i]的右子女是结点A[2i+1]，否则结点A[i]没有右子女。

44、对于关键码序列18,30,35,10,46,38,5,40进行排序（假定堆根结点为最小关键码），在初始建堆过程中需要进行的关键码交换次数为【3】。

45、二叉树是结点的有限集合，这个有限集合或者为【空集】，或者由一个根结点及两棵不相交的、分别称作根的左子树和右子树的二叉树组成。

46、串的顺序存储有两种方法，分别是：

（紧缩格式）和（非紧缩格式）。

47、若采用H1=keymod11作为散列函数为关键字为（4,9,18,23,29,35,37,41,49）的数据元素构造一个散列表，并且以线性探测法处理冲突，若查找每个元素的概率相等，则每个元素的平均查找长度为（14/9）。

48、如果按照平均执行时间来看，快速排序、起泡排序、直接选择排序和直接插入排序中，（快速排序）是最优的。

49、已经某二叉树的前序序列是ABCD，中序序列是DBAC,它的后序序列是（DBCA）。

50、设一线性表中有a1,a2,`````,a500个元素按递增顺序排列，则用二分法查找给定值K,最多需要比较（9）次。

51、对于具有144个记录的文件，若采取分块查找法并且每块长度为8，则平均查找长度为（14）。

52、常用的稀疏矩阵的存储方式有三元组法和（十字链表法）。

53、在归并排序中，归并排序算法的时间复杂性为（O（nlog2n））。

54、m阶B树的根结点若不是叶结点，那么它至多有m棵子树，至少有2棵子树。

那么它的中间结点至少有（m/2）棵子树。

55、对于关键码序列1,9,7,91,24,30,40,105,92,25进行堆排序（假定堆的根结点是最小关键码），在初始建堆过程中需进行的关键码交换次数为（0）。

56、数据结构是相互之间存在一种或多种特点的关系的数据元素的集合，它包括3个方面的内容，分别是逻辑结构、存储结构和（运算）。

57、按对称序周游二叉树等同于按（后根）次序周游对应的树（林）。

58、设只包含根结点的二叉树的高度为0，则高度为K的二叉树的最小结点数为（K+1）。

59、在一个单链表中，在指针p所指向的结点之后插入指针s所指向的结点时，应执行“s—>

next=（p—>

next）；

”和“p—>

next=（s）；

”的操作。

60、用权值集合{5，6，16，8，11}构造一棵霍夫曼树，那么这棵树的带权路径长度为（103）。

61、如果一棵二叉树结点的前序序列是ABDEC，后序序列是DEBCA，则该二叉树结点的中序序列是（无法确定）。

62、线性表L=（a1，a2…，an）用数组表示，假定删除表中任意元素的概率相同，则删除一个元素平均需要移动元素的个数为（n-1）/2。

63、按行优先顺序存储下三角矩阵Ann的非零元素，则计算非零元素аij（1≤j≤i≤n）的地址的公式为Loc（aij）=Loc（a11）+i*（i-1）/2+（j-1）。

64、对线性表进行二分法检索，其前提条件是：

线性表以顺序方式存储，并且按关健码值排好序。

65、散列法存储的基本思想是：

由结点的关键码值决定结点的存储地址。

66、对n个记录的文件进行二路归并排序，所需要的辅助存储空间为O（n）。

67、对于关键码序列18，30，35，10，46，38，5，40进行堆排序（假定堆的根结点为最小关键码），在初始建堆过程中需要进行的关键码交换次数为3。

68、线性表L=（a1,a2,…an）用数组表示，假定删除表中任何一元素的概率相同，则删除一个元素平均需要移动元素的个数为（n-1）/2。

69、散列法存储的基本思想是：

由结点的关键码值决定结点的存储地址。

70、对于给出一组权w={13,14,19,20}，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为132。

71、数组Q[1,…,max]是一个环形队列，front为当前队头元素的前一位置，rear为队尾元素的位置。

那么当front，rear满足条件rear-front=0时，环形队列为空；

满足（rear+1）modmax=front条件时，环形队列已填满。

72、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分法查找关键码值20，需做的关键码比较次数是4。

73、若一棵二叉树有12个结点,那么这棵树的深度至少为（4）,其能够达到的最大深度为（12）。

74、在完全二叉树的顺序存储中，若结点i有右子女，则其右子女是结点（2i＋1）。

75、设矩阵A是一个m×

n的整数矩阵（一个整数占两个字节），若该矩阵以行序为主序连续存放在计算机中，如果矩阵A的第一个数据a11的存放地址为2000，则第i行第j个元素aij的存放地址为（2im－2m＋2j＋1998）。

76、数组Q〔0，…，n－1〕用来表示一个环形队列，f为当前队头的第一个位置，r为队尾元素的位置，假定队列中元素的个数总小于n，则计算队列中元素个数的公式为（（n＋r－f）modn）。

77、散列法存储中处理碰撞的方法主要有两类:

拉链法和（开放地址法）。

78、按后根次序周游树等同于按（对称）序周游对应的二叉树。

79、m阶B+树的根节点至少有

（2）个子女。

80、设有而为组A[0...9][0...19,]其每个元素占两个字节，数组按列优先顺序存储，第一个元素的存储地址为100，那么元素A[6,6]的存储地址为（232）。

81、设有关键码序列（17，8，3，25，16，1，13，19，18，4，6，21），要按关键码值递增的次序排列，用初始增量为4的希尔排列法，一趟扫描后的结果是（16,1,3,19,17,4,6,21,18,8,13,25）。

82、对于一个线性表经常进行的是存取操作，很少进行插入和删除操作时，则采用顺序存储结构为宜；

相反，当经常进行插入和删除操作时，则采用链接存储结构为宜。

83、数据结构包括三个方面的内容是：

数据的（逻辑结构），数据的存储结构，数据的运算。

第3章操作系统

1、为使多个进程有效地同时处理输入和输出，最后使用（缓冲池）结构的缓冲技术。

2、线程的引用使得操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统的（吞吐量）。

3、从工作特性的角度可将设备分类为（I/O）设备和存储设备。

4、虚拟设备是通过（SPOOLing）技术，把独享设备变成能为若干用户共享的设备。

5、系统中有N个进程，则进程就绪队列中最多有（N-1）个进程。

6、原语相对一般广义指令的主要区别是：

（原语的不可分割性）。

7、空闲块表方式特别适合于文件物理结构为（顺序结构）的文件系统。

8、在存储管理中，为实现地址映射，硬件应提供两个寄存器：

一个是基址寄存器，另一个是（限长寄存器）。

9、在多道程序设计中，为了保证系统的安全，将指令系统中的指令分为（特权指令）和非（特权指令）两部分。

10、可变分区的主存分配算法有（最先适应算法）、最佳适应算法和最坏适应算法。

11、系统为了管理文件，设置了专门的数据结构（文件控制块）（FCB）。

FCB是执行创建文件系统调用时建立的。

12、进程创建工作主要完成的是创建进程控制块（PCB），并把它挂到（就绪）队列中。

13、进程之间的联系称之为进程通信，（通信原语）是进程通信的工具。

14、在页式存储管理中，用户程序的逻辑地址由（逻辑页号）和页内地址两部分组成。

15、在页式存储管理中，存放在高速缓冲存储器中的部分页表成为（块表）。

16、文件目录是（文件控制块）的有序集合。

17、在使用OPEN命令打开文件时，同时要给出文件的（读写方式）。

18、在多级目录结构中查找一个文件时需要按路径名搜索，当层次较多时要耗费很多时间，为此要引入【当前目录】。

19、在请求页式管理中，当硬件地址变换机构发现所需的页不在内存时，会产生【缺页】中断信号，由中断处理程序做出相应的处理。

20、及时响应是【分时系统或分时操作系统】和实时操作系统的特征。

21、文件目录是【文件控制块（FCB）】的有序集合。

22、死锁的四个必要条件是【互斥条件】、【部分分配（占有等待）】、不可剥夺和循环等待。

23、不让死锁发生的策略可以分成静态和动态两种，死锁预防属于【静态的】。

24、一些进程相互合作共同完成同一项任务，进程之间的这种直接的协同工作的关系称为【进程同步或同步】。

25、在操作系统的存储管理中，存储共享的两个目的是【节省内存空间】和实现进程通信。

26、虚拟页式存储管理中，当内存空间已经被占满而又要调入新页时，必须进行页面淘汰。

页面淘汰算法包括：

最佳淘汰算法（OPT）、【先进先出淘汰算法（FIFO）】、最近最少使用淘汰算法（LRU）和最不经常使用淘汰算法（LFU）。

27、系统中有些资源一次只允许一个进程使用，这类资源称为【临界资源】。

28、当进程完成I/O后，进程由等待状态变为【就绪】状态。

29、用于生产过程控制的系统一般都是实时系统，它要求具有对输入数据【及时或立即】作出反应（响应）的能力。

30、一个程序在一个数据集合上的一个执行过程称为【进程】，它是系统进行资源分配的独立单位。

31、【文件控制块FCB】是系统为管理文件而设置的一个数据结构。

它记录了系统管理文件所需要的全部信息。

32、在文件系统中，文件的逻辑结构可分为两类，它们是流式文件和【记录式】文件。

33、为保证文件系统的安全性，备份是常用的措施。

备份常用的方法有海量转储和【增量】。

34、死锁产生的原因是系统资源不足和【进程推进速度不合理】。

35、虚拟存储管理系统中，在进行地址映射时，若所需页面不在内存，则产生【缺页】中断。

36、在一类设备上模拟另一类设备，例如用高速磁盘模拟慢速打印机，则被模拟的设备称为【虚设备或虚拟设备】。

37、抖动是由【缺页率或页面淘汰算法不合理】引起的。

38、把【逻辑地址】转换为【绝对地址】的工作称为地址转换或重定位。

地址转换可分为两类：

静态地址转换和动态地址转换。

39、进程对主存的访问往往具有局部性，即（时间）局部性和（空间）局部性。

40、在进程创建时先赋予进程一个初始优先数，以后在进程运行过程中不断修改优先数，用这种方法设置的优先数称为（动态优先数）。

41、按性质和用途分类，文件可为系统文件、（库文件）及用户文件。

42、从静态的观点看，操作系统中的进程是由程序、数据和（进程控制块）三部分组成。

43、批处理系统有两个特点：

一个是【多道】，另一个是【成批】。

前者是指系统内可以同时存在多个作业，后者是指在系统运行过程中不允许作业与其他作业发生相互作用。

44、中断装置发现中断后，通过交换（中断向量或程序状态字或PSW）引出中断处理程序。

45、用户程序调用操作系统有关功能的途径是（利用系统调用命令）。

46、进程被创建后，最初处于（就绪）状态，然后经进程调度程序选中后进入运行状态。

47、当用户申请打开一个文件时，操作系统将该文件的文件控制块保存在内存的（系统打开文件）表中。

48、（及时响应）是分时系统和实习操作系统的特征。

49、在单CPU系统中，如果同时存在12个并发进程，则处于就绪队列中的进程最多有（11）个。

50、文件系统中，当用户进程打开一个文件时，操作系统将该文件的文件描述符保存在内存的（用户打开文件）表中。

51、访问磁盘时，当磁头到达指定磁道后，必须所需要的扇区到达读写头下，这一部分时间称为（延迟）时间。

52、虚拟存储管理的效率与程序局部性程度有很大关系，进程运行时，在一段时间内程序的执行呈现出高度的（时间局部性）和（空间局部性）。

53、文件的逻辑结构可分为两类：

流式文件和记录式文件。

54、当一个进程由于等待某事件的发生而不能运行时，称此进程处于等待。

55、在页式管理中，存储页面表的作用是记录内存页面的分配情况，存取页面表的结构有三种方法：

位示图、空闲页面表和空闲页面链表。

56、一个具有独立功能的程序独占CPU直接得到最终结果的顺序执行过程具有三个基本特点：

数序性、封闭性和再现性。

57、进程之间相互协调，彼此之间交换信息，这就是进程间的通信。

当系统中各进程并发共享资源，从而使系统资源得以充分利用，这往往表现为进程的同步。

系统中许多进程需共享资源，而资源需要排他性使用，进程之间相互作用构成进程互斥。

58、每个中断处理程序都有一个入口地址（PC）及其运行环境（程序状态字），它们被称为中断向量，保存在内存中固定的单元。

59、对于多个进程共享的公共区域提供访问限制和访问检查，是为了防止操作越权。

60、一个进程在运行过程中可能与其他进程产生直接的或间接的相互作用，进程的这一特性称为交往性。

61、一般将中断源分为强迫性中断和自愿性中断两大类。

62、线程是进程中的一个执行实体，每个线程有唯一的标识符和一张线程描述表。

63、（分时操作系统）允许多个用户同时使用计算机，操作系统接收每个用户在最终端发出的命令，采用时间轮转的方式处理用户的服务请求。

64、从资源分配的角度可将设备分为（独占设备）、共享设备和虚拟设备。

65、按照资源的使用性质，一般把系统中的资源分为两大类：

永久性资源和（临时性资源）。

66、所谓原语是有若干条（机器指令）构成的一段程序，用以完成特定的功能。

67、用户程序经过编译之后的每个目标模块都是以0为基地址顺序编址，这种地址称为（逻辑地址）。

68、把多个输入和多个输出缓冲区统一起来,形成一个既能用于输入,又能用于输出的缓冲区。

该缓冲区称为（缓冲池）。

69、交换技术又称为对换技术（swapping）,这种技术多用于（分时系统）。

70、重定位技术分为静态重定位和动态重定位，两者最显著的区别是（重定位时机）不同。

71、死锁的产生与各并发过程的相对速度有关，产生死锁的必要条件为互斥条件、（不可剥夺条件）、不分分配和循环等。

72、解除死锁常常采用两种可行的办法：

资源剥夺法和撤销进程法。

73、CPU工作方式有目态和管态两种。

目态是指运行用户程序，管态是指运行操作系统程序。

执行编译程序时，CPU处于目态。

74、对未提交修改的封锁必须保持到事务的终点。

75、如果资源分配图中有回路，则系统中（可能或不一定）发生死锁。

76、从数据组织方式的角度可将设备分为块设备和字符设备。

第4章数据