《10月自考英语（二）模拟试题及答案.doc》由会员分享，可在线阅读，更多相关《10月自考英语（二）模拟试题及答案.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本资料由湖南自考网收集整理，更多自考资料请登录 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。第第 1 1 页页(共共 6 6 页页)全国全国 20092009 年年 1 1 月高等教育自学考试月高等教育自学考试数据结构试题数据结构试题课程代码：课程代码：0233102331一、单项选择题一、单项选择题(本大题共本大题共 1515 小题，每小题小题，每小题 2 2 分，共分，共 3030 分分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、在每小题列出的四个备选项中只有一个是符合
2、题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分多选或未选均无分。1.下列程序段的时间复杂度为()s=0；for(i=1；in；i+)for(j=1；jnext=NULL；C.head!=NULL；D.head-next=head；3.栈是一种操作受限的线性结构，其操作的主要特征是()A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组 An存放循环队列的元素，其头、尾指针分别为 front 和 rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为()A.(rear-front-1)nB.(rear-front
3、)nC.(front-rear+1)nD.(rear-front+n)n5.判断两个串大小的基本准则是()A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小6.二维数组 A45按行优先顺序存储，若每个元素占 2 个存储单元，且第一个元素 A00的存储地址为1000，则数组元素 A32的存储地址为()A.1012B.1017C.1034D.10367.高度为 5 的完全二叉树中含有的结点数至少为()A.16B.17C.31D.328.已知在一棵度为 3 的树中，度为 2 的结点数为 4，度为 3 的结点数为 3，则该树中的叶子结点数为()A.5B
4、.8C.11D.189.下列所示各图中是中序线索化二叉树的是()10.已知含 6 个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点 v0出发进行深度优先遍历可能得到的顶点访问序列为()A.(v0，v1，v2，v5，v4，v3)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v5，v2，v3，v4)D.(v0，v1，v4，v5，v2，v3)11.如图所示有向图的一个拓扑序列是()A.ABCDEF本资料由湖南自考网收集整理，更多自考资料请登录 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。再长的路，一步步也能走完，再短的路，不迈开双脚也无
5、法到达。第第 2 2 页页(共共 6 6 页页)B.FCBEADC.FEDCBAD.DAEBCF12.下列关键字序列中，构成大根堆的是()A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，313.对长度为 15 的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为()A.1539B.1549C.1551D.155514.已知一个散列表如图所示，其散列函数为 H(key)=key11，采用二次探查法处理冲突，则下一个插入的关键字 49 的地址为()15.数据库
6、文件是由大量带有结构的()A.记录组成的集合B.字符组成的集合C.数据项组成的集合D.数据结构组成的集合二、填空题二、填空题(本大题共本大题共 1010 小题，每小题小题，每小题 2 2 分，共分，共 2020 分分)请在每小题的空格中填上正确答案。错填、不填均无分请在每小题的空格中填上正确答案。错填、不填均无分。16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_。17.在双向循环链表中插入一个新的结点时，应修改_个指针域的值。18.若进栈序列为 a，b，c，且进栈和出栈可以穿插进行，则可能出现_个不同的出栈序列。19.链串的结点大小定义为结点的_中存放的字符个数。20.广义表(
7、a，(d，(c)的深度为_。21.在含有 3 个结点 a，b，c 的二叉树中，前序序列为 abc 且后序序列为 cba 的二叉树有_棵。22.若用邻接矩阵表示有向图，则顶点 i 的入度等于矩阵中_。23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为 5 的一趟希尔排序的结果为_。24.索引顺序查找的索引表由各分块中的最大关键字及各分块的_构成。25.VSAM 文件的实现依赖于操作系统中的_存取方法的功能。三、解答题三、解答题(本大题共本大题共 4 4 小题，每小题小题，每小题 5 5 分，共分，共 2020 分分)26.假设有一个形如的 88 矩阵，矩阵元
8、素都是整型量(次对角线以上的元素都是 0)。若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组 B 中，请回答下列问题：(1)B 数组的体积至少是多少?(2)若 a18存储在 B0中，a56存储在 Bk中，则 k 值为多少?(1)(2)27.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。(1)写出排序过程中前两趟的划分结果；(2)快速排序是否是稳定的排序方法?(1)本资料由湖南自考网收集整理，更多自考资料请登录 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。第第 3 3 页页(共共 6
9、 6 页页)(2)28.假设通信电文使用的字符集为a，b，c，d，e，f，g，h，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这 8 个字符设计哈夫曼编码。要求：(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；(2)按左分支为 0 和右分支为 1 的规则，分别写出与每个字符对应的编码。(1)(2)29.已知 3 阶 B树如图所示，(1)画出将关键字 6 插入之后的 B树；(2)画出在(1)所得树中插入关键字 2 之后的 B树。(1)(2)四、算法阅读题四、算法阅读题(本大题共本大题共 4 4 小题，每小题小题，每小题 5 5 分
10、，共分，共 2020 分分)30.假设以带头结点的单链表表示线性表，单链表的类型定义如下：typedefintDataType;typedef struct node DataType data;struct node*next;LinkNode,*LinkList;阅读下列算法，并回答问题：(1)已知初始链表如图所示，画出执行 f30(head)之后的链表；题 30 图(2)简述算法 f30 的功能。void f30(LinkList head)LinkListp,r,s;if(head-next)r=head-next;p=r-next;r-next=NULL;while(p)s=p;p=
11、p-next;if(s-data%2=0)s-next=head-next;head-next=s;else s-next=r-next;r-next=s;r=s;本资料由湖南自考网收集整理，更多自考资料请登录 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。第第 4 4 页页(共共 6 6 页页)(1)(2)31.假设以二叉链表表示二叉树，其类型定义如下：typedef struct node DataTypedata;struct node*lchild,*rchild;/左右孩子指针*BinTree;阅读下列算法，并
12、回答问题：(1)已知以 T 为根指针的二叉树如图所示，写出执行 f31(T)之后的返回值；(2)简述算法 f31 的功能。int f31(BinTree T)intd;if(!T)return 0;d=f31(T-lchild)+f31(T-rchild);if(T-lchild&T-rchild)returnd+1;elsereturnd;(1)(2)32.设有向图邻接表定义如下：typedef struct VertexNode adjlist MaxVertexNum ;int n，e；图的当前顶点数和弧数ALGraph；邻接表类型其中顶点表结点 VertexNode边表结点 EdgeN
13、ode 结构为：阅读下列算法，并回答问题：(1)已知某有向图存储在如图所示的邻接表 G 中，写出执行 f32(G)的输出；(2)简述算法 f32 的功能。int visited MaxNum;void DFS(ALGraph*G,int i)EdgeNode*p;visited i =TRUE;if(G-adjlist i.firstedge=NULL)printf(%c,G-adjlist i.vertex)；else p=G-adjlist i.firstedge;while(p!=NULL)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-next;本资料由
14、湖南自考网收集整理，更多自考资料请登录 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。第第 5 5 页页(共共 6 6 页页)void f32(ALGraph*G)inti;for(i=0;i n;i+)visited i =FALSE;for(i=0;i n;i+)if(!visitedi)DFS(G,i);(1)(2)33.下列算法 f33 的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列
15、按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。#define MAXLEN 100typedef int KeyType;typedef struct KeyType key;InfoType otherinfo;NodeType;typedef NodeType SqList MAXLEN;void f33(SqList R,int n)int i,j,k;NodeType t;i=0;j=n-l;while(i Rk+l.key)t=Rk;Rk=Rk+1;Rk+1=t;j-;for(k=j;k i;k-)if(2)t=Rk;Rk=Rk-1;Rk-1=t;(3);(1)
16、(2)(3)本资料由湖南自考网收集整理，更多自考资料请登录 下载再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。第第 6 6 页页(共共 6 6 页页)五、算法设计题五、算法设计题(本本大大题题 1010 分分)34.假设以带头结点的单链表表示线性表，单链表的类型定义如下：typedef int DataType;typedef struct node DataType data;struct node*next;LinkNode,*LinkList;编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为：voidf34(LinkList head);本资料由湖南自考网收集整理，更多自考资料请登录 下载考试必看：自考一次通过的秘诀！