【数据结构】数据结构试卷7份附答案

数据结构试卷

一、选择题（每小题2分，共20分）

1、与线性表的顺序存储不相符的特性是（ ）。

a.不便于插入和删除 b.必须连续的存储空间

c.需另外开辟空间保存元素间的关系 d.存储容量固定

2、下列时间复杂度最好的是( )。

3、在链表中最常用的操作是删除表中最后一个结点和在最后一个结点之后插入元素，则采用（ ）最节省时间。

a、带头指针的单向循环链表 b、带头指针的双向循环链表

c、带尾指针的单向循环链表 d、双向链表

4、设一个栈的输入序列为1、2、3、4，则借助一个栈所得到的输出序列不可能的是（ ）

a、1，2，3，4 b、4，3，2，1 c、1，3，4，2 d、4，1，2，3

5、一棵左右子树均不空的二叉树在中序线索化后，空的指针域的个数是( )。

a、0 b、1 c、2 d、不确定

6、10个顶点的连通图的深度优先生成树的边数为（ ）。

a、11 b、10 c、9 d、无法确定

7、12个结点的平衡二叉树的最大深度为( )。
a、4 b、5 c、6 d、7

8、设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较（ ）次。
a、9　 b、8　 c、7　 d、6

9、一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（　　）

a、（14，18，38，46，65，40，20，53，86，74）

b、（14，38，18，46，65，20，40，53，86，74）

c、（14，18，20，38，40，46，53，65，74，86）

d、（14，86，20，38，40，46，53，65，74，18）

10、快速排序方法在（ ）情况下最不利于发挥其长处。

a、要排序的数据太大 b、要排序的数据中含有多个相同值

c、要排序的数据已基本有序 d、要排序的数据个数为奇数

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

1、下面程序段中带下划线的语句的执行次数是

for(i=0;i<=n;i++)

for(j=0;j<=i;j++)

x=x+1;

2、若串s=‘software’,其非空子串的数目是

3、设数组a[1..5,1..6] 的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则a[5，5]的地址是 。

4、已知广义表l=（（a），a），则该广义表表头为____________，该广义表表尾为____________。

5、已知一棵完全二叉树中共有768 个结点，则该二叉树中共有____________个叶子结点。

6、由八个分别带权值为7、19、2、6、32、3、21、10的叶子结点构造一棵哈夫曼树，则该树的带权路径长度为____________。

7、若对长度为10的有序表进行折半查找，则在等概率时查找成功的平均查找长度为____________。

8、对关键字序列(46，79，56，38，40，84)进行一趟快速排序之后的结果为____ ___ ____。

三、判断题（每小题1分，共9分）

1、线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ）

2、算法就是程序。（ ）

3、在单链表中，头结点是必不可少的。（ ）

4、字符串是由零个或多个字符组成的有限序列，空格串的串长度为零。（ ）

5、数组元素的下标值越大，存取时间越长。（ ）

6、在哈夫曼树中，权值最大的叶子结点离根结点最近。（ ）

7、用邻接表存储一个图时，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（ ）

8、在线性探测法处理冲突的散列表中，所有同义词在表中相邻。（ ）

9、在一个大根堆中，最小元素不一定在最后。（ ）

四、应用题（每小题5分，共25分）

1、试利用广义表取表头函数head（）和取表尾函数tail（），将原子d从下列广义表中分解出来，请写出每一步的运算结果。

l=（a，b，（c，d），（e，(f，g)））

2、假设一棵二叉树的先序序列为ebadcfhgikj，中序序列为abcdefghijk，请画出该二叉树，并写出它的后序序列。

3、已知长度为12的表：（jan，feb，mar，apr，may，june，july，aug，sep，oct，nov，dec），按表中元素的顺序依次构造一棵平衡二叉排序树，并求其等概率情况下查找成功的平均查找长度。

4、已知一组关键字：（40，27，28，12，15，50，7），要求采用堆排序从小到大排序，画出建立初始堆的过程图示。

5、已知一组关键字为{22，41，53，46，30，13，01，67}，共八个元素，哈希函数为：h(k)= （3k） % 11 ,采用线性探测再散列法处理冲突。在0—10的散列地址空间中画出该哈希表，并计算该表在等概率情况下查找成功与不成功时的平均查找长度。

五、算法设计题（共3小题，共30分）

1、写一算法实现带头结点的单链表l的就地逆置，即在原表的存储空间中将表（a1,a2,…,an）逆置为（an,…,a2,a1）。（10分）

2、已知顺序表l递增有序，写一算法将x插入到表l的适当位置上，以保持表l的有序性。（10分）

3、已知二叉树t采用二叉链表存储结构，编写算法将二叉树t的左右子树进行交换。（10分）

试卷答案

一、选择题（每小题2分，共20分）

1、c 2、a 3、b 4、d 5、c 6、c 7、b 8、c 9、b 10、c

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

1、 (n+1)(n+2)/2 2、 36 3、 1140 4、表头为（a），表尾为（a）

5、_384_ 6、261 7、2.9 8、(40，38，46，56，79，84)

三、判断题（每小题1分，共9分）

1、× 2、× 3、× 4、× 5、×

6、√ 7、× 8、× 9、√

四、应用题（每小题5分，共25分）

1、 a=tail(l)=（b，（c，d），（e，(f，g)））

b=tail(a)=（（c，d），（e，(f，g)））

c=head(b)=（c，d）

d=tail(c)=（d）

e=head(d)=d

即：d=head(tail(head(tail(tail(l)))))

2、后序序列为：

五、算法设计题（共3小题，共30分）

1、（10分）

void reverselist ( linklist l )

{ p=l->next; l->next=null;

while( p )

{ q=p->next; p->next=l->next;

l->next=p; p=q;

}

}

2、（10分）

void insertlist ( seqlist *l, elemtype x)

{ i=l->last;

while( i>=0 && l->elem[i]>x )

{ l->elem[i+1]=l->elem[i]; i--; }

l->elem[i+1]=x; l->last++;

}

3、（10分）

void changebitree ( bitree t )

{ if( t )

{ p=t->lchild; t->lchild=t->rchild; t->rchild=p;

changebitree( t->lchild );

changebitree( t->rchild );

}

}

数据结构试卷

一、选择题（每题2分，共30分）。

1、若某线性表中最常用的操作是在第i个元素之前插入一个元素和删除第i个元素，则采用( )存储方式最节省时间。

a、散列表 b、单链表 c、二叉链表 d、顺序表

2、设输入序列为a，b，c，d。下面的四个序列中，借助一个栈能够得到的输出序列是（ ）。

a、d，c，a，b b、c，a，d，b

c、a，c，d，b d、d，a，b，c

3、已知完全二叉树有80个结点，则整个二叉树有（ ）个度为0的结点。

a、40 b、41 c、39 d、不确定

4、从逻辑上可以把数据结构分为（ ）两大类。

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

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

5、若一个栈以向量v[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。

a、top=top+1； v[top]=x b、 v[top]=x；top=top+1

c、top=top-1； v[top]=x d、 v [top]=x；top=top-1

6、在有序表a[20]中按二分查找方法查找元素a[13]，依次比较的元素下标是 ( )，假设有序表的起始元素从a[0]开始存放。

a、9，14，12，13 b、9，15，12，13

c、9，14，11，12，13 d、10，15，12，13

7、表达式a*(b+c)-d的后缀表达式是( )。

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

8、下列数据表中，（　　）是堆。

a、（100，80，55，60，50，40，58，35）

b、（10，18，15，20，50，80，30，60）

c、（10，15，18，50，80，30，60，20）

d、（10，30，60，20，15，18，50，80）

9、设给定权值总数有n 个，其哈夫曼树的结点总数为( ) 。

a、不确定 b、2n c、2n+1 d、2n-1

10、设循环队列用数组a[n]存储，头尾指针分别为front和rear。求解当前队列中元素个数的公式是（ ）。

a、rear-front b、front-rear

c、n-(front-rear) d、(n+rear-front)%n

11、设无向图的顶点个数为n，则该图最多有（ ）条边。

a、n-1 b、n(n-1)/2 c、n(n+1)/2 d、n/2

12、设图g采用邻接表存储，对该图进行深度优先遍历，则算法的时间复杂度为( )。

a、o(n) b、o(n+e) c、o(n2) d、o(n3)

13、在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的键值（ ）。

a、一定都是同义词 b、一定都不是同义词

c、都相同 d、不一定都是同义词

14、对下图，不能得到的拓扑序列为（ ）。

a、a，b，c，d，e，f，g，h b、a，e，b，f，c，g，d，h

c、a，b，e，f，c，d，g，h d、a，b，c，d，h，g，f，e

15、矩阵a5×6的每个元素占5个字节，将其按行优先次序存储在起始地址为1000的连续内存空间中，则元素a44的地址为（ ）。

a、1120 b、1125 c、1140 d、1145

三、读算法，写结果（每小题4分，共8分）

1、下列算法：

status createtree( bitree &t)

{ scanf(“%c”,&ch);

if (ch==’#’) t=null;

else {

t=(bitnode *)malloc(sizeof(bitnode)));

if (t==null) exit(overflow);

t－>data=ch;

createtree(t－>lchild);

createtree(t－>rchild);

}

return ok;

}

如果按照abc＃＃de＃g＃＃f＃＃＃次序顺序读入字符（其中＃表示空格字符），则请画出该算法构造的二叉树。

2、存储结构为带头结点的单链表l。假设单链表l如下：

void changelist ( linklist l )

{ p=l->next; l->next=null;

while( p )

{ q=p->next; p->next=l->next;

l->next=p; p=q;

}

}

请画出上述算法后的单链表l，并简要概述上述算法的功能

四、应用题（共6小题，共37分）

1、已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清。请构造出该二叉树。（4分）

先序序列： bc e gh

中序序列： c da ghf

后序序列： db fea

2、已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序。写出堆排序、二路归并排序每趟的结果。（7分）

3、已知森林如下图所示，画出由森林转换得到的二叉树。（4分）

4、已知关键码集合为{47,7,29,11,16,92,22,8,3}，散列表的表长为11，散列函数为h(key)=key % 11，采用线性探测法处理冲突。请在0—10的散列地址空间中画出该散列表，并计算该表在等概率情况下查找成功与不成功时的平均查找长度。（6分）

5、根据图的邻接矩阵，利用prim算法求图的最小生成树mst。要求写出详细的求解过程，即画出构造mst过程中的结构体数组中各域的变化情况。（8分）

6、对s=’adbadabbaabadabbadada’，t= ‘adabbadada’，计算kmp算法中t的next值，并画出与s目标串的匹配过程。（8分）

五、算法填空及设计题（共2小题，共10 分）

1、设二叉树采用二叉链表存储，各结点有lchild、data和rchild三个域，设计算法仅打印出其中所有叶子结点的值。（5分）

void print(bnode *tl )

{}

2、已知顺序表l递增有序，写一算法将x插入到表l的适当位置上，以保持表l的有序性，不考虑空间溢出。（5分）

其中顺序表的数据结构定义为：

typedef struct{ elemtype *elem; int length}sqlist;

void insertlist ( sqlist &l, elemtype x)

试卷答案

一、选择题（每题2分，共30分）。

1、b 2、c 3、a 4、c 5、c 6、c 7、b 8、b

9、d 10、d 11、b 12、b 13、d 14、d 15、c

二、填空题（共9题，共15分）

1、 36 2、 o（1）、 o（logn） 3、 261

4、 cdefde 5、 p->piror s->piror->next=s

6、 ls=ls->next free(p)或者delete(p)

7、(40，38，46，56，79，84) 8、 (a) (a) 9、 3

三、读算法，写结果（每小题4分，共8分）

4、

（1）散列表构造及其查找成功的比较次数………………（2分）

	0	1	2	3	4	5	6	7	8	9	10
关键码	11	22		47	92	16	3	7	29	8
比较次数	1	2		1	1	1	4	1	2	2

（2）计算成功时的平均查找长度…………………………（2分）

asl＝（5×1＋3×2＋1×4）/9=15/9

（3）计算查找不成功时的比较次数………………………（2分）

地址	0	1	2	3	4	5	6	7	8	9	10
比较次数	3	2	1	8	7	6	5	4	3	2	1

计算不成功时的平均查找长度

asl＝（3＋2＋1＋8＋7＋6＋5＋4＋3＋2＋1）/11=42/11

5、

	2	3	4	5	6	7	u	v－u	输出	得分
adjvex lowcost	1 50	1 60	1 ∞	1 ∞	1 ∞	1 ∞	{1}	{2,3,4,5,6,7}	(1,2) 50	1分
adjvex lowcost		1 60	2 65	2 40	1 ∞	1 ∞	{1,2}	{3,4,5,6,7}	(2,5) 40	1分
adjvex lowcost		1 60	5 50		5 70	1 ∞	{1,2,5}	{3,4,6,7}	(5,4) 50	1分
adjvex lowcost		4 52			4 30	4 42	{1,2,5,4}	{3,6,7}	(4,6) 30	1分
adjvex lowcost		4 52				4 42	{1,2,5,4,6}	{3,7}	(4,7) 42
adjvex lowcost		7 45					{1,2,5,4,6,7}	{3}	(7,3) 45	1分
							{1-7}	{}

所求得的mst为……………………………………………（3分）

6、

（1）计算next值……………………………………………（3分）

下标	1	2	3	4	5	6	7	8	9	10
t	a	d	a	b	b	a	d	a	d	a
next	0	1	1	2	1	1	2	3	4	3

（2）画出kmp的匹配过程………………………………（5分）

第一趟：

a

d

b

a

d

a

b

b

a

a

b

a

d

a

b

b

a

d

a

d

a

a

d

a

b

b

a

d

a

d

a

第二趟：

a

d

b

a

d

a

b

b

a

a

b

a

d

a

b

b

a

d

a

d

a

a

d

a

b

b

a

d

a

d

a

第三趟：

a

d

b

a

d

a

b

b

a

a

b

a

d

a

b

b

a

d

a

d

a

a

d

a

b

b

a

d

a

d

a

第四趟：

a

d

b

a

d

a

b

b

a

a

b

a

d

a

b

b

a

d

a

d

a

a

d

a

b

b

a

d

a

d

a

第五趟：

a

d

b

a

d

a

b

b

a

a

b

a

d

a

b

b

a

d

a

d

a

a

d

a

b

b

a

d

a

d

a

五、算法填空及设计题（共2小题，共10 分）

1、（5分）

void print(bnode *tl )

{  

  if (tl!=null)

     {

       if(tl->lchild==null&& tl->rchild==null)

             cout<<tl->data;

       print(tl->lchild);

       print(tl->rchild);

}

}

2、（5分）

void insertlist ( sqlist *l, elemtype x)

{   i=l.length-1; 

   while( i>=0 && l.elem[i]>x )

   { l.elem[i+1]=l.elem[i]; i--; }

   l.elem[i+1]=x; l.length++;}

数据结构试卷1

二、填空题（共9题，共15分）

1、若串s=‘computer’，其非空子串的数目是 。(1分)

2、如果算法时间复杂度用大○记号表示，则常数阶记为 、对数阶记为 。(1分)

3、由八个分别带权值为7、19、2、6、32、3、21、10的叶子结点构造一棵哈夫曼树，则该树的带权路径长度为 。(2分)

4、执行下列程序段后，串x的值为 。(2分)

s=”abcdefgh”; t=”xyzw”; substr(x,s,3,strlen(t));

substr(y,s,strlen(t),2); strcat (x,y);

5、双向循环链表中，在指针p所指结点前插入指针s所指的结点，应执行下列语句，其中结点的数据结构为piror、data和next域：(2分)

s－>next=p；

s－>prior= ；

p－>prior=s；

；

6、设有一个链栈，其中各结点中有data和next两个域，栈顶指针为ls，其中ls≠null，p是一个临时指针变量，则执行出栈的基本操作是 p=ls ； ； 。(2分)

7、对关键字序列(46，79，56，38，40，84)进行一趟快速排序之后的结果为 。(2分)

8、广义表((a)，a)的表头是 ，表尾是 。(2分)

9、在一个3阶的b_树中，每个结点所含的子树数目最多为 。 (1分)

一、解释下列术语（每小题4分，共20分）

1. 头指针

2. 二叉排序树的定义

3. 头结点

4. 数据的逻辑结构

5. 排序方法的稳定性

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

（在每小题的4 个备选答案中，选出一个正确的答案，多选少选均不得分）

1. 在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时顺向后移动( ) 个元素

a.n-i b. n-i+1 c. n-i-1 d.i

2. 某个栈的输入序列为1，2，3，4，下面的四个序列中( )不可能是它的输出序列

a.1,2,3,4 b.2,3,4,1 c. 4,3,2,1 d.3,4, 1,2

3. 对二叉排序进行( )遍历可以得到结点的排序序列

a.前序 b.中序 c. 后序 d.按层次

4．有64个结点的完全二叉树的深度为（ ）。

a 8 b 7 c 6 d 5

5．折半查找法的时间复杂度是( )

a.(n2) b.o(n) c. o(n㏒n) d. o(㏒n)

6．a(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素a[5，5]的地址为（ ）。

a 1140 b 1145 c 1120 d 1125

7. 有n个叶子结点的哈夫曼树的结点总数为（ ）。

a 不确定 b 2n c 2n+1 d 2n-1

8. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac, 则它的前遍历序列是（ ）。

a acbed b decab c deabc d cedba

9．若循环队列用数组a(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（ ）。

a (r-f+m)mod m b r-f+1 c r-f-1 d r-f

10. 一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树（树中结点个数大于1）。

a 空或只有一个结点 b 高度等于其结点数

c 任一结点无左孩子 d任一结点无右孩子

三，判断题（每小题2分，对的打√，错的打×，共10分）

1．若图g的最小生成树不唯一，则g的边数一定多于n-1，并且权值最小的边有多条（其中n为g的顶点数）。 ( )

2．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访到该图的每个顶点。( )

3．若某二叉树的叶子结点数为1（树中只有一个结点的情况除外），则其先序序列和后序序列一定相反。（ ）

4．在队列中，队头指针总是指向第一个数据元素。（ ）

5．线性表的唯一存储形式是链表。（ ）

四，解答题（每小题6分，共24分）

a) 从一的平衡二叉树开始，把关键字（5，19，6，22，16，15，30）按出现的先后顺序逐一插入，从而构造一棵平衡二叉树排序树，每插入一个关键字后，若需要进行平衡旋转，则标明其旋转类型及旋转后的结果。

b) 满足下列条件的二叉树具有什么形状？

i. 前序和中序遍历次序相同；

ii. 中序和后序遍历次序相同；

iii. 前序和后序遍历次序相同；

c) 写出所给数据表，采用快速排序方法按升序排序的每一趟的结果：（25，10，20，31，5，28）。

d) 具有144个记录的文件，若采用分块查找法查找，则分成几块最好？每块的最佳长度是多少？假定每块的长度是8，确定所在块、块中均采用顺序查找法查找，则平均查找长度是多少？

五、编写算法（共16分）

a) 写出，建立一个具有n个顶点的无向网的邻接矩阵的算法。提示：先将矩阵a的每个元素都初始化成0，然后，读入边及数值（i, j, w）,将a的相应元素置成w。（8分）

b) 线性表v采用顺序存储结构，试编写删除v中的第i个元素起的k个元素的算法。（8分）

数据结构试卷2

一、填空题（共20分，每空1分）

1． 数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，通常有下列四种存储结构： （1） 、 （2） 、 （3） 和 （4） 。

2． 评价算法的标准很多，通常是以执行算法所需要的 （5） 和所占用的（6） 来判别一个算法的优劣。

3． 队列操作的原则是（7），栈的插入和删除操作在（8）进行。

4． 对循环队列q，它的最大存储空间是maxsize，队头指针是front，队尾指针是rear，采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。

5． 在以 head 为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分别为 （11） 和 （12）。

6． 假设二维数组a[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址 ，已知a的开始存储位置为100，按行优先顺序存储的元素a[2][5]的第一个字节的地址为（13）。

7． 空格串的长度为串中所包含（14） 字符的个数，空串的长度为 （15） 。

8． 有向图 g 用邻接矩阵 a[n，n] 存储表示，其第 i 行的所有元素之和等于顶点 i 的 （16） 。

9． 在关键字序列 (12 ， 23 ， 34 ， 45 ， 56 ， 67 ， 78 ， 89 ， 91) 中折半查找关键字为 89和25 的结点时，所需进行的比较次数分别为 （17） 和 （18）。

10． 请说出两种处理哈希冲突的方法 （19） 、_（20）

二、选择题（共20分，每题2分）

1. 对线性表，在下列哪种情况下应采用链式存储结构？（ ）

a．经常需要随机存取元素 b．经常需要进行插入和删除操作

c．表中元素的个数不变 d．表中元素需要占据一片连续的存储空间

2. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比

较（ ）个结点。

a．n b．n/2 c．(n-1)/2 d．(n+1)/2

3. 若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用（ ）存储方式最节省运算时间。 a．单链表 b．双链表

c．仅有头指针的单循环链表 d．仅有尾指针的单循环链表

4. 在一个单链表中，若要删除p指针所指结点的后继结点，则执行（ ）。

a．p-> next; p-> next=p-> next-> next； b．p-> next=p-> next-> next；

c．p=p-> next； d．p=p-> next->>next；

5. 在具有 n 个结点的二叉链表中，非空的链域个数为（ ）。

a．n-1 b． n c． n+1 d．不确定

6. 有64个结点的完全二叉树的深度为（ ）（假设根结点的层次为1）。

a．8 b． 7 c． 6 d．5

7. 边远山区的那个小村庄，现要为他们建成能互相通信的网 ，并且总的花费最少，这可以归结为什么问题（ ）。 a．最短路径 b．关键路径 c．拓扑排序 d．最小生成树

8. 折半查找法要求查找表中各元素的键值必须是（ ）。

a．递增或递减 b．递增 c．递减 d．无序

9. 下列排序算法中，（ ）算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。

a．直选择排序 b．冒泡排序 c．归并排序 d．堆排序

10. 对于键值序列（2，33，21，18，65，38，7，49，24，86），用筛选法建堆，必须从键值为（ ）的结点开始。

a．86 b． 2 c．65 d．38

三、判断题（共10分，每题2分）

1. 已知指针p指向链表l中的某结点，执行语句p=p->next不会删除该链表中的结点。( )

2. 如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。( )

3. 若一棵二叉树的任一非叶结点度均为2，则该二叉树为满二叉树。( )

4. 任一aoe网中至少有一条关键路径，且是从源点到汇点的路径中最短的一条。( )

5. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（ ）

四、简答题（共24分,每题8分）

1. 二叉树的先序遍历序列为：a b c d e f g h i，中序遍历序列为：b c a e d g h f i，画出这棵二叉树。

2. 输入一个结点序列{300，100，80，52，40，64，350}，试画出构造平衡二叉树的过程，并说明平衡旋转类型。

3. 已知一组记录的排序码为（46，79，56，38，40，80，95，24），写出对其进行快速排序的每一趟排序的结果。

五、算法设计题（共16分）

1． 试写一建立单链表的算法。（8分）

2． 已知一个非空线性链表第一个结点的指针为l，请写一算法，将链表中数据域值最大的那个结点移到链表最后面。（8分）

数据结构试卷试3

一、填空（20分，每小题2分）

1、若用s[1]~s[m]作为顺序栈的存储空间，栈空的标志是栈顶指针t=m+1，则每进行一次（ ）操作，需将t的值加1。

2、队列的特征是( )。

3、在单向链表中增加一个表头节点的目的是（　）。

４、3个结点可以构成（ ）种不同形状的树，可以构成（ ）种不同形状的二叉树。

５、在平衡二叉排序树中，每个结点的平衡因子等于（ ）。

６、可以进行拓扑排序的有向图一定是（ ）。

７、为了实现折半查找，线性表必须采用（ ）方法存储。

８、若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（ ）

９、在排序过程中，任何情况下都不比较排序码大小的排序方法是（ ）。

二、选择填空（20分，每小题2分）

1、链表最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）
存储方式最省时间。
a. 单链表 b. 双链表 c. 单循环链表 d. 带尾指针的单循环链表

2、栈和队列都是(   )
        a．顺序存储的线性结构              b．链式存储的非线性结构
c．限制存取点的线性结构            d．限制存取点的非线性结构

３、若对有18个元素的有序表作折半查找。则查找a[3]的比较序列的下标为（）。

a．1，2，3 b．9，5，2，3 c．9，4，2，3 d．10，5，３，２

4、设n，m为某二叉树上的两个结点，在中序遍历时，n在m前的条件是(   )
        a．n在m右方     b．n是m祖先     c．n在m左方      d．n是m子孙
5、对长度为10的有序表进行折半查找，设在等概率时查找成功的平均查找长度是(   )
        a．2.9            b．3.1            c．3.4            d．2.6

6、带权有向图g用邻接矩阵a存储，则顶点 i 的入度等于a中第 i ( )。
a 行非∞的元素之和 b. 列非∞的元素之和
c. 行非∞且非0的元素个数 d. 列非∞且非0的元素个数

7. 在有n个叶子结点的哈夫曼树中，其结点总数为　( )。
a不确定 b2n c2n+1 d2n-1

8、任何一个无向连通图的最小生成树　( )。
a只有一棵 b有一棵或多棵 c一定有多棵 d可能不存在

9、设有1000个无序的元素，希望用最快的速度挑出其中前10个最大元素，在以下排序方法中用哪一种最好（ ）。

a、选择排序 b、冒泡排序 c、堆排序 d、快速排序

10、直接插入排序在最好情况下的时间复杂度为（ ）

a. o(logn) b. o(n) c. o(n*logn) d(n2)

三、判断正误（10分，每小题2分。对得打“√”，错的打“╳”）

1、如果一个串中所有字符均在另一串中出现，则说前者是后者的子串。 （）

2、（101，88，46，70，34，39，45，58，66，10）是堆。 （）

3、 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离很较近。（ ）

4、用树的前序遍历和中序遍历可以导出树的后序遍历。 （）

5、在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反的方向移动，从而可以认为该算法时不稳定的。 （）

四、简答题（35分）

１、将关键字集合k={60，40，49，23，25，13，95，196，85}，创建平衡二叉排序树。

2、设一数列的顺序是1、2、3、4、5、6，通过栈结构

1） 能否排成顺序为3、2、5、6、4、1的数列？

2）能否排成顺序为1、5、4、6、2、3的数列？

3、一棵共有n个结点的树，其中所有分枝结点的度均为k，求该树中叶子结点的个数。

4、有关键字集合k{37，15，50，01，55，25，84，30，44，24，27，38}，α=0.75，采用除留余数法，解决冲突用线性探测，将k散列到哈希表。

5、 给定一组记录的关键词，其顺序是13、7、9、15、8、16、12、4、11、20、10、14，试写出：

a) 用快速排序算法操作时，第一趟结束后的状态。

b) 用希尔排序算法操作时（逐减增量序列是6、3、2、1），第一趟和第二趟结束后的状态。

c) 用选择排序算法操作时，第一趟和第二趟（即选择最大和次大 者送到最后排序位置）结束后的状态（两趟分别写出）。

五、算法（15分）

１、写出一个将二叉树左、右孩子交换的算法。 （7分）

２、试写出一个利用遍历图的方法输出一条无向图g中从顶点vi到vj长度为l的简单路径的算法。（8分）

数据结构试卷试4

一、选择填空（每小题2分，共20分）

（在每小题的4 个备选答案中，选出一个正确的答案，多选少选均不得分）

1．有64个结点的完全二叉树的深度为（ ）。

a 8 b 7 c 6 d 5

2． 折半查找法的时间复杂度是( )

a.(n2) b.o(n) c. o(n㏒n) d. o(㏒n)

3. 在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时顺向后移动( ) 个元素

a.n-i b. n-i+1 c. n-i-1 d.i

4. 某个栈的输入序列为1，2，3，4，下面的四个序列中( )不可能是它的输出序列

a.1,2,3,4 b.2,3,4,1 c. 4,3,2,1 d.3,4, 1,2

5. 对二叉排序进行( )遍历可以得到结点的排序序列

a.前序 b.中序 c. 后序 d.按层次

6．a(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素a[5，5]的地址为（ ）。

a 1140 b 1145 c 1120 d 1125

7. 有n个叶子结点的哈夫曼树的结点总数为（ ）。

a 不确定 b 2n c 2n+1 d 2n-1

8. 一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树（树中结点个数大于1）。

a 空或只有一个结点 b 高度等于其结点数

c 任一结点无左孩子 d任一结点无右孩子

9. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac, 则它的前遍历序列是（ ）。

a acbed b decab c deabc d cedba

10．若循环队列用数组a(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（ ）。

a (r-f+m)mod m b r-f+1 c r-f-1 d r-f

二、判断题（每小题2分，对的打√，错的打×，共8分）

a) 若某二叉树的叶子结点数为1（树中只有一个结点的情况除外），则其先序序列

和后序序列一定相反。（ ）

2．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访

到该图的每个顶点。( )

3．线性表的唯一存储形式是链表。（ ）

4．在队列中，队头指针总是指向第一个数据元素。（ ）

三、解释下列术语（每小题5分，共25分）

1.关键路径

2 树的路径长度

3.头结点

4. 数据的存储结构

5. 排序方法的稳定性

四、解答题（每小题6分，共24分）

1.满足下列条件的二叉树具有什么形状？

i. 前序和中序遍历次序相同；

ii. 中序和后序遍历次序相同；

iii. 前序和后序遍历次序相同；

2.有一组关键字，如果以不同的次序输入，这时建立起来的二叉排序树是否相同？当以中序遍序这些二叉排序树时，其遍序的结果是否相同？为什么？

3.具有144个记录的文件，若采用分块查找法查找，则分成几块最好？每块的最佳长度是多少？假定每块的长度是8，确定所在块、块中均采用顺序查找法查找，则平均查找长度是多少？

4.写出所给数据表，采用快速排序方法按升序排序的每一趟的结果：（25，10，20，31，5，28）。

五，编写算法（共23分）

b) 写出，建立一个具有n个顶点的无向网的邻接矩阵的算法。提示：先将矩阵a的每个元素都初始化成0，然后，读入边及数值（i,j,w）,将a的相应元素置成 w.（13分）

c) 线性表v采用顺序存储结构，试编写删除v中的第i个元素起的k个元素的算法。（10分）

数据结构试卷试5

一、解释下列术语（每小题4分，共20分）

1. 头指针

2. 二叉排序树的定义

3. 头结点

4. 数据的逻辑结构

5. 排序方法的稳定性

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

（在每小题的4 个备选答案中，选出一个正确的答案，多选少选均不得分）

1. 在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时顺向后移动( ) 个元素

a.n-i b. n-i+1 c. n-i-1 d.i

2. 某个栈的输入序列为1，2，3，4，下面的四个序列中( )不可能是它的输出序列

a.1,2,3,4 b.2,3,4,1 c. 4,3,2,1 d.3,4, 1,2

3. 对二叉排序进行( )遍历可以得到结点的排序序列

a.前序 b.中序 c. 后序 d.按层次

4．有64个结点的完全二叉树的深度为（ ）。

a 8 b 7 c 6 d 5

5．折半查找法的时间复杂度是( )

a.(n2) b.o(n) c. o(n㏒n) d. o(㏒n)

6．a(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素a[5，5]的地址为（ ）。

a 1140 b 1145 c 1120 d 1125

7. 有n个叶子结点的哈夫曼树的结点总数为（ ）。

a 不确定 b 2n c 2n+1 d 2n-1

8. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac, 则它的前遍历序列是（ ）。

a acbed b decab c deabc d cedba

9．若循环队列用数组a(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（ ）。

a (r-f+m)mod m b r-f+1 c r-f-1 d r-f

10. 一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树（树中结点个数大于1）。

a 空或只有一个结点 b 高度等于其结点数

c 任一结点无左孩子 d任一结点无右孩子

三、判断题（每小题2分，对的打√，错的打×，共10分）

1．若图g的最小生成树不唯一，则g的边数一定多于n-1，并且权值最小的边有多条（其中n为g的顶点数）。 ( )

2．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访到该图的每个顶点。( )

3．若某二叉树的叶子结点数为1（树中只有一个结点的情况除外），则其先序序列和后序序列一定相反。（ ）

4．在队列中，队头指针总是指向第一个数据元素。（ ）

5．线性表的唯一存储形式是链表。（ ）

四、解答题（每小题6分，共24分）

a) 从一的平衡二叉树开始，把关键字（5，19，6，22，16，15，30）按出现的先后顺序逐一插入，从而构造一棵平衡二叉树排序树，每插入一个关键字后，若需要进行平衡旋转，则标明其旋转类型及旋转后的结果。

b) 满足下列条件的二叉树具有什么形状？

i. 前序和中序遍历次序相同；

ii. 中序和后序遍历次序相同；

iii. 前序和后序遍历次序相同；

c) 写出所给数据表，采用快速排序方法按升序排序的每一趟的结果：（25，10，20，31，5，28）。

d) 具有144个记录的文件，若采用分块查找法查找，则分成几块最好？每块的最佳长度是多少？假定每块的长度是8，确定所在块、块中均采用顺序查找法查找，则平均查找长度是多少？

五，编写算法（共16分）

e) 写出，建立一个具有n个顶点的无向网的邻接矩阵的算法。提示：先将矩阵a的每个元素都初始化成0，然后，读入边及数值（i, j, w）,将a的相应元素置成w。（8分）

f) 线性表v采用顺序存储结构，试编写删除v中的第i个元素起的k个元素的算法。（8分）

数据结构试卷试6

一、填空题（共20分，每空1分）

1． 数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，通常有下列四种存储结构： （1） 、 （2） 、 （3） 和 （4） 。

2． 评价算法的标准很多，通常是以执行算法所需要的 （5） 和所占用的（6） 来判别一个算法的优劣。

3． 队列操作的原则是（7），栈的插入和删除操作在（8）进行。

4． 对循环队列q，它的最大存储空间是maxsize，队头指针是front，队尾指针是rear，采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。

5． 在以 head 为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分别为 （11） 和 （12）。

6． 假设二维数组a[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址 ，已知a的开始存储位置为100，按行优先顺序存储的元素a[2][5]的第一个字节的地址为（13）。

7． 空格串的长度为串中所包含（14） 字符的个数，空串的长度为 （15） 。

8． 有向图 g 用邻接矩阵 a[n，n] 存储表示，其第 i 行的所有元素之和等于顶点 i 的 （16） 。

9． 在关键字序列 (12 ， 23 ， 34 ， 45 ， 56 ， 67 ， 78 ， 89 ， 91) 中折半查找关键字为 89和25 的结点时，所需进行的比较次数分别为 （17） 和 （18）。

10． 请说出两种处理哈希冲突的方法 （19） 、_（20）_。

二、选择题（共20分，每题2分）

1. 对线性表，在下列哪种情况下应采用链式存储结构？（ ）

a．经常需要随机存取元素 b．经常需要进行插入和删除操作

c．表中元素的个数不变 d．表中元素需要占据一片连续的存储空间

2. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比

较（ ）个结点。

a．n b．n/2 c．(n-1)/2 d．(n+1)/2

3. 若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用（ ）存储方式最节省运算时间。 a．单链表 b．双链表

c．仅有头指针的单循环链表 d．仅有尾指针的单循环链表

4. 在一个单链表中，若要删除p指针所指结点的后继结点，则执行（ ）。

a．p-> next; p-> next=p-> next-> next； b．p-> next=p-> next-> next；

c．p=p-> next； d．p=p-> next->>next；

5. 在具有 n 个结点的二叉链表中，非空的链域个数为（ ）。

a．n-1 b． n c． n+1 d．不确定

6. 有64个结点的完全二叉树的深度为（ ）（假设根结点的层次为1）。

a．8 b． 7 c． 6 d．5

7. 边远山区的那个小村庄，现要为他们建成能互相通信的网 ，并且总的花费最少，这可以归结为什么问题（ ）。 a．最短路径 b．关键路径 c．拓扑排序 d．最小生成树

8. 折半查找法要求查找表中各元素的键值必须是（ ）。

a．递增或递减 b．递增 c．递减 d．无序

9. 下列排序算法中，（ ）算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。

a．直选择排序 b．冒泡排序 c．归并排序 d．堆排序

10. 对于键值序列（2，33，21，18，65，38，7，49，24，86），用筛选法建堆，必须从键值为（ ）的结点开始。 a．86 b． 2 c．65 d．38

三、判断题（共10分，每题2分）

1. 已知指针p指向链表l中的某结点，执行语句p=p->next不会删除该链表中的结点。( )

2. 如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。( )

3. 若一棵二叉树的任一非叶结点度均为2，则该二叉树为满二叉树。( )

4. 任一aoe网中至少有一条关键路径，且是从源点到汇点的路径中最短的一条。( )

5. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（ ）

四、简答题（共24分,每题8分）

1. 二叉树的先序遍历序列为：a b c d e f g h i，中序遍历序列为：b c a e d g h f i，画出这棵二叉树。

2. 输入一个结点序列{300，100，80，52，40，64，350}，试画出构造平衡二叉树的过程，并说明平衡旋转类型。

3. 已知一组记录的排序码为（46，79，56，38，40，80，95，24），写出对其进行快速排序的每一趟排序的结果。

五、算法设计题（共16分）

1． 试写一建立单链表的算法。（8分）

2． 已知一个非空线性链表第一个结点的指针为l，请写一算法，将链表中数据域值最大的那个结点移到链表最后面。（8分）

---

资料仅供学习使用

编者能力有限，如有错误欢迎留言交流

编者的其他专栏：

c语言

单片机原理

模式识别原理

数字电子技术

自动控制原理

模拟电子技术

数据结构

线性代数

复变函数与积分变换

 概率论与数理统计

高等数学

大学物理

电路原理

关注编者了解更多