06-09数据结构真题及答案.docx

《06-09数据结构真题及答案.docx》由会员分享，可在线阅读，更多相关《06-09数据结构真题及答案.docx（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、06数据构造5。分一、单项选择题(在每题的四个备选答案中，选出一个正确的答案，并将其号码 填写在题干后面的括号内。每题1分，共10分).数据的根本单位是)A.数据项B.数据类型C数据对象D.数据元素.假设频繁的对线性表进展插入和删除操作，那么该线性表应当承受 存储构造。()A.挨次 B.链式 C散列D.任意.假设进栈序列为3, 5, 7, 9,进栈过程中可以出栈，那么不行能的出栈次序是)A.7, 5, 3, 9B.9, 7, 5, 3C.7, 5, 9, 3D.9, 5, 7, 34,下面的说法中，正确的选项是1 )A.字符串的长度指串中包含的字母的个数B.字符串的长度指串中包含的不同字符的个

2、数C. 一个字符串不能说是其自身的一个子串D.假设T包含在S中，那么T肯定是S的一个子 串5.广义表Ua, b),c, d)的表尾是)A.dB.c, d Cc, d) D. ( c, d)6 .n个顶点的连通图，其生成树有 条边。()A.n-1B.nC.n+1 D,不确定7 .假设一棵二叉树有8个度为2的结点，那么该二叉树的叶节点个数为1)A.7B.8C.9 D.不确定8 .在有n个节点的二叉链表中有 个空链域。)A.n+1B.nC.n-1D.不确定9 .在等概率的状况下，承受挨次插查找法查找长度为n的线性表，平均查找长度为)A.nB.n/2C.(n+l)/2D.(n-l)/210 .以下排序

3、方法中，排序的比拟次数与序列的初始排列状态无关的是()A.选择排序B.插入排序C.冒泡排序D.快速排序二、填空题(本大题共10小题，每题1分，共10分)假定一个挨次队列的队首和队尾分别为f和r,那么推断队空的条件为 c1 .在挨次存储的线性表中插入或删除一个元素平均约移动表中 的元素。2 .设有一个二维数组A54,按行序优先存储，A的存储地址是10,每个数组元素占2个字节，那么A2的存储地址是 o3 .深度为k的二叉树至多有 个结点。位21.在有n个结点，e条边的有向图的邻接表中有 个表结点。4 .对一棵二叉树进展 遍历时，得到的结点序列是一个关键字的有序序列。5 .在一个图中，全部顶点的度数

4、之和是边数的 倍。8假设有序表(15, 21, 33, 46, 58, 80, 87)中折半查找元素33时，与关键字比拟 次查找成功。9.设哈希表长m=14,哈希函数H(key尸key MOD 11。表中已有4个元素:0 1 2 3 45678 9 10 11 12 1315386184五、算法设计（本大题共1小题，共10分）答：Linklist exchange（Linklist &head,Linklist p） q=head-next;pre=head; 初始化q、pre指针，当q指针移动到与P指针相等时，贝ijpre指针正好指向前 驱结点；while（q! =NULL&q! =p） p

5、re=q;q=q-next;if（p-next=NULL） printf（“p 无后继结点n）;else q=p-next;/利用q、pre p三个指针联合实现当前结点与前驱结点的交换；pre-next=q;p-next=q-next;q-next=p;）山东省2022年一般高等教育专升本统一考试计算机科学与技术专业综合二试卷参考答案数据构造（50分）一、单项选择题每题1分，共10分）1 .【答案】C【解析】具有三个结点的二叉树的形态共有5种，而具有三个结点的树的形态是2种。2 .【答案】C【解析 1假设输出的第一个元素为n,那么全部元素均已经入栈，所以出栈挨次即为元素的逆序排列，因此，输出的

6、第i个元素的值为n-i+1。3 .【答案】A【解析】依据树与二叉树的相互转换数关系，以及树及二叉树的遍历挨次，有以下结论：门树的先根遍历挨次与对应二叉树的先序遍历挨次一样；（2）树的后根遍历挨次与对 应二叉树的中序遍历挨次一样。4 .【答案】D【解析】算法的时间性能的评价主要使用算法的时间简单度，算法的空间性能的评价主要 承受空间简单度。5 .【答案】A【解析】线性表的挨次存储构造要求安排连续的存储空间，因此，可以实现数据元素的顺 序存取以及随机存取。但元素的插入和删除需要涉及大量元素的移动；而线性表的链式存 储便利于元素的插入与删除，但是不能实现随机存取，只能进展挨次存取。6 .【答案】D【

7、解析】挨次表要求存储空间是连续，所以，只要知道基地址，知道每个元素所占的字节 数，就可以求每个元素的存储起始地址。7 .【答案】D【解析】在中序线索二叉树中，假设某结点有右子树，那么在访问完该结点后要访问右子树 中最左边的结点，所以答案选D。8 .【答案】C【解析】栈的根本性质是后进先出，在入栈序列为abcde,出栈的第一个元素为d时，那么已 经入栈，所以，此时“ abc三个元素的出栈序列中，肯定是cba的挨次，而不能消灭cab 的挨次，所以选项C是错误的。9 .【答案】A【解析】构成广义表的数据元素可以单个元素，也可以是由假设干个元素所组成的子表。 广义表属于特别的线性表，特别的地方在于广义

8、表的元素中能否使用子表。10 .【答案】B【解析】依据二叉树的根本性质3,对于任意一棵二叉树，满足度为0的结点为度为2的 结点数加1。所以，答案选B二、填空题（本大题共10小题，每题1分，共10分）1 .【答案】肯定相邻【解析】挨次表承受连续存储空间作为元素的存储构造，所以，规律上相邻的数据元的物 理存储空间也肯定相邻。2 .【答案】块【解析】在索引挨次表中，将全部的关键字进展分块，块与块之间关键字大小有序，在每 个块内部元素排列无序，可以把每个组中最大元素值作为该组的索引参加到索引表中排列， 所以，索引表中元素排列是有序的，因此，在查找元素时，先查找索引表，获得查找元素 所在组后，再使用挨次

9、查找去查找相应的块。3 .【答案】安排和收集【解析】安排法排序属于一种典型的多关键字排序，安排排序的根本思想是排序过程无须 比拟关键字，而是通过“安排”和“收集”过程来实现排序。4 .【答案】入度【解析】拓扑排序每次都选择没有前驱的结点进展输出，其中结点没有前驱，即入度为0o 5.【答案】n+1【解析】二叉链表中，每个结点有2个指针域，具有n个结点的二叉链表一共有2n个指针 域，其中，除根结点外，每个结点需要一个指针来指向，所以空的指针域的个数为n+1。 6.【答案】出度【解析】有向图的邻接表是指:全部顶点建立顶点结点，以每个顶点为弧尾的全部弧对应的 另外一个顶点序号构成表结点链接形成的单链表

10、。所以，通过计数每个单链表中表结点的个数，可以计算每个顶点的出度。7 .【答案】列【解析】有向图的邻接矩阵的特点是，通过求解每一行上1的个数，可以求解每个顶点的 出度；通过求解每一列上1的个数，可以求解每个顶点的出度。无向图的邻接矩阵属于对 称矩阵，每个顶点的度即为行或列上1的个个数。8 .【答案】双亲【解析】树的表示方法一共有三种，双亲表示法、孩子表示法以及孩子兄弟表示法。其中 双亲表示法为每个树中元素建立一个结点，包括存储数据元素本身，以及该结点的双亲结 点的存储下标，所以，该存储方法可以很简洁的求解结点的双亲以及祖先，但是求解结点 的孩子及后代需要遍历整个数组。9 .【答案】67o【解析

11、】【解析】O图为五个权值形成的哈夫曼树，树的带权路径长度为:(2+3)*4+5*3+9*2+14*1=67.【答案】n(n-l)【解析】在有n个顶点的有向完全图中，从每个顶点出去的弧有n-1条，所以总弧数为 n(n-l) o四、综合题(30分，每题5分1 . 答：viod creat (Linklist &L)L=(Linklist)malloc(sizeof (Lnode);L-next=NULL;for (i=n;i0;i+) p=(Linklist)malloc(sizeof (Lnode); scanf(&p-data);p-next=L-next;L-next=p;) 留意：除了使用

12、头插法，还有尾插法，可以查阅资料写出算法。2 .答：求顶点0其余各顶点的最短路径110(0,1)/2OO60(0, 1,2)50(0, 3, 2)/330(0, 3)30(0, 3)/4100(0, 4)100(0, 4)90(0, 3, 4)60(0, 3, 2, 4)添加 顶点132.答：依据（1中序遍历的特点：左子树、根、右子树的遍历挨次；2）后序遍历的特 点：左子树、右子树、根；3）二叉树的每棵子树也符合该特性。所以，该二叉树的构造 过程为：.答：该邻接表的构造描述如下：#define VERTEX_MAX 100typedef struct nodeint adjvex;struct

13、 node *next; Edgenode;表结点的类型定义 typedef struct vnodevextype vertex;Edgenode *firstedge; VertexNode;顶点结点的类型定义Typedef struct VertexNode adjlistVERTEX_MAX;int n, e;顶点数和边数 ALGraph;邻接表的类型定义void BFS (ALGraph *G) for(v=0;vn;v+) visitedv=FALSE;InitQueue (Q)；for (v=0;vn;v+) if (!visitedv) visitedv=TURE;Printf

14、( %cv , G-adjlistv. vertex);EnQueue(Q, v)while (!QueueEmpty (Q) DeQueue (Q, u)；for (p=G-adjlistu. firstedge;p;p=p-next) if (!visitedp-adjvex) visitedp-adjvex=TRUE;Printf( , G-adjlistp-adjvex. vertex); EnQueue (Q, p-adjvex);).答：依据哈希函数以及拉链法解决冲突，构造如下哈希表：山东省2022年一般高等教育专升本统一考试数据构造（50分）一、单项选择题每题1分，共10分.【答

15、案】D【解析】全部能输入到计算机中的符号的总称为数据，数据元素是构成数据的根本单位， 数据元素可以由假设干条记录组成，每条记录又可由假设干数据项组成。一样性质的数据 元素的集合构成数据对象。数据元素的类型称为数据类型。1 .【答案】B【解析】承受挨次存储构造的线性表在进程插入和删除元素时需要涉及大量元素的移动问 题。而链式存储构造可以很简洁的实现插入和删除操作，因此选B。2 .【答案】D【解析】假设9作为第一个出栈元素，前提是3, 5, 7已经依次入栈了，所以，此时输出 挨次只能为9, 7, 5, 3o选项D是错误的。3 .【答案】D【解析】字符串的长度应当是串中全部包含的字符的个数，所以选项

16、A只提到了字母，选 项B提到了不同字符的个数，均是错误的，每个字符串都属于自己的子串，因此选项C错 误。4 .【答案】D【解析】广义表的表头是广义表中的头元素，广义表的表尾是指除去表头元素，其余元素 所组成的广义表，因此，答案选D而不是C,更不是A和B。5 .【答案】A【解析】图的生成树是指包含图中全部的n个顶点，但仅包含连通这个n个顶点的n-1条 边。6 .【答案】C【解析】依据二叉树的根本性质3：对于任意一棵二叉树满足n0=n2+l,所以，当度为2的 结点数为8时，叶子结点个数为9。7 .【答案】A【解析】在二叉链表中每个结点有两个指针域，而除了根结点外，每个结点均需要占用其中一个指针域，

17、所以空的指针域个数为：2*n-(nT)=n+1个。8 .【答案】C【解析】在等概率的状况下，每个元素的查找概率都是1/n,其中查找最终一个元素需要 比拟1次，查找第n-1个结点需要比拟2次，依次类推，查找第1个结点需要比拟n次， 平均查找长度为：(1+2+3+,) /n= (n+l)/2o.【答案】A【解析】对含有n个元素的线性表，执行选择排序时，无论序列的初始排列如何，均需要进 展n-1趟排序，每次都需要n-i次比拟，确定出第i个位置上的元素来，所以答案选Ao而 插入排序、冒泡排序当元素已经有序时，比拟次数可以降低为n-1次；快速排序当元素排列 根本有序时，性能反而降低。二、填空题(本大题共

18、10小题，每题1分，共10分).【答案】f二r【解析】在循环队列中，分别用f指示队头，r指向队尾。所以当f二二r时，表示队列中没 有元素存在，通常当(r+l)%maxsize=f时，表示该循环队列已满。(以牺牲一个存储空间 伟代价)。在此留意是“ = = ，而不是。1 .【答案】1/2【解析】假设在长度为n的挨次表中插入元素时，插入位置有n+1个，平均需要移动元素 数量为(0+1 + 2,+n) /(n+l)=n/2；当删除元素时，删除位置有n个，平均需要移动的元 素个数为：(0+l+2+,+ (n-1) /n=(n-1)/2。都接近1/2的元素个数。2 .【答案】38【解析】 二位数组每行中

19、有5个元素，每个元素占2个字节，因此L0C (3,2) =L0C(0, 0) + (3*4+2)*2=38.【答案】2K -1【解析】二叉树的根本性质2。3 .【答案】e【解析】有向图的邻接表是以图中全部顶点作为头结点，将全部以该顶点为弧尾的弧生成 表结点构成的。所以，表结点数与弧数是一一对应的。4 .【答案】中序【解析】二叉排序树中全部左子树中结点均比根结点的值小，所以右子树中结点值均比根 结点的值大，假设左右子树不空，左右子树都满足该特性，所以二叉排序树的中序遍历挨 次是由小到大的挨次排列的。5 .【答案】2【解析】无论在有向图还是在无向图中，每条边或弧在计算顶点的度时均被用过2次，所 以

20、，得到的顶点的度的和就是边数的2倍。6 .【答案】3【解析】该有序表中包含7个元素，因此先与第4个元素进展比拟，然后和第2个元素进展比拟，最终和第3个元素进展比拟，所以共需要比拟3次成功。7 .【答案】9【解析】依据哈希函数求得函数值为5,查找觉察冲突，依据二次探测再散列，分别将函 数值+12、-12, +22、-22,并对表进步行取余，进展摸索。所以答案填9。8 .【答案】n(n-l)/2【解析】在有n个顶点的无向完全图中，从每个顶点出去的边有nT条边，但每条边被用 过2次,所以总边数为n(nT)/2。三、推断题(本大题共5小题，每题1分，共5分).【答案】X【解析】算法的特性包含确定性。确

21、定性就是指每条指令必需是确定的含义，不能产生二 义性，并且，在任何条件下，算法只有唯一的一条执行路径，即对一样的输入只能得出一 样的输出。1 .【答案】X【解析】线性表的链式存储构造的存储单元地址不要求连续，但是可以连续；而线性表的 挨次存储构造肯定要求安排连续的存储单元。2 .【答案】V【解析】队列属于特别的线性表，要求在表的一端进展插入，在表的另一端进程删除，能 够插入的一端称为队尾，能够删除的一端称为对头。3 .【答案】X【解析】内部排序指的是待排记录存放在计算机随机存储器中进展的排序过程，外部排序 指的是待排记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存 进展访问

22、的排序过程。拓扑排序不属于内部排序。4 .【答案】V【解析】一棵树转化为二叉树，其根结点肯定没有右孩子，即该二叉树没有右子树。只有2棵及以上的非空树组成的森林转化为二叉树，才能使得对应二叉树有右子树。四、综合应用题(本大题共 3 小题，每题 5 分，共 15 分.答：具有三个结点的二叉树共有5种根本形态，具体如以下列图所示：.答：I 1 0 0 0 o如图为该图的邻接矩阵。从VI动身的深度优先遍历挨次为1 0 0 0 1L0 1 o 1 o jV1-V4-V5-V2-V3 或 Vlf V2f V5-V4f V3 或 Vlf V3f V2f V5f V4 或 Vlf V3f V4f V5fV21

23、 .答:树转换为二叉树为：其中该二叉树的先序遍历挨次为A, B, C, E, F, G, D五、算法设计(本大题共1小题，共10分)答：Linklist delete(Linklist &L, Elemtype x) Linklist p, q;q=L; p=L-next;初始化p指向第一个结点，q始终指向p结点的前驱;while (p!二NULL) if (p-data=x)q-next=p-next;free (p);找到符合条件的结点;p=q-next; )p=q-next; )删除该结点，并修改P指针;elseelseq=p：p=p-next;q=p：p=p-next;先使q后移，p向

24、后移动。06C语言程序设计50分六、单项选择题(在每题的四个备选答案中，选出一个正确的答案，并将其号码 填写在题干后面的括号内。每题1分，共15分).C语言程序的根本单位是1 )A.程序行B.语句 C.函数D.字符.可用作C语言用户标识符的一组字符串是)A.void define WORD B.a3_b3_123 IF C.For abc Case D.2a DO sizeof.设inta=12,那么执行完语句a+二a-二a*a后，a的值是()A.552B.264C.144D.-264.以下表达正确的选项是()A.do-while语句构成的循环不能用其它语句构成的循环来代替。B. do-whi

25、le语句构成的循环只能用break语句退出。C.用do-while语句构成的循环，在while后的表达式为非零时完毕循环。D.用do-while语句构成的循环，在while后的表达式为零时完毕循环。5 .设有说明int ptr10其中的标识符ptr是()A.10个执行整型变量的指针B.指向10个整型变量函数指针C.一个指向具有10个整型元素的一维数组的指针D.具有10个指针元素的一维指针数组，每个元素都只能指向整型量.有以下程序段typedef structNODEint num;struct NODE *next;OLD;那么以下表达中正确的选项是)A.以上的说明形式非法B.NODE是一个构

26、造体类型C.OLD是一个构造体类型D.OLD是一个构造体变量6 .以下不能正确计算代数式值的C语言表达式是()A.l/3*sin(l/2)*sin(l/2)B.sin(0.5)*sin(0.5)/3C.pow(sin(0.5),2)/3D. l/3.0*pow(sin( 1.0/2),2)8c语言规定，程序中各函数之间)A.既允许直接递归调用也允许间接递归调用B. 不允许直接递归调用也不允许间接递归调用C. 允许直接递归调用不允许间接递归调用D.不允许直接递归调用允许间接递归调用9 .在宏定义#definePI3.14159中，用宏名PI代替一个()A.单精度数B.双精度数C.常量D.字符串假

27、设用二次探测再散列处理冲突，关键字为49的记录的存储位置是.具有n个顶点的无向完全图，有 条边。三、推断题（本大题共5小题，每题1分，共5分）.算法在执行时，对同样的输入可以得到不同的结果。（）1 .线性表的链式存储构造的内存单元地址肯定不连续。（）.队列允许插入的一段成为队尾，允许删除的一端称为队头。（）2 .拓扑排序是内部排序。）.树转换成二叉树，其根结点的右子树肯定为空。）四、综合应用题（本大题共3小题，每题5分，共15分）.画出具有三个结点的二叉树的全部形态（不考虑数据信息的组合状况）。5分）1 .写出以下列图的邻接矩阵，并写出其从VI动身的深度优先搜寻遍历序列5分）.将以下列图所示的

28、树转换成二叉树，并写出该二叉树的先序遍历序列。（5分）五、算法设计（本大题共1小题，共10分）.线性表承受链式存储构造，结点类型定义如下，试编写一个算法，在带头结点的单链表L 中，删除全部值为x的结点。typedef struct LNode1().在C语言中，要求运算数必需是整型的运算符是(A.%B./C.=y)&(y=z)B.(x=y)AND(y=z)C.(x=y=z)D.(x=y)&(y=z).有以下程序段int k=0,a=3,b=4,c=5;k=ac?c:k;执行该程序段后，k的值是1)A.3B.2C.lD.0.假设定义char *s= NameAddressn ，那么指针s所指字符

29、串的长度为()A.19B.15C.18D.说明不合法.下述对C语言字符数组的描述中错误的选项是(A.字符数组可以存放字符串B.字符数组中的字符串可以整体输入、输出C.可以在赋值语句中通过赋值运算符对字符数组整体赋值D.不行以用关系运算符对字符数组中的字符串进展比拟12 .设有如下的函数exam(floatx) printf( n%f,x*x);)那么函数的类型为()A.与参数x的类型一样B.是voidC.是int D.无法确定七、阅读以下程序，写出其运行结果(每题5分，共25分)1、程序：main int i,j,x;for(i=l;i=4;i+)for(j=l;j=4-i;j+)printf

30、( )；for(j=0;j0)switch(k)case 1: n+=k;case 2: n+二k; default: break;)k-；)printf( u%dn ”,n);)答案：3、程序：main int ij,row,column,m;static int array33= 100,200,300,28,72,-30,-850,2,6;m=array00;for(i=0;i3;i+)for(j=0;j3;j+)if(arraylij程序#includeint p(int k,int a) int m,i,c=0;for(m=2;m=k;m+)for(i=2;im;i+)if(!(m%

31、i) break;if(i= =m) ac+=m;)return c;)#define MAXN 20mainint i,m,slMAXNJ;m=p(13,s);for(i=0;ib的关系运算结果是。9 .假设定义int a10;那么允许数组a的下标值最小可以是。五、请写出以下程序的运行结果(此题10分，每题2分)l.main int n=100;if(n100)printf* “; elseprintf( # )； ).main int a=2,bl,c=2; if(ab)if(b0)c=0;else c+=l;printf( uc=%dn ”,c);.main char s= u stud

32、entOteacher u;printf( u%sn ,s);.main int a=3,b=4;printf( a=%d,b=%dn ”,+a,b+);.main static int a5,i;for(i=0;i5;i+)ai=ai+i;for(i=0;i5;i+)printf( d,六、单项选择题(此题10分,每题2分)l.main int k=l 1;printf( k=%d,k=%o,k=%xn ”,k,k,k);Ak= ll,k=l 2,k= 11B k= 11 ,k= 13,k= 13 Ck= 1 l,k=013,k=0xb Dk= 11 ,k= 13,k=b2 .main in

33、t y=10;while(y);printf( y=%dn ,y);)A.y=10; B.y=lC.y=随机值D.y=-13 .main int a,b,*pl,*p2;pl=&a;p2=&b;*pl=100;*p2=2O0;c=*pl+*p2; printf( dn ”,c);A.300B. 100+200C.100D.200.在以下程序中，当执行到gets(ss)；语句时，假设输入字符为“ABC”时，那么该程序的输 出结果是：main char ss10= 12345stract(ss, u6789 )；gets(ss);printf( u%sn ”,ss);)A.ABC B.ABC9 C

34、.123456ABCD.ABC456789.main chara= umorning ”,t;int i,j=();for(i=l;i7;i+)if(ajai)j=i;t=aj;aj=a7;a7=t;puts(a);)A.mogninr B.mo C.morningD.mornin七、编程题(10分，每题5分)1 .请将以下一组数据读入到S数组中，并从中找出最小的值并输出。30, 56, 88, 45, 100, 20.请将以下给出的字符串读入到ss数组中，并输出该字符串。Student and TeacherElemType data;struct LNode *next;LNode,*Li

35、nklist;07数据构造50分一、单项选择题（10分，每题1分）1 .按二叉树的定义，具有3个结点的二叉树有 种。A.3B.4C.5D.62 .假设一个栈的入栈序列是1, 2, 3,.，n,其输出序列为pl, p2, p3,.，pn,假设 pl=n,那么 pi 为（）A.iB.n=iC.n-i+qD.不确定3 .下面结论 是正切的。）A.树的先根遍历序列与其对应的二叉树的先序遍历序列一样B.树的后根遍历序列与其对应的二叉树的先序遍历序列一样C.树的先根遍历序列与其对应的二叉树的中序遍历序列一样D.以上都不对4 .评价一个算法时间性能的主要标准是（）A.算法易于调试B.算法易于理解C算法的稳定

36、性和正确性D.算法的时间简单度5 .线性表的挨次存储构造是一种 的存储构造。）A.随机存取B.挨次存取C.索引存取D.散列存取6 .在挨次表中，只要知道,就可在一样时间内求出任一结点的存储地址。（）A.基地址B.结点大小C.向量大小D.基地址和结点大小7 .在中序线索二叉树中，假设某结点有右孩子，那么该结点的直接后继是（）A.左子树的最右下结点B.右子树的最右下结点C.左子树的最左下结点D.右子树耳朵最左下结点8 .一个栈的入栈序列是abcde,那么栈的不行能输出序列是（）A.edcbaB.decba C.dceab D.abcde9 .广义表是线性表的推广，它们之间的区分在于）A.能否使用子

37、表B.能否使用原子项C.表的长度D.是否能为空10 .假设一棵二叉树具有10个度为2的结点，那么该二叉树的度为。的结点的个数是A.9B.ll C.12D.不确定二、填空题（每空1分，共10分）L挨次表中规律上相邻的元素的物理位置 o2 .在分块查找方法中，首先查找索引表，然后再用挨次查找方法查找相应的3 .安排排序的两个根本过程是4 .在拓扑排序中，拓扑序列的第一个顶点必定是 为（）的顶点。5 .有n个结点的二叉链表中。其中空的指针域为 o6 .有向图的邻接表表示适于求顶点的。7 .有向图的邻接矩阵表示中，第i 上非零元素的个数为顶点vi的入度。8 .在树的 表示法中，求指定结点的双亲或祖先格

38、外便利，但是求指定结点的孩子或其他后代可能要遍历整个数组。9,由五个分别带权值为9,2,3,5,14的叶子结点构成一棵哈夫曼树，该树的带权路径长度为10.具有n个顶点的有向图最多有 条边。三、填空题（30分）1 写出头插法建立单链表的算法（5分）2,求单源最短路径从源点（）开头），要求写出过程。（5分）3.某二叉树的中序遍历序列：dfaechi后序遍历序列：fdbehica（1） 请构造出该二叉树；（3分）（2） 写出前序遍历序列；（2分）4,设查找的关键字序列15,4,30,41,11,22,1。画出对应的二叉排序树。（5分）5 .写出图的广度优先搜寻算法（用邻接表存储）（5分）6 ,线性表

39、的关键字集合：19,14,23,01,68,20,84,27,55,11,10,79散列函数为：H （k） =k%13,承受拉链法处理冲突, 并设计出链表构造。（5分）08数据构造50分一、单项选择题（10分，每题1分）.1 .假设一个栈的输入序列为1, 2, 3,，n,输出序列的第一个元素是i,那么第i个输出元 素是A. i-j-1B.i-j C.j-i+1D.不确定的2 .循环队列存储在数组AO.m中，那么入队的操作为UA.rear=rear+1B .rear=（rear+ l）mod（m-l）C.rear=（rear+ l）mod mD.rear=（rear+ l）mod（m+1）.二维

40、数组A的每个元素是由6个字符组成的串，其行下表i=（）, 1,，8,列下表 j=l,2,，10。假设A按行序为主序存储，元素A8的起始地址与当A按列序为主序 存储时的元素 的起始地址一样。设每个字符占一个字节）（）A.A85B.A310C.A58D.A09.下面说法不正确的选项是（）A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用挨次存储构造D.广义表可以是一个多层次的构造.算术表达式A+B*C-D/E转为前缀表达式后为（）A-A*C/DE B.-A+B*CD/E C.-+ABC/DE D-+A*BC/DE.有n个叶子的哈夫曼树的结点总数为（）A.不确定B.2n C

41、.2n+1D.2n-1.假设X是中序线索二叉树中一个有左孩子的结点，且X不为根，那么X的前驱为（）A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点3 .无向图 G=（V, E）,其中 V=a, b, c, d, e, f, E=a, b, a, e, a, c, b, e, c, f, f, d, e, d,对该图进展广度优先遍历，得到的顶点序列正确的选项是1 ） A.a, b, e, c, d, fB.a, c, f, e, b, dC.a, e, b, c, f, dD.a, e, d, f, c, b4 .假定有k个关键字互为同义词，假设用线性探测法把这k个关键字存入散列表中，至少 要进展 探测。（）A.k-1 次 B.k 次 C.k+1 次 D.kk+1） /2 次5 .以下排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数 据初始特性影响的是）A.直接插入排序B.快速排序C.直接选择排序D.堆排序二、填空题（5分，每题1分）.在有序表AL.12中，承受折半查找算