数据结构 填空题

1、数据结构习题库之二：填空题若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的数据元素前，需要先依次移动 个数据元素。在非空双向循环链表中由q所指的那个链结点后插入一个由p指的链结点的动作对应的语句依 次为：p-prior=q; p-next=q-next; q-next=p;。（空白处为一条赋值语句）已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地 址为 LOC（a1），那么，LOC（ai）=。 具有2000个结点的二叉树，其深度至少为。 具有n0个叶结点的哈夫曼树（Huffman）的分支总数为。 若连通图的顶点个数为n，则该图的生成树的边数为。在

2、序列（2，5，8，11，15，16，22，24，27，35, 40）中采用折半查找（二分查找）方法查找元素24,需要进行 次元素之间的比较。 索引文件中的索引表是提供的，并且索引表的表项按有序列排列。 对具有n个元素的任意序列采用插入排序法进行排序，整个排序过程中要进行次元 素之间的比较。 插入排序法、选择排序法、拓扑排序法与归并排序法中，不是内排序方法。在一个图中，所有顶点的度数之和等于所有边的数目的倍。 图的深度优先搜索方法类似于二叉树的遍历。数据文件最重要的操作除了插入、删除、修改和查找外，还 。将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一个一维数组中，然后采

3、用折半查找方法查找元素12,被比较过的数组元素的下标依次为。在索引表，若一个索引项对应基本数据中一条记录，则称此索引为稠密索引；若索引表中一个索引对应基本数据中的若干记录，则称此索引为索引。每趟排序从未排序的子序列中依次取出元素与已经排好序的序列中元素进行比较，然后将其放在已经排好序的序列的合适位置。这种排序法称为 排序法。从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一 部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为 排序法。希尔排序法、快速排序法、堆积排序法和二路归并排序法四种排序法

4、中，要求辅助空间最多 TOC o 1-5 h z 的是。对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序，以序列的第一个元素为基准元素得到的划分结果是。数据结构课程讨论的主要内容是数据的逻辑结构、存储结构和。若频繁地对线性表进行插入与删除操作，该线性表应采用存储结构。若链结点的构造为datalnext，那么，判断由list所指的单向循环链表中只有一个结点的条件是 求串T在主串S中首次出现的位置的操作是。完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是。一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一 。在序列(2,5,8,

5、11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要进行次元素之间的比较。若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=key MOD 9,与18发生冲突的元素有个。每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换位置，这种排序方法成为排序法。排序过程中所进行的元素之间的比较次数与参加排序的序列的初始状态无关的排序方法是 排序法。若堆栈采用顺序存储结构，在不产生溢出的时候往堆栈中插入一个新元素，首先，然后再。在一棵二叉树中有n0个叶结点，有n2个度为2的结点，则n0=。 索引文

6、件包括 和 两部分，而且是按照关键字值有序排列的。对具有n个元素的序列采用插入排序法和选择排序法，排序趟数均为，而采用泡排序 法进行排序，排序趟数是一个范围。一般情况下，将一个递归算法变换成等价的非递归算法主要设 机制。循环单链表与循环非循环单链表的主要不同是。若具有n个结点的非空二叉树采用二叉链表存储结构，该链表一共有个指针域，其中个指针域存放非空指针，有个指针域存放空指针(nil)。 具有n个顶点的无向图的边数最多为，具有n个顶点的有向图的边数最多为在散列文件(Hash文件)中，处理冲突的方法通常有、 三种。 数据结构课程研究的主要内容包括、三方面。 在长度为n的线性表A的第i个位置插入一

7、个新元素的过程应该首先， 然后，最后。(1WnWn+1)若具有n个结点的二叉树采用二叉链表结构，则该链表中共有个指针域，其中个指针域用于链接孩子结点，个指针域存放nil。 TOC o 1-5 h z 对具有n个元素的序列采用堆积排序法进行排序，排序趟数为。快速排序在平均情况下的空间复杂度为。 若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为。 具有n个结点的非空二叉排序树的最小深度为。 深度为h且有个结点的二叉树称为满二叉树。(设根结点处在第1层)。二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B， G， D， H，其后序遍历序列为。已知序列(

8、34, 76, 45，18, 26, 54, 92, 65,)，按照逐点插入法建立一棵二叉排序列树，该树的深度是。一个不带有权的有向图采用邻接矩阵存储方法，其邻接矩阵是一 。带权连通图 G=(V,E)，其中 V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v4)6, (v1,v4)9, (v2,v3)8, (v2,v4)4, (v2,v5)4, (v3,v4)6, (v4,v5)2,(注：顶点偶对右下角的数据为边上的权值)，G的最小 生成树的权值之和为。在线性表中采用折半查找法(二分查找法)查找一个数据元素，线性表中元素应该按值有序，并且采用存储方法。52.若对序列(49, 3

9、8, 65, 97, 76, 13, 27, 50)采用选择排序法排序，则第三趟结束后序列的状 态是。设某非空单链表，其结点形式为datalnext,若要删除指针q所指结点的直接后继结点，则需 执行下列语句序列：p=q-next; delete p; 队列可以看成是一种运算受限制的线性表，也称为 线性表。在非空树上，没有直接前趋。 设有33个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有个结点。 无向图中的连通分量定义为无向图的。在开散列表上查找键值等于K的结点，首先必须计算该键值的，然后再通过指针查找该结点。对静态表顺序查找算法采用设置岗哨方式与普通的设置循环控制变量相比，进行一次查找所 花

10、费的平均时间大约减少。若要对某二叉排序树进行遍历，保证输出的所有结点键值序列按递增次序排列，应对该二叉树采用 遍历法。文件的基本存取单位是。设需将一组数据按升序排序。在无序区中依次比较相邻两个元素ai和ai+1的值，若ai的值 大于ai+1的值，则交换ai和ai+1。如此反复，直到某一趟中没有记录需要交换为止，该排序方 法被称为。在插入排序、快速排列、堆排序、归并排序中，排序方法不稳定的 。 抽象数据类型的特点是将和封装在一起，从而现实信息隐藏。 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需一个位置。 在队列中，允许进行插入操作的一端称为，允许进行删除操作的一端称为。 设 S1=

11、good”,S2= ,S3=book”，则 S1, S2 和 S3 依次联接后的结果是。已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含 有的叶子结点的数目为。每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做排序。如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用 较为适当。假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的 形式表达为。用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是 TOC o 1-5 h z 和；若只设尾指针，则出

12、队和入队的时间复杂度分别是和。深度为h的完全二叉树至少有 个结点；至多有 个结点；h和结点总数n之间的关系是。 在n个记录的有序顺序表中进行折半查找，最大的比较次数 。n个顶点的连通图用邻接距阵表示时，该距阵至少有个非零元素。 假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为。 串 S= I am a worker”的长度是。假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为在n个结点的线索二叉链表中，有个线索指针。若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间

13、复杂度 为。对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为由10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的 最大值可能达到。 TOC o 1-5 h z 在线性表的单链接存储结构中，每个结点包含有两个域，一个口 域，另一个叫 域。 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度 ，在 表尾插入元素的时间复杂度为。 对于一个长度为n的单链接存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。在线性表的顺序存储中，若一个元素的下标为i,则它的前驱元素的下标为，后继元素的下标为。87 .在线

14、性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为，若假定p为一个数组a中的下标，则其后继结点的下标为。88、 在循环单链表中，最后一个结点的指针指向 结点。89、 在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向其 结点。90、 在循环双向链表中表头结点的左指针域指向结点，最后一个结点的右指针域指向 结点。91、若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为。92、 在程序运行过程中不能扩充的数组是分配的数组。这种数组在声明它时必须指 定它的大小。93、将一个n阶三对角矩阵A的三条对角线

15、上的元素按行压缩存放于一个一维数组B中，A00 存放于B0中。对于任意给定数组元素A I J ，如果它能够在数组B中找到，则它应在 位置。94、 队列的插入操作在 进行，删除操作在进行。95、设有一个顺序栈S，元素S1，S2, S3, S4，S5, S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为。96、 通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的 局部变量、形式参数的存储空间以及返回地址。97、 在一棵树中，结点没有前驱结点。98、一棵树的广义表表示为a （b （c，d （e，f），g （h），I （j，k （x，y）

16、，结点k的所有祖先的结点数为 个。99、根据一组记录（56, 42, 50，64, 48）依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当插入到值为 的结点时需要进行旋转调整。100、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为和。101、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 、和 三项。在稀疏矩阵所对应的三元组线性表中，每个三元组元素按 为主序、为辅序的次序排列。 队列的插入操作在进行，删除操作在进行。 栈又称为表，队列又称为表。 在一个循环顺序队列Q中，判断队空的条件为，判断队满的条件为 在一个顺序栈中，若栈顶指针等于，则为空

17、栈；若栈顶指针等于， 则为满栈。在一个链栈中，若栈顶指针等于NULL，则为；在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为或该队列为。 向一个链栈插入一个新结点时，首先把栈顶指针的值赋给，然后把新结点的 存储位置赋给。假定front和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件为 。中缀算术表达式3+4/(25-(6+15)*8所对应的后缀算术表达式为。后缀算术表达式24 8 + 3 * 4 10 7 - * /所对应的中缀算术表达式为，其值 为。 对于一棵具有n个结点的树，该树中所有结点的度数之和为。 一棵深度为5的满二叉树中的结点数为个。在一棵二叉树中，

18、假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为 个。 对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为，右孩 子结点的编号为，双亲结点的编号为。 在一棵二叉树中，第5层上的结点数最多为。 假定一棵二叉树的结点数为18,则它的最小深度为，最大深度为。假定一棵二叉树顺序存储在一维数组a中，则ai元素的左孩子元素为，右孩 子元素为，双亲元素(i1)为。 对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为 个，其中 个用于指向孩子结点，个指针空闲着。在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。 对一棵二叉搜索树

19、进行中序遍历时，得到的结点序列是一 。从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明，若元素的值小于根结点的值，则继续向 查找，若元素的大于根结点的值，则继续向查找。 在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为，右 孩子元素的下标为。在一个小根堆中，堆顶结点的值是所有结点中白，在一个大根堆中，堆顶结点 的值是所有结点中的。 当从一个小根堆中删除一个元素时，需要把 素填补到 位置，然后再按条件把它逐层调整。 在一个图中，所有顶点的度数之和等于所有边数的倍。 在一个具有n个顶点的无向完全图中，包含有条边，在一个具有n个顶点的有向完全图中，包含有 条边。

20、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要条边。对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为。对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为 和 条。对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为 和。对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为，对用邻接表表示的图进行任一种遍历时，其时间复杂度为。对于下面的无向图G1，假定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得 到的顶点序列为，从顶点v0开始进行广度优先搜索遍历得到的顶点序列为对于下面的有向图G2,假

21、定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得 到的顶点序列为，从顶点v0开始进行广度优先搜索遍历得到的顶点序列为对于下面的带权图G3，其最小生成树的权为。对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为和 以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为， 时间复杂度为。 以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为。从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时，其查找长度分别为和。在线性表的 存储中，无法查找到一个元素的前驱或后继元素。在线性表的 存储中，对每一个元素只能采用顺序

22、查找。在线性表的散列存储中，处理冲突有和 两种方法。对于线性表(18,25,63,50,42,32,90)进行散列存储时，若选用H(K)=K % 9作为散列函数，则散列地址为0的元素有 个，散列地址为5的元素有 个。144 .每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端， 此种排序方法叫做排序。每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做排序。 在直接选择排序中，记录比较次数的时间复杂度为，

23、记录移动次数的时间复 杂度为。在堆排序的过程中，对n个记录建立初始堆需要进行次筛运算，由初始堆到堆排序结束，需要对树根结点进行 次筛运算。 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度 ，整个堆排 序过程的时间复杂度为。149 .假定一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序方法建立的初始堆为150,快速排序在平均情况下的时间复杂度为，在最坏情况下的时间复杂度为151,假定一组记录的排序码为(46,79,56,38,40,80),对其进行快速排序的一次划分的结果为在二路归并排序中，对n个记录进行归并的趟数为。 对20个记录进行归并排序时，共需要进行趟归并，

24、在第三趟归并时是把长度为的有序表两两归并为长度为的有序表。假定一组记录的排序码为(46,79,56,38,40,80),对其进行归并排序的过程中，第二趟归并后 的结果为。已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的 地址为 LOC(a1)，那么，LOC(ai)=。含有3个2度结点和4个叶结点的二叉树可含个1度结点。含有2n个结点的二叉树高度至少是，至多是(仅含根结点的二叉树高度为零)。用起泡法对n个关键码排序，在最好情况下，只需做次比较和 次移动；在最坏的情况下要做 次比较。数据结构的存储结构包括顺序、索引和散列等四种。在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。如果一个对象部分地包含自己，或自己定义自己，则称这个对象 的对象。一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有 子女。向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的 上。在对一组记录关键字(54，38，96，23，15，72，60，45，83)进行冒泡排序时，整个冒泡排序过程中需进行 趟才能完成。将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A00存放于B0中。对于任意给