《数据结构》-数据结构试题

数据结构试题一选择题（从下列答案选项中选出一个正确答案，每小题2分1线性表就是顺序表，这种说法（）。A正确B错误2若已知一个栈的入栈序列是1,2,3,4,5，不可能得到的输出序列是（）。A2,3,4,1,5B5,4,1,3,2C2,3,1,4,5D1,5,4,3,23串的逻辑结构与（）的逻辑结构不同。A栈B队列C树D线性表4如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）A正确B错误5设有两个串P和Q，求Q在P中首次出现的位置的操作称为（）。A连接B模式匹配C求子串D求串长6已知模式串T“ABCAABBCABCAABDAB”，该模式串的NEXT数组值为（）。A1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1B0，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1C1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1，D1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，17设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，A11为第一个元素，其存储地址为1，每个元素占1个地址空间，则A85的地址为（）。A13B33C18D408若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法（）。A正确B错误9树形结构的特点是一个结点可以有（）。A、多个直接前趋B、多个直接后继C、多个前趋D、一个后继10在一棵高度为H的满三叉树中，结点总数为（）A、3H1B、3H1/2C、3H1/3D、3H11设森林T中有4棵树，结点个数依次为N1,N2,N3,N4，当把森林T转换成一棵二叉树后，二叉树根结点的右子树上有（）个结点。AN11BN1CN1N2N3DN2N3N412任何一个无向连通图的最小生成树（）。A只有一颗B有一颗或多棵C一定有多棵D可能不存在13一个无向连通图的生成树是含有该连通图的全部顶点的（）。A、极小连通子图B、极小子图C、极大连通子图D、极大子图14在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零，这种说法。A正确B错误15对于关键字序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为（）的结点开始。A100B60C12D1516下列排序算法中，时间复杂度不受数据初始状态影响，恒为ONLOG2N）的是（）A、堆排序B、冒泡排序C、直接选择排序D、快速排序17下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。A、选择B、冒泡C、归并D、堆18在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（）型调整使其平衡。ALLBLRCRLDRR19常采用下面几种方式解决散列法中出现的冲突问题（）。A数字分析法、除余法、平方取中法B数字分析法、除余法、线性探测法C数字分析法、线性探测法、多重散列法D线性探测法、多重散列法、链地址法二填空题（每空2分）1以下程序段的时间复杂度是_，其中N为正整数。VOIDFUNINTNINTI1,K100WHILEI1I_/建初始堆FORINI1I/进行N1趟堆排序TEMPR1R1RIRITEMPSIFT_/重建堆/FOR/HEAPSORT五算法设计题（算法中请加上必要的语句注释）数据结构试题一、判断题（共10分，每题1分）1、深度为H的非空二叉树的第I层最多有2I1个结点。（）2、在完全二叉树中,若某结点无左孩子,则它必是叶结点。（）3、一组权值，可以唯一构造出一棵赫夫曼树。4、在N个结点的无向图中,若边数多于N1,则该图必是连通图。（）5、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（）6、无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。（）7、折半查找只适用于有序表，包括有序的顺序表和有序的链表。（）8、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（）9、在初始数据为逆序时，冒泡排序所执行的比较次数最多。（）10、希尔排序在效率上较直接插入排序有较大的改进。但是不稳定的。（）二、填空题（共20分，每空2分）1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个_,，且存在一条从根到该结点的_。2、三个结点的二叉树，最多有_种形状。3、任何一棵二叉树，若N0，N2分别是度为0，2的结点的个数，则N0和N2的关系为_。4、设有10个值，构成赫夫曼树，则该赫夫曼树共有_个结点。5、在一个无向图中，所有顶点的度数之和等于所有边数的_倍。6、一个连通图的生成树是该图的_连通子图。若这个连通图有N个顶点,则它的生成树有_条边。7、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_。8、将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫_。三、选择题（共20分，每题2分）1、设X是一棵树，X是对应于X的二叉树，则X的后序遍历和X的_序遍历相同A先序B中序C后序D都不是2、设有100个元素，用折半查找法进行查找时，在查找成功的情况下，最大比较次数是_。A100B50C99D73、设散列表长M14,散列函数H（K）K11，已知表中已有4个结点R154R385R616R847，其他地址为空，如用线性探查法处理冲突，关键字为49的结点地址是_。A8B3C5D94、在含有N个项点有E条边的无向图的邻接矩阵中，零元素的个数为_。AEB2ECN2EDN22E5、图的深度优先遍历类似于树的_。A先序遍历B中序遍历C后序遍历D层次遍历6、下面关于图的存储的叙述中，哪一个是正确的。_A用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关8、用某种排序方法对关键字序列（23，72，21，47，15，27，59，35，20）进行排序时，前三趟的结果情况如下_23，21，47，15，27，59，35，20，7221，23，15，27，47，35，20，59，7221，15，23，27，35，20，47，59，72则所采用的排序方法是_A选择排序B起泡排序C归并排序D快速排序9、将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为_。A30B31C16D3210、如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_A有向完全图B连通图C强连通图D有向无环图四、应用题（共28分，每题4分）1、将下图转换为二叉树，对转换后的二叉树进行先序、中序、后序遍历序列。2、什么是赫夫曼（HUFFMAN）树有一组数值14、21、32、15、28，画出赫夫曼树，并计算其WPL。3、设一个有向图为GV,E,其中VV1,V2,V3,V4，E,画出该有向图，画出相应邻接表，写出从顶点V1出发进行深度优先和广度优先搜索得到的顶点序列。4、用序列（46，88，45，39，70，58，101，10，66，34）建立一个平衡的二叉排序树，画出ABCDEFGJ该树。5、已知一组键值序列为41，66，73，52，40，37，65，43，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。6、已知一组关键字为（26，36，41，38，44，15，68，12，06，51，25），用线性探查法解决冲突构造这组关键字的哈希表。表长取13，哈希函数HKEYK