《算法与数据结构》05级(计算机)-2期末考试A卷
- 格式：doc
- 大小：72.00 KB
- 文档页数：4
共8页 第1页
一、填空题（每小题2分，共16分）
1、查找有两种基本形式，分别是 查找和 查找。
2、对线性表进行二分查找时，要求线性表必须是 ，且要
求 。
3、 动态存储管理主要是解决系统如何 _______________、_____________ 的两大问题。
4、 对于内部排序，有多种排序方法。按排序基本思想（策略），可分为 、
、 、归并排序和基数排序。
5、索引表是存储记录的 和记录的 之间的对照表，每个元素
称为一个索引项。
6、排序的基本操作包括两方面，分别是 和 。
7、哈希函数是一种映象，是从 到 的一种映象。
8、对于文件，按物理结构划分，可分为顺序文件、 文件、 文
件和多关键字文件。
二、单项选择题（请将答案写在题目后的括号中。每题2分，共14分）
1、对于有n个顶点e(e>n)条边的带权无向图，以下关于该图的最小生成树的描述正确的
是（ ）。
（A）最小生成树是唯一的。
（B）最小生成树中所有边上的权值之和是唯一的。
（C）最小生成树有n条边。
（D）最小生成树有n个顶点e-1条边。
2、设有一个长度为n的线性表，当采用顺序查找方法时，每个元素的平均查找长度
是 ；而采用二分查找方法时，其平均查找长度是 。（ ）
（A） n/2 ,O(n) （B） (n+1)/2, O(n㏒2n)
（C） (n+1)/2, O(㏒2n) （D） n/2,O(㏒2n)
3、以下关于平衡因子(Balance Factor)的描述，正确的是（ ）。
（A） 二叉树上结点的左子树的深度减去其右子树深度。
（B） 二叉树上结点的右子树的深度减去其左子树深度。
（C） 二叉树上结点的左子树的结点数减去其右子树结点数。
（D） 二叉树上结点的右子树的结点数减去其左子树结点数。
4、 设哈希表长m=14，H（key）=key MOD 13，address(19)=6，address(41)=2，
address(57)=5，address(85)=7，其余地址为空。对于关键字31，若用线性探测法解决冲
突，其地址是 ；若用二次探测法解决冲突，其地址是 。（ ）
（A） 4，8 （B） 4，11 （C） 8，4 （D） 11，4
5、从未排序序列中挑选元素，并将其依次放入到已排序序列中(初始时为空)的一端的方
法是（ ）。
共8页 第2页
（A） 直接插入排序 （B） 选择排序
（C）快速排序 （D） 堆排序
6、用直接插入法对下列四个序列按非递减方式排序，元素比较次数最少的是（ ）。
（A） 21，32，46，40，80，69，90，94 （B） 94，32，40，90，80，46，21，69
（C） 32，40，21，46，69，94，90，80 （D） 90，69，80，46，21，32，94，40
7、 文件在外存上的上的组织方式称为文件的物理结构。基本的物理结构有：（ ）
(A) 顺序结构，链接结构，线性结构 (B) 线性结构，链接结构，索引结构
(C) 顺序结构，链接结构，索引结构 (D) 顺序结构，链接结构，线性结构
三、分析题（每题7分，共35分）
1、 对于下面的有向图，请给出对该图进行拓扑排序时的过程。
2、 将关键字序列（25，29，18，23，15，38，27，11，21）依次插入到初态为空的二叉
排序树中，请画出所得到的树T的过程；然后画出删除18之后的二叉排序树T1；最后再
画出插入18之后的二叉排序树T2。
3、 线性表的关键字集合{31，25，18，29，42，69，95，53，17，16，47，116，87}，
共有13个元素，已知散列函数为：H（k） = k MOD 11，采用链地址法处理冲突，请给出
对应的散列表结构。
4、 已知关键字序列{35，19，12，40，47，39，27，44，16，53}，请给出对该序列做非
递减排序的第一趟快速排序过程。
5、 已知关键字序列{15，29，12，40，47，39，58，27，73，44，86，55}，请给出采用
希尔排序法对该序列做非递减排序的过程（设增量序列是5，3，1）。
四、算法填空（每空2分，共20分）
请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。
1、设查找表ST是按关键字大小有序存放的，用折半查找法从表ST中查找关键字为key
的数据元素。顺序表的类型定义如下：
#define MAX_SIZE 100
typedef struct SSTable
{ RecType elem[MAX_SIZE] ; /* 顺序表 */
int length ; /* 实际元素个数 */
}SSTable ;
int Bin_Search(SSTable ST , KeyType key)
V0
V1
V2
V
3
V4
V5
V6
共8页 第3页
{ int Low=1，High=ST.length, Mid ;
while ( )
{ Mid=(Low+High)/2 ;
if (EQ(ST. elem[Mid].key, key)) return(Mid) ;
else if (LT(ST. elem[Mid].key, key)) Low=Mid+1 ;
else ;
}
return(0) ; /* 查找失败 */
}
2、查找散列表HT中的关键字K的记录，用开放定址法中的线性探测法解决冲突，类型
定义如下：
#define NULLKEY -1 /* 根据关键字类型定义空标识 */
typedef struct
{ KeyType key ; /* 关键字域 */
otherType otherinfo ; /* 记录的其它域 */
}RecType ;
int Hash_search(RecType HT[], KeyType k, int m)
{ int h, j ;
h=h(k) ; /* h(k)表示计算散列地址的哈希函数 */
while (j
else ;
}
return(-1) ;
}
以下两题是排序算法填空，所使用的待排序的记录类型的定义如下：
#define MAX_SIZE 100
typedef int KeyType ;
typedef struct RecType
{ KeyType key ; /* 关键字码 */
infoType otherinfo ; /* 其他域 */
}RecType ;
typedef struct Sqlist
{ RecType R[MAX_SIZE] ;
int length ;
}Sqlist ;
3、冒泡排序算法。
#define FALSE 0
共8页 第4页
#define TRUE 1
void Bubble_Sort(Sqlist *L)
{ int j ,k , flag ;
for (j=0; j
{ flag=TRUE ;
for (k=1; ; k++) /* 一趟排序 */
if (LT(L->R[k+1].key, L->R[k].key ) )
{ flag=FALSE ; L->R[0]=L->R[k] ;
L->R[k]=L->R[k+1] ;
;
}
if (flag==TRUE) ;
}
}
4、选择排序算法。
void simple_selection_sort(Sqlist *L)
{ int m, n , k;
for (m=1; ; m++)
{ k=m ;
for (n=m+1; n<=L->length; n++)
if ( LT(L->R[n].key, L->R[k].key) ) k=n ;
if ( ) /* 记录交换 */
{ L->R[0]=L->R[m]; L->R[m]=L->R[k];
;
}
}
}
五、编写算法（15分）
1、设查找表采用单链表存储，请写出对该表进行顺序查找的动态查找的算法。动态查找
的要求是：若链表中有关键字值为key的结点，则将该结点删除；否则，将其插入到链表
的最后。数据结构定义如下：（7分）
typedef struct Lnode
{ KeyType key ; /* 关键字码 */
infoType otherinfo ; /* 其他域 */
struct Lnode *next; /*指针域*/
}LNode; /*结点的类型 */
2、请写出直接插入排序的算法，然后对算法进行分析。（数据结构的定义见四题中的待排
序的记录类型的定义）（8分）
