全国自考（数据结构）模拟试卷3
一、1.单项选择题
0. 设有两个串p和q，求q在p中首次出现的位置的运算称为( )
A．连接
B．模式匹配
C．求子串
D．求串长
1. 对于shell排序来说，给定的一组排序数值为 49,38,65,97,13,27,49,55,04 则第二趟排序后的结果为( )
A．04,13,27,49,49,38,55,65,76,97
B．04,13,27,38,49,49,55,65,76,97
C．13,04,49,38,27,49,55,65,97,76
D．13,27,49,55,04,49,38,65,97,76
2. 将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用( )方法能够最快地找出其中最大的正整数。
A．快速排序
B．插入排序
C．选择排序
D．归并排序
3. 长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的ASL值是( )
A．13850
B．62/13
C．14580
D．49/13
4. 一个具有N个顶点的有向图最多有( )条边。
A．N(N-1)/2
B．N(N-1)
C．N(N+1)
D．N(N+1)/2
5. Aarr和Barr两个数组的说明如下： VAR Aarr:Array[O··7]of char; Barr:Array[-5··2,3,··8]of char; 这两个数组分别能存放的字符的最大个数是( )
A．7和35
B．1和5
C．8和48
D．1和6
6. 对于一棵具有三个结点的二叉树，共有( )种不同的树的形态。
A．4
B．5
C．6
D．7
7. 设一个数组中，行下标i的范围是从1到8，列下标的范围是从1到10，假设此数组的初始存储地址是A，则如果将此数组按照列优先的顺序连续存放，则元素Q[5][8]的起始地址是( )
A．1
B．23
C．24
D．529
8. 具有24个记录的序列，采用冒泡排序最少的比较次数是( )
A．1
B．23
C．24
D．529
9. 下列说法中正确的是( )
A．任何一棵二叉树中至少有一个结点的度为2
B．任何一棵二叉树中的每个结点的度为2
C．任何一棵二叉树中的度肯定等于2
D．任何一棵二叉树中的度可以小于2
10. 二分查找算法要求被查找的表是( )
A．键值有序的链表
B．键值不一定有序的链表
C．键值有序的顺序表
D．键值不一定有序的顺序表
11. 下面的程序在执行时，S语句共被执行了( )次。
i=1;
while(i＜=n)
{for(j=i;j＜n;j++)
{ S ;
}
i=i+1;
} 
12. 堆(Heap)是( )
A．完全二叉树
B．线性表
C．二叉排序树
D．平衡二叉树
13. 下面程序的时间复杂性是( ) for (i=1;i＜=n;i++) for(j=1;j＜=m;j++) {A[i][j]=i*j; }
A．O(m2)
B．O(n2)
C．O(m*n)
D．O(m+n)
14. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )
A．存储结构
B．存储实现
C．逻辑结构
D．运算实现
二、2.填空题
0. 对无向图，其邻接矩阵是一个关于______对称的矩阵。
1. 多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是______。
2. 18.已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
(1)在P结点之前插入S结点的语句序列是______；
(2)在表首插入S结点的语句序列是______。
a P—＞nex=S b P—＞next=P—＞next—＞next
c P—＞next=S—＞next d S—＞next=P—＞next
e S—＞next=L f Q=P
g while(P—＞next!=Q＞P=P—＞next
h while(P—＞next!=NULL)P=P—＞next
i P=L j L=S
3. 在散列技术中，处理冲突的方法有：______和______。
4. 如果我们定义一个长度为N的串空间，则它最多能放______个字符。
5. 假设在图G中任意的顶点设为vi，此顶点对应的度为D(vi)，此图的顶点数为n。则边数e和度数之间的关系为______。
6. ______的邻接矩阵不一定是不对称的。
7. 在串的匹配运算中，一般我们将主串称为______，而将子串称为______。
8. 当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有______。
9. N个顶点的连通图，至少有______条边。
三、3.解答题
0. 已知有一个关键字序列为(99,38,309,08,27,145,67,96,186,122,71,63,59)，假设用散列函数为h(key)=key%13，现在如果采用拉链法解决冲突问题，请画出这组关键字的散列表。
1. 已知有一关键字序列为{486,79,596,34,900,120,789,179,703,307)，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。
2. 写出二分查找的递归算法。
3. 已知连通图如下：
分别以邻接矩阵的邻接表实现存储，试给出该图的邻接矩阵和邻接表，若从顶点B出发对该图进行遍历，分别给出一个按深度优先搜索和广度优先搜索的顶点序列。
四、4.算法阅读题
0. 以下运算实现在链队上的入队列，请在______处用适当的语句予以填充。
void EnQueue(QueptrTp*lq,DataType x)
{ LqueueTp*P;
p=(LqueueTp*)malloc(sizeof(LqueueTp));
______=x;
p—＞next=NULL;
(1q—＞rear)—＞next=______;
______;
}
1. 以下运算实现在链栈上的初始化，请在______处用适当的语句予以填充。
void InitStack(LStackTp*ls){______;)
2. 以下算法在指针T所指的二叉排序树上的查找键值等于K的结点。成功时回送指向该结点的指针；否则回送空指针。请分析程序，并在______上填充合适的语句。
bitreptr search_bst(bitreptr T,keytype K)
{ if(T==NULL)return(NULL);
else switch
{ case T—＞key==K:______;
case______: return(search_bst(T—＞lchild,K));
case______: return(search_bst(T—＞rchild,K));
}
}
3. 以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。
void insert_sqlist(sqlist L,datatype x,int i)／*将X插人到顺序表L的第i-1个位置*／
{ if(L.1ast==maxsize)error("表满");
if((i＜1)||(i＞L.last+1))error("非法位置");
for(j=L.last;j≥i;j--)
L.data[i-]=X;
L.last=L.last+1;
}
五、5.算法设计题
0. 写出向某个有序文件中插入一个记录的程序。
