发布时间 : 星期二 文章中国石油大学数据结构试题及答案更新完毕开始阅读
二、 填空题（）
1、 数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构 四种 2、 数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构 四种 3、一种抽象数据类型包括（数据 ）和（操作 ）两个部分。
4、设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配） 5、 栈、队列逻辑上都是（线性存储）结构。
6、 线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关
系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。 7、栈中存取数据的原则（ 后进先出），队列中存取数据的原则（ 先进先出 ）
8、串是由（ 零个或多个）字符组成的序列。（ 长度为零的串 ）称为空串，（ 由一个或多个空格组成的串）称为空格串。
9、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第（6）次匹配成功。 10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组A[m][n],若采用按行优先存放的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（ n*i+j）。
11、向一个顺序栈插入一个元素时，首先使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写 ）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。
12、在一个循环队列Q中，判断队空的条件为（Q.front= =Q.rear）, 判断队满的条件为（ (Q.rear+1)%MaxSize= =q.front ）
13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（ n-1 ）。 14、一棵高度为5的满二叉树中的结点数为（ 63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。
15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为（ 2*i+1），右子女结点为（ 2*i+2 ），双亲结点（i>=1 ）为（「(i-1)/2 ┐ ）.
16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。
17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。 18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（ 4 ）个字符编码。
19、设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若
设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（ 2h+1 ）个。
20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。 21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。
22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235） 23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。
24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（ ５ ），判定树中前５层的结点数为（３１），最后一层的结点数为（１９）。
25、在一个无向图中，所有顶点的度数之和等于所有边数的（２）倍。在一个具有n个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n个顶点的有向完全图中，包含有（ n(n-1) ）条边。
26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和（n-1）。
27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是( 1044)。
28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序，则最好选择（选择排序）。
29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。
30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n）
31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。
32、处理冲突的三种方法，分别为(线性探测)、（ 随机探测 ）、（ 链地址法）。 33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ Ｏ（n2） ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（Ｏ（elog2e） ）
34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog2n）），在最坏情况下的时间复杂度为（Ｏ（n2））；快速排序在平均情况下的空间复杂度为（Ｏ（log2n）），在最坏情况下的空间复杂度为（Ｏ（n））。
35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行归并排序的过程中，第二趟排序后的结果是（［３８ ４６ ５６ ７９］［４０ ８０］）
36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行快速排序的第一次划分的结果是（［３８ ４０］４６［５６ ７９ ８０］）。 37、一个结点的子树的（ 个数 ）称为该结点的度。度为（ 零 ）的结点称为叶结点或终端结点。度不为（ 零 ）的结点称为分支结点或非终端结点。树中各结点度的（ 最大值 ）称为树的度。
38、设Ki=Kj (1<=i<=n, 1<=j<=n,j<>i)且在排序前的序列中Ri领先于Rj (i 40 、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（Ｏ（log2n）），整个排序过程的时间复杂度为（Ｏ（nlog2n））。 41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。 42、假定一个线性表为 （”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”）,若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为（３），（３），（２）。 43、对于包含５０个关键码的３阶B-树，其最小高度为（４），最大高度为（５）。 44、从一棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减１） 45、假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表的长度平均为（５）。 46、在散列存储中，装载因子α又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于（n/m）。 47、在有向图的邻接矩阵中，第i行中“1”的个数是第i个顶点的（出度），第i列中“1”的个数是第i个顶点的（入度）。在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的（度），矩阵中“1”的个数的一半是图中的（边数）。 48、在对m阶B-树中，每个非根结点的关键码数最少为（「m/2┐-1）个，最多为（m-1）个，其子树棵数最少为（「m/2┐），最多为（m）。 三、 判断题 四、运算应用题 1、在一个有n个元素的顺序表的第i个元素（1 ? i ? n）之前插入一个新元素时，需要向后移动多少个元素？