数据结构填空题题库

111.线性结构中元素之间存在着（一对一）关系，树型结构中元素之间存在着（一对多）关系。2.评价数据结构的两条基本标准是：（存储需要量）和（运算的时间效率）。3.算法的五个特性是指（有穷性/确定性、可行性、输入和输出）。4.数据的逻辑结构是从逻辑关系上描述数据，它与数据的（存储结构）无关，是独立于计算机的。5.数据的逻辑结构包括（线性结构）和非线性结构。6.针对线性链表的基本操作有很多，但其中最基本的4种操作分别为（插入）、删除、查找和排序。7.对于长度为n的顺序存储的线性表，当随机插入和删除一个元素时，需平均移动元素的个数为（n/2）。8.在单链表中设置头结点的作用是（简化插入、删除算法）。9.访问单链表中的结点，必须沿着（指针域或next域）依次进行。10.在双向链表中，每个结点有两个指针域，一个指向（前驱结点），另一个指向（后继结点）。11.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=（p-next-next）。12.设单链表中指针P指向结点m，若要删除m之后的结点（若存在），则需修改指针的语句是：（p-next=p-next-next）。13.已知广义表A=(a,(b,(c,d))),则表尾是（((b,(c,d)))），深度为（3）。14.广义表A((a，b，c)，(d，e，f))的表头为（(a,b,c)），长度为（2）。15.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素A[I][J]，如果它能够在数组B中找到，则它应在（2*I+J位）置。16.存储稀疏矩阵的方法是多种多样的，其中的四种方法有（三元组表示法），（伪地址表示法），（带辅助行向量的二元组表示法），（行-列表示法）17.三元组表示法，每个结点包括３个字段，分别为该非零元素的（行下标）（列下标）和（值）。18.在串S=“stud”中，子串有（11）个。19.设s1=”study”,s2=”hard”,则调用函数strcat(s1,s2)后得到（studyhard）。20.设有两个串p和q，求q在p中首次出现位置的运算称做（模式匹配）21.设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为（3）。22.栈的特点是：（后进先出），栈顶的位置是随着进栈和出栈_操作而变化的。23.若有一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素为n，则第i个输出元素是（n-i+1）。24.通常程序在调用另一个程序时，都需要使用一个（栈）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。25.通常元素进栈的顺序是（先移动栈顶指针，然后存入元素）。26.通常元素出栈的顺序是（先取出栈顶元素，然后移动栈顶指针）。27.队列的特点是：（先进先出），其插入操作在（队尾）进行，删除操作在（对头）进行。28.有数据元素1、2、3，依次进队列，其出队列序列为（123）。2229.从一个循环队列中删除一个元素，通常的操作是（先取出元素，然后移动队头指针）。30.向一个循环队列中插入一个元素，通常的操作是（先存放元素，然后移动队尾指针）。31.在一棵二叉树上第8层的结点数最多是（128）32.在深度为5的满二叉树中，叶子结点的个数为（16）。33.在深度为5的满二叉树中，共有（31）个结点。34.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为（350）。35.深度为k的完全二叉树至少有（）个结点，至多有（）个结点，若按自上而下，从左到右的次序编号（从1开始），则编号最小的叶子结点的编号是（）。36.设二叉树根结点的层次为O，对含有100个结点的二叉树，可能的最大树深和最小树深分别是（）。37.深度为n的二叉树最多有（2N次方-1）个结点。38.设二叉树的根为第一层，则第i层上的结点数最多有（2i）。39.在一棵二叉树中，度为2的结点的个数是5，则叶结点的个数为（6）。40.n个结点的完全二叉树，其深度h=（log2n+1）。41.在一棵二叉树中,度为2的结点个数为8,则叶结点个数为（9）。42.已知一颗完全二叉树中共有767结点，则该树中共有（384）个叶子结点。43.200个结点的完全二叉树，其深度h=（8）。44.对有n个结点的完全二叉树，编号为i(i1)结点的双亲结点的编号为（），当i%2==0时，该结点是其双亲的（）。45.一颗有6个结点的完全二叉树，其结点按编号存放数据为：A、B、C、D、E、F，若按中根遍历该树得到的数据序列为：（DBEAFC）。46.现有按中序遍历二叉树的结果为abc，问有（5）种不同形态的二叉树可以得到这一遍历结果。47.若按（中序）遍历二叉排序树可得到一个关键字的有序序列。48.树是结点的集合，它的根结点数目是（1）。49.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（gdbehfca）。50.设树T的度为4，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则T中叶子结点的个数为（8）。51.树和二叉树的3个主要差别（树的结点个数至少为1，而二叉树的结点个数可以为0）；树中的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左右之分，而二叉树的结点有左右之分。52.从概念上说，树与二叉树是两种不同的数据结构，通过某种算法将树转化成二叉树的基本目的是（树可采用二叉树的存储结构并利用二叉树的已有的算法解决树的有关问题）。53.假定一棵树的广义表表示为A（B（E（K，L），C（G），D(H(M),I,J)））,则该树的度为（3），树的深度为（3）。554.在一棵树中，有且仅有一个结点没有前驱，称为（根）结点;非根结点有且仅有一个（双亲）。55.n个顶点的无向完全图具有（n(n-1)/2）条边，n个顶点的有向完全图具有（n(n-1)）条弧。56.n个顶点的连通图的生成树具有（n-1）条边。3357.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（n）58.行二分法查找，最大的比较次数是（log2n+1）。59.设线性表（al,a2，…，a500）元素的值由小到大排列，对一个给定的k值用二分法查找线性表，在查找不成功的情况下至多需比较（9）次。60.二分法查找的存储结构仅限于（顺序存储结构），且是有序的。61顺序查找的平均查找长度为（0（n））折半查找只适用于有序表，且限于顺序存储结构，其平均查找长度为：（0(log2n)）。62.设有100个元素，用折半查找时，最大比较次数是（7）。63.在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为（2）。64.希尔排序法属于（插入）排序。65。在对一组记录（54,38,99,23，15，72,60,45,83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（3）次。66.每次从无序子表中取出一个元素，然后把它插入到有序子表中的适当位置，此种排序方法叫做（插入）排序，每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种方法叫做（选择）排序。67.在对一组记录（10,50,25,70,35,22,30,85,40）进行直接插入排序时，当把第6个记录22插入到有序表时，为寻找插入位置需比较（2）次。68.堆排序法属于（选择）排序。69.对一组记录（50,40,95,20,15,70,60,45,80）进行简单选择排序时，第4次交换和选择后，未排序记录（即无序数）为（50,70,60,95,80）。70.假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（n(n-1)/2）。71.对n个元素的序列进行冒泡排序时，最少的比较次数是（n-1）。72.（快速堆）排序方法采用的是二分法的思想，其数据的组织采用完全二叉树结构。73。在堆排序和快速排序中，若原始记录接近正序或反序，则选用（堆排序），若原始记录无序，则最好选用（快速排序）。74.在插入和选择排序中，若初始数据基本正序，则选用（插入排序）；若初始数据基本反序，则选用（选择排序）。75.希尔排序是属于（直接插入）排序的改进方法。76.在单链表上难以实现的排序方法有（快速排序、堆排序、希尔排序）。