2021年4月山西自考《数据结构》考前模拟试题和答案

时间：2020-12-29 15:04:17 作者：储老师

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

一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。
第1题设有两个串p和q，求q在p中首次出现的位置的运算称为()
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
【正确答案】 B

第2题将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用()方法能够最快地找出其中最大的正整数。
A. 快速排序
B. 插入排序
C. 选择排序
D. 归并排序
【正确答案】 C

第3题在下图中，从顶点V1出发，按广度优选遍历图的顶点序列是()
2021年4月山西自考《数据结构》考前模拟试题和答案

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

第4题设有一个无向图G＝(V，E)和G′＝(V′，E′)，如果G′是G的生成树，则下面不正确的说法是()
A. G′为G的子图
B. G′为G的连通分量
C. G′为G的极小连通子图且V′＝V
D. G′是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. Head↑.next＝NULL；
C. Head↑.next＝Head；
D. Head↑.next=Head↑
【正确答案】 B

第14题从一个包含2000个结点的散列表A［1..2000］中查找结点的平均比较次数()从一个包含200个结点的散列表B［1..200］中查找结点的平均比
较次数。
A. 大于
B. 小于
C. 等于
D. 不确定
【正确答案】 D

第15题深度为k的二叉树，所含叶子的个数最多为()

2021年4月山西自考《数据结构》考前模拟试题和答案

【正确答案】 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，并且最下面一层的结点都集中在该层最左边的若干位置上。
2021年4月山西自考《数据结构》考前模拟试题和答案

第2题请画出二叉树的五种基本形态。
【正确答案】二叉树有五种不同的基本形态： A：空二叉树 B：只有一个根结点的二叉树 C：右子树为空的二叉树 D：左子树为空的二叉树 E：左、右子树都非空的二叉树
2021年4月山西自考《数据结构》考前模拟试题和答案

第3题请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图（顶点vi表示）。
2021年4月山西自考《数据结构》考前模拟试题和答案

【正确答案】 A，B，C对应的图分别为：
2021年4月山西自考《数据结构》考前模拟试题和答案

第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->next=q->next;
free(q);
}
else error(″不存在第i个结点″)
}
【正确答案】 (p!=NULL)&&(p->next!=NULL) p->next

第3题以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在___上填充合适的语句。
pointer research-openhash(keytype K,openhash HP)
{ i=H(K);/*计算K的散列地址*/
p=HP［i］;/*i的同义词子表表头指针传给p*/
while(___)p=p->next;/*未达到表尾且未找到时，继续扫描*/
______;
}
【正确答案】 (p!=NULL)&&(p->key!=K) return(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*/

声明：

（一）由于考试政策等各方面情况的不断调整与变化，本网站所提供的考试信息仅供参考，请以权威部门公布的正式信息为准。

（二）本网站在文章内容来源出处标注为其他平台的稿件均为转载稿，免费转载出于非商业性学习目的，版权归原作者所有。如您对内容、版权等问题存在异议请与本站联系，我们会及时进行处理解决。