2009年1月全国自学考试《数据结构》试题.docVIP

2009年1月自学考试数据结构试题 (本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分1.下列程序段的时间复杂度为( ) s=0； for(i=1；in；i++) for(j=1；jn；j++) s+=i*j； A.O(1) B.O(n) C.O(2n) D.O(n2) 2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是( ) A.head==NULL； B.head-next==NULL； C.head!=NULL； D.head-next==head； 3.栈是一种操( ) A.先进先出 B.后进先出 C.进优于出 D.出优于进 4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( ) A.(rear-front-1)％n B.(rear-front)％n C.(front-rear+1)％n D.(rear-front+n)％n 5.判断两个串大小的基本准则是( ) A.两个串长度的大小 B.两个串中首字符的大小 C.两个串中大写字母的多少 D.对应的第一个不等字符的大小 6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为( ) A.1012 B.1017 C.1034 D.1036 7.高度为5的完全二叉树中含有的结点数至少为( ) A.16 B.17 C.31 D.32 8.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( ) A.5 B.8 C.11 D.18 9.下列所示各图中是中序线索化二叉树的是( ) 10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为( ) A.(v0，v1，v2，v5，v4，v3) B.(v0，v1，v2，v3，v4，v5) C.(v0，v1，v5，v2，v3，v4) D.(v0，v1，v4，v5，v2，v3) 11.如图所示有向图的一个拓扑序列是( ) A.ABCDEF B.FCBEAD C.FEDCBA D.DAEBCF 12.下列关键字序列中，构成大根堆的是( ) A.5，8，1，3，9，6，2，7 B.9，8，1，7，5，6，2，33 C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，3 13.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( ) A. B. C. D. 14.已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( ) 15.数据库文件是由大量带有结构的( ) A.记录组成的集合 B.字符组成的集合 C.数据项组成的集合 D.数据结构组成的集合 (本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_________。 17.在双向循环链表中插入一个新的结点时，应修改_________个指针域的值。 18.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现_________个不同的出栈序列。 19.链串的结点大小定义为结点的_________中存放的字符个数。 20.广义表(a，(d，(c)))的深度为_________。 21.在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有_________棵。 22.若用邻接矩阵表示有向图，i的度等于矩阵中_________。 23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为_________。 24.索引顺序查找的索引表由各分块中的最大关键字及各分块的_________构成。 25.VSAM文件的实现依赖于操作系统中的_________存取方法的功能。 (本大题共4小题，每小题5分，共20分) 26.假设有一个形如 8×8矩阵，矩阵元素都是整型量(次对角线以上的元素都是0)。 B中，请