5． 树最适合用来表示_________。
A. 有序数据元素 B. 无序数据元素 C．
素之间具有分支层次关系的数据 D. 元素之间无关联的数据
6．
4个顶点的无向完全图有__________条边。
元
A. 6 B. 12 C. 16 D. 20
7．
散列表的装填因子越大，则发生冲突的可能性就_________。 A. 越小 B. 越大 C. 不确定
8. 在长度为n的有序表中折半查找一个元素的平均查找长度是_____。
(n2) (nlogn) (n) D. O(logn) 9. 下列方法中，________是不稳定的排序方法。
A. 折半插入排序 B. 直接插入排序 C. 冒泡排序 D. 堆排序 10．________二叉排序树可得到一个关键字的有序序列。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历
二、是非题：（每题1分，共10分）（说明：正确的选“A”,错误选“B” ） 1． 线性表的顺序存储结构优于链式存储结构。 （ ） 2． 空串和空格串是相同的。 （ ） 3． 图结构中，每个结点的前驱和后续都可以有任意多个。 （ ） 4． 快速排序算法在待排序数据有序时最不利于发挥其长处。 （ ） 5． 连通网的最小生成树是唯一的。 （ ） 6． 栈是FIFO的线性表。 （ ） 7． 由二叉树的先序和后序遍历序列不能唯一确定这棵二叉树。（ ） 8． 若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，
则该图一定是连通图。 （ ） 9． 折半查找方法要求查找表必须是关键字的有序表，但是对存储结构没有限
制。 （ ） 10．
在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上
的所有结点。 （ ）
主观题部分
一、简答题：（50分）
1. 若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）为什么（10分）
2.将下图所示森林转化为二叉树并在其上标出中序全线索。（10分）
3.已知如右图所示的有向图，写出该图的: (1)邻接矩阵 (2）一个可能的拓扑有序序列。 （10分）
4．设散列函数H(key)=key MOD 7,用线性探测再散列法解决冲突。对关键字序列{ 13，28，72，5，16，8，7，9，11，29 }在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。（10分）
5．对于序列{ 26，33，35，29，19，12，22 }，
（1）判断它是否是堆，若是，写出其是大顶堆还是小顶堆；若不是，把它调整为堆，写出调整的过程和调整后的序列。 （5分） （2）写出对该序列进行直接插入排序每一趟结束时的关键字状态。（5分）
二、算法设计题：（20分）
1、编写递归算法，计算二叉链表存储的二叉树的结点数目。（10分） 2、基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。 （10分）
附：答案或答案要点
第一章章节练习答案 （一）选择题：
1．D 2．C 3．A 4．C 5．A 6．B 7．B 8．D （二）判断题： 1．× 2．√ 3. × 4．√
第二章章节练习答案
（一）选择题： 1．B, A 2．C 3．C 4．C 5．A, B, C , A （二）判断题： 1．√ 2．√ 3．√ （三）问答题：
1． 应采用顺序结构。因为顺序表是随机存取的存储结构，在顺序表中存取任何元素所花的时间都一样。而链表是顺序存取的存储结构。
2． 应采用链式结构。因为在链表中是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素，效率高。
3． 头结点在位置上可视为首元结点的前驱，则做插入/输出操作时，i=1（即插入或删除的位置是1）时不需要做特别处理，否则i=1时需要修改头指针。 （四）算法题：
1． status insert_L (LinkList L, ElemType x)
{/*带头结点*/ LinkList p,s;
for (p=L; p->next && p->next->data
s->data=x; s->next=p->next; p->next=s; return OK; }
2．status insert_Sq(SqList *va,ElemType x)
{ int i;
if( va->length==va->listsize) exit OVERFLOW;
for( i=va->length-1;i>=0 && va->elem[i]>x;--i)
va->elem[i+1]= va->elem[i];
va->elem[i+1]=x; va->length++; return OK; }
3．void reverse(LinkList L) {/*带头结点*/ LinkList p;
p=L->next; L->next=NULL; for(; p; p=p->next){ q=p->next; p->next=L->next; L->next=p;
} }
第三章章节练习答案
（一）选择题： 3. B 5. B, A 6. A，C （二）判断题：1．√ 2．× 3．√ 4．√ （三）问答与算法题：
1． 所有可能的输出序列有：{ABC}、{ACB}、{BAC}、{BCA}、{CBA} 2．算法：
#define MAXQSIZE 100 typedef struct {
ElemType *elem; int front; int length; }CycQueue;
status EnQueue(CycQueue *Q, ElemType e) {
if (Q->length==MAXQSIZE) return ERROR; Q->elem[(Q->front+Q->length) % MAXQSIZE]=e; Q->length++; return OK; }
status DeQueue(CycQueue *Q, ElemType *e)
{
if (Q->length==0) return ERROR; *e= Q->elem[Q->front]; Q->length - -; return OK; }
第四章章节练习答案
2. D 3. B 4. D 5. B 6. A 1.× 2.× 3.× 4.× 第七章章节练习答案
1. B 2. A 3. B 4. B
1. √ 2. √ 3. √ 4. √ 1．
5. ×（一）选择题：（二）判断题：
（一）选择题：（二）判断题： （三）问答题：
郑州大学远程教育学院数据结构试题及答案
