文档库

最新最全的文档下载
当前位置:文档库 > 数据结构练习题

数据结构练习题

《数据结构(C语言版)》练习题

一.选择题(共15题,每题2分,共30分)

1.算法分析的两个主要方面是(A)。

A. 空间复杂度和时间复杂度

B. 正确性和简单性

C. 可读性和文档性

D. 数据复杂性和程序复杂性

2. 计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、(B )等5个特性。

A. 可执行性、可移植性和可扩充性

B. 可执行性、有穷性和确定性

C. 确定性、有穷性和稳定性

D. 易读性、稳定性和确定性

3. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算法的时间复杂度( C )。

A. O(log2n)

B.O(1)

C. O(n)

D.O(n2)

4. 线性表L=(a1,a2,……,an),下列说法正确的是(D )。

A. 每个元素都有一个直接前驱和一个直接后继

B. 线性表中至少要有一个元素

C. 表中诸元素的排列顺序必须是由小到大或由大到小

D. 除第一个和最后一个元素外,其余每个元素都由一个且仅有一个直接前驱和直接后继

5. 判断一个循环队列Q(最多n个元素)为满的条件是(C )。

A. Q->rear==Q->front

B. Q->rear==Q->front+1

C. Q->front==(Q->rear+1)%n

D. Q->front==(Q->rear-1)%n

6. 一个顺序栈S,其栈顶指针为top,则将元素e入栈的操作是(A )。

A. *S->top=e;S->top++;

B. S->top++;*S->top=e;

C. *S->top=e

D. S->top=e;

7. 广义表(a,b,c)的表尾是(B )。

A. b,c

B. (b,c)

C. c

D. (c)

8. 稀疏矩阵一般的压缩存储方法有两种,即(C )。

A. 二维数组和三维数组

B. 三元组和散列

C. 三元组和十字链表

D. 散列和十字链表

9. 在一棵具有5层的满二叉树中结点总数为(A)。

A. 31

B. 32

C. 33

D. 16

10. 用顺序存储的方法,将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..n]中,若结点R[i]有左孩子,则其左孩子是(C )。

A. R[2i-1]

B. R[2i+1]

C. R[2i]

D. R[2/i]

11. 对于具有n个顶点的图,若采用邻接矩阵表示,则该矩阵的大小为(B )。

A. n

B. n2

C. n-1

D. (n-1)2

12. 设G1=(V1,E1)和G2=(V2,E2)为两个图,如果V1?V2,E1?E2则称(A )。

A. G1是G2的子图

B. G2是G1的子图

C. G1是G2的连通分量

D. G2是G1的连通分量

13. 已知一个有序表为(11,22,33,44,55,66,77,88,99),则折半查找55需要比较( A )次。

A. 1

B. 2

C. 3

D. 4

14. 解决哈希冲突的主要方法有( D )。

A. 数字分析法、除余法、平方取中法

B. 数字分析法、除余法、线性探测法

C. 数字分析法、线性探测法、再哈希法

D. 线性探测法、再哈希法、链地址法

15. 在任何情况下,时间复杂度均为O(nlogn)的不稳定的排序方法是(C )。

A.直接插入

B. 快速排序

C. 堆排序

D. 归并排序

二.填空题(共10题,每题2分,共20分)

1数据结构按逻辑结构可分为两大类,它们分别是和。

2.设单链表的结点结构为(data,next)。已知指针p指向单链表中的结点,q指向新结点,欲将q插入到p结点之后,则需要执行的语句:。

3.一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear,则循环队列中元素的个数为:。

4. 两个串相等的充分必要条件是两个串的长度相等且。

5. 已知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]的地址是

6. 广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是:。

7. 具有n个结点的完全二叉树的深度是

8. 在一棵二叉树中,度为0的结点的个数是n0,度为2的结点的个数为n2,则有n0=

9. 判定一个有向图是否存在回路,可以利用。

10. 在散列存储中,装填因子α的值越大,则存取元素时发生冲突的可能性就越;α值越小,则存取元素发生冲突的可能性就越。

三.简答题(共6题,每题5分,共20分)

1.函数GetElem实现返回单链表的第i个元素,请在空格处将算法补充完整。

int GetElem(LinkList L,int i,Elemtype *e){

LinkList p;int j;

p=L->next;j=1;

while(p&&j

(1) ;++j;

}

if(!p||j>i) return ERROR;

*e= (2) ;

return OK;

}

2.已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg,写出该二叉树的后序序列

并画出该二叉树。

3.假设用于通信的电报仅由8个字母构成,字母在电文中出现的频率分别为0.07、0.19、

0.02、0.06、0.32、0.03、0.21和0.10. (1)构造出相应的哈夫曼树;(2)写出这个8个

字母设计哈夫曼编码((3)计算该哈夫曼树的加权路径长度

4.下图为一无向图,请:(1)给出该无向图存储结构的邻接链表表示(邻接顶点请以顶

点序号递增排序,以使答案唯一);(2)写出对其分别进行深度优先遍历的结果(从顶点1开始)。

1

234

5678

9

四.程序题(共2题,每题10分,共20分)

1.已知头指针分别为la和lb 的带头结点的单链表中,结点按元素值非递减有序排列。写

出将la 和 lb两链表归并成一个结点按元素值非递减有序排列的单链表(其头指针为 lc)。

2.输入50个学生的记录(每个学生的记录包括学号和成绩),组成记录数组,然后按成绩

由高到低的次序输出(每行10个记录)。排序方法采用选择排序。

《数据结构(C语言版)》练习题答案

一选择题:1-5:ABCDC 6-10:ABCAC 11-15:BAADC

二填空题:

1.线性结构和非线性结构

2.答案:q->next=p->next p->next=q

3.答案:(rear-front+M)%M

4.对应位置字符相同

5.Loc(A[0][0])+(i*N+j)*k

6.(x,y,z)

7.?log2n?+1

8.n2+1

9.拓扑排序

10.大,小

三判断题:

四简答题

1 答案:(1)p=p->next (2)p->data

2.

a

b

d e

c

f

h

g

后序序列为:debhfgca

3.

28

56

23

1117

710

32

60

1921

40

100

1

1

1

1

1

1

1

(2)

数据结构练习题

(3)加权路径长度为2.61

数据结构练习题

(2)深度优先的遍历序列为:125967384

五程序题:

1.

LinkedList Union(LinkedList la, lb)

{ pa=la->next;pb=hb->next;

lc=(LinkedList )malloc(sizeof(LNode));

pc=lc;∥pc是结果链表中当前结点的前驱

while(pa&&pb)

if(pa->datadata)

{pc->next=pa;pc=pa;pa=pa->next;}

else {pc->next=pb;pc=pb;pb=pb->next;}

if(pa)pc->next=pa; else pc->next=pb;

free(la);free(lb);∥释放原来两链表的头结点。

}∥算法Union结束。

2.typedef struct

{ int num; float score; }RecType;

void SelectSort(RecType R[51],int n)

{ for(i=1; i

{ //选择第i大的记录,并交换到位

k=i; //假定第i个元素的关键字最大

for(j=i+1;j<=n;j++) //找最大元素的下标

if(R[j].score>R[k].score) k=j;

if(i!=k) R[i] <-->R[k]; //与第i个记录交换

}//for

for(i=1; i<=n; i++) //输出成绩

{ printf("%d,%f",R[i].num,R[i].score); if(i%10==0) printf("\n");} }//SelectSort