2023年专升本试题数据结构

7.图的Depth-FirstSearch（DFS）遍历思想实际上是二叉树（）遍历措施日勺推广。

《数据构造》专升本考试试题

（A）先序（B）中序（C）后序（D）层序

（2023年3月）8.在下列链队列Q中，元素a出队的操作序列为（）o

一、单项选择题（本大题共20小题，每题2分，共40分）

1.对于一种算法，当输入非法数据时，也要能作出对应於J处理，这种规定称为（）。

（A）对的性（B）可行性（C）强健性（D）输入性

2.设S为C语言的语句，计算机执行下面算法时，算法的时间复杂度为（）.(A)p=Q.front->next;p->next=Q.front->next;

for（i=n-l；i>=0；i一）(B)p=Q.front->next;Q.front->next=p->next;

for（j=0：j<i；j++）S；(C)p=Q.rear->next;p->next=Q.rear->next;

（A）m（B）0（nlgn）（C）0（n）（D）0（作）（D）p=Q->next;Q->next=p->next;

3.折半查找法合用于（）。9.Huffman树的I带权途径长度WPL等于（）

（A）有序次序表（B）有序单链表（A）除根结点之外日勺所有结点权值之和（B）所有结点权值之和

（C）有序次序表和有序单链表都可以（D）无限制（C）各叶了•结点附带权途径长度之和（D）根结点的值

4.次序存储构造的优势是（）。10.线索二叉链表是运用（）域存储后继结点的地址。

（A）利于插入操作（B）利于删除操作（A）Ichild（B）data（C）rchild（D）root

（C）利于次序访问（D）利于随机访问11.研究数据构造就是研究（）o

5.深度为k的完全二叉树，其叶子结点必在第（）层上。（A）数据日勺逻辑构造（B）数据的存储构造

（A）k-1（B）k（C）kT和k（口）1至k（C）数据H勺逻辑构造和存储构造（D）数据的逻辑构造、存储构造及其基本操作

6.具有60个结点口勺二叉树，其叶子结点有12个，则度为1的结点数为（）o12.算法分析的两个重要方面是（

(A)11(B)13(C)48(D)37

（A）空间复杂度和时间复杂度（B）对的性和简朴性

（C）可读性和文档性（D）数据复杂性和程序复杂性（

13.若一种线性表中最常用的操作是取第i个元素和我第i个元素的前趋元素，则采用（）（A）完全图（B）连通图（C）有回路（D）一棵树

存储方式最节省时间。二、填空题（本大题共20个空，每空2分，共40分）

（A）次序表（B）单链表（C）双链表（D）单循环链表1.逻辑构造决定了算法的,而存储构造决定了算法的o

14.在一种长度为n的次序表中，在第i个元素之前插入一种新元素时，需向后移动（）2.栈和队列都是一种的线性表，栈的插入和删除只能在进行。

个元素。3.线性表（a「a,a,）的次序存储构造1|',设每个单元的长度为L,元素3的存储地址LOC（a.）

（A）n-i（B）n-i+1（C）n-i-1（D）i为_______________________

15.非空的循环单链表head的尾结点p满足（）。4.已知一双向链表如下（指针域名为next和prior）：

（A）p->next=head（B）p->next==NULL

/

（C）p==NULL（D）p==head

16.一种栈的输入序列为：a,b,c,d,e,则栈的不也许输出的序列是（）o

(A)a,b,c,d,e(B)d,e,c,b,a

(C)d,c,e,a,b(D)e,d,c,b,a

现将P所指的结点插入到X和y结点之间，其操作环节为：；

17.设SUBSTR（S,i,k）是求S中从第i个字符开始的持续k个字符构成H勺子串口勺操作，则对

TS=<Beijing&Nanjing,，SUBSTR(S,4,5)=

(A)'ijing'(B)<jing&,(C)'ingNa'(D)'ing&N'5.n个结点无向完全图的的边数为,n个结点的生成树的边数

18.广义表（（a）,a）的表尾是（)o为C

(A)a(B)(a)(C)0(D)((a))6.已知一有向无环图如下：

19.在一棵具有5层的满二叉树中结点总数为（)o

(A)31(B)32(C)33(D)16

20.假如从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是

任意写出二种拓扑排序序列：、Q

7.已知二叉树H勺中序遍历序列为BCA,后序遍历序列为CBA,则该二叉树的先序遍历序列

2.给定表（19,14,22,15,20,21,56,10）＜.（6分）

为,层序遍历序列为o

（1）按元素在表中的次序，建立一棵二叉排序树。

8.数据的存储构造可用四种基本的存储措施表达，它们分别是o

9.在图形构造中，每个结点的前驱结点数和后续结点数可以。

10.写出带头结点的双向循环链表L为空表的条件o

11.哈夫曼树是其树的带权途径长度的二叉树。

（2）对（1）中所建立的二叉排序树进行中序遍历，写出遍历序列。

12.n个顶点的连通图至少有条边。

三、应用题（本大题共6小题，共40分）

1.设散列函数H（k）=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},规定用线性探测3.已知一维数组中的数据为（18,12,25,53,竺），试写出插入排序（升序）过程。并指出具

法处理冲突。（8分）有n个元素的插入排序的时间复杂度是多少？（6分）

（1）构造HASH表。

4.已知二叉树的先序遍历序列为ABCDEFGH,中序遍历序列为CBEDFAGH,画出该二叉树.

（2）分别求查找成功和不成功时的平均查找长度。（5分）

5.已知一网络的邻接矩阵如下，求从顶点A开始时最小生成树。（6分）

A006510000四、程序分析填空题(本大题共2小题，每题5分，共10分)

B600005300

C5000070021.函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。

D1570064

Eco3006co6intGetElem(LinkListL,inti,Elemtype*e){

F0000246oo

LinkListp；intj；

ABCDEF

p=L->next;j=l;

while(p&&j<i){

(1)；++j；

)

if(!pIIj>i)returnERROR;

*e=(2);

6.已知数据六个字母及在通信中出现频率如下表:

returnOK;

ABCDEI--

0.150.150.10.10.20.3

)

把这些字母和频率作为叶子结点及权值，完毕如下工作(9分，要有过程)。

2.函数ListDeletie_sq实现次序表删除算法，请在空格处将算法补充完整。

(1)画出对应的Huffman树。

intListDelete_sq(Sqlist*L,inti){