数据结构填空题.pdf

一、填空题一、填空题(每空每空1 1分分,共共156156分分)1.数据结构的存储结构包括顺序、索引和散列等四种。【答案】链接【答案】链接2.设关键字序列7,12,26,30,47,58,66,70,82,90，当用折半查找方法查找时，所需比拟的次数为3次的关键字分别是。【答案】【答案】7 26 58 827 26 58 823.假定一个线性表为 12,23,74,55,63,40,82,36，假设按key%3条件进行划分，使得同一余数的元素成为一个子表，那么包含74的子表长度为。【答案】【答案】2 24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对()()结构也无特殊要求。【答案】【答案】存储存储5.设双向循环链表每个结点结构为(data,llink,rlink),那么结点*p的前驱结点的地址为()()。【答案】【答案】p-llinkp-llink6.n个顶点的连通无向图的生成树含有()()条边。【答案】n-17.在一个最大堆中，堆顶结点的值是所有结点中的()()。【答案】最大值【答案】最大值8.假定对长度n=50的有序表进行折半搜索，那么对应的判定树中最底下一层的结点数为个。【答案】【答案】19199.对于带头结点的链栈top，取栈顶元素的操作是。【答案】*y=top-next-data10.假定一棵三叉树即度为3的树的结点个数为50，那么它的最小高度为。假定树根结点的深度为0。【答案】【答案】4 411.二维数组是一种非线性结构，其中的每一个数组元素最多有()()个直接前驱或直接后继。【答案】两个【答案】两个12.在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为()()。【答案】【答案】O(logO(log2 2n)n)13.队列的删除操作在进行。【答案】队头或队首【答案】队头或队首14.设图G=(V,E)，V=1,2,3,4,E=,，从顶点1出发，对图G进行广度优先搜索的序列有()()种。【答案】【答案】2 215.向一棵二叉搜索树中插入一个元素时，假设元素的值小于根结点的值，那么应把它插入到根结点的上。【答案】左子树【答案】左子树16.快速排序在平均情况下的时间复杂度为()()。【答案】【答案】O(nlogO(nlog2 2n)n)17.由关键字序列42,97,75,23,68,34建成的最大堆是()()。【答案】【答案】97 97，6868，7575，2323，4242，343418.对于关键字序列,，用筛选法建堆，必须从关键字为的结点开始。【答案】【答案】60 6019.从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为。【答案】【答案】3 320.设有二叉树根结点的层次为，一棵高度为h的满二叉树中的叶子结点个数是。【答案】【答案】2 2h h21.在一个最小堆中，堆顶结点的值是所有结点中的()()。【答案】最小值【答案】最小值22.在长度为n的顺序表中删除一个元素时,等概率情况下的平均移动元素的次数是。【答案】【答案】(n-1)/2(n-1)/223.由关键字序列57,24,76,63,18,31,15生成的一棵二叉排序树，其等查找概率情况下查找成功的平均查找长度为。【答案】【答案】18/718/724.数据结构包括逻辑结构、和数据的运算三个方面。【答案】存储结构【答案】存储结构25.在一棵m阶B树上，每个非根结点的关键码数最多为()()个。【答案】【答案】m-1m-126.在双向链表中,每个结点除了数据域外,还有两个指针域,它们分别指向()()。【答案】前趋结点和后继结点【答案】前趋结点和后继结点27.一般来说,深度优先生成树的高度比广度优先生成树的高度要()()。【答案】高【答案】高28.递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和。【答案】局部变量【答案】局部变量29.在一个堆的顺序存储中，假设一个元素的下标为i(0in-1)，那么它的右子女元素的下标为。【答案】【答案】2i+22i+230.数据结构的逻辑结构包括线性结构和结构两大类。【答案】非线性【答案】非线性31.队列是具有()()特性的线性表。【答案】【答案】先进先出先进先出32.根本数据类型是计算机已经实现了的。【答案】数据结构【答案】数据结构33.n个顶点且含有环路的无向连通图中，至少含有()()条边。【答案】【答案】n n34.假设设L是指向带表头的单链表,语句L-link=L-link-link的作用是()()单链表中的第一个结点。【答案】删除答案】删除35.8个数据元素为34，76，45，18，26，54，92，65，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为。【答案】【答案】2 236.大小为M的顺序存储的循环队列sq队满的条件为。【答案】【答案】(sq.rear+1)%M=sq.front(sq.rear+1)%M=sq.front37.假设设顺序栈的最大容量为MaxSize，top=-1表示栈空，那么判断栈满的条件是。【答案】【答案】top=MaxSize-1top=MaxSize-138.假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，那么在搜索成功情况下的平均搜索长度为。【答案】【答案】20.520.539.在程序运行过程中不能扩充的数组是()()分配的数组。这种数组在声明它时必须指定它的大小。【答案】静态【答案】静态40.设有程序段为for(i=1;i10;i+)for(j=1;j=i;j+)p=i*j;printf(“%4dn,p);那么执行p=i*j的次数为。【答案】【答案】45 4541.一棵高度为5的完全二叉树中，最多包含有个结点。假定树根结点的高度为0。【答案】【答案】636342.第i(i=1,2,n-1)趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做()()排序。【答案】直接插入【答案】直接插入43.设栈S和队列Q的初始状态为空，元素A，B，C，D，E，和F依次通过栈S，且一个元素出栈后即进入队列Q，假设6个元素出队列的顺序是B，D，C，F，E，A，那么栈S的容量至少是()()。【答案】答案】3 344.假设设串S=“documentHash.doc0，那么该字符串S的长度为()()。【答案】【答案】161645.在对m阶B树插入元素的过程中，每向一个结点插入一个关键码后，假设该结点的关键码个数等于()()个，那么必须把它分裂为2个结点。【答案】【答案】m m46.栈是一种限定在表的一端进行插入和删除的线性表，又被称为()()表。【答案】后出先进答案】后出先进47.在无向图G的邻接矩阵表示中，第j列中非零元的个数等于该顶点的。【答案】【答案】度度48.在一个链式队列中，假设队头指针与队尾指针的值相同，那么表示该队列至多有个结点。【答案】一【答案】一49.假定一棵二叉树的结点数为18，那么它的最小高度为。假定树根结点的高度为0。【答案】【答案】4 450.在单链表中,除了表头结点外,任意结点的存储位置由其直接()()结点的指针域的值所指示。【答案】前驱【答案】前驱51.由分别带权为9，6，2，5，7的五个叶子结点构造的哈夫曼树的带权路径长度为。【答案】【答案】656552.对长度为20的有序表进行二分查找的判定树的高度为()()。【答案】【答案】5 553.快速排序在平均情况下的空间复杂度为()()。【答案】【答案】O(logO(log2 2n)n)54.在一个链式队列中，假设队头指针与队尾指针的值相同，那么表示该队列至多有个结点。【答案】【答案】1 155.队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为()()表。【答案】先进先出【答案】先进先出56.当用长度为MaxSize的数组顺序存储一个栈时，假设用top=MaxSize表示栈空，那么表示栈满的条件为。【答案】【答案】top=0top=057.假设进栈序列为a，b，c，且进栈和出栈可以穿插进行，那么可能出现个不同的出栈序列。【答案】【答案】5 558.假设设一个n的矩阵A的开始存储地址LOC(0,0)及元素所占存储单元数d，按行存储时其任意一个矩阵元素aij的存储地址为()()。【答案】LOC(0,0)+(i*n+j)*d59.如果n个顶点的图是一个环，那么它有()()棵生成树。【答案】【答案】n n60.设有程序段为：for(i=1;i=10;i+)for(j=1;jnext=p-next;p-next=s;s-next=p-next;p-next=s;62.以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素的渐进时间复杂度为。【答案】【答案】O(n)O(n)63.在直接选择排序中，记录比拟次数的时间复杂度为()()。【答案】【答案】O(n O(n2 2)64.栈下溢是指在时进行出栈操作。【答案】【答案】栈空栈空65.在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对()()进行特殊处理。【答案】表头指针【答案】表头指针66.一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的()()存取的。【答案】下标或顺序号【答案】下标或顺序号67.利用三元组表存放稀疏矩阵中的非零元素，那么在三元组表中每个三元组元素对应一个非零元素的行号、列号和()()。【答案】值【答案】值68.克鲁斯卡尔算法适用于求的网的最小生成树。【答案】【答案】边稀疏边稀疏69.用链表表示线性表,表中元素之间的逻辑关系是通过链表中结点的来实现的。【答案】【答案】指针指针70.将一棵树按照左子女-右兄弟表示法转换成对应的二叉树，那么该二叉树中树根结点肯定没有子女。【答案】右【答案】右71.由带权为9，6，2，5，7的五个叶子结点构造的哈夫曼树，其根结点的权值为。【答案】【答案】292972.11个顶点的连通网络N有10条边，其中权值为1,2,3,4,5的边各2条，那么网络N的最小生成树各边的权值之和为()()。【答案】【答案】303073.线性表是由nn0个()()组成的有限序列。【答案】数据元素【答案】数据元素74.给定一组数据对象的关键码为46，79，56，38，40，84，对其进行一趟快速排序处理，得到的右子表中有()()个对象。【答案】【答案】3 375.将一个n阶对称矩阵的上三角局部或下三角局部压缩存放于一个一维数组中，那么一维数组需要存储()()个矩阵元素。【答案】【答案】n(n+1)/2n(n+1)/276.对于一棵具有n个结点的树，该树中所有结点的度数之和为。【答案】【答案】n-1n-177.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个()()上，才会被加入到生成树中。【答案】连通分量【答案】连通分量78.设序列25,36,40,45,48,56,60,68,72,85，当用折半查找方法查找36时，所需比拟的次数为。【答案】【答案】2 279.哈希查找是通过 来确定记录的存储地址的。【答案】交换【答案】交换90.单链表中逻辑上相邻的结点而在物理位置上【答案】【答案】哈希函数哈希函数80.对n个数据对象进行堆排序，总的时间复杂度为()()。【答案】【答案】O(nlogO(nlog2 2n)n)81.在线性表的散列存储中，装载因子 又称为装载系数，假设用m表示散列表的长度，n表示待散列存储的元素的个数，那么等于。【答案】【答案】n/mn/m82.设图的顶点数为n，那么求解最短路径的Dijkstra算法的时间复杂度为()()。【答案】【答案】O(nO(n2 2)83.一棵3阶B树中含有50个关键码，那么该树的最大高度为()()。【答案】【答案】5 584.从一棵二叉搜索树中搜索一个元素时，假设给定值大于根结点的值，那么需要向 继续搜索。【答案】右子树【答案】右子树85.链接存储表示的结点存储空间一般在程序的运行过程中进行动态地()()和释放。【答案】分配【答案】分配86.线性表的链接存储只能通过()()顺序访问。【答案】链接指针【答案】链接指针87.直接插入排序在初始有序时，进行次关键字比拟。【答案】【答案】n-1 n-188.假设将一棵树A(B(C,D,E),F(G(H),I)按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点的个数为个。【答案】【答案】2 289.每次直接或通过基准元素间接比拟两个元素，假设出现逆序排列就交换它们的位置，这种排序方法叫做()()排序。()()相邻。【答案】不一定【答案】不一定91.链表只适用于()()查找。【答案】顺序【答案】顺序92.在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用()()次调整算法。【答案】【答案】n-1n-193.向一个顺序栈插入一个元素时，首先使后移一个位置，然后把待插入元素写入到这个位置上。【答案】【答案】栈顶指针栈顶指针94.在带表头结点的单链表中删除某一指定结点，必须找到该结点的结点。【答案】【答案】前一个前一个95.在一棵高度为3的四叉树中，最多含有个结点，假定树根结点的高度为0。【答案】【答案】858596.在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有棵。【答案】【答案】4 497.设图G=(V,E)，V=V0,V1,V2,V3,E=(V0,V1),(V0,V2),(V0,V3),(V1,V3)，那么从顶点V0开始的图G的不同深度优先序列有()()种。【答案】【答案】4 498.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是()()。【答案】【答案】选择排序选择排序99.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作()()。【答案】【答案】存储密度存储密度100.用邻接矩阵存储图，占用的存储空间与图中的()()数有关。【答案】顶点【答案】顶点101.对称矩阵的行数与列数()()且以主对角线为对称轴，aij=aji，因此只存储它的上三角局部或下三角局部即可。【答案】相等【答案】相等102.在直接选择排序中，记录移动次数的时间复杂度为()()。【答案】【答案】O(n)O(n)103.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为()()。【答案】【答案】1515，1212，1111，1010，8 8，1616，1818，1717，1313，1919104.完全二叉树有200个结点,那么整个二叉树有个度为1的结点。【答案】【答案】1 1105.普里姆算法适用于求的网的最小生成树。【答案】【答案】边稠密边稠密106.在一个堆的顺序存储中，假设一个元素的下标为i(0in-1)，那么它的左子女元素的下标为。【答案】【答案】2i+12i+1107.假设用邻接矩阵表示有向图，那么顶点i的入度等于矩阵中()()。【答案】【答案】所对应列中的非零元素个数所对应列中的非零元素个数108.链队列lq为空的条件为。【答案】【答案】Lq-rear=lq.front Lq-rear=lq.front109.长度为11的有序表进行折半查找时，在等查找概率情况下查找成功的平均查找长度为。【答案】【答案】3 3110.第i(i=0,1,.,n-2)趟从参加排序的序列中第i个至第n-1个元素中挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做()()排序。【答案】直接选择【答案】直接选择111.快速排序在最坏情况下的时间复杂度为()()。【答案】【答案】O(nO(n2 2)112.由关键字序列36,96,84,18,52,27建成的最小堆是。【答案】【答案】(18,36,27,96,52,84)(18,36,27,96,52,84)113.深度为10的完全二叉树,至少有个结点。【答案】【答案】512512114.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，那么叶子结点数为个。【答案】【答案】6 6115.向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行和top=p操作。【答案】【答案】p-link=topp-link=top116.假设用表示树的边其中x是y的双亲，一棵树的边集为,，该树的度是()()。【答案】【答案】3 3117.设待排序的表为42，55，12，47，94，06，18，63，利用快速排序方法对其进行排序，经第一趟排序后，表的状态为。【答案】【答案】(18,06,12,42,94,47,55,63)(18,06,12,42,94,47,55,63)118.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的()()。【答案】【答案】输入量输入量119.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有个。【答案】【答案】6 6120.n(n0)个顶点的连通无向图各顶点的度之和最少为。【答案】【答案】2(n-1)2(n-1)121.对n个元素的序列进行冒泡排序时，情况下比拟次数最少，比拟次数为。【答案】【答案】初始数据有序初始数据有序 n-1 n-1122.在程序运行过程中可以扩充的数组是()()分配的数组。这种数组在声明它时需要使用数组指针。【答案】动态【答案】动态123.一棵3阶B树中含有50个关键码，那么该树的最小高度为()()。【答案】【答案】4 4124.仅允许在表的同一端进行插入和删除运算的线性表被称为。【答案】【答案】栈栈125.链表与顺序表、索引表、散列表等都是数据逻辑结构的()()表示。【答案】存储【答案】存储126.如果一个对象局部地包含自己，或自己定义自己，那么称这个对象是的对象。【答案】递归【答案】递归127.在有向图的邻接表表示中，每个顶点邻接表中所含的结点数等于该顶点的。【答案】【答案】出度出度128.给定一组数据对象的关键码为46,79,56,38,40,84，那么利用堆排序方法建立的初始堆最大堆为()()。【答案】【答案】8484，7979，5656，3838，4040，4646129.设关键字序列17,8,13,25,24,16,3，19，1，用希尔排序法按升序排序，用初始增量4进行一趟排序后的结果是()()。【答案】【答案】1,8,3,19,17,16,13,25,241,8,3,19,17,16,13,25,24130.设循环队列用数组Am表示,队头、队尾指针分别是front和rear,那么判定队满的条件为。【答案】【答案】(rear+1)%M=front(rear+1)%M=front131.求解带权连通图最小生成树的Prim算法使用图的()()作为存储结构。【答案】邻接矩阵【答案】邻接矩阵132.在堆排序中，对n个记录建立初始堆需要调用()()次调整算法。【答案】【答案】n/2n/2133.一棵二叉树的先根序列为，中根序列为，那么后根序列为。【答案】【答案】FDBECAFDBECA134.用折半查找法查找一个线性表中的元素时，此线性表必须是。【答案】【答案】有序的有序的135.在有向图的邻接矩阵表示中，第j列元素之和等于第j个顶点的。【答案】【答案】入度入度136.在链表中进行插入和()()操作的效率比在顺序存储结构中进行相同操作的效率高。【答案】删除【答案】删除137.算法的一个特性是()()，即算法必须执行有限步就结束。【答案】有穷性【答案】有穷性138.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做()()排序。【答案】二路归并【答案】二路归并139.向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给()()。【答案】栈顶指针【答案】栈顶指针140.根据n个元素建立一棵二叉搜索树的渐进时间复杂度大致为。【答案】【答案】O(nlogO(nlog2 2n)n)141.抽象数据类型的特点是()()、信息隐蔽、使用与实现别离。【答案】数据封装【答案】数据封装142.在双向循环链表中插入一个新的结点时，应修改()()个指针域的值。【答案】【答案】四四143.在有向图中，以顶点v为终点的边的数目称为v的()()。【答案】【答案】入度入度144.将一个n阶对称矩阵A的上三角局部按行压缩存放于一个一维数组B中，A00存放于B0中，那么AIJ在IJ时将存放于数组B的()()位置。【答案】【答案】(2n-I-1)*I/2+J(2n-I-1)*I/2+J145.如果某二叉树的中根序列为vxuyzw，层次序列为uvwxyz，那么先根序列为。【答案】【答案】uvxwyzuvxwyz146.对用邻接表表示的连通图进行深度或广度优先遍历时的时间复杂度为。【答案】【答案】O(n+e)O(n+e)147.下面程序段的时间复杂度是。for(i=1;in-1;i+)y=y+1;for(j=1;j(2*n);j+)x=x+1;【答案】【答案】O(nO(n2 2)148.由分别带权为9，2，5，7的四个叶子结点构造的哈夫曼树的带权路径长度为。【答案】【答案】44 44149.向一个循环队列中插入元素时，需要首先移动指针，然后再向所指位置写入新元素。【答案】队尾【答案】队尾150.链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的()()的值。【答案】指针域【答案】指针域151.有一个10阶三角矩阵A,采用压缩方式(以行序为主存储)存储在一维数组B中,假设A1,1 存储在B1中，那么A5,8 存储在B。【答案】【答案】38 38