1、 共 3 页 第 1 页 数据结构专升本考试试题（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.
2、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）正确
3、性和简单性 （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，则栈
4、的不可能输出的序列是（ ） 。（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=Beijingj=1;while(p*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= （1） ;（2 ） ; return OK;五、算法设计题（本大题共 2 小题，每小题 10 分，共 20 分）1编写算法，实现带头结点单链表的逆置算法。2设顺序表 va 中的数据元数递增有序。试写一算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。
