发布时间 : 星期三 文章自考数据结构历年试题及答案更新完毕开始阅读7e7bb987e53a580216fcfe68
B．在p所指结点的元素之前插入元素 C．在p所指结点的元素之后插入元素 D．在结点*p之前插入结点*s 4．栈和队列都是（ ）
A．限制存取位置的线性结构 B．顺序存储的线性结构 C．链式存储的线性结构 D．限制存取位置的非线性结构
5．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（ ）
A．1和n+1 B．1和n/2 C．－1和n D．－1和n+1
6．执行下列程序段后，串X的值为（ ） 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的运算是（ ） A．tail (head (LS)) B．head (tail (head (LS))) C．head (tail (LS)) D．tail (tail (head (LS))) 9．在具有n个叶子结点的严格二叉树中，结点总数为（ ） A．2n+1 B．2n C．2n-1 D．2n-2
10．若
C．vi和vj相互邻接 D．vi与vj?不相邻接
11．在一个带权连通图G中，权值最小的边一定包含在G的（ ） A．最小生成树中 B．深度优先生成树中 C．广度优先生成树中 D．深度优先生成森林中
12．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ ） A．左子树的叶子结点 B．左子树的分支结点 C．右子树的叶子结点 D．右子树的分支结点 13．希尔排序的增量序列必须是（ ） A．递增的 B．随机的 C．递减的 D．非递减的
14．如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（ ） A．插入排序 B．归并排序
C．冒泡排序 D．堆排序 15．设置溢出区的文件是（ ） A．索引非顺序文件 B．ISAM文件 C．VSAM文件 D．顺序文件
二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．下列程序段的时间复杂度为_O(n^2)_ product = 1;
for (i = n;i>0; i--) for (j = i+1; j 17．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是________________。 删除*P的直接后继结点 18．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________ 1)cbad, cbda, cdba 2)cabd, cadb, cdab 19．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________________。 2 / ( 4 + 2 ) = 1/3 20．右图表示的广义表为________________。[img]/0046615335847449.jpg[img] ( ( e ), ( ( e ), ( b, c ) ), ( L ) ) 21．若一棵满三叉树中含有121个结点，则该 树的深度为________________。 5 // ( 3^5 - 1 ) / ( 3 - 1 ) = 121 22．若以邻接矩阵表示有向图，则邻接矩阵上 第i行中非零元素的个数即为顶点vi的________________。 出度 23．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用________________排序方法。 24．在含20个关键字的3阶B树（2－3树）上查找一个关键字，至多需要访问___________次外存。 25．文件上的两类主要操作为________________和________________。 检索 和 维护 http://www.ezikao.com.cn/uploadimages/2 三、解答题（本大题共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 请仿照上例写出利用两个栈从1 2 3 4得到4 1 3 2的操作步骤。 H1,P1,H2,H1,H1,H1,P1,H2,P2,P2,P1,H2,P2,P1,H2,P2 27．已知树如右图所示，（1）写出该树的后序序列； （2）画出由该树转换得到的二叉树。 1) EBJKFGHICDA 2) 树变二叉树:兄弟相连,保留长子的连线 . A . / . B . / \\\\ . E C . / \\\\ . F D . / \\\\ . J G . \\\\ \\\\ . K H . \\\\ . I 28．为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是 hi = (h(key) + i(key%5+1))%7 0≤i≤6 （1）画出构造所得的散列表； （2）求出在等概率情况下查找成功时的平均查找长度。 1) . 0 1 2 3 4 5 6 . 31 17 48 33 40 2) ( 1 + 1 + 3 + 2 + 4 ) / 5 = 11 / 5 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 high ) { int mid if (low mid = (low +high)/2; MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high); Merge (R, low, mid, high); } } // MergeSortDC （1）第一次调用时的参数值； （2）第二次调用时的参数值； （3）第三次调用时的参数值； （4）第四次调用时的参数值； （5）第五次调用时的参数值； //此题有一定的难度,涉及到递归调用时,系统堆栈的情况 . low mid high 1) 1 1 2 2) 3 3 4 3) 1 2 4 4) 5 5 6 5) 7 7 8 6) 5 8 6 7) 1 8 4 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb)