专升本试题(数据结构)

1、精选的文件数据结构考试题(2015年3月)第一，选择题(这个大问题共20个，每个小问题2个，共40个)1.算法在输入非法数据时也进行适当的处理。这称为()。(a)准确性(b)可行性(c)加固(d)可输入性2.将s设定为c语言的陈述式，当电脑执行下列演算法时，演算法的时间复杂度为():for(I=n-1；I=0；I-)for(j=0)；Jnextp-next=q . front-next；(B)p=q . front-next；q . front-next=p-next；(C)p=q . rear-next；p-next=q . rear-next；(D)p=Q-next；q-next=p-ne

2、xt；9.Huffman树的权重路径长度WPL等于()(a)除根节点外的所有节点权重之和(b)所有节点权重之和(c)每个叶节点的加权路径长度总和(d)根节点值10.队列二进制列表是使用()域存储后续节点的地址。(a)lchild(b)data(c)rchild(d)root11.研究数据结构是研究。(a)数据的逻辑结构(b)数据的存储结构(c)数据的逻辑结构和存储结构(d)数据的逻辑结构、存储结构和基本活动算法分析的两个主要方面是()。(a)空间复杂性和时间复杂性(b)准确性和简洁性(c)可读性和文档性(d)数据复杂性和程序复杂性13.线性表格中最常见的任务是查找第一个元素和查找第一个元素的第

3、一个元素，使用()保存方法最节省时间。(a)顺序表(b)单链路列表(c)双链路列表(d)单环路链路列表14.在长度为n的顺序表格中，在第I个元素之前插入新元素时，将()元素向后移动。(A) n-i (B) n-i 1 (C)n-i-1 (D)i15.非空循环单链路列表head的结束节点p满足()。(A) p-next=head (B) p-next=NULL(C) p=NULL (D)p=head16.如果堆栈的输入序列为a、b、c、d、e，则堆栈的不可输出序列为()。(A)a、B、c、d、e (B)d、e、c、B、A(C)d、C、e、a、b (D)e、D、C、b、a17.对于SUBSTR(S

4、，I，k)查找由从S中的第I个字符开始的连续k字符组成的子字符串的操作，s= beijin nanjin ，SUBSTR(S，4，5)=()。(a)“ijing”(b)“Jin”(c)“ingna”(d)“ingn”18.广义表(a)，a)的后缀为()。(A)A(B)(A)(C)()(D)(A)19.具有5个层次的二进制树的节点总数为()。(A)31 (B)32 (C)33 (D)1620.如果可以通过对无向图的某个顶点执行深度优先搜索来访问所有顶点，则此图形必须为()。(a)完整的图(b)连接的图(c)环(d)树第二，填空(这个大问题共20个空格，每个空白2分，共40分)1.逻辑结构决定了算

5、法的内容，存储结构决定了算法的内容。2.堆栈和队列都是正在插入和删除堆栈的线性表。3.定线表格(a1、a2、an)的顺序存储结构中，将每个单元的长度设置为l，将元素ai的存储地址LOC(ai)设置为4.已知的双向列表如下(指针域名为next和prior):yxeqp在x和y节点之间插入p指向的节点。操作步骤如下：乌苏娜5.n个节点无向完全图的边数为，n个节点的生成树的边数为。已知的无回路图形如下：ebacdfg随机编写两个拓扑排序序列，7.如果已知二进制树的中间顺序遍历序列是BCA，下一顺序遍历序列是CBA，则该二进制树的第一顺序遍历序列是，序列遍历序列是。8.数据的存储结构可以用四种基本存储

6、方法表示，每种方法。9.图形结构中每个节点的前一个节点数和下一个节点数都是可能的。10.创建进退刀节点的双向循环链接列表l为空的表格的条件。11.霍夫曼树是具有相应树的权重路径长度的二叉树。12.n个顶点的连接图形至少有一个角。第三，应用问题(这个大问题共6个问题，共40分)1.必须通过设置散列函数H(k)=k% 13并将关键字系列设置为22，12，24，6，45，7，8，13，21，以线性检测方法处理冲突。(8点)(1)配置哈希表。(2)分别查找成功和失败查找的平均查找长度。2.给定表(19，14，22，15，20，21，56，10)。(6分)(1)按表中元素的顺序创建第二个排序树。按中间顺

7、序遍历(2)生成的二进制排序树，以创建遍历序列。3.已知一维数组的数据为(18，12，25，53，18)，因此，请尝试使用插入排序(升序)过程。具有n个元素的插入对齐的时间复杂性是多少？(6分)4.已知二进制树的第一个遍历序列为ABCDEFGH，中间遍历序列为CBEDFAGH，并绘制此二进制树。(5分)5.已知网络的相邻矩阵如下：找到从顶点a开始的最小生成树。(6分)A B C D E F6.6个已知数据字符和通信频率如下表所示。abcdef0.150.150.10.10.20.3使用此字母和频率作为叶点和权重，完成以下任务(9点，需要过程):(1)绘制相应的哈夫曼树。(2)计算加权路径长度W

8、PL。(3)查找a、b、c、d、e、f的Huffman代码。第四，程序分析空白问题(这个大问题共2个小问题，每个小问题5分，共10分)1.函数GetElem实现返回单个连接列表的第I个元素。在空格中补充算法。Int getelem (link list l，int I，elemtype * e) link list p；int j；p=L-next；j=1；while(pji)return ERROR；* e=(2)；Return OK2.函数ListDelete_sq实现顺序表删除算法，在空格中补充整个算法。Int list delete _ sq (sqlist * l，int I) int k；if(i1 | | iL-length)return ERROR；for(k=I-1；k length-1；k)l-slis