数据结构填空题集锦

《数据结构填空题集锦》由会员分享，可在线阅读，更多相关《数据结构填空题集锦（14页珍藏版）》请在金锄头文库上搜索。

1、数据结构填空题集锦1. 数据结构是指数据及其相互之间的 联系。当结点之间存在M对N (M： N)的联系时，称这种结构为图或者是图的结构2. 队列的插入操作是在队列的进行，删除操作是在队列的首 进行。3. 当用长度为N的数组顺序存储一个栈时，假定用top=N表示栈空，则表示栈满的条件是 top=0 (要超出才为满)。4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为0(1)，在表 尾插入元素的时间复杂度为0(n)。5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7，列下标j从0 到3，贝I二维数组W的数据元素共占用理个字节。W中第6行的元素和第4列的元素

2、共占用个字节。若按行顺序存放二维数组W，其起始地址为100,则二维数组元素W6, 3的起始地址为108。6广义表A= (a,(a,b),(a,b),c),则它的深度为丄，它的长度为丄。7. 二叉树是指度为2的 有序树。一棵结点数为N的二叉树，其所有结点的度的总和是 n-1。8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个有序序列有序列表。对一 棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的_后缀表 达式后缀表达式(或列波兰式)。9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为2n个，其中n-1 个用于指向孩子, n+1个指针是空闲的。10若

3、对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A 中，即编号为0的结点存储到A0中。其余类推，则A i 元素的左孩子元素为2加一， 右孩子元素为2加二 ，双亲元素为 (i-1) /2 。11. 在线性表的散列存储中，处理冲突的常用方法有开放地址法和 链接法 两种。12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_快速排序；当 待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用 并归排序。1. 通常从四个方面评价算法的质量：正确性、易读性、强壮性 和 高效性。2. 一个算法的时间复杂度为(n3+n21og2n+14n)/n2，其数量级表示为

4、O (n)。3. 假定一棵树的广义表表示为A (C, D (E, F，G), H (I, J),则树中所含的结点数为 9 个，树的深度为3 ，树的度为。4. 后缀算式9 2 3 +- 10 2 / -的值为-1。中缀算式(3+4X) -2Y/3对应的后缀算式为3 4 X* 2 Y * 3 / -。5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有2n个指针域，其中有_n-1个指针域是存放了地址，有_n+1个指针是空指针。6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_e个和_2e

5、个。7. AOV网是一种有向无回路的图。8. 在一个具有n个顶点的无向完全图中，包I含有n(n-1)/2 条边，在一个具有n个顶 点的有向完全图中，包含有n(n-1) 条边。9假定一个线性表为(12,23,74,55,63,40),若按Key % 4条件进行划分，使得同一余数的元素 成为一个子表，则得到的四个子表分别为(12,40)、_( )、_(_74)和(23,55,63)。10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂,则新树比原树的高度增加1。11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为O (log2 n) _ ,整个 堆排序过程的时间复杂度为O (

6、nlog2 n)。12. 在快速排序、堆排序、归并排序中，归并排序是稳定的。1、 数据的逻辑结构被分为集合、_线性、树和图四种。2、 一种抽象数据类型包括数据描述和操作声明两个部分。3、在下面的数组a中链接存储着一个线性表，表头指针为ao.next，则该线性表为.(38,56, 25, 60, 42, 74)。4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为HLnext =NULL和HL=HL_next； 。5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的 前一个位置，该循环队列的最大长度为n-1。6、当堆栈采用顺序存储结构时，

7、栈顶元素的值可用S.stack S.top表示：当堆栈采用链接 存储结构时，栈顶元素的值可用 HSdata表示。7、 一棵高度为5的二叉树中最少含有5个结点，最多含有31个结点；8、 在图的邻接表中，每个结点被称为边结点，通常它包含三个域：一是邻接点域：二是权域:三是链域。9、 在一个索引文件的索引表中，每个索引项包含对应记录的索引值域和开始位置域两项数据。10、假定一棵树的广义表表示为A (B (C, D (E, F, G), H (I, J),则树中所含的结点数为10个，树的深度为3，树的度为3,结点H的双亲结点为b，孩子结点为 i和J。11、 在堆排序的过程中，对任一分支结点进行筛运算的

8、时间复杂度为O (log2n)整个 堆排序过程的时间复杂度为 O(nlog2n)。12、在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项(叶子结点中的索 引项为关键字和空指针)后，若该结点的索引项数等于 M_个，则必须把它分裂为 M-1 个结点。16. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储（或存储结构）无关，是 独立于计算机的。17. 在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用 p 表示为 head= pnextnext。18. 栈顶的位置是随着 进栈和退栈 操作而变化的。19. 在串S= “structure”中，以t为首

9、字符的子串有12 个。20假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B0存储 矩阵中第1个元素al, 1,则B31中存放的元素是a4,8。21. 已知一棵完全二叉树中共有768结点，则该树中共有_J84个叶子结点。22. 已知一个图的广度优先生成树如右图所示，则与此相 应的广度优先遍历序列为。23. 在单链表上难以实现的排序方法有快速排序和 堆排序.希尔排序 。24在有序表（12, 24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字 比较次数为。25多重表文件和倒排文件都归属于多关键字 文件。五1设顺序循环队列Q0： m-1的队头指针和队尾指针分

10、别为F和R,其中队头指针F指向当 前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =_(F+1) % m；。2. 设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为0(n)，在链式存储结构上实现顺序查找的平均时间复杂度为0(n)。3. 设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有2n 个指针域，n+1个空指针域。4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面 插入结点B的操作序列为 s-next=p-next; s-next=s 。5. 设无向图G中有n个顶点和e条边，

11、则其对应的邻接表中有n个表头结点和2e个表结点。6. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m,则e和m有_m=2e关 系。7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为_cba。8. 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是4，编号为8的左孩子结点的编号是16。9. 下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。int index(char s , char t)i=j=O;while(ivstrlen(s) & jvstrlen(t) if(

12、si=tj)i=i+l; j=j+l;elsei=_i-j+1; j=0;if (j=strlen(t)return(i-strlen(t);else return (-1);10. 设一个连通图G中有n个顶点e条边，则其最小生成树上有n-1条边。1. 为了能有效地应用HASH查找技术，必须解决的两个问题是 构造一个好的HASH函数和 。2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedef struct int s100; int top; sqstack;void push(sqstack & stack,int x)if (stack.top=m-l) pri

13、 ntf(“ overflow”)；1. else stack.top+;stack.sstack.top=x;3. 中序遍历二叉排序树所得到的序列是有序序列(填有序或无序)。4. 快速排序的最坏时间复杂度为 O(n2)，平均时间复杂度为 O(nlog2n)。5. 设某棵二叉树中度数为0的结点数为NO,度数为1的结点数为N1,则该二叉树中度数为2的结点数为N0-1；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_2N0+N1个空指针域。2. 6.设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=_d/2_。7. 设一组初始记录关键字序列为(55, 63, 44, 38

14、, 75，80, 31，56)，则利用筛选法建立的初始堆为(31, 38, 54, 56, 75, 80, 55, 63)。v - 3- 2- 41v - 1- 32v - 1- 4- 238. 设某无向图G的邻接表为v4- 1- 3,则从顶点V1开始的深度优先遍历序列为(1, 3, 4, 2)；广度优先遍历序列为(1, 3, 2, 4)。七1. 数据的物理结构主要包括顺序存储结构 和链式存储结构两种情况。2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为9；若用二叉链表作为该完全二叉树的存储结构，则共有501个空指针域。3. 设输入序列为1、2、3,则经过栈的作用后可以得到5种不同的输出序列。4. 设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的出度，第i列上所有元素之和等于顶点i的入度。5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有_0_个度数为1的结点。6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为e=d。7. 中序遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X,则最多需要比较 7次就可以断定数据元素X是否在查找表中。9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂