全国2005年10月高教自考《数据结构》试题

　　三、解答题(本大题共4小题，每小题5分，共20分)

　　26. 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。
　　(1)写出队满的条件表达式；
　　(2)写出队空的条件表达式；
　　(3)设m=40,rear=13,quelen=19,求队头元素的位置；
　　(4)写出一般情况下队头元素位置的表达式。
　　(1)
　　(2)
　　(3)
　　(4)
　　27. 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。
　　28. 画出下图所示有向图的所有强连通分量。

　　29. 对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。
　　(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；
　　(2)对所举序列进行快速排序，写出排序过程。
　　(1)
　　(2)
　　四、算法阅读题(本大题共4小题，每小题5分，共20分)
　　30. 阅读下列算法，并回答问题：
　　(1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L；
　　(2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L；
　　(3)简述算法的功能。
　　void f30(SeqList*L, DataType x)
　　{
　　int i =0, j;
　　while (ilength && x>L->data［i］)i++;
　　if(ilength && x==L->data［i］)

　　　{
　　for(j=i+1;jlength;j++)
　　L->data［j-1］=L->data［j］;
　　L->length--;
　　　}

　　 else

　　　　 {
　　for(j=L->length;j>i;j--)
　　L->data［j］=L->data［j-1］;
　　L->data［i］=x;
　　L->length++;
　　　　　}
　　}
　　(1)
　　(2)
　　(3)
　　31. 已知图的邻接表表示的形式说明如下：
　　#define MaxNum 50 //图的最大顶点数
　　typedef struct node {
　　int adjvex; //邻接点域
　　struct node *next; //链指针域
　　} EdgeNode; //边表结点结构描述
　　typedef struct {
　　char vertex; //顶点域
　　EdgeNode *firstedge; //边表头指针
　　} VertexNode; //顶点表结点结构描述
　　typedef struct {
　　VertexNode adjlist［MaxNum］; //邻接表
　　int n, e; //图中当前的顶点数和边数
　　} ALGraph; //邻接表结构描述
　
　　下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。
　　typedef enum {FALSE, TRUE} Boolean;
　　Boolean visited［MaxNum］;
　　void DFSForest(ALGraph *G){
　　int i;
　　for(i=0;in;i++)
　　visited［i］=___________________(1);
　　for(i=0;in;i++) if (!visited［i］) DFSTree(G,i);
　　}
　　void DFSTree(ALGraph *G, int i) {
　　EdgeNode *p;
　　visited［i］=TRUE;
　　p=G->adjlist［i］. firstedge;
　　while(p!=NULL){
　　if(!visited［p->adjvex］){
　　printf(″<%c,%c>″,G->adjlist［i］. vertex,
　　G->adjlist［p->adjvex］.
　　vertex);
　　_______________(2);
　　}
　　_______________(3);
　　　}
　　}
　　(1)
　　(2)
　　(3)
　　32. 阅读下列算法，并回答问题：
　　(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L；
　　(2)写出上述函数调用过程中进行元素交换操作的总次数。
　　void f32(int R［］,int n){
　　int i,t;
　　for (i=0;i　　while (R［i］!=i){
　　t=R［R［i］］;
　　R［R［i］］=R［i］;
　　R［i］=t;
　　}
　　}
　　(1)
　　(2)
　　33. 已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为：
。请在空缺处填入适当内容，使其成为一个完整算法。
　　void f33 (LinkList L, LinkList H［］, int m)
　　{//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在
　　int i,j;
　　LinkList p,q;
　　for (i=0;i　　H［i］=_____________(1);
　　p=L->next;
　　while(p)
　　{
　　q=p->next;
　　j=p->key%m;
　　_________________(2);
　　H［j］=p;
　　_________________(3);
　　}
　　free(L);
　　}
　　(1)
　　(2)
　　(3)
　　五、算法设计题(本大题10分)
　　34. 假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示 　　typedef char DataType;
　　typedef struct node {
　　DataType data;
　　struct node *lchild, *rchild; //左右孩子指针
　　struct node *parent; //指向双亲的指针
　　} BinTNode;
　　typedef BinTNode *BinTree;
　　若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。
　　(1)就后继的不同情况，简要叙述实现求后继操作的方法；
　　(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。