数据结构）
专升本试题（
精品资料
9. Huffman树的带权路径长度WP等于(
)
(B)所有结点权值之和
《数据结构》专升本考试试题
(A)除根结点之外的所有结点权值之和
(D)根结点的值 (C)各叶子结点的带权路径长度之和
10.线索二叉链表是利用( )域存储后继结点的地址。 (A) lchild (B) data 11 .研究数据结构就是研究( (A)数据的逻辑结构
(C)数据的逻辑结构和存储结构 (C) rchild )。
(D) root
(B)数据的存储结构
(2015 年 3 月)
(D) 数据的逻辑结构、存储结构及其基本操作 一、单项选择题(本大题共20小题，每小题2分，共40分)
1 ?对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为( )
(A) 正确性 (B) 可行性 (C) 健壮性 (
D) 输入性
2?设S为C语言的语句，
计算机执行下面算法时，算法的时间复杂度为(
for(i=n-1 ； i>=0 ； i--) for(j=0 ; j
2 2
(A) n (B) O( nlgn) (C) O(n) (D) O(n ) 3 ?折半查找法适用于( )。
(A)有序顺序表 (B)有序单链表
(D)无限制 (C)有序顺序表和有序单链表都可以
4 ?顺序存储结构的优势是(
)。 (A)利于插入操作 (B)利于删除操作
(C)利于顺序访问 (D)利于随机访问 5 ?深度为k的完全二叉树，其叶子结点必在第( )层上
(A) k-1 (B) k (C) k-1 和 k (D) 1 至 k
6 ?具有60个结点的二叉树，其叶子结点有12个，则度为1的结点数为(
(A) 11 (B) 13 (C) 48 ( D 37 7.图的Depth-First Search(DFS) 遍历思想实际上是二叉树( )遍历方法的推广。
(A)先序 (B)中序 (C)后序 (D)层序 8 .在下列链队列Q中，元素a出队的操作序列为( ) Q
(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;
仅供学习与交流，如有侵权请联系网站删除 谢谢2
12.
。
算法分析的两个主要方面是(
) (B)正确性和简单性
(A)空间复杂度和时间复杂度
数据复杂性和程序复杂性
(C)可读性和文档性 (D) 个元素和找第i个元素的前趋元素，则采用 13. 若一个线性表中最常用的操作是取第i (A())存储方式最节省时间。顺序表 (B)单链表 (C)双链表 (D)单循环链表 14.在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动( 个元素。(A)
n-i (B) n-i+1
(C) n-i-1
(D) i
15 .非空的循环单链表head的尾结点p满足(
)。 (A) p->n ext==head (B) p->n ext==NULL
(C) p==NULL
(D) p==head
16.
一个的输入序列为：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,a
于17. S=Beijing &Nanjing 设SUBSTR(S,i,k)是求' ，SSUBSTR(S,4,5)=中从第i个字符开始的连续( )。k 个字符组成的子串的操作，则对
(A) ‘ ijing ' (B) ‘jing& ' (C) ‘ in gNa' (D) ‘ ing&N18.广义表((a),a)
的表尾是( )。
(A) a (B) (a) (C)() (D
19.在一棵具有5层的满二叉树中结点总数为( ) (A) 31
(B) 32
(C) 33
(D) 16
20.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是
(A)完全图
(B)连通图 (C)有回路 (D) —棵树
二、填空题(本大题共20个空，每空2分，共40分)
1. ______________________________ 逻辑结构决定了算法的 ___________________________________ ，而存储结构决定了算法的 ____________ < 2.
栈和队列都是一种 ________ 的线性表，栈的插入和删除只能在 ________ 进行
精品资料
3. 地
线性表(ai,a2,…,an)的顺序存储结构中，设每个单元的长度为 L,元素ai的存储
三、应用题(本大题共6小题，共40分)
1.设散列函数H(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21}, 探测
法处理冲突。(8分) (1) 构造 HASHg。
要求用线性
址LOC(a)为
4. 已知一双向链表如下(指针域名为next和prior):
现将p所指的结点插入到x和y结点之间，其操作步骤为： _________________________
5. ___________________________________________ n个结点无向完全图的的边数为 的边数
为 ____________________ 。 6. 已知一有向无环图如下：
任意写出二种拓扌卜排序序列： ____________________ 、 ______________________ 。
7. 已知二叉树的中序遍历序列为 BCA后序遍历序列为CBA则该二叉树的先序遍历序列 为 _________________ ，层序遍历序列为 __________________ 。 8. 数据的存储结构可用四种基本的存储方法表示，它们分别
9. 在图形结构中，每个结点的前驱结点数和后续结点数可
以 ____________________________ 。
10. 写出带头结点的双向循环链表 L为空表的条件 _____________________________ 11. ______________________________________ 哈夫曼树是其树的带权路径长度 ___________________________________________ 的二叉树。
仅供学习与交流，如有侵权请联系网站删除谢谢3
n个结点的生成树(2)分别求查找成功和不成功时的平均查找长度。 2 .给定表(19,14,22,15,20,21,56,10
)。( 6 分)
(1)按元素在表中的次序，建立一棵二叉排序树。
(2) 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列
3.已知一维数组中的数据为(18,12,25,53,1^ ),试写出插入排序(升序)过程。并指出具 有n
素的插入排序的时间复杂度是多少？
(6分)
,
专升本试题(数据结构)教学文案
