发布时间 : 星期二 文章南邮通达2015数据结构B刷题试题及答案更新完毕开始阅读58edaf846c85ec3a86c2c560
数据结构试卷（八）
一、选择题(30分)
1. 字符串的长度是指（ ）。
(A) 串中不同字符的个数 (C) 串中所含字符的个数
(B) 串中不同字母的个数 (D) 串中不同数字的个数
2. 建立一个长度为n的有序单链表的时间复杂度为（ ）
(A) O(n)
(B) O(1)
(C) O(n2)
(D) O(log2n)
3. 两个字符串相等的充要条件是（ ）。
(A) 两个字符串的长度相等
(B) 两个字符串中对应位置上的字符相等
(C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对
4. 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择
（ ）。
(A) 99
(B) 97
(C) 91
(D) 93
5. 在二叉排序树中插入一个关键字值的平均时间复杂度为（ ）。
(A) O(n)
(B) O(1og2n)
(C) O(nlog2n)
(D) O(n2)
6. 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过
程中比较元素的顺序为( )。
(A) A[1]，A[2]，A[3]，A[4] (C) A[7]，A[3]，A[5]，A[4]
(B) A[1]，A[14]，A[7]，A[4] (D) A[7]，A[5] ，A[3]，A[4]
7. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。
(A) 8
(B) 7
(C) 6
(D) 5
8. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3
的结点，则该三叉链权中有（ ）个度数为0的结点。
(A) 5
(B) 6
(C) 7
(D) 8
29
9. 设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，
f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。
(A) aedfcb
(B) acfebd
(C) aebcfd
(D) aedfbc
10. 队列是一种（ ）的线性表。
四、算法设计题(20分)
1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。 设计一个在链式存储结构上统计二叉树中结点个数的算法。
void countnode(bitree *bt,int &count) {
if(bt!=0)
{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} }
2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。
typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;
typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode;
typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) {
int i,j; glinklistnode *p;
for(i=0;i<=n-1;i++) g2[i].firstarc=0; for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) if (g1.edge[i][j]==1) {
p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p;
p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; }
}
30
(A) 先进先出 (B) 先进后出 (C) 只能插入 (D) 只能删除
31
数据结构试卷（九）
一、选择题(30分)
1．下列程序段的时间复杂度为（ ）。
for(i=0； i for(i=0； i (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) 冒泡排序 32