自考模拟题：2020年8月自考《数据结构》考前试题和答案

经历了这么长时间的复习，相信大家的书本知识已经可以融会贯通，历年真题也已经做的差不多了，那么现在就需要多做些模拟题来巩固知识点以及进行查漏补缺。福建自考网小编整理了2020年8月自考《数据结构》模拟试卷，希望对大家有所帮助。

自考《数据结构》模拟题和答案02331

一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。
第1题 设有两个串p和q，求q在p中首次出现的位置的运算称为()
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
【正确答案】 B  
 
第2题 将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用()方法能够最快地找出其中最大的正整数。
A. 快速排序
B. 插入排序
C. 选择排序
D. 归并排序
【正确答案】 C      

第3题 在下图中，从顶点V1出发，按广度优选遍历图的顶点序列是()

A. V1V5V3V4V2V6V7
B. V1V5V3V4V2V7V6
C. V1V7V2V6V4V5V3
D. V1V2V4V7V6V5V3
【正确答案】 A      

第4题 设有一个无向图G＝(V，E)和Gprime;＝(Vprime;，Eprime;)，如果Gprime;是G的生成树，则下面不正确的说法是()
A. Gprime;为G的子图
B. Gprime;为G的连通分量
C. Gprime;为G的极小连通子图且Vprime;＝V
D. Gprime;是G的一个无环子图
【正确答案】 B    

第5题 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用()存储结构。
A. 二叉链表
B. 广义表
C. 三叉链表
D. 顺序
【正确答案】 C  
 
第6题 深度为6(根的层次为1)的二叉树至多有()个结点。
A. 31
B. 32
C. 63
D. 64
【正确答案】 B  
 
第7题 已知一个单链表中有3000个结点，每个结点存放一个整数，()可用于解决这3000个整数的排序问题且不需要对算法作大的变动。
A. 直接插入排序方法
B. 简单选择排序方法
C. 快速排序方法
D. 堆排序方法
【正确答案】 D      

第8题 二维数组M［i,j］的元素是4个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到4，列下标j的范围从0到5。M按行存储时元素M［3，5］的起始地址与M按列存储时元素()的起始地址相同。
A. M［2，4］
B. M［3，4］
C. M［3，5］
D. M［4，4］
【正确答案】 B      

第9题 在一个具有n个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以top作为栈顶指针，则作退栈操作时，top的变化是()
A. top=top-1
B. top=top+1
C. top不变
D. top不确定
【正确答案】 B      

第10题 对广义表((a),(b))进行下面的操作head(head((a),(b)))后的结果是()
A. a
B. (a)
C. ()
D. 不确定
【正确答案】 A      

第11题 判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用()
A. 求关键路径的方法
B. 求最短路径的Dijkstra方法
C. 广度优先遍历方法
D. 深度优先遍历方法
【正确答案】 D      

第12题 链栈与顺序栈相比，有一个比较明显的优点即（）
A. 插入操作更加方便
B. 通常不会出现栈满的情况
C. 不会出现栈空的情况
D. 删除操作更加方便
【正确答案】 B  
 
第13题 带头结点的单链表Head为空的判定条件是()
A. Head＝NULL；
B. Headuarr;.next＝NULL；
C. Headuarr;.next＝Head；
D. Headuarr;.next=Headuarr;
【正确答案】 B      

第14题 从一个包含2000个结点的散列表A［1..2000］中查找结点的平均比较次数()从一个包含200个结点的散列表B［1..200］中查找结点的平均比
较次数。
A. 大于
B. 小于
C. 等于
D. 不确定
【正确答案】 D  
 
第15题 深度为k的二叉树，所含叶子的个数最多为()

【正确答案】 C

二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填写上正确答案。错填、不填均无分。
第1题 一个字符串相等的充要条件是___和___。
【正确答案】 两个字符串的长度相等 对应位置的字符相等  
 
第2题 在散列技术中，处理冲突的方法有：___和___。
【正确答案】 开放定址法 拉链法      

第3题 当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有___。
【正确答案】 右子树  
 
第4题 在二叉排序树中，其左子树中任何一个结点的关键字一定___其右子树的各结点的关键字。
【正确答案】 小于  
 
第5题 一般来说，数组中的元素具有___的数据类型，并且数组元素的下标的上界和下界都是___的。
【正确答案】 统一 固定  
 
第6题 一个n*n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为___。
【正确答案】 n*(n+1)/2  
 
第7题 在一个按行优先顺序存储的二维数组(M*N)中，假设数组的基地址是P，并且数组的每一个元素所占的存储空间为d个字节，则aij的地址计算公式为___。
【正确答案】 LOC(aij)=P+［i*N+j］*d      

第8题 计算机软件系统中，有两种处理字符串长度的方法：一种是采用___，第二种是___。
【正确答案】 固定长度 设置长度指针  
 
第9题 在单链表中，除了首元结点外，任一结点的存储位置是由___指示。
【正确答案】 其直接前趋结点的链域的值      

第10题 在___遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
【正确答案】 先序  

三、解答题（本大题共4小题，每小题5分，共20分）
第1题 已知一棵二叉树的前序遍历序列是ABDGCEFH，其中序遍历序列为DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?
【正 确答案】 根据二叉树的遍历规则，前序遍历总是先访问根结点，然后依次遍历其左右子树，而中序遍历规则是先遍历左子树，再访问根结点，然后访问右子树，则由以上规 则，我们极易得出此二叉树的根结点是A，中序遍历序列中，根结点左右两边的结果分别属于其左、右子树，所以得出左子树包含3个节点：B，D，G，右子树包 含四个结点C，E，F，H。在左子树中，先序遍历序B位于最前，而中序遍历序列中，B位于最后，则可以得出结点B无右子树，只有左子树，又在B的子树中， 无论先序遍历还是中序遍历，D都位于G的前面，则G只能是D的右孩子，且D无左孩子，按照以上分析规则，我们同样可以分析出此二叉树的右子树的结构。从而 我们得到了此二叉树的最终结构为：此二叉树的后序遍历序列为：GDBEHFCA 从求出的二叉树的形状我们可以看出此二叉树不是完全二叉树，完全二叉树的性质是：一棵完全二叉树只有最下面的两层的结点数可以小于2，并且最下面一层的结 点都集中在该层最左边的若干位置上。  

 
第2题 请画出二叉树的五种基本形态。
【正确答案】 二叉树有五种不同的基本形态： A：空二叉树 B：只有一个根结点的二叉树 C：右子树为空的二叉树 D：左子树为空的二叉树 E：左、右子树都非空的二叉树  
 

第3题 请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图（顶点vi表示）。


【正确答案】 A，B，C对应的图分别为：  

 
第4题 已知有一关键字序列为{505，94，512，61，908，170，897，275，653，463}，如果我们采用快速法对此序列进行排序(按照升序排序)，请给出每一趟排序的结果。
【正确答案】 快速排序采用分治法进行，其基本思想如下：将原问题分解成为若干个规模更小但结构和原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解的组合为原问题的解，根据上述思想，我们可以得到如下快速排序的各趟结果如下：
初始：505，94，512，61，908，170，897，275，653，463
第1趟：［463，94，275，61，170］505［897，908，653，512］
第2趟：［170，94，275，61］463，505［897，908，653，512］
第3趟：［61，94］170［275］463，505［897，908，653，512］
第4趟：61［94］170［275］463，505［897，908，653，512］
第5趟：61，94，170，［275］，463，505［897，908，653，512］
第6趟：61，94，170，275，463，505［897，908，653，512］
第7趟：61，94，170，275，463，505［512，653］897［908］
第8趟：61，94，170，275，463，505，512［653］897［908］
第9趟：61，94，170，275，463，505，512，653，897［908］
第10趟：61，94，170，275，463，505，512，653，897，908  

四、算法阅读题（本大题共4小题，每小题5分，共20分）
第1题 求下面算法中变量count的值：(假设n为2的乘幂，并且n<2)
int Time
{int n
count=0;x=2;
while(x
{x*=2;count++;
}
return(count)
}
【正确答案】 count=log2n  
 
第2题 以下为单链表的删除运算，分析算法，请在___处填上正确的语句。
void delete-lklist(lklist head,int i)
{ p=find-lklist(head,i-1);
if(___)
{ q=___;
p- free(q);
}
else error(Prime;不存在第i个结点Prime;)
}
【正确答案】 (p!=NULL)(p-  
第3题 以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在___上填充合适的语句。
pointer research-openhash(keytype K,openhash HP)
{ i=H(K);/*计算K的散列地址*/
p=HP［i］;/*i的同义词子表表头指针传给p*/
while(___)p=p- ______;
}
【正确答案】 (p!=NULL)(p-  
第4题 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置，请在___处用适当的语句予以填充。
Trans-Sparmat(SpMatrixTp a,SpMatrixTp *b)
{(*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu
if(a.tu)
{q=1;
for(col=1;___;col++)
for(p=1;p<=a.tu;p++)
if(___)==col)
{(*b).data［q］.i=a.data［p］.j;
(*b).data［q］.j=a.data［p］.i;
(*b).data［q］.v=a.data［p］.v;
___;
}
}
}
【正确答案】 col<=a.nu a.data［p］.j q++  
五、算法设计题（本题10分）
第1题 设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。
【正确答案】 可通过设置一个标志位进行区分的方式来进行交替扫描，算法描述如下： Alterbubblesort(r)/*交替扫描法起泡排序*/ Rectype R\[ \]; {int i,j,temp,flag;/*设置扫描标志flag*/ flag=True; i=0; while(flag)/*开始扫描*/ { flag=False; for (j=n-i,jR\[j+1\].key) {flag=True; temp=R\[j\]; R\[j\]=R\[j+1\]; R\[j-1\]=temp; } } i++;/*往右扫描*/ } }/*Alterbubblesort*/  

以上就是&“自考模拟题：2020年8月自考《数据结构》考前试题和答案”的所有内容，希望能帮到大家。想要获取更多自考免费真题库和模拟题库可以收藏福建自考网，免费领取。