数据结构习题1

6、在一个具有n个顶点的有向完全图中，包含有 条边。 7、广义表((a),a)的表尾是 。

8、 设哈希(散列)表表长为15(哈希地址为0~14)，哈希函数为H(key)=key,冲突处理采用线性探测Hi=(H(key)+1),则将一列数15，20，26，30，35，40存储该哈希表，元素40的哈希地址为______________________。

9、表长为n的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素需移动元素的平均次数为___ __。

10、常用查找算法有顺序查找、二分查找、分块查找，这三种查找的时间效率由低到高的排列顺序为________________。

三、简答题（本题共4小题，每小题5分，满分20分

1、给定权值2，10，12，4，8，5，构造相应的哈夫曼树并求出带权路径长度WPL。

2、设某二叉树中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，请画出这棵二叉树并写出先序遍历序列和层次遍历序列。

3、写出用快速排序将关键字序列{44,13,79,38,54,40,15,80,24}排序过程（第一记录关键字为基准）的每一趟结果。

4、已知某有向图的邻接表如下图，顶点集合为{V1，V2，V3，V4，V5，V6 }，请完成 （1）画出该有向图；

（2）写出该有向图从V1开始的所有可能的拓扑排序序列。 0 1 2 3 4 5

V1 V2 V3 V4 ^ V5 V6 1 2 3 5 3 ^ ^ ^ ^ 1

^

四、算法完成题：根据算法思想，在下列每小题的所给横线上填上合适的语句或短语。（本题两小题共8个空，每空2分，满分16分）

1、下面是二分法（折半）查找算法。在给定有序（从小到大）的顺序表中，查找关键字值为k的记录，若找到，返回记录下标，否则返回-1。 typedef int KeyType; typedef struct

{ KeyType key; /*存放关键字*/

40

ElemType data; /*其他数据, */

} LineList;

int BinSearch(LineList R[],int n,KeyType k) { int i,low=0,high=n-1,mid; while ( ) { mid=(low+high)/2;

if (kR[mid].key) low= ； else return mid;

}

； }

2、下面是利用队列对二叉树进行从上往下，从左往右的层次遍历算法。 #define max 50 typedef struct btnode { char data;

struct btnode *lchild,*rchild; }bttree;

void lev_order(bttree *bt,int m) { bttree *queue[max]， bttree *p; int front=0,rear=0,i;

queue[ ]=bt; /*根结点进队*/ while( ) /*当队不空时*/ { p=queue[front]; front= ; printf(\ \ if(p->lchild!=NULL)

{ if((rear+1)%m!=front) /*队不满时*/ { queue[rear]=p->lchild;

rear=(rear+1)%m;

} }

if(p->rchild!= ) { if((rear+1)%m!=front) { queue[rear]=p->rchild;

rear=(rear+1)%m; } } }

41

}

五、算法设计题（本题共3小题，每小题8分，满分24分）

1、设计一个算法，功能是在带头结点的单链表head中删除数据域值最小的结点。 typedef int ElemType; typedef struct NODE { ElemType data; struct NODE *next; }node,*linklist;

2、 二叉树采用链式存储结构，结构定义如下，试设计一个递归算法计算一棵给定二叉树的

叶子结点数。 t ypedef struct BTNode {ElemType data;

3、已知有向图用邻接表为存储结构（如下），设计一算法计算有向图每一顶点的度的算法。

typedef struct arcnode

{ int adjvex;

struct arcnode *nextarc; }ARCNODE;

typedef struct vnode {char data[10];

ARCNODE *firstarc; }VNODE,ADJLIST[10]; typedef struct

{ ADJLIST vertices; int vexnum,arcnum; int digraph; }ALGRAPH;

struct BiTNode *lchild, *rchild; }BTNode, *BTtree;

参考答案

一、选择题：（本题共10小题，每小题2分，满分20分）

1、B 2、A 3、D 4、C 5、C 6、B 7、A 8、D 9、B 10、A

二、填空题：（本题共10小题，每小题2分，满分20分）

1、空间复杂度 2、p->next

3、一端删除，另一端插入（或先进先出或FIFO）。

42

4、2195 5、2i 6、n(n-1) 7 （a）

8、7 9、(n-1)/2 10、顺序查找、分块查找、二分查找

三、简答题（本题共4小题，每小题5分，满分20分

1、给定权值2，10，12，4，8，5，构造相应的哈夫曼树并求出带权路径长度wpl。 （2+4）*4+5*3+（8+12+10）*2=99

2、设某二叉树中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，请画出这棵二叉树并写出先序遍历序列和层次遍历序列。

先序：EACBDGF 层次：EAGCFBD

3、写出用快速排序将关键字序列{44,13,79,38,54,40,15,80,24}排序过程（第一记录关键字为基准）的每一趟结果。

第一趟：24 13 15 38 40 44 54 80 79 第二趟：15 13 24 38 40 44 54 80 79 第三趟：13 15 24 38 40 44 54 79 80.

4、已知一有向图的邻接表如下图，顶点集合为{V1，V2，V3，V4，V5，V6 }，请完成 （1）画出该有向图；

（2）写出该有向图从V1开始的所有可能的拓扑排序序列。

V1，V5，V2，V6，V3，V4 V1，V5，V6，V2，V3，V4 V1，V5，V2，V3，V6，V4

四、算法完成题：根据算法思想，在下列每小题的所给横线上填上合适的语句或短语。 （本题两小题共8个空，每空2分，满分16分）

1、二分法（折半）查找算法，在给定有序（从小到大）的顺序表中，查找关键字值为k的记录，若找到，返回记录下标，否则返回-1

依次为：low<=high mid-1 mid+1 return -1

2、下面是利用队列对二叉树进行从上往下，从左往右的层次遍历算法。

依次为：rear++、 front!=rear、 (front+1)%m或(front+1)%max或(front+1)、 NULL

五、算法设计题（本题共3小题，每小题8分，满分24分）

1、设计一个算法，功能是在带头结点的单链表head中删除数据域值最小的结点。 void delmin(linklist *head) {linklist q,p,r; Elemtype min;

p=(*head)->next;

min=p->data; while(p)

{ if(min>p->data)

min=p->data;

p=p->next;

}

43

p=(*head)->next;

q=*head; while(p)

{ if(min==p->data) { r=p->next;

q->next=p->next;

p=r; } else {q=p;

p=p->next; }

}

2、二叉树采用链式存储结构，结构定义如下，试设计一个递归算法计算一棵给定二叉树的叶子结点数。 int countleaf(BTtree bt) { int left,right;

if (bt==NULL) return 0; else if (bt->lrchild==NULL&&bt->rchild==NULL) return 1 ; else

{ left= countleaf(bt->lchild); right=countleaf(bt->rchild); return left+right; } }

3、已知有向图用邻接表为存储结构，设计一算法计算有向图每一顶点的度的算法。 void degree(ALGRAPH g) for(i=0;inextarc; }

for(i=0;i

for(i=0;i

for(i=0;i

{ degree[i]=indegree[i]+outdegree[i]; { p=g.vertices[i].firstarc;

printf(“=”,degree[i]); while(p)

{ k=p->adjvex; } indegree[k]++; } p=p->nextarc; }

}

44