2023年专升本试题数据结构

《数据结构》专升本考试试题（２0２3年３月）一、单项选择题（本大题共2０小题，每小题2分,共40分)１.对于一个算法,当输入非法数据时,也要能作出相应的解决，这种规定称为()。(A)对的性（B)可行性(C)健壮性(D)输入性２．设Ｓ为C语言的语句,计算机执行下面算法时,算法的时间复杂度为(）。ｆor(i＝ｎ－１;i＞=０；ｉ--)fｏr(j=０；ｊ＜i;j++)Ｓ；(A)n2(B)O(nlgｎ）（Ｃ)O(ｎ)(D）O(n2)3.折半查找法合用于(）。(A）有序顺序表（B)有序单链表（C）有序顺序表和有序单链表都可以(D）无限制４.顺序存储结构的优势是()。（A）利于插入操作(Ｂ)利于删除操作（C）利于顺序访问(D)利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。（A)ｋ-1(Ｂ）ｋ(C)k－１和k(Ｄ)1至k6.具有6０个结点的二叉树，其叶子结点有１2个，则度为1的结点数为(）。(A)１1(B）13（C)4８(D)377．图的Deptｈ-FｉrstSｅaｒcｈ(DFS）遍历思想事实上是二叉树（)遍历方法的推广。(A)先序(Ｂ）中序（C)后序(D）层序8．在下列链队列Q中,元素a出队的操作序列为（)。bbcd∧afrontrearＱ(A)p＝Ｑ．front->next；ｐ->next=Q.front－>ｎｅｘt;（B)p=Q．ｆronｔ->next；Ｑ.ｆroｎｔ－>nｅxt=p->ｎexｔ;(C)p＝Q.ｒeａr->ｎext;p->next＝Ｑ.rear->nｅxｔ;(D）p＝Ｑ->ｎext;Q->ｎｅxt=ｐ->next；9.Huffmaｎ树的带权途径长度WPL等于（)（A)除根结点之外的所有结点权值之和(Ｂ）所有结点权值之和（C）各叶子结点的带权途径长度之和(Ｄ)根结点的值10.线索二叉链表是运用（）域存储后继结点的地址。(A）ｌcｈilｄ(Ｂ）dａtａ（C）ｒchｉld(Ｄ)roｏt11.研究数据结构就是研究()。（A）数据的逻辑结构ﻩﻩ (Ｂ）数据的存储结构(C)数据的逻辑结构和存储结构(D）数据的逻辑结构、存储结构及其基本操作12.算法分析的两个重要方面是()。(A)空间复杂度和时间复杂度ﻩ(Ｂ）对的性和简朴性（Ｃ)可读性和文档性（D)数据复杂性和程序复杂性１３.若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用(）存储方式最节省时间。（A)顺序表(Ｂ）单链表 （C)双链表(D)单循环链表1４.在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时,需向后移动（)个元素。（A)n－iﻩ （Ｂ）n-ｉ+1 (C）n-i－1 （D)i15．非空的循环单链表heａd的尾结点p满足(）。(Ａ)p->neｘt=＝heaｄﻩﻩ（B)ｐ-＞nｅxt＝＝NULＬﻩﻩ（C）ｐ＝=ＮULＬﻩ ﻩ （D)p==head16．一个栈的输入序列为:a，b，ｃ,d,e，则栈的不也许输出的序列是（）。（A）ａ，b，c，d,e(Ｂ）ｄ,e,c,b,aﻩ （C)d，c，e，a，bﻩ(Ｄ)e,d,c,b,a17.设SUＢＳTR(S,i，ｋ)是求Ｓ中从第i个字符开始的连续k个字符组成的子串的操作,则对于Ｓ＝‘Beｉjiｎg&Ｎanjｉｎg’，ＳUBＳＴR（Ｓ,4,５)=()。（A）‘ijiｎg’(B)‘jing&’ （Ｃ)‘ｉngＮａ’ﻩ（D）‘ing&N’18．广义表(（a),a)的表尾是（)。（A)aﻩﻩ (B）（a) ﻩﻩ（Ｃ）()ﻩ （D)（(a)）１9．在一棵具有5层的满二叉树中结点总数为（）。（A）31 (B)32ﻩ (C）33 (D）２0．假如从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是（）。(A)完全图 （B）连通图ﻩ (C)有回路 ﻩ(Ｄ)一棵树二、填空题（本大题共２0个空,每空2分,共40分）逻辑结构决定了算法的,而存储结构决定了算法的。栈和队列都是一种的线性表,栈的插入和删除只能在进行。线性表（a1,a2,…,an）的顺序存储结构中,设每个单元的长度为Ｌ，元素ａi的存储地址LOC(ａi)为已知一双向链表如下(指针域名为ｎexｔ和ｐrｉor):yyxeep现将p所指的结点插入到x和y结点之间，其操作环节为：；;;；5.ｎ个结点无向完全图的的边数为，n个结点的生成树的边数为。6.已知一有向无环图如下：EBEBACDFG任意写出二种拓扑排序序列:、。7.已知二叉树的中序遍历序列为ＢCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。8.数据的存储结构可用四种基本的存储方法表达，它们分别是。9.在图形结构中,每个结点的前驱结点数和后续结点数可以。10.写出带头结点的双向循环链表L为空表的条件。11．哈夫曼树是其树的带权途径长度的二叉树。12.n个顶点的连通图至少有条边。三、应用题（本大题共6小题，共40分）1.设散列函数H(k)=k%13,设关键字系列为{22,1２，24,6，４5,7，8，13,２１}，规定用线性探测法解决冲突。(8分)（1）构造HASＨ表。(2）分别求查找成功和不成功时的平均查找长度。给定表（19,１4，22,15,20,2１,56，１0）。(６分）按元素在表中的顺序，建立一棵二叉排序树。对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。已知一维数组中的数据为（18，１2，25,53,18），试写出插入排序（升序)过程。并指出具有ｎ个元素的插入排序的时间复杂度是多少？(6分)已知二叉树的先序遍历序列为ＡBCDEFGH，中序遍历序列为ＣＢＥDFAＧＨ,画出该二叉树。（５分)已知一网络的邻接矩阵如下，求从顶点Ａ开始的最小生成树。（6分)ABＣDEF6．已知数据六个字母及在通信中出现频率如下表:ABＣＤEＦ0.15０.15０.10．1０.20.3把这些字母和频率作为叶子结点及权值，完毕如下工作（9分，要有过程）。（1)画出相应的Huffman树。（2)计算带权途径长度ＷPL。(3）求Ａ、Ｂ、C、Ｄ、E、Ｆ的Hｕｆfｍａn编码。四、程序分析填空题(本大题共2小题,每小题５分，共１0分)1．函数GｅtElem实现返回单链表的第ｉ个元素,请在空格处将算法补充完整。 intGeｔEleｍ(LinｋLisｔL,ｉnti,Ｅlemtｙpｅ*e）｛ ﻩLiｎkListp；inｔj；p=L->ｎext;j＝1; ﻩwhｉle(ｐ＆&j＜i){ (1);++j;}iｆ(!p|｜j＞ｉ）reｔｕrｎERROR；*e=（2);rｅturnOＫ;}2．函数ListDｅlete_sq实现顺序表删除算法,请在空格处将算法补充完整。iｎtListDeｌetｅ＿ｓq(Ｓqlｉsｔ*L，inti){intｋ;ｉf（i<1||i>L－>lｅngｔh)ｒeturnERRＯＲ；for(k=i－1;ｋ<L-