专升本试题(数据结构).doc

数据结构专升本考试试题 （2015年3月）一、单项选择题（本大题共20小题，每小题2分，共40分）1对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。 (A) 正确性 (B) 可行性 (C) 健壮性 (D) 输入性2设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ ）。for(i=n-1；i=0；i-) for(j=0；jnext; p-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-next;9 Huffman树的带权路径长度WPL等于（ ）（A）除根结点之外的所有结点权值之和 （B）所有结点权值之和（C）各叶子结点的带权路径长度之和 （D）根结点的值10线索二叉链表是利用（ ）域存储后继结点的地址。 （A）lchild （B）data （C）rchild （D）root11研究数据结构就是研究（ ）。（A） 数据的逻辑结构 （B） 数据的存储结构 （C） 数据的逻辑结构和存储结构 （D） 数据的逻辑结构、存储结构及其基本操作12算法分析的两个主要方面是（ ）。 （A）空间复杂度和时间复杂度 （B）正确性和简单性 （C）可读性和文档性 （D）数据复杂性和程序复杂性13若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。（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,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=Beijing&Nanjing，SUBSTR(S,4,5)=（ ）。（A）ijing （B）jing&（C）ingNa（D）ing&N18广义表(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 逻辑结构决定了算法的 ，而存储结构决定了算法的 。2 栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。3 线性表（a1,a2,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为 4 已知一双向链表如下(指针域名为next和prior)： y x e q p现将p所指的结点插入到x和y结点之间，其操作步骤为： ； ； ； ；5n个结点无向完全图的的边数为 ， n个结点的生成树的边数为 。6已知一有向无环图如下：EBACDFG 任意写出二种拓扑排序序列： 、 。7已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为 ，层序遍历序列为 。8数据的存储结构可用四种基本的存储方法表示，它们分别是 。9在图形结构中，每个结点的前驱结点数和后续结点数可以 。10写出带头结点的双向循环链表L为空表的条件 。11哈夫曼树是其树的带权路径长度 的二叉树。12n个顶点的连通图至少有 条边。 三、应用题（本大题共6小题，共40分）1设散列函数H(k)=k % 13,设关键字系列为22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。(8分)(1) 构造HASH表。(2) 分别求查找成功和不成功时的平均查找长度。2 给定表（19,14,22,15,20,21,56,10）。（6分）（1） 按元素在表中的次序，建立一棵二叉排序树。（2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。3 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过程。并指出具有n个元素的插入排序的时间复杂度是多少？(6分)4 已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出该二叉树。（5分）5 已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(6分) A B C D E F6已知数据六个字母及在通信中出现频率如下表：ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作(9分，要有过程)。（1）画出对应的Huffman树。（2）计算带权路径长度WPL。（3）求A、B、C、D、E、F的Huffman编码。四、程序分析填空题（本大题共2小题，每小题5分，共10分）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实现顺序表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L,int i) int k; if(iL-length) return ERROR;for(k=i-1;klength-1;k+) L-slistk= （