江苏开放大学数据结构与算法期末复习题三

数据结构期末复习题三

一、单选题

1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( C )。

A n

Bn/2

c(n+1)/2

D(n-1)/2

2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p 之间插入一个s所指的结点,则执行( D )。

As→link=p→link;p→link=s;

B p→link=s;s→link=q;

c p→link=s→link; s→link=p;

Dq →link=s; s→link =p;

3、栈的插入和删除操作在（ A )进行。

A栈顶

B栈底

C任意位置

D指定位置

4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( B )

A24

B71

c48

D53

二、填空题(每空1分，共32分)

1、数据的逻辑结构被分为（集合）（线性）（树）和（图）四种。

2、一种抽象数据类型包括（数据描述）和（操作声名）两个部分。

3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为（(38，56，25，60，42，74)）

4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为（HL→next =NULL）和（HL=HL→next）

5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的（前一个位置），该循环队列的最大长度为（n-1）

6、当堆栈采用顺序存储结构时，栈顶元素的值可用（S.stack [S.top]）表示;当堆栈采用链接存储结构时，栈顶元素的值可用（HS→data）表示。

7、一棵高度为5的二叉树中最少含有（5）个结点，最多含有（31）个结点;

8、在图的邻接表中，每个结点被称为（边结点），通常它包含三个域:一是（邻接点域）;二是（权域）;三是（链域）

9、在一个索引文件的索引表中，每个索引项包含对应记录的（索引值域）和（开始位置域）两项数据。

10、假定一棵树的广义表表示为A (B(C，D (E，F，G)，H (I，J)))，则树中所含的结点数为（10）个，树的深度为（3）,树的度为（3），结点H的双亲结点为（B）,孩子结点为（I和J）。

11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为（ ）,整个堆排序过程的时间复杂度为（ ）

12、在对m阶的B_树插入元素的过程中,每向一个结点插入一个索引项(叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于（m ）个，则必须把它分裂为（m – 1）个结点。

三、运算题

1、已知一组记录的排序码为(46，79，56，38，40，80,95，24)，写出对其进行快速排序的每一次划分结果。

1. 一个线性表为B= (12，23，45，57，20，03，78，31，15，36)，设散列表为HT[0..12]，散列函数为H(key) = key %13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

查找成功的平均查找长度:ASL succ=14/10=1.4

1. 已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。

此二叉树的后序遍历结果是:EDCBIHJGFA

4、已知一个图的顶点集V各边集G如下:

v={0，1，2，3，4，5，6，7，8，9};

E={ (0，1)，(0，4)，(1，2)，(1，7)，(2，8)，(3，4)，(3 ,8)，(5，6)，

(5，8)，(5，9)，(6，7)，(7，8)，(8，9) }

当它用邻接矩阵表示和邻接表表示时，分别写出从顶点Vo出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。

假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。

1. 算法填空，在画有横线的地方填写合适的内容对顺序存储的有序表进行二分查找的递归算法.

答：（low + high）/2；Binsch(A,low,mid -1,K)；Binsch(A.mid+1,high,K)；-1;

六、编写算法

编写算法，将一个结点类型为Lnode 的单链表按逆序链接，即若原单链表中存储元素的次序为 ，则逆序链接后变为, 。

Void contrary (Lnode*& HL)

 

AI创作