《数据结构》作业
本课程作业由两部分组成。第一部分为“客观题部分”，由选择题组成，每题1分，共15分。第二部分为“主观题部分”，由和应用题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。
客观题部分：
一、选择题（每题1分，共10题）
1、顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的。
A.线性结构 B.非线性结构
C.存储位置 D.指针
2、算法指的是（ ）。
A.对特定问题求解步骤的一种描述，是指令的有限序列。
B.计算机程序
C.解决问题的计算方法
D.数据处理
3、算法在发生非法操作时可以作出处理的特性称为（ ）。
A.健壮性 B.确定性
C.可行性 D.正确性
4、若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（ ）存储方法最节省时间。
A.顺序表 B.单链表
C.双链表 D.单循环链表
5、头结点的单链表head为空的判定条件是（ ）。
A.head==NULL B.head->next==NULL
C.head->next==head D.head!=NULL
6、单循环链表的主要优点是（ ）。
A.不再需要头指针了
B.从表中任一结点出发都能扫描到整个链表；
C.已知某个结点的位置后，能够容易找到它的直接前趋；
D.在进行插入、删除操作时，能更好地保证链表不断开。
7、使用双向链表存储线性表，其优点是可以（ ）。
A.方便双向查找 B.更方便数据的插入和删除
C.节约存储空间 D.很快回收存储空间
8、设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ）。
A.S1的栈底位置为0，S2的栈底位置为n-1
B.S1的栈底位置为0，S2的栈底位置为n/2
C.S1的栈底位置为0，S2的栈底位置为n
D.S1的栈底位置为0，S2的栈底位置为1
9、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。
A.6 B.4
C.3 D.2
10、表达式a*(b+c)-d的后缀表达式是（ ）。
A.abcd*+- B.abc+*d-
C.abc*+d- D.-+*abcd
11、深度为k的完全二叉树至少有（）个结点。
A.2k-2+1 B.2k-1
C.2k-1 D.2k–1-1
12、一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。
A.n=h+m B.h+m=2n
C.m=h-1 D.n=2h-1
13、设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，根结点的左子树上有（）个结点。
A.n1-1 B.n1
C.n1+n2+n3 D.n2+n3+n4
14、有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找不成功的情况下，s和b的关系是（ ）。
A.s=b B.s>b
C.s D.不一定
15、散列技术中的冲突指的是（ ）。
A.两个元素具有相同的序号
B.两个元素的键值不同，而其他属性相同
C.数据元素过多
D.不同键值的元素对应于相同的存储地址
主观题部分：
一、（每题2.5分，共2题）
1、已知如图所示的有向图，请给出该图的：
（1）每个顶点的入/出度；
（2）邻接矩阵；
（3）邻接表；
（4）逆邻接表；
（5）强连通分量。
2、带头结点的链表和不带头结点的链表有什么不同？
二、应用题（每题5分，共2题）
1、如果矩阵A中存在这样的一个元素A[i][j]满足条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写一个函数计算出m×n的矩阵A的所有马鞍点。
2、有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树(请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉,并计算出带权路径长度WPL及该树的结点总数。
