数据结构c语言版习题集答案全：某大学C语言期末复习题及答案-4

闲来无事，做做别人家的期末试题，没有答案，自己做的，可能有错，欢迎指正。

做这套题基本考百度，很多概念都忘了。

一个数据结构在计算机中表示(又称映像)称为____结构。

____是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。

在一般情况下,一个算法的时间复杂度是____的函数。

在 ____链表中,既可以通过设定一个头指针也可以通过设定一个尾指针来确定它,即通过头指针或尾指针可以访问到该链表中的每个结点。

在一个双向链表中指针p所指向结点之前插入一个新结点时,其时间复杂性的量级为____。

在单链表中,要删除某一指定的结点,必须找到该结点的____。

在一棵二叉树中,假定度为2的结点数为5个,度为1的结点数为6个,则叶子结点数为____个。

在含有N个结点的二叉链表中有____空链域。

遍历一含有n个结点的二叉树,时间复杂度为____。

具有300个结点的完全二叉树,叶子结点数____。

对初始序列(40,80,55,28,10,96,30,50,35,66)调整成小根堆,堆顶为____。

对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为____。

对序列(40,80,55,28,10,96,30,50,35,66)进行希尔排序,第一趟排序增量取5,则第一趟排序结果为____ (注意用空格隔开各数据即可)。

对序列(40,80,55,28,10,96,30,50,35,66)进行快排,则第一趟划分后40处于第____个元素位置。

对序列(40,80,55,28,10,96,30,50,35,66)进行快排,则第一趟划分结果____。(注意用空格隔开各数据即可)。

参考答案

1-5：CBCCA

6-10：BACBB

11-15：BABDD

16-20：CBBCB

21-25：CDCCB

26-30：CABCC

31-35：BCCDA

36-38：DCB

39：O((n^2)/2)(这题不会，猜的）

40：存储

41：数据元素

42：问题规模

43：循环

44：O(1)

45：前驱结点

46：6

47：n 1

48：O(n)

49：150

50：第1空 3 第2空 3

51：10

52：45

53：10 28 40 55 80 30 35 50 66 96（猜的，大概看了几眼希尔排序，没有全部理解）

54：5（猜的，大概开了下快速排序，没有全部理解）

55：35 30 10 28 40 96 55 50 80 66（猜的，大概开了下快速排序，没有全部理解）