时间:2011-12-25 13:20:02
(2)若stackl的栈顶指针为topl,stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则：
栈stackl空的条件是：___________；
栈stack2空的条件是：___________；
栈stackl和栈stack2满的条件是：___________。
27.已知广义表如下：
A=(B,y)
B=(x，L)
L=(a，b)
要求：
(1)写出下列操作的结果
tail(A)=_______________.
head(B)=______________。
(2)请画出广义表A对应的图形表示。
28.已知二叉树如下：
请画出该二叉树对应的森林。
29.请回答下列问题：
(1)英文缩写DAG的中文含义是什么？
(2)请给出下面DAG图的全部拓扑排序。
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.已知线性表(a1,a2,a3...，an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为(x,x,-x,-x,x,x,-x)，变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容，使其成为完整的算法。
f30(int a［］，int n)
{ int k，m,temp；
m= (1) ；
while (a［m］<0 &&m<n)
m= (2) ；
k=m;
while (k<n)
{ while(a［k］>=0&&k<n)
k= (3) ；
if(k<n)
{ temp=a［k］；
a［k］=a［m］；
a［m］= (4) ；
m= (5) ；
}
}
}
(1)
(2)
(3)
(4)
(5)
31.阅读下列程序，并回答问题：
#include<stdio.h>
substr(char*t,char*s,int pos,int len)
{ while（len>0&&*s）
{ *t=*(s+pos-l);
t++;s++;len--;
}
*t=' ';
}
char *f31(char*s)
{ char t[100];
if (strlen(s)=1)
return s;
substr(t,s,1,1);
substr(s,s,2,strlen(s)-1);
f31(s);
return strcat(s,t);
}
main( )
{ char str[100]= ''String'';
printf(''%sn'',f31(str));
}
(1)请写出执行该程序后的输出结果；
(2)简述函数f31的功能。
32.下面程序实现插入排序算法。
typedef struct{
int key;
Info otherinfo;
}SeqList;
void InsertSort(SeqList R［］,int n)
{/* 待排序列保存在R［1..n］中*/
SeqList x；
int i，j，k，lo,hi,mi;
for (i=2；i<=n；i++)
{
(1) ；
lo=1；
hi=i-l;
while (lo<=hi)
{
mi=(lo+hi)/2;
if ( (2) ) break;
if (R［mi］.key>x.key) hi=mi-l;
else lo=mi+l;
}
if (mi=lo) k=i - mi;
else k=i - mi-1;
for (j=0；j<k；j++)
(3) ；
R［i-j］=x；
}
}
在空白处填写适当的内容，使该程序功能完整。
(1)
(2)
(3)
33.设有单链表类型定义如下：
typedef struct node {
int data;
struct node *next;
} *LinkList;
阅读下列算法，并回答问题：
void f33(LinkList head, int A, int B)
{
LinkList p=NULL;
While (head !=NULL)
{
if (head->data>A&&head->data<B)
p=head;
head=head->next;
}
if (p !=NULL)
printf("%dn",p->data);
}
(1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果；
(2)简述算法f33的功能。
五、算法设计题（本题10分）
34.已知二叉树的定义如下：
typedef struct node{
int data;
struct node *lchild, *rchild;
}*Bitptr；
编写递归算法求二叉树的高度。函数原型为：int f34（Bitptr t）；
全国2010年1月高等教育自学考试
数据结构试题
课程代码：02331
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，