2023长春理工大学计算机809数据结构真题_长春理.docVIP

长春理工大学

2023年全国硕士研究生统一入学考试自命题试题

考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、选择题(每题

考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

一、选择题(每题2分，共30分)

求整数n（n=0）的阶乘如下，时间复杂度是( )

Intfact(intn){

If(n=1)return1;returnn*fact(n-1);

}

A.O(logn) B.O(n) C.O(nlogn) D.O(n*n)

单链表中，S插到P之后，语句是( )

S-next=p+1; p-next=S;

P-next=S; S-next=p-next;

S-next=p-next; p-next=s-next;

S-next=p-next; p-next=S;

入栈1，2，3，4，5，进栈合法的是( )

51234

45132

43125

32154

F是森林，B是F变换得到的二叉树，若F中有n个非叶子结点，则B中右指针域空的有（）个

n-1

n

n+1

n+2

分别以下列序列构造二叉排序树，与其他三个所构造结果不同的是( )

A.100 80 90 60 120 110 130

B.100 120 110 130 80 60 90

C.100 60 80 90 120 110 130

D.100 80 60 90 120 130 110

6.已知一棵完全二叉树，第六层有8个叶子结点，则该树结点个数最多为( )

A.39 B.111 C.52 D.119

有一组数据（15，9，7，8，20，-1，7，4）用快速排序进行排序，一趟后的结果为（）

BCD都不对

9，7，8，4，-1，7，15，20

20，15，8，9，7，-1，4，7

9，4，7，8，7，-1，15，20

某线性表采用顺序，每个元素占4个存储单元，首地址200，下标为12（下标从0开始）的元素的存储地址是（）

A.248 B.247 C.246 D.244

在表长为n时的单链表中，下列操作时间复杂度为O(n)的是（）

删除P结点的直接后继结点

P结点之后插入一个结点

删除表中的第一个结点

查找第i个结点

表达式a*(b+c)-d的后缀表达式是（）

abcd*+-

abc+*d-

abc*+d-

-+*abcd

二叉有哪些信誉好的足球投注网站树中一个新结点总是作为（）

最左下方结点

叶子节点

最右下方结点

根节点

串S=”abcdefgh”,其中子串个数为（）

A.9 B.36 C.37 D.8

已知二叉树前序为ABDCEFGHK，中序为BDAEFCHKG,则后序为（）

DBFEKHGCA

BDFEKHGCA

DBEFKHGCA

BDEFKHCGA

循环队列，队满的条件（）

(sq.rear+1)%maxsize==(sq.front+1)%maxsize

(sq.front+1)%maxsize==sq.rear

(sq.rear+1)%maxsize==sq.front

Sq.rear==sq.front

串是一种特殊的线性表，特殊在（）

可以顺序存储

数据元素可以是一个字符

可以链接存储

数据元素可以是多个字符

二、填空题（每空2分，共20分）

广义表（（a,b,c),d,e)的长度为

堆排序和快速排序中，在原始序列基本有序的情况下，选择哪个

n个结点的二叉树线索化后有 个线索（不计头结点）

用大小为10的数组实现循环队列，rear和front值分别是0，3，则队列中元素个数为

数据结构包括逻辑结构，存储结构和数据的 三个方面

具有n个顶点的图最多有 个连通分量

平均查找长度与个数n无关的查找方法是

左右括号是否匹配的算法，采用 的数据结构方法

在二叉树有哪些信誉好的足球投注网站树上实行 遍历后得到有序序列

待排序列46，79，56，38，40，84创建初始小根堆

三、综合应用题（共70分）

防控物资运输过程分解为9个事件，11项活动，其AOE图如下图所示。

A7=9A10=27

A7=9

A10=2

A1=61

A1=6

2

A4=1A5=15

A4=1

A5=1

9

A11=4

A11=4

A8=78

A8=7

A2=43A3=54A9=4A6=2

A2=4

3

A3=5

4

A9=4

①每个活动的最早和最晚开始时间

②有哪些关键活动

③完成本次防控物资运输至少需要几个事件

310，08，27，132，68，95，187，70，63，47

H(K)=(K)MOD13,使用链地址法