数据结构与算法分析习题及参考答案(7)

6．矩阵压缩存储的方法都是用三元组表存储矩阵元素。 （ ）

7．结点数为n的完全二叉树的深度为log2n+1。 （ ） 8．在一个有向图的邻接表中，如果某个顶点的链表为空，则此顶点的度一定为零。 （ ） 9．在顺序表中取出第i个元素所花费时间与i成正比。 （ ） 10．在快速排序算法中，取待排序的n个记录中的某个记录（如第一个记录）的键值为基准，将所有记录分为两组，此记录就排在这两组的中间，这也是此记录的最终位置。

（ ） 四、简答题（每小题4分，共20分）

1．在双向循环链表中p所指结点之后插入s所指结点，设结点结构为(priou,data,next)，试给出语句序列。

2．对于下图，用Kruskal算法构造出一棵最小生成树，要求图示出每一步的变化情况。

3．已知一棵二叉树的后序序列与中序序列分别为DBECA与BDAEC，试画出此二叉树。 4．对于权值序列w={1,10,8,5,3,1,3}，试画出它对应的哈夫曼树。 5．已知关键字序列{12,26,38,89,56}，试构造平衡二叉树。 五、算法题（共25分）

1．程序填空题(每空2分，共8分)

下面程序的功能是二叉树的层次遍历的非递归算法，其中二叉树的结点结构为(lchild,data,rchild)，队列的常用方法有：入队EnQueue，出队DlQueue，判空QueueEmpty；试将程序补充完整。

template

void BiTree::levelorder(BiTreeNode *T, void (*Visit)(Type & e)){ Queue< BiTreeNode *>& Q; BiTreeNode *p

EnQueue(Q,T); ; while(! ){ ; if(p->lchild){

EnQueue(Q,p->lchild);visit(p->lchild->data) } if( ){

EnQueue(Q,p->rchild);visit(p->rchild->data) } }// while

}//levelorder

2．程序填空题(每空2分，共8分)

31

下面程序的功能是用链地址法处理冲突，哈希函数为H(key)=key % m，进行哈希表的插入算法。（如表中已存在关键字相同的记录，则不进行插入），试将程序补充完整。

typedef enum{SUCCESS,UNSUCCESS}Status; template typedef struct Node{ Type elem;

struct Node *next; }Node,*LinkList; template typedef struct {

LinkList *head; int m; }HashTable;

template

Status SerchHashTable(HashTable H,Type e){ int k=e.key % m;

Node *pre=NULL,*p=H[k].head; while(p&&p->elem.key!=e.key){ pre=p;p= ; }//while if(!p){

Node *q=new Node; q->elem= ; pre->next= ;

q->next=NULL; //将q追加在相应链表的末尾 return SUCCESS; }

else return ; } //SerchHashTable

3．(9分)阅读下面的算法，试回答： （1）此算法的功能是什么？ （2）变量c的结果表明什么？

（3）对于如下的有向图，执行此算法后c的值是多少？

template

int MGraph::cid(MGraph g){ //g是有向图的邻接数组存储结构 int i,j,c=0;

for(j=0;j

32

i=0;

while(g.arcs[i,j]= =0&&i= g.vexnum)c++ }//for return c; }//cid

六、写算法（共20分）

1．(12分)以单链表为存储结构实现直接插入排序，排序的结果是单链表按关键字值升序排序，试编写此算法。算法申明如下：

template

void LinkList::StraitInsertSort(Lnode *la)

2．(8分)下面是一个二叉树的前序遍历的递归算法，试改写此算法，消去第二个递归调用PreOrder(T->rchild,Visit)。

template

void BiTree::PreOrder(BiTreeNode *T, void (*Visit)(Type& e)){ if(T){

Visit(T->data);

PreOrder(T->lchild,Visit); PreOrder(T->rchild,Visit); }//if

}//PreOrder

模拟试卷七参考答案

一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）

1．B） 2．D） 3．B） 4．C） 5．C） 6．C） 7．C） 8．C） 9．C） 10．D） 二、填空题（每空1分，共15分） 1．参考答案：引用型 2．参考答案：O(n4) 3．参考答案：112

4．参考答案：线性结构 5．参考答案：O(n) 6．参考答案：栈顶 栈顶指针 7．参考答案：3 x 2 + * 5 - 8．参考答案：4 9 9．参考答案：n-1

10．参考答案：邻接知阵 邻接表 11．参考答案：插入 12．参考答案：4

33

三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）

1．参考答案：√ 2．参考答案：× 3．参考答案：√ 4．参考答案：√ 5．参考答案：× 6．参考答案：× 7．参考答案：× 8．参考答案：× 9．参考答案：× 10．参考答案：√

四、简答题（每小题4分，共20分）

1．参考答案：在双向循环链表中p所指结点之后插入s所指结点的指针变化图示如下：

出语句序列如下： p->next->priou=s; s->next=p->next; s->priou=p; p->next=s;

2．参考答案：（只要考生正确写出其中任四步即给满分）本题用Kruskal算法构造出最小生成树共需五步，具每一步的变化情况如如：

34

3．参考答案：

4．参考答案：

5．参考答案：如下图所示：

五、算法题（共25分） 1．参考答案：Visit(T->data) QueueEmpty(Q) DlQueue(Q,p) 2．参考答案：p->next e q UNSUCCESS 3．（1）参考答案：求图中入度为零的顶点数。 （2）参考答案：图中入度为零的顶点数。 （3）参考答案：2

p->rchild 35