数据结构自考2016年10月真题及答案解析

已知单链表类型定义如下：

typedef struct node

 { int data;

    struct node *next;

}ListNode;

typedef ListNode * List_pt;

单链表L中结点数不少于2。设计算法判断L中存储的全部n个数据是否是斐波那契序列的前n项。如果是，则函数返回1，否则返回0。函数原型如下：

int IsF(List_ptr head);    //判定是否是斐波拉契序列

注：斐波拉契序列的定义为：f0=0，f1=，,fn=fn-1+fn-2 (n≥2)

阅读程序，回答下列问题。

int f33( NodeType R[], KeyType k, int n)

{      int i=n-1, count=1;

       R[0]. key =k;

       while(R[i]. key !=k)

      {     i--;

           count++;

}

 if(i-==0) return-1;

 else return count;

}

(1)变量 count的含义是什么?

(2)f33的功能是什么?

已知二叉树的二叉链表类型定义如下，阅读程序，并回答问题。

typedef char DataType;

typedef struct node

{       DataType data;      //data是数据域

       struct node *lchild, *rchild;     //分别指向左、右孩子结点

 }BinTNode;

 typedef BinTNode * BinTree;

 void f31( BinTree bt)

{       if (bt!=NULL)

    {       printf("%c", bt->data );

              f31(bt->lchild;

               printf("%c", bt->data );

     }

}

若二叉树如下所示，写出调用f31(T)的输出结果。

阅读下列程序，写出f32的输出结果。

void f32()

{ SeqStack *S;

     char x, y;

      Initstack(S);

      x= 'h';

       y= 't';

      Push(S, x);

      Push(S, 'c'):

      x= Pop(S);

      Push(S, x);

       Push(S, y);

      Push(S, 'a');

      Push( S, x )

     while( !StackEmpty(S))

 {    y= Pop(S);

     printf(”%c”,y);

}

      printf ("%c\n"'!');

}

设非空双向循环链表L的头指针为head，表结点类型为DLNode，定义如下。

typedef int DataType;

typedef struct dlode

{   DataType data;    //data是数据域

       struct dlnode * prior, *next;      // prior指向前趋结点,next指向后继结点

 }DLNode;

   typedef DLNode * DLinkList;

初始时，L中所有结点的prior域均为空(NULL)，next域和data域中已经正确赋值。如题30图a所示。

函数f30完成的功能是：将L中各结点的prior域正确赋值，使L成为双向循环链表。如题30图b所示。

将空白处应填写的内容答在答题卡上。

void f30( DLinkList head)

 {    DLNode *p;

       p=head;

       while(p->next!=____(1)____)

     { ____(2)____=p;

         p=p->next;

    }

      ____(3)____=p;

}

对于给定的一组关键字序列{26，18，60，65，45，13，32}，写出使用直接选择排序方法将其排成升序序列的过程。

现有5个权值分别是20、31、16、7和15的叶结点，用它们构造一棵哈夫曼树，画出该树。

对题27图所示的无向带权图G，回答下列问题。

(1)给出图G的邻接矩阵;

(2)给出图G的一棵最小生成树。

线性探查法和拉链法解决的是散列存储中的_______问题。

对题26图中所给的二叉排序树T回答下列问题。

(1)给出能生成r的2种关键字插入序列;

(2)给出r的前序遍历序列。

在有n个元素组成的顺序表上进行顺序查找。若查找每个元素的概率相等，则查找成功时平均查找长度是_______。

在无向图G的邻接矩阵A中，若A[i,j]=1，则A[j,i]=_______。

已知大根堆中的所有关键字均不相同，最大元素在难项，第2大元素可能存在的位置有2个，第3大元素可能存在的位置有_______个。

一棵二叉树中，度数为l的结点个数为n1，度数为2的结点个数为n2，则叶结点的个数为_______。

二叉树采用顺序存储方式保存，结点Z保存在数组A[7]中，若X有右孩子结点L则Y保存在_______中。

已知广义表LS=((a,b)，c，d)，head(LS)是_______。

设顺序表第1个元素的存储地址是1000，每个数据元素占6个地址单元，则第11个元素的存储地址是_______。

在一个单链表中，已知指针变量q所指结点不是表尾结点，若在q所指结点之后插入指针变量S所指结点，则正确的执行语句是_______。

两个栈S1和S2共用含100个元素的数组S[0一99]，为充分利用存储空间，若S2的栈底元素保存在S[99]中，则S1的栈底元素保存在_______中。

在一棵5阶B树中，每个非根结点中所含关键字的个数最少是(　　)

下列选项中，既能在顺序存储结构也能在链式存储结构上进行查找的方法是(　　)

对一组数据(2，12，16，88，5，10)进行排序，若前3趟排序结果如下：

第一趟：2，12，16，5，10，88

第二趟：2，12，5，10，16，88

第三趟：2，5，10，12，16，88

则采用的排序方法是(　　)

设有序表为{9，12，21，32，41，45，52}，当二分查找值为52的结点时，元素之间的比较次数是(　　)

己知有向图G如下所示，G的拓扑序列是(　　)

下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是(　　)

一个森林有m棵树，顶点总数为n，则森林中含有的总边数是(　　)

设图的邻接矩阵A如下所示。各顶点的度依次是(　　)

若对下列无向图进行深度优先遍历，得到的正确遍历序列是(　　)

一棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。树中包含的结点数是(　　)

如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序遍历序列是(　　)

设17个元素的顺序表中，若将第i(1≤i

已知广义表LS=(((a))，((b，(c))，(d，(e，f)))，0)，LS的长度是(　　)

若用一个大小为7的数组作为循环队列的存储结构，且当前rear和front的值分别为2和4，在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3个操作之前rear和front的值分别是(　　)

下列选项中，不属于线性结构特征的是(　　)