kok电子竞技

1、 .wd.数据构造课程复习资料一、填空题：1.设需要对5个不同的记录关键字进展排序，那么至少需要比拟 4 次，至多需要比拟 10 次。2.设二叉排序树的高度为h，那么在该树中查找关键字key最多需要比拟 n 次。3.设在长度为20的有序表中进展二分查找，那么比拟一次查找成功的结点数有 1个，比拟两次查找成功有结点数有2个。4.数据构造从逻辑上划分为三种根本类型：线性构造、树型构造和 图型构造。5.在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有 n(n-1)条边。6.向一棵B_树插入元素的过程中，假设最终引起树根结点的分裂，那么新树比原树的

2、高度增加1。7.在堆排序的过程中，对任一分支结点进展筛运算的时间复杂度为O(log2n) ，整个堆排序过程的时间复杂度为O(nlog2n) 。8.在快速排序、堆排序、归并排序中，归并排序是稳定的。9.在有n个叶子结点的哈夫曼树中，总结点数是n-1 。1. 评卷人2. 得分3.4.10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，那么在二叉链表BT中所对应的结点一定左右子树空。11.数组A为对称矩阵，其中每个元素占5个单元。现将其下三角局部按行优先次序存储在起始地址为1000的连续的内存单元中，那么元素A5，6对应的地址是1225 。12.在有n个结点的无向图中，其边数最多为n(n-1

3、)/2。13.取出广义表A=(x,(a,b,c,d)中原子x的函数是head(A)。14.对矩阵采用压缩存储是为了节省空间。15.带头结点的双循环链表L为空表的条件是L-next=L-prior 或 L-next=L。16.设线性表中元素的类型是实型，其首地址为1024，那么线性表中第6个元素的存储位置是1044。17.对于顺序存储的栈，因为栈的空间是有限的，在进展入栈插入运算时，可能发生栈的上溢，在进展出栈删除运算时，可能发生栈的下溢。18.在双向链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。19.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。 20.折半查找的

4、存储构造仅限于顺序存储构造，且是有序的。21.对于一个顺序存储的线性表，在表头插入元素的时间复杂度为O(n),在表尾插入元素的时间复杂度为O(1)。22.在稀疏距阵所对应的三元组线形表中，每个三元组元素按行号为主序，列号为辅序的次序排列。23.中缀表达示3+X*2.4/5-6所对应的后缀表达示为3 x 2.4 5 6 *。24.在一棵高度为h的3叉树中，最多含有(3 h-1)/2结点。25.分析下面算法程序段，给出最大语句频度n3，该算法的时间复杂度是 O(n3)。for (i=0;in;i+)for (j=0;jnext!=p) q=q-next;s= new Node; s-data=e;

5、q-next= s ; /填空s-next= p ; /填空29.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q= p-next;p-next=q-next; /填空delete q ; /填空30.两个串相等的充分必要条件是两个串的长度相等且对应位置的字符一样。31.二维数组A1020采用列序为主方式存储，每个元素占一个存储单元并且A00的存储地址是200，那么A612的地址是200 +6 * 20 + 12= 326。32.二维数组A10.205.10采用行序为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000，那么A189的地址是1000 + (18-10

6、) * 6 + (9 - 5) * 4 = 1208。33.求以下广义表操作的结果：(1) GetTailGetHead(a,b),(c,d); (b)(2) GetTailGetHeadGetTail(a,b),(c,d) (d)34.一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是求矩阵第i列非零元素之和。35.一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是将矩阵第i行全部置为零。36.在利用快速排序方法对一组记录54，38，96，23，15，72，60，45，83进展快速排序时，递归调用而使用的栈所能到达的最大深度为2，共需递归调用的次数为4，其中第二次递归调用是对23

7、，38，15组记录进展快速排序。37.在堆排序，快速排序和归并排序中，假设只从存储空间考虑，那么应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；假设只从排序结果的稳定性考虑，那么应选取归并排序方法；假设只从平均情况下排序最快考虑，那么应选取快速排序方法；假设只从最坏情况下排序最快并且要节省内存考虑，那么应选取堆排序方法。38.称算法的时间复杂度为O(f(n)，其含义是指算法的执行时间和 f(n) 的数量级一样。39.在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。40.假设为循环队列分配的向量空间为Q20，假设队列的长度和队头指针值分别为13和17

8、，那么当前尾指针的值为 10。41.对于栈只能在栈顶插入和删除元素。42.设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，那么顺序栈的容量至少应为 3 。43.数据构造一般包括三个方面内容：数据的 逻辑构造，数据的存储构造及数据的运算。44.在包含n个结点的顺序表上做等概率插入运算，平均要移动n/2个结点。45.队列的特性是先进先出。46.二叉树中叶子数为30，仅有一个孩子的结点数为20，那么总结点数为79。47.中序遍历二叉排序树中的结点可以得到一个递增的关键字序列选填“先序、“中序或“后序。48.n个节点的连通图

9、至少有n-1条边。49.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑，应最好选择 快速排序排序。50.带有一个头结点的单链表head为空的条件是假设指针域的名称为nexthead-next=NULL。51.设一组初始关键字序列为(38，65，97，76，13，27，10)，那么第3趟简单项选择择排序后的结果为10,13,27,76,65,97,38。52.在拓扑排序中，拓扑序列的第一个顶点必定是 入度为零 的顶点。53.数据的逻辑构造分为两大类，它们是线性构造和 非线性构造。54.在单链表中假设结点指针域名称为next，删除指针P所指结点的后继结点的语句是p-next=p-

10、next-next。55.循环队列用数组datan存储元素值，用front,rear分别作为头尾指针，那么当前元素个数为(rear-front+n)%n。56.假设n为主串长，m 为子串长，那么串的朴素匹配算法最坏的情况下需要比拟字符的总次数n-m+1m 。57.广义表(a),(b),j,(d)的表尾是(b),j,(d)。58.二叉树有61个叶子节点，且仅有一个孩子的节点数为45，那么总节点数为 166 。59.解决计算机与打印机之间速度不匹配问题，须要设置一个数据缓冲区，应是一个 队列 构造。二、单项选择题：1.队列的特点是 B A.先进后出 B.先进先出 C.任意位置进出 D.前面都不正确

11、2.有n 个记录的文件，如关键字位数为d，基数为r，那么基数排序共要进展 遍分配与收集。 B A.n B.d C.r D.n - d3.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序 B A.都不一样 B.完全一样C.先序和中序一样，而与后序不同 D.中序和后序一样，而与先序不同4.设有198 个初始归并段，如采用K-路平衡归并三遍完成排序，那么K值最大为 C A.12 B.13 C.14 D.155.下面关于广义表的表达中，不正确的选项是 B A.广义表可以是一个多层次的构造 B.广义表至少有一个元素C.广义表可以被其他广义表所共享 D.广义表可以是一个递归表6.设二叉

12、树根结点的层次为0，一棵深度高度为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，以下关系式不正确的选项是 B A.f=c B.cf C.f=2k+1-a D.csk-17.从L=(apple,pear),(orange,banana)中，取出banana元素的表达式为 D A.head(tail(L) B.head(head(tail(L)C.tail(head(tail(L) D.head(tail(head(tail(L)8.以下文件的物理构造中，不利于文件长度动态增长的文件物理构造是 A A.顺序构造 B.链接构造 C.索引构造 D.Hash构造9.在数据构造中，数据元素可由

13、C A.实体 B.域 C.数据项 D.字段10.对于有n个顶点的有向图，由弗洛伊德FloyD算法求每一对顶之间的最短路径的时间复杂度是 D A.O(1) B.O(n) C.O(n) D.O(n3)11.对n个记录的文件进展快速排序，所需要的辅助存储空间为 B A.O1 B.Olog2n C.On D.On212.哈夫曼树中一定不存在 B A.度为0的结点 B.度为1的结点 C.度为2的结点 D.带权的结点13.下述哪一条是顺序存储方式的优点？ A A.存储密度大 B.插入和删除运算方便C.获取符合某种条件的元素方便 D.查找运算速度快14.有一个二维数组Amn，假设A00存放位置在600(10

14、)，A33存放位置在678(10)，每个元素占一个空间，问A23(10)存放在什么位置？脚注(10)表示用10 进制表示，m3 D A.658 B.648 C.633 D.65315.以下关于二叉树遍历的表达中，正确的选项是 A A.假设一个叶子是某二叉树的中序遍历的最后一个结点，那么它必是该二叉树的前序遍历最后一个结点B.假设一个结点是某二叉树的前序遍历最后一个结点，那么它必是该二叉树的中序遍历的最后一个结点C.假设一个结点是某二叉树的中序遍历的最后一个结点，那么它必是该二叉树的前序最后一个结点D.假设一个树叶是某二叉树的前序最后一个结点，那么它必是该二叉树的中序遍历最后一个结点16.第K层

15、二叉树的结点总数最多为 A A.2k-1 B.2k+1 C.2K-1 D.2k-117.线性表进展二分法查找，其前提条件是 C A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序18.n 个记录进展堆排序，所需要的辅助存储空间为 C A.O(1og2n) B.O(n)C.O(1) D.O(n2)19.线性表7，34，77，25，64，49，20，14进展散列存储时，假设选用HK=K%7作为散列函数，那么散列地址为0的元素有 个。 D A.1

16、B.2 C.3 D.420.以下关于数据构造的表达中，正确的选项是 D A.数组是不同类型值的集合 B.递归算法的程序构造比迭代算法的程序构造更为精炼C.树是一种线性构造 D.用一维数组存储一棵完全二叉树是有效的存储方法21.以下数据构造中哪一个是线性构造？ B A.有向图 B.队列 C.线索二叉树 D.B树22.在一个单链表HL中，假设要在当前由指针p指向的结点后面插入一个由q指向的结点，那么执行如下 语句序列。 D A.p=q; p-next=q; B.p-next=q; q-next=p;C.p-next=q-next; p=q; D.q-next=p-next; p-next=q;23

17、. 不是队列的根本运算。 A A.在队列第i个元素之后插入一个元素 B.从队头删除一个元素C.判断一个队列是否为空 D.读取队头元素的值24.假设一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，假设p1=n，那么pi为 C A.i B.n=i C.n-i+1 D.不确定25.栈的特点是 B ，队列的特点是A 。 A.先进先出 B.先进后出26.设有两个串p和q，求q在p中首次出现的位置的运算称作 B A.连接 B.模式匹配 C.求子串 D.求串长27.二维数组A中，每个元素Aij的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开场连续存放在存储器内，该数

18、组按列存放时，元素A47的起始地址为 B A.SA+141 B.SA+180 C.SA+222 D.SA+22528.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，那么其后序遍历的结点访问顺序是 D A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca29.在一非空二叉树的中序遍历序列中，根结点的右边 A A.只有右子树上的所有结点 B.只有右子树上的局部结点C.只有左子树上的局部结点 D.只有左子树上的所有结点30.具有6个顶点的无向图至少应有 条边才能确保是一个连通图。 A A.5 B.6 C.7 D.831.

19、二分查找和二叉排序树的时间性能 B A.一样 B.不一样32.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 B A.On2 B.O(nlog2n) C.O(n) D.O(log2n)33.在待排序的元素序列根本有序的前提下，效率最高的排序方法是 A A.插入排序 B.选择排序 C.快速排序 D.归并排序34.下述几种排序方法中，要求内存量最大的是 D A.插入排序 B.选择排序 C.快速排序 D.归并排序35.设有两个串p和q，求q在p中首次出现的位置的运算称作 B A.连接 B.模式匹配 C.求子串 D.求串长36.二维数组A中，每个元素Aij的长度为3个字节，行下标i从

20、0到7，列下标j从0到9，从首地址SA 开场连续存放在存储器内，该数组按列存放时，元素A47的起始地址为 B A.SA+141 B.SA+180 C.SA+222 D.SA+22537.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，那么其后序遍历的结点访问顺序是 D A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca38.在一非空二叉树的中序遍历序列中，根结点的右边 A A.只有右子树上的所有结点 B.只有右子树上的局部结点C.只有左子树上的局部结点 D.只有左子树上的所有结点39.具有6个顶点的无向图至少应有

21、条边才能确保是一个连通图。 A A.5 B.6 C.7 D.840.二分查找和二叉排序树的时间性能 B A.一样 B.不一样 C.可能一样 D.不确定41.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 B A.On2 B.O(nlog2n) C.O(n) D.O(log2n)42.在待排序的元素序列根本有序的前提下，效率最高的排序方法是 A A.插入排序 B.选择排序 C.快速排序 D.归并排序43.下面的序列中 是大顶堆。 D A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,14

22、4.对一个算法的评价，不包括如下 方面的内容。 B A.强健性和可读性 B.并行性 C.正确性 D.时空复杂度45.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，那么执行 A A.p-next=HL-next; HL-next=p B.p-next=HL; HL=pC.p-next=HL; p=HL D.HL=p; p-next=HL46.对线性表，在以下哪种情况下应当采用链表表示？ B A.经常需要随机地存取元素 B.经常需要进展插入和删除操作C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变47.一个栈的输入序列为1 2 3，那么以下序列中不可能是栈的输出序列

23、的是 C A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 348.每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是 B A.冒泡排序 B.简单项选择择排序 C.希尔排序 D.直接插入排序49.采用开放定址法处理散列表的冲突时，其平均查找长度 B A.低于链接法处理冲突 B.高于链接法处理冲突C.与链接法处理冲突一样 D.高于二分查找50.假设需要利用形参直接访问实参时，应将形参变量说明为 参数。 D A.值 B.函数 C.指针 D.引用51.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有一样的 A A.行号 B.列号 C.元素值 D.非零元素个数52.

24、快速排序在最坏情况下的时间复杂度为 D A.O(log2n) B.O(nlog2n) C.O(n) D.O(n2)53.从二叉搜索树中查找一个元素时，其时间复杂度大致为 C A.O(n) B.O(1) C.O(log2n) D.O(n2)54.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，那么该操作的时间复杂度为 D A.O(log2n) B.O(1) C.O(n2) D.O(n)55.设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为m的结点数为Nm，那么N0= B A.Nl+N2+Nm B.l+N2+2N3+3N4+(m-1)NmC.N2+

25、2N3+3N4+(m-1)Nm D.2Nl+3N2+(m+1)Nm56.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开场连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址为 C A.SA+141 B.SA+144 C.SA+222 D.SA+22557.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为 B A.uwvts B.vwuts C.wuvts D.wutsv58.深度为5的二叉树至多有 个结点。 C A.16 B.32 C.31 D.1059.在一个无向图中，所有顶点的度数之和等于所有边数

26、的 倍。 C A.1/2 B.1 C.2 D.460.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 C A.n B.n/2 C.(n+1)/2 D.(n-1)/261.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为 C A.On2 B.O(nlog2n) C.O(n) D.O(log2n)62.下述几种排序方法中，要求内存量最大的是 D A.插入排序 B.选择排序 C.快速排序 D.归并排序63.排序方法中，从未排序序列中依次取出元素与已排序序列初始时为空中的元素进展比拟，将其放入已排序序列的正确位置上的方法，称为 C A.希尔排序 B.起泡排序 C.插入

27、排序 D.选择排序64.对于长度为9的有序顺序表，假设采用折半搜索，在等概率情况下搜索成功的平均搜索长度为 的值除以 9。 C A.20 B.18 C.25 D.2265.在有向图中每个顶点的度等于该顶点的 C A.入度 B.出度 C.入度与出度之和 D.入度与出度之差66.在基于排序码比拟的排序算法中， 算法的最坏情况下的时间复杂度不高于O(n10g2n)。 C A.起泡排序 B.希尔排序 C.归并排序 D.快速排序67.当的值较小时，散列存储通常比其他存储方式具有 的查找速度。 B A.较慢 B.较快 C.一样 D.不清楚68.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码

28、查询时找到一个表项的平均探查次数不超过1.5，那么散列表项应能够至少容纳 个表项。 A (设搜索成功的平均搜索长度为Snl1+l(1一)2，其中为装填因子)A.400 B.526 C.624 D.67669.堆是一个键值序列k1,k2,.kn,对I=1,2,.|_n/2_|,满足 C A.kik2ik2i+1 B.kik2i+1k2iC.kik2i且kik2i+1(2i+1n) D.kik2i或kik2i+1(2i+1n) 70.假设将数据构造形式定义为二元组(K，R)，其中K是数据元素的有限集合，那么R是K上 B A.操作的有限集合 B.映象的有限集合 C.类型的有限集合 D.关系的有限集合

29、71.以下图示的顺序存储构造表示的二叉树是 A 72.由同一关键字集合构造的各棵二叉排序树 B A.其形态不一定一样，但平均查找长度一样 B.其形态不一定一样，平均查找长度也不一定一样C.其形态均一样，但平均查找长度不一定一样 D.其形态均一样，平均查找长度也都一样73.ISAM文件和VSAM文件的区别之一是 C A.前者是索引顺序文件，后者是索引非顺序文件B.前者只能进展顺序存。笳咧荒芙顾婊嫒.前者建立静态索引构造，后者建立动态索引构造D.前者的存储介质是磁盘，后者的存储介质不是磁盘74.以下描述中正确的选项是 D A.线性表的逻辑顺序与存储顺序总是一致的B.每种数据构造都具备三个

30、根本运算：插入、删除和查找C.数据构造实质上包括逻辑构造和存储构造两方面的内容D.选择适宜的数据构造是解决应用问题的关键步骤75.下面程序段的时间复杂度是 B I=s=0While(srear=Q-front B.(Q-rear+1)%maxsize=Q-frontC.Q-rear=0 D.Q-front=088.设有一广义表E=a,b,(c,d)，其长度为 A A.2 B.3 C.4 D.589.某二叉树的前序遍历序列为ABDEFC，中序遍历序列为DBEFAC，那么后序遍历序列为 D A.DFEBCA B.DBECFA C.BDAECF D.DBEFCA90.以下 不是利用查找表中数据元素的

31、关系进展查找的方法。 C A.有序表的查找 B.二叉排序树的查找 C.平衡二叉树 D.散列查找91.下述几种排序方法中，要求内存量最大的是 B A.插入排序 B.快速排序 C.归并排序 D.选择排序92.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 B A.1/2 B.1 C.2 D.493.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，那么执行 A A.p-next=HL-next; HL-next=p B.p-next=HL; HL=pC.p-next=HL; p=HL D.HL=p; p-next=HL94.对线性表，在以下哪种情况下应当采用链表表示

32、？ B A.经常需要随机地存取元素 B.经常需要进展插入和删除操作C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变95.一个栈的输入序列为1 2 3，那么以下序列中不可能是栈的输出序列的是 C A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 396.每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是 B A.冒泡排序 B.简单项选择择排序 C.希尔排序 D.直接插入排序97.采用开放定址法处理散列表的冲突时，其平均查找长度 B A.低于链接法处理冲突 B.高于链接法处理冲突C.与链接法处理冲突一样 D.高于二分查找98.假设需要利用形参直接访问实参时，应将

33、形参变量说明为 参数。 D A.值 B.函数 C.指针 D.引用99.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有一样的 A A.行号 B.列号 C.元素值 D.非零元素个数100.快速排序在最坏情况下的时间复杂度为 D A.O(log2n) B.O(nlog2n) C.O(n) D.O(n2)101.从二叉搜索树中查找一个元素时，其时间复杂度大致为 C A.O(n) B.O(1) C.O(log2n) D.O(n2)102.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，那么该操作的时间复杂度为 D A.O(log2n) B.O(1) C.O(n2) D.O(n)103.设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为m的结点数为Nm，那么N0= B A.Nl+N2+Nm B.l+N2+2N3+3N4+(m-1)NmC.N2+2N3+3N4+(m-1)Nm D.2Nl+3N2+(m+1)Nm104.设有序表中有1000个元素，那么用二分查找查找元素X 最多需要比拟 次。 B A.25 B.10 C.7 D.1105.设连通图G中的边集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，那么从顶点a出发可以得到一种深度优先遍历的顶点序列为