数据结构

1数据结构——C语言版一、填空题1.在双链表中要删除已知结点*s，其时间复杂度为O(1)。2.循环队列用数组data[max]存放其元素值，已知其头、尾指针分别是front和rear，则当前队列中元素的个数是(m+rear-front)%m。3.具有12个结点的完全二叉树的叶结点有6个。4.在任何一棵二叉树中，度为0的结点n0和度为2的结点n2之间的关系是n0=n2+1。5.已知完全二叉树的第4层有4个结点，则其叶子结点数是6。6.在仅有尾指针rear指示的单循环链表rear中，在表尾插入一个结点s的语句序列是s-next=rear-next;rear-next=s。7.栈顶的位置是随着入栈出栈操作而变化的。8.数据结构一般包括三个方面的内容：数据的逻辑结构、数据的存储结构及对数据的运算。9.假设以S和X分别表示进栈和出栈操作，则对输入序列1，2，3，4，5进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为bceda。10.数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。11.在带头结点的双链表head中，指针p所指结点是开始结点的条件是p-prior==head。12.在选择排序、堆排序、快速排序、直接插入排序中，稳定的排序方法是直接插入排序。13.在具有n个结点的双链表中做插入、删除运算，平均时间复杂度为O(n)。14.队列的队尾位置随着入队而变化。15.快速排序在最坏情况下的时间复杂度是O(n2)。16.n(n0)个顶点连通无向图的生成树恰有n-1条边。17.在一个长度为n的顺序表中第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动n-i+1个元素。18.在只有一个数据元素的情况下，链队列的出队操作需要修改尾指针。19.数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、数据的物理结构和数据的运算。20.在双循环链表中，若要在指针p所指结点之前插入指针s所指的结点，则需执行下列语句：s-prior=p-prior;p-prior-next=s;s-next=p;和p-prior=s;。21.从栈顶指针为top的链栈中删除一个结点，并将被删除的结点的值保存在x中，其操作步骤为x=top-data；top=top-next;。22.用数组A[m]来存放循环队列q的元素，且它的头、尾指针分别为front和rear，队列满足条件(q-rear+1)%m==q-front,则队列中当前的元素个数为m-1。23.深度为6的二叉树最多有63个结点。24.右图为某树的静态双亲表示，则结点D、E的双亲结点分别为B和C。25.已知指针p指向双向链表中的一个结点（非首结点、非尾结点），则将结点s插入在p结点的直接后继位置的语句是s-next=p-next；s-prior=p；s-next-prior=s；p-next=s；26.一个二叉树中，度为2的结点有3个，则叶结点有4个。27.顺序栈s存储在数组s-data[max]中，对s进行出栈操作，执行的语句序列是x=s-data[s-top];s-top--;。0A-11B02C03D14E2228.以下运算实现在循环队列中的初始化操作voidinitqueue(seqqueue*q){q-front=0;q-rear=0;}29.若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的第一个结点。30.对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的左子树上继续查找。31.数据的逻辑结构与数据元素本身的内容和形式无关。32.程序段“for(i=1;i=n;i++){k++;for(j=1;j=n;j++)x=x+k;}”的时间复杂度T(n)=O(n2)。33.已知带表头结点的单链表L，指针p指向L链表中的一个结点（非首结点、非尾结点），则：删除结点p的直接后继结点的语句是p-next=p-next-next；删除首结点的语句是L=L-next。34.二叉树通常有顺序存储结构和链式存储结构两种。35.二叉树在二叉链表表示方式下，p指向二叉树的根结点，经运算s=p；while(s-rchild)s=s-rchild后，s指针指向右子树最右结点。36.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是O(n2)。二、选择题1.下列算法的时间复杂度是（B）。for(i=1;i=n;i++)c[i]=i；A、O（1）B、O（n）C、O（log2n）D、O（nlog2n）2.在表长为n的顺序表上做插入运算，平均要移动的结点数为（B）。A、nB、n/2C、n/3D、n/43.在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（A）。A、S-next=P-next；P-next=S；B、P-next=S-next；S-next=P；C、P-next=P；P-next=S；D、P-next=S；S-next=P；4.在具有m个结点的完全二叉树中，结点i（i1）的父结点是（D）。A、2iB、不存在C、2i+1D、⌊i/2⌋5.在一个具有k个结点的无向图中，要连通全部结点至少需要（C）。A、k条边B、k+1条边C、k-1条边D、k/2条边6.最小生成树指的是（C）。A、由连通图所得到的边数最少的生成树B、由连通图所得到的顶点相对较少的生成树C、连通图的所有生成树中权值之和最小的生成树D、连通图的极小连通子图7.二叉排序树中，关键字值最大的结点（D）。A、左指针一定为空B、右指针一定为空C、左、右指针均为空D、左、右指针均不为空8.数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（D）。A、索引存储方法B、顺序存储方法C、链式存储方法D、散列存储方法39.在已知头指针的单链表中，要在其尾部插入一新结点，其算法的时间复杂度为（C）。A、O（1）B、O（log2n）C、O（n）D、O（n2）10.循环队列是空队列的条件是（A）。A、Q-rear==Q-frontB、（Q-rear+1）%maxsize==Q-frontC、Q-rear==0D、Q-front==011.有n个叶结点的哈夫曼树所具有的结点数为（D）。A、nB、n+1C、2nD、2n-112.图的广度优先搜索遍历类似于树的（D）。A、先序遍历B、中序遍历C、后序遍历D、层次遍历13.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）。A、1/2倍B、1倍C、2倍D、4倍14.对n个不同的排序码进行冒泡排序，在元素无序情况下的比较次数为（D）。A、n+1B、nC、n-1D、n（n-1）/215.顺序查找法适合于存储结构为（B）的线性表。A、散列存储B、顺序存储或链接存储C、压缩存储D、索引存储16.链栈与顺序栈相比，比较明显的优点是（D）。A、插入操作更加方便B、删除操作更加方便C、不会出现下溢的情况D、不会出现上溢的情况17.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（C）。A、顺序表B、用头指针表示的单循环链表C、用尾指针表示的单循环链表D、单链表18.下列陈述中正确的是（D）。A、二叉树是度为2的有序树B、二叉树中结点只有一个孩子时无左右之分C、二叉树中必有度为2的结点D、二叉树中最多只有两棵子树，并且有左右之分19.在查找过程中，若同时还要做增、删工作，这种查找则称为（B）。A、静态查找B、动态查找C、内查找D、外查找20.线性表是（A）。A、一个有限序列，可以为空B、一个有限序列，不能为空C、一个无限序列，可以为空D、一个无限序列，不能为空21.在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（B）。A、O（n）B、O（1）C、O（log2n）D、O（n2）22.若一个栈的输入序列是1，2，3，……，m，输出序列的第一个元素是m，则第ｉ个输出元素是（B）。A、m-iB、m–i+1C、iD、不确定23.以二叉链表作为二叉树的存储结构，在具有m个结点的二叉链表中(m0)，空链域的个数为（C）。A、2m-1B、m-1C、m+1D、2m+124.快速排序算法在最坏情况下的时间复杂度为（C）。A、O（n）B、O（nlog2n）C、O（n2）D、O（log2n）25.具有m个结点的无向图的边数最多为（B）。A、m+1B、m（m-1）/2C、m（m+1）D、2m（m+1）26.线性表采用链式存储时，结点的地址（C）。A、必须是连续的B、必须是不连续的4C、连续与否均可D、必须有相等的间隔27.栈与一般线性表的区别主要在（D）。A、元素个数B、元素类型C、逻辑结构D、插入、删除元素的位置28.从未排序序列中挑选元素，将其放在已排序序列的一端，这种排序方法称为（A）。A、选择排序B、插入排序C、快速排序D、冒泡排序29.若m个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个（B）。A、一般矩阵B、对称矩阵C、对角矩阵D、稀疏矩阵30.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（B）。A、99B、98C、48D、5031.堆排序是一种（B）排序。A、插入B、选择C、交换D、归并32.在单链表中，增加头结点的目的是（C）。A、使单链表至少有一结点B、标志表中首结点位置C、方便运算的实现D、说明单链表是线性表的链式存储实现33.下列排序方法中，排序趟数与序列的原始状态有关的方法是（D）。A、选择排序B、希尔排序C、堆排序D、冒泡排序34.堆的形状是一棵（C）。A、二叉排序树B、满二叉树C、完全二叉树D、平衡二叉树35.在一棵具有5层的满二叉树中，结点总数为（A）。A、31B、32C、33D、1636.带头结点的单链表head为空的判定条件是（B）。A、head=NULL；B、head-next=NULL；C、head-next=head；D、head!=NULL；37.一个链栈的栈顶指针是top，则执行出栈操作时（栈非空），用x保存被删除结点的值，则执行（D）。A、x=top；top=top-next；B、x=top-data；C、top=top-next；x=top-data；D、x=top-data；top=top-next；38.在一个具有m个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（B）。A、O（1）B、O（m）C、O（m2）D、O（log2m）39.对线性表进行二分查找时，要求线性表必须（B）。A、以顺序方式存储B、以顺序方式存储且元素有序C、以链接方式存储D、以链接方式存储且元素有序40.在一棵二叉树中，第5层上的结点数最多为（C）。A、8B、15C、16D、3241.在下列排序方法中，不稳定的排序方法是（B）。A、直接插入排序B、直接选择排序C、冒泡排序D、归并排序42.快速排序在（C）情况下最易发挥其长处。A、被排序的数据中含有多个相同排序码B、被排序的数据已基本有序C、被排序的数据完全无序D、被排序的数据中的最大值和最小值相差悬殊43.若用冒泡排序对关键字序列｛18，16，14，12，10，8｝进行从小到大的排序，所需进5行的关键字比较总次数是（B）。A、10B、15C、21D、3444.下列有关线性表的叙述中，正确的是（A）。A、线性表中的元素之间是线性关系B、线性表中至少有一个元素C、线性表中任何一个元素有且仅有一个直接前趋D、线性表中任何一个元素有且仅有一个直接后继45.用冒泡排序的方法对n个数据进行排序，第一趟共比较（C）对元素。A、1B、2C、n-1D、n46.由二叉树的（B）遍历，可以惟一确定一棵二叉树。A、前序和后序B、前序和中序C、后序D、中序47.用（B）方法遍历一棵二叉排序树，可以得到各结点键值的递增序列。A、先根遍历B、中根遍历C、层