专升本试题数据结构

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=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)162

5、0. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点, 则该图一定就是()。(A) 完全图(B) 连通图(C) 有回路(D) 一棵树二、填空题 ( 本大题共 20 个空 , 每空 2 分, 共 40 分)1 逻辑结构决定了算法的,而存储结构决定了算法的。2 栈与队列都就是一种的线性表 , 栈的插入与删除只能在进行。3 线性表 (a 1,a 2, ,a n) 的顺序存储结构中 , 设每个单元的长度为L, 元素 ai 的存储地址 LOC(ai)为4已知一双向链表如下 ( 指针域名为 next 与 prior):xyqpe现将 p 所指的结点插入到x 与 y 结点之间 , 其操作步骤

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

7、小题 , 共 40 分)1. 设散列函数 H(k)=k % 13, 设关键字系列为 22,12,24,6,45,7,8,13,21,要求用线性探测法处理冲突。 (8 分)(1) 构造 HASH表。(2) 分别求查找成功与不成功时的平均查找长度。（ 2） 对 (1) 中所建立的二叉排序树进行中序遍历, 写出遍历序列。3已知一维数组中的数据为 (18,12,25,53,18), 试写出插入排序 ( 升序 ) 过程。并指出具有 n 个元素的插入排序的时间复杂度就是多少？ (6 分)4已知二叉树的先序遍历序列为 ABCDEFGH,中序遍历序列为 CBEDFAGH,画出该二叉树。 (5 分)5已知一网络

8、的邻接矩阵如下, 求从顶点 A 开始的最小生成树。 (6 分)A B CDE FA651B653C572D15764E366F2462给定表 (19,14,22,15,20,21,56,10)。(6 分)（1） 按元素在表中的次序 , 建立一棵二叉排序树。6. 已知数据六个字母及在通信中出现频率如下表:L-slistk=(1);(2);return OK;五、算法设计题 ( 本大题共 2 小题 , 每小题 10 分, 共 20 分)1. 编写算法 , 实现带头结点单链表的逆置算法。ABCDEF0、 150、150、 10、10、20、 3把这些字母与频率作为叶子结点及权值, 完成如下工作 (9

9、 分, 要有过程 ) 。(1) 画出对应的 Huffman 树。(2) 计算带权路径长度 WPL。2. 设顺序表 va 中的数据元数递增有序。试写一算法, 将 x 插入到顺序表的适当位置上, 以保持该表的有序性。(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);r