2024年甘肃开放大学《数据结构》形成性考核参考试题库（含答案）

2024年甘肃开放大学《数据结构》形成性考核参考试题库(含答案)A、都是0B、地址域D、空闲域D、线性表charsex;}person[5];需要给结构体数组中第2个变量的no成员赋值为5,正确D、person[1].no=5.19.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有()个叶子结点。C、12栈顶，栈1的底在V[0],栈2的底在V[m-1],则栈满的条件是()。21.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[],根结点存A、R[2*i+l]23.循环单链表的主要优点是()。D、从表中的任意结点出发都能扫描到整个链表24.一棵树的广义表表示为a(b(c),de(g(h)),f,k)),则该树的叶子结点个数为25.设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有()个结点。D、任意多个B、紧凑结构和非紧凑结构C、线性结构和非线性结构32.n个顶点的生成树有()条边。37.一棵树的广义表表示为a(b(c),d(e(g(h)),f,k)),则该树的度为()。B、138.对下面的有向图进行深度优先遍历得到的遍历序列是()。A、bcfdeg39.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。现要将指针指向的新结点插入到指针p指向的结点之后，下面的操作序列中正确的A、q=p->next;p->next=q->nA、p->next=p->next->n48.n个顶点的无向图的接表最多有()个结点。49.一棵深度为6的满二又树一共有个()结点。B、2和452.一个容量为15的循环队列中，队尾指针是rear,队头是front,初始时均为0,54.若已知一个栈的进栈序列是1,2,3,...,n,其输出序列为p1,p2,p3,,pn,若p1A、一定是2D、一定是1②边数大于顶点个数减1③至少有一个顶点度为162.一棵深度为h的满k又树有如下性质：第h层上的结点都是叶子结点，其余各层上的每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对A、i63.该二叉树对应的森林有()棵树。64.一个递归算法必须包括()。A、递归部分68.一棵完全二又树按层次遍历的序列为ABCDEFGHI则在前序遍历中结点E的直接前驱为结点()。69.一棵树的广义表表示为a(b(c),d(e(g(h)),f,k)),则该树中e结点的孩子结点个数为()。70.最大容量为n的循环队列，队尾指针是rear,队头指针是front,初始时均为0,B、根结点但不是分支结点D、分支结点但不是根结点72.已知输入序列为abcd,经过队列后能得到的输出序列有()。73.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。带头结点的单链表L为空的条件是()C、线性存储结构和非线性存储结构D、顺序存储结构和链式存储结构78.对图从顶点a出发进行广度优先遍历，则()是不可能得到的遍历序列。79.对于任何一棵二又树，如果其终端结点数为no,度为2的结点数为n2,则no=80.用邻接表存储图所用的空间大小()。A、与图的顶点数和边数都有关B、只与图的边数有关85.表示一个有100个顶点，1000条边的非带权有向图的邻接矩阵有()个大于零矩阵元素86.已知一个有向图的边集为{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},则由该图产生的一种可能的拓扑序列为()。87.已知链表的每个结点包括一个指针域next,它指向该结点的后继结点。非空的循环单链表head的尾结针p满足()。A、都是n94.表示一个有100个顶点，1000条边的无向图的邻接矩阵有()个非零矩阵元素。95.已知单链表的每个结点包括一个指针域next,它指向该结点的后继结点。假定己建立以下动态链表结构，且指针pl和p2已指向如图所示的结点：则以下可以将p2所指结点从链表中删除并释放该结点的语句组是()。PePeA、pl->next=p2->next;free96.一颗非空二叉树其前序遍历序列与后序遍历序列正好相反，则该二叉树一定A、所有结点均无左孩了结点B、所有结点均无右孩子结点C、只有一个叶结点D、是任意一棵二又树97.一棵完全二又树按层次遍历的序列为ABCDEFGHI,后序遍历中结点B的直接后继是结点()。98.分析以下程序段，其时间复杂度为T()=()99.在一棵具有35个结点的完全二叉树中，该树的深度为()。100.无向图G=(V.E),其中：VA、,b,e,c,d,f101.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数是()7A、s->next=a->next->next;a->next->neD、a=a->next:s->next104.一棵树的广义表表示为a(b(c),d(e(g(h)),f,k)),则该树的高度为()105.由3个结点所构成的二又树有()种形态。106.已知链表的每个结点包括一个指针域next它指向该结点的后继结点。在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则()。A、p指向头结点B、p指向尾结点C、米p的直接后继是头结点D、米p的直接后继是尾结点107.栈和队列的共同点是()。A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点108.由权值分别是8,7,2,5的叶子结点生成一棵赫夫曼树，它的带权路径长度为109.在一个无向图中，所有顶点的度数之和等于所有边数的()倍。A、1/2111.一个图中包含k个连通分量，若按深度优先遍历方法访问多有顶点，则必须调用()次深度优先遍历算法。A、带尾指针的非循环链表B、带尾指针的循环链表C、带头指针的非循环链表D、带头指针的循环链表A、一个图的邻接矩阵表示是唯一的，邻接表表示也唯一B、一个图的邻接矩阵表示是唯一的，邻接表表示不唯一C、一个图的邻接矩阵表示不唯一的，邻接表D、一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一119.在一棵二叉树的二叉链表中，空指针域等于所有非空指针域相加()。120.设深度为k的二叉树上只有度为0和度为2的结点，则这棵树所含的结点数122.设有一个顺序栈S,元素1,2,3,4,5,6依次进栈，如果6个元素的出栈顺序为2,3,4,6,5,1,1则顺序站的容量至少可以存储()个元素。124.后缀表达式“45*32+-”的值为()。B、可以改变133.计算机算法指的是解决问题的有限运算序列，它必具备输入、输出和()等五A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性134.队列的“先进先出”特性是指()。A、最早插入队列中的元素总是最后被删除B、当同时进行插入、删除操作时，总是插入操作优先D、每次从队列中删除的总是最早插入的元素135.一个向量第一个元素的地址是100,每个元素的长度为2,则第5个元素的地136.5、森林F中有三棵树，每棵树上的结点个数分别为n1,n2和n3,森林F转换二叉树后，根结点的右子树上结点个数为()。A、存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同B、普通二叉树只能用链式存储结构存储D、二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树138.数组Q[n]用来表示一个循环队列，为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n,计算队列中元素的公式为()。判断题2.任何一个递归过程都可以转换成非递归过程3.任何无向图都存在生成树。4.二叉树的前序和后序遍历序列能惟一确定这棵二叉树。5.三叉链表存储二叉树，指针域除了指向左孩子结点和右孩子结点，还要指向兄6.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型邻B、错误B、错误22.二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。23.任何A0V网拓扑排序的结果都是唯一的。A、正确24.顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移25.在带头节点的单循环链表中，任意节点中的指针域都不为空26.用栈这种数据结构可以实现队列这种数据结构，反之亦然。32.由