高等教育自学考试数据结构试题.docx

1、高等教育自学考试数据结构试题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1在数据结构中，数据的逻辑结构可以分成（）A内部结构和外部结构 B线性结构和非线性结构C紧凑结构和非紧揍结构 D动态结构和静态结构2在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（）A数据元素的相邻地址表示 B数据元素在表中的序号表示C指向后继元素的指针表示 D数据元素的值表示3设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（）s - next = p - next; p -

2、 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和s2的栈顶指针的初值分别为（）A1和n+1 B1和n/2C1和n D1和n+16执行下列程序段后，串X的

3、值为（） S=?abcdefgh?; T=?xyzw?; substr (X,S,2,strlen(T); substr (Y,S, stelen(T),2); strcat (X,Y);A?cdefgh? B?cdxyzw?C?cdefxy? D?cdefef?7多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（）A数组的元素处在行和列两个关系中 B数组的元素必须从左到右顺序排列C数组的元素之间存在次序关系 D数组是多维结构，内存是一维结构8从广义表LS（(p, q), r, s）中分解出原子q的运算是（）Atail (head (LS) Bhead (tail (head (LS)

4、Chead (tail (LS) Dtail (tail (head (LS)9在具有n个叶子结点的严格二叉树中，结点总数为（）A2n+1 B2nC2n-1 D2n-210若是有向图的一条边，则称（）Avi邻接于vj Bvj邻接于viCvi和vj相互邻接 Dvi与vj不相邻接11在一个带权连通图G中，权值最小的边一定包含在G的（）A最小生成树中 B深度优先生成树中C广度优先生成树中 D深度优先生成森林中12当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（）A左子树的叶子结点 B左子树的分支结点C右子树的叶子结点

5、D右子树的分支结点13希尔排序的增量序列必须是（）A递增的 B随机的C递减的 D非递减的14如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（）A插入排序 B归并排序C冒泡排序 D堆排序15设置溢出区的文件是（）A索引非顺序文件 BISAM文件CVSAM文件 D顺序文件二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。16下列程序段的时间复杂度为_。product = 1;for (i = n;i0; i-)for (j = i+1; jproduct *=j;17已知指针p指向单

6、链表中某个结点，则语句p - next =p - next - next的作用是_。18假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为_，不可能得到的出栈序列为_。19若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为_。20右图表示的广义表为_。21若一棵满三叉树中含有121个结点，则该树的深度为_。22若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的_。23若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该

7、选用_排序方法。24在含20个关键字的3阶B树（23树）上查找一个关键字，至多需要访问_次外存。25文件上的两类主要操作为_和_。三、解答题（本大题共4小题，每小题5分，共20分）26设栈S1的入栈序列为1 2 3 4（每个数字为13个元素），则不可能得到出栈序列3142。但可通过增设栈S2来实现。例如，按下图中的箭头指示，依次经过栈S1和S2，便可得到序列3 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请仿照

8、上例写出利用两个栈从1 2 3 4得到4 1 3 2的操作步骤。27已知树如右图所示，（1）写出该树的后序序列； （2）画出由该树转换得到的二叉树。28为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是hi = (h(key) + i(key%5+1)%7 0i6（1）画出构造所得的散列表；（2）求出在等概率情况下查找成功时的平均查找长度。29已知R1.8中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC对R进行自顶向下的二路归并排序过程中，前5次调用函数Merge(

9、R, low, mid, high)时参数 low, mid 和high的值。void MergeSortDC (int R, int low, int mid, int high ) int mid; if (lowHIGH) mid = (low +high)/2; MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high); Merge (R, low, mid, high); / MergeSortDC （1）第一次调用时的参数值；（2）第二次调用时的参数值； （3）第三次调用时的参数值；（4）第四次调用时的参数值；（5）第五次调用时

10、的参数值；四、算法阅读题（本大题共4小题，每小题5分，共20分）30下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。void union (LinkList La, LinkList Lb) /本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La - next; LinkList pb = Lb -

11、next; free (Lb); 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) ; else q = pb; pb = pb - next; free (q); if (pb) (3) ; (1) (2) (3)31已知串的存储结构为动态存储分配的顺序串。阅读下列算法，并回答问题： （1）写出执行函数调用 strc (s, r)的返回结果，其中s=aba, r=abababa;（2）简述函

12、数strc的功能。int strc (HString * sub, HString * str)int i=0, j, k, count =0;while (i length ?C sub - 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+;return count;(1)(2)32下列函数MDFSForest的功能是，对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历，输出所得深度优先

13、生成森林中各条边。请在空缺处填入合适内容，使其成为一个完整的算法。#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 *G) int i, k; f

14、or (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) ; （1）（2）（3）33已知整形数组L1.8中的元素依次为（9，8，5，7，6，3，2，1），阅读下列函数，并写出执行函数调用sort(L, 8)时，对L进行的头两趟（pass

15、分别为0和1）处理结果。Void sort (int R,int n) int pass = 0, k, exchange, x; do k=pass%2+1; exchange = 0; while (kN) if (RkRk+1) x = Rk; Rk = Rk+1; Rk+1 = x; exchange =1; K+=2 pass +; while (exchange = = 1| pass =1); 第一趟（pass = 0）:第二趟（pass = 1）:五、算法设计题（本大题共10分）34已知二叉排序树中结点的关键字为整数，设计递归算法按递增有序性输出树中所有大于或等于给定值x的结点，并以函数的参数返回输出的结点个数。假设以二叉链表为存储结构，其结点结构为：lchildkeyrchild