数据结构试题（华南理工大学）数据结构试题一2.docx

?一、选择题(30分)1．下列程序段的时间复杂度为（ ）。for(i=0； im； i++) for(j=0； jt； j++) c[i][j]=0；for(i=0； im； i++) for(j=0； jt； j++) for(k=0； kn； k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]；(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) i3．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ ）。 (A) N1-1(B) N2-1(C) N2+N3(D) N1+N34．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ ）。 (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) 710.设完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 (A) n(n-1)/2(B) n(n-1)(C) n(n+1)/2(D) (n-1)/211.设顺序表的长度为n，则顺序查找的平均比较次数为（ ）。(A) n(B) n/2(C) (n+1)/2(D) (n-1)/212.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（ ）次比较。(A) 1(B) 2(C) 3(D) 413.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ ）。(A) 6(B) 11(C) 5(D) 6.514.设有向无环图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，315.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。(A) 4(B) 5(C) 6(D) 7二、填空题(30分)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． 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。3． 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。4． 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。5． 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_____