最新全国1月高等教育自学考试数据结构试题及答案.pdf
《最新全国1月高等教育自学考试数据结构试题及答案.pdf》由会员分享,可在线阅读,更多相关《最新全国1月高等教育自学考试数据结构试题及答案.pdf(13页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 全 国 2 0 1 1 年 1 月 高 等 教 育 自 学 考 试 数 据 结 构 试 题 及 答 案 精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 全国 2011 年 1 月高等教育自学考试 数据结构试题(课程代码:02331)一、单项选择题(本大题共 15 小题,每小题 2 分,共 30 分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列选项中与数据存储结构无关的术语是()A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有 n 个元素的有序表归并成一个有序表,最少的比较次数是()A.n-1
2、 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为 m,队头指针 front 指向队头元素,队尾指针 rear 指向队尾元素的下一个位置,则向队列中插入新元素时,修改指针的操作是()A.rear=(rear-1)%m;B.front=(front+1)%m;C.front=(front-1)%m;D.rear=(rear+1)%m;4.递归实现或函数调用时,处理参数及返回地址,应采用的数据结构是()A.堆栈 B.多维数组 C.队列 D.线性表 要求的请将其代码填写在题后的括号内错选多选或未选均无分下列选项中与数据存储结构无关的术语是顺序表链队列 指向队头元素队尾指针指向队尾元素
3、的下一个位置则向队列中插入新元素时改指针的操作是递归实现或函数调用时处 如有侵权请联系网站删除设有两个串和其中是的子串则求在中首次出现位置的算法称为求子串串匹配串联接求串长对精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 5.设有两个串 p 和 q,其中 q 是 p 的子串,则求 q 在 p 中首次出现位置的算法 称为()A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表 A,若 head(A)等于 tail(A),则表 A为()A.()B.()C.(),()D.(),(),()7.若一棵具有 n(n0)个结点的二叉树的先序序列与后序序列正好相反,则该二 叉
4、树一定是()A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为 n 的二叉树 D.存在度为 2 的结点的二叉树 8.若一棵二叉树中度为 l 的结点个数是 3,度为 2 的结点个数是 4,则该二叉树 叶子结点的个数是()A.4 B.5 C.7 D.8 9.下列叙述中错误的是()A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10.已知有向图 G=(V,E),其中 V=V1,V2,V3,V4,E=,图 G的拓扑序列是()A.V1,V2,V3,V4 B.
5、V1,V3,V2,V4 要求的请将其代码填写在题后的括号内错选多选或未选均无分下列选项中与数据存储结构无关的术语是顺序表链队列 指向队头元素队尾指针指向队尾元素的下一个位置则向队列中插入新元素时改指针的操作是递归实现或函数调用时处 如有侵权请联系网站删除设有两个串和其中是的子串则求在中首次出现位置的算法称为求子串串匹配串联接求串长对精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 C.V1,V3,V4,V2 D.V1,V2,V4,V3 11.平均时间复杂度为 O(n log n)的稳定排序算法是()A.快速排序 B.堆排序 C.归并排序 D.冒泡排序 12.已知关键字序列
6、为(51,22,83,46,75,18,68,30),对其进行快速排 序,第一趟划分完成后的关键字序列是()A.(18,22,30,46,51,68,75,83)B.(30,18,22,46,51,75,83,68)C.(46,30,22,18,51,75,68,83)D.(30,22,18,46,51,75,68,83)13.某索引顺序表共有元素 395 个,平均分成 5 块。若先对索引表采用顺序查 找,再对块中元素进行顺序查找,则在等概率情况下,分块查找成功的平均 查找长度是()A.43 B.79 C.198 D.200 14.在含有 10 个关键字的 3 阶 B-树中进行查找,至多访问的
7、结点个数为()A.2 B.3 C.4 D.5 15.ISAM 文件系统中采用多级索引的目的是()A.提高检索效率 B.提高存储效率 C.减少数据的冗余 D.方便文件的修改 二、填空题(本大题共 10 小题,每小题 2 分,共 20 分)请在每小题的空格中填上正确答案。错填、不填均无分。16.数据结构由数据的逻辑结构、存储结构和数据的 _三部分组成。17.在单链表中某结点后插入一个新结点,需要修改 _个结点指针域的值。要求的请将其代码填写在题后的括号内错选多选或未选均无分下列选项中与数据存储结构无关的术语是顺序表链队列 指向队头元素队尾指针指向队尾元素的下一个位置则向队列中插入新元素时改指针的操
8、作是递归实现或函数调用时处 如有侵权请联系网站删除设有两个串和其中是的子串则求在中首次出现位置的算法称为求子串串匹配串联接求串长对精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 18.设栈 S 的初始状态为空,若元素 a、b、c、d、e、f 依次进栈,得到的出栈 序列是 b、d、c、f、e、a,则栈 S 的容量至少是 _。19.长度为零的串称为 _。20.广义表 G=(a,b,(c,d,(e,f),G)的长度为 _。21.一棵树 T 采用孩子兄弟链表存储,如果树 T 中某个结点为叶子结点,则该结 点在二叉链表中所对应的结点一定是 _。22.一个有 n 个顶点的无向连通图
9、,最少有 _条边。23.当待排关键字序列基本有序时,快速排序、简单选择排序和直接插入排序三 种排序方法中,运行效率最高的是 _。24.在一棵深度为 h 的具有 n 个结点的二叉排序树中,查找任一结点的最多比较 次数是 _。25.不定长文件指的是文件的 _大小不固定。三、解答题(本大题共 4 小题,每小题 5 分,共 20 分)26.已知一棵二叉排序树(结点值大小按字母顺序)的前序遍历序列为EBACDFHG,请回答下列问题:(1)画出此二叉排序树;(2)若将此二叉排序树看作森林的二叉链表存储,请画出对应的森林。27.已知有向图的邻接表如图所示,请回答下面问题:(1)给出该图的邻接矩阵;(2)从结
10、点 A出发,写出该图的深度优先遍历序列。要求的请将其代码填写在题后的括号内错选多选或未选均无分下列选项中与数据存储结构无关的术语是顺序表链队列 指向队头元素队尾指针指向队尾元素的下一个位置则向队列中插入新元素时改指针的操作是递归实现或函数调用时处 如有侵权请联系网站删除设有两个串和其中是的子串则求在中首次出现位置的算法称为求子串串匹配串联接求串长对精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 28.已知待排记录的关键字序列为 25,96,11,63,57,78,44,请回答下列 问题:(1)画出堆排序的初始堆(大根堆);(2)画出第二次重建堆之后的堆。29.已知关键字
11、序列为(56,23,41,79,38,62,18),用散列函数 H(key)=key%11 将其散列到散列表 HT0.10 中,采用线性探测法处理冲突。请回答下列问题:(1)画出散列存储后的散列表:(2)求在等概率情况下查找成功的平均查找长度。四、算法阅读题(本大题共 4 小题,每小题 5 分,共 20 分)30.阅读下列程序。void f30(int A,int n)int i,j,m;for(i=1;in;i+)for(j=0;ji;j+)m=Ai*n+j;Ai*n+j=Aj*n+i;Aj*n+i=m;要求的请将其代码填写在题后的括号内错选多选或未选均无分下列选项中与数据存储结构无关的术语
12、是顺序表链队列 指向队头元素队尾指针指向队尾元素的下一个位置则向队列中插入新元素时改指针的操作是递归实现或函数调用时处 如有侵权请联系网站删除设有两个串和其中是的子串则求在中首次出现位置的算法称为求子串串匹配串联接求串长对精品好资料-如有侵权请联系网站删除 精品好资料-如有侵权请联系网站删除 回答下列问题:(1)已知矩阵 B=9 8 7 6 5 4 3 2 1,将其按行优先存于一维数组 A 中,给出执行函数调 用 f30(A,3)后矩阵 B 的值;(2)简述函数 f30 的功能。31.假设以二叉链表表示二叉树,其类型定义如下:typedef struct node char data;stru
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新 全国 高等教育 自学考试 数据结构 试题 答案
限制150内