数据结构复习题及参考答案.docx
- 文档编号:17945678
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:57
- 大小:223.08KB
数据结构复习题及参考答案.docx
《数据结构复习题及参考答案.docx》由会员分享,可在线阅读,更多相关《数据结构复习题及参考答案.docx(57页珍藏版)》请在冰点文库上搜索。
数据结构复习题及参考答案
中南大学网络教育课程考试复习题及参考答案
数据结构(专科)
一、判断题:
1.数组是一种复杂的数据结构,数组元素之间的关系既不是线性的也不是树形的。
[]
2.链式存储在插人和删除时需要保持物理存储空间的顺序分配,不需要保持数据元素之间的
逻辑顺序。
[]
3.在用循环单链表表示的链式队列中,可以不设队头指针,仅在链尾设置队尾指针。
[]
4.通常递归的算法简单、易懂、容易编写,而且执行的效率也高。
[]
5.一个广义表的表尾总是一个广义表。
[]
6.当从一个小根堆(最小堆)中删除一个元素时,需要把堆尾元素填补到堆顶位置,然后再
按条件把它逐层向下调整,直到调整到合适位置为止。
[]
7.对于一棵具有n个结点,其高度为h的二叉树,进行任一种次序遍历的时间复杂度为O(h)。
[]
8.存储图的邻接矩阵中,邻接矩阵的大小不但与图的顶点个数有关,而且与图的边数也有关。
[]
9.直接选择排序是一种稳定的排序方法。
[]
10.闭散列法通常比开散列法时间效率更高。
[]
11.有n个结点的不同的二叉树有n!
棵。
[]
12.直接选择排序是一种不稳定的排序方法。
[]
13.在2048个互不相同的关键码中选择最小的5个关键码,用堆排序比用锦标赛排序更快。
[]
14.当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。
[]
15.一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。
[]
16.在用散列表存储关键码集合时,可以用双散列法寻找下一个空桶。
在设计再散列函数时,
要求计算出的值与表的大小m互质。
[]
17.在只有度为0和度为k的结点的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,
则有n0=nk+1。
[]
18.折半搜索只适用于有序表,包括有序的顺序表和有序的链表。
[]
19.如果两个串含有相同的字符,则这两个串相等。
[]
20.数组可以看成线性结构的一种推广,因此可以对它进行插入、删除等运算。
[]
21.在索引顺序表上实现分块查找,在等概率查找情况下,其平均查找长度不仅与表中元素个
数有关,而且与每一块中元素个数有关。
[]
22.在顺序表中取出第i个元素所花费的时间与i成正比。
[]
23.在栈满情况下不能作进栈运算,否则产生“上溢”。
[]
24.二路归并排序的核心操作是将两个有序序列归并为一个有序序列。
[]
25.对任意一个图,从它的某个顶点出发,进行一次深度优先或广度优先搜索,即可访问图的
每个顶点。
[]
26.二叉排序树或者是一棵空二叉树,或者不是具有下列性质的二叉树:
若它的左子树非空,则
根结点的值大于其左孩子的值;若它的右子树非空,则根结点的值小于其右孩子的值。
[]
27.在执行某个排序算法过程中,出现了排序码朝着最终排序序列位置相反方向移动,则该算
法是不稳定的。
[]
28.一个有向图的邻接表和逆邻接表中表结点的个数一定相等。
[]
29.在链队列中,即使不设置尾指针也能进行入队操作。
[]
30.如果一个串中的所有字符均在另一串中出现,则说前者是后者的子串。
[]
31.对称矩阵的存储只需要存储一半的数据元素。
[]
32.一棵二叉树的中序遍历序列与该二叉树转换成森林的后序遍历序列相同。
[]
33.用Prim算法和KruskAI算法求最小代价生成树的代价不一定相同。
[]
34.折半查找说法的前提之一是线性表有序。
[]
35.如果某数据结构的每一个元素都最多只有一个直接前驱,则其必为线性表。
[]
36.快速排序法在最好的情况下时间复杂度是O(n)。
[]
37.进栈、出栈操作的时间复杂度为O(n)。
[]
38.进栈操作时,必须判断栈是否已满。
[]
39.一个有序的单链表不能采用折半查找法进行查找。
[]
40.二叉排序树采用先序遍历可以得到结点的有序序列。
[]
41.对长度为100的有序线性表用二分法查找时,最小比较次数为0。
[]
42.一棵二叉排序树,根元素肯定是值最大的元素。
[]
43.设有两个串p和q,其中q是p的子串,把q在p中首次出现的位置作为q在p中的位置的
算法称为匹配。
[]
44.若有一个叶子结点是某子树的中序遍历的最后一个结点,则它必是该子树的先序遍历的最后
一个结点。
[]
45.对于n个记录的集合进行冒泡排序,在最坏的情况下的时间复杂度是O(n2)。
[]
46.用邻接矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结
点的个数有关,而与图的边数无关。
[]
47.哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突的方法。
[]
48.因为算法和程序没有区别,所以在数据结构中二者是通用的。
[]
49.不管是行优先还是列优先,二维数组的最后一个元素的存储位置都是一样的。
[]
50.直接插入排序时,关键字的比较次数与记录的初始排列无关。
[]
51.二叉树的先序遍历不可能与中序遍历相同。
[]
52.任何二叉树,不可能没有叶子结点。
[]
53.一个稀疏矩阵采用三元组法存储不可能是((5,3,7),(5,4,4),(5,3,5))。
[]
54.一个无序的顺序表不能采用折半查找法进行查找。
[]
二、选择题:
1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为[]
A.O(n)B.O(n/2)C.O
(1)D.O(n2)
2.带头结点的单链表first为空的判定条件是[]
A.first==NULLB.first->1ink==NULL
C.first->link==firstD.first!
=NUlL
3.当利用大小为n的数组顺序存储一个队列时,该队列的最大长度为[]
A.n-2B.n-lC.nD.n+1
4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。
在传值参数情形,需为对
应形式参数分配空间,以存放实际参数的副本;在引用参数情形,需保存实际参数的(),
在被调用程序中可直接操纵实际参数。
[]
A.空间B.副本C.返回地址D.地址
5.在一棵树中,()没有前驱结点。
[]
A.分支结点D.叶结点C.树根结点D.空结点
6.在一棵二叉树的二叉链表中,空指针域数等于非空指针域数加[]
A.2B.1C.0D.-1
7.对于长度为9的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索长度
为()的值除以9。
[]
A.20B.18C.25D.22
8.在有向图中每个顶点的度等于该顶点的[]
A.入度B.出度
C.入度与出度之和D.入度与出度之差
9.在基于排序码比较的排序算法中,()算法的最坏情况下的时间复杂度不高于O(n1og2n)。
[]
A.起泡排序B.希尔排序C.归并排序D.快速排序
10.当α的值较小时,散列存储通常比其他存储方式具有()的查找速度。
[]
A.较慢B.较快C.相同D.不清楚
11.设有一个含200个表项的散列表,用线性探查法解决冲突,按关键码查询时找到一个表项
的平均探查次数不超过1.5,则散列表项应能够至少容纳()个表项。
[]
(设搜索成功的平均搜索长度为ASL={1+l/(1一α)}/2,其中α为装填因子)
A.400B.526C.624D.676
12.堆是一个键值序列{k1,k2,…..kn},对I=1,2,….|_n/2_|,满足[]
A.ki≤k2i≤k2i+1B.ki C.ki≤k2i且ki≤k2i+1(2i+1≤n)D.ki≤k2i或ki≤k2i+1(2i+1≤n) 13.若将数据结构形式定义为二元组(K,R),其中K是数据元素的有限集合,则R是K上[] A.操作的有限集合B.映象的有限集合 C.类型的有限集合D.关系的有限集合 14.在长度为n的顺序表中删除第i个元素(1≤i≤n)时,元素移动的次数为[] A.n-i+1B.IC.i+1D.n-i 15.若不带头结点的单链表的头指针为head,则该链表为空的判定条件是[] A.head==NULLB.head->next==NULL C.head! =NULLD.head->next==head 16.引起循环队列队头位置发生变化的操作是[] A.出队B.入队C.取队头元素D.取队尾元素 17.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是[] A.2,4,3,1,5,6B.3,2,4,1,6,5 C.4,3,2,1,5,6D.2,3,5,1,6,4 18.字符串通常采用的两种存储方式是[] A.散列存储和索引存储B.索引存储和链式存储 C.顺序存储和链式存储D.散列存储和顺序存储 19.设主串长为n,模式串长为m(m≤n),则在匹配失败情况下,朴素匹配算法进行的无效位移次数为[] A.mB.n-mC.n-m+1D.n 20.二维数组A[12][18]采用列优先的存储方法,若每个元素各占3个存储单元,且第1个元 素的地址为150,则元素A[9][7]的地址为[] A.429B.432C.435D.438 21.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是[] A.(e,f)B.((e,f))C.(f)D.() 22.下列图示的顺序存储结构表示的二叉树是[] 23.n个顶点的强连通图中至少含有[] A.n-1条有向边B.n条有向边 C.n(n-1)/2条有向边D.n(n-1)条有向边 24.对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为[] A.(19,23,56,34,78,67,88,92)B.(23,56,78,66,88,92,19,34) C.(19,23,34,56,67,78,88,92)D.(19,23,67,56,34,78,92,88) 25.若在9阶B-树中插入关键字引起结点分裂,则该结点在插入前含有的关键字个数为[] A.4B.5C.8D.9 26.由同一关键字集合构造的各棵二叉排序树[] A.其形态不一定相同,但平均查找长度相同 B.其形态不一定相同,平均查找长度也不一定相同 C.其形态均相同,但平均查找长度不一定相同 D.其形态均相同,平均查找长度也都相同 27.ISAM文件和VSAM文件的区别之一是[] A.前者是索引顺序文件,后者是索引非顺序文件 B.前者只能进行顺序存取,后者只能进行随机存取 C.前者建立静态索引结构,后者建立动态索引结构 D.前者的存储介质是磁盘,后者的存储介质不是磁盘 28.下列描述中正确的是[] A.线性表的逻辑顺序与存储顺序总是一致的 B.每种数据结构都具备三个基本运算: 插入、删除和查找 C.数据结构实质上包括逻辑结构和存储结构两方面的内容 D.选择合适的数据结构是解决应用问题的关键步骤 29.下面程序段的时间复杂度是[] I=s=0 While(s {I++; s+=I; } A.O (1)B.O(n)C.O(log2n)D.O(n^2) 30.对于顺序表来说,访问任一节点的时间复杂度是[] A.O (1)B.O(n)C.O(log2n)D.O(n^2) 31.在具有n个节点的双链表中做插入、删除运算,平均时间复杂度为[] A.O (1)B.O(n)C.O(log2n)D.O(n^2) 32.经过下列运算后,QueueFront(Q)的值是[] InitQueue(Q);EnQueue(Q,a);EnQueue(Q,a);DeQueue(Q,x); A.aB.bC.1D.2 33.一个栈的入栈序列是a,b,c,则栈的不可能输出序列是[] A.acbB.abcC.bcaD.cab 34.循环队列是空队列的条件是[] A.Q->rear==Q->frontB.(Q->rear+1)%maxsize==Q->front C.Q->rear==0D.Q->front==0 35.设s3="IAM",s4="ATERCHER".则strcmp(s3,s4)=[] A.0B.小于0C.大于0D.不确定 36.一维数组的元素起始地址loc[6]=1000,元素长度为4,则loc[8]为[] A.1000B.1004C.1008D.8 37.广义表((a,b),c,d)的表尾是[] A.aB.bC.(a,b)D.(c,d) 38.对于二叉树来说,第Ⅰ层上至多有()个节点[] A.2iB.2i-1C.2i-1D.2i-1-1 39.某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF,则后序遍历序列为[] A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GDBEHFCA 40.M叉树中,度为0的节点数称为[] A.根B.叶C.祖先D.子孙 41.已知一个图如下所示,若从顶点a出发按宽度搜索法进行遍历,则可能得到的一种顶点序列为[] 42.堆的形状是一棵[] A.二叉排序树B.满二叉树C.完全二义树D.平衡二叉树 43.排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端 的方法,称为[] A.希尔排序B.归并排序C.插入排序D.选择排序 44采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为[] A.nB.n/2C.(n+1)/2D.(n-1)/2 45.散列查找是由键值()确定散列表中的位置,进行存储或查找[] A.散列函数值B.本身C.平方D.相反数 46.顺序文件的缺点是[] A.不利于修改B.读取速度慢C.只能写不能读D.写文件慢 47.索引文件的检索方式是直接存取或按()存取[] A.随机存取B.关键字C.间接D.散列 48.串的逻辑结构与()的逻辑结构不同。 [] A.线性表B.栈C.队列D.树 49.二叉树第i(i≥1)层最多有()个结点。 [] A.2iB.2iC.2i-1D.2i-1 50.设单链表中p指向结点A,若要删除A后结点(若存在),则需要修改p的操作为[] A.p->next=p->next->nextB.p=p->next C.p=p->next->nextD.p->next=p 51.设一数列的输入顺序为1,2,3,4,5,6,通过栈操作不可能排成的输出序列为[] A.3,2,5,6,4,1B.1,5,4,6,2,3C.2,4,3,5,1,6D.4,5,3,6,2,1 52.设字符串S1=’ABCDEFG’,S2=’PQRST’,则运算S=CONCAT(SUB(S1,2,LENGTH(S2)), SUB(S1,LENGTH(S2),2))的结果为[] A.‘BCQR’B.‘BCDEF’C.’BCDEFG’D.‘BCDEFEF’ 53.有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地 址为1,每个元素占1个地址空间,则a85地址为[] A.13B.33C.18D.40 54.如果结点A有3个兄弟,而且B为A的双亲,则B的度为[] A.3B.4C.5D.1 55.线索化二叉树中某结点D没有左孩子的必要条件是[] A.D->Lchild=nullB.D->ltag=1 C.D->Rchild=nullD.D->ltag=0 56.串的长度是[] A.串中不同字母的个数B.串中不同字符的个数 C.串中所含字符的个数,且大于0D.串中所含字符的个数 57.数组A[1…5,1…6]的每个元素占5个单元,将其按行优先次序存储在起始地址为1000的连续 的内存单元中,则元素A[5,5]的地址为[] A.1140B.1145C.1120D.1125 58.若用数组S[1..n]作为两个栈S1和S2的共同存储结构,对任何一个栈,只有当S全满时才不 能作入栈操作。 为这两个栈分配空间的最佳方案是[] A.S1的栈底未知为0,s2的栈底位置是n+1 B.S1的栈底未知为0,s2的栈底位置是n/2 C.S1的栈底未知为1,s2的栈底位置知是n D.S1的栈底未知为1,s2的栈底位置是n/2 59.队列操作的原则是[] A.先进先出B.后进先出C.只能进行插入D.只能进行删除 60.在有n个结点的二叉链表中,值为非空的链域的个数为[] A.n-1B.2n-1C.n+1D.2n+1 61.某二叉树的中序序列和后序序列正好相反,则该二叉树一定是()的二叉树。 [] A.空或只有一个结点B.高度等于其结点数 C.在任一结点无左孩子D.任一结点无右孩子 62.在具有n个结点且为完全二叉树的二叉排序树中查找一个关键值,其平均比较次数的数量级为[] A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2) 63.若表R在排序前已按键值递增顺序排列,则()算法的比较次数最少。 [] A.直接插入排序B.快速排序C.归并排序D.选择排序 64.下列排序算法中,时间复杂度不受数据初始状态影响,恒为O(log2n)的是[] A.堆排序B.冒泡排序C.简单选择排序D.快速排序 65.设有1000个元素,用二分法查找时,最小比较次数为[] A.0B.1C.10D.500 66.一个元素进入队列的时间复杂度是[] A.O (1)B.O(n)C.O(n2)D.O(log2n) 67.设一颗完全二叉树中根结点的编号为1,而且23号结点有左孩子但没有右孩子,则完全二叉 树总共有()个结点。 [] A.24B.45C.46D.47 68.下列排序方法中,()比较次数与记录的初始状态无关。 [] A.直接插入排序B.起泡排序C.快速排序D.直接选择排序 69.一棵Huffman树总共有11个结点,则叶子结点有()个。 [] A.5B.6C.7D.9 70.在一个无向图中,所有顶点的度数之和等于所有边数的()倍。 [] A.1/2B.1C.2D.4 71.采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为[] A.nB.n/2C.(n+1)/2D.(n-1)/2 72.采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为[] A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n) 73.下述几种排序方法中,要求内存量最大的是[] A.插入排序B.选择排序C.快速排序D.归并排序 74.排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较, 将其放入已排序序列的正确位置上的方法,称为[] A.希尔排序B.起泡排序C.插入排序D.选择排序 75.如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G},数据元素之间的关系为 A.线性结构B.树结构C.图结构D.链表结构 76.设有二维数组A[50][60],其元素长度为1个字节,按列优先顺序存储,首元素A[0][0]的地 址为200,则元素A[10][20]的存储地址为[] A.820B.720C.1210D.1410 77.一组记录(50,40,95,20,15,70,60,45,80)进行冒泡排序时,第一趟需进行相邻记 录的交换的次数为[] A.5B.6C.7D.8 78.具有20个结点的二叉树,其深度最多为[] A.4B.5C.6D.20 79.在具有N个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针, 则判断队空的条件为[] A.front==rearB.(rear+1)%MAXSIZE==front C.front-rear==1D.rear%MAXSIZE==front 80.一个5×5的对称矩阵采用压缩存储,需要存储()个元素。 [] A.5B.10C.15D.20 81.一个无向连通图有5个顶点、8条边,则其生成树将要去掉()条边。 [] A.3B.4C.5D.6 82.设一颗二叉树共有50个叶子结点(终端结点),则共有()个度为2的结点。 [] A.25B.49C.50D.51 83.数据结构是研究数据的()以及它们之间的相互关系。 [] A.理想结构、物理结构B.理想结构、抽象结构 C.物理结构、逻辑结构D.抽象结构、逻辑结构 84.线性表采用链式存储时,其地址[] A.必须是连续的B.部分地址必须是连续的 C.一定是不连续的D.连续与否均可以 85.设循环队列Q[1...N-1]的头尾指针为F,R,当插入元素时尾指针R加1,头指针F总是指向 队列中第一个元素的前一个位置,则队列中元素计数为[] A.R-FB.N-(R-F)C.(R-F+N)%ND.(F-R+N)%N 86.完成堆排序的全过程需要()个记录大小的辅助空间。 [] A.1B.nC.nlog2nD.n2 87.若给定关键字集合为{20,15,14,18,21,36,40,10},一趟快速排序结束时,键值的排列为[] A.10,15,14,18,20,36,40,21B.10,15,14,18,20,40,36,21 C.10,15,14,20,18,40,36,21D.15,10,14,18,20,36,40,21 88.有一棵二叉树如图所示,该树是[] A.二叉平衡树B.二叉排序树C.堆的形状D.以上都不是 89.设有一个10阶的对称矩阵a,采用压缩存储方式,以行序为主存储,a[0][0]的存储地址为100, 每元素占1个地址空间,则a[
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习题 参考答案