数据结构练习题2

《数据结构练习题2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、选择题11.设某无向图冇n个顶点，则该无向图的邻接表中冇(b)个表头结点。(A)2n(B)n(C)n/2(D)n(n-l)2.设无向图G中冇n个顶点，则该无向图的最小生成树上冇(b)条边。(A)n(B)n-1(C)2n(D)2n-l11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X,则入队列的操作序列为(c)。(A)fi'ont->next=s；front=s；(B)s->next=rear；rear=s；(C)rear->next=s；rear=s；(D)s->next=front；front=s；12

2、.设某无向图中冇n个顶点c条边,(A)O(n+c)(B)0(n2)则建立该图邻接表的时间复杂度为((C)O(nc)(D)0(n3))o13.设某哈夫曼树中启199个结点,则该哈夫曼树中有(b)个叶子结点。(A)99(B)100(C)101(D)1024.设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为(B)。(A)5,3,4,6,1,2(B)3,2,5,6,4,1(C)3,1,2,5,4,6(D)1,5,4,6,2,323.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B插入结点X的操作序列

3、为(b)o(A)s->ncxt=p->ncxt；p->ncxt=-s；(B)q->ncxt=s；s->ncxt=p；(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q；1.下列程序段的时间复杂度为(a)ofor(i=0；i

4、+n)2.设顺序线性表屮有n个数据元素，则删除表中第i个元素需要移动(a)个元素。(A)n-i(B)n+1-i(C)n-l-i(D)i5.设指针变量p指向双向链表中结点A,指针变量s指向被插入的结点X,则在结点A的后而插入结点X的操作序列为(d)os->right=p->right；p->right->left=s；s->right=p->right；(A)p->right=s；s->left=p；p->right->left=s；(B)s->left=p；s->right=p->right；p->right=s:(C)p->right=s；p->right->lefl=s；

5、s->left=p；(D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；9.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有(0)个。(A)4(B)5(C)610.设完全无向图中有n个顶点，贝IJ该完全无向图屮有(a)条边。(A)n(n-l)/2(B)n(n-1)(C)n(n+l)/21.2.3.4.1.(D)77.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为(b)。(A)8(B)7(C)6(D)58.设一棵三叉树屮有2个度数为1的

6、结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有(c)个度数为0的结点。(A)5(B)6(C)7(D)89.设无向图G中的边的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为(a)。(A)aedfcb10.队列是一种(A)先进先出设一组权值集合度之和为(d)o(B)acfebd(a)的线性表。(B)先进后出W={2,3,4,5,(C)aebcfd(D)aedfbc(C)只能插入(D)只能删除6},则由该权值集合构造的哈夫曼树屮带权路径长(A)20(B)30(C)

7、40(D)451.设一条单琏表的头指针变量为headR该琏表没冇头结点，则其判空条件是(a)o(A)head=O(B)head->next==O(C)head->next==head(D)head!=O8.设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为(b)o(A)abedfe(B)acfcbd(C)acbdfc(D)aedfeb9.设输入序列是1、2、3、……、n,经过栈的作用后输出序列的