高等教育自学考试《数据结构》复习资料[2]

下列排序方法中排序所花费时间不受数据初始排列特性影响的算法是___________

A直接插入排序

B冒泡排序

C直接选择排序

D快速排序

下列排序方法中最好情况下时间复杂度为O（N）的算法是___________

A选择排序

B归并排序

C快速排序

D直接插入排序

二判断题（每小题分共分）

（ ）线性表的长度是线性表占用的存储空间的大小

（ ）双循环链表中任一结点的后继指针均指向其逻辑后继

（ ）队列只能采用链式存储方式

（ ）树（或森林）转化为对应的二叉树后两者的分支数相等

（ ）由二叉树的先序序列和中序序列能唯一确定一棵二叉树

（ ）图中一个顶点i的出度等于其邻接矩阵中第i列的非元个数

（ ）在用线性探查法解决沖突所构造的闭散列表中每组同义词中至少有一个元素的地址正好等于其散列地址

（ ）所谓沖突即是两个关键字的值相同的元素其散列地址相同

（ ）对n个元素的有序表用快速排序方法进行排序时间复杂是O（n）

（ ）存在有偶数个结点的满二叉树

三填空题（每空分共分）

在单链表中若要删除指针P所指结点的后继结点则需执行下列三条语句 U=P↑nextP↑next=U↑next___________

设有一个链队列结点结构为队尾指针为Ls（≠nil）则执行入队操作时 S↑next=Ls↑next______________________

单链表中指针P所指结点不为尾结点的条件是___________

设数组B[…………]中的任一元素均占个单元从首地址SA开始把数组B按行优先存储 则元素B[]的地址为___________

在有n（n>）个结点的二叉链表中非空链域的个数为___________

深度为（根的层次号为i）的完全二叉树至多有___________个结点

一个具有n个顶点的连通有向图至多有___________条边

一棵二叉排序树中若存在个结点其成功的查找长度≤则有___________个结点其成功的查找长度= 在对有个数据的有序表作二分查找时有___________个结点的查找长度是 在完全二叉树中编号为i的结点的左孩子结点的编号为___________

[] [] []