杭州电子科技大学数据结构2011-2019年考研专业课真题.pdf – 人人…(杭州电子科技大学排名全国第几位)

杭州电子科技大学

2019年攻读硕士学位研究生招生考试

《数据结构》试题

(试题共五大题，共6页，总分150分)

姓名报考专业准考证号

【所有答案必须写在答题纸上，做在试卷或草稿纸上无效！】

一、判断题(本大题共10小题，每小题1分，本大题共10分)

1.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。()

2.对任何数据结构链式存储结构一定优于顺序存储结构。()

3.循环队列通常用指针来实现队列的头尾相接。()

4.若栈的入栈序列为】,2,3,4,5,6,则其出栈序列可以是325,6,1,4.()

5.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。()

6.取广义表的表尾就是返回广义表中最后一个元素。()

7.稀疏矩阵压缩存储后，必会失去随机存取功能。()

8.关键路径是aoe网中从源点到终点的最长路径。()

9,对一棵二叉树进行层次遍历时，应借助于一个栈。()

10.在用弗洛伊德算法求解各顶点的最短路径时，每个表示两点间路径的

path”i[i,j]一定是pathk[ij的子集(k=l,2,3,….n)。()

二、单项选择题(本大题共15小题，每小题2分，本大题共30分)

1.从逻辑上.可以把数据结构分为()大类

a.动态结构、静态结构b.顺序结构、链式结构

c.线性结构、非线性结构d.初等结构、构造型结构

2.在一个二维数组a中，假设每个数组元素在长度为3个存储单元，行下标i

为0-8,列下标j为。?9,从首地址sa开始连续存放。在这种情况下，元素

a[8][5]的起始地址为()

a.sa+141b.sa+144c.sa+222d.sa+255

3.在双向链表指针p的结点前插入一个指针q的结点操作是()

a.p->llink=q;q->rlink=p;p->llink->rlink=q:q->llink=q;

b.p->llink=q;p->llink->rlink=q;q->riink=p;q->llink=p->llink;

c.q->rlink=p;q->llink=p->llink;p->llink->rlink=q;p->llink=q;

d.q->llink=p->llink;q->rlink=q;p->llink=q;p->llink=q;

4.在一个长为n的顺序表中删除第i个元素和第i个位置插入一个元素的时间复

杂度为()

a.nb.i-1c.n-id.n-i+1

第i页共6页

5.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是

（）

a.head=nullb.head—>next=nullc.head—>next=headd.head!=null

6.一个栈的输入序列为1,2,3,…,n,若输出序列的第一个元素是n,输出第i

（l<=i<=n）个元素是（）

a.不确定b.n-i+1c.id.n-i

7.设表头不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是

（）

a.只有表头结点指针，没有表尾指针的双向循环链表

b.只有表尾结点指针，没有表头指针的双向循环链表

c.只有表头结点指针，没有表尾指针的单向循环链表

d.只有表尾结点指针，没有表头指针的单向循环链表

8.若栈采用顺序存储方式存储，现两栈共享空间top[i]代表第i个栈（i

=1,2）栈顶，栈1的底在v[l],栈2的底在v[m],则栈满的条件是（）?

a.|top[2]-top[l]|=0b.top[l]+l=top[2]

c.top[l]+top[2]=md.top[lj=top[2]

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

a.abcd*+-b.abc+*d-c.abc*+d-d.-+*abcd

10.已知操作符包括”*”、ur\”（”和”）将中缀表达式a+b-a*（（c+d）/e-f）+g

转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放哲时还不能确定运算次

序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个

数是（）

a.5b.7c.8d.11

11.若将关键字1,2,3,4,5,6,7依次插入到初始为空的平衡二叉树r中，则r

中平衡因子为0的分支结点的个数是（）.

a.0b.1c.2d.3

12.设无向图g=（v,e）和g，=（v，，e）如果g，是g的生成树，则下面说法中错误的是

（）

a.g，是g的子图b.g，是g的连通分量

c.g，是g的极小连通子图且v=v，d.g，是g的一个无环子图

13.设给定权值总数有n个，其哈夫曼树的结点总数为（）

a.不确定b.2nc.2n+ld.2n-l

14.用相邻矩阵a表示图，判定任意两个顶点vi和vj之间是否有长度为m的

路径相连，则只要检查（）的第i行第j列的元素是否为零即可。

a.mab.ac.amd.am-1

第2页共6贞

15.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍

历得到的序列可能是（）

a.1354267b.1347652c.1534276d.1247653

三、填空题（本大题共15小题，每小题2分，本大题共30分）

1.n个顶点的连通图的生成树含有条边。

2.假定有k个关键字互为同义词，着用线性探测法把这k个关键字填入散列表

中，至少要进行次探测。

3.对序列｛98.36,-9,0,47,23,1,8,10.7｝采用增量为4的希尔排序，第一趟的排序结

果是0

4,一组记录的关键码是（46,79,56,38,40,84）,以第一个记录为基准，从

小到大得到的快速排序第一次划分结果是o

5.对数据序列（8,9,10,4,5,6,20,1,2）采用冒泡排序（从后向前升序

进行），需要进行趟完成排序。

6.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是o

7,已知一棵二叉树的层序排列是abcdef,中序序列为badcfe,则先序序列

为。

8.下图中的强连通分量的个数为_____个。

第3页共6页

9.已知字符集缶力凡(1?￡&11},若各字符的哈夫曼编码依次是0100,10,0000,

0101,001,011,11,0001,则编码序列0100011001001011110101的译码结果

是。

10.使用迪杰斯特拉(dijkstra)算法求下图中从顶点1到其他各顶点的最短路径,

依次得到的各最短路径的目标顶点是。

11.对于一个非连通无向图.共有28条边,则该图至少有个顶点。

12.n个顶点的无向图的邻接表最多有个表结点。

13.对n阶对称矩阵压缩存储时，需要表长为的顺序表。

14.若无向图g=(v,e)中含有7个顶点，要保证g在任何情况下都是连通的.则需要

的边数最少是条。

15.对下图进行拓扑排序，可以得到不同的拓扑序列的个数是。

第4页共6页

四、简答题(本大题共5小题，每小题8分，本大题共40分)

1.某带权有向图及其邻接表如f:

(1)写出从a点开始深度优先的访问序列(邻接边的顺序按邻接表链表顺序);

(2)画出深度优先生成树；

(3)该图为aoe网络，求顶点c的最早发生时间和及活动fc的最晚开始时间。

2.将关键字序列(7,8,30,11,18,9,14)散列存储到散列表中，散列表的

存储空间是一个下标从0开始的一位数组，散列函数为:h(key)=(key*3)

mod7,处理冲突采用线性探测再散列法，要求装填因子为0.7。

(1)请画出所构造的散列表。

(2)分别计算等概率情况下，查找成功和查找不成功的平均杳找长度。

3.设图g=(v,e)以邻接表存储，如图所示，画出其邻接矩阵以及图g。

4.设计一个算法，求出指定结点在给定二叉排序树中的层次。

节点结构:

structtree

(

intdata;

structtree*left;

structtree*right;

);

intfindlevel(treeroot,intdata)

第5页共6页

5.给定一个二叉树和其中的一个结点，请找出中序遍历顺序中该节点的下一个

结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的

指针。

节点结构如下:

structtreelinknode{

intval;

structtreelinknode*left;

structtreelinknode*right;

structtreelinknode*next;

treelinknode(intx):val(x),ieft(null),right(null),next(null){

}

};

treelinknode*getnext(treelinknode*pnode)

五、程序题(本大题共4小题，每小题10分，本大题共40分)

1.编写算法，实现在单向链表上删除具有重复值的多余节点，使得表中每个节

点的数值均保持不同。

2.假设?个算数表达式中包括圆括号()，方括号[],和花括号{},编写?个算法

来判别表达式中的括号是否配对，以字符’\0’作为算数表达式的结束符

boolbracketscheck(char*str)

3.已知图的邻接矩阵的存储结构说明为:

typedefstruct{

intvertex[m];

intedge[m];}gadjmatrix;

图的邻接表的存储结构说明为

typedefstructnodel{

intinfo;

intadjvertex;

structnodel*nextarc;}glinklistnode;

typedefstructnode2{

intvertexinto;

glinklistnode*firstarc;}glinkheadnode:

请设计计算法mattolist,将无向图的邻接矩阵转为对应的邻接表。

voidmattolist(gadjmatrixgl[],glinkheadnodeg2[]){

}

4.在n个元素中，找出第k大的元素，用c语言写出数据结构，设计算法实现

上述要求，并分析时间复杂性，最好是平均时间复杂性为o(n).

第6页共6页

杭州电子科技大学

2018年攻读硕士学位研究生招生考试

《数据结构》试题

(试题共五大题，共5页，总分150分)

姓名报考专业_____________准考证号

【所有答案必须写在答题纸上，做在试卷或草稿纸上无效！】

一、判断题(本大题共10小题，每小题2分，本大题共20分)

1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。()

2.单链表中设置的头结点只具有标识的作用。()

3.队列是一种能分别在表的两端进行插入与删除操作的线性表结构，具有先进后

出的特性。()

4.采用顺序存储方式存储，两个栈共享个存储区v[0..maxsizct],为提高空

间利用率，减少溢出的可能，应把两个栈的栈底分别设在向量空间的两端。()

5.哈夫曼树是带权路径长度最短的树，带权路径长度等于所有结点的权值之和。

()

6.一颗有n个结点的二叉树，采用链衣(uink-rlink)存储结构，则树中共有

n+1个空指针.()

7.强连通分量是无向图的极大强连通了?图。()

8.有向图和无向图可以采用邻接矩阵存储，但带权的有向图和无向图，不能采用

邻接矩阵存储，只能使用邻接衣存储。()

9.设t为一棵二叉平衡树，向树中插入一个结点n,然后立即删除该结点，则不

会破坏树的结构。()

10.归并排序在任何情况卜,都比所有简单排序速度快。＜)

二、单项选择题(本大题共10小题，每小题2分，本大题共20分)

1.下面关于算法说法正确的是().

a.算法最终必须由计算机程序实现

第i贞大5页

b.算法是对特定问题求解步骤的描述，是指令的有限序列，其中每一条指令表

示一个操作.

c.算法的可行性是指指令不能有二义性

d.以上几个都是错误的

2.下述哪一条是顺序存储结构的优点？（）。

a.存储密度大b.插入运算方便

c.删除运算方便d.可方便地用于各种逻辑结构的存储表示

3.设1、2、…、n-kn共n个数按顺序入栈，若第一个出栈的元素是n,则

第三个出栈的元素是

a.3b.n-2c.n-3d.任何元素均可能

4.若一棵二叉树具有7个度为2的结点，6个度为1的结点，则度为。的结点个

数是（）。

a.9b.8c.15d.不确定

5.一棵二叉树的前序遍历序列为abcdefg,它的中序遍历序列可能是（）.

a.cabdefgb.abcdefgc.dacefbgd.adcfeg

6.连通一个n个顶点的无向图，其边的个数至少为（）,如果是有向图则边

数至少为（）.

a.n-1,nb.n,n-lc.n*2-l,n*2d.n,n+1

7.已知有向图g=（v,e）,其中v=（v1,v2,v3,v4,v5,v6,v7,v8},

e=?v1,v2>,<v1,v4>,<v2,v7>,<v4,v7>,<v7,v8>,<v3,v4>,<v3,v5>,<v4,v6>,<v

5,v6>},下列哪个序列不是g的拓扑有序序列（）.

a.v1,v2,v3.v4,v5,v6,v7,v8b,v3,vi,v2,v4,v5,v6,v7,v8

c.v1,v3,v2,v4,v5,v6,v7,v8d.vi,v3,v4,v2,v5,v6,v7,v8

8.对线性表进行折半查找，表中元素的存储方式及元素排列要求为（）.

a.链接方式存储，元素无序b.链接方式存储，元素有序

c.顺序方式存储，元素无序d,顺序方式存储，元素有序

9.设哈希表长为15,哈希函数是h（key）=key%13,表中已有数据的关键字为15,

22,50,13,20,36,28,现要将关键字为48的结点加到表中，用二次探测再

散列法解决冲突，则放入的位置是（）.

第2页共5页

a.8b.3c.5d.9

10.对序列｛16,8,6,7,21,-2,4｝进行排序，进行一趟后数据的排列变为(4,

8,-2,7,21,6,16):则采用的是()排序.

a.选择b.快速c.希尔d.冒泡

三、填空题(本大题共15空，每空2分，本大题共30分)

1.元素总数基本稳定的线性表，采用存储结构，能在很少进行插入和删

除操作的情况下，以最快的速度存取表中元素.

2.长度为n的列表，被等分为n/k段，每段长度为k,不同段之间的元素不存在

逆序。对该列表进行插入排序的最坏时间复杂度为。

3.顺序栈用data[l..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作

是.

4.树在计算机内的表示方式有一(1)_,_(2)_,_(3)_。

5.一棵度为m的树有n个节点。若每个节点直接用m个链指向相应的儿子，则

表示这个树所需要的总空间是n*(m+l)(假定每个链以及表示节点的数据域都是

一个单位空间).当采用儿子/兄弟(firstchild/nextsibling)表示法时，所

需的总空间是.

6.设深度为d(只有一个根结点时，d为1)的二叉树只有度为。和2的结点，

则此类二叉树的结点数至少为.

7.如果一个完全二叉树最底下一层为第六层(根为第一层)且该层共有8个叶结

点，那么该完全二叉树共有一个结点。

8.g是一个非连通无向图，共有30条边，则该图至少有个顶点.

9.dijkstra短路径算法从源点到其余各顶点的短路径的路径长度按次序

依次产生，该算法弧上的权出现情况时，不能正确产生最短路径.

10.在一个大小为k的空散列表中，按照线性探测冲突解决策略连续插入散列值

相同的n个元素(n<k).问:此时，该散列表的平均成功查找次数是.

11.设用希尔排序对数组｛97,35,-10,0,48,22,1,8,9,7)进行排序，给

出的步长(也称增量序列)依次是4,2,1则排序需趟，写出第一趟

结束后，数组中数据的排列次序.

第3页共5页

四、简答题（本大题共5题，本大题共40分）

1.（本题5分）斐波那契数列fn定义如下:fo=o,fl=l,fn=fn-l+fn-2,

n=2,3…,如果用大0表示法，试给出递归计算fn时递归函数的时间复杂度是

多少.

2.（本题8分）假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自

左向右）为ecrahxms,中序序列为acehmrsxo请画出该二叉树，并将其转换为

对应的森林。

3.（本题8分）下图是带权的有向图g的邻接表表示法，求:

（1）以结点vi出发深度遍历图g所得的结点序列；

（2）从结点vi到结点v8的最短路径；

4.（本题10分）对输入关键字序列501,89,513,60,906,170,879,245,

653.460进行:

（1）建立堆排序的初始堆（小顶堆），要求画出主要过程.

（2）输出最小值后，如何得到次小值?（并画出相应结果图）

5.（本题9分）设一组数据为{1,13,27,30,56,70,9,12,23},现采用的哈希函数

是h（key）=keym0d13,即关键字对13取模，冲突用链地址法解决，设哈希表

的大小为13（0..12）,试画出插入上述数据后的哈希表。

第4页共5页

五、程序题（本大题共3题，本大题共40分）

l（本题10分）设单链表的表头指针为h,结点结构由data和next两个域构

成，其中data域为字符型。写出算法dc（h,n）,判断该链表的前n个字符是否中

心对称。例如xyx,xyyx都是中心对称。

2.（本题15分）在二叉树中查找值为x的结点，试编写算法（用c语言）打印

值为x的结点的所有祖先，假设值为x的结点不多于一个，后试分析该算法的

时间复杂度。

3.（本题15分）设有顺序n个盒子，每个盒子有一个小球，每个小球的颜色是

红，白，蓝之一。要求重新安排这些小球，使得所有红色小球在前，所有白色小球

居中，所有蓝色小球居后，重新安排时对每个小球的颜色只能看一次，并且只允

许交换操作来调整小球的位置。

第5页共5页

/

杭州电子科技大学

2011年攻读硕士学位研究生入学考试

《数据结构》试题

(试题共五大题，5页，150分)

姓名报考专业_______________准考证号

【所有答案必须写在答题纸上，做在试卷或草稿纸上无效！】

一、选择题(每小空2分，共28分)

1.在下列数据结构中具有先进先出特性，具有先进后出特性.

a:线性表b:栈c:队列d:串

2.如下关于串的陈述中，正确的是、.

a:串是数据元素类型特殊的线性表b:串中的元素是字母

c:串中若干个元素构成的子序列称为子串d:空串即为空格串

3.对广义表a=(((a),(b)),((c)))

执行操作gettail(gethead(gettail(a)))的结果是:.

执行操作gethead(gettail(gethead(a)))的结果是:.

a:()b:(())c:(a)d:(b)e:(c)

4.任何一个连通网的最小生成树.

a:只有一棵b:有一棵或多棵c:一定有多棵d:可能不存在

5.在有n个结点的二叉树的三叉链表表示中，空指针数为.

a:不确定b:nc:n+1d:n+2

6.关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点

的路径.

a:弧的数目最多b:弧的数目懒少c:权值之和最大d:权值之和最小

7.设无向图6=(丫鹏)和6=(v\e),若g,是g的生成树，

则下面不正确的说法是..

a:g.是g的子图b:g,是g的连通分量-

c:g是g的无环子图d:g,是g的极小连通子图且v’=v

8.下列查找方法中适用于查找单链表.

a:顺序查找b:折半查找c:分块查找d:hash查找

9.卜.列排序方法中，是稳定的；具有最好的平均性能:当恃排

序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中以

为佳.

a:堆排序b:快速排序c:直接插入排序d:简单选择排序

第i页共5页

二、填空题(每空2分，共26分)

1.数据结构通常有下列4类基本结构:线性结构、树型结构、图型结构、.

2.线性表的存储结构是以物理位置来表示数据元素之间的逻辑关系的.

而线性表的存储结构是通过指针保持数据元素之间的逻辑关系的.

3.n个顶点的强连通图至少有条狐，至多有条狐。

4.若某一二叉树按中序遍历可得到有■序序列，则该二叉树是.若某一二又

树从根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，

则该二叉树是.

5,若对完全二叉树中的结点从1开始按层进行编号，设最人编号为n,则编号为i

的结点(1。9)的父结点编号为；所有编号的结点为叶子结点?

6.压栈次序为a、b、c,则不可能得到的输出序列是.

7.已知特排序序列为:33,34,7,28,38,11.65,15.37,20.则:

以第一个元素为枢轴的快速排序一趟分划的结果是?

堆排序初始建堆(小顶堆)的结果是.

希尔排序第一越(增量为3)的结果是.

三、图示结构题(每小题8分，共40分)

i,已知某二叉树的先序遍历次序为:abcdefg.中序遍历次序为:badcfeg.

(1)画出该二叉树形.

(2)给出该二叉树的后序遍历次序.

(3)画出中序线索化后的二叉树形.c

2.已知某无向图如右图所示:

(1)画出该图的邻接表存储结构.(vw-v/t)

(2)画出该图的邻接矩阵存储结构。只)

(3)根据你所绘制的邻接表给出dfs

及bfs次序.

3.依序将关键字20、40、30、80、70、50、60、10插入到一棵2-3树中(初始状

态为空)，

(1)请画出该b-树.

(2)再先后删除关键字40、60.画出删除后的b-树。

4,设哈希函数为h(key)=keymod7,用链地址法处理冲突，若依次在哈希表中插入

12个元素32、65、83、25、74、21、33、18、61、27,47、28.

(1)画出它们在表中的分布情形.

(2)计算其平均成功的查找长度.

5.假设用于通讯的电文仅由8个字符a、b、c、d、e、f、g、ii组成，字符在电文

中出现的频率分别为3、12、9,23、2,17,21、13

(1)画出你所建的哈夫曼树，

(2)给出每一字符的哈夫曼编码.

笫2页共5页

四、阅读以下函数，指出算法的功能(每小题6分，共36分)

1.statusal(sqlistl,elemtypecur_e,elcmtype&next_e)

{//初始条件:顺序线性表l已存在

inti=l;

elemtype*p=l.elem;

while(i<l.length&&*p?=cur_e){

if

p++:

)

if(i=l.length)

returninfeasible;

else{

next_e=*++p;

returnok;

)

)

2.statusa2(linklistl,inti,elemtypee)

(〃初始条件:带头结点的单链表l已存在

intj=0:

linklistp=l,s;

whi1e(p&&j<i-1){

p=p->next;

j++:

)

if(!piij>i-1)

returnerror:

s=(linklist)malloc(sizeof(lnode)):

s->data=e;

s->next=p->next;

p->next=s;

returnok:

)

3.inta3(linkqueueq)

i//初始条件:链队列q已存在

inti=0;

queueptrp:

p=q.front;

第3页共5页

while(q.rear!=p){

i++:

p=p->next;

)

returni;

}

4.voida4(bitreet,status(*visit)(telemtype))

{//初始条件:二叉树t已存在

if(t){

a4(t->lchiid,visit);

a4(t->rchild,visit):

visit(t->data);

)

5.inta5(sstablest,keytypckey)

(〃初始条件:顺序表st已存在

inti;

st.elem[0].kcy=key;

for(i=st.length;!eq(st.elem[i].key,key):—i);

returni;

)

6.inta6(sqlistl,inti)

{〃初始条件:顺序表l已存在

intmin:

intj,k;

k=i;

min=l.r[i].key;

for(j=i+1;j<=l.length;j++)

if(l.r[j].key<min){

k=j;

min=l.r[j].key;

)

returnk:

笫4页共5页

五、算法设计题(每小题10分，共20分)

i.设单链表结点结构为:

typedefstructlnode{

intdata;

structlnode*next:

)*linklist;

写一函数voida7(linklistl)

试采用直接插入排序的方法将单链表4(带头结点)中的结点按非递减次序排列。

2.设二叉链表结构为:

typedefstructbitnode{

telerntypedata;

structbitnode*lchild,*rchild;

}*bitree;

写一函数voida8(bitreet)求二叉树7的深度。

第5页共5页

/

杭州电子科技大学

2012年攻读硕士学位研究生入学考试

《数据结构》试题

（试题共五大题，共四页，总分150分）

姓名报考专业准考证号

【所有答案必须写在答题纸上，做在试卷或草稿纸上无效！】

一、判断题（本大题共10小题，每小超2分.本大题共20分）

1.数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算

机的.

2.数据对象是数据元素的有限集合.

3.顺序存储结构要求存储单元地址连续,而链式存储结构要求存储单元地址不连

续.

4.若某完全二叉树中共有121个结点，则第68个结点的度为0.

5.一个连通图必定是一个无向完全图.

6.平衡二叉树必定是完全二叉树.

7.只要精心设计，总是可以设计出无冲突的哈希函数.

8.在最坏情况下，堆排序的时间性能是0（nlogn）,比快速排序最坏情况好.

9.通常，在一棵非空的二叉排序树中.“删除某个元素后乂将其插入.则所得的二又

排序树与删除前的二叉排序树相同.

10.若哈希表采用线性探测法处理冲突，同义词在表中不一定相邻存储.

二、单项选择题（本大题共9小题，12个选项，每个选项2分，本大题共24分）

1,线性表的顺序存储结构是一种的存储结构.

a.散列存取b.索引存取c.随机存取d.顺序存取

2.循环队列用数组a[a]存放其元素值，已知队列的头和尾分别用front和rear来

指示，初始化时置front=rear=0,则当前队列长度是.

a.（rear-front+m）%mb.rear-front+1

c.rear-front_1d.rear-front

3.线性表的链式存贮结构的优点为.

a.存储空间可充分利用b.可随机存取表中任一元素

c.插入删除操作较为方便d.便于不找线性表中的元素

4.折半插入排序是对直接插入持序算法的改进，它着眼t减少?

a.移动元素的次数c.排序的超数

c.与关键字比较的次数d.空间复杂度

第i页共4页

5.设有向图的顶点个数为n,则该有向图最多有条弧.

a.n-1b.n(n-l)c.n(n+l)d.n’

6.如果二又树中任何一个祚终端结点的值都人了其左子树上所有结点的值而小丁

其右于树上所有结点的值，要得到各结点值的递增序列，应按遍历次序揖

列结点.

a.先序b.中序c.后序d.层序

7.具有n个结点的huffman树有个叶子结点..

a.n-1b.「n/21c.|_n/2」d.不定

8.已知广义表工=(々,%2),4(53?)),从l中取出原子项y的运算是.

a.head(tai1(head(l)))b.tai1(head(head(tail(l))))

c.tai1(tai1(head(tai1(l))))d.head(tail(head(head(l))))

9.已知待排序的关键字序列为:36,21,78,63,6,52,15,39,48,70,10,需按非递减

次序排序，则希尔排序第一趟(增埴为5)的结果为(1):起泡排序第一趟的

结果为(2):快速排序第一趟(以第一个元素为支点)的结果为(3):

堆排序初始建堆(大顶堆)的结果为(4).

a.21,36,63,6.52,15,39,48,70,10,78

b.78,70,52,63,21,36,15,39,48,6,10

c.78,52,63.70,21,15,36,39,48.6,10

d.10,21,15,6,36,52,63.39,48.70.78

e.10,15,39,48,6,36,21,78,63,70,52

f.21,36,78.63,6,52,15,39,48,70,10

三、填空题(本大题共12小题，20个填空项，每个填空项2分，本大题共40分)

1.一个队列的入队序列是1,2,3,4,则队列可能的掠出序列是.

2.判断不带头结点的单循环链表l为空的条件是.

3.设二维数组的“以行序为主序存储，每个元素占4个字节，存储器按字节编址.

已知a的起始存储位置(即数组元素a?的存储地址)为1000,则数组元素标的存储

地址是(1).数组a的存储址是(2)字节.

4.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过.

5.若无向图有100个顶点、200条边.用邻接矩阵存储,则该邻接矩阵有(1)个

矩阵元素，(2)个非零元素.

6.高度为5的完全二叉树至少有(1)个叶/结点,至多有(2)个叶子结

点.

7.将一个森林f话换为二叉树b,则f的先序遍历是b的遍历?

8.一个饵法的语句频度之和为t(n)=(3n’+2n’lo&n+4n-7)/(5n),用时间复杂

度表示为0().

9.在一棵m阶b树中，每个非终端结点至多有棵子树。

笫2页共4列

10.根据数据元素之间的关系的不同特征,可以分成集合、(1)、(2)和

图状结构4类基本结构.

11.statusdeleterear(linklist&rear,elemtype&e)

(〃rear是带头结点的单循环链表的尾指针(指向循环偌表的表尾元素结点)，

〃本算法删除首元结点，并由e返同其值.

if(rear->next=rear)

returnerror;

____(1)____；

rear->next->next=p->next:

e=p->data;

if(p==rear)

⑵:

________(3)________:

returnok;

)

12.bitreesearchbst(bitreet,keytypekey)

(〃在根指针t所指的一义排序树中递归地音找某关键字等于key的数据元素.

〃若杳找成功，则返回该元素结点的指针，否则返回空指针

if(!t)

⑴:

elseif(t->data.key=key)

returnt;

elseif(t->data.key<key)

⑵:

else

⑶；

四、简答题(本大题共6小题，每小题6分，本大题共36分)

1.某二叉树的先序遍历序列为:jcbadefigh,中序遍历序列为abcedfjgih。

(1)请画出该二叉树；

(2)画出其中序线索二叉树.

2.对如心所示的有向图，

(1)画出其邻接表:

(2)针对⑴的邻接专写出从顶点1

开始的深度优先和广最优先遍历序列.

3.设数据元素的关键字序列为(10,14,7,23,80,65,54,90,36,47,23),依次输入这

些元素，创建一棵平衡的二义排序树(avl树)，请逐一画出每插入一个元素后的avl

第3页共4页

树的形态.

4.什么是稳定排序方法？希尔排序是不是稳定排序方法？简单选抒排序是不是稔

定持序方法？

5.设哈希表长度是16,哈希函数为h(key)=keymod13,用线性探测再散列法处

理冲突，依次在哈希表中插入12个元素(47,38,80,45,14,51,31,18,63.72,9.581.

(1)画出它们在表中的分布情形.

(2)计算等概率时杳找成功的平均杳找k度asl?

6.假设用于通讯的电文仅由8个字符组成,字符在电文中出现的领率及现有的一进

制前缀编码如卜所示:

字符abcdefgh

频率a137242202315

编码uno111010000mu11001101

请问这套编码是不是最优的前缀编码？为什么？如果不是，请给出更高效的编码。

五、算法设计题(本大题共3小题，每小题10分，本大题共30分)

1.设有一个不带头结点的单链表，表中元素值均不相同.试编写一个算法，删除该

单链表中元素值为x的数据元素,若删除成功，则返问irue,否则返回false.

单链表的结点定义为:

typedefstructlnode{

elemtypedata;

structlnode*next;

ilnode,*linklist;

【以卜两展均假设一叉树采用二叉链表存储结构，结点定义如卜:

typedefstructbitnode{

telemtypedata;

structbitnode?ichiid,*rchiid;

ibitnode,*bitree;]

2.设计一算法,计算给定二义树t中度为2的结点个数。

3.设指针p(升空)指向一义树中的某个结点.且该结点的左右千树均1f空，试写

出求p所指结点的中序后继的算法.

第4贡共4页

杭州电子科技大学

2013年攻读硕士学位研究生入学考试

《数据结构》试题

(试题共六大题，6页，150分)

姓名报考专业______________准考证号

【所有答案必须写在答题纸上，做在试卷或草稿纸上无效！】

一、是非题(每小题2分，共10分)

1.对「插入、删除操作，单链衣和顺序衣的时间复杂及都可计为.

2.队列是种操件受限的线性表，所有对数据元素的操作仅限一端进行“

3.ii线性结构的遍历过程是对结构中的蜉数据元素访问h.仅访问?次,“结构

中数据元素之间的美系无关.

4.对r?求坡小代价生成树的力.法，kruskal方法优「prim方法.

5.哈希衣的杏找效率。衣找表的长位无关。

二、选择题(每空2分，共28分)

1.线性表在的情况卜适「使用链表结构实现＜

n:表中含有人址结点m需处常修改衣中结点如

c:需经常对我进行删除、插入d:表中数据几索依美键字有序

2.如卜关丁巾的陈述中，错误的是.

a:串是数据对象为字符集的线性&b:中的长度为字符的个数

c:串中若干个连续字符构成的子序列称为广小?巾中的数据元索是？私

3.设仃.维数组a[6][5]，库一数组元素所川存储空间为1个字必存储器按字

?编址。已知a在存储册中的起始地址为100.则按行为储此无索a12j⑶的

第一?个字。的地址是:按列存储时，元素a12n3]的第-个字苗的

地址是.

a:128b:152c:ihod:200

4.对广义&a二(((a?b),(c)),(d))

执行操作rettai1(gelhead(geltai1(a)))的结果足:.

执行操作gelhead(gehail(geihcmi(a)))(f)结果是:-

a:《)b?(a)c:(h)(i:(()e:(1|)

第i页共6页

5.jk栈次序为k2、3、4则不可能得到的输出序列足。

a:1432b:2113c:3421d:1321

6.设任意无向图g=（v,e）jfllg=（v，e’）,？；:g.是g的连通分崎，则卜列说法

中不正确的矩。

a:g’是g的子图b:g.足g的连通「图

c:g.是g的极大连通子图d:（；是g的极大连通广图rv.等丁?v

7.卜列科找方法中针对关键字仃序的顺序表优找效率较低。

a:顺序杳找b:折半查找c:分块杳找d:史波那央自找

8.卜列排序方法中,是稳定的:共仃最好的平均性能:

所需的辅存空间最大。面对不同的初始数据，的时间更

杂度恒为0（nlogn）:而的时间复杂度恒为0<n）:

a:快速排序b:简单选择排序c:希尔排序d:打井排序

三、填空题（每空2分，共22分）

1.以物理位置来表示数据元素之间的逻辑关系的存储结构被称为:

通过指计来保持数据元素之间的逻辑关系的存储结构被称为:

2.对完全_义树中的结点从1开始按层进行连续编号。设编号为i的结点的父结

点存在，则编号为的结点为其父结点；设编号为i的左核子结点存在,

则

编号为的结点为其左孩子结点；设编号为i的4.孩f结点存在，则

编号为的结点为其仃孩子结点.

3.已知某?义树的先序遍历次序为:a.r.cd.e.匕g.h.中仔遍历次序为:b.i）.

c,f,e,a,h,g.则其后序遍历次序为:层次遍历次序为0

4.n个顶点的强连通图至少有条弧，至多有条弧。

5.一棵m阶的b树，第一层至少有一个结点；第二层至少仃2个结点，除根上

外的所有作终端结点至少有棵/树，树中所有11终端结点至多tf

___________棵j树。

四、图示结构题（每小题8分，共40分）

1.已知某森林的先序遍历次序为:a,d,e,f,g,h,b,i,c,j,k,l,m,nc,

中存遍历次序为:d,i-,g.li,l-.a.l.b.j.lm,、,k,g

<1）画出该森林°

（2）画出该森林用孩，兄弟法表示的存储结构，

批2页共6’；?

已知某无向图如右图所示:

(1)回出该图数组表示法(邻接矩阵)存储结构.

(2)画出该图的邻接衣存储结构。b…..c

(3)根据你所绘制的邻接表给出dfs及bi:s次序，/、.、“〉，，

并画出深度优先生成树和广深度优先牛.成树。’ef>

3.依序将关键字65,5。,30,20,10.45,60,55,25,70插入到棵.义作序树中(初

始状态为空，

(1)请画出该二义排序树。

(2)若之后删除关键字65,画出删除后的.义排序树.

(3)以同样的关键字插入次序建、z平衡二义排序树，请血出该平衡一义树。

4.设哈希函数为h(kcy)=kcymod13?哈希太长为15,用开放定址法处理冲突，

增批序列使用二次探测再散列。若依次在哈希表中插入ii个兀索:

34,12,67,43,98,23,51,86,05,37,22.

(1)画出它们在我中的分布情形。

(2)求其等概率情况卜平均成功的竹我长度。

5.假设用丁通讯的电文仅由8个字符a,b,c,d,e,f,g,h组成，字符化电文

中出现的频率分别为6,25,3,17,8,15,10,16

(1)而出你所建的哈大段树，

<2)给出每一字符的哈夫曼编码。

五、阅读以下函数，指出算法的功能(每小题6分，共30分)

1.boolal(unklistl.inii.elemtypec)

{//l为带头结点的单链我

intj=0:

linklistp=l,s:

whi1e(p&&j<i-1)(

p=p->nexl:

j”:

i

it(!p.t