杭州电子科技大学

2021年攻读硕士学位研讨生招生考试

《数据规划》试题

(试题共五大题，共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页

杭州电子科技大学

2021年攻读硕士学位研讨生招生考试

《数据规划》试题

(试题共五大题，共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