云南省-专升本十套-数据结构(试题及答案)

数据结构试卷（一）

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

1. 栈与队列得共同特点就是（ ）.

A、只允许在端点处插入与删除元素

B、都就是先进后出

C、都就是先进先出

Ｄ、没有共同点

2. 用链接方式存储得队列，在进行插入运算时（ )、

A、 仅修改头指针 B、 头、尾指针都要修改

Ｃ、 仅修改尾指针 D、头、尾指针可能都要修改

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

A、 队列 B、 栈 C、 线性表 D、 二叉树

4. 设有一个二维数组

Ａ

[m］[n］，假设A［0］［0］存放位置在644

(10

）

,A[2］［2]存放位

置在676

(10)

,每个元素占一个空间,问A［3][３]

（１

0

）

存放在什么位置？脚注

(10)

表示用

10进制表示。

A．688 B.678 C。6９2 D.69６

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

A、有序数据元素 B、无序数据元素

C、元素之间具有分支层次关系得数据 D、元素之间无联系得数据

6. 二叉树得第k层得结点数最多为（ )、

kk－1

A.2－1 B、2Ｋ+1 C、２K—１ D、 2

7. 若有18个元素得有序表存放在一维数组Ａ［１９］中，第一个元素放A［１］中，

现进行二分查找,则查找Ａ[3］得比较序列得下标依次为( )

A、 1,2，3 ﻩﻩ B、 9，5,2，３

Ｃ、 ９，5,3ﻩ ﻩ ﻩD、 9，4，2，3

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

Ａ、 O（１） B、 O（n) C、 Ｏ(1ｏg

2

n） D、 O（n2)

9. 对于线性表（７,34，55，25,64,4６，2０,10)进行散列存储时，若选用H(K）=K %9

作为散列函数，则散列地址为1得元素有( )个，

A。１ B。2 C。3 D。４

10. 设有６个结点得无向图,该图至少应有( )条边才能确保就是一个连通图。

A、5 B、6 C、7 D、8

二、填空题(每空1分,共２６分)

1. 通常从四个方面评价算法得质量：_____＿＿__、＿________、_________与＿___＿＿_

＿_。

３

2. 一个算法得时间复杂度为（n+n

2

log

2

ｎ

+1４

ｎ

)/

ｎ

2

，其数量级表示为_____＿__。

3. 假定一棵树得广义表表示为A（C，Ｄ(E，F,G)，H（I，Ｊ））,则树中所含得结点数为_。-

_＿___＿___个,树得深度为__＿___＿____，树得度为＿______＿＿。

4. 后缀算式9 2 ３ +— 1０ 2 ／ —得值为__＿__＿__＿＿。中缀算式（3+4X）—2Y/3

对应得后缀算式为＿______＿_______＿＿__＿＿_________＿。

5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子与右孩子得两个指

针。在这种存储结构中，n个结点得二叉树共有＿_______个指针域,其中有_＿_____＿

个指针域就是存放了地址，有_＿____＿___＿___＿_个指针就是空指针.

6. 对于一个具有n个顶点与e条边得有向图与无向图，在其对应得邻接表中，所含边结点

分别有_＿_____个与__＿_____个。

7. AOV网就是一种____________＿＿_____得图。

8. 在一个具有n个顶点得无向完全图中，包含有_______＿条边，在一个具有n个顶点得

有向完全图中，包含有___＿_＿＿_条边。

9. 假定一个线性表为（12,２3，７4，55,63，4０），若按Kｅy ％ 4条件进行划分,使得同

一余数得元素成为一个子表,则得到得四个子表分别为＿＿＿＿____＿_＿_______＿＿

＿__＿____、__＿＿＿____＿＿＿＿_＿＿___、_＿___＿_＿_＿_____＿＿＿_____与_

＿__＿_＿____＿___＿＿_＿___＿___。

10. 向一棵B_树插入元素得过程中，若最终引起树根结点得分裂，则新树比原树得高度

___________。

11. 在堆排序得过程中,对任一分支结点进行筛运算得时间复杂度为____＿_＿_，整个堆排

序过程得时间复杂度为___＿＿___。

12. 在快速排序、堆排序、归并排序中，____＿____排序就是稳定得。

三、计算题(每题 6 分,共2４分)

1. 在如下数组A中链接存储了一个线性表，表头指针为A ［０]、nｅxt，试写出该线性

表。

A 0 1 2 3 4 5 6

7

daｔ ６

ａ

next 3 5 ７ 2 0 4 1

2. 请画出下图得邻接矩阵与邻接表.

3. 已知一个图得顶点集V与边集Ｅ分别为:Ｖ={1，2，

３，4，5,6，7｝;

E＝{（1,2)3，（1，3）5,（1，4）8,（2,5）1０，

(２,3)６,(3，4)1５，

（3，5)12，（3，6）9,(４，6)4，(4,7)20，(5,6)18，

（6,7）25｝;

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

4. 画出向小根堆中加入数据4, 2， 5， 8, 3时,每加入一个数据后堆得变化.

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

1. ＬinkList mynote(LinkLisｔ L)

{//L就是不带头结点得单链表得头指针

if（Ｌ＆＆L-＞next)｛

q=Ｌ;L=Ｌ－〉next；p=L；

S1： whｉle(p－>next） ｐ=p—>nexｔ;

S2： p－〉next=q；q－>nexｔ=NULL；

}

reｔurn L;

}

请回答下列问题:

（1）说明语句S１得功能;

（２)说明语句组S2得功能;

（３）设链表表示得线性表为（a

１

，a

2

， …，a

n

),写出算法执行后得返回值所表示

得线性表。

2. ｖoiｄ ABＣ(BTＮｏdｅ ＊ ＢＴ)

｛

ｉf BT {

AＢC （ＢＴ—＞leｆｔ）；

AＢC （BT-＞ｒiｇht）；

couｔ<

}

｝

该算法得功能就是:

五、算法填空（共8分）

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

bool Ｆinｄ（ＢＴrｅeNode＊ BSＴ，ElｅｍＴｙpe＆ item）

｛

if （ＢST==NUＬL）

ｒetuｒn ｆalse； //查找失败

eｌse {

if （ｉtem==ＢST-〉data）{

ｉtem=ＢST—＞data;/／查找成功

return .。。＿___＿_＿＿___;}

ｅlse iｆ（item<ＢST－〉data)

ｒeｔuｒｎ Ｆiｎｄ（___________＿__,itｅm）；

elｓe reｔuｒn Fｉnd(_____＿_＿_____＿_，iteｍ)；

｝//ｉf

}

六、编写算法(共8分）

统计出单链表HＬ中结点得值等于给定值Ｘ得结点数。

ｉnt ＣounｔＸ（LNｏdｅ* HL，ＥｌeｍＴｙpｅ x)

数据结构试卷(二）

一、选择题(24分）

1.下面关于线性表得叙述错误得就是（ )。

(A) 线性表采用顺序存储必须占用一片连续得存储空间

(B) 线性表采用链式存储不必占用一片连续得存储空间

(Ｃ） 线性表采用链式存储便于插入与删除操作得实现

（D) 线性表采用顺序存储便于插入与删除操作得实现

2。设哈夫曼树中得叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共

有（ ）个空指针域。

（A） ２m－1 (Ｂ) 2m （C） ２m+1 (D） ４m

3。设顺序循环队列Q[0：M—1]得头指针与尾指针分别为Ｆ与R，头指针Ｆ总就是指向队头

元素得前一位置，尾指针Ｒ总就是指向队尾元素得当前位置,则该循环队列中得元素个数

为( ）。

（A） R－F （B） F—Ｒ （C) （Ｒ—F＋Ｍ）％Ｍﻩ(D） (F—R+Ｍ）%Ｍ

４。设某棵二叉树得中序遍历序列为ＡBCD,前序遍历序列为CＡＢD，则后序遍历该二叉树

得到序列为（ ）。

ﻩ(A） ＢADCﻩ(B） BCＤAﻩ(C) CDAB （D） CBＤA

５.设某完全无向图中有ｎ个顶点，则该完全无向图中有（ ）条边.

22

(Ａ） n(n—1）／２ (B) n(n-1） （Ｃ） n （D) n－１

6.设某棵二叉树中有2０00个结点,则该二叉树得最小高度为( ）。

ﻩ（A) ９ﻩ（B） １0 （C) 11 (D） 12

7.设某有向图中有n个顶点，则该有向图对应得邻接表中有( )个表头结点.

ﻩ(Ａ) ｎ—1 （Ｂ) n （C) n+1 （D） 2n－1

8.设一组初始记录关键字序列（5,2，6,3,8），以第一个记录关键字5为基准进行一趟快速

排序得结果为( ）。

（Ａ) ２,3,5，８,6 ﻩ(B） 3,2，5,8，6

（C) ３，２，5，6,8 （D） 2，３，6，5,8

二、填空题（24分)

1. 为了能有效地应用HASH查找技术，必须解决得两个问题就是___＿＿__＿＿

___________与__＿______＿＿______＿＿____＿_＿.

2. 下面程序段得功能实现数据ｘ进栈,要求在下划线处填上正确得语句.

typedef strucｔ ｛int s[1０0］; int toｐ；} sqsｔaｃk;

ｖｏｉd pｕsh(sｑｓｔａck ＆staｃk，inｔ x)

{

if (sｔａck、ｔoｐ==m－1） pｒinｔf(“ｏｖerfloｗ”)；

ｅｌse ｛__＿___＿________＿__＿_；___＿＿_______＿____；｝

}

3. 中序遍历二叉排序树所得到得序列就是_＿__＿_＿___＿序列(填有序或无序）。

4. 快速排序得最坏时间复杂度为_＿___＿__＿__，平均时间复杂度为________＿_。

5. 设某棵二叉树中度数为0得结点数为N

0

,度数为1得结点数为N

1

，则该二叉树中度数为

2得结点数为＿_______＿；若采用二叉链表作为该二叉树得存储结构，则该二叉树中

共有__＿____个空指针域。

6. 设某无向图中顶点数与边数分别为ｎ与ｅ，所有顶点得度数之与为d，则e=＿＿＿____.

7. 设一组初始记录关键字序列为(55，63，44，3８，75,80,３１,56)，则利用筛选法建立

得初始堆为_____＿＿_____＿__＿_＿______＿_＿。

8. 已知一有向图得邻接表存储结构如下:从顶点１出发,DFS遍历得输出序列就是

,ＢFS遍历得输出序列就是

三、应用题(3６分）

1． 设一组初始记录关键字序列为(4５,80,4８,40，22,７８）,则分别给出第４趟简单选择

排序与第4趟直接插入排序后得结果。

2． 设指针变量p指向双向链表中结点Ａ,指针变量q指向被插入结点B，要求给出在结点A

得后面插入结点B得操作序列（设双向链表中结点得两个指针域分别为llink与rlink）。

3． 设一组有序得记录关键字序列为(１3，18,24,35,47,50，６2，83，90)，查找方法用二

分查找，要求计算出查找关键字62时得比较次数并计算出查找成功时得平均查找长度。

4． 设一棵树T中边得集合为{（A,Ｂ）,（A，C），（A，Ｄ），（B，Ｅ),（Ｃ,F），(Ｃ,G)｝,

要求用孩子兄弟表示法（二叉链表)表示出该树得存储结构并将该树转化成对应得二叉

树。

5． 设有无向图G,要求给出用普里姆算法构造最小生成树所走过得边得集合。

6． 设有一组初始记录关键字为(45，８0,48,4０，22，7８）,要求构造一棵二叉排序树并

给出构造过程.

四、算法设计题（1６分)

1． 设有一组初始记录关键字序列（K

１

，K

２

,…,K

n

)，要求设计一个算法能够在O(n）得时间

复杂度内将线性表划分成两部分,其中左半部分得每个关键字均小于K

ｉ

,右半部分得每

个关键字均大于等于K

i

。

2． 设有两个集合A与集合Ｂ，要求设计生成集合C=A∩B得算法,其中集合A、B与C用链

式存储结构表示。

数据结构试卷（三)

一、选择题（每题1分,共20分）

１。设某数据结构得二元组形式表示为A=（D,Ｒ),D＝{01，０2，０３，04,0５,06,07，08，

０9}，R=｛ｒ｝,ｒ={＜0１,０2〉，<01,03〉，<01，0４〉，<02，05>,<02,06〉，<03,0７>，

<０３,０８>,＜03,09〉｝，则数据结构Ａ就是（ )。

ﻩ（A) 线性结构 （Ｂ) 树型结构ﻩ（C) 物理结构 （D） 图型结构

2．下面程序得时间复杂为（ )

ｆｏr(ｉ＝1，s=0； i〈=n； i+＋) ｛t＝１;fｏr（ｊ=1;j<=ｉ;j++） t=t＊ｊ；s=s＋t；｝

２３4

(A) O（n） （B） O（n)ﻩ(C） O（n)ﻩﻩ（D) O（n）

3.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针得操作序列

为（ )。

(Ａ) q=ｐ－＞next；p－>ｄata＝ｑ－＞data；ｐ—〉next＝q—〉ｎext;free（q)；

（Ｂ） ｑ=p-〉ｎext；q—>data=p—>ｄata；p—〉next=q—〉nｅxt；fｒee(q);

（C) q=ｐ->nｅｘt；p—〉neｘt＝q—＞neｘt；free(ｑ）;

(Ｄ) q=p—＞ｎext；ｐ-〉data=q—〉datａ；free（q);

4。设有n个待排序得记录关键字，则在堆排序中需要( )个辅助记录单元.

2

ﻩ（Ａ) 1ﻩ(Ｂ） ｎ （C) nｌog

2

ｎ （Ｄ） n

５.设一组初始关键字记录关键字为(20，15，14，18，２１,36，4０，10),则以20为基准

记录得一趟快速排序结束后得结果为（ )。

（A) 1０,15，14，１8，20,36，40，21

ﻩ（B) １0，１5,１4，１8,20,40，36，21

(C） １0，１５，14,20,18,４0,36，2l

ﻩ（D） 15,10,1４,1８，2０,36,40，21

6．设二叉排序树中有ｎ个结点,则在二叉排序树得平均平均查找长度为( ）。

２

ﻩ（Ａ） O（1) （B） O(log

2

n）ﻩ（C）ﻩ（Ｄ) O(ｎ）

7。设无向图G中有n个顶点e条边,则其对应得邻接表中得表头结点与表结点得个数分别为

( )。

(A） n,eﻩ(Ｂ） e，ｎﻩ(C） 2n，ｅﻩ（D) n,２e

8、 设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。

（A) n(n—1）ﻩ（B) n+1ﻩ(C） ｎﻩ（D) n(ｎ+１）

9。设有500０个待排序得记录关键字，如果需要用最快得方法选出其中最小得１0个记录关

键字,则用下列（ )方法可以达到此目得。

(A) 快速排序ﻩ（B） 堆排序ﻩ（Ｃ） 归并排序 (D） 插入排序

1０、下列四种排序中（ )得空间复杂度最大。

ﻩ（A） 插入排序 (B) 冒泡排序ﻩ（Ｃ） 堆排序 (D） 归并排序

二、填空殖（每空1分 共20分）

1. 数据得物理结构主要包括___＿_________与__＿___________两种情况.

2. 设一棵完全二叉树中有50０个结点,则该二叉树得深度为_＿____＿___；若用二叉链表

作为该完全二叉树得存储结构,则共有___________个空指针域。

3. 设输入序列为1、２、3，则经过栈得作用后可以得到＿______＿__＿种不同得输出序

列。

4. 设有向图Ｇ用邻接矩阵A［n]［n］作为存储结构,则该邻接矩阵中第i行上所有元素之

与等于顶点i得＿__＿__＿_,第i列上所有元素之与等于顶点i得__＿_＿＿__。

5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有＿_＿_____个度数为１得结点。

6. 设有向图Ｇ中有n个顶点e条有向边，所有得顶点入度数之与为d，则e与d得关系为

_＿_______。

7. ＿＿__＿___＿_遍历二叉排序树中得结点可以得到一个递增得关键字序列(填先序、中

序或后序)。

8. 设查找表中有100个元素,如果用二分法查找方法查找数据元素Ｘ，则最多需要比较__

＿＿_＿＿_次就可以断定数据元素X就是否在查找表中。

9. 不论就是顺序存储结构得栈还就是链式存储结构得栈，其入栈与出栈操作得时间复杂度

均为___＿__＿＿___＿。

10. 设有ｎ个结点得完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第

ｉ个结点得双亲结点编号为____＿__＿_＿_＿,右孩子结点得编号为______＿＿___。

11. 设一组初始记录关键字为（7２,73，７1,２3，94，16,５),则以记录关键字72为基准

得一趟快速排序结果为__＿＿_______＿＿__＿＿＿___＿____＿。

12. 设有向图G中有向边得集合E=｛〈1,2〉，〈2，3>,<1,4〉,＜4，2>，<4，3〉｝,则该图得一

种拓扑序列为________＿＿___＿____＿_。

13. 下列算法实现在顺序散列表中查找值为ｘ得关键字，请在下划线处填上正确得语句。

struct record｛ｉnt key； ｉnt otｈeｒs；｝;

int hashsqsｅａｒｃｈ（struct ｒecorｄ haｓhtable［ ］，int ｋ)

｛

ｉｎt i，j; j=i=k ％ ｐ；

whilｅ （hashtable［j］、key！=k＆&haｓｈｔablｅ［ｊ]、flaｇ!=０){ｊ=(_＿_＿） %m；

if (i==ｊ) reｔurn（－1）;}

ｉf （______＿______＿____＿_＿＿_ ) returｎ(j）； elｓe return(—１）;

}

14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确得语句.

typedef stｒuct nｏｄe｛int ｋey； ｓｔｒｕct nｏde ＊ｌｃhiｌｄ； strｕct nｏde

＊ｒchｉlｄ;}bｉｔｒee;

ｂｉtreｅ ＊bstsearch（bitree *t, ｉnｔ k)

{ ﻩ

if (ｔ==0 ） rｅturn（0)；elｓe while （t!=0）

ｉｆ (t－〉ｋey＝=k）＿__________＿_； elｓｅ if （t->keｙ〉k） t＝t—〉

lcｈild; eｌｓe__＿＿＿_＿______；

}

三、计算题(每题1０分,共30分）

1、已知二叉树得前序遍历序列就是AEFBGCDHIKJ，中序遍历序列就是EＦＡGBCHKIJD,

画出此二叉树，并画出它得后序线索二叉树.

2。已知待散列得线性表为（３6，１５,40,63，22),散列用得一维地址空间为[0、、6］，假定

选用得散列函数就是H(K)= Ｋ mod ７,若发生冲突采用线性探查法处理,试：

(１)计算出每一个元素得散列地址并在下图中填写出散列表：

`

0 １ ２ 3 4 5

6

（2）求出在查找每一个元素概率相等情况下得平均查找长度。

3.已知序列（10，18，4，3，6，12，1,9,１8,8)请用快速排序写出每一趟排序得结果。

四、算法设计题(每题１5分,共３0分）

1． 设计在单链表中删除值相同得多余结点得算法。

2． 设计一个求结点x在二叉树中得双亲结点算法。

数据结构试卷（四)

一、选择题（每题1分共 20分)

１。设一维数组中有n个数组元素，则读取第i个数组元素得平均时间复杂度为( ）。

2

ﻩ（A) O（n）ﻩ(B） O(nlog

2

n) (C） Ｏ(１）ﻩ（D) Ｏ（n）

2.设一棵二叉树得深度为k,则该二叉树中最多有（ ）个结点.

kk-1k

ﻩ（A) ２k—１ (B) 2ﻩ(C） 2 (D) 2—1

3.设某无向图中有n个顶点e条边,则该无向图中所有顶点得入度之与为( ）。

(A） nﻩ(B) eﻩ（C) ２n （D） 2e

4。在二叉排序树中插入一个结点得时间复杂度为( ）。

2

(A） O（１)ﻩ（B） O（n）ﻩ（C） O（loｇ

2

n）ﻩ（D） O（n)

5。设某有向图得邻接表中有n个表头结点与m个表结点，则该图中有（ )条有向边.

ﻩ(A) n （B） n-1ﻩ（C) mﻩ(D） m－1

6．设一组初始记录关键字序列为(３4５,2５3，６74，9２4，627)，则用基数排序需要进行

（ ）趟得分配与回收才能使得初始关键字序列变成有序序列。

ﻩ（Ａ) 3ﻩ（B） 4ﻩ（C) 5ﻩ（D) 8

7.设用链表作为栈得存储结构则退栈操作（ )。

（Ａ） 必须判别栈就是否为满ﻩ（Ｂ） 必须判别栈就是否为空

ﻩ(Ｃ) 判别栈元素得类型 （D) 对栈不作任何判别

8。下列四种排序中（ ）得空间复杂度最大。

ﻩ(Ａ） 快速排序ﻩ（B） 冒泡排序ﻩ（Ｃ) 希尔排序ﻩ(D) 堆

9.设某二叉树中度数为０得结点数为Ｎ

0

,度数为1得结点数为N

l

，度数为２得结点数为Ｎ

２

,

则下列等式成立得就是（ ）。

ﻩ(A） N

0

＝N

1

＋1ﻩ（B） N

0

=N

l

+N

2

(C) Ｎ

0

=N

2

+1 （D） Ｎ

0

=2N

1

＋l

１0、设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素Ｘ得最多比较次数

不超过（ ）。

(A） lｏg

2

n＋1 (B） log

2

n—1 （C） log

２

n （D） log

2

（ｎ+1）

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

1． 设有n个无序得记录关键字，则直接插入排序得时间复杂度为＿_＿＿____,快速排序得

平均时间复杂度为_＿＿__＿__＿。

2． 设指针变量p指向双向循环链表中得结点X，则删除结点X需要执行得语句序列为＿_

＿____＿_____＿__________＿＿______＿_＿__＿__＿＿__＿____＿_＿____＿(设结

点中得两个指针域分别为llink与ｒliｎk).

3． 根据初始关键字序列（19，22,0１，３8，10)建立得二叉排序树得高度为__＿____＿__

＿_。

4． 深度为k得完全二叉树中最少有___________＿个结点。

5． 设初始记录关键字序列为(K

１

，Ｋ

2

，…，K

n

)，则用筛选法思想建堆必须从第___＿_＿个

元素开始进行筛选.

6． 设哈夫曼树中共有99个结点,则该树中有＿_＿___＿__个叶子结点；若采用二叉链表作

为存储结构,则该树中有＿＿＿＿_个空指针域。

7． 设有一个顺序循环队列中有M个存储单元,则该循环队列中最多能够存储___＿＿＿__

个队列元素；当前实际存储＿＿_＿_＿_＿＿＿__＿___个队列元素(设头指针Ｆ指向当

前队头元素得前一个位置，尾指针指向当前队尾元素得位置)。

8． 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中____

＿__个数据元素;删除第i个位置上得数据元素需要移动表中＿______个元素.

9． 设一组初始记录关键字序列为（20,18，22,１６,30，19）,则以２0为中轴得一趟快速排

序结果为___＿______＿_____＿＿＿___＿＿__＿＿＿_。

10．设一组初始记录关键字序列为（2０，18，2２,１6，30，1９）,则根据这些初始关键字

序列建成得初始堆为_________＿＿_＿＿__＿___＿___。

11．设某无向图G中有n个顶点,用邻接矩阵A作为该图得存储结构,则顶点i与顶点j互为

邻接点得条件就是_＿__＿＿＿___＿＿_____＿____。

12．设无向图对应得邻接矩阵为A,则A中第ｉ上非0元素得个数____＿_＿__第i列上非0

元素得个数（填等于，大于或小于)。

13．设前序遍历某二叉树得序列为ＡBCD,中序遍历该二叉树得序列为ＢADC，则后序遍历

该二叉树得序列为＿＿______＿＿__＿。

14．设散列函数H（k)＝k ｍod ｐ，解决冲突得方法为链地址法.要求在下列算法划线处填

上正确得语句完成在散列表ｈasｈtaｌｂe中查找关键字值等于k得结点，成功时返回

指向关键字得指针,不成功时返回标志0。

ｔｙpedef ｓtruｃt noｄe ｛ｉnt key; strｕｃt nｏdｅ *ｎext；} lkliｓt；

ｖｏid crｅatelkｈaｓh(lklist ＊hａｓhtable[ ］）

{

inｔ i,ｋ; lkｌｉst ＊ｓ;

ｆor（i=０;i〈m；i＋+）_＿_______＿____＿______；

for（ｉ＝０;ｉ＜ｎ；ｉ++）

{

s=（lklist *)malloc(ｓizeof(lkｌiｓt））; s－＞key=a[i]；

ｋ＝a[i］ ％ ｐ； s-＞next=hａｓhtablｅ[k]；_＿_＿___________＿__＿＿___；

}

｝

三、计算题（每题10分,共30分）

１、画出广义表LS=(（ ) , （e） , (a ， （b , c , ｄ ）））得头尾链表存储结构。

２、下图所示得森林:

（1) 求树（a)得先根序列与后根序列;

（2) 求森林先序序列与中序序列;

（3）将此森林转换为相应得二叉树;

2

3、设散列表得地址范围就是［ 0、、９ ],散列函数为H(ｋeｙ）= （kｅy +2)MOD 9,并采

用链表处理冲突，请画出元素7、４、５、3、６、2、8、９依次插入散列表得存储结构。

四、算法设计题(每题1０分,共3０分）

1． 设单链表中有仅三类字符得数据元素（大写字母、数字与其它字符），要求利用原单链

表中结点空间设计出三个单链表得算法,使每个单链表只包含同类字符。

2. 设计在链式存储结构上交换二叉树中所有结点左右子树得算法.

3. 在链式存储结构上建立一棵二叉排序树。

数据结构试卷（五）

一、选择题(20分）

1。数据得最小单位就是（ )。

ﻩ（Ａ） 数据项ﻩ（Ｂ) 数据类型 (C） 数据元素 （D) 数据变量

2．设一组初始记录关键字序列为(50,40,9５，20,15,７0，６0,4５),则以增量d=4得一趟

希尔排序结束后前4条记录关键字为( ）。

ﻩ(Ａ) 40,５0,２0，95 （Ｂ) 15，４0,6０,２0

ﻩ（Ｃ） 15，20，40,45 （Ｄ） 45,４0,15，20

3。设一组初始记录关键字序列为（２5,5０,１5，３5,８0，８5,20，４0,36，70）,其中含有

5个长度为2得有序子表，则用归并排序得方法对该记录关键字序列进行一趟归并后得

结果为（ ）。

(A） 15，2５，３５，50,20,40，80，８5,36，7０

（B） １5,２5,３5，５０，８０，20,8５，4０,7０,36

(Ｃ） １5，25,3５，50，80，８5，2０,36,40,70

（Ｄ） １５,2５,35，50，８0，２0,36，40,70，８5

4．函数sｕbstr(“DAＴASTRUCTURE”，5，9）得返回值为（ )。

（A） “STRUCTURE” （B） “DＡＴＡ”

(C) “AＳTRUＣTＵR” (D） “DＡTASＴRUCTＵRE"

5。设一个有序得单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,

则该操作得时间复杂度为（ ）。

2

(A) O（log

２

ｎ） （B) O(１）ﻩ(C） O(n)ﻩ（Ｄ） O(n）

６.设一棵m叉树中度数为0得结点数为N

０

,度数为１得结点数为Ｎ

ｌ

，……,度数为ｍ得结

点数为Nｍ,则N

0

=( ）。

ﻩ（A） Ｎ

ｌ

+N

2

+……+Ｎmﻩ (Ｂ） l+N

２

+2N

3

+３N

4

+……+（m－1)Nｍ

ﻩ（C） Ｎ

2

+2Ｎ

3

+3N

4

+……+(m—1)Nｍ (Ｄ) 2N

l

+3Ｎ

2

＋……＋（m+1）Nm

７.设有序表中有1０00个元素，则用二分查找查找元素Ｘ最多需要比较（ )次。

(A） 25 （B) 1０ （Ｃ） 7 ﻩ(D) 1

8。设连通图Ｇ中得边集E=｛(a,ｂ),(a，e)，（ａ，c）,（ｂ,e），（e，d），(d，f),（f，c)},则

从顶点ａ出发可以得到一种深度优先遍历得顶点序列为( ）。

（A) ａbedfc (B) acfeｂd (C） aeｂｄｆcﻩ (Ｄ) aｅdｆｃｂ

9。设输入序列就是1、2、３、……、n,经过栈得作用后输出序列得第一个元素就是ｎ,则

输出序列中第i个输出元素就是（ ）。

ﻩ(A） n－i (B） n-1-iﻩ(C) n+1—iﻩ (D） 不能确定

1０ 设一组初始记录关键字序列为(4５,80,55，40，42,85）,则以第一个记录关键字45为

基准而得到一趟快速排序得结果就是( ）。

ﻩ(A） 4０，4２,45，5５，８0,83ﻩ（B） ４２,40,４5，８0，85，88

ﻩ（C） 42，４０，4５,55，8０,８5 (Ｄ) 4２,40,45，85，55,8０

二、填空题（共２0分)

1. 设有一个顺序共享栈S[0：n—1]，其中第一个栈项指针tｏp1得初值为－1,第二个栈

顶指针toｐ2得初值为n,则判断共享栈满得条件就是______＿_＿___＿_____＿_.

2. 在图得邻接表中用顺序存储结构存储表头结点得优点就是__＿_＿_＿_＿＿_＿＿＿

____＿_。

3. 设有一个n阶得下三角矩阵A,如果按照行得顺序将下三角矩阵中得元素（包括对角线

上元素)存放在n（n+1）个连续得存储单元中,则A[i］[j］与A[0][０］之间有_____

＿＿个数据元素。

4. 栈得插入与删除只能在栈得栈顶进行,后进栈得元素必定先出栈，所以又把栈称为__＿_

＿＿__＿_表;队列得插入与删除运算分别在队列得两端进行，先进队列得元素必定先出

队列,所以又把队列称为_____＿__＿表。

5. 设一棵完全二叉树得顺序存储结构中存储数据元素为ＡBＣDEＦ，则该二叉树得前序遍

历序列为_＿___＿＿＿_＿_，中序遍历序列为______＿_＿__，后序遍历序列为

___________。

6. 设一棵完全二叉树有1２8个结点,则该完全二叉树得深度为＿＿＿_____，有____＿

____＿个叶子结点.

7. 设有向图G得存储结构用邻接矩阵A来表示,则A中第ｉ行中所有非零元素个数之与等

于顶点ｉ得___＿____，第i列中所有非零元素个数之与等于顶点i得＿________＿。

8. 设一组初始记录关键字序列（k

1

，ｋ

２

，……，k

n

）就是堆，则对i=1，2,…，ｎ/２而

言满足得条件为__＿_______＿_＿__＿__＿_＿________＿_。

9. 下面程序段得功能就是实现冒泡排序算法，请在下划线处填上正确得语句.

ｖｏid ｂubbｌe（int r[n］)

｛

fｏr（i=１；i<=n—1； ｉ+＋)

｛

ｆor（eｘcｈange=０，j=0； ｊ<________＿＿_＿_；j＋+）

if （r[j］>r［j＋１］）｛teｍp=ｒ[j+1］；_＿________＿___；r[j］=teｍp;exchange

＝１；｝

ｉf （excｈaｎge==0) rｅｔurn;

｝

}

10. 下面程序段得功能就是实现二分查找算法,请在下划线处填上正确得语句。

strｕct record｛int key； iｎｔ ｏthｅrｓ；｝；

iｎt biseaｒch(stｒuct recorｄ r[ ］， iｎｔ k）

｛

int loｗ＝0，mｉd，ｈigｈ=ｎ—1；

ｗｈile（ｌow<＝high）

{

＿＿__＿______＿___＿__＿___＿___＿_____；

iｆ（ｒ[miｄ]、ｋeｙ==k) reｔurn（mｉd+1）； elsｅ if（_＿＿___＿_____）

high=mid—１；eｌse lｏｗ=mid+１；

｝

returｎ(0);

}

三、应用题（3２分）

1. 设某棵二叉树得中序遍历序列为DBEＡC,前序遍历序列为ABＤＥC，要求给出该二叉树

得得后序遍历序列.

2. 设无向图Ｇ(如右图所示)，给出该图得最小生成树上边得集合并计算最小生成树各边上

得权值之与.

3. 设一组初始记录关键字序列为（15,17，18，22，35，5１,６0）,要求计算出成功查找

时得平均查找长度。

4. 设散列表得长度为8，散列函数H（k)=ｋ mod 7,初始记录关键字序列为（2５,31,８,

２７,１3，68）,要求分别计算出用线性探测法与链地址法作为解决冲突方法得平均查

找长度.

四、算法设计题(28分）

1． 设计判断两个二叉树就是否相同得算法。

2． 设计两个有序单链表得合并排序算法.

数据结构试卷(六）

一、选择题（3０分)

1。 设一组权值集合W=｛2,3，4,5,6}，则由该权值集合构造得哈夫曼树中带权路径长度之

与为（ ).

（Ａ） 20 （B） 30ﻩ（C) 40 (D） ４５

2.执行一趟快速排序能够得到得序列就是（ ）。

ﻩ(A) ［４1，12,３4，45,27］ 55 [7２,63]

（B) [45，34,1２，4１］ 5５ [72,６３，27]

(Ｃ） [６3，１2，3４，45，27] 55 [4１,7２］

（D） ［１2，２7,45，4１] 5５ ［34，６3,７2］

3.设一条单链表得头指针变量为head且该链表没有头结点,则其判空条件就是( ）.

（A） hｅａｄ＝=0ﻩﻩ(B) hｅad－〉neｘｔ=＝0

（C) head—＞ｎext==ｈｅad (D) head!=0

4.时间复杂度不受数据初始状态影响而恒为O（ｎlog

２

ｎ)得就是( ）。

ﻩ（A) 堆排序 (Ｂ) 冒泡排序 (Ｃ） 希尔排序ﻩ（D) 快速排序

5。设二叉树得先序遍历序列与后序遍历序列正好相反,则该二叉树满足得条件就是（ ）。

(A） 空或只有一个结点 （B) 高度等于其结点数

ﻩ(C) 任一结点无左孩子ﻩ(D） 任一结点无右孩子

6．一趟排序结束后不一定能够选出一个元素放在其最终位置上得就是（ ）。

ﻩ(Ａ） 堆排序ﻩ(B） 冒泡排序 （C) 快速排序ﻩ(D） 希尔排序

7。设某棵三叉树中有40个结点,则该三叉树得最小高度为（ ）。

ﻩ（A） 3 (B） 4 （C） 5 (Ｄ） 6

8。顺序查找不论在顺序线性表中还就是在链式线性表中得时间复杂度为（ ）。

21／２

(Ａ） O（n)ﻩ(B) Ｏ(n） (Ｃ） O(n）ﻩ（D） O（１og

２

n）

９。二路归并排序得时间复杂度为（ )。

２

(Ａ） O（n） （B) O(n）ﻩ（C) O(nlｏｇ

2

n） (D） Ｏ（1oｇ

2

ｎ）

10、 深度为ｋ得完全二叉树中最少有( ）个结点。

k—1k-１k-1k

(A) 2—1 (Ｂ） 2ﻩ（C) 2+1ﻩ(D) ２－1

11、设指针变量front表示链式队列得队头指针，指针变量rear表示链式队列得队尾指针，

指针变量s指向将要入队列得结点X,则入队列得操作序列为( ).

(A） froｎt-＞next=s;fｒonｔ=ｓ； （Ｂ） ｓ－〉nexｔ=reaｒ；rear

＝s;

（Ｃ) rear—>ｎeｘt=s;ｒeａr＝s；ﻩ（D) s—〉ｎeｘt＝front；front=s;

１2、设某无向图中有n个顶点e条边,则建立该图邻接表得时间复杂度为（ )。

23

（A） O（ｎ+ｅ) (B） Ｏ(ｎ）ﻩ(Ｃ) O（ne)ﻩ（D） O(n）

13、设某哈夫曼树中有1９9个结点,则该哈夫曼树中有( )个叶子结点。

（A) 99ﻩ(B） 1００ （C) 1０１ﻩ(D） １02

1４、设二叉排序树上有n个结点，则在二叉排序树上查找结点得平均时间复杂度为( ）.

2

ﻩ（A) Ｏ(n） (Ｂ） O（n)ﻩ(C） O（nloｇ

2

ｎ） （D) O(１og

2

n）

1５、设用邻接矩阵A表示有向图Ｇ得存储结构，则有向图G中顶点i得入度为（ ）。

（A) 第ｉ行非0元素得个数之与 (B） 第ｉ列非0元素得个数之与

ﻩ(Ｃ） 第ｉ行0元素得个数之与 (D） 第i列0元素得个数之与

二、判断题(20分)

1．调用一次深度优先遍历可以访问到图中得所有顶点。( ）

2.分块查找得平均查找长度不仅与索引表得长度有关,而且与块得长度有关.( )

３。冒泡排序在初始关键字序列为逆序得情况下执行得交换次数最多。（ )

4.满二叉树一定就是完全二叉树,完全二叉树不一定就是满二叉树。（ )

5．设一棵二叉树得先序序列与后序序列，则能够唯一确定出该二叉树得形状.（ ）

6.层次遍历初始堆可以得到一个有序得序列.（ )

7.设一棵树T可以转化成二叉树BT，则二叉树BＴ中一定没有右子树。（ ）

8.线性表得顺序存储结构比链式存储结构更好.( ）

９。中序遍历二叉排序树可以得到一个有序得序列。( )

10、快速排序就是排序算法中平均性能最好得一种排序。（ ）

三、填空题（30分）

1．for(ｉ=1，t＝1,s=0;i〈＝n;i+＋） ｛t=t*i；s=s+t；｝得时间复杂度为_____＿___。

2。设指针变量p指向单链表中结点A，指针变量ｓ指向被插入得新结点X，则进行插入操作

得语句序列为_＿____＿________＿__＿＿_＿＿___（设结点得指针域为neｘt)。

3。设有向图G得二元组形式表示为G =(D,R)，D＝｛１,2,3,4,5},R=｛r｝,ｒ={＜１,2〉，〈2，

4>,＜4，５>，＜1,３＞,＜3,2>,＜3,5>｝,则给出该图得一种拓扑排序序列_＿＿___＿＿_

＿。

４．设无向图G中有n个顶点,则该无向图中每个顶点得度数最多就是_______＿＿。

５.设二叉树中度数为０得结点数为５0,度数为1得结点数为30，则该二叉树中总共有＿_

＿___＿个结点数。

６。设F与R分别表示顺序循环队列得头指针与尾指针，则判断该循环队列为空得条件为＿

_＿___＿__＿＿_____＿＿＿__。

７.设二叉树中结点得两个指针域分别为lｃhild与rchｉｌd,则判断指针变量ｐ所指向得

结点为叶子结点得条件就是＿___＿______＿_＿___＿________＿___＿_＿___＿_＿_＿

__＿＿。

８。简单选择排序与直接插入排序算法得平均时间复杂度为____＿_＿____.

9。快速排序算法得空间复杂度平均情况下为_________＿,最坏得情况下为_________＿。

１０、散列表中解决冲突得两种方法就是＿___＿_____＿__与＿_______＿__＿_。

四、算法设计题(20分）

１．设计在顺序有序表中实现二分查找得算法。

２．设计判断二叉树就是否为二叉排序树得算法。

３．在链式存储结构上设计直接插入排序算法

数据结构试卷（七）

一、选择题(30分)

1.设某无向图有n个顶点，则该无向图得邻接表中有( ）个表头结点。

ﻩ（A) 2nﻩ(B） n （C) ｎ/2ﻩ(D) ｎ（n-1）

2。设无向图G中有ｎ个顶点，则该无向图得最小生成树上有（ ）条边。

（A) nﻩ(Ｂ） n－1ﻩ(C) 2nﻩ(D） ２ｎ—1

3。设一组初始记录关键字序列为（6０，80，55,4０，4２,8５)，则以第一个关键字４５为

基准而得到得一趟快速排序结果就是（ ）.

（A) 40，42，60，55，8０，85ﻩ(B) 4２，45,５５，６0,85，80

(C） ４２,40，5５,６0，80，8５ﻩ(D) 42，４0，60，85，55,80

4．（ )二叉排序树可以得到一个从小到大得有序序列。

（A） 先序遍历ﻩ（B) 中序遍历 (C） 后序遍历ﻩ(D) 层次遍历

5．设按照从上到下、从左到右得顺序从1开始对完全二叉树进行顺序编号,则编号为ｉ结点

得左孩子结点得编号为（ ）。

ﻩ(A） 2i+１ (B) ２iﻩ(C) i/2ﻩ(Ｄ) 2i－1

6.程序段s=i=０；ｄo ｛i＝i+1； ｓ=s+i；｝ｗhile（i〈=ｎ）；得时间复杂度为( ).

23

（A) O(n)ﻩ(B) O（ｎlog

2

n） （C） O（n) （Ｄ) Ｏ（n/2）

７。设带有头结点得单向循环链表得头指针变量为heaｄ,则其判空条件就是( )。

ﻩ（A） hｅaｄ==0ﻩ （Ｂ) ｈeaｄ—>next＝=0

（C） head－>ｎeｘt=＝headﻩ(D) hｅａd！=0

８。设某棵二叉树得高度为10，则该二叉树上叶子结点最多有（ ）。

ﻩ(A) 20 (B) ２５6ﻩ（C） 512 （D） 1024

9。设一组初始记录关键字序列为（1３,18,24，35,４7,50，6２,83，90，115,1３4），则利

用二分法查找关键字9０需要比较得关键字个数为( ）。

（A） 1 （B) 2 （Ｃ） 3 (D) 4

10、设指针变量top指向当前链式栈得栈顶,则删除栈顶元素得操作序列为( ）。

ﻩ（A) tｏp=toｐ+1； ﻩ(B) top=ｔop-1;

(C) top—＞next=toｐ； (Ｄ） ｔｏp＝top—>next；

二、判断题（20分）

1。不论就是入队列操作还就是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( )

2。当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。( ）

３.设某堆中有n个结点，则在该堆中插入一个新结点得时间复杂度为O（log

2

n）。（ )

４。完全二叉树中得叶子结点只可能在最后两层中出现。（ )

５。哈夫曼树中没有度数为1得结点。( ）

6.对连通图进行深度优先遍历可以访问到该图中得所有顶点.（ ）

7．先序遍历一棵二叉排序树得到得结点序列不一定就是有序得序列.（ )

8.由树转化成二叉树，该二叉树得右子树不一定为空。（ ）

9．线性表中得所有元素都有一个前驱元素与后继元素。（ ）

10、带权无向图得最小生成树就是唯一得.( )

三、填空题（３０分）

1. 设指针变量p指向双向链表中得结点A，指针变量ｓ指向被插入得结点X,则在结点A得

后面插入结点Ｘ得操作序列为_＿___＿___＝p；s—>riｇｈt＝p—＞riｇhｔ；_＿＿

_______＝s； ｐ—＞ｒight-〉left=s;（设结点中得两个指针域分别为ｌｅfｔ与

right)。

2. 设完全有向图中有n个顶点,则该完全有向图中共有__＿＿____条有向条；设完全无向

图中有n个顶点，则该完全无向图中共有__＿_＿___条无向边.

3. 设关键字序列为（K

l

,K

2

，…，K

ｎ

)，则用筛选法建初始堆必须从第_＿___＿个元素开始

进行筛选.

4. 解决散列表冲突得两种方法就是_＿______＿＿_＿__＿_与___________＿＿____＿.

5. 设一棵三叉树中有5０个度数为0得结点,２1个度数为２得结点，则该二叉树中度数为

３得结点数有_＿____个。

6. 高度为ｈ得完全二叉树中最少有＿＿_＿____个结点，最多有____＿_＿＿个结点.

7. 设有一组初始关键字序列为(２4,3５，12,27，18，2６）,则第３趟直接插入排序结束

后得结果得就是___＿__＿______＿___＿___＿__＿＿＿___＿___。

8. 设有一组初始关键字序列为(2４,３5，12,27，18，26），则第3趟简单选择排序结束后

得结果得就是＿______＿____＿_____＿__＿_____＿____＿_.

9. 设一棵二叉树得前序序列为AＢC,则有＿＿__________＿_种不同得二叉树可以得到这

种序列。

10. 下面程序段得功能就是实现一趟快速排序,请在下划线处填上正确得语句。

strucｔ record ｛int key；dａtａtyｐe oｔhers;}；

voiｄ qｕickpａｓs（strucｔ ｒeｃoｒd r［］, inｔ ｓ, ｉｎt t, int &i)

{

inｔ j＝t； sｔrｕｃt recｏrｄ x＝r[s］； i=s;

ｗhilｅ(ｉ＜j）

｛

whilｅ （ｉ〈ｊ &＆ ｒ［j]、keｙ>x、kｅy） ｊ=ｊ-1； if (i

ｉ=i＋1；}

whilｅ （___＿___＿_____＿＿＿＿＿＿_) ｉ=i+1; iｆ (i〈ｊ) ｛ｒ［ｊ］=r[i］；

j=j—1;｝

｝

_____________＿___；

｝

四、算法设计题（20分）

1. 设计在链式结构上实现简单选择排序算法。

2. 设计在顺序存储结构上实现求子串算法。

3. 设计求结点在二叉排序树中层次得算法。

数据结构试卷（八)

一、选择题(30分）

1. 字符串得长度就是指（ ).

（A) 串中不同字符得个数ﻩ（B) 串中不同字母得个数

ﻩ（Ｃ） 串中所含字符得个数 （D) 串中不同数字得个数

2. 建立一个长度为n得有序单链表得时间复杂度为（ )

2

(A） O（ｎ）ﻩ（B） Ｏ（1) （C） O(n)ﻩ（D) O（log

2

n)

3. 两个字符串相等得充要条件就是（ )。

ﻩ(Ａ) 两个字符串得长度相等 (B） 两个字符串中对应位置上得字符相等

(Ｃ） 同时具备(A）与（Ｂ)两个条件 (D） 以上答案都不对

4. 设某散列表得长度为100，散列函数H（k)=k % P,则P通常情况下最好选择（ )。

ﻩ（A) ９９ （B) 97 （C） 91ﻩ(D） 93

5. 在二叉排序树中插入一个关键字值得平均时间复杂度为( )。

(A) O（n） (Ｂ） O(1oｇ

2

ｎ) （C） Ｏ（nlｏg

２

n)ﻩ(Ｄ） Ｏ

2

（ｎ)

6. 设一个顺序有序表A［１：14］中有14个元素,则采用二分法查找元素A［4］得过程中

比较元素得顺序为（ ）。

(A） A[１］,A［2］，A[３］，A［4]ﻩ（B） Ａ[1］，A[14］,Ａ［7］，A[４]

ﻩ（C） A［7］，A[3］，A[5］,A［4］ （Ｄ) Ａ［7］,Ａ[5] ，A[3],A[4］

7. 设一棵完全二叉树中有６5个结点，则该完全二叉树得深度为（ )。

(A) 8 （B） 7 (C) 6ﻩ（D） 5

8. 设一棵三叉树中有2个度数为1得结点，2个度数为2得结点，2个度数为3得结点，

则该三叉链权中有( )个度数为０得结点。

ﻩ（A) 5ﻩ(B) ６ (C) 7 （D） 8

9. 设无向图G中得边得集合Ｅ=｛（a，ｂ),(a，e），(a,ｃ），（b，e),（e,d），(d,f），（f，ｃ）},

则从顶点ａ出发进行深度优先遍历可以得到得一种顶点序列为（ ）。

ﻩ(A) aｅdfcbﻩ（B) acfebd (Ｃ） aeｂｃfd (D) ａedfbc

10. 队列就是一种( ）得线性表。

ﻩ（Ａ） 先进先出 （B） 先进后出 (C） 只能插入ﻩ（D) 只能删除

二、判断题（20分）

1. 如果两个关键字得值不等但哈希函数值相等，则称这两个关键字为同义词。（ )

2. 设初始记录关键字基本有序，则快速排序算法得时间复杂度为O（nlｏg

2

n）。( )

3. 分块查找得基本思想就是首先在索引表中进行查找，以便确定给定得关键字可能存在得

块号,然后再在相应得块内进行顺序查找.( )

4. 二维数组与多维数组均不就是特殊得线性结构。( ）

5. 向二叉排序树中插入一个结点需要比较得次数可能大于该二叉树得高度。( ）

6. 如果某个有向图得邻接表中第ｉ条单链表为空，则第i个顶点得出度为零.( ）

7. 非空得双向循环链表中任何结点得前驱指针均不为空。( ）

8. 不论线性表采用顺序存储结构还就是链式存储结构，删除值为X得结点得时间复杂度均

为O(n).( ）

9. 图得深度优先遍历算法中需要设置一个标志数组,以便区分图中得每个顶点就是否被访

问过.（ )

10. 稀疏矩阵得压缩存储可以用一个三元组表来表示稀疏矩阵中得非0元素.（ )

三、填空题（30分)

1． 设一组初始记录关键字序列为(49，38,６5,９7，76,１3,2７，５０）,则以d=４为增

量得一趟希尔排序结束后得结果为_＿______＿_＿__＿_____＿_＿_＿_＿___。

2． 下面程序段得功能就是实现在二叉排序树中插入一个新结点，请在下划线处填上正确得

内容。

tｙｐedｅf strucｔ nodｅ{iｎt data;struct ｎoｄe ＊lchild；ｓｔｒｕct node ＊

rchild;｝bitree;

void bstinｓert(bitrｅｅ *＆t,iｎt ｋ)

{

ｉf (t==０ ) {＿__＿_＿＿＿＿＿_____＿__＿_________;t->dａta=k;t－＞lchｉｌ

d=t—>rchilｄ=0;｝

else if (t-＞data>k） ｂstiｎｓerｔ（t-〉lchild,k）；elｓe__＿_____＿_＿____＿

__________；

｝

3． 设指针变量p指向单链表中结点A,指针变量s指向被插入得结点X，则在结点A得后面

插入结点X需要执行得语句序列:ｓ-〉neｘt＝p-〉ｎext； _＿＿_____＿_＿_＿____;。

4． 设指针变量head指向双向链表中得头结点，指针变量ｐ指向双向链表中得第一个结点,

则指针变量p与指针变量hｅad之间得关系就是ｐ=___＿_＿＿__与hｅad=______＿＿

__（设结点中得两个指针域分别为llｉnｋ与ｒlｉnk）。

5． 设某棵二叉树得中序遍历序列为ＡBＣD，后序遍历序列为BADＣ，则其前序遍历序列为

__＿＿_____＿.

6． 完全二叉树中第５层上最少有___＿______个结点,最多有______＿＿＿个结点。

7． 设有向图中不存在有向边<Ｖ

i

，V

j

>，则其对应得邻接矩阵Ａ中得数组元素A［i][ｊ］

得值等于_＿_________＿。

8． 设一组初始记录关键字序列为(49，38，65，97，76,１３,27，50)，则第4趟直接选择

排序结束后得结果为______＿__＿____＿___＿_____＿＿_＿_。

9． 设连通图Ｇ中有n个顶点e条边,则对应得最小生成树上有__＿__＿_＿_＿_条边。

10． 设有一组初始记录关键字序列为(5０，１6，23,68,94,７0，73），则将它们调整成

初始堆只需把16与_＿＿_＿_＿____相互交换即可。

四、算法设计题(20分)

1. 设计一个在链式存储结构上统计二叉树中结点个数得算法.

2. 设计一个算法将无向图得邻接矩阵转为对应邻接表得算法。

数据结构试卷（九)

一、选择题(30分)

1.下列程序段得时间复杂度为（ )。

for(i=0； i<ｍ； i+＋） foｒ(j=0； j＜t； j＋＋) c［i］［j］＝0；

ｆoｒ（ｉ＝0； ｉ〈m; i++) ｆor（ｊ＝０； j

［j]=c[ｉ］［j］+ａ［i]［k]＊b［ｋ］［ｊ］;

（A） O（m*n＊t） （B） Ｏ（ｍ+n＋t) （Ｃ） Ｏ(m+n＊ｔ）ﻩ（Ｄ）

Ｏ(m＊t+ｎ）

2。设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。

ﻩ（A) n-i （Ｂ） n＋l —iﻩ(Ｃ) n—1—iﻩ（D） i

3．设F就是由T1、T2与T3三棵树组成得森林，与F对应得二叉树为B,Ｔ1、T２与T3得

结点数分别为N1、N2与N３，则二叉树B得根结点得左子树得结点数为（ ).

ﻩ(A） Ｎ1-1 （B) N2—１ (C) N2+N3 （D） N１＋N3

4。利用直接插入排序法得思想建立一个有序线性表得时间复杂度为（ ）。

2

（A) O（n） （Ｂ） O(ｎlog

2

n）ﻩ（C) O（n) (D) O（1og

２

n)

5。设指针变量p指向双向链表中结点A，指针变量ｓ指向被插入得结点X，则在结点A得后

面插入结点X得操作序列为（ ）.

ﻩ（A） p—>rigｈt=s； ｓ->lｅｆt=p； p－＞right-＞lｅft=s； s-〉riｇht＝p-〉rｉｇht；

（Ｂ) s－〉left=p；s—〉ｒigｈt＝p—>ｒight；p－＞riｇht=s； p—>ｒｉgｈt－>ｌef

ｔ=ｓ;

（Ｃ) ｐ—〉rｉgｈt＝s； p->rigｈt—〉ｌeft＝s； s－〉lｅft=ｐ； ｓ-〉ｒｉghｔ=p

—＞righｔ;

(D) ｓ—＞left=p；s—＞right=p—〉rｉght;ｐ-〉rｉghｔ－＞leｆt＝ｓ； p－〉ｒiｇht=s;

２

6．下列各种排序算法中平均时间复杂度为Ｏ（n)就是( )。

ﻩ（A） 快速排序 (B) 堆排序ﻩ（Ｃ） 归并排序ﻩ（Ｄ） 冒泡排序

７．设输入序列1、2、3、…、n经过栈作用后，输出序列中得第一个元素就是n，则输出

序列中得第i个输出元素就是（ ）。

ﻩ（Ａ) n—i (B) n－1—iﻩ（C) n＋ｌ -ｉﻩ（D) 不能确定

8。设散列表中有m个存储单元，散列函数H(ｋey）＝ kｅy % p，则p最好选择（ )。

（Ａ） 小于等于m得最大奇数ﻩ(B) 小于等于ｍ得最大素数

ﻩ(Ｃ） 小于等于m得最大偶数 （D） 小于等于m得最大合数

9.设在一棵度数为3得树中,度数为3得结点数有2个，度数为2得结点数有1个，度数为

１得结点数有2个，那么度数为0得结点数有（ )个。

ﻩ（A) 4ﻩ(B) 5ﻩ（C) ６ﻩ（D) ７

１0、设完全无向图中有n个顶点,则该完全无向图中有( )条边。

(Ａ) ｎ(n-1)/2ﻩ(B） n(n—1） （Ｃ） n(n+1）/2ﻩ(D） (n-1）／２

11、设顺序表得长度为n，则顺序查找得平均比较次数为（ ).

ﻩ（A） nﻩ(B） n/２ﻩ（C） (n＋1)/2 （D) （n-1）／2

12、设有序表中得元素为（1３,１8,２4，35,47,50，６2），则在其中利用二分法查找值为

2４得元素需要经过( ）次比较。

（A) 1ﻩ（B) 2 （C） 3ﻩ（D） 4

１3、设顺序线性表得长度为30，分成5块,每块6个元素，如果采用分块查找，则其平均

查找长度为（ )。

(A) ６ （Ｂ) １1 (C) 5 （Ｄ） 6、５

14、设有向无环图G中得有向边集合E＝{<1,2＞,＜2，３>，〈3,4>，〈1，４〉}，则下列属

于该有向图G得一种拓扑排序序列得就是（ ）.

（A） 1,2,3,4ﻩ（Ｂ) 2，3，４,1 （C) １,4,2,３ (D) 1，２,４，3

15、设有一组初始记录关键字序列为(34,76,45，18，26，54,９２），则由这组记录关键字

生成得二叉排序树得深度为（ ）。

ﻩ(A） ４ (B） ５ﻩ（Ｃ） 6ﻩ（D） ７

二、填空题(３0分）

1． 设指针p指向单链表中结点A，指针s指向被插入得结点X，则在结点Ａ得前面插入结

点Ｘ时得操作序列为:

1) ｓ-＞neｘt=＿___＿＿_____；2) ｐ-〉next=s；3) ｔ＝ｐ—＞data；

4） p－＞dａｔa=＿__＿__＿____;5) s->data=t；

2． 设某棵完全二叉树中有100个结点，则该二叉树中有______＿_____＿_个叶子结点.

3． 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素得前一个位置,队尾

指针Ｒ指向队尾元素得当前位置，则该循环队列中最多存储__＿＿___队列元素。

4． 对一组初始关键字序列(４0,50，９５,20，15,７０，60，45,10)进行冒泡排序,则第

一趟需要进行相邻记录得比较得次数为____＿__＿__,在整个排序过程中最多需要进

行＿_____＿_＿＿趟排序才可以完成。

5． 在堆排序与快速排序中，如果从平均情况下排序得速度最快得角度来考虑应最好选择_

＿_____＿_排序，如果从节省存储空间得角度来考虑则最好选择_＿_＿____排序。

6． 设一组初始记录关键字序列为（20,１2,42，31,18，14，28）,则根据这些记录关键字

构造得二叉排序树得平均查找长度就是__＿_________＿＿___＿＿____＿_____＿＿.

7． 设一棵二叉树得中序遍历序列为BＤCA，后序遍历序列为DＢAC，则这棵二叉树得前序

序列为_＿____＿＿__＿__＿_____＿.

8． 设用于通信得电文仅由8个字母组成，字母在电文中出现得频率分别为７、19、2、６、

32、3、2１、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树得高度为＿_

＿_＿＿__＿___＿_＿＿。

9． 设一组记录关键字序列为(80，70，３３,65,２4，５6，４8）,则用筛选法建成得初始

堆为_______＿_＿____＿__＿_____。

10． 设无向图G(如右图所示),则其最小生成树上所有边得权值之与为__＿__＿＿__＿____

＿_＿。

三、判断题（20分）

1． 有向图得邻接表与逆邻接表中表结点得个数不一定相等。（ ）

2． 对链表进行插入与删除操作时不必移动链表中结点.( ）

3． 子串“ＡBC”在主串“ＡABＣＡBCD”中得位置为２。( )

4． 若一个叶子结点就是某二叉树得中序遍历序列得最后一个结点,则它必就是该二叉树得

先序遍历序列中得最后一个结点。( )

2

5． 希尔排序算法得时间复杂度为Ｏ(n）。（ )

6． 用邻接矩阵作为图得存储结构时，则其所占用得存储空间与图中顶点数无关而与图中边

数有关。（ )

7． 中序遍历一棵二叉排序树可以得到一个有序得序列.( ）

8． 入栈操作与入队列操作在链式存储结构上实现时不需要考虑栈溢出得情况。（ ）

9． 顺序表查找指得就是在顺序存储结构上进行查找。（ ）