专升本试题(数据结构)

1、数据结构专升本考试试题（ 20XX 年 3 月）一、单项选择题（本大题共20 小题，每小题 2 分，共 40 分）1对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。(A)正确性(B)可行性(C)健壮性(D)输入性2设 S 为 C 语言的语句 , 计算机执行下面算法时，算法的时间复杂度为（）。for(i=n-1；i>=0 ；i-)for(j=0；j<i ；j+) S；(A) n2(B) O(nlgn)(C) O(n)(D) O(n2)3折半查找法适用于（）。（A）有序顺序表（B）有序单链表（C）有序顺序表和有序单链表都可以（D）无限制4顺序存储结构的优势是（）

2、。（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-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。（A）先序（ B）中序（ C）后序（ D）层序8在下列链队列 Q中，元素 a 出队的操作序列为（）。frontabcd Qrear（ A） p=Q.front->next; p->ne

3、xt= 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

4、）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

5、-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） jin

6、g& （ 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,a 2,a n）的顺序存储结构中，设每个

7、单元的长度为L，元素 ai 的存储地址 LOC(ai)为4已知一双向链表如下 ( 指针域名为 next 和 prior)：xyqpe现将 p 所指的结点插入到x 和 y 结点之间，其操作步骤为：；5 n 个结点无向完全图的的边数为， n个结点的生成树的边数为。6已知一有向无环图如下：BFDGACE任意写出二种拓扑排序序列：、。7已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。8数据的存储结构可用四种基本的存储方法表示， 它们分别是。9在图形结构中， 每个结点的前驱结点数和后续结点数可以。10写出带头结点的双向循环链表L 为空表的条件。11哈夫

8、曼树是其树的带权路径长度的二叉树。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） ,试写出插入排序（升序）

9、过程。并指出具有 n 个元素的插入排序的时间复杂度是多少？(6 分)4已知二叉树的先序遍历序列为 ABCDEFGH，中序遍历序列为 CBEDFAGH，画出该二叉树。（5 分）5已知一网络的邻接矩阵如下，求从顶点A 开始的最小生成树。 (6 分 )A B CDE FA651B653C572D15764E366F2466已知数据六个字母及在通信中出现频率如下表：ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作(9 分，要有过程 ) 。（1）画出对应的 Huffman 树。（2）计算带权路径长度WPL。（3）求 A、B、C、D、E、F 的 Huff

10、man 编码。四、程序分析填空题（本大题共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&&j<i)(1) ;+j;if(!p|j>i) return ERROR;*e=(2);return OK;2函数 ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L,int i)int k;if(i<1|i>L->length) return ERROR;for(k=i-1