福建师范大学数据结构08级期末试题

Question

如题所述

Answer 1

《数据结构》期末考试试卷（ A ）

一、 选择题（每小题2分，共24分）
1．计算机识别、存储和加工处理的对象被统称为( A )
A.数据 B.数据元素
C.数据结构 D.数据类型
2．栈和队列都是（ A ）
A．限制存取位置的线性结构 B．顺序存储的线性结构
C．链式存储的线性结构 D．限制存取位置的非线性结构
3．链栈与顺序栈相比，比较明显的优点是( D )
A.插入操作更加方便 B.删除操作更加方便
C.不会出现下溢的情况 D.不会出现上溢的情况
4．采用两类不同存储结构的字符串可分别简称为( B )
A.主串和子串 B.顺序串和链串
C.目标串和模式串 D.变量串和常量串
5． 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：B
A. 110 B .108
C. 100 D. 120
6．串是一种特殊的线性表，其特殊性体现在：B
A.可以顺序存储 B .数据元素是一个字符
C. 可以链接存储 D. 数据元素可以是多个字符
7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： C
A. 2h B .2h-1
C. 2h+1 D. h+1
软件开发网 www.mscto.com
8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ A
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
9．一个有n个顶点的无向图最多有多少边？C
A. n B .n(n-1)
C. n(n-1)/2 D. 2n
10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?C
A. 1/2 B .1
C. 2 D. 4
11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）
A．左子树的叶子结点 B．左子树的分支结点
C．右子树的叶子结点 D．右子树的分支结点
软件开发网 www.mscto.com
12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )
A.35和41 B.23和39
C.15和44 D.25和51
二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）
原理见课本128页

三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分)
深度优先；C0-C1-C3-C4-C5-C2
宽度优先：C0-C1-C2-C3-C4-C5
四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）
原理见课本250页

五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分）
0 1 2 3 4 5 6 7 8
12 23 45 66 76 88 93 103 166
过程：
mid=(0+8)/2=4
high=3,low=0 mid=1
high=0,low=0 mid=0（找到12）
high=8,low=5,mid=6（找到93）
high=8,low=7,mid=7
high=8 low=8 mid=8
算法：见课本84页上

六、知单链表的结点结构为
Data next
下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。
请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)
void SelectSort(LinkedList L)
{
LinkedList p,q,min;
DataType rcd;
p= (1) ;
while(p!=NULL) {
min=p;
q=p->next;
while(q!=NULL){
if( (2) )min=q;
q=q->next;
}
if( (3) ){
rcd=p->data;
p->data=min->data;
min->data=rcd;
}
(4) ;
}
}
本题不会。嘿嘿。。。。
七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分)
输入：
四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入
2：输出：算法产生至少一个量作为输出
3.：确定性：组成算法的每条指令是清晰的，无歧异的。
4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的

八、何谓队列的"假溢"现象？如何解决？（5分）
队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。

九、说明并比较文件的各种物理结构。（6分）

Answer 2

1.若已知a=1,b=2,则表达式！a<b的值是。
2.若有以下定义
double a[10]；
则a数组元素下标的上限为 ，下限为 。
1.以下程序的输出结果是 main()
{ int a=1, b=2; a=a+b; b=a-b; a=a-b; printf("%d,%d\n", a, b );
}
2.下列程序的输出结果是16.00，请填空。main()
3.下列程序段的输出结果是。 main()
4.下列程序段的输出结果是。 int n='c'; switch(n++)
5.以下程序的输出结果是。 main() , *p=arr; p++; printf("%d\n",*(p+3)); }
6.以下程序用来输出结构体变量ex所占存储单元的字节数，请填空。 struct st ; main()
7.以下程序运行后，显示：
main()
{ float a=365.7189;
int b=12,c;
c=(int)a+b;
printf(“c=%d\n”,c);
}
8.以下程序是用来输入5个整数，并存放在数组中，找出最大数与最小数所在的下标位置，并把二者对调，然后输出调整后的5个数。
#include <stdio.h>
main()
{ int a[5],t,i,maxi,mini;
for(i=0;i<5;i++)
scanf(“%d”,&a[i]);
mini=maxi=;
for(i=1;i<5;i++)
{
if() mini=i;
if(a[i]>a[maxi]) ;
}
printf(“最小数的位置是：％d\n”,mini);
printf(“最大数的位置是：％d\n”,maxi);
t=a[maxi];
;
a[mini]=t;
printf(“调整后的数为：”)；
for(i=0;i<5;i++)
printf(“%d”,a[i]);
printf(“\n”);
}
9. 计算1+1/2+1/4+…+1/50的值，并显示出来。
main()
{ int i=2;
float sum=1.0;
while(i<=)
{ sum+=1/;
i+=2;
}
printf(“sum=%f\n”,sum);
}

10.exchange函数的调用语句为exchange(&a,&b,&c)；。它将3个数按由大到小的顺序调整后依次放入a,b,c三个变量中，a中放最大值，请填空。
void swap(int *pt1,int *pt2)
{ int t;
t=*pt1;*pt1=*pt2;*pt2=t;
}
void exchange(int *q1,int *q2,int *q3)
{ if(*q3>*q2) swap();
if(*q1<*q3) swap();
if(*q1<*q2) swap();
}
11.表示条件：10<x<100或x<0的C语言表达式是