数据结构》总的试卷以及答案.doc

《数据结构》总的试卷以及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、承诺：我将严格遵守考场纪律，并知道考试违纪、作弊的严重性，承担由此引起的一切后果。专业班级学号学生签名：2005—2006学年第1学期试卷数据结构课程类别：必修考核方式：开卷（限课本）题号一二三四五六七八九总分分数评卷人一、单选题（每题2分，共20分）1.以下数据结构中哪一个是线性结构？(B)A.有向图B.队列C.线索二叉树D.B树2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下(D)语句序列。A.p=q;p->next=q;B.p->next=q;q-

2、>next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;3.以下哪一个不是队列的基本运算？（A）A.在队列第i个元素之后插入一个元素B、从队头删除一个元素C、断一个队列是否为空D.读取队头元素的值4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成(B)个不同的字符串？A.14B.5C.6D.85.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为(B)。第10页共10页EAGCBDF图1A

3、．11B.35C.19D.53以下6-7题基于图1。1.该二叉树结点的前序遍历的序列为(C)。A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B2.该二叉树结点的中序遍历的序列为(A)。A.A、B、C、D、E、G、FB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD、B、D、C、A、F、G、E3.下面关于图的存储的叙述中正确的是(B)。A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用

4、邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D第10页共10页．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关1.下列关于二叉树遍历的叙述中，正确的是(D)。A.若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是

5、该二叉树的前序最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点2.栈和队列的共同特点是(A)。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点一、填空题（每空1分，共26分）1.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_O(n)__，在表尾插入元素的时间复杂度为_O(1)__。2.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是__p->next=HS;HS=p__;删除一个结点时，需

6、要执行的操作是第10页共10页_HS=HS->next_（假设栈不空而且无需回收被删除结点）。1.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩子结点的编号为_2i_，若它有右孩子，则右孩子结点的编号为_2i+1_，若它有双亲，则双亲结点的编号为_ëi/2û（或i/2）_。2.表示图的两种常用的存储结构为__邻接矩阵__、__邻接表_。3.假定一棵树的广义表表示为A（D（E，G），H（I，J）），则树中所含的结点数为_7__个，树的深度为__2__，树的度为_

7、_2___。4.在一个具有10个顶点的无向完全图中，包含有_____45__条边，在一个具有n个顶点的有向完全图中，包含有_n(n-1)____条边。5.队列的插入操作是在队列的___队尾____进行，删除操作是在队列的__队首____进行6.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_2n__个，其中_n-1_个用于指向孩子，n+1__个指针是空闲的。7.设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s

8、1，则顺序栈的容量至少应为__3__。一、运算题（每题6分，共24分）图31.试对图2中的二叉树画出其：(1)顺序存储表示的示意图；第10页共10页(1)二叉链表存储表示的示意图。答案：（1）：012345678910111213141516123456789（2）：见图3所示1.已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。并画出该二叉树。中序序列：e，b，d，c，a，g，i，h，j，f前序序列：a，b，e，d，c，f，g，h，i，j后序序列：e，c,d，b，i，j，h，g,f，a