2016年南京大学考研：计算机数据结构测试题和答案(二).doc

2016年南京大学考研：计算机数据结构测试题及答案（二） 　　　一、选择题(30分) 　　1.下列程序段的时间复杂度为( )。 　　for(i=0; im; p= c[i][j]+a[i][k]*b[k][j];= i=0; 　　(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n) 　　2.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。 　　(A) n-i (B) n+l -i (C) n-1-i (D) i 　　3.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为( )。 　　(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3 　　4.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( )。 　　(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n) 　　5.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为( )。 　　(A) p-right=s; s-left=p; p-right-left=s; s-right=p-right; 　　(B) s-left=p;s-right=p-right;p-right=s; p-right-left=s; 　　(C) p-right=s; p-right-left=s; s-left=p; s-right=p-right; 　　(D) s-left=p;s-right=p-right;p-right-left=s; p-right=s; 　　6.下列各种排序算法中平均时间复杂度为O(n2)是( )。 　　(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序 　　7.设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是( )。 　　(A) n-i (B) n-1-i (C) n+l -i (D) 不能确定 　　8.设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择( )。 　　(A) 小于等于m的最大奇数 (B) 小于等于m的最大素数 　　(C) 小于等于m的最大偶数 (D) 小于等于m的最大合数 　　9.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有( )个。 　　(A) 4 (B) 5 (C) 6 (D) 7 　　10.设完全无向图中有n个顶点，则该完全无向图中有( )条边。 　　(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 　　11.设顺序表的长度为n，则顺序查找的平均比较次数为( )。 　　(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2 　　12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过( )次比较。 　　(A) 1 (B) 2 (C) 3 (D) 4 　　13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为( )。 　　(A) 6 (B) 11 (C) 5 (D) 6.5 　　14.设有向无环图G中的有向边集合E={1，2，2，3，3，4，1，4}，则下列属于该有向图G的一种拓扑排序序列的是( )。 　　(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3 　　15.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为( )。 　　(A) 4 (B) 5 (C) 6 (D) 7 　　二、填空题(30分) 　　1. 1. 设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为： 　　1) s-next=___________;2) p-next=s;3) t=p-data; 　　4) p-data=___________;5) s-data=t; 　　2. 2. 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。 　　3. 3. 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。 　　4. 4. 对一组初始关键字序列(40，50，95，20，15，70，60，