《计算机三级数据库第2章数据结构与算法填空题.doc》由会员分享，可在线阅读，更多相关《计算机三级数据库第2章数据结构与算法填空题.doc（10页珍藏版）》请在金锄头文库上搜索。
1、第2章 数据结构与算法1、已知一个待散列存储的线性表为（18,34,58,26,75,67,48,81），散列函数为h(k)=k mod 11,若采用线性探查法解决冲突，则平均查找长度为（14/9）；若采用链接法解决冲突，则平均查找长度为（13/9）。2、将一个n阶三角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A00存放于B0中。对于任意给定数组元素Aij，它应是数组B中第（2i+j-3）行的元素。3、二叉树是结点的有限集合，这个有限集合或者为空集，或者由一个根节点及两棵不相交的、分别称为根的左子树和右子树的（二叉树）组成。4、串是由零个或多个（字符）组成的。5、在一棵二叉树中
2、，度为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)=k mod 7,哈希表的地址空间为06，对关键字序列（32，13，49，55，
3、22，38，12）按线性探测法解决冲突，关键字12应存放在散列表中的地址是（5），查找关键字12需要比较的次数为（6次）。12、散列法存储中处理碰撞的方法主要有两类：拉链法和（开地址法）。13、队列是限制插入只能在表的一段进行的线性表，其特点是（先进先出）。14、设F是T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，一直T1、T2和T3的结点个数分别为n1、n2和n3，则二叉树B的根结点左子树和右子树中结点的个数分别为 【n1-1】和【n2+n3】.15、广义表和线性表的区别在于：线性表的成分都是结构上不可分的单元素，而广义表的成分既可以是单元素，又可以是有结构的 【表】。16、某二叉
4、树结点的对称序序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树对应的树林中高度最大的树的高度为【2】。17、一个算法的时间复杂性通常用数量级形式表示，当一个算法的时间复杂性与问题的规模n无关时，则表示为【O(1)】。18、算法的时间复杂性是指该算法包含【简单操作次数】的多少，它是一个算法运行时间的相对度量；一个算法的空间复杂性是指该算法在运行过程中临时占用的【存储空间】的大小。19、若一颗二叉树中只有叶结点和左、右子树皆非空的结点，设叶结点的个数为R，则左、右子树皆非空的结点个数是【R-1】。20、完全二叉树最简单、最节省空间的方式，就是把所有结点按【层次次序】一次存放在一片连续的存
5、储单元中。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，
6、24，18，8，13，25.26、若在一棵二叉排序树中叶结点的数目为6，那么树中度为2的结点数目为【5】。27、对于给出的一组权w=5,6,8,12，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为【61】。28、设有二维数组A1，101，12，其每个元素占2个字节，数据按行优先顺序存储，第一个元素的存储地址为1000，则元素A55的存储地址为【1104】。29、在双向链表中，每个结点都含有两个指针域，它们一个指向其前驱结点，另一个指向其【后继】结点。30、在一个10阶的B-树上，每个非树根结点所含的关键字数目最多允许为【9】个，最少允许为【4】个。31、设散列表的地址空间为0到18，散列函
7、数为h（k）=k mod19，用线性探查法解决碰撞。现从空的散列表开始，依次插入关键码值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，itt+1,其中t=log2n，d0=n，d1=1，n为待排序记录的个数，则
8、第二趟排序结束后，前四条记录为【（15,23,54,38）】。36、设有一个二维数组A16，14，若数组的起始地址为200，并且数据元素以行序为主序存放在数组中，每个元素占用4个存储单元，那么元素A3,4的存储地址为【260】。37、设待排序关键码序列为（25,18,9,33,67,82,53,95,12,70），要按关键码值递增的顺序进行排序，采取以第一个关键码为分界元素的快速排序法，第一趟完成后关键码33被放到了第【9】个位置。38、设根结点的层次为0，则高度为K的完全二叉树的最小结点数为（2k）。39、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以很快的速度存取线性表的数
9、据元素时，应采用（顺序）存储结构。40、在散列文件中，因为散列函数不是一对一的关系，所以选择好的散列函数和（冲突处理方法）是散列文件的关键。41、关系数据库规范化理论的研究中，在函数的范畴内，（BCNF）达到了最高的规范化程度。42、假定在有序表A1，20上进行二分查找，则比较一次查询成功的结点数为【1】，比较三次查找成功的结点数为【4】。43、用数组A1，n顺序存储完全二叉树的各结点，则当i0，且inext=（pnext）；”和“pnext=（s） ；”的操作。60、用权值集合5，6，16，8，11构造一棵霍夫曼树，那么这棵树的带权路径长度为（103）。61、如果一棵二叉树结点的前序序列是A
10、BDEC，后序序列是DEBCA，则该二叉树结点的中序序列是（无法确定）。62、线性表L=（a1，a2，an）用数组表示，假定删除表中任意元素的概率相同，则删除一个元素平均需要移动元素的个数为 （n-1）/2 。63、按行优先顺序存储下三角矩阵Ann的非零元素，则计算非零元素ij（1jin）的地址的公式为Loc(aij)=Loc(a11)+ i*(i-1)/2+(j-1) 。64、对线性表进行二分法检索，其前提条件是：线性表以 顺序 方式存储，并且按关健码值排好序。65、散列法存储的基本思想是：由结点的 关键码值 决定结点的存储地址。66、对n个记录的文件进行二路归并排序，所需要的辅助存储空间为
11、 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、数组Q1,max是一个环形队列，front为当前队头元素的前一位置，rear为队尾元素的位置。那么当fr
12、ont，rear满足条件 rear-front=0 时，环形队列为空；满足（rear+1）mod max=front 条件时，环形队列已填满。72、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分法查找关键码值20，需做的关键码比较次数是4 。73、若一棵二叉树有12个结点,那么这棵树的深度至少为(4),其能够达到的最大深度为(12)。74、在完全二叉树的顺序存储中，若结点i有右子女，则其右子女是结点（2i1）。75、设矩阵A是一个mn的整数矩阵（一个整数占两个字节），若该矩阵以行序为主序连续存放在计算机中，如果矩阵A的第一个数据a11的存放地址为2000，则第i行第j个元素aij的存放地址为（2im2m2j1998）。76、数组Q0，n1用来表示一个环形队列，f为当前队头的第一个位置，r为队尾元素的位置，假定队列中元素的个数总小于n，则计算队列中元素个数的公式为（nrf） mod n）。77、散列法存储中处理碰撞的方法主要有两类:拉链法和(开放地址法)。 78、按后根次序周游树等同于按（对称）序周游对应的二叉树。79、m阶B+树的根节
