华东交通大学-学年第一学期考试卷数据结构

k纪违试考道知22不k纪违试考道知22将分处上以及过

华东交通大学第一学期考试卷试卷编号：（A）卷构(课程类别（考试日期：记到

受弊作

因和籍学除开被将

考生注意事项：1、本试卷共页总分100分考试时间120分。、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。者考人他代或考代人他

题题分，分)1．以下不于算法要素的是（有穷性B.可行性C.可读性D.输入2．顺序表机访问元素a基本操作的时间复杂度为（1O(nC.logn)D.O(k)

得

评人请道知还，性重严的弊作、。果后切一的，起律引纪此场由考担守承遵愿格，严位将学我士：学诺予承授

3．图的广优先搜索算法中定义的辅助数据结构为（）A.队列B.栈C.邻接表D.二叉树4．求T在串S首次出现位置的基本操作叫做（）求子串B.模式匹配C.串替换D.串连接5．广义表L=(apple,pear),(banana,orange))的表尾是（）(apple,)B.((apple,pear)C.(banana,orange)D.(()6．n×n对称矩阵压缩存储到（）个元的空间中考范围之）nB.nC.n(n+1)D.7．在一棵有2009结点的完全二叉树中，叶子结点有（）个。1001B.C.1005D.8．由权值为7，1926，32，3，，10的结点构成的赫夫曼树的带权路径长度为（）271B.261C.241D.2319．有向图所有顶点的入度之和为n，则出之和为（）B.C.n-110在有序表(1,8,9,16,23)中折半查找关键字的比较次数是（）A.2B.3C.4D.5/

题空分，分)

得

评人1．线性表顺序表示称为_顺序表_。2．8个顶点的连通图最多有_边，最少有_7___条边。3．含9叶子结点的3阶B-树中至少有_非叶子结点考试范围外）4．广义表(()a,((b,),d)的深度为_3__。5．按低下优先存储整数数A9×3×5×8

时，1元素a的存储地址是0，每个整数40000字节，a的地址是____________考试范之外）31256．设S=‘IAMAWORKER!T=‘GOOD，Concat(SubString(6,2),Concat(SubString(S,7,))=

AGOOD

。7．总长的顺序循环队列中，队头指针为front，队指针为rear，队列满的件为______(rear+1)n=front____，队列空的条件为_front=rear__。8．下图中AOE-关键活动为

<A,B>__，，，<H,I。9．下图中有向图，从顶点A出发进行广度优先遍历的顶点序列为_ABCDEFGHI___。10p指向单链表L的中间结点的指针，补充下列删除p后继结点的程序段。

G

2s

B

1

8

I__p->nexet=s->next;____free();11程序段

A

6

4

C1

E

7

H

4for(i=0;i<n;)for(j=0;j<i;j++)k++;

5

D

2

F

4中，语句的执行次数为_。题题分，分)1．写出图所示的AOV网的个不同的拓扑序列。参考答：11，5，2，，6231，5，2，，3

得

评人5

4

1，5，6，，36/

2．画出和图中的森林对应的二叉树。A

H

J

M

IK

LN

OC

D

E

PF

G参考答：AB

HC

I

JD

K

MF

E

L

NG

O3．进栈序为ABC写出所有可能的出栈序列。参考答：可以通穷举所有可性来求：①A入A出，B出C入C出，即；②A入A出，B、、，即ACB③、B入，出，C入出，A出即BCA；④、B入，BA出C入出，即BAC⑤、、入，、B、出，即CBA；合计有可能性。4．按照四运算加、减、乘、除和幂运算(∧)的优先关系的惯例，将表达式A－＋∧F转换为前缀和后缀表式（试范围外）5．画3结点的二叉树的所有形态。5形态6．二叉树先序序列为，中序序列为CBAEDF，画出该二叉树。参考答：AB

DCE

F/4

i7．按下表关键字的顺序构造一棵二叉平衡树。i

（考试围之外）(5,1,9,2,10,)8选取哈希函数H(k)(3k)MOD11用开放地址法处理冲突d=i((7k)MOD10+1)(i1,3,在的散列地址空间中对关键字序列(53,30,67构造哈希表。参考答：01357891022674153461301题题分共)1．写一算，对带头结点的单链表L实现就地逆置。单链表结点