《1月全国数据结构自考试题及答案解析.docx》由会员分享，可在线阅读，更多相关《1月全国数据结构自考试题及答案解析.docx（9页珍藏版）》请在三一文库上搜索。
1、精品自学考 料推荐全国 2019 年 1 月高等教育自学考试数据结构试题课程代码： 02331一、单项选择题（本大题共15 小题，每小题2 分，共 30 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1在数据结构中，数据的逻辑结构可以分成（）A 内部结构和外部结构B线性结构和非线性结构C紧凑结构和非紧揍结构D动态结构和静态结构2在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）A 数据元素的相邻地址表示B数据元素在表中的序号表示C指向后继元素的指针表示D数据元素的值表示3设 p 指向单链表中的一个结点，s 指向待插入的结
2、点，则下述程序段的功能是（）s - next = p - next;p - next = s;t = p - data; p - data = s - data; s -data = t; A 结点 *p 与结点 *s 的数据域互换B在 p 所指结点的元素之前插入元素C在 p 所指结点的元素之后插入元素D在结点 *p 之前插入结点 *s4栈和队列都是（）A 限制存取位置的线性结构B顺序存储的线性结构C链式存储的线性结构D限制存取位置的非线性结构5若数组s0.n-1 为两个栈s1 和 s2 的共用存储空间，且仅当s0.n-1 全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1
3、 和 s2 的栈顶指针的初值分别为（）A 1 和 n+1B 1 和 n/2C 1 和 nD 1 和 n+16执行下列程序段后，串X 的值为（）S= abcdefgh ;T= xyzw ;substr (X,S,2,strlen(T);substr (Y,S, stelen(T),2);strcat (X,Y);A cdefghB cdxyzw C cdefxy D cdefef7多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（）A 数组的元素处在行和列两个关系中B数组的元素必须从左到右顺序排列1精品自学考 料推荐C数组的元素之间存在次序关系D 数组是多维结构，内存是一维结构8从广义表
4、LS （ (p, q), r, s ）中分解出原子q 的运算是（）A tail (head (LS)C head (tail (LS)B head (tail (head (LS)D tail (tail (head (LS)9在具有 n 个叶子结点的严格二叉树中，结点总数为（）A 2n+1B 2nC 2n-1D 2n-210若 是有向图的一条边，则称（）A v邻接于 vB v邻接于 viijjC vi和 vj 相互邻接D vi 与 vj 不相邻接11在一个带权连通图G 中，权值最小的边一定包含在G 的（）A 最小生成树中B深度优先生成树中C广度优先生成树中D深度优先生成森林中12当在二叉排序
5、树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（）A 左子树的叶子结点B左子树的分支结点C右子树的叶子结点D右子树的分支结点13希尔排序的增量序列必须是（）A 递增的B随机的C递减的D非递减的14如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（）A 插入排序B归并排序C冒泡排序D堆排序15设置溢出区的文件是（）A 索引非顺序文件B ISAM 文件C VSAM 文件D顺序文件二、填空题（本大题共10 小题，每小题2 分，共 20 分）请在每小题的空格中填上正确答案。
6、错填、不填均无分。16下列程序段的时间复杂度为_ 。product = 1;for (i = n;i0; i-)for (j = i+1; j next =p - next - next 的作用是_ 。18假设元素只能按a,b,c,d 的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为_ ，不可能得到的出栈序列为_ 。2精品自学考 料推荐19若链串结点中的指针占4 个字节，每个字符占1 个字节，则结点大小为2 的链串的存储密度为 _ 。20右图表示的广义表为_ 。21若一棵满三叉树中含有121 个结点， 则该树的深度为 _ 。22若以邻接矩阵表示有向图， 则邻接矩阵上第
7、 i 行中非零元素的个数即为顶点vi 的 _ 。23若希望只进行 8 趟排序便能在4800 个元素中找出其中值最小的8 个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用_ 排序方法。24在含 20 个关键字的3 阶 B 树（ 2 3 树）上查找一个关键字，至多需要访问_次外存。25文件上的两类主要操作为 _ 和_ 。三、解答题（本大题共4 小题，每小题 5 分，共 20 分）26设栈 S1 的入栈序列为1 2 3 4 （每个数字为 13 个元素），则不可能得到出栈序列3142。但可通过增设栈 S2 来实现。例如，按下图中的箭头指示，依次经过栈S1 和 S2，便可得到序列3
8、1 4 2。如果用 H1 和 H2 分别表示栈 S1 和 S2 的进栈操作， 用 P1 和 P2 分别表示两个栈的出栈操作，则得到 3 1 4 2 的一个操作步骤为H1， H1， H1， P1， H2，P2， P1，H2 ，P1， H2， P2， H1， P1，H2 ，P2， P2 请仿照上例写出利用两个栈从 1 2 3 4 得到 4 1 3 2 的操作步骤。27已知树如右图所示，（ 1）写出该树的后序序列；（ 2）画出由该树转换得到的二叉树。3精品自学考 料推荐28为关键字 （17，33，31，40，48）构造一个长度为7 的散列表， 设散列函数为h(key)=key%7,用开放定址法解决冲
9、突的探查序列是hi = (h(key) + i(key%5+1)%70 i 6（ 1）画出构造所得的散列表；（ 2）求出在等概率情况下查找成功时的平均查找长度。29已知 R 1.8中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC对 R 进行自顶向下的二路归并排序过程中，前5 次调用函数Merge(R, low, mid, high) 时参数low, mid和 high 的值。void MergeSortDC (int R, int low, int mid, int high )int mid;if (low next;LinkList pb = L
10、b - next;free (Lb);4精品自学考 料推荐while (pa & pd)if (pa - data data) pre = pa; pa = pa - next; else if (pa - data pb -data)(1) ;pre = pb;pb = pb - next;(2) ;elseq = pb; pb = pb - next; free (q);if (pb)(3);(1)(2)(3)31已知串的存储结构为动态存储分配的顺序串。阅读下列算法，并回答问题：（ 1）写出执行函数调用 strc (s, r)的返回结果，其中 s= aba , r= abababa ; （
11、 2）简述函数 strc 的功能。int strc (HString * sub, HString * str)int i=0, j, k, count =0;while (i lengthsub - length +1)j=i; k=0;while (k length & str - chj = =sub - chk )j+; k+;if (k = = sub - length)count +; i=j-sub - length +1;else i+;5精品自学考 料推荐return count;(1)(2)32下列函数MDFSForest 的功能是，对一个采用邻接矩阵作存储结构的图进行深度
12、优先搜索遍历，输出所得深度优先生成森林中各条边。请在空缺处填入合适内容，使其成为一个完整的算法。#define MaxMun 20 / 图的最大顶点数typedef struct char vexs MaxNum; / 字符类型的顶点表int edges MaxNumMaxNum; /邻接矩阵int n, e; / 图的顶点数和边数MGraph; / 图的邻接矩阵结构描述typedef enum FALSE, TRUE Boolean;Boolean visited MaxNum;void MDFSTree (MGraph *G , int i);void MDFSForest (MGraph
13、 *G)int i, k;for (i=0; i n; i+)visited i =(1);for (k = 0; k n; k+)if (!visited k) MDFSTree (G,k);void MDFSTree (MGraph *G , int i)int j;visited i=TRUE;for (j=0; j n; j+)if (2)printf ( G - vexs i, G - vexs j);(3);6精品自学考 料推荐（ 1）（ 2）（ 3）33已知整形数组L 1.8中的元素依次为（9， 8， 5， 7， 6， 3，2， 1），阅读下列函数，并写出执行函数调用sort(L
14、, 8) 时，对 L 进行的头两趟（pass分别为 0 和 1）处理结果。Void sort (int R,int n)int pass = 0, k, exchange, x;do k=pass%2+1;exchange = 0;while (kRk+1)x = Rk; Rk = Rk+1; Rk+1 = x;exchange =1;K+=2pass +;while (exchange = = 1| pass =1);第一趟（ pass = 0） :第二趟（ pass = 1） :五、算法设计题（本大题共10 分）34已知二叉排序树中结点的关键字为整数，设计递归算法按递增有序性输出树中所有大于或等于给定值 x 的结点，并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构，其结点结构为：lchildkeyrchild7