专升本试题(数据结构)

1、 PAGE PAGE 5数据结构专升本考试试题（2015 3 月）一、单项选择题（本大题共 20 小题，每小题 2 分，共 40 分）对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（。正确性(B)可行性(C)健壮性(D)输入性设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（for(i=n-1；i=0；i-)for(j=0；jnext=head（B）p-next=NULL（C）p=NULL（D）p=head 16一个栈的输入序列为：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

2、,b,a17设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对S=Beijing&Nanjing，SUBSTR(S,4,5)=（。（A）ijing（B）jing&（C）ingNa18广义表(a),a)的表尾是（。（A）a（B）(a)（C）()19在一棵具有5层的满二叉树中结点总数为（。（A）31（B）32（C）33（D）16 20（。（A）完全图（B）连通图（C）有回路（D）一棵树二、填空题（本大题共 20 个空，每空 2 分，共 40 分）逻辑结构决定了算法的，而存储结构决定了算法的。栈和队列都是一种的线性表，栈的插入和删除只能在进行。（a,a,aLai

3、 的存储地址LOC(a)12n为p=Q.front-next; p-next=Q.front-next;p=Q.front-next;Q.front-next=p-next;p=Q.rear-next; p-next=Q.rear-next;p=Q-next;Q-next=p-next;Huffman树的带权路径长度WPL等于（）（A）除根结点之外的所有结点权值之和（B）所有结点权值之和（C）各叶子结点的带权路径长度之和（D）根结点的值线索二叉链表是利用（）域存储后继结点的地址。（A）lchild（B）data（C）rchild（D）root研究数据结构就是研究（。4nextprior)：xy

4、qpe现将p所指的结点插入到x和y结点之间，其操作步骤为：；xyqpe；5n 个结点无向完全图的的边数为， n 个结点的生成树的边为。6已知一有向无环图如下：BFBFDAGCE任意写出二种拓扑排序序列：、。 7已知二叉树的中序遍历序列为 BCA，后序遍历序列为 CBA，则该二叉树的先序遍历序为，层序遍历序列为。数据的存储结构可用四种基本的存储方法表示它们分别是。在图形结构中每个结点的前驱结点数和后续结点数可以。写出带头结点的双向循环链表L为空表的条件。哈夫曼树是其树的带权路径长度的二叉树。n个顶点的连通图至少有条边。三、应用题（本大题共 6 小题，共 40 分）1设散列函数 H(k)=k %

5、13,设关键字系列为22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。(8 分)HASH分别求查找成功和不成功时的平均查找长度。已知一维数组中的数据为（18,12,25,53,18）,（升序）n？(6ABCDEFGH，CBEDFAGH，画出该二叉树。（5 分）已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(6分A B CDE FA A 651B 653C 572D157643636246F 2给定表（19,14,22,15,20,21,56,10（6分）（1） 按元素在表中的次序，建立一棵二叉排序树。L-slistk=（1）;ABCABCDEF0.150.150.10.10.20.3（2）;return OK;把这些字母和频率作为叶子结点及权值，完成如下工作(9 分，要有过程)。HuffmanWPL。A、B、C、D、E、FHuffman四、程序分析填空题（2510）1函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。int GetElem(LinkList L,int i,Elemtype *e)LinkList p；int j；p=L-next;j=1; while(p&ji) return ERROR;*e=(2);return OK;2函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完