06-09数据结构真题及答案(4)

【解析】在二叉链表中每个结点有两个指针域，而除了根结点外，每个结点均需要占用其中一个指针域，所以空的指针域个数为：2*n-(n-1)=n+1个 。 9. 【答案】C

【解析】在等概率的情况下，每个元素的查找概率都是1/n，其中查找最后一个元素需要比较1次，查找第n-1个结点需要比较2次，依次类推，查找第1个结点需要比较n次，平均查找长度为：（1+2+3+?）/n=(n+1)/2。 10. 【答案】A

【解析】对含有n个元素的线性表，执行选择排序时，无论序列的初始排列如何，均需要进行n-1趟排序，每次都需要n-i次比较，确定出第i个位置上的元素来，所以答案选A。而插入排序、冒泡排序当元素已经有序时，比较次数可以降低为n-1次；快速排序当元素排列基本有序时，性能反而降低。

二、填空题（本大题共10小题，每小题1分，共10分） 1. 【答案】f==r

【解析】在循环队列中，分别用f指示队头，r指向队尾。所以当f==r时，表示队列中没有元素存在，通常当(r+1)%maxsize==f时，表示该循环队列已满。（以牺牲一个存储空间伟代价）。在此注意是“＝＝”，而不是“＝”。 2．【答案】1/2

【解析】假设在长度为n的顺序表中插入元素时，插入位置有n+1个，平均需要移动元素数量为（0＋1＋2?+n）/(n+1)=n/2；当删除元素时，删除位置有n个，平均需要移动的元素个数为：（0＋1＋2＋?+(n-1)）/n=(n-1)/2。都接近1/2的元素个数。 3. 【答案】38

【解析】二位数组每行中有5个元素，每个元素占2个字节，因此LOC（3,2）=LOC(0,0)+(3*4+2)*2=38 4. 【答案】2 -1

【解析】二叉树的基本性质２。 5．【答案】e

【解析】有向图的邻接表是以图中所有顶点作为头结点，将所有以该顶点为弧尾的弧生成表结点构成的。所以，表结点数与弧数是一一对应的。 6.【答案】中序

【解析】二叉排序树中所有左子树中结点均比根结点的值小，所以右子树中结点值均比根结点的值大，如果左右子树不空，左右子树都满足该特性，所以二叉排序树的中序遍历顺序是由小到大的顺序排列的。 7．【答案】2

【解析】无论在有向图还是在无向图中，每条边或弧在计算顶点的度时均被用过２次，所以，得到的顶点的度的和就是边数的２倍。 8.【答案】3

【解析】该有序表中包含７个元素，因此先与第４个元素进行比较，然后和第２个元素进行比较，最后和第３个元素进行比较，所以共需要比较３次成功。

K

16

9．【答案】9

【解析】根据哈希函数求得函数值为５，查找发现冲突，根据二次探测再散列，分别将函数值+1、-1、+2、-2?，并对表长进行取余，进行试探。所以答案填9。 10. 【答案】n(n-1)/2

【解析】在有n个顶点的无向完全图中，从每个顶点出去的边有n-1条边，但每条边被用过2次，所以总边数为n(n-1)/2。

三、判断题（本大题共5小题，每小题1分，共5分） 1．【答案】×

【解析】算法的特性包含确定性。确定性就是指每条指令必须是确定的含义，不能产生二义性，并且，在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得出相同的输出。 2．【答案】×

【解析】线性表的链式存储结构的存储单元地址不要求连续，但是可以连续；而线性表的顺序存储结构一定要求分配连续的存储单元。 3．【答案】√

【解析】队列属于特殊的线性表，要求在表的一端进行插入，在表的另一端进程删除，能够插入的一端称为队尾，能够删除的一端称为对头。 4．【答案】×

【解析】内部排序指的是待排记录存放在计算机随机存储器中进行的排序过程，外部排序指的是待排记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。拓扑排序不属于内部排序。 5．【答案】√

【解析】一棵树转化为二叉树，其根结点一定没有右孩子，即该二叉树没有右子树。只有2棵及以上的非空树组成的森林转化为二叉树，才能使得对应二叉树有右子树。 四、综合应用题（本大题共3小题，每小题5分，共15分）

1．答：具有三个结点的二叉树共有5种基本形态，具体如下图所示：

２

２

２

２

?0?1?2．答： ?1??1??0V2

1110?0001??0000?如图为该图的邻接矩阵。从V1出发的深度优先遍历顺序为

?0001?1010??V1→V4→V5→V2→V3或V1→V2→V5→V4→V3或V1→V3→V2→V5→V4或V1→V3→V4→V5→

17

3．答：树转换为二叉树为：其中该二叉树的先序遍历顺序为A，B，C，E，F，G，D

ABCEFDG

五、算法设计（本大题共１小题，共10分） 答：Linklist delete(Linklist &L,Elemtype x) { Linklist p,q;

q=L; p=L->next; //初始化p指向第一个结点，q始终指向p结点的前驱； while(p!=NULL)

{ if(p->data==x) //找到符合条件的结点； {q->next=p->next; free(p);

p=q->next; //删除该结点，并修改p指针； } else {q=p;

p=p->next; //先使q后移，p向后移动。 } } }

18

06C语言程序设计（50分）

六、单选题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填写在题干后面的括号内。每小题1分，共15分）

1.C语言程序的基本单位是（ ）

A.程序行 B.语句 C.函数 D.字符 2.可用作C语言用户标识符的一组字符串是（ ）

A.void define WORD B.a3_b3 _123 IF C.For –abc Case D.2a DO sizeof 3.设int a=12，则执行完语句a+=a-=a*a后，a的值是（ ） A.552 B.264 C.144 D.-264 4.以下叙述正确的是（ ）

A.do-while语句构成的循环不能用其它语句构成的循环来代替。 B. do-while语句构成的循环只能用break语句退出。

C.用do-while语句构成的循环，在while后的表达式为非零时结束循环。 D.用do-while语句构成的循环，在while后的表达式为零时结束循环。 5.设有说明int（*ptr）[10]其中的标识符ptr是（ ） A.10个执行整型变量的指针 B.指向10个整型变量函数指针

C.一个指向具有10个整型元素的一维数组的指针

D.具有10个指针元素的一维指针数组，每个元素都只能指向整型量 6.有以下程序段 typedef struct NODE{

int num;

struct NODE *next; }OLD;

则以下叙述中正确的是（ ）

A.以上的说明形式非法 B.NODE是一个结构体类型 C.OLD是一个结构体类型 D.OLD是一个结构体变量 7.以下不能正确计算代数式值的C语言表达式是（ ） A.1/3*sin(1/2)*sin(1/2) B.sin(0.5)*sin(0.5)/3 C.pow(sin(0.5),2)/3 D.1/3.0*pow(sin(1.0/2),2) 8.C语言规定，程序中各函数之间（ ） A.既允许直接递归调用也允许间接递归调用 B.不允许直接递归调用也不允许间接递归调用 C.允许直接递归调用不允许间接递归调用 D.不允许直接递归调用允许间接递归调用

9.在宏定义#define PI 3.14159中，用宏名PI代替一个（ ） A.单精度数 B.双精度数 C.常量 D.字符串

19

10.在C语言中，要求运算数必须是整型的运算符是（ ） A.% B./ C.< D.!

11.为表示关系x≥y≥z，应使用的C语言表达式是（ ） A.(x>=y)&&(y>=z) B.(x>=y)AND(y>=z) C.(x>=y>=z) D.(x>=y)&(y>=z) 12.有以下程序段

int k=0,a=3,b=4,c=5;k=a>c?c:k; 执行该程序段后，k的值是（ ） A.3 B.2 C.1 D.0

13.若定义char *s=\，则指针s所指字符串的长度为（A.19 B.15 C.18 D.说明不合法 14.下述对C语言字符数组的描述中错误的是（ ） A.字符数组可以存放字符串

B.字符数组中的字符串可以整体输入、输出

C.可以在赋值语句中通过赋值运算符对字符数组整体赋值 D.不可以用关系运算符对字符数组中的字符串进行比较 15.设有如下的函数 exam(float x){ printf(\

}

则函数的类型为（ ）

A.与参数x的类型相同 B.是void C.是int D.无法确定

七、阅读下列程序，写出其运行结果（每小题5分，共25分）1、程序： main() { int i,j,x; for(i=1;i<=4;i++)

{for(j=1;j<=4-i;j++) printf(\

for(j=0;j<=2*i+1;j++) printf(\ printf(\

} } 答案： 2、程序： main() { int k=3,n=0;

20

）

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库06-09数据结构真题及答案(4)在线全文阅读。