数据结构复习_考试题及答案汇总(共7套)

1、华东交大数据结构期考试卷及答案(一)参考答案以及评分标准(A )卷题号四五六七八九十总分累分人 签名题分20205010100得分考生注意事项：1、本试卷共上页，总分100分,考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一甲的用孙alp淋 =la。系辿sis魁一廿运出拈怅哩三静-H卦帝郛K-定东盘与三阳勿旧闻 盟数eEw震疥幽卡津宾却”YWT都钟？YW磐S京员zsis s数据结构(C )课程 课程类别：堂、限、任闭卷(1开卷(范围)(仅限课本)：考试日期：20卷-7-5一、选择题(每题2分，共20分)|得分|评阅人1、在数据结构的讨论中把数据结构从逻辑上分为(C

2、 )A)内部结构与外部结构 B)静态结构与动态结构I I0线性结构与非线性结构 D)紧凑结构与非紧凑结构2、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s, 则执行( D )。A) sTink=plink;p->link=s;B) plink=s;slink=q;C) plink=slink;slink=p;D) qlink=s;sTink=p;3、队和栈的主要区别是(D )A)逻辑结构不同B)存储结构不同C)所包含的运算个数不同D)限定插入和删除的位置不同4、在循环队列中用数组A0.mT存放队列元素，其队头和队尾指针分别为 front和rear,则当前队列中的元素

3、个数是( D )。A) (front rear+1)%mB) (rear front+l)%mC) (front rear+m)%mD) (rear front+m)%m5、下面程序段的时间复杂度为( C )for (int i=0;i<m;i+)for (int j=O;j<n;j+) aij=i*j;A) 0(m:) B) 0(n2) C) 0 (m*n) D) 0 (m+n)6、 一棵二叉树的前序遍历序列为ABCDEFG,它的中序序列可能是（B/D）A） CABDEFG B） ABCDEFG C） DACEFBG D）BADCFEG7、下面结构中最适于表示稀疏无向图的是（E

4、）A）邻接矩阵B）逆邻接表C）邻接多重表D）十字链表E）邻接表8、一个对象序列的排序码为46, 79, 56, 38, 40, 84,采用快速排序以位于最 左位置的对象为基准而得到的第一次划分结果为（C ）。A） 38, 46, 79, 56, 40, 84B） 38, 79, 56, 46, 40, 84C） 40, 38, 46, 56, 79, 84D） 38, 46, 56, ?9, 40, 849、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（C ）个。A）n-1 B） n C） n+110、线性链表不具有的特点是（A ）。A）随机访问0插

5、入与删除时不必移动元素D） n+2B）不必事先估计所需存储空间大小D）所需空间与线性表长度成正比二、填空题（每题1分，共20分）得分评阅人1、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（n+l）/2 ）2、将一个递归算法改为对应的非递归算法时，通常需要使用（栈 ）3、二又树中第5层上的结点个数最多为（16）4、已知五个元素ABCDE的进栈次序为ABCDE,若C为第一个出栈元素，则下一个 出栈的元素不可能是（A ）；5、向一个由HS指向的带头结点的链栈中插入一个结点时p时，需要执行的操作 是（.p->next=HS->next; HS->next=p ）；

6、删除一个结点时，需要执行的操作 是（_ HS->next =HS->next->next _）（假设栈不空而且无需回收被删除结点）。 6、已知链栈的结点结构的栈顶指针为top,则实现将指针p所指结点插入栈顶的 语句依次为（ p->next=top ）和（ top=p ）o7、对于线性表（70, 34, 55, 23, 65, 41, 20）进行散列存储时，若选用H （K） 二K%7作为散列函数，则散列地址为0的元素有（1 ）个，散列地址为6的有（4） 个。8、假定一棵树的广义表表示为A （D （E, G）, H （I, J）,则树中所含的结点数 为7个，树的深度为_3

7、,树的度为2_o9、若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一 维数组A中，即编号为0的结点存储到A0中。其余类推，则Ai元素的左孩 子元素为_21+1,右孩子元素为 2i+2,双亲元素为一（i-l）/2_o 10、在一个具有10个顶点的无向完全图中，包含有_45一条边，在一个具有n 个顶点的有向完全图中，包含有_n（n-1）条边。1. 11、后缀算式79 2 30 +- 4 2 /*的值为_94。中缀算式（3+X*Y） -2*Y/3对应的后缀算式为_3 XY* + 2Y*3 / -。三、简答题（5题，共50分）1、已知某二义树的前序序列为EBADCFHGI ,中序序

8、列为 ABCDEFGHL请画出二义树并写出它的后序序列。（构造出二叉树 7分，后序遍历3分，共10分） 参考答案：得分评阅人后序序列:ACDBGIHFE 二义树为:第12页共5页评分标准：构造出二叉树7分，后序遍历3分2、将关键码53, 78, 65, 17, 87, 09, 81, 45, 23依次插入到一棵初始为空的 二又搜索树中，画出每插入一个关键码后的二又排序树。（每个过程1分，共9分） 参考答案：评分标准：（每个过程1分，共9分）3、假定用于通讯的电文仅有8个字母Cl, C2,，C8组成，各个字母在电文中 出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4,试为这8

9、个字母设计哈夫曼编 码树并写出每个字母的编码。（画出哈夫曼树得3分，写出一个字母的编码是1分, 总分共n分） 参考答案：cS cl虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。本题中各字母编码如下: cl:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:ll c8:0011评分标准：画出哈夫曼树得3分，每个字母的编码是1分，共8分4、已知一个图的定点集V各边集G如下：(16分)V=0,1,2, 3, 4, 5, 6, 7, 8, 9);E=(0, 1), (0,4), (1,2), (1,7), (2, 8), (3,4), (3, 8), (5,6

10、), (5, 8), (5, 9), (6, 7),(7,8), (8, 9)当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的定点序列和按广度优先搜索遍历得到的定点序列。假定每个顶点邻接表中的节点是按顶点序号从大到小的次序链接的。图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时参考答案4、图浜度优先序列广度优先序列邻接印阳表示时0, I. 2, 8, 3, 4,工 6, 7, 90, B, $ 2, 7, 3, 8. 6, 5, 9邻接表表示时Or 4, 3, 8, 9r 5, 6, 7, b 20, 4, 1, 3, 7, 2, 8, 6, 9, 5评分标

11、准：正确写出每个序列得4分5、 LinkList mynote(LinkList L)/L是不带头结点的单链表的头指针if(L&&L->next)q=L； L=L>next： p=L；SI：while(p >next) p=p >next；S2：p >next=q： q>next=NULL：return L：）请回答下列问题：（l）说明语句SI的功能；（2）说明语句组S2的功能;（3）设链表表示的线性表为（al,a2,an），写出算法执行后的返回值所 表示的线性表。答案：（1）查询链表的尾结点 （1分）（2）将第一个结点链接到链表的尾部，作为

12、新的尾结点-一（1分）（3）返回的线性表为（a2, a3, , an, al） （2分）四、程序编程题（每题5分，共10分）得分评阅人1、统计出单链表HL中结点的值等于给定值X的结点数。int CountX（LNode* HL, ElemType x）参考答案：int CountX（LNode* HL, ElemType x） int i=0; LNode* p=乩;1.为计数器 （1 分）while（p!=NULL） if （P->data=x） i+;p=p_>next;/while,出循环时i中的值即为x结点个数 （3分）return i ;（ 1 分）/CountX2、试写

13、一算法写出用二义链表表示给定二义树的叶子结点总数。int GetLeaves（ BinTree root）参考答案：int GetLeaves（ BinTree root）求叶结点总数static int leaf=0;此1用于记叶结点数，注意用静态变量（1分）if（root） 递归计算叶结点数if（!（root->lchiId root->rchiId）leaf+;如果该结点无左右孩子，则叶子数加1GetLeaves（root->lchild）;算左子数的叶结点数GetLeaves （root->rchild）; 算右子树的叶结点数）（3分）return leaf;

14、返回结果 （1 分）华东交大数据结构期考试卷及答案（二）数据结构（C ）课程 课程类别：必、限、任闭卷（1开卷（范围）（仅限课本）：考试日期：一用常淋nip淋 圣需 。去皿尽£魁一mW田理怅哩as题号四五六七八九十总分累分人 签名题分2026241416100得分考生注意事项：1、本试卷共L页，总分100分,考试时间120 分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、 选择题（每小题2分，共20分）1 .在一个带有附加表头结点的单链表HL中，若要向表头插入一 个由指针P指向的结点，则执行（）。A. HL=p; p->next=HL;B. p->nex

15、t=HL->next;C. p->next=HL; p=HL;D. p->next=HL; HL=p;HL->next=p;2 .若顺序存储的循环队列的QueueMaxSizef,则该队列最多可存储（）个元A. nB. n-1 C. n+13 .下述哪一条是顺序存储方式的优点？（）A.存储密度大C.获取符合某种条件的元素方便D.不确定B.插入和删除运算方便D.查找运算速度快4,设有一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35 .下列关于二叉树遍历的叙述中，正确的是()。A.若一

16、个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二义树的 前序遍历最后一个结点B.若一个点是某二叉树的前序遍历最后一个结点，则它必是该二义树的中序 遍历的最后一个结点、C.若一个结3捻某二叉树的中序遍历的最后一个结点，则它必是该二叉树的 前序最后一个结点D.若一个树叶是某二叉树的前序最后一个结点，则它必是该二义树的中序遍 历最后一个结点6 . k层二义树的结点总数最多为().A. 2-1 B. 2K+1 C. 2K-1 D. 27 .对线性表进行二分法查找，其前提条件是().A.线性表以链接方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以顺

17、序方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序8 .对n个记录进行堆排序，所需要的辅助存储空间为A. 0 (log:n) B. 0 (n) C. 0(1) D. 0 (n2)9 .对于线性表(7, 34, 77, 25, 64, 49, 20, 14)进行散列存储时，若选用H (K) =K%7作为散列函数，则散列地址为。的元素有()个，A. 1B. 2C. 3D. 410 .下列关于数据结构的叙述中，正确的是().A.数组是不同类型值的集合B .递归算法的程序结构比迭代算法的程序结构更为精炼C .树是一种线性结构D,用一维数组存储一棵完全二义树是有效的

18、存储方法2、 填空题(每空1分，共26分)1 .数据的逻辑结构被分为、和 四利I。2 . 一个算法的时间复杂度为(3/+2000Hog二加90)/,其数量级表示为 03 .对于一个长度为n的单链存储的队列，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为。4 .假定一棵树的广义表表示为A (D (E, G), H (I, J),则树中所含的结点数为 个，树的深度为，树的度为 c5 .后缀算式79 2 30 +- 4 2 / *的值为 二中缀算式(3+X*Y)-2Y/3对应的后缀算式为 o6 .若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0

19、的结点存储到A0中。其余类推，则A i 元素 的左孩子元素为,右孩子元素为，双亲元素为7 .在树中，一个结点的直接后继结点称为该结点的,一个结点的直接 前趋结点称为该结点的 O8 .在一个具有10个顶点的无向完全图中，包含有 条边，在一个具有n个顶点的有向完全图中，包含有 条边。9 .栈又称为 表，队列又称为 表。10 .表示图的两种常用的存储结构为 和 c11 .队列的插入操作是在队列的 进行，删除操作是在队列的进行。12 .在线性表的散列存储中，装填因子a乂称为装填系数，若用m表示散列表的长 度，n表示待散列存储的元素的个数，则a等于。3、 运算题(每题3分，共24分)1 .在如下数组A中

20、链接存储了一个线性表，表头指针存放在A 0. next,试写 出该线性表。234567data next2 .已知一棵二义树的前序遍历的结果是ABKCDFGHIJ,中序遍历的结果是 KBCDAFHIGJ,试画出这棵二叉树。3 .已知一个图的顶点集V为：¥=1, 2, 3, 4, 5, 6, 7);其共有10条边。该图用如下边集数组存储:122552261364547677751122233457试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。4、 阅读算法(每题7分，共14分)1 .在下面的每个程序段中，假定线性表La的类型为List,元素类型ElemType 为i

21、nt,并假定每个程序段是连续执行的。试写出每个程序段执行后所得 到的线性表Lao(1) InitList(La);Int a = 100, 26, 57, 34, 79;For (i=0;i<5;i+)Insert (La, ai);TraverseList(La);(2) DeleteFront (La);InsertRear(La, DeleteFront(La);TraverseList(La);(3) ClearList(La);For (i=0;i<5;i+)InsertFront(La, ai);TraverseList(La);2 .现面算法的功能是什么？void A

22、BC(BTNode * BT)(if BT cout«BT->data«，'ABC(BT->left);ABC(BT->right);5、 编写算法(共16分)HL为单链表的表头指针，试写出在该单链表中查找具有给定的元素item的算法。 bool Find(LNode* HL, ElemType &item)参考答案:1、 单选题(每题2分，共20分)l.B 2.B 3.A 4.C 5.D 6.A 7.C8.C9.D10.D2、 填空题(每空1分，共26分)2. 集合结构线性结构树结构图结构3. 0(n)4. 0(1)0(1)5. 7226

23、. 943 XY* + 2Y*3/-7. 2i+l2i+2(i-l)/28. 孩子(或子)结点 双亲(或父)结点9. 45 n(n-l)10. 先进后出先进先出11. 邻接矩阵邻接表边集数组12. 尾首13. n/m3、 运算题(每题6分，共24分)1 . 线性表为:(90, 40, 78, 50, 34, 60)2 .当前序序列为ABKCDFGHIJ,中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如 下图4所示：(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)74.见图5。L La=(26.34,57,79,100) La=(57.79,10

24、0.34)(3)La=(79.34,57,26/00)2.前序遍历链式存储的二叉树。五、 编写算法(16分)bool Find(LNode* HL. ElemType &item)LNode* p=HL;if (p->data=item) return true;)else p=p->next;return false;)华东数据结构期考试卷及答案（三）第17页共5页参考答案（B ）卷数据结构（C ）课程 课程类别：名、限、任闭卷（1开卷（范围）（仅限课本）:考试日期：题号四五7V七八九十总分累分人 签名题分20304010100得分考生注意事项：1、本试卷共上页，总分10

25、0分,考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、 单选题（每题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->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3 .以下哪一个不是队列的基本运算？ （ A

26、）A.在队列第i个元素之后插入一个元素B.从队头删除一个元素C.判断一个队列是否为空D.读取队头元素的值4 .字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多 可以组成（B）个不同的字符串？A. 14B. 5C. 6D. 8A. 11 B. 35 C. 19图15 .由权值分别为3,862的叶子生成一棵哈夫曼树，它的带权路径长度为（B ）。以下68题基于图6.A. E> G F、A、C、D、B该二叉树结点的前序遍历的序:列为（CF、B、DD、G、FB. E、 A、 G CsD. E、 G、 As C、 D、 F、 BC. E、A、C、B、7 .该二又树结点的中序遍历的

27、序列为（AA. A、 B、 C、 D、 E、 G> FB. E、 A、 G、 C、 F、 B、 DC. E、A、C、B、D、G、FE. B、D、C、A、F、G、E8 .该二叉树的按层遍历的序列为（C）oB. E、A、Cx B、D、G、FD. E、 G、 A、 C、 D、 F、 BA. E G、 F、 A、 C、 D、 BC. E A、 G、 C、 F、 B、 D9 .下面关于图的存储的叙述中正确的是（B ）oA.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C.用邻接矩阵法存储图，占用的存储空间大

28、小与图中结点个数和边数都有关D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点 个数无关10 .设有关键码序列（q, g, m, z, a, n, p, x, h）,下面哪一个序列是从上述序 列出发建堆的结果?（B ）A. a, g, h, m, n, p, q, x, zB.a, g, m, h, q, n, p, x, zC. g, m, q, a, n, p, x, h, zD.h, g, m, p, a, n, q, x, z2、 填空题（每空1分，共26分）1 .数据的物理结构被分为顺序、链表、索引、散列一四种。2 .对于一个长度为n的顺序存储的线性表，在表头插入元

29、素的时间复杂 度为-0（n） ,在表尾插入元素的时间复杂度为一 0（1；二3 .向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是 p->next=HS;HS=p ；删除一个结点时，需要执行的操作是 HS=HS->next （假设栈不空而且无需回收被删除结点）。4 .对于一棵具有n个结点的二义树，一个结点的编号为i（lWiWn）,若它有左孩子则左孩子结点的编号为_2i,若它有右孩子，则右孩子 结点的编号为_2i+l,若它有双亲，则双亲结点的编号为i/2（或 i/2 ）5 .当向一个大根堆插入一个具有最大值的元素时，需要逐层一向上一 调整，直到被调整到一根位置为止。6 .表

30、示图的两种常用的存储结构为_邻接矩阵_、_邻接表7 .对于线性表(70, 34, 55, 23, 65, 41, 20)进行散列存储时，若选 用H (K) =K%7作为散列函数，则散列地址为。的元素有_1一个, 散列地址为6的有4个。8 .在归并排序中，进行每趟归并的时间复杂度为-0(n),整个排序 过程的时间复杂度为 0(nlog：n：1,空间复杂度为_0(n)。3、 运算题(每题10分,共30分)1 .写出下列中缀表达式的后缀形式:(1) 3X/(Y-2)+l(2) 2+X*(Y+3)答案：(1) 3 X *Y 2 -/I +(2) 2 X Y 3 + * +2 .试对图2中的二义树画出其

31、：(I)顺序存储表示的示意图；(2)二义链表存储表示的示意图。123456789答案：(1)：0123678910111213141516(2)：见图3所示3 .已知一个图的顶点集V和边集E分别为:V=1,2, 3,4, 5, 6,7;E=(1,2)3, (1,3)5, (1,4)8, (2,5)10, (2, 3)6, (3,4)15, (3, 5)12, (3,6)9, (4,6)4, (4,7)20, (5,6)18, (6, 7)25;按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依 次得到的各条边。答案：普里姆算法从顶点1出发得到最小生成树为：(1,(2) (1,3)

32、5， (1,4)8, (4,6)4,(2,5)10, (4,7)204、 阅读算法(每题10分,共20分)1. void AE(Stack& S)InitStack(S);Push(S,3);Push(S, 4);int x=Pop(S)+2*Pop(S);Push(S, x);int i, a5 = l, 5, 8,12,15);for(i=0;i<5;i+) Push(S, 2*ai);while(!StackEmpty(S) cout«Pop(S)«,;该算法被调用后得到的输出结果为：30 24 16 10 2 102. void ABC (BTNode

33、 *BT,int &cl,int &c2) if (BT !=NULL) ABC(BT->Cft,c 1 ,c2);cl+;if (BT->left=NULL&&BT->right=NULL) c2+;ABC(BT->right,c 1 ,c2);)/if该函数执行的功能是什么？答案：该函数的功能是：统计出BT所指向的二叉树的结点总数和叶子总数5、 编写算法(共10分)编写从类型为List的线性表L中将第i个元素删除的算法，(假定不需要对i 的值进行有效性检查,也不用判别L是否为空表。)void Delete(List& L, i

34、nt i)答案：void Delete(List& L, int i)(for (int j=i-l;j<L size-1; j+)L. listj>L. listCj+1;第 i 个元素的下标为 i-1L. size;)华东交大数据结构期考试卷及答案（四）一”蛇扑DIP孙DIP孙。眯辿S求蜜SH5与aB谡奥娈喀丝Te罪常七黑窕隐茶杰琪坦香R数据结构（C ）课程课程类别：堂、限、任闭卷（1开卷（范围）（仅限课本）：考试日期：2011-1 -12题号四五六七八九十总分累分人 签名题分20304010100得分考生注意事项：1、本试卷共上页，总分100分,考试时间120分钟。2

35、、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、选择题（每题2分，共20分）1、数据的四种存储结构是（A ）A,顺序存储结构、链接存储结构、索引存储结构和散列存储结构B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构D,顺序存储结构、树型存储结构、图型存储结构和散列存储结构2、若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后 一个结点，要使操作时间最少，下列选项中，应选择的存储结构是（C）A.无头结点的单向链表B.带头结点的单向链表C.带头结点的双循环链表 D.带头结点的单循环链表3、若元素

36、的入栈顺序为1, 2, 3., n,如果第2个出栈的元素是n,则输出的 第i （l<=i<=n）个元素是（D ）A. n-iB. n-i+1C. n-i+2D.无法确定4、若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二义树可能的形状是 （B ）A.树中没有度为2的结点 B.树中只有一个根结点C.树中非叶结点均只有左子树D.树中非叶结点均只有右子树5、下面程序段的时间复杂度为( C )for (int i=0;i<m;i+)for (int j=O;j<n;j+) ai j=i*j;A) 0(m2) B) 0(n2) C) 0 (m*n)D) 0 (m+n)6、 设

37、有一组关键字(19, 14, 23, 1, 6, 20, 4, 27, 5, 11, 10, 9),用散列 函数H(key)=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录 个数为(C ) A. 1B. 2C. 3 D. 47、指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r 在表中次序的程序段是(A) A. p->next=r； q->next=r->next； r->next=q： B. p->next=r； r->next=q： q->next=r->next； C. r->next=q； q

38、->next=r->next； p->next=r； D. r->next=q： p->next=r： q->next=r->next；8、一个对象序列的排序码为46, 79, 56, 38, 40, 84>,采用快速排序以位于最 左位置的对象为基准而得到的第一次划分结果为(C )。A) 38, 46, 79, 56, 40, 84B) 38, 79, 56, 46, 40, 84C) 40, 38, 46, 56, 79, 84D) 38, 46, 56, ?9, 40, 849、串的操作函数str定义为：int str(charts) cha

39、r *p-s； while (*p !='0' ) p+； return p-s； 则str( abcde")的返回值是(C)A. 3 B. 4 C. 5 D. 610、设已有m个元素有序，在未排好序的序列中挑选第m+1个元素，并且只经过 一次元素的交换就使第m+1个元素排序到位，该方法是(D )oA.折半排序B.冒泡排序C.归并排序D.简单选择排序得分评阅人二、填空题(每题2分，共30分)3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为(n+l)/2 )4、将一个递归算法改为对应的非递归算法时，通常需要使用(栈 )5、数据的链式存储结构的特点是借

40、助(指针)表示数据元素之间的逻辑关系。6、下面程序段的时间复杂度为(0(n)osum=l；for (i=0;sum<n;i+) sum+=l；5、给定一组数据6, 2, 7, 10, 3, 12以它构造一棵哈夫曼树，则树高为_5_, 带权路径长度WPL的值为_96_。6、假定一棵树的广义表表示为A （D （E, G）, H （I, J）,则树中所含的结点数 为7个，树的深度为_3，树的度为-2_o7、假定一个最大堆（大根堆）为（56, 38, 42, 30, 25, 40, 35, 20）,则依次 向它插入45和64两个元素后得到的最大堆为：64, 56, 42, 38, 45, 40,

41、 35, 20, 30, 25 8、在一个具有10个顶点的无向完全图中，包含有_45一条边，在一个具有n个 顶点的有向完全图中，包含有_n（n-l）条边。9、后缀算式79 2 30 +- 4 2 /*的值为_94。中缀算式（3+X*Y）-2*Y/3 对应的后缀算式为_3 XY* + 2Y*3/-o10、.由字符集（s, t, a, e, 1及其在电文中出现的频度构建的哈夫区树如图所示。已知某段 电文的哈夫曼编码为111000010100,请根据该哈夫哒树进行译码，写出原来的电文（eatst）。第21页共5页得分评阅人三、简答题（5题，共53分）1、己知某二义树的前序序列为EBADCFHGI ,

42、中序序列为 ABCDEFGHL请画出二叉树并写出它的后序序列。（构造出二叉树 7分，后序遍历3分，共10分）参考答案：后序序列:ACDBGIHFE二义树为：B) »EF评分标准：构造出二义树7分，后序遍历3分2、在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、3、1, 29, 画出插入关键码后的二义查找树。（5分）3、.要在的向量空间中建立两个栈stackl和stack2,请回答:应该如何设计这两个栈才能充分利用整个向量空间？（5分）若stackl的栈顶指针为topi, stack2的栈顶指针为top2,如果需要充分利用 整个向量空间，则：栈stack

43、l空的条件是：（）;（2分）栈stack2空的条件是：（）;（2分）栈stackl和栈stack2满的条件是：（）。（2分）答：（1）采用双向栈的形式，stackl的栈底设置在下标为0的元素上，stack2的栈底设置在下标为n-1的元素上。（2）topl=-l» top2=n, topl-l=top24、设有单链表类型定义如下： typedef struct node int data;struct node *next; *LinkList;阅读下列算法，并回答问题：void f (LinkList head, int A, int B) LinkList p二NULL;while

44、 (head !=NULL)if （head->data>A&&head->data<B）p=head;head=head->next;if （p !=NULL）printf（"%dn”, p->data）;（1）已知链表h如下图所示，给出执行f（h, 5, 8）之后的输出结果；（5分）简述算法f的功能。 （5分）答：（1）7（2）输出链表h中（若存在）最后一个大于A到小于B的值。5、 LinkList mynote（LinkList L）/L是不带头结点的单链表的头指针if（L&&L-next）q=L； L=L&g

45、t;next； p=L；SI：while（p >next） p=p >next；S2：p >next=q； q>next=NULL；return L： 请回答下列问题： （1）说明语句SI的功能：（2）说明语句组S2的功能;（3）设链表表示的线性表为（al,a2,an），写出算法执行后的返回值所 表示的线性表。答案：（1）查询链表的尾结点 （1分）（2）将第一个结点链接到链表的尾部，作为新的尾结点 -一（1分）（3）返回的线性表为（a2, a3, , an, al） （2分）得分评阅人四、程序编程题（每题10分，共10分）1、已知二义树的定义如下： typedef st

46、ruct node int data;struct node *lchild, *rchild;*Bitptr;编写递归算法求二义树的高度。函数原型为：int BiTreeHeight (Bitptrt)； 答：int BiTreeHeight (Bitptr t) if(!t) return 0;lh= BiTreeHeight (t->lchild);rh= BiTreeHeight (t->rchild);return lh>rh?lh+l:rh+l;)一W蛇 孙 圣舟。兴辿s£魁一廿坦田弗诞映 躯戮eE话震洋健本津实却物YWT部仲NYWS翅汞员.老蚓迎回教殳

47、，内城M钟知京看华东教数据结构课程据结构期考试卷及答案（五）试卷编号:(A)卷课程类别：必题号四五六七八九十总分累分人 签名题分2030103010XXXXX100得分XXXXX考生注意事项：1、本试卷共工页，总分100分,考试时间120分钟。2、考试结束看，考生不得将试卷、答题纸和草稿纸带出考场。一、选择题（每题2分，共20分）1、在一个链队列中，若f, r分别为队首、队尾指针,指结点的操作为（ ）（A） f->next=c； f=s（C） s->next=r； r=s2、下面程序的时间复杂度为（for（i=0;i<m;i+）(B) r->next=s； r=s(D)

48、 s->next=f； f=s )for(j=0;j<n;j+)AiQ=iwj；(A) O(M2)(B) O(N2)(C) O(M*N) (D) O(M+N)3、设高度为h的二叉树上只有度为0和度为2的结点，则此类二义树中所包含的结点数至少为：()(A) 2h(B) 2h-1(C) 2h+1(D) h+14、设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的 操作序列为()。(A) q=p->next： p->data=q->data； p->next=q>>next； free(q)：(B) q=p->next： q-

49、>data=p->data； p->next=q->next； free(q)：(C) q=p->next； p->next=q->next； free(q)：(D) q=p->next； p->data=q->data； free(q)；5、含N个顶点的连通图中的任意一条简单路径，其长度不可能超过()(D)N14, 18, 21, 36, 40, 10),则以20 )°(A) 1(B) N/2(C) N-16、设一组初始关键字记录关键字为(20, 15, 为基准记录的一趟快速排序结束后的结果为(7 7 H/A B c D/

50、10, 15, 14, 18,10, 15, 14, 18,10, 15, 14, 20,15, 10, 14, 18,20, 36,20, 40,18, 40,20,40, 2136, 2136, 2I36, 40, 21第27页共5页7、若在线性表中采用折半查找法查找元素，该线性表应该()o(A)元素按值有序(B)采用顺序存储结构(C)元素按值有序，且采用顺序存储结构(D)元素按值有序，且采用链式存储结构8、. n个节点的完全二叉树，编号为i的节点是叶子结点的条件是()o(A) i<n (B) 2"iv=n (C) 2*i+1 >n (D) 2*i>n9、如果只

51、想得到1024个元素组成的序列中的前5个最小元素，那么用()方法最快。(A)起泡排序(B)快速排序 (C)堆排序 (D)直接选择排序10、对于线性表(7, 34, 77, 25, 64, 49, 20, 14)进行散列存储时，若选用H(K) =K%7作为散列函数，则散列地址为0的元素有()个，(A)1(B)2(C)3(D)4二、填空题(每空2分，共30分)1、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 (1),在表尾插入元素的时间复杂度为(2) o2、设查找表中有100个元素，如果用二分法查找方法查找数据元素X,则最多需要比较 (3) 一次就可以断定数据元素X是否在查找表

52、中3、若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的 个数为 (4)o4、若一棵二义树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为M, 则左、右子树皆非空的结点个数为一(5)5、设数组data 0m作为循环队列SQ的存储空间(判断队列满，少用一个元素 空间)，front为队头指针，rear为队尾指针，则执行出队操作的语句为(6)06、设哈夫曼树中共有n个结点，则该哈夫曼树中有(7)个度数为1的结点。7、设一组初始记录关键字序列为(49, 38, 65, 97, 76, 13, 27, 50),则以d=4 为增量的一趟希尔排序结束后的结果为 (8) o8、队列的

53、插入操作在 (9) 进行,删除操作在(10) 进行。9、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。 typedef struct node int data; struct node wlchild; (11) ;)bitree; void createbitree(bitree *&bt) (scanf( "c"，&ch);if(ch=,#t)(12;else bt=(bitree*)malloc(sizeof(bitree);bt->data=ch;(13);createbitree(bt->rchild); )10、下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处 填上正确的内容。typedef struct