一、填空题
1、数据结构研究的三大方面内容包括 、 、 。
2、线性表由（a1,a2,…..,an）组成，a1称为头结点，an称为 结点，a3称为a2的直接 ，a2称为a3的直接 。
3、栈和队列是一种特殊的线性表，栈具有 的性质，队列具有 的性质。
4、树最适合用来表示具有 性和 性的数据。
5、数据的逻辑结构分为线性和 。
6、栈的操作原则是 队列的操作原则是 。
7、空串是 的性质，长度为 。
8、图的两种遍历方式是 和 。
二、选择题：
1、在表长为n的顺序表上做插入运算，平均移动的结点数为（ ）
A．n B．n/2 C．n/3 D．n/4
2、在表长为n的顺序表上做删除运算，平均移动的结点数为（ ）
A．n B．n/2 C．n/3 D．n/4
3、线性表采用链式存储时，结点的地址（ ）
A．必须是连续的 B．必须是不连续的
C．连续与否均可 D．必须有相等的间隔
4、线性表采用顺序存储时，结点的地址（ ）
A．必须是连续的 B．必须是不连续的
C．连续与否均可 D．必须有相等的间隔
5、循环队列是空队的条件是（ ）
A．Q->rear=Q->front B．(Q->rear+1)%maxsize=Q->front
C．Q->rear=0 D．Q->front=0
6、空串与空白串（ ）
A．相同 B．不相同 C．可能相同 D．不能确定
7、循环队列是队满的条件是（ ）
A．Q->rear=Q->front B．(Q->rear+1)%maxsize=Q->front
画出while语句的流程图C．Q->rear=0 D．Q->front=0
9、将一棵有含有50个结点的二叉树，度为0的结点的个数为5个，度为1的结点的个数是（）
A．4 B．50 C．41 D．40
10、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ）
A．99 B．98 C．48 D．50
11、哈夫曼树是访问叶结点的带权路径长度（ ）的二叉树。
A．最短 B．最长 C．可变 D．不定
12、若n个结点的无向图采用邻接矩阵存储方法，则该邻接矩阵是一个（ ）
A．一般矩阵 B．对称矩阵 C．对角矩阵 D．稀疏矩阵
13、在关键字序列{12,23,34,45,56,67,78,89,91}中二分查关键字为45、89和12的结点时，所需进行的比较次数分别为（ ）
A．４,４,３ B．４,３,３ C．３,４,４ D．３,３,４
14、以下排序方法中，不稳定的排序方法是（ ）
A．直接选择排序 B．二分法插入排序 C．归并排序 D．基数排序
15、直接插入排序在最好的情况下的时间复杂度是（ ）
A．O(n) B．O(logn) C．O(nlogn) D．O(n2)
16、在散列函数H（k）=k%m中，一般来讲m应取（ ）
A．奇数 B．偶数 C．素数 D．充分大的数
17、堆排序是一种（⑨ ）
A．插入 B．选择 C．交换 D．归并
三、应用题
1、分析下面程序段中划线语句的时间复杂度：
for(i=1;i<=n;i++)
{ k=i;
for(j=1;j<=n;j++)
if(a[j]>a[j+1]) k=j;
t=a[k];a[k]=a[i];a[i]=k;
2、指针变量指向的结点变量并未开辟空间，结点空间开辟需要执行的语句是什么？
3、数据元素进栈次序为1,2,3，进栈过程中允许出栈，请写出各种可能的出栈元素序列。
4、写出下图所示的二叉树的前序、中序、后序遍历的结点顺序
5、对于下图所示的无向图，试给出：该图的邻接矩阵。
6、已知字符集合{A,B,C,D,E}，给定权值为12,8,6,3,5，构造相应的哈夫曼树及给出A,B,C,D,E的哈夫曼编码。
7、已知一棵二叉树的先序遍历序列是EFHIGJK，中序遍历序列是HFIEJGK，试画出此二叉树。
8、已知散列函数为H（k）=k%13，关键字值序列为19，01,23,14,55,20,84,27,68,11,10,77，处理冲突的方法为线性探查法，散列表长度为13，试画出该散列表。
9、写出对关键字序列（40,24,80,39,43,18,20）进行冒泡排序的每一趟结果。
10、分析下面程序段中划线语句的时间复杂度：
int i=1;;
while(i<=n)
i=i*2;
11、结点释放空间需要执行的语句是什么？
12、对于下图所示的无向图，试给出：该图的邻接矩阵。
13、已知字符集合{A,B,C,D,E}，给定权值为4,22,3,8,5，构造相应的哈夫曼树及给出A,B,C,D,E的哈夫曼编码。
14、画出此二叉树对应的森林。
四、判断程序段的功能
1、
对于如上图所示的单链表结构执行：
p->next=q->next;
free(q);
的作用是什么？
2、下面函数的功能是什么？
void Push(SeqStack *s,DataType x)
{
if(StackFull(s))
printf( “stack overflow”);
S->top++;
S->data[S->top]=x;
}
3、下面函数的功能是什么？
DataType Pop(SeqStack *s,DataType x)
{
if(StackEmpty(s))
printf( “stack underflow”);
x=S->data[S->top];
S->top--;
return x;
}
五、算法设计题：
1、利用栈，将10进制数转换为二进制数（只限整数部分）
void conversion( )
{ init(s);
scanf (“%d”,&n);
while(n){ //余数进栈
push(&s,n%2);
n=n/2;
}
while(! Stackempty(s))
{ e=pop(&s); //余数出栈
printf(“%d”,e);
}
}
2、统计带头结点的单链表中结点的个数。
int count(node *L)
{ int x=0;
node *p;
p=L->next;
while(p)
{
x++;
p=p->next;
}
return x;
}
3、设计算法统计带头结点的单链表中，值为X的结点的个数。
int count(node *L，int x)
{ int flag=0;
node *p;
p=L->next;
while(p)
{
if(L->data==x) flag++;
p=p->next;
}
return flag;
}
4、设计一个算法，求顺序表中值为X的节点的个数。
int count(list *la,int x)
{
int i,flag=0;
if(la->len==0) {return 0;exit(1);}
for(i=0;i<la->len;i++)
{
if(la->data[i]==x) flag++;
}
return flag;
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论