2005级电类联合班数据结构课程期末考试正式卷b

华南理工大学2005级电类联合班数据结构课程期末考试B1填空题10题，4X10分1哈希表的长度M1000，哈希函数HKMKAMOD1，其中表示向下取整，若键值K60映射到位置500，则实数A的一个可能取值是。2有向图G的邻接矩阵为，则|E|4，图G是强连通图填写强、弱或不。3算法A的时间复杂度是LNN，算法B是NLNN，则当N很大时，算法A运行得更快。4多维数组CHARA345在内存中以行主序线性存放，且元素A012的内存地址是0X0100，则元素A123的内存地址是，如果以列主序线性存放，结果为。以16进制表示5插入排序在最好情况下的时间复杂度为ON，选择排序在平均情况下的时间复杂度为ONLOG2N。仅计算比较操作，用大O记法表示6二叉树节点的中序遍历结果为4251637。7高度为H的M叉树至少包含1个叶子节点，至多包含MH1个叶子节点。8在一个包含N个顶点的简单有向图中，如果每个顶点的入度都为1，则该图包含N条边。9若D,A,T,A,S,T,R,U,C,T,U,R,E表示一个最大堆的初始状态按照字母表顺序，使用非叶子节点下沉算法将其转化成合法的最大堆的过程中相同元素不需要交换，在相同元素中选择交换节点的时候，优先考虑左侧节点，一共需要做次数组元素的交换，你认为这一算法的平均时间复杂度是。10利用一个栈将输入序列1,2,3,4转换成输出序列，则可能的输出序列一共有14种。2单项选择题4题，4X4分1若长度为N的线性表采用链式存储结构，在其第I个位置插入一个新元素的时间复杂度为BAO1BONCON2DOLNN2要形成二叉搜索树，可能的节点插入序列为CA4,6,1,2,3B4,6,3,2,1C4,2,3,6,1D4,3,2,6,13假设数组A包含元素序列7,1,8,0,5,2,4,9，采用下列哪种排序算法将数组元素从小到大排序需要的元素交换次数最少A冒泡排序B选择排序C插入排序D快速排序以每一分划的第一个元素为基准4借助一个无约束的双向队列，能够从输入序列1,2,3,4,5得到的输出序列有AA5,3,1,4,2B5,2,3,4,1C5,2,3,1,4D5,1,3,2,43简答题4题，5X4分1使用深度优先遍历DFS从无向图G的顶点A出发，得到的顶点访问顺序是什么如果使用广度优先遍历呢假设有多个邻接顶点可供选择的时候，依据字母顺序2编写函数INTCOUNTLEAVESNODEROOT计算二叉树中的叶子节点个数，其中数据类型NODE定义如下STRUCTNODEINTDATANODELEFT,RIGHT/EQUALS0WHENNOCHILD3已知字符序列H,K,N,R,S,M,A,E的相对出现频度分别是1,2,4,8,16,25,50,100。使用依据这一信息构建的HUFFMAN编码对加密串111000010110110011101进行解码，要求画出HUFFMAN编码树并标出叶子节点的编码序列。分配编码时，权值小的边分配0，大的分配14插入字符串序列AT,NOW,NO,NOT,NOTHING,THE,TO,THERE到一个TRIE中，画出形成的树结构。普通节点用单圆圈表示，串终止节点用双圆圈表示4实现下面标注/TODO的函数，将链表A中奇数位置的元素头元素从0开始计数提取出来，放到链表的最后，不一定要维持原有元素的顺序，只要保证所有偶数位置的元素在奇数位置的元素前。10分STRUCTNODEINTDATANODENEXT/EQUALS0WHENLASTNODESHUFFLENODEA/TODO5栈STACK的接口有VOIDPUSHT,TPOP,INTSIZE和BOOLISEMPTY，现有两个STACKS1,S2且S2为空，要将S1中的元素全部放入S2，并且保持和S1中原本一样的顺序，但不允许使用额外的数据结构，仅能够使用一些辅助的非数组类型的变量，请用C简要描述你的算法，元素类型用T表示。10分6编写函数BOOLHASLOOPNODE