《数据结构》期末考试试题及答案.doc

《数据结构》期末考试试题及答案.doc《数据结构》期末考试试题及答案
《数据结构》期末考试试题及答案
1 / 14
《数据结构》期末考试试题及答案
页眉内容
贵州大学理学院数学系信息与计算科学专业
《数据结构》期末考试试题及答案
( 2003-2004 学年第 2 学期 )
一、 单项选择题
1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。
、正确性 (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．顺序存储结构的优势是（ ）。
（A）、利于插入操作 （B）、利于删除操作
（C）、利于顺序访问 （D）、利于随机访问
5．深度为 k的完全二叉树，其叶子结点必在第（ ）层上。
（A）、k-1 （B）、k （C）、 k-1和 k （ D）、1至 k
6．具有 60个结点的二叉树，其叶子结点有 12个，则度过 1的结点数为（ ）
Eckhard Wagner
《数据结构》期末考试试题及答案
《数据结构》期末考试试题及答案
14 / 14
《数据结构》期末考试试题及答案
页眉内容
（A）、11 （B）、13 （C）、48 （D）、37
7．图的 Depth-First Search(DFS)遍历思想实际上是二叉树（ ）遍历方法的推广。
（A）、先序 （B）、中序 （C）、后序 （D）、层序
8．在下列链队列 Q 中，元素 a 出队的操作序列为（ ）
front a b c
Q
（A）、 p=->next; p->next= ->next;
（B）、 p=->next; ->next=p->next;
（C）、 p=->next; p->next= ->next;
（D）、 p=Q->next; Q->next=p->next;
9． Huffman树的带权路径长度 WPL 等于（ ）
A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和
C）、各叶子结点的带权路径长度之和（ D）、根结点的值
10．线索二叉链表是利用（ ）域存储后继结点的地址。
（A）、 lchild （B）、 data （C）、rchild （D）、 root
二、填空题
1． 逻辑结构决定了算法的 ，而存储结构决定了算法的 。
《数据结构》期末考试试题及答案
《数据结构》期末考试试题及答案
3 / 14
《数据结构》期末考试试题及答案
Eckhard Wagner
《数据结构》期末考试试题及答案
《数据结构》期末考试试题及答案
14 / 14
《数据结构》期末考试试题及答案
页眉内容
2． 栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。
3． 线性表（ 1 2
n）的顺序存储结构中，设每个单元的长度为
L ，元素 ai 的存储地址 LOC(ai
为
a ,a , ,a
)
4． 已知一双向链表如下 (指针域名为 next和 prior)：
x y
q
e
p
现将 p所指的结点插入到 x和 y 结点之间，其操作步骤为： ；
； ； ；
5．n个结点无向完全图的的边数为 ，
n 个结点的生成树的边数为 。
6．已知一有向无环图如下：
任意写出二种拓扑排序序列：