杭州电子科技大学数据结构期末复习卷.doc

是非题
1。 　数据结构可用三元式表示（Ｄ，S,P）．其中：D是数据对象,S是D上的关系,
Ｐ是对D的基本操作集。×
2.　 线性表的链式存储结构具有可直接存取表中任一元素的优点。 ×
3。　 字符串是数据对象特定的线性表。
4。 二叉树是一棵结点的度最大为二的树.×
5. 邻接多重表可以用以表示无向图,也可用以表示有向图。×
6． 可从任意有向图中得到关于所有顶点的拓扑次序。×
7. 一棵无向连通图的生成树是其极大的连通子图。×
８. 二叉排序树的查找长度至多为ｌog2ｎ。×
9. 对于一棵ｍ阶的B-树。树中每个结点至多有m　个关键字.除根之外的所有非终端结点至少有┌m／２┐个关键字。×
10．对于目前所知的排序方法,快速排序具有最好的平均性能。
１１。 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。×
12. 二维数组是其数据元素为线性表的线性表。
13。 连通图G的生成树是一个包含G的所有n个顶点和ｎ—1条边的子图。×
１4. 折半查找不适用于有序链表的查找．
15.　完全二叉树必定是平衡二叉树。
16.　中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点.
１７。 队列是与线性表完全不同的一种数据结构。×
18. 平均查找长度与记录的查找概率有关。
19． 二叉树中每个结点有两个子结点,而对一般的树,则无此限制,所以,二叉树是树的特殊情形。×
20.　算法的时间复杂性越好,可读性就越差;反之,算法的可读性越好,则时间复杂性就越差。×

二.选择题
１。若对编号为1,２，3的列车车厢依次通过扳道栈进行调度,不能得到 (e　) 的序列。
a:１,２，3 b:１,3,2 　c：2，1，3 　 ｄ:２,3，1　 e:3,１,2 ｆ：3，２,１

２。递归程序可借助于(　　ｂ　 )转化为非递归程序。
ａ：线性表 　 b:栈 　 　 c:队列　 ｄ:数组

3． 在下列数据结构中（ c　 )具有先进先出（FIＦO)特性，
( b 　)具有先进后出(FIＬO)特性。
ａ:线性表 　 　　b：栈 　 　 c：队列 　 　d：广义表

4。　 对字符串s=’daｔａ—sｔrｕｃturｅ’执行操作ｒeplacｅ（s,ｓuｂstrinｇ(ｓ，６,8）,'ｂａs’）
的结果是 (　　d　 ） 。
a: ‘databaｓe' b: ‘datａ－baｓe' c: ‘ｂas’　　　d： ‘ｄａｔａ—bａsuｃtuｒe’

5． 设有二维数组A５x7 ,每一元素用相邻的4个字节存储,存储器按字节编址。
已知A的起始地址为100.则按行存储时,元素Ａ0６的第一个字节的地址是（d)
按列存储时，元素Ａ06的第一个字节的地址是(a）
a: 22０ 　b:　　200　 c： 140 　d: 124

６。　对广义表　A＝(（a,(b)),（c,(））,ｄ)执行操作ｇｅｔtaiｌ(ｇetｈead（gｅttaｉl(A)))
的结果是:(b）。
a：() 　 　 b： （(）) 　 　ｃ: d ｄ: （d)

７.假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, ２2, 6，　３2， 14。若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合,新生成的二叉树总是插入在最右），则频率为7的字符编码是(g)，频率为32的字符编码是（c)。
a： ０0 　b: 01 　c： 10 　 ｄ:　1１
e： 0１1　 　 f： 110 　 g:　1１１0 ｈ:111１

８。对二叉排序树(　b )可得到有序序列.
a:按层遍历 　 　b：前序遍历 　 c:中序遍历 　 d:后序遍历

9.已知某树的先根遍历次序为ａbcｄefg，后根遍历次序为ｃｄｅbgfa。
若将该树转换为二叉树,其后序遍历次序为(d）。
a: 　abcdefg　　 ｂ: cdebgfa 　 c： 　ｃｄeｇbｆa 　 d： edcｇfba

10.对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子,其位序是（　ｄ　）。
编号为n的结点若存在双亲,其位置是( a　）。
a:ｎ/2　 b: 2ｎ　　 　　 c:２n—1　 　d：2n＋1　 　ｅ:n 　 f:　2(n＋１)

11．关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点（c）的路径.
ａ:弧的数目最多 b:弧的数目最少 c:权值之和最大　 　 d：权值之和最小

12. 哈希表的查找效率取决于（d）.
a：哈希函数b:处理冲突的方法。 ｃ:哈希表的装填因子。d:以上都是
13．从逻辑上可以把数据结构分成（ c ）。
　　A。动态结构和静态结构B。顺序组织和链接组织
C。线性结构和非线性结构D．基本类型和组合类型

１4．在计算递归函数时,如不用递归过程,应借助于( b ）这种数据结构。
A．线性表Ｂ。栈C.队列D。双向队列

1５.若已知某二叉树的中序和后序遍历序列分别BＣAEFD和CBFEDA，则该二叉树的先序序列为( a ）．
A. ABCDEF 　　 B.　ABDCEF 　 　 C。 ＡBDCFE 　　　 　 Ｄ。 ＡCＢDFＥ

16．当待排序序列的关键字次序为倒序时,若需为之进行正序排序，下列方案中( d　)为佳.
A.起泡排序B。快速排序
C．直接插入排序Ｄ。简单选择排序

17．若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是( c　)。
A． 二叉排序树 B。　赫夫曼树 　 C． 堆 　 　 　 Ｄ。　平衡二叉树

１8.下图所有可能的拓扑序列有（ ｂ ）种。

A．　2　　 　 　 　B.　3　 　 　　　　 Ｃ。 4 　 　 D。 5

19．下列排序算法中，( d）算法可能会出现:初始数据为正序时，花费的时间反而最多。
A。 堆排序 Ｂ。 起泡排序 　 C。 归并排序 　 　 D。 快速排序

20.右图为一棵3阶Ｂ-树。 　　 　 　　 　 ２0 ,２5在该树上插入元素1５　 　
后的Ｂ—树是（ c ）. 　 　 　 　 　10　, 14　 　　　 21 　 　　 35

A。 　 　 1５ , 2５　　 　　 B。 　 20 , 25

　 10 , 14 　 ２０ , 21 　　 35　 　　 　　　 １0 , 1４　 1５ , 21 　 3５

C。 　　 　 20 　 　 　　 　 　 　　　D。 　 14 , 25

14　 　　 2５　 　 　　　 　　　 　10 , 15 　2０ ,　21 　 35

10　 　　　15 　 21　 　 35

２1.设森林Ｆ中有三棵树,第一、第二和第三棵树的结点个数分别为ｍ1、m2和m3，则与森林Ｆ对应的二叉树根结点的右子树上的结点个数是（ ｄ )．
A. m1B。 ｍ１＋m2 C。 m３　 　D. m２+m3

22。 根据插入次序(８0,90,10０，11０,85,７0，75,60，７２)建立二叉排序树。
图（a）是最终变化的结果。
若仍以该插入次序建立平衡二叉树。图（c)是最终变化的结果。

　 ８0 　 　 　 　　 　　　　　 80 　　 　 　　 　

７0 　 90 　 　 　 　　 75 　 　 9０ 　 　　 　 　 　 　 　 　 　 　　 　

6０ 　　 75　 8５ 　 １0０ 　 　　 　６0　 ７０　　 ８5 　100 　 　 　 　 　 　　 　 　 　 　 　 　 　

　　　72 　 110　 　72　 　 　 　　　　　 　 １1０ 　 　 　 　　 　 　　　

　a:　 　 　 　 b：

90 　 　 　　　 　 　　 　 　９0　　 　 　　 　 　　 　 　 　 　 　 　 　

７51０0 　 　 　 　　80　 　 　　　　100 　 　 　 　 　 　 　 　 　 　 　　 　

708０ 　 110　 　　 　 75 　 ７0 85 　　 １10 　 　 　　 　 　 　 　 　 　

６０ 7２ 　　85 　 　 　６0　 ７2 　　 　 　 　 　 　 　　　 　

　　　 c:　 　 　　　 　　 　　 　 　 ｄ:

23.设输入序列为２0,４5，３0,8９,70,38，62，19依次插入到一棵2—3树中(初始状态为空）,该Ｂ—树为( b　)。再删除38,该Ｂ-树为（ ｆ　)。

　 ( 3０ 6２ ） 　 　　　 　 　 （ 45 　) 　 　 　 　　

（1９,20）( 38 45 )　（ 70，89 )　 　 ( 30 ）　 　　 ( 70　)

（1９　20) 　 (38 )（　62　) (　89 )

a： 　 　 　 　 　 　 　 　 b：

　 　( 45 　7０　 ） 　　 　　 　 　 　 　 　 （ 　45　 ） 　

(20) 　 (　6２ )　 (　8９　)　 　 　 　　 （　20 ) 　　 （ ７0　）

（19)（ 30 ） 　 　 　 　 （ 19 ） 　(　30,38 ）( 62 ） （ 8９ ）

　 　　 　 　c: 　 　 　 　　 　 　 　 d:

　　　 　( 30 70　 )　　 　 　　　 　 　 　 （ ４5 ） 　 　 　

（19，2０） (　４5 ６2) 　(　８9 ) 　 　 ( ２0 ) 　 　 （　７0 )

(19 ） 　　 （30 )(　6２ )　 ( 89　)

　　　 　 　 　 ｅ:　　　 　　 　 　　 　 　　 　　　 　 ｆ:

24.已知一组待排序的记录关键字初始排列如下:４5,34，87，25,６7,43，1１,66,27,78 。
（　g ）是快速排序法一趟排序的结果；
（ a　）是希尔排序法（初始步长为4)一趟排序的结果;
(　ｂ　)是初始堆（大堆顶);
(d）是基数排序法一趟排序的结果。
A．27，34,11,２5，45，43,87，6６,6７，7８ 　 　B．８7,78，45，６６，６7,43,1１，２5,２7,３４
C.１１,4３,34,２5,45，66，２7，67,87,78 　 　 D．11，43,34,45,25，66,87，６７,27,78
E． 3４,4５，2５,６7,43，１１，66，27，78，8７ 　　　 F.87,45，11,25,34,７８，2７，66,6７，43
G.27,34,１1,25,4３,45,67，66,８7,７8 H．34,1１，２7,２５，４３,78,45,67,66，87

25．若有序表中关键字序列为:1４，２0，２５,32，34,45，57，６9,77，83,92。对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是( c ).查找32时需进行(　c ）次比较。
Ａ.１Ｂ。2Ｃ.3D。4
2６。　设一棵二叉树ＢＴ的存储结构如下：
1 　2 　 3 　4　　 5 　6 7 　 8
ｌｃｈｉld ２　 ３ 　0 0 6 　 0 0 0
daｔa A B Ｃ D E　　 F G 　 H
rchild ０ 　　 5 4 0 87 ０　 ０
其中ｌｃｈild，ｒcｈild分别为结点的左、右孩子指针域，daｔa为结点的数据域.则
该二叉树的高度为(　d );
第3层有( a )个结点(根结点为第1层）。
　 A．2　 　 Ｂ。 ３ 　　 　Ｃ。 4 　　　　 　 D。 5

27.　一个连通图的最小生成树( b　)．
A.只有一棵 　　　 　 B。　有一棵或多棵 　 C. 一定有多棵　 　 D. 可能不存在

２8．若某二叉树有2０个叶子结点，有２0个结点仅有一个孩子,则该二叉树的总结点数是(　c ）.
　A.４０ 　 　 　B． 55 　 　 　 　 　C.　５９ 　　 　 　 D。 61

２9.已知哈希表地址空间为A[0。。８］,哈希函数为H(k)=k mod 7,采用线性探测再散列处理冲突。若依次将数据序列:７6,45，88,21,９４，77,17存入该散列表中，则元素１7存储的下标为（　f　）;在等概率情况下查找成功的平均查找长度为（ c ）．
　　A。0B。1 　 　 　 　C.２ 　 　　 　　 D．３
E。　４ 　　 　 　 　Ｆ。 5　 　 　　 　　　G。 6 　　 　 　 Ｈ。 7
3０．已知某有向图的邻接表存储结构如图所示.
0 E 2 1 ∧
1 D 0 3 4 ∧
2 C 4
3 B 1 2 0 ∧
4 A 2 ∧

根据存储结构,依教材中的算法其深度优先遍历次序为（ｄ)。
广度优先遍历次序为(c)。各强连通分量的顶点集为（)。
a: 　ａbcde。　 　 ｂ:　 edcba.　 c: eｃｄab. 　 　d：　 eｃadb.
e: ａbc及ed 　　f： ａc及beｄ ｇ: 　ａｂ及ced 　 　h: bc及ａeｄ
31. 已知某无向图的邻接表如下所示； 　　 　 　 　
(　 )是其原图。　 　 　　 　 　 　
（　 )是按该邻接表遍历所得深度优先生成树.
（ ）是按该邻接表遍历所得广度优先生成树.
０ a 　３21
１ b3０
　2 c 　 　4 　 3 　 0
3 d 　 　 5　 　 ２ 　 １ 　　 ０
　4 e 　 　 　５　 　　 　2
5 ｆ　　 　 　 ４ 　 　 　　3
Ａ。　a b 　　 　 　 　B. a b　 　 　 　 C. a ｂ　 　

c　 d　　 c 　　 ｄ　 　 c 　ｄ 　 　

e f　 　 e f　 　 e　　 f 　

D. a ｂ 　 　 　 　 E。 a 　 b　 　 F。 a 　 b

d　　　 ｃ 　 　 　 　　 ｃ 　 d 　 　 　　　　 　　　 c d

　 f 　　　 ｅ 　 　 　 e　 　 f　 　 　 　 　 　　e　 f

3２.若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定
的结点,将该结点与其后继（若存在）结点交换位置，使得经常被查找的结点逐渐移至
表尾。以下为据此策略编写的算法,请选择适当的内容，完成此功能。
顺序表的存储结构为：
ｔｙpeｄef sｔruct{
　 　　　　 　 EleｍType ＊elｅm;　／／数据元素存储空间，０号单元作监视哨
　 　 　 int length;　//表长度
　　 　　 }SSTａbｌe;
ｉnt　search＿seq（ＳＳTablｅ ＳT, KｅyTypｅ　kｅy)
｛　//在顺序表ST中顺序查找关键字等于ｋey的数据元素。
/／若找到，则将该元素与其后继交换位置,并返回其在表中的位置,否则为0.
ST。elｅm［0]．kｅｙ=ｋey；
i＝ST.leｎgth;
while(SＴ．eleｍ[i].kｅｙ！=ｋｅy);
if（)
｛ SＴ.eｌｅm［ｉ]←→SＴ.elem[i＋1］;
;
} 　
return i;
｝
A。　i〉０ 　 　B。 i〉＝0　 C。 ｉ〈ＳＴ．leｎｇth 　 　　 Ｄ。 ｉ<＝ST。ｌength
E。 ｉ＋+ F。 ｉ－- 　 　 G。 Ａ和Ｃ同时满足 　　 H。　B和Ｄ同时满足

33.下列函数为堆排序中的堆调整过程(调整H。ｒ[s]的关键字,使H。r[ｓ。。m]成为一小顶堆）．请在“"处填上合适的内容,完成该算法。
Voｉｄ ｈeapａｄｊuｓｔ（ heapｔype ＆　Ｈ , ｉｎt　s , iｎt m ) {
rc=H。ｒ［s];
foｒ　(j＝2*ｓ;j<=m；ｊ＊=2)　{
ｉｆ (j〈m && )　++ｊ；
iｆ （ ) breaｋ;
Ｈ.r［s]=H.r[j］;　s=j;
｝
;
｝/／ｈｅapａdjust
a: （H。r［j]。kｅy〉Ｈ。r[ｊ+１]。key)；
b: ！(rc。ｋey〈 H。ｒ［j]。keｙ）;
c: （H.ｒ[j]。key〈H.ｒ[j+1]。key)；
　 d：　　！(rc。ｋｅy >H。ｒ[ｊ］。kｅy）；
e: H。r[s］=ｒｃ;
f： rc=Ｈ。r[s］；
ｇ： h。r[ｊ］=rc；
h： rc=Ｈ。r[ｊ]；

三.算法设计题
1． 单链表结点的类型定义如下：
tｙｐedef　ｓｔrｕcｔ　LNｏde ｛
　iｎt datａ;
　 　 　 struct LＮｏde *next;
｝ LＮｏde，　*Ｌｉnｋlist;
写一算法,Contrary(linkｌiｓt &L) ,对一带头结点且仅设尾指针L的循环单链表
就地逆置.（即表头变表尾,表尾变表头.)

2．二叉树用二叉链表存储表示。
typedef strｕｃｔ BiTNｏｄe ｛
　 　 TelemType　　dａta;
Stｒｕcｔ BiTNode *lｃhild， ＊rchild；
} BiTNoｄe, *BｉTree;
试编写销毁二叉树T的算法ＤeｓｔroyBiＴreｅ （　BiTree &T）。

3．设带头结点的单链表中的元素以值非递减有序排列，试编写算法，删除表中所有值相同的多余元素。
单链表结点的类型定义如下:
　　ｔｙｐｅdef stｒuｃt LNｏｄe｛
　 　　 iｎt data;
　 　 　Struct LＮｏｄｅ *ｎext；
　 }LＮodｅ， ＊LinkＬist；

4.二叉树用二叉链表存储表示。
tｙpeｄeｆ sｔｒｕｃt　ＢiTNｏde {
　 　 　 TelemTｙpｅ　 data;
　 　Struｃｔ　BｉTＮｏde *lchild, *rｃhｉｌd;
｝ BiTNode， *BiTrｅe；
试编写算法，求元素值为ｘ的结点的左孩子(返回x的左孩子的指针）。