数据结构,专科
一、简答题（
1、假设一个有向图的顶点集合V={c1,c2,c3,c4,c5},弧集
S={
(1)试根据上述关系，画出该有向图；（2）该图有环吗？若无
环，则写出它的一个拓扑有序序列；若有环，请写出组成环的顶点序列。
答：
2、已知某二叉树的先序序列为{ ABHFDECKG }，中序序列为
{ HBDFAEKCG }, 画出该二叉树。
答：二叉树是
a
/ \
b e
/ \ \
h f c
/ / \
d k g
后序是hdfbkgcea
3、已知关键字序列{70，83，100，65，10，9，7，32}，现对其
从小到大排序，写出快速排序每一趟结束时的关键字状态。
答#include
int main()
{
int i,j,t;
int a[7]={70，83，100，65，10，32，7，9};
for(j=0;j<6;j++)//进行6次循环
for(i=0;i<6-j;i++)// 每次实现6-j次循环
if(a[i]>a[i+])
{ t=a[i];
a[i]=a[i+1];
a[i+1]=t;
}//每次a[i]与a[i+1]比较，大的就调换两者位置
for(i=0;i<7;i++)
printf("%d ",a[i]);
}
譬如第一次结果就是70，83，100，65，10，32，7，9
70比83小，所以位置没变。。
4、设s="I AM A WORKER"，t=" GOOD"，q=" WORKER"。求：
StrLength(s)，StrLength(t) ，SubString(s,8,6) ，
Index(s,q,1) 。
答：strlength(s)=14；strlength(t)=4；substr(s,8,6)=worker；substr(s,q,1)=o;
5、在单链表中设置头结点有什么作用？
答：头结点就是在单链表的开始结点之前附加的一个结点，设置头结点的优点有两个：（1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上一样，无须进行其他特殊处理；（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就一样了。
6、设哈希函数H(key)=key MOD 13,用线性探测再散列法解决
冲突。对关键字序列{ 55，19，01，68，23，27，20，84 }
在地址空间为0-10的散列区中建哈希表，画出此表，并求等
概率情况下查找成功时的平均查找长度。
答：
二、编程题
1、设顺序表va中的数据元素递增有序。设计算法，将x插入到
顺序表的适当位置上，并仍保持该表的有序性。
答：．status insert_Sq(SqList *va,ElemType x)
{
int i;
if( va->length==va->listsize) exit OVERFLOW;
for( i=va->length-1;i>=0 && va->elem[i]>x;--i)
va->elem[i+1]= va->elem[i];
va->elem[i+1]=x; va->length++;
return OK;
}
2、编写递归算法, 按先序顺序输出二叉链表存储的二叉树中所
有度为2的结点。
答：int nodes(BiTree T)
{
if(!T) return 0;
return nodes(T->lchild)+nodes(T->rchild)+1; }
3、 若希望循环队列中的元素都能利用，需设一个标志域tag,并以tag 的值为0或1来区分头、
尾指针相同时队列的状态是“空”还是“满”。试编写与此结构相应的入队列的算法。
1.假设一个有向图的顶点集合V={c1,c2,c3,c4,c5},弧集S={
（2）写出该图从 c1出发的一个深度优先遍历序列。
答：1）邻接矩阵： ?????????
??????
?????00
1
10001000000000100
000100000010
（2）可能的拓扑序列为：15234 （注意4一定是最后一个，2一定在1和5后） （3）12345 （4）52431
2 .已知一组权值分别是3、12、7、4、2、8、11，画出叶子分别对应这些权值的Huffman树，并求其带权路径长度。
答：已知下列字符ABCDEFG的权值分别为3，12，7，4，2，8，11，是设计哈夫曼编码
A B C D E F G
先后结合的结点：
(2,3),(5,4),(7,8),(9,11),(15,12),(20,27),如图：
编码：
A:0001
B:11
3.设关键字集合为{10，2，14，8，12，13}，用堆排序方法对其从小到大排序，写出堆排序的初态、建堆和排序过程中重建堆的过程。答：
堆排序初态: {10，2，14，8，12，13}
建堆:{14 12 13 8 2 10}
输出14之后再建堆：{13 12 10 8 2 14}
输出13之后再建堆：{12 8 10 2 13 14}
输出12之后再建堆：{10 8 2 12 13 14}
输出10之后再建堆：{8 2 10 12 13 14}
输出8之后再建堆：{2 8 10 12 13 14}有序
4.设s="I AM A WORKER"，t=" GOOD"，q=" WORKER"。求：StrLength(s)，StrLength(t) ，SubString(s,8,6) ，Index(s,q,1) 。
答;
StrLength是字符串长度,SubString（s,8,7）是截取s,第8个开始,截取7个字符
答：：StrLength(s)=13
StrLength(t)=4
SubString(s,8,6)=student
Index(s,q,1)=3
5.描述以下3个关于单链表的术语的区别：头指针、头结点、首元结点。
答：头结点：是为了方便操作链表而附设的,头结点数据域通常用来保存跟链表有关的信息,比如链表的长度；
首元结点：就是链表里“正式”的第一个结点,即链表的开始结点。形如a1,a2,a3,...an；
头指针：头指针是指向链表的基地址。如果链表存在头结点则头指针就是指向头结点的地址,反之指向首元结点的地址。
6.设散列函数H(key)=key MOD 11,用线性探测再散列法解决冲突。对关键字序列{ 13，28，72，5，16，18，7，11，24 }在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。
答：ASL=(1+1+1+2+5+1+1+4)/8=16/8=2
二、编程题（每题10分，共30分）
1.设计算法，实现单链表的就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an ,an-1,…,a1）。
答：void reverse(LinkList L)
{/*带头结点*/
LinkList p;
p=L->next; L->next=NULL;
for(; p; p=p->next){
q=p->next;
p->next=L->next;
L->next=p;
}
}
2.编写递归算法，求二叉链表表示的二叉树T的叶子结点个数。答：int leafNum(bnode* root)
{
static int num=0;
if(!root->left&&!root->right)
num++;
if(root->left)
leafNum(root->left);
if(root->right)
leafNum(root->right);
return num;
}
4.假设将循环队列定义为：以整型域变量front和length分别指示循环队列中队头元素位置和队列中元素个数，指针elem指示存放队列
元素的连续空间的首地址，写出相应的入队列的算法。答：算法：
#define MAXQSIZE 100
typedef struct {
ElemType *elem;
int front;
int length;
}CycQueue;
status EnQueue(CycQueue *Q, ElemType e)
{
if (Q->length==MAXQSIZE) return ERROR;
Q->elem[(Q->front+Q->length) % MAXQSIZE]=e;
Q->length++;
return OK;
}
status DeQueue(CycQueue *Q, ElemType *e)
{
if (Q->length==0) return ERROR;
*e= Q->elem[Q->front];
Q->length - -;
return OK;
}