数据结构（C语言版）习题(2)

数据结构习题二 2/8

中_______________个用于指向孩子，_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。

11. 在线性表的散列存储中，处理冲突的常用方法有________________________和_____________________________两种。

12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用

________________________排序。

?00001? ?00000???

?0?1000?三、 运算题 ??1. 已知一个6?5稀疏矩阵如右所示，试： 0000?2???50000?（1） 写出它的三元组线性表； ??（2） 给出三元组线性表的顺序存储表示。 00700?? ??2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从 空树起，逐个输入各个数据而生成的二叉搜索树。

3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：

(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 4. 已知一个图的顶点集V和边集E分别为：

V={1,2,3,4,5,6,7};

E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};

若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。

图6

四、 阅读算法 1. int Prime(int n)

{ int i=1;

int x=(int) sqrt(n);

while (++i<=x)

if (n%i==0) break; if (i>x) return 1; else return 0; }

(1)指出该算法的功能；

(2)该算法的时间复杂度是多少？

2. 写出下述算法的功能： void AJ(adjlist GL, int i, int n)

数据结构习题二 3/8

{

Queue Q;

InitQueue(Q); cout<

while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) {

int j=p->adjvex; if(!visited[j]) {

cout<

p=p->next; } } }

五、 算法填空

如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) {

int low=0; int high=n-1;

while (low<=high) {

int mid=_______________________________；

if (K==A[mid].key) return mid; //查找成功，返回元素的下标

else if (K<[mid].key)

______________________________________; //在左子表上继续查找

else __________________________________; //在右子表上继续查找

}

return -1; //查找失败，返回-1 }

六、 编写算法

HL是单链表的头指针，试写出删除头结点的算法。 ElemType DeleFront(LNode * & HL)

数据结构习题二 4/8

习题二参考答案

一、 单选题

1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、 填空题

1. 联系 图（或图结构） 2. 尾 首 3. top==0 4. O（1） O（n）

5. 128 44 108 6. 3 3 7. 有序 n-1

6 5 5 8. 有序序列 后缀表达式（或逆波兰式） 1 5 1 9. 2n n-1 n+1 3 2 -1 10. 2i+1 2i+2 (i-1)/2 4 5 -2 11. 开放定址法 链接法 5 1 5 12. 快速 归并 6 3 7 图7 三、 运算题 1. （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分) （2） 三元组线性表的顺序存储表示如图7示。

2. 如图8所示。

3. DFS：????? BFS：????? 4. 拓朴排序为： 4 3 6 5 7 2 1 四、阅读算法

1. (1) 判断n是否是素数（或质数） （2）O（n）

2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。 五、 算法填空

(low+high)/2 high=mid-1 low=mid+1 六、 编写算法

ElemType DeleFront(LNode * & HL) {

if (HL==NULL){ cerr<<\空表\

exit(1); }

LNode* p=HL; HL=HL->next;

ElemType temp=p->data; delete p; return temp; }

图8