30、奇文共欣赏，疑义相如析——陶渊明
《数据结构》模拟试卷1
一、 单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内
错选或未选均无分
1. 线性表定义为 ( )
A. 一个无限序列，可以为空 B. 一个无限序列，不能为空
C. 一个有限序列，可以为空 D. 一个有限序列，不能为空
2. 以二叉链表作为二叉树的存贮结构时，在具有n个结点的二叉链表中(n>0)，空指针域的个数为 ( )
A．2n-1 B. n+1 C. n-1 D. 2n+1
3. 若一个序列的进栈顺序为1,2,3,4, 那么不可能的出栈序列是 ( )
A. 4,2,3,1 B. 3,2,1,4 C. 4,3,2,1 D. 1,2,3,4
4. 具有65个结点的完全二叉树其深度为（根的层次号为1） ( )
A. 8 B. 7 C. 6. D. 5
5. 下列排序算法中, 排序在每趟结束后不一定能选出一个元素放到其排好的最终位置上的算法是 ( )
A. 选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序
6. 设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为 ( )
A. O(nlog2e) B. O(elog2n) C. O(en) D. O(n+e)
7. 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用的查找方法是 ( )
A.顺序 B. 分块 C. 折半 D. 其它
8. 链表不具有的特点是 ( )
A. 所需空间与线笥表成正比 B. 不必事先估计存储空间
C. 插入删除时不需移动元素 D. 随机访问
9. 设有两个子串S和T, 求T在S中首次出现的位置的运算称为 ( )
A. 连接 B. 求子串 C. 模式匹配 D. 求串长
10.设有98个元素,采用二分法查找时,最大比较次数是 ( )
A. 49 B. 15 C. 20. D. 7
11.如果以链表作为栈的存储结构,则出栈操作时 ( )
A. 必须判别栈是否为空 B. 判别栈元素的类型
C. 必须判别栈是否为满 D. 对栈不必作任何判别
12.下列存储表示中,哪一个不是树的存储形式 ( )
A.双亲表示法 B. 孩子链表表示法
C. 顺序存储表示法 D. 孩子兄弟表示法
13.对n个记录的文件进行堆排序，最坏情况下的执行时间为 ( )
A. O(log2n) B. O(nlog2n) C. O(n) D. O(n2)
14.一个记录的关键字为（46，79，56，38，42，88），采用快速排序以第一个记录为基准得到的第一次划分结果为 ( )
A.(38,42,46,56,79,88)
B.(42,38,46,79,56,88)
C.(42,38,46,56,79,88) D.(42,38,46,56,79,88)
15.设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为 ( )
A. O(nlog2e) B. O(ne) C. O(en) D. O(n+e)
二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）不写解答过程，将正确的答案写在每小题的空格内
错填或不填均无分
1.在一个算法中，一条语句重复执行的次数称为______
2．数据结构的三个要素是数据的逻辑结构、 (1) 和 (2)
3．在单链表中，指针p所指结点为最后一个结点的条件是
4．带头结点的单链表中，除头结点外，任一结点的存储位置（地址）是在
5．多个值相同的元素只分配一个存储空间，零元素不分配空间，称为
6．已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，则后序遍历序列为
7．如要将序列{52,18,25,70,96,72,75}建成小根堆，则只需把18与 相互交换
8．利用直接选择排序算法对n个记录进行排序，在最坏情况下，记录交换的次数为
9．由二叉树的 (1) 序列或 (2) 序列可以唯一确定一棵二叉树
10．文件的基本操作主要是指 (1) 和 (2)
三、解答题（本大题共4小题，每小题5分，共20分）
1． 已知一组关键字为{25,7,32,98,93,17,49,93,27}
对以上关键字进行冒泡排序，写出每一次排序结果的排列次序（5分）
2． 设有一组关键码{68,31,120,49,98,53}需插入到表长为12的散列表中
(1) 设计一个适当的散列函数；（2分）
(2)用设计的散列函数将上述关键码插入散列表
画出建好的散列表结构（假定用线性探测法解决冲突）；（3分）
3. 已知序列{7,8,5,12,4,7},给出二叉排序树的构造过程
（5分）
4. 分别按前序、中序、后序遍历下图所示的二叉树，给出相应的结点序列（5分）
四、算法阅读题（本大题共4小题，每小题5分，共20分）
1．下列算法是对一个用链表表示的文件进行直接选择排序，请填入合适的内容，使其成为一个完整的算法
void SelectSort(LinkList head)
{ //链表结构的直接选择排序（降序）
ListNode * p=head；//p为未排序的第一个结点指针
while(p!=NULL) {
m=p; //m为当前最大值时遍历未排序表的指针
pos=p; //pos 为当前最大值结点指针
while(m->next!=NULL) {
if( (1) )
{ q=m; pos=m->next;} //q为pos的前趋
(2) ；
}
if(pos!=p) {
(3) ;
if(p==head)
(4) ;
else
(5) ;
s=pos;
}
else { s=p; p=p->next; } //s为p的前趋
}
}
2. 用顺序存储结构实现将两个有序表合并成一个有序表，合并后的结果不另设新表存储，写出算法的空缺部分
说明：A,B为整型有序表，合并后的结果仍放在A中
void merge(SeqList * A, SeqList B);
{ int n ,m ;
n=A->length; m=B.length;//A,B表的长度分别赋给n,m
while(m>0) {
if(n==0 || A->data[n-1]< B.data[m-1])
{ A->data[n+m-1]=B.data[m-1];
(1) ;
}
else { (2) ; n=n-1; }
}
(3) ;
}
3.下列算法求出指定结点*p在二叉排序树中所在的层次，请填上适当的内容，使之成为完整的算法
int SearchLevel(BSTree T, BSTNode * p)
{ int level=0;
if(T==NULL)
return(0);
else {
leavl=level+1;
while( (1) ) {
if(T->data< p->data) T=T->rchild;
else (2) ;
(3) ;
}
}
return level;
}
4. 设不带头结点单链表的结点是按关键字从小到大排列的，试对下面链表的查找算法填空，使之成为完整的算法
void search(LinkList head, DataType x)
{//有序链表上的查找，查找成功返回结点指针，否则返回NULL
ListNode * p=head;
while( (1) && p->data < x)
(2) ;
if( (3) )
return p;
else
return NULL;
}
五、算法设计题（本题共10分）
试编写算法将一个带头结点单循环链表A分解为两个具有相同结构的链表B、C，其中，B表中结点是A表中值为奇数的结点，而C表中结点是A表中值为偶数的结点(要求利用原表结点空间)
??
??
??
??
第1页
30、奇文共欣赏，疑义相如析——陶渊明