数据结构复习资料

数据结构复习资料 一、 填空题

1、广义表（a,（a,b）,d,e,（（i,j）,k））的长度是 5 ，深度是 3 。

2、如果某二叉树中有30个叶结点，另有30个结点仅有一个孩子结点，则该二叉树中共有 89 个结点。 3、设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域空的结点有 n+1 个。 4、顺序查找时，存储方式应是 顺序存储 ；折半查找时，要求线性表是 顺序存储且有序 ；分块查找时，要求线性表 顺序存储且块间有序 ；哈希查找时，要求线性表的存储方式是 哈希存储 。

二、 选择题

1、关于逻辑结构，以下说法错误的是（ B ）。

B、运算的定义与逻辑结构无关 2、线性表中正确的说法是（ D ）。

D、除了第一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和直接后继

3、若某线性表最常用的操作室存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A、顺序表

4、线性表（a1,a2,,an）以链式方式存储时，访问第i个元素的时间复杂度为（ C ）。 C、O(n)

5、非空的循环单链表head的尾结点p满足（ A ）。 A、p->link==head

6、若已知一个栈的入栈序列是1，2，3，……30，其输出序列是p1,p2,p3,……,pn，若p1=30，则p10为（ D ）。 D、21

7、设数组data[m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ D ）。

D、front = ( front + 1 ) % m

8、串“ababaabab”的next数组值为（ C ）。 C、0，1，1，2，3，4，2，3，4 9、若串S=“software”，其中串的数目是（ C ）。 C、36

10、在简单模式匹配中，当模式串位j与主串位i的比较时，新一趟匹配开始，主串的位移公式是（ D ）。

D、i = i – j + 2

11、对（ C ）进行相应的遍历仍需要栈的支持。

C、后序线索树

12、下面的叙述中，不正确的是（ B ）。

B、任何一个关键活动前提完成，将使整个工期提前完成 13、采用分块查找时，数据的组织方式为（ B ）。

B、把数据分成若干块，块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引表 14、对数据序列（10，9，15，20，5，7，18，6，12，8），若用堆排序的筛选方法建立的初始堆是（A）；若用快速排序法，用第一个元素与其他元素比较，排序一趟后的结果是（D）；冒泡排序一趟后的结果是（F）；初始增量为5的希尔排序一趟后的结果是（E）

A、5，6，7，10，8，15，18，20，12，9 D、8，9，6，7，5，10，18，20，12，15 F、9，10，15，5，7，18，6，12，8，20 E、7，9，6，12，5，10，18，15，20，8 15、在下列排序算法中，占用辅助空间最多的是（ A ）。 A、归并排序

三、 判断题

1、数据的逻辑结构式指数据的各数据项之间的逻辑关系。（ 错误 ） 2、链表中的头结点仅起到标识作用。（ 错误 ） 3、静态链表中地址相邻的元素具有前驱后继关系。（ 错误 ） 4、任何一个递归过程都可以转换为非递归过程。（ 正确 ） 5、空串与空格串是相同的。（ 错误 ）

6、有一个以上结点的二叉树，已知先序和后序遍历序列，能唯一确定一棵二叉树。（ 错误 ） 7、树的先根遍历算法可以理解为深度优先遍历算法的一种特殊形式。（ 正确 ）

8、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（ 正确 ） 9、哈希函数越复杂，随机性越好，冲突的概率越小。（ 错误 ） 10、堆栈序是一种稳定的排序算法。（ 错误 ）