专升本试题(数据结构)

《专升本试题(数据结构)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、序单链表都可以（D）无限制4．顺序存储结构的优势是（）。（A）利于插入操作（B）利于删除操作（C）利于顺序访问（D）利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。（A）k-1（B）k（C）k-1和k（D）1至k6．具有60个结点的二叉树，其叶子结点有12个，则度为1的结点数为（）。（A）11（B）13（C）48（D）377．图的Depth-FirstSearch(DFS)遍历思想实际上是二叉树（）遍历方法的推广。（A）先序（B）中序（C）后序（D）层序8．在下列链队列Q中，元素a出队

3、的操作序列为（）。bcd∧afrontrearQ（A）p=Q.front->next;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）根结点的值1

4、0．线索二叉链表是利用（）域存储后继结点的地址。（A）lchild（B）data（C）rchild（D）root11．研究数据结构就是研究（）。（A）数据的逻辑结构（B）数据的存储结构（C）数据的逻辑结构和存储结构（D）数据的逻辑结构、存储结构及其基本操作12．算法分析的两个主要方面是（）。（A）空间复杂度和时间复杂度（B）正确性和简单性（C）可读性和文档性（D）数据复杂性和程序复杂性13．若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。（A）顺序表（B

5、）单链表（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

6、．设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=‘Beijing&Nanjing’，SUBSTR(S,4,5)=（）。（A）‘ijing’（B）‘jing&’（C）‘ingNa’（D）‘ing&N’18．广义表((a),a)的表尾是（）。（A）a（B）(a)（C）()（D）((a))19．在一棵具有5层的满二叉树中结点总数为（）。（A）31（B）32（C）33（D）1620．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）

7、。（A）完全图（B）连通图（C）有回路（D）一棵树二、填空题（本大题共20个空，每空2分，共40分）1．逻辑结构决定了算法的，而存储结构决定了算法的。2．栈和队列都是一种的线性表，栈的插入和删除只能在进行。3．线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为4．已知一双向链表如下(指针域名为next和prior)：yxeqp现将p所指的结点插入到x和y结点之间，其操作步骤为：；；；；5．n个结点无向完全图的的边数为，n个结点的生成树的边数为。6．

8、已知一有向无环图如下：共3页第3页EBACDFG任意写出二种拓扑排序序列：、。7．已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。8．数据的存储结构可用四种基本的存储方法表示，它们分别是。9．在图形结构中，每个结点的前驱结点数和后续结点数可以。10．写出带头结点的双向循环链表L为空表的条件。11．哈夫曼树是其树的带权路径长度的二叉树。12．n个顶点的连通图至少有条边。三、应用题（本大题共6小题，共40分