863 、数据结构与程序设计

10、判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ ）。

（A）单源最短路Dijkstra算法（B）所有顶点对最短路Floyd算法

（C）广度优先遍历算法（D）深度优先遍历算法

二、填空题（每小题2分，共20分）

1、数据的存储结构一般分为顺序存储、链式存储、 和四种方式。

2、中缀表达式 (A + B) * D + E / (F + A * D) + C对应的后缀表达式是。

3、KMP算法是解决模式匹配的有效算法，设数组下标从0从始，则模式串“babbabbab”对应的next[]值是。

4、一棵具有46个叶结点的完全二叉树，最多有个结点。

5、若p已指向了二叉树t的树根，则让p指向这棵二叉树的中序首点（中序遍历下的第一个结点）可以用以下的语句实现：。

6、编号为1，2，3，4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有种。

7、______排序方法采用的是二分法的思想，______排序方法其数据结构的组织采用的是完全二叉树结构。

8、若函数 int max（int a[]，int n）用于求长度为n（n>0）的整型组a中的最大值，其递归定义可以表示为：。

9、若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有_________个叶结点。

10、散列函数 以为自变量，函数值作为结点的。

三、程序填空与程序分析题（每小题6分，共24分）

1、函数frequency（）的功能统计字符串s中各个不同字符出现的频度，数组a记录s中不同的字符，数组c中记录每一种字符的出现次数，k返回不同字符的总数，请将程序补充完整。

voidfrequency(char s[],char a[],int c[],int *k)

{ int i,j,len=strlen(s);

if ( !len) /*原字符串为空*/

{ printf("Thestring is empty.\n ");*k = 0;

return;

}

else /*原字符串不为空*/

{ a[0] = s[0]; c[0] = 1; *k = 1; /*处理第一个字符*/

for( i = 1; i < len; i++ )

① /*数组c初始化*/

for( i = 1; i < len; i++ )

{ /*对s中剩余字符进行检测*/

j = 0;

while ( j < *k &&a[j] != s[i]) /*检查s[i]是否已在a[]中*/

②

if ( j == *k )/*s[i]不在a中*/

{a[*k]= ③

c[*k]= ④

(*k) = ⑤

}

else ⑥ /*s[i]已在a中*/

}

}

}

2、设带头结点的单链表的存储结构定义如下：

typedef char datatype;

typedef struct node{

datatypedata;

struct node* next;

} listnode;

typedef listnode* linklist;

函数deletelist（）的功能是将带头结点的单链表head中的重复结点删除（即data域相同的结点只保留第一个结点），请将程序补充完整。

linklist deletelist(linklist head)

{ linklist p,pre,s;

p=head->next;

while (p)

{pre=p;

s=p->next;

while (s!=NULL)

{while (s&&s->data!=p->data) /*从结点p后找与其相同的结点*/

{ ⑦

s=s->next;

}

if (s!=NULL)/*找到了与p相同的结点s*/

{ pre->next=s->next;

⑧

}

⑨

}

p=p->next;

}

return head;

}

3、二叉排序树链式存储结构定义如下：

typedef intdatatype;

typedefstruct node

{ datatype key;/*结点值*/

struct node *lchild,*rchild; /*左、右孩子指针*/

}bsnode;

typedefbsnode *bstree;

函数insertbstree（）的功能是在二叉排序树t中插入一个新结点x（若树中存在相同结点则不做插入操作），请将其补充完整。

voidinsertbstree(bstree *t,datatype x)

{ bstree f,p;

⑽

while (p) /*查找插入位置*/

{ if (x==p->key) ⑾ /* 若二叉排序树t中已有key，则无需插入*/

f=p;/* f用于保存新结点的最终插入位置 */

p=(x<p->key)? ⑿

}

p=(bstree) malloc(sizeof(bsnode)); /*生成待插入的新结点*/

p->key=x;

⒀

if (*t==NULL) ⒁ /*原树为空*/

else

if(x<f->key)

⒂

elsef->rchild=p;

}

4、阅读下面的递归程序，说明这个函数的功能是什么？如果数组的大小为n，则该程序的时间复杂度是多少？设数组a的初始值是21,30,52,35,69,70,90,61,78,99，则执行change1（a,0,9）后，数组a的内容是什么？

voidchange1(int a[],int low,int high)

{ inti,j,t;

i=low;j=high;

if (i<j)

{ while (i<j && a[i]%2!=0) i++;

while(i<j && a[j]%2==0) j--;

if (i!=j)

{t=a[i];

a[i]=a[j];

a[j]=t;

}

change1(a,i+1,j-1);

}

}

四、解答题（每小题10分，共40分）

1、一棵前序序列为1，2，3，4的二叉树，其中序序列可能是4，1，2，3吗？设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。

2、假定用于通信的电文仅由8个字母c1， c2， c3，c4， c5，c6， c7，c8组成， 各字母在电文中出现的频率分别为5， 25，3， 6，10， 11，36， 4。试构造哈夫曼树，并为这8个字母设计不等长Huffman编码。

3、 顺序表的快速排序为何采用由外向内来回比较法，是否可以从同一个方向扫描？采用带头结点的单链表存储的线性表是否可以做快速排序？对初始序列（50，20，79，24，49，84，3，99，12）以50作为“枢轴”进行第一次划分后的结果是什么？

4、 给定无向网如下图2所示，请采用prim算法用图示描述求解该图的最小生成树的过程。（初始入选点为A，每选取一条边画一个图）

五、算法与程序设计题（第1、2题每小题14分，第3小题18分，共46分）

答题要求：

①描述算法的基本设计思想；

②给出每个算法所需的数据结构定义；

③根据设计思想和实现步骤，采用用C语言写出对应的算法程序，关键之处请给出简要注释。

1、设一带头结点的单链表的头指针为head，链表的记录中包含着整数类型的info域，试采用直接插入法将此链表的记录按照info递增的次序进行就地排序。

2、二叉树采用二叉链表存储结构，t为其根结点，分别用递归与非递归方法编写函数，返回二叉树的前序尾点地址（前序遍历下的最后一个结点）。

3、AOV网采用带入度域的邻接表存储结构如图3所示。请用C语言定义这种结构，编写程序建立一个有向图的这种存储结构（出边表），并输出图中入度为0的顶点。