您的位置:自考365 > 复习指导 > 笔记串讲 > 工学 > 高等教育自学考试《数据结构》复习资料

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

2006-12-25 14:58   【 】【我要纠错

  一、单项选择(每空2分,共20分)

  1、若某线性表中最常用的操作是在最后一个元素之前插入和删除元素,则采用___________最节省运算时间。

  A、单链表

  B、仅有头指针的单循环链表

  C、仅有尾指针的单循环链表

  D、双链表

  2、哈夫曼树的带权路径长度WPL等于___________.

  A、除根以外的所有结点的权植之和

  B、所有结点权值之和

  C、各叶子结点的带权路径长度之和

  D、根结点的值

  3、设输入序列为1,2,3,4,5,借助一个栈不可能得到的输出序列是___________.

  A、1,2,3,4,5

  B、1,4,3,2,5

  C、4,1,3,2,5

  D、1,3,2,5,4

  4、对于下面二叉树,按后序遍历所得的结点序列为___________.

  

  A、1234567

  B、1245367

  C、4251637

  D、4526731

  5、栈和队列都是___________.

  A、顺序存储的线性结构

  B、链式存储的线性结构

  C、限制存储点的线性结构

  D、限制存储点的非线性结构

  6、已知完全二叉树有30个结点,则整个二叉树有___________个度为1的结点。

  A、0

  B、1

  C、2

  D、不确定

  7、对下图,不能得到的拓扑序列是___________.

  

  A、1,2,3,4,5,6,7,8

  B、1,5,2,6,3,7,4,8

  C、1,2,5,6,3,4,7,8

  D、1,2,3,4,8,7,6,5

  8、下列排序算法中,第一趟排序完毕后,其最大或最小元一定在其最终位置上的算法是___________.

  A、归并排序

  B、直接选择排序

  C、快速排序

  D、基数排序

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

  A、直接插入排序

  B、冒泡排序

  C、直接选择排序

  D、快速排序

  10、下列排序方法中,最好情况下,时间复杂度为O(N)的算法是___________.

  A、选择排序

  B、归并排序

  C、快速排序

  D、直接插入排序

  二、判断题(每小题1分,共10分)

  ( )1、线性表的长度是线性表占用的存储空间的大小。

  ( )2、双循环链表中,任一结点的后继指针均指向其逻辑后继。

  ( )3、队列只能采用链式存储方式。

  ( )4、树(或森林)转化为对应的二叉树后,两者的分支数相等。

  ( )5、由二叉树的先序序列和中序序列能唯一确定一棵二叉树。

  ( )6、图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数。

  ( )7、在用线性探查法解决冲突所构造的闭散列表中,每组同义词中至少有一个元素的地址正好等于其散列地址。

  ( )8、所谓冲突即是两个关键字的值相同的元素,其散列地址相同。

  ( )9、对n个元素的有序表用快速排序方法进行排序,时间复杂是O(n2)。

  ( )10、存在有偶数个结点的满二叉树。

  三、填空题(每空2分,共20分)

  1、在单链表中,若要删除指针P所指结点的后继结点,则需执行下列三条语句: U:=P↑。next;P↑。next:=U↑。next;___________.

  2、设有一个链队列,结点结构为:队尾指针为Ls(≠nil),则执行入队操作时, S↑。next:=Ls↑。next;___________;___________.

  

  3、单链表中指针P所指结点不为尾结点的条件是___________. 4、设数组B[1……4,1……5]中的任一元素均占3个单元,从首地址SA开始把数组B按行优先存储, 则元素B[3,4]的地址为___________. 5、在有n(n>0)个结点的二叉链表中,非空链域的个数为___________. 6、深度为6(根的层次号为i)的完全二叉树至多有___________个结点。

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

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

  四、解答下列各题(共30分)

  1、 以数据集{3,4,5,8,12,18,20,30}为叶子结点的权值,(1)构造一棵哈夫曼树 (4分)

  (2)计算其带权路径长度(2分)。

  2、已知二叉树的先序、中序和后序序列分别如下,但其中有一些已模糊不清,构造出该二叉树(6分)

  先序序列 _BC_EF__中序序列 BDE_AG_H后序序列 _DC_GH_A

  3、如图所示

  

  (1)写出邻接矩阵(2分)

  (2)求出其最小生成树(4分)

  4、设散列函数H(X)=K MOD 7,若输入序列为 {100,90,120,60,78,35,42,31,15,20,22,12,16,27},求:(1)构造出开散列表。

  (2)求出在等概率查找情况下查找成功的平均查找长度。

  5、有一个数据序列:25,50,70,100,43,7,12.现采用堆排序算法进行排序,写出每趟的结果。

  五、算法设计题:(共20分)

  1、设计一个用带头结点的单链表表示的直接插入排序算法,各结点结构如图:

  要求:用类PASCAL语言写出算法(10分)

  

  2、设二叉树采用二叉链表表示,各结点结构为:其中data为整数型字段。设计算法判别一棵二叉树是否是二叉排序树。(10分)

  

本文转载链接:高等教育自学考试《数据结构》复习资料

分享到:
  • 站内搜索
  • 课程搜索
  • 试题搜索

热门搜索:教材 报名 查分 免考 考试计划