数据结构真题及答案.pdf

《数据结构真题及答案.pdf》由会员分享，可在线阅读，更多相关《数据结构真题及答案.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、是一个关键字的有序序列。7.在一个图中，全部顶点的度数之和是边数的 倍。8.假设有序表(15,21,33,46,58,80,8 7)中折半查找元素3 3 时，与关键字比较次查找成功。9.设哈希表长m=14,哈希函数H(key)=key MOD 11。表中已有4 个元素：0 1 2 3 4 5 6 7 8 9 10 11 12 13I I I 1 I is 13 8 16 1 18 4 1 I I r n r n假设用二次探测再散列处理冲突，关键字为4 9 的记录的存储位置是10.具有n 个顶点的无向完全图，有 条边。三、推 断 题（本大题共5小题，每 题1分，共5分）1.算法在执行时，对同样的

5、输入可以得到不同的结果。（）2.线性表的链式存储构造的内存单元地址肯定不连续。（）3.队列允许插入的一段成为队尾，允许删除的一端称为队头。（）4.拓扑排序是内部排序。（）5.树转换成二叉树，其根结点的右子树肯定为空。（）四、综 合 应 用 题（本大题共3小题，每 题5分，共15分）1.画出具有三个结点的二叉树的全部形态（不考虑数据信息的组合状况）。（5分）2.写出以下图的邻接矩阵，并写出其从V I 动身的深度优先搜寻遍历序列（5 分）3.将以下图所示的树转换成二叉树，并写出该二叉树的先序遍历序列。（5分）五、算 法 设 计（本大题共1小题，共10分）1.线性表承受链式存储构造，结点类型定义如下

6、，试编写一个算法，在带头结点的单链表L中，删除全部值为x 的结点。typedef struct LNodeElemType data;struct LNode next;LNode,*Linklist;07 数据构造 50分一、单 项 选 择 题（1 0 分，每 题 1 分）1.按二叉树的定义，具 有 3 个结点的二叉树有 种。（）A.3 B.4 C.5 D.62.假设一个栈的入栈序列是1,2,3,，n,其输出序列为pl,p2,p3.p n,假设p l=n,则 pi 为（）A.i B.n=i C.n-i+q D.不确定3.下面结论 是正切的。（）A.树的先根遍历序列与其对应的二叉树的先序遍历序

7、列一样B.树的后根遍历序列与其对应的二叉树的先序遍历序列一样C.树的先根遍历序列与其对应的二叉树的中序遍历序列一样D.以上都不对4.评价一个算法时间性能的主要标准是（）A.算法易于调试 B.算法易于理解C.算法的稳定性和正确性 D.算法的时间简单度5.线性表的挨次存储构造是一种 的存储构造。（）A.随机存取 B.挨次存取 C.索引存取 D.散列存取6.在挨次表中，只要知道,就可在一样时间内求出任一结点的存储地址。（）A.基地址 B.结点大小 C.向量大小 D.基地址和结点大小7.在中序线索二叉树中，假设某结点有右孩子，则该结点的直接后继是（）A.左子树的最右下结点 B.右子树的最右下结点C.左

8、子树的最左下结点 D.右子树耳朵最左下结点&一个栈的入栈序列是abcde,则栈的不行能输出序列是（）A.edcba B.decba C.dceab D.abcde9.广义表是线性表的推广，它们之间的区分在于（）A.能否使用子表 B.能否使用原子项C.表的长度 D.是否能为空10.假设一棵二叉树具有10个度为2 的结点，则该二叉树的度为0 的结点的个数是（）A.9 B.ll C.12 D.不确定二、填 空 题（每 空 1 分，共 1 0 分）1.挨次表中规律上相邻的元素的物理位置_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。2.在分块查找方法中，首先查找索引表，

9、然后再用挨次查找方法查找相应的3.安排排序的两个根本过程是4.在拓扑排序中，拓扑序列的第一个顶点必定是 为0的顶点。5.有n个结点的二叉链表中。其中空的指针域为,6.有 向 图 的 邻 接 表 表 示 适 于 求 顶 点 的。7.有向图的邻接矩阵表示中，第i _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _上非零元素的个数为顶点v i的入度。8.在树的 表示法中，求指定结点的双亲或祖先格外便利，但是求指定结点的孩子或其他后代可能要遍历整个数组。9.由五个分别带权值为9,2,3,5,1 4的叶子结点构成一棵哈夫曼树，该树的带权路径长度为1 0.具有n个顶点的有向图最

10、多有 条边。三、填空题（3 0分）1.写出头插法建立单链表的算法（5分）2.求单源最短路径（从源点0开头），要求写出过程。（5分）3.某二叉树的中序遍历序列：d f a e c h i后序遍历序列：f d b e h i c a（1）请构造出该二叉树；（3分）（2）写出前序遍历序列；2分）4.设查找的关键字序列 1 5,4,3 0,4 1 1 1,2 2,1。画出对应的二叉排序树。（5分）5.写出图的广度优先搜寻算法（用邻接表存储）（5分）6.线性表的关键字集合：1 9,1 4,2 3,0 1,6 8,2 0,8 4,2 7,5 5,1 1,1 0,7 9 散列函数为：H （k）=k%1 3,

11、承受拉链法处理冲突,并设计出链表构造。（5分）08 数据构造50分 一、单项选择题（1 0分，每 题1分）1.假设一个栈的输入序列为1,2,3,，n,输出序列的第一个元素是i,则 第i个输出元素 是（）A.i-j-1 B.i-j C.j-i+1 D.不确定的2.循 环 队 列 存 储 在 数 组 中，则入队的操作为（）A.rear=rear+1 B.rear=(rear+1 )mod(m-1)C.rear=(rear+l)mod m D.rear=(rear+1 )mod(m+1)3.二维 数 组 A 的每个元素是由6 个字符组成的串，其 行 下 表 i=0,1,，8,列下表j=l,2.10。

12、假 设 A 按行序为主序存储，元 素 A85的起始地址与当A 按列序为主序存储时的元素 的起始地址一样。(设每个字符占一个字节)()A.A85 B.A310 C.A58 D.A094.下面说法不正确的选项是0A.广义表的表头总是一个广义表 B.广义表的表尾总是一个广义表C.广义表难以用挨次存储构造 D.广义表可以是一个多层次的构造5.算术表达式A+B*C-D/E转为前缀表达式后为0A.-A*C/DE B.-A+B*CD/E C.-+ABC/DE D.-+A*BC/DE6.有n 个叶子的哈夫曼树的结点总数为0A.不确定 B.2n C.2n+1 D.2n-17.假 设 X 是中序线索二叉树中一个有

13、左孩子的结点，且X 不为根，则X 的前驱为()A.X的双亲 B.X的右子树中最左的结点C.X的左子树中最右结点 D.X的左子树中最右叶结点8.无向图 G=(V,E),其中 V=a,b,c,d,e,f,E=a,b),a,e,at c.b.e,c,f,f,d,e,d ,对该图进展广度优先遍历，得到的顶点序列正确的选项是()A.a,b,e,c,d,f B.a,c,f,e,b,dC.a,e,b,c,f,d D.a,e,d,f,c,b9.假定有k 个关键字互为同义词，假设用线性探测法把这k 个关键字存入散列表中，至少要进展 探测。()A.k-1 次 B.k 次 C.k+1 次 D.k(k+1)/2 次1

14、0.以下排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是()A.直接插入排序 B.快速排序 C.直接选择排序 D.堆排序二、填 空 题(5分，每 题1分)1.在有序表AI1.12中，承受折半查找算法查等于A|12|的元素，所比较的元素下标依次为2.求图的最小生成树有两种算法，算法适合于求稀疏图的最小生成树。3.一棵左子树为空的二叉树在先序线索化后，其 中 的 空 链 域 的 个 数 为。4.在单链表L 中，指针p 所指结点有后继结点的条件是。5.一个深度为k,具有最少结点数的完全二叉树按层次，(同层次从左到右)用自然数依次对结点编号，则编号是i 的结点

15、所在的层次号是(跟所在的层次号规定为1层)。三、推 断 题(5分，每 题1分)1.链表是承受链式存储构造的线性表，进展插入、删除操作时，在链表中比在挨次存储构造中效率图。()2 .对一棵二叉树进展层次遍历时，应借助于一个栈。（3 .将一棵树转成二叉树，跟节点没有左子树。（）4 .一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）5 .在待排序数据有序的状况下，快速排序效果好。（）四、应 用 题（20分，每题5分）1 .用集合 4 6,8 8,4 5,3 9,7 0,5 8,1 0 1,1 0,6 6,3 4 建立一棵二叉排序树，画出该树，并求在等概率状况下的平均查找长度。2 .设一组关键字

16、 9,0 1,2 3,1 4,5 5,2 0,8 4,2 7 ,承受哈希函数：H （ke y）=ke ym o d 7和二次探测再散列法解决冲突，对该关键字序列构造表长为1 0 的哈希表。3 .假设用于通讯的电文仅由8个字母组成，字母在电文中消灭的频率分别为0.0 7、0.1 9、0.0 2、0.0 6、0.3 2、0.0 3、0.2 1、0.1 0,试为这8个数字设计哈夫曼编码。4 .用普里姆算法构造以下图的一棵最小生成树，并给出选点挨次。（以为起点）五、算法设计题（10分）编写一个算法来交换单链表中指针P所指接点与其后继结点，HEAD是该链表的头结点，P指向该链表中的某一结点。山东省202

17、2年一般高等教育专升本统一考试数据构造（5 0分）一、单项选择题（1（）分，每 题 1 分）1 .【答案】D【解析】栈的根本性质是后进先出，此题中，在输出序列第一个元素是i时，只 能 确 定 1-i-1 这些元素的输出的先后次序，但是不能确定出第i个元素具体输出哪个元素。2 .【答案】D【解析】在循环队列中，r e a r 指针指示队尾，此题中存储数组实质上为A m+1 。所以，入队列的操作应当是修改r e a r=（r e a r+l）%（m+l）,答案C是错误的。3.【答案】B【解析】此题中二维数组属于9行 1 0 列。所以，首先确定以行序为主序的存储中，A 8 5 在全部元素排列中的位置

18、为第8 5 位，同样确实定以列序为主序的第8 5 个存储元素的元素应当为A 3 1 0 。4.【答案】A【解析】构成广义表的数据元素可以是单个元素，也可以是广义表。广义表的表头就是广义表中的第一个元素，可以是单个元素，也可以是子表。选项B、C、D都是正确的。5.【答案】D【解析】在算数表达式的前缀表达式实质上就是运算符写在两个运算数的前面，固然在实现转换时，要考虑运算数的相对位置不变，而且考虑运算的优先级问题。固然，也可以采用二叉树表示出算数表达式，这样，前序遍历挨次即为前缀表达式（波兰式），后序遍历即位后缀表达式（逆波兰式），此题答案选D。6.【答案】D【解析】哈夫曼树的特点是没有度为1的结

19、点，依据二叉树的性质3,n0=n2+l,所以，具有n个叶子结点的二叉树具有n-l个度为2的结点，因此，答案选D。7.【答案】C【解析】由于在中序线索二叉树中，结 点X有左子树，所以，该结点前驱在左子树中，左子树中最右的结点是子树中最终一个遍历的结点，该结点可能为叶子结点，也可能是度为1的 结 点（即有左孩子）。8.【答案】A【解析】依据此题无向图的定义，可以图G如右图所示：、,依据广度优先遍历的算法思想，可以确定A是正确的，选项B、C、D都是错误的。9.【答案】D【解析】实行线性探测法存储这k个同义词，则第一个关键字可以直接存储，其 余 的k-1个元素中，抱负的状况下，第1个元素探测1次可以存

20、储，第2个元素探测2次才能存储，以此类推，因此，至少需要探测的次数为k（k+l）/2。10.【答案】B【解析】直接插入排序的算法思想是从第2到最终一个元素，依次插入到前面的有序序列中,因此，每趟执行完毕，不能确定出一个元素最终的位置：快速排序的每趟可以确定出枢轴元素的最终位置，而且，当元素根本有序时，其排序性能会降低，所 以 选B o选 项C、D能符合第一条要求，但是其时间性能跟待排元素的序列无关。二、填 空 题（本大题共10小题，每 题1分，共10分）1.【答案】6、9、11、12【解析】依据有序表的折半查找的m id的取值为（low+high）/2,可以确定判定树的形态如下，10J 112

21、查 找 下 标 为1 2的元素时，先后要与下标为：6、9、11、1 2四个元素进展比较。2.【答案】克鲁斯卡尔（K r u ska l）【解析】求解最小生成树的算法主要有两种，普里姆算法（P rim）时间简单度为O （n2）,与网中的边数无关，因此适合于求边稠密的网的最小生成树；而克鲁斯卡尔（K ru ska l）算法时间简单度为O （e log e）,因此，适合于求边稀疏的网的最小生成树。3.【答案】2【解析】左子树为空，则根结点没有前驱，左孩子指针域为空，另外，根结点右子树中最终一个结点没有后继，右孩子指针域也为空，所以，该二叉树中空链域的个数为2。4.【答案】p-ne x t!=N U

22、L L （或文字说明“指针P所指结点的指针域不等于N U L L”）【解析】在单链表L中，指 针p所指结点有后继，前提是指针P所指结点的指针域不等于NULL,假设指针域默认为ne x t,则可以表示为“p-ne x t!=N U L L”。（注：NULL肯定是大写）L log z j+i5 .【答案】2【解析】深 度 为K的结点已经构成完全二叉树，所 以 前i个结点也为完全二叉树，所以依据性质4可以确定第i个结点的深度为L g 2 J+1。三、推 断 题（5分，每 题1分）1.【答案】V【解析】链式存储构造的线性表的优点就在于实现插入和删除操作时，不需要大量元素的移动，因此，比挨次存储构造中实

23、现插入删除操作效率高。2【答案】X【解析】实现二叉树的按层遍历时，应借助于一个队列作为关心构造。3【答案】V【解析】树转换为二叉树是依据的孩子兄弟表示法这种存储构造，树根没有兄弟，所以，一棵树转换成二叉树，对应二叉树根结点没有左子树。4【答案】X【解析】有向图的邻接表中结点的个数与逆邻接表中结点的个数是相等的，都等于图中全部顶点的入度和（或出度和）的值。5【答案】X【解析】就平均时间而言，快速排序目前被认为是最好的一种内部排序方法，但是，当待排序列根本有序时，快速排序将蜕化为冒泡排序，因此，排序效果反而降低。四、综合应用题（本大题共3小题，每 题5分，共1 5分）1-答：依据结点画出二叉排序的

24、过程如下图：等概率状况下，平均查找长度为：1 5*2+4*2+3*3+2*2+1*1)/1 0=3.22 .答：依据哈希函数和处理冲突的方法为二次探测再散列，构造哈希表如下图:0 1 2 345 67891 4 1 9 2 3 84 2 7 5 5 2 0【解析】留意关键字的挨次,9%7=2;1%7=1;2 3%7=2,冲突，但是(2+1 2)%1 0=3;1 4%7=0;5 5%7=6;2 0%7=6,冲突，但是(6+1 2)%1 0=7;84%7=0,冲突，但是(0+1 2)%1 0=1,已经占用，由于函数值己经是0 了，在这里不能再摸索-1 2,因此(0+2 2)%1 0 必,所以8 4

25、 存储在下标4的单元格内。最 终 2 7%7=6,冲 突,(6+1 2)%1 0=7,仍旧冲突,(6-1 2)%1 0=5,所 以 2 7 存储在下标5的单元格内。3 .答：依据每个字符消灭的频率，我们可以求解哈夫曼树，为便利求解，不妨将频率变为整数，则权值分别为：7,1 9,2,6,3 2,3,2 1,1 0,由此构造哈夫曼如图：由此可以设定每个字符的哈夫曼编码：0.0 2：0 0 0 0 0：0.0 3:0 0 0 0 1;0.0 6:0 0 0 1;0.0 7:0 0 1 0;0.1:0 0 1 1;0.3 2:0 1;0.1 9:1 0;0.2 1:1 1.4 .答:依据普里姆算法构造

26、最小生成树，如以下图所示：五、算法设计(本大题共1 小题，共1()分)答：Linklist exchange(Linklist&head,Linklist p)q=head-next;pre=head;/初始化q、pre指针，当q 指针移动到与P 指针相等时，贝！Ipre指针正好指向前驱结点；while(q!=NULL&q!=p)pre=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

27、年一般高等教育专升本统一考试计算机科学与技术专业综合二试卷参考答案数据构造(50分)一、单项选择题(每题1分，共 10分)1.【答案】C【解析】具有三个结点的二叉树的形态共有5 种，而具有三个结点的树的形态是2 种。2.【答案】C【解析】假设输出的第一个元素为n,则全部元素均已经入栈，所以出栈挨次即为元素的逆序排列，因此，输出的第i 个元素的值为n-i+L3.【答案】A【解析】依据树与二叉树的相互转换数关系，以及树及二叉树的遍历挨次，有以下结论：(1)树的先根遍历挨次与对应二叉树的先序遍历挨次一样；(2)树的后根遍历挨次与对应二叉树的中序遍历挨次一样。4.【答案】D【解析】算法的时间性能的评价

28、主要使用算法的时间简单度，算法的空间性能的评价主要承受空间简单度。5.【答案】A【解析】线性表的挨次存储构造要求安排连续的存储空间，因此，可以实现数据元素的顺序存取以及随机存取。但元素的插入和删除需要涉及大量元素的移动；而线性表的链式存储便利于元素的插入与删除，但是不能实现随机存取，只能进展挨次存取。6.【答案】D【解析】挨次表要求存储空间是连续，所以，只要知道基地址，知道每个元素所占的字节数，就可以求每个元素的存储起始地址。7.【答案】D【解析】在中序线索二叉树中，假设某结点有右子树，则在访问完该结点后要访问右子树中最左边的结点，所以答案选D。8.【答案】C【解析】栈的根本性质是后进先出，在

29、入栈序列为a b cd e,出栈的第一个元素为d时，则己经入栈，所以，此 时“abc”三个元素的出栈序列中，肯 定 是c b a的挨次，而不能消灭cab的挨次，所以选项C是错误的。9.【答案】A【解析】构成广义表的数据元素可以单个元素，也可以是由假设干个元素所组成的子表。广义表属于特别的线性表，特别的地方在于广义表的元素中能否使用子表。10.【答案】B【解析】依据二叉树的根本性质3,对于任意一棵二叉树，满足度为0的结点为度为2的结点数加1。所以，答案选B二、填 空 题（本大题共10小题，每 题1分，共10分）1.【答案】肯定相邻【解析】挨次表承受连续存储空间作为元素的存储构造，所以，规律上相邻

30、的数据元的物理存储空间也肯定相邻。2.【答案】块【解析】在索引挨次表中，将全部的关键字进展分块，块与块之间关键字大小有序，在每个块内部元素排列无序，可以把每个组中最大元素值作为该组的索引参加到索引表中排列，所以，索引表中元素排列是有序的，因此，在查找元素时，先查找索引表，获得查找元素所在组后，再使用挨次查找去查找相应的块。3.【答案】安排和收集【解析】安排法排序属于一种典型的多关键字排序，安排排序的根本思想是排序过程无须比较关键字，而是通过“安排”和“收集”过程来实现排序。4.【答案】入度【解析】拓扑排序每次都选择没有前驱的结点进展输出，其中结点没有前驱，即入度为0。5.【答案】n+1【解析】

31、二叉链表中，每个结点有2个指针域，具有n个结点的二叉链表一共有2 n个指针域，其中，除根结点外，每个结点需要一个指针来指向，所以空的指针域的个数为n+1。6.【答案】出度【解析】有向图的邻接表是指:全部顶点建立顶点结点，以每个顶点为弧尾的全部弧对应的另外一个顶点序号构成表结点链接形成的单链表。所以，通过计数每个单链表中表结点的个数，可以计算每个顶点的出度。7 .【答案】列【解析】有向图的邻接矩阵的特点是，通过求解每一行上1的个数，可以求解每个顶点的出度；通过求解每一列上1的个数，可以求解每个顶点的出度。无向图的邻接矩阵属于对称矩阵，每个顶点的度即为行或列上1的个个数。8 .【答案】双亲【解析】

32、树的表示方法一共有三种，双亲表示法、孩子表示法以及孩子兄弟表示法。其中双亲表示法为每个树中元素建立一个结点，包括存储数据元素本身，以及该结点的双亲结点的存储下标，所以，该存储方法可以很简洁的求解结点的双亲以及祖先，但是求解结点的孩子及后代需要遍历整个数组。树的带权路径长度为:(2+3)*4+5*3+9*2+1 4*1=671 0 .【答案】n(n-l)【解析】在 有 n 个顶点的有向完全图中，从每个顶点出去的弧有n-1 条，所以总弧数为n(n-l)。四、综 合 题(3 0 分，每 题 5 分)1 .答：viod crea t(L inklist&L)L=(L inklist)ma lloc(s

33、iz eof(L node);L-next=N U L L;for(i=n;i0;i+)p=(L inklist)ma lloc(siz eof(L node);sca nf(&p-da ta);p-next=L-next;L-next=p;留意：除了使用头插法，还有尾插法，可以查阅资料写出算法。2 .答：求顶点0其余各顶点的最短路径11 0(0,1)/2OO60(0,1,2)50(0,3,2)/33 0(0,3)3 0(0,3)/41 0 0(0,4)1 0 0(0,4)90(0,3,4)60(0,3,2,4)添加顶点1323.答：依 据（1）中序遍历的特点：左子树、根、右子树的遍历挨次；（

34、2）后序遍历的特点：左子树、右子树、根：（3）二叉树的每棵子树也符合该特性。所以，该二叉树的构造过程为：由此可得到二叉树的前序遍历挨次为：a b dfceih5.答：该邻接表的构造描述如下：#define V E R T E X.M AX 1 0 0typedef struct nodeint a djvex;struct node*next;E dgenode;表结点的类型定义typedef struct vnodevextype vertex;E dgenode*firstedge;V ertexN ode;顶点结点的类型定义T ypedef struct V ertexN ode a d

35、jlist V E R T E X JIAX ;int n,e;顶点数和边数 AL G ra ph;邻接表的类型定义void BF S(AL G ra ph*G)for(v=0;vn;v+)visited v=F AL S E;InitQ ueue(Q)；for(v=0;vn;v+)if(!visited v)visited v=T U R E;P rintf(,G-a djlist v.vertex);E nQ ueue(Q,v)while(!Q ueueE mpty(Q)DeQ ueue(Q,u)；for(p=G-a djlist u.firstedge;p;p=p-next)if(!vi

36、sited p-a djvex)visited p-a djvex=T R U E;P rintf(,G-a djlist p-a djvex.vertex);E nQ ueue(Q,p-a djvex);)6.答：依据哈希函数以及拉链法解决冲突，构造如下哈希表：0123456891011山东省2 0 2 2 年一般高等教育专升本统一考试数 据 构 造（50 分）一、单项选择题（每题1 分，共 1 0 分）1 .【答案】D【解析】全部能输入到计算机中的符号的总称为数据，数据元素是构成数据的根本单位，数据元素可以由假设干条记录组成，每条记录又可由假设干数据项组成。一样性质的数据元素的集合构成数据

37、对象。数据元素的类型称为数据类型。2 .【答案】B【解析】承受挨次存储构造的线性表在进程插入和删除元素时需要涉及大量元素的移动问题。而链式存储构造可以很简洁的实现插入和删除操作，因此选B。3 .【答案】D【解析】假 设 9作为第一个出栈元素，前提是3,5,7已经依次入栈了，所以，此时输出挨次只能为9,7,5,3。选项D是错误的。4 .【答案】D【解析】字符串的长度应当是串中全部包含的字符的个数，所以选项A 只提到了字母，选项 B提到了不同字符的个数，均是错误的，每个字符串都属于自己的子串，因此选项C错误。5 .【答案】D【解析】广义表的表头是广义表中的头元素，广义表的表尾是指除去表头元素，其余

38、元素所组成的广义表，因此，答案选D而不是C,更不是A和B。6 .【答案】A【解析】图的生成树是指包含图中全部的n个顶点，但仅包含连通这个n个顶点的n-1 条边。7 .【答案】C【解析】依据二叉树的根本性质3：对于任意一棵二叉树满足n O=n 2+I,所以，当度为2的结点数为8时，叶子结点个数为9。8 .【答案】A【解析】在二叉链表中每个结点有两个指针域，而除了根结点外，每个结点均需要占用其中一个指针域，所以空的指针域个数为：2*n-(n T)=n+l个。9 .【答案】C【解析】在等概率的状况下，每个元素的查找概率都是1/n,其中查找最终一个元素需要比 较 1次，查找第n-1 个结点需要比较2次

39、，依次类推，查找第1个结点需要比较n次，平均查找长度为：(1+2+3+,)/n=(n+l)/2o1 0 .【答案】A【解析】对 含 有 n个元素的线性表，执行选择排序时，无论序列的初始排列如何，均需要进展 n-1 趟排序，每次都需要n-i 次比较，确定出第i个位置上的元素来，所以答案选A。而插入排序、冒泡排序当元素已经有序时，比较次数可以降低为n-1 次；快速排序当元素排列根本有序时，性能反而降低。二、填空题(本大题共1 0 小题，每 题 1分，共 1 0 分)1 .【答案】f=r【解析】在循环队列中，分别用f指示队头，r指向队尾。所 以 当 f=r 时，表示队列中没有元素存在，通常当(r+I

40、)%m ax s i z e=f时，表示该循环队列已满。(以牺牲一个存储空间伟代价)。在此留意是“=，而不是。2 .【答案】1/2【解析】假设在长度为n的挨次表中插入元素时，插入位置有n+1 个，平均需要移动元素数 量 为(0+l +2+n)/(n+l)=n/2；当删除元素时，删除位置有n个，平均需要移动的元素个数为：(0+l+2+(n-l)/n=(n-l)/2 o都接近1/2 的元素个数。3 .【答案】3 8【解析】二位数 组 每 行 中 有 5 个 元 素，每 个 元 素 占 2个字节，因 此 LO C (3,2)=LO C(O,0)+(3*4+2)*2=3 84 .【答案】2 K-1【解

41、析】二叉树的根本性质2。5.【答案】e【解析】有向图的邻接表是以图中全部顶点作为头结点，将全部以该顶点为弧尾的弧生成表结点构成的。所以，表结点数与弧数是一一对应的。6 .【答案】中序【解析】二叉排序树中全部左子树中结点均比根结点的值小，所以右子树中结点值均比根结点的值大，假设左右子树不空，左右子树都满足该特性，所以二叉排序树的中序遍历挨次是由小到大的挨次排列的。7 .【答案】2【解析】无论在有向图还是在无向图中，每条边或弧在计算顶点的度时均被用过2次，所以，得到的顶点的度的和就是边数的2 倍。8 .【答案】3【解析】该有序表中包含7个元素，因此先与第4个元素进展比较，然后和第2 个元素进展比较

42、，最终和第3个元素进展比较，所以共需要比较3次成功。9.【答案】9【解析】依据哈希函数求得函数值为5,查找觉察冲突，依据二次探测再散列，分别将函数值+12、-12、+22、-2 z,并对表进步行取余，进展摸索。所以答案填9。10.【答案】n(n-l)/2【解析】在 有 n 个顶点的无向完全图中，从每个顶点出去的边有n T 条边，但每条边被用过 2 次，所以总边数为n(n-1)/2。三、推断题(本大题共5 小题，每 题 1 分，共 5 分)1.【答案】X【解析】算法的特性包含确定性。确定性就是指每条指令必需是确定的含义，不能产生二义性，并且，在任何条件下，算法只有唯一的一条执行路径，即对一样的输

43、入只能得出一样的输出。2.【答案】X【解析】线性表的链式存储构造的存储单元地址不要求连续，但是可以连续；而线性表的挨次存储构造肯定要求安排连续的存储单元。3.【答案】V【解析】队列属于特别的线性表，要求在表的一端进展插入，在表的另一端进程删除，能够插入的一端称为队尾，能够删除的一端称为对头。4.【答案】X【解析】内部排序指的是待排记录存放在计算机随机存储器中进展的排序过程，外部排序指的是待排记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进展访问的排序过程。拓扑排序不属于内部排序。5.【答案】V【解析】一棵树转化为二叉树，其根结点肯定没有右孩子，即该二叉树没有右子树。只有2

44、 棵及以上的非空树组成的森林转化为二叉树，才能使得对应二叉树有右子树。四、综合应用题(本大题共 3 小题，每题 5 分，共 15 分)1,答：具有三个结点的二叉树共有5 种根本形态，具体如以下图所示：VI-V4-V5-V2-V3 或 VI-V2-*V5-V4-V3 或 VI-V3-*V2-*V5-*V4 或 VI-V3-*V4-*V5-V23.答：树转换为二叉树为：其中该二叉树的先序遍历挨次为A,B,C,E,F,G,D五、算法设计答：L i n k l i s t L i n k l i s t(本大题共1小题，共10分)d el ete(L i n k l i s t&L,E l em ty

45、 p e x)p,q;q=L;p=L-n ex t;w h i l e(p!=N U L L)i f (p-d a ta=x)初始化P指向第一个结点，q始终指向P结点的前驱;/找到符合条件的结点;q-n ex t=p-n ex t;f r ee(p);p=q-n ex t;删除该结点，并修改P指针;el s eq=p;p=p-n ex t;/先使q后移，p向后移动。06c语言程序设计 50分六、单项选择题(在每题的四个备选答案中，选出一个正确的答案，并将其号码填写在题干后面的括号内。每 题1分，共15分)1.C语言程序的根本单位是()A.程序行 B.语句 C.函数 D.字符2.可用作C 语言用

46、户标识符的一组字符串是()A.void define WORD B.a3_b3 _123 IF C.For abc Case D.2a DO sizeof3.设inta=12,则执行完语句a+=a-=a*a后，a 的 值 是()A.552 B.264 C.144 D.-2644.以下表达正确的选项是()A.do-while语句构成的循环不能用其它语句构成的循环来代替。B.do-while语句构成的循环只能用break语句退出。C.用 do-while语句构成的循环，在while后的表达式为非零时完毕循环。D.用 do-while语句构成的循环，在while后的表达式为零时完毕循环。5.设有说明

47、int(*ptr)10其中的标识符ptr是()A.10个执行整型变量的指针B.指 向 10个整型变量函数指针C.一个指向具有10个整型元素的一维数组的指针D.具 有 1 0 个指针元素的一维指针数组，每个元素都只能指向整型量6.有以下程序段typedef structNODE(int num;struct NODE*next;OLD;则以下表达中正确的选项是()A.以上的说明形式非法 B.NODE是一个构造体类型C.OLD是一个构造体类型 D.OLD是一个构造体变量7.以下不能正确计算代数式值的C 语言表达式是()A.l/3*sin(l *sin(l/2)B.sin(0.5)*sin(0.5)

48、/3C.pow(sin(0.5),2)/3 D.l/3.0*pow(sin(1.0/2),2)8.C语言规定，程序中各函数之间()A.既允许直接递归调用也允许间接递归调用B.不允许直接递归调用也不允许间接递归调用C.允许直接递归调用不允许间接递归调用D.不允许直接递归调用允许间接递归调用9.在宏定义#define PI 3.14159中，用宏名P I代替一个()A.单精度数 B.双精度数 C.常量 D.字符串10.在 C 语言中，要求运算数必需是整型的运算符是()A.%B./C.=y)&(y=z)B.(x=y)AND(y=z)C.(x=y=z)D.(x=y)&(y=z)12.有以下程序段int

49、 k=0,a=3,b=4,c=5;k=ac?c:k;执行该程序段后，k 的 值 是()A.3 B.2 C.l D.013.假设定义char*s=NameAddressn ,则指针S所指字符串的长度为()A.19 B.15 C.18 D.说明不合法14.下述对C 语言字符数组的描述中错误的选项是()A.字符数组可以存放字符串B.字符数组中的字符串可以整体输入、输出C.可以在赋值语句中通过赋值运算符对字符数组整体赋值D.不行以用关系运算符对字符数组中的字符串进展比较15.设有如下的函数exam(floatx)printf(n%f”,x*x);则函数的类型为()A.与参数x 的 类 型 一 样 B.

50、是 void C.是 int D.无法确定七、阅读以下程序，写出其运行结果(每题5分，共25分)1、程序：main int i,j,x;for(i=l;i=4;i+)for(j=1 ；jv=4-i;j+)printf(“)；for(j=0;j0)switch(k)case 1:n+=k;case 2:case 3:n+=k;default:break;)k-；)printf(a%dn,n);)答案：3、程序：main int i,j,row,column,m;static int array33=100,200,300,28,72,-30,-850,2,6;m=array00;for(i=0;