2008年10月全国自考数据结构试题及答案.doc

2008年10月全国自考数据结构试题 课程代码：02331 一、单项选择题(本大题共小题，每小题分，共分) 1（） A. B. 队列 C. 树 D. 图 2．下面程序段的时间复杂度为（） for (i=0; im; i++) for (j=0; jn; j++) A[i][j]=i*j; A. O (m2) B. O (n2)C. O (m*n) D. O (m+n) 3．在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（A） A. p-next==head B. p-next-next==head C. p-next==NULL D. p==head 4．若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（） A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 5．两个字符串相等的条件是（） A. B. 含有相同的字符集 C. 都是非空串 D. 串的长度相等且对应的字符相同 6．如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（） A. head (tail (head (L))) B. head (head(head(L))) C. tail (head (tail (L))) D. head (head (tail (L))) 7．已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（） A. B. 1 C. 48 D. 49 8．在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，（） A. out B. Dout-1 C. Dout+1 D. n 9．如图所示的有向无环图可以得到的拓扑序列的个数是（） A. B. 4 C. 5 D. 6 10．如图所示的带权无向图的最小生成树的权为（C） A. B. 52 C. 54 D. 56 11．对长度为n的关键字序列进行堆排序的空间复杂度为（） A. log2n） B. O（1） C. O（n） D. O（n*log2n） 12．已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为 （35，51，24，13，68，56，42，77，93） （35，24，13，51，56，42，68，77，93） 所采用的排序方法是（） A. B. 冒泡排序 C. 快速排序 D. 归并排序 13．已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（） A. B. T[4] C. T[8] D. T[10] 14．适宜进行批量处理的文件类型是（） A. B. 索引顺序文件 C. 散列文件 D. 多关键字文件 15．VSAM文件的索引结构为（） A. B. 二叉排序树 C. B-树 D. 最优二叉树 二、填空题(本大题共小题，每小题分，共分)n的问题的时间耗费为T（n）=3n3，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的（4）倍。 17．将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是（O(m+n)）。 18．已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是（(rear-front+m)%m）。 19．字符串“sgabacbadfgbacst” 中存在有（3）个与字符串“ba”相同的子串。 20．假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC(a00),且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为（LOC(a00)+4(5j+i)）。x,y表示树的边（其中x是y的双亲），已知一棵树的边集为 {b,d,a,b,c,g,c,f,c,h,a,c}，该树的度是（3）。 22．n个顶点且含有环路的无向连通图中，至少含有（n）条边。 23．在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换