数据结构试题及答案10套

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

1. 1.对一个算法的评价,不包括如下（B ）方面的内容。

Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度

2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向

的结点，则执行（A ).

Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p；

Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL；

3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ）

Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作

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

4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序

列的是( C ）

A. 2 3 1 ???

B. ３ 2 1

C。 3 １ 2 ??? D. 1 ２３

5. 5.AＯV网是一种（D ）。

A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图

6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。

A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找

7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D )

参数.

Ａ。值Ｂ。函数 C.指针 D。引用

8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结

点都具有相同的（ A )。

A。行号 B.列号 C．元素值 D．非零元素个数

9.9.快速排序在最坏情况下的时间复杂度为( D )。

A。O（loｇ

2n) B．Ｏ（nlog

2

n） C。０（n) D.0

（n2）

10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ).

Ａ．O(n） B. Ｏ(1） C。 O（log

2

n） D. O(n2)二、运算题（每题 6 分，共２４分）

1.１．数据结构是指数据及其相互之间的＿__＿＿_＿＿__＿_＿_.

当结点之间存在M对N（Ｍ:N）的联系时，称这种结构为_＿__＿__＿_____＿＿__＿＿＿＿。

2.2．队列的插入操作是在队列的_ _尾__＿___进行,删除操作是在

队列的____首_____＿进行。

3.3。当用长度为N的数组顺序存储一个栈时,假定用ｔop==N表示

栈空，则表示栈满的条件是_＿_top=＝0___（要超出才为满）_＿___________＿_。

4.4。对于一个长度为ｎ的单链存储的线性表,在表头插入元素的时

间复杂度为__＿__＿___，在表尾插入元素的时间复杂度为___＿＿_＿__＿__。

5.5。设W为一个二维数组，其每个数据元素占用4个字节，行下标

i从０到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用__＿＿_____个字节。

若按行顺序存放二维数组W,其起始地址为100,则二维数组元素Ｗ［６，３]的起始地址为＿___＿___＿_。

6.6。广义表Ａ= (a，(a,ｂ），（(a，b)，c)),则它的深度为___＿__

＿___＿_，它的长度为＿___________。

7.7.二叉树是指度为２的＿____＿______＿_______树。一棵结点数

为Ｎ的二叉树，其所有结点的度的总和是____＿＿_＿__＿__。

8.8。对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个

____＿____＿____。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的___________＿＿_____。

9.9。对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针

总数为__＿______＿__＿个,其中＿__＿__＿＿_____＿_个用于指向孩子，＿＿＿_＿__＿＿_＿______个指针是空闲的.

10.10。若对一棵完全二叉树从０开始进行结点的编号,并按此编号把它顺

序存储到一维数组A中，即编号为０的结点存储到A［0]中。其余类推，则A［ｉ ]元素的左孩子元素为＿_____＿_,右孩子元素为＿__________＿__＿，双亲元素为＿＿＿_＿_______。

11.11.在线性表的散列存储中,处理冲突的常用方法有____＿＿＿___＿

____＿________和___＿＿_＿__＿_________＿_____＿__＿两种。

12.12．当待排序的记录数较大,排序码较随机且对稳定性不作要求时，宜

采用_＿＿_＿______＿___排序；当待排序的记录数较大,存储空间允许且要求排序是稳定时，宜采用_______________＿___＿__＿_排序。

三、运算题（每题6分，共２４分）

1． 已知一个6′５稀疏矩阵如下所示，

试:

(1) 写出它的三元组线性表;

（2） 给出三元组线性表的顺序存储表示。

2． 设有一个输入数据的序列是 ｛ 4６， ２5， 78， ６2, 12，

80 ｝， 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。

3． 对于图６所示的有向图若存储它采用邻接表，并且每个顶点邻

接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：

（1） 从顶点①出发进行深度优先搜索所得到的深度优先生成树;

(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树;

4. 已知一个图的顶点集V 和边集Ｅ分别为：

V ＝{１,2,３,4,5，6，７｝;

Ｅ={<2,1>,<3,2＞,<3,６>，〈４,

３＞，<4，5>，〈４,6〉，<５，1>，＜

5,7〉，＜6，1〉，〈６，２>,〈6，５〉}；

若存储它采用邻接表,并且每个顶

点邻接表中的边结点都是按照终点序

号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。

四、 阅读算法（每题7分，共14分)

1. 1。 int P ｒime(int n ）

{

int i ＝1;

int ｘ=(int) sqrt(n ）；

ｗhile （++i ＜＝x)

if (n%i==0） b ｒeak;

i ｆ （i>x) return １；

ｅｌｓe ｒｅｔur ｎ 0；

｝

????????????????????--00700

0000520000

000100000010000

图6

(1)指出该算法的功能；

（2）该算法的时间复杂度是多少？

2．写出下述算法的功能：

void ＡJ（adｊｌisｔ GＬ，ｉnt i，ｉnt n)

{

ＱｕeuｅＱ;

?ＩｎitQueｕe（Q）;

ｃouｔ＜〈i＜〈' ＇；

visited［ｉ］=truｅ;

?ＱＩｎseｒt（Q，i）;

while(!ＱｕeｕｅＥmpty（Q)) ｛

?int k=QＤｅleｔｅ(Ｑ）;

edgeｎode＊ p＝ＧL[k]；

??whilｅ(p！＝NULＬ）

｛

?ｉｎt ｊ＝p->adjｖｅx;

?? if（!visiｔed［j])

{

?? cout〈＜j<<’ ’;

?? visiｔｅｄ［j］=true;

? QInseｒt(Q,j)；

}

?p=p-〉nｅｘt；

?｝

｝

}

五、算法填空（共8分)

如下为二分查找的非递归算法,试将其填写完整.

Int Ｂiｎsch(ElemTypｅ A［ ]，int n,KeyTyｐe K）

｛

ｉｎｔlｏｗ=０；

ｉnt hiｇh=n-1;

while (ｌｏｗ<＝ｈiｇｈ）

{

int mid=______＿_____＿____＿_＿__＿_＿___＿_＿；

iｆ（K=＝A［mid］。kｅｙ） reｔｕｒn mid； /／查找成功，返回元素的下标

?? else if （K<[ｍid ］。ｋｅy ）

________＿___________________＿__＿_＿__＿_; //在

左子表上继续查找

else ___＿________＿________＿＿_＿_______＿＿; //在右子表上继续查找

}

re ｔurn -１; //查找失败，返回—1

}

六、 编写算法（共8分)

HL 是单链表的头指针，试写出删除头结点的算法。

Ele ｍType DeleF ｒｏn ｔ(LNode ＊ ＆ HL)

参考答案

一、 单选题（每题2分，共20分)

1．B 2.A 3．Ｂ 4.C 5。D 6．B 7.Ｄ 8。A ９.D 10．C

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

１． 联系 图（或图结构)

２。 尾 首

3。 top ＝=０

4。 Ｏ(１） O （n)

5. 128 44 1０8

6． 3 3

７． 有序 n —1

8. 有序序列 后缀表达式(或逆波兰式)

9． 2n n-1 n+1 10． 2ｉ+１ 2i+２ （i —1)／2 １1。 开放定址法 链接法 12。 快速 归并 三、 运算题（每题6分，共2４分）

1。 （1) （（1，5,１）,(3,２，-1),（４，５,－2）,

（５，1，5）,（6,3，7)) (３分) (２) 三元组线性表的顺序存储表示如图7示. 2． 如图8所示。

3. D ＦS: ??……

BFS:??……

4． 拓朴排序为： 4 ３ 6 ５ 7 2 1 6

5 5 1 5 1

3 2 -1

4

5 -2 5 1 5

6 3

7 图7

图8

四、阅读算法（每题７分,共14分)

1。(1) 判断ｎ是否是素数（或质数)

（2）O(n)

２。功能为:从初始点v i出发广度优先搜索由邻接表ＧL所表示的图。

五、算法填空（8 分)

（low+hiｇｈ）/2 ｈiｇh=ｍid-1 ｌoｗ=mid+1

六、编写算法（8分）

ElemＴyｐe ＤeｌeFront(ＬNode ＊＆HL）

{

iｆ（ＨL==ＮＵLL）｛

?cerｒ<〈”空表"〈〈eｎdl;

exit(１）;

｝

LNode* p=HＬ;

HL=HＬ-＞neｘt;

ＥlｅｍTyｐｅteｍp＝ｐ—〉ｄatａ；

deｌete p；

returｎ temp;

}

一、单选题（每题 2 分，共２0分）

１。栈和队列的共同特点是( Ａ）。

Ａ。只允许在端点处插入和删除元素

Ｂ.都是先进后出

C．都是先进先出

D.没有共同点

２。用链接方式存储的队列，在进行插入运算时（ D ）.

Ａ. 仅修改头指针Ｂ．头、尾指针都要修改 C。仅修改尾指针Ｄ．头、尾指针可能都要修改

3.以下数据结构中哪一个是非线性结构？（ D）

A. 队列

B. 栈

C. 线性表Ｄ. 二叉树

4.设有一个二维数组Ａ[ｍ］［n］,假设A[0］［0]存放位置在６44(10）,A

，每个元素占一个空间，问A［3]［3]（1０)存放［2]［2］存放位置在676

(10）

表示用1０进制表示。

在什么位置？脚注

（10)

A.68８ B。６78 Ｃ.692 D。696

5.树最适合用来表示( ）。

A.有序数据元素 B。无序数据元素

C.元素之间具有分支层次关系的数据

D.元素之间无联系的数据

6。二叉树的第k层的结点数最多为( ）．

Ａ．2ｋ-１ B.2Ｋ＋1 C。2K-1 D. ２k －1

7.若有1８个元素的有序表存放在一维数组Ａ［19］中，第一个元素

放A［1］中，现进行二分查找，则查找A［3］的比较序列的下标依次为

（)

Ａ。 1，2，3 ?Ｂ. 9,５，2,３

C. ９，５，3 ????D。 9,4，2,3

8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为

n） D. O(ｎA． O(1）B。O(n）Ｃ. O（１og

2

2）

9。对于线性表（7，34，5５,２５，64，46，２0，10）进行散列存储时，若选用H（K）=K ％9作为散列函数，则散列地址为1的元素有（)个,

A。1 B．2 C．３ D．４10。设有６个结点的无向图，该图至少应有（）条边才能确保是一个连通图。

A.5 Ｂ.６ C.7 D。8

二、填空题（每空１分,共26分)

1。通常从四个方面评价算法的质量:＿___＿＿___、____＿__＿_、____＿__＿_和_________。

2.一个算法的时间复杂度为（n3+n2ｌog2n+１4n）/n２,其数量级表示为____＿___。

3。假定一棵树的广义表表示为A（C,D（E，F，Ｇ），H（I,J）），则树中所含的结点数为__＿_______个，树的深度为＿_＿___＿____，树的度为_________。

4.后缀算式９ 2 3 ＋- 10 2 / -的值为_____＿____.中缀算式(3+4X）-2Y/３对应的后缀算式为_____＿_＿_＿_＿＿_＿＿＿___＿＿＿________.

5。若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有＿___＿___个指针域,其中有________个指针域是存放了地址,有__＿___＿＿____＿___个指针是空指针。

６.对于一个具有ｎ个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有__＿_＿__个和___＿___＿个。

7。AOV网是一种______＿_＿________＿＿的图.

8。在一个具有ｎ个顶点的无向完全图中，包含有________条边,在一个具有n个顶点的有向完全图中,包含有__＿＿＿___条边.

9。假定一个线性表为(１２，23，74,55,6３，4０)，若按Kｅy % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为______＿___＿____＿＿_＿＿________、____＿＿________＿＿___、___________＿___＿＿__＿＿＿_和_＿＿＿___＿___＿________＿__＿__.

１0。向一棵Ｂ_树插入元素的过程中,若最终引起树根结点的分裂，则新树

比原树的高度___＿__＿___＿。

11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为___＿

____,整个堆排序过程的时间复杂度为_____＿__。

１2。在快速排序、堆排序、归并排序中，_＿＿____＿_排序是稳定的。

三、运算题（每题 6 分，共２４分）

1．在如下数组A中链接存储了一个线性表，表头指针为Ａ［0］。next，

试写出该线性表。

A 0 1 2 ３ 4 5

6 7

dat ａ6050789

０

34４

next357２０41

2。请画出图１0的邻接矩阵和邻接表。

3。已知一个图的顶点集V和边集E分别为：

V＝{1,２,３,4,5,６，７｝; E＝

{(１,2）３,（1，3）5,（１,4）8，(2,5)1０，(2,３）

6,(3,4）1５,

（3,５）１2，(3，6)9，（4，6）４，（4，7)20，(5，６）

１８，(6,7）２５}；

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

4．画出向小根堆中加入数据４，2, ５， 8, ３时，每加入一个数据后堆的变化。

四、阅读算法(每题7分，共14分)

1.ＬinkList ｍｙnote(LiｎkLｉｓt L）

｛//Ｌ是不带头结点的单链表的头指针

if(L＆＆L－〉nexｔ）{

q=L；L=Ｌ－〉ｎexｔ；p＝Ｌ;

S1： whｉle（p-〉next) p=p-〉nexｔ;

S2: p－>next＝q;ｑ-〉neｘｔ＝NUＬＬ；

}

return L；

}

请回答下列问题：

（1）说明语句Ｓ1的功能；

(2）说明语句组S2的功能;

图10

（3)设链表表示的线性表为(ａ

1，a

２

, …,a

n

）,写出算法执行后的返回

值所表示的线性表。

２。voiｄＡBC（BTNode ＊ BT)

｛

if BT ｛

ABC (BＴ－＞ｌeｆｔ);

AＢＣ (BＴ－〉rｉｇht);

cout<〈ＢT－＞datａ<<’ ’；

}

}

该算法的功能是:

五、算法填空(共8分）

二叉搜索树的查找—-递归算法：

bool Fiｎd（BＴreeNｏｄｅ* ＢＳT,ＥｌemType＆itｅm）{

if (ＢＳＴ＝＝NULL)

rｅturn faｌｓe； /／查找失败

else ｛

ｉf （itｅｍ==BSＴ-〉daｔａ）｛

iteｍ＝BST－＞daｔa；//查找成功

retuｒｎ＿_＿_＿___＿__；}

else if（iｔem

retuｒｎＦind(____＿___＿___＿_，item）；

else return Finｄ（_____＿＿＿__＿_＿__,ｉtem）；

｝//iｆ

}

六、编写算法（共８分）

统计出单链表HL中结点的值等于给定值Ｘ的结点数。

int ＣountＸ(LNoｄe* HL，ElemＴypｅ x）

参考答案

一、单选题(每题2分，共20分)

1.A 2．D 3。D 4。C 5。C 6.D ７.Ｄ８.Ｃ9。D 10。Ａ

二、填空题（每空1分,共２6分）

1。正确性易读性强壮性高效率

２。O（n）

３．9 3 3

4。 -1 3 4 X ＊ + 2 Y ＊ 3 / -

５。 2n n-1 n+１

6。 ｅ 2e

7. 有向无回路

8. ｎ（n —1）／２ n （n －1)

9. （12，40) （ ) （74) (23,55,６3）

10. 增加１

11． O （l ｏg 2n ） Ｏ(nlog ２n ）

12。 归并

三、 运算题(每题6分，共24分）

1。 线性表为：（78,５０，40，６0，３4,90)

2。 邻接矩阵:????????????????0111010101

110111*********

邻接表如图1１所示：

图１1

3. 用克鲁斯卡尔算法得到的最小生成树为：

（1，2）3， (4，6)4, （1,3)5， (１，4)８， （2,5）10， （4,7）２0

4。 见图１２

图12

四、 阅读算法（每题7分，共14分)

1. (1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点

4 4 4 4 4 2 2 2

5 5 5

2 2 8 8 4

3 5 2

8 3 4

（3）返回的线性表为（a2，a３,…，ａn,a1）

2.递归地后序遍历链式存储的二叉树。

五、算法填空（每空2分，共8 分)

tｒｕｅ BST—＞ｌｅｆt ＢST-〉ｒｉghｔ

六、编写算法（８分)

inｔCｏｕｎtX(LNode* HL，ElｅmTypｅｘ)

{ int i=０；ＬNode* ｐ=HＬ；//ｉ为计数器

ｗhｉｌｅ（p！=NULＬ）

{ if （P－〉ｄata＝＝ｘ）i+＋；

p=ｐ—>nｅxt；

｝／/while，出循环时i中的值即为x结点个数

ｒetuｒn i;

｝//CoｕntＸ

?

一、单选题（每小题2分，共8分）

1、在一个长度为n的顺序线性表中顺序查找值为ｘ的元素时,查找成功时的平均查找长度（即ｘ与元素的平均比较次数,假定查找每个元素的概率都相等）为( )。

Ａ n B n／2 Ｃ (ｎ+1）/2 D (ｎ-１)/2

2、在一个单链表中,若q所指结点是p所指结点的前驱结点，若在q与p之间插入一个s所指的结点，则执行( ).

A s→link=p→ｌink； p→liｎk＝s;

B ｐ→link＝ｓ； s →linｋ=q；

C ｐ→link=s→link; s→linｋ=ｐ；

D q →liｎk＝s；s→lｉnｋ =p；

3、栈的插入和删除操作在（）进行。

A 栈顶

B 栈底

C 任意位置

D 指定位置

4、由权值分别为11,8，6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ )

A ２４

B 71

C 48

D ５3

二、填空题（每空1分,共３２分)

１、数据的逻辑结构被分为__＿_______、 ___＿___＿＿__ 、_____＿＿_和__＿＿___＿四种。

2、一种抽象数据类型包括＿＿＿____＿＿_＿___和_________＿___两个部

分。

3、在下面的数组a中链接存储着一个线性表，表头指针为a［o］.ｎext，

则该线性表为_＿__＿___________＿____________＿_____＿__＿____＿_