数据结构1252正式稿.docx
- 文档编号:15466026
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:207
- 大小:3.40MB
数据结构1252正式稿.docx
《数据结构1252正式稿.docx》由会员分享,可在线阅读,更多相关《数据结构1252正式稿.docx(207页珍藏版)》请在冰点文库上搜索。
数据结构1252正式稿
一、选择题
1-已知如图1所示的一个图,若从顶点V1出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为(A)。
A.V1V2V4V8V5V3V6V7B.V1V2V4V5V8V3V6V7C.V1V1V4V8V3V5V6V7D.V1V3V6V7V2V4V5V8
1-已知如图1所示的一个图,若从顶点V1出发,按广度优先进行遍历,则可能得到的一个顶点序列为(C)。
A.V1V2V3V6V7V4V5V8B.V1V2V3V4V5V8V6V7C.V1V2V3V4V5V6V7V8D.V1V2V3V4V8V5V6V7
1-已知如图1所示的一个图,若从顶点a出发,按深度优先搜索法进行遍历,则可能到的一种顶点序列为(D)。
A.abecdfB.acfebdC.aebcfdD.aedfcb
1-已知如图2所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则可能得到的一种顶点序列为(B)。
A.abcedfB.abcefdC.aebcfdD.acfdeb
1-如图若从顶点a出发按深度优先搜索法进行遍历,则可能得到的顶点序列为(B)。
A.aebcfdB.abedcfC.acebdfD.acfbde
1-已知如图1所示的一个图,若从顶点a出发,按深度优先搜索法进行遍历,则可能得到的一种顶点洗了为(D)。
A.abecdfB.acfebdC.aebcfdD.aedfcb
1-双向循环链表结点的数据类型为:
structnode
{intdata;
Structnode*next;/**/
Structnode*prior;
};
设p指向表中某一结点,要显示p所指结点的直接前驱结点的数据元素,可用操作(B)。
A.print(“%d”,p->next->data);B.printf(“%d”,p->prior->data);C.printf(“%d”,p-prior->next);D.printf(“%d”,p->data);
1-char*p;
p=StrCat(“ABD”,“ABC”)
Printf(“%s”,p);
的显示结果为(B)。
A.-1B.ABDABCC.ABD.1
1-如图若从顶点a出发深度优先搜索法进行遍历,则可能得到的顶点序列为(B)。
A.acfgedbB.aedbgfcC.acfebdgD.aecbdgf
1-如图,若从顶点a出发按广度优先搜索法进行遍历,则可能得到的顶点序列为(B)。
A.acebdgfB.abecdgfC.acfedgbD.abecfdg
1-如图若从顶点a出发按广度优先搜索法进行遍历,则可能得到的顶点序列为(D)。
A.acebdfghB.aebcghdfC.aedfbcghD.abecdfgh
1-如图,若从顶点a出发按广度优先搜索法进行遍历,则可能得到的顶点序列为(B)。
A.acebdgfB.abecdgfC.acfedgbD.abecfdg
1-下面算法的时间复杂度为(B)。
Intf(unsignedintn){
If(n==0||n==1)return1;
Else
}
A.O
(1)B.O(n)C.O(n2)D.O(n!
)
1-执行下面程序段时,S语句的执行次数为(D)。
for(inti=1;i<=n;i++)
for(intj=1;j<=I;j++)S;
A.n2B.n2/2C.n(n+1)D.n(n+1)/2
1-在一个程度为n的顺序存储的有序表中搜索值为x元素时,其时间复杂度最好情况为(A)。
A.O
(1)B.O(
)C.O(log2n)D.O(n)
1-下面程序段的时间复杂度为(C)。
for(inti=0;i for(intj=0;j A.O(m2)B.O(n2)C.O(m*n)D.O(m+n) 1-下面算法的时间复杂度为(B)。 intf(unsignedintn){ if(n==0||n==1)return1; elsereturnn*f(n-1); } A.O (1)B.O(n)C.O(n2)D.O(n! ) 1-设循环队列的结构是 structQueue{ DataTypedata[MaxSize] intfront,rear; }; 若有一个Queue类型的队列Q,试问判断队列慢的条件应为(D)。 A.Q.front==Q.rear;B.Q.front-Q.rear==MaxSize;C.Q.front+Q.rear==MaxSize;D.Q.front==(Q.rear+1)%MaxSize; 1-设有一个递归算法入下 IntX(intn){ If(n<=3)return1; ElsereturnX(n-1)+X(n-4)+1; } 试问计算X(X(5))时需要调用(C)次X函数。 A.2B.3C.4D.5 1-设有一个递归算法如下: intfact(intn){//n大于等于0 if(n<=0)return1; elsereturnn*fact(n-1); } 则计算fact(n)需要调用该函数的次数为(B)此。 A.nB.n+1C.n+2D.n-1 1-一个二叉树按顺序方式存储在一个一维数组中,如图 则结点E在二叉树的第(B)层。 A.1B.2C.3D.4 1-(B)是性质相同的数据元素的集合,是数据的子集。 A.数据元素B.数据对象C.数据结构D.数据项 1-n个顶点的连通图中至少含有(A)条边。 A.n-1B.nC.n(n-1)/2D.n(n-1) B-把数据存储到计算机中,并具体体现数据元素间的逻辑结构为(A)。 A.物理结构B.逻辑结构C.算法的具体实现D.给相关变量分配存储单元 B-表达式a*(b+c)-d的后缀表达式是(B)。 A.abcd*+-B.abc+*d-C.abc*++d-D.-+*abcd B-不带头结点的单链表first为空的判定条件是(A)。 A.first==NULL;B.first->link==NULL;C.first->link==first;D.first! =NULL; C-采用分块查找时,若线性表中共有324个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块,每块应分(B)个结点最佳。 A、10B.18C.6D.324 C-采用顺序查找法对长度为n的线性表进行查找(不采用表尾监视哨的方法),最坏的情况下要进行(B)次元素间的比较。 A.n+2B.nC.n-1D.n/2 C-采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为(C)。 A.nB.n/2C.(n+1)/2D.(n-1)/2 C-采用折半查找方法查找长度为n的线性表时,每个元素的平均查找长度为(A)。 A.O(n*n)B.O(nlog2n)C.O(n)D.s(log2n) C-常对数组进行的两种基本操作是(C)。 A.建立与删除B.索引与、和修改C.查找和修改D.查找与索引 C-串的长度是指(B)。 A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数 C-串函数StrCat(a,b)的功能是进行串(D)。 A.比较B.复制C.赋值D.连接 C-串函数StrCmp(“abA”,“aba”)的值为(D)。 A.1B.0C.“abAaba”D.-1 C-串函数StrCmp(“b”,“cd”)的值为(D)。 A.1B.0C.“bcd”D.-1 C-串函数StrCmp(“d”,“D”)的值为(B)。 A.0B.1C.-1D.3 C-串是(D)。 A.不少于一个字母的序列B.任意个字母的序列C.不少于一个字符的序列D.有限个字符的序列 C-串与普通的线性表相比较,它的特殊性体现在(C)。 A.顺序的存储结构B.链接的存储结构C.数据元素是一个字符D.数据元素可以任意 C-串与普通的线性表相比较,它的特殊性体现在(C)。 A.顺序的存储结构B.链接的存储结构C.数据元素是一个字符D.数据元素可以任意 C-从n个数中选取最大元素(C)。 A.基本操作时数据元素间的交换B.算法的时间复杂度是O(n2)C.算法的时间复杂度是O(n)D.需要进行(n+1)次数据元素间的比较 C-从具有n个结点的AVL树中搜索一个元素时,在等概率情况下进行成功搜索的时间复杂度大致为()C。 A.O(n)B.O (1)C.O(log2n)D.O(n2) C-从未排序序列中挑选元素,并将其放入已排序序列的一端,此方法称为(C)。 A.插入排序B.交换排序C.选择排序D.归并排序 C-从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。 将其放入已排序序列的正确的位置上,此方法称为(A)A.插入排序B.选择排序C.交换排序D.归并排序 C-从一个栈顶指针为top的链栈中删除一个结点时,用变量x保存被删结点的值,则执行(A)。 A.x=top->data;top=top->next;B.x=top->data;C.top=top->next;x=top->data;D.top=top->next;x=data; D-带头结点的单链表first为空的判定条件是(B)。 A.first==NULL;B.first->link==NULL;C.first->link==first;D.first! =NULL D-带头结点的单向链表为空的判断条件是(B)(设头指针head)。 A.head==NULLB.head->next==NULLC.head->next==headD.head! =NULL D-当a的值较小时,散列存储通常比其他存储方式具有(B)的查找速度。 A.较慢B.较快C.相同D. D-当利用大小为n的数组顺序存储一个队列时,该队列的最大长度为(B)。 A.n-2B.n-1C.nD.n+1 D-当利用大小为n的数组顺序存储一个桟时,假定用top==n表示桟空,则向这个桟插入一个元素时,首先应执行(B)语句修改top指针。 A.top++B.top--C.top=0D.top=1 D-当两个元素出现逆序的时候就交换位置,这种排序方法称为(B)。 A.插入排序B.交换排序C.选择排序D.归并排序 D-当一个作为实际参数传递的对象占用的存储空间较大并且需要修改时,则对应的形参应说明为(B)。 A.基本类型B.引用型C.传值型D.常值引用型 D-队列的插入操作在(B)进行。 A.队头B.队尾C.队头或队尾D.在任意指定位置 D-对5个不同的数据元素进行直接插入排序,最多需要进行(B)次比较。 A.8B.10C.15D.25 D-对n个元素进行冒泡排序,通常要进行n-1趟冒泡,在第j趟冒泡中共要进行(C)次元素间的比较。 A.jB.j-1C.n-jD.n-j-1 D-对n个元素进行冒泡排序若某趟冒泡中只进行了(C)次元素间的交换,则表明序列已经排好序。 A.1B.2C.0D.n-1 D-对存储有n个元素的长度为m的散列表进行搜索,平均搜索长度为(C)有关。 A.nB.mC.n/mD.n*m D-对待排序的元素序列进行划分,将其分为左、右两个子序列,再对两个子序列施加同样的排序操作,直到子序列为空或只剩一个元素为止。 这样的排序方法是(C)。 A.直接选择排序B.直接插入排序C.快速排序D.起泡排序 D-对二叉排序树进行(C)遍历,可以使遍历所得到的序列是有序序列。 A.按层次B.后序C.中序D.前序 D-对具有n个元素的任意序列采用插入排序法进行排序,排序趟数为(A)。 A.n-1B.nC.n+1D.[log2n] D-对数据元素序列(49,72,68,13,38,50,97,27)进行排序,前三趟排序结果时的结果依次为第一趟: 49,72,68,13,38,50,97,27;第二趟: 49,68,72,13,38,50,97,27;第三趟: 13,49,68,72,38,50,97,27。 该排序采用的方法是(A)。 A.插入排序法B.选择排序法C.冒泡排序法D.堆积排序法 D-对线性表进行二分查找时,要求线性表必须(C)。 A.以顺序存储方式B.以链接存储方式C.以顺序存储方式,且数据元素有序D.以链接存储方式,且数据元素有序 D-对序列(49,38,65,97,76,13,47,50)采用直接插入排序法进行排序,要把第七个元素47插入到已排序中,为寻找插入的合适位置需要进行(C)次元素间的比较。 A.3B.4C.5D.6 D-对有14个数据元素的有序表R[14]进行折半搜索,搜索到R[3]的关键码等于给定值,此时元素比较顺序依次为(C)。 A.R[0],R[1],R[2],R[3]B.R[0],R[13],R[2],R[3]C.R[6],R[2],R[4],R[3]D.R[6],R[4],R[2],R[3] D-对有18个元素的有序表作二分(折半)查找,则查找A[3]的比较序列的下标可能为(D)。 A.3B.3C.3D.3 D-对于表头指针为first的单链表,其空表的判定条件是(A)。 A.first==NULLB.first->link==NULLC.first->link==firstD.first! =NULL D-对于具有e条边的无向图,它的邻接表中共有(C)个边结点。 A.e-1B.e+1C.2eD.3e D-对于具有n个顶点的图,若采用邻接矩阵表示,则该矩阵的大小为(B)。 A.nB.n2C.n-1D.(n-1)2 D-对于顺序存储的有序表{5,12,20,26,37,42,46,50,64},若采用折半查找,则查找元素26的比较次数是(C)。 A.3B.3C.4D.5 D-对于一个具有n个顶点的无向图,该图最多有(B)条边。 A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1) D-对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为(A)。 A.nB.eC.2nD.2e D-对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则所有顶点邻接表中的结点总数为(D)。 A.nB.eC.2nD.2e D-对于一个线性表,若要求既能进行较快地插入和删除,又要求存储结构能够反映数据元素之间的逻辑关系,则应该(B)。 A.以顺序存储方式B.以链接存储方式C.以索引存储方式D.以散列存储方式 D-对于有向图,其邻接矩阵表示比邻接表表示更易于(A)。 A.求一个顶点的入度B.求一个顶点的出边邻接点C.进行图的深度优先遍历D.进行图的广度优先遍历 D-对于长度为9的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索长度为(C)的值除以9。 A.20B.18C.25D.22 D-对长度为10的顺序表进行搜索,若搜索前面5个元素的概率相同,均为1/8,搜索后面5个元素的概率相同,均为3/40,则搜索任一元素的平均搜索长度为(C)。 A.5.5B.5C.39/8D.19/4 D-对长度为10的线性有序表A[10]进行折半查找,若查找到元素A[1]时成功,则查找长度为(B)。 A.1B.2C.3D.4 D-对长度为10的线性有序表A[10]进行折半查找,若查找到元素A[2]时成功,则查找长度为(C)。 A.1B.2C.3D.4 D-对长度为n的有序单链表,若搜索单个元素的概率相等,则顺序搜索到表中任一元素的平均搜索长度为(B)。 A.n/2B.(n+1)/2C.(n-1)/2D.n/1 D-多维数组实际上是由嵌套的(A)实现的。 A.一维数组B.多项式C.三元素表D.简单变量 E-二叉树的深度为k,则二叉树最多有(D)个结点。 A.2kB.2k-1C.2k-1D.2k-1 E-二叉树第k层上最多有(B)个结点。 A.2kB.2k-1C.2k-1D.2k-1 E-二叉树是非线性数据结构,所以(C)。 A.它不能用顺序存储结构存储B.它不能用链式存储结构存储C.顺序存储结构和链式存储结构都能存储D.顺序存储结构和链式存储结构都不能使用 E-二维数组实际上是由嵌套的(A)实现的。 A.一维数组B.多项式C.三元组表D.简单变量 F-非空的单向循环链表的尾结点满足(C)(设头指针为head,指针p指向尾结点)。 A.p->next==NULLB.p==NULLC.p->next==headD.p==head G-根据n个元素建立一个有序单链表的时间复杂度为(C)。 A.O (1)B.O(n)C.O(n2)D.O(nlog2n) G-关于哈希查找的说法正确的是(B)。 A.除留余数法是最好的B.哈希函数的好坏要根据具体情况而定C.删除一个元素后,不管用哪种方法处理冲突,都只需简单地把该元素删除掉D.因为冲突是不可避免的,所以装填因子越小越好 H-哈希函数有一个共同的性质,即函数值应当以(D)取其值域的每个值。 A.最大概率B.最小概率C.平均概率D.同等概率 H-含5个结点(元素值均不相同)的二叉搜索树有(B)种。 A.54B.42C.36D.65 J-假定一个链式队列的队头和队尾指针分别为front和rear,则判断队空的条件为(D)A.front==rearB.front! =NULLC.rear! =NULLD.front==NULI。 J-假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear,则判断队空的条件为(D)。 A.front+1==rearB.rear+1==frontC.front==0D.front==rear J-假定一棵二叉树的第i层上有3i个结点,则第i+1层上最多有(B)个结点。 A.3iB.6iC.9iD.2i J-假定一棵二叉树中,双分支结点数为15,单分支结点数为30,则叶子结点数为(B)。 A.15B.16C.17D.47 J-假设在有序线性表A[1..20]上进行二分查找,则比较五次查找成功的结点数为(B)。 A.4B.5C.6D.8 J-将含有150个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点的编号为1,则编号为69的结点的双亲结点的编号为(B)。 A.33B.34C.35D.36 J-就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是(A)。 A.堆排序<快速排序<归并排序B.堆排序<归并排序<快速排序C.堆排序>归并排序>快速排序D.堆排序>快速排序>归并排序 J-具有65个结点的完全二叉树的高度为(C)。 (根的层次号为0)A.8B.7C.6D.5 J-具有n个顶点的有向图最多可包含有(D)条有向边。 A.n一1B.nC.n(n一1)/2D.n(n一1) J-具有n个顶点的有向无环图最多可包含(C)条有向边。 A.n-1B.nC.n(n-1)/2D.n(n-1) K-空串与空格串(B)。 A.相同B.不相同C.可能相同D.无法确定 K-快速排序方法在(B)情况下最不利于发挥其长处。 A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数 L-利用12这四个值作为叶子结点的权,生成一棵哈夫曼树,该树中所有叶子的最长带权路径长度为(A)。 A.18B.16C.12D.30 L-利用n个值作为叶结点的权生成的哈夫曼树中共包含有(B)个双支结点。 A.nB.n-1C.n+1D.2*n-1 L-利用n个值作为叶结点的权生成的哈夫曼树中共包含有(D)个结点。 A.nB.n+1C.2*nD.2*n-1 L-利用双向链表存储线性表的优点是(B)。 A.便于单向进行插入和删除的操作B.便于双向进行插入和删除的操作C.节省空间D.只便于插入操作,不便于删除操作 L-链表不具有的特点是(A)。 A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比 L-链表所具备的特点是(C)。 A.可以随机方位任一结点B.占用连续的存储空间C.插入删除元素的操作不需要移动元素结点D.可以通过下标对链表进行直接访问 L-链式桟与顺序桟相比,一个比较明显的优点是(B)。 A.插入操作更加方便B.通常不会出现桟满的情况C.不会出现桟空的情况D.删除操作更加方便 L-两个字符串相等的条件是(D)。 A.两串的长度相等B.两串包含的字符相同C.两串的长度相等,并且两串包含的字符相同D.两串的长度相等,并且对应位置上的字符相同 L-邻接表是图的一种(B)。 A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构 M-每次把待排序的区间划分为左、右两个子区间,其中左区间中记录的关键字均小于等于基准记录的关键字,右区间中记录的关键字均大于等于基准记录的关键字,这种排序称为(B)。 A.插入排序B.快速排序C.堆排序D.归并排序 P-排序方法中,从尚未排序序列中挑选元素,并将其依次放入已排序序列(初始为空)的一端的方法,称为(D)排序。 A.归并B.插入C.快速D.选择 P-排序过程中,每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置,直到全部排好序为止,该排序算法是(A)。 A.直接插入排序B.快速排序C.冒泡排序D.选择排序 P-排序算法中,从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(要求比较次数尽量少),然后将其放入已排序序列的正确位置的方法是(C)。 A.冒泡B.直接插入C.折半插入D.选择排序 P-判断一个顺序队列sq(最多元素为m0)为空的条件是(C)。 A.sq->rear-sq->front==m0B.sq->rear-sq->front-1==m0C.sq->front==sq->rearD.sq->front==sq->rear+1 P-判断一个循环队列Q(最多元素为m0)为空的条件是(A)。 A.Q->front==Q->rearB.Q->front! =Q->rearC.Q->front==(Q->rear+1)%m0D.Q->front! =(Q->rear+1)%m0 P-判断栈S满(元素个数最多n个)的条件是(C)。 A.s->top==0B.s->top! =0C.s->top==n-1D.s->top! =n-1 Q-请指出在顺序表{452}中,用二分法查找关键码12需
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 1252 正式