数据结构试题

一．填空题

1. 数据的逻辑结构从逻辑关系上描述数据，它与数据__存储（或存储结构）___无关，

是于计算机的。

2. 栈顶的位置是随着_进栈或退栈____操作而变化的。

3. 一个n*n的下三角矩阵A中的元素aij(i>j,1小于等于i,j小于等于n)按行存于一个一

维数组B[1..n(n+1)/2]中，对其中的任一元素aij，若在B中的位置为k,则k=_i(i-1)/2+j________.

4．已知一棵完全二叉树有768个结点，则该树有（384）个子节点 5.__二分查找_________又称折半查找，它是一种效率较高的查找方法。

6.数据结构按逻辑结构可分为两大类，它们分别是_线性结构和非线性结构_______________。

7.在栈中存取数据遵从的原则是__后进先出____________________。

8.对于数组An*n其元素aij按行优先与列优先存储地址之差为__(i-1)(n-1)-(j-1)(m-1)_____________（设两次存储的LOC(a11)相同）。 9.高度为5的完全二叉树至少有_16______个结点。

10.在包含n个结点的顺序表上做等概率插入运算，平均要移动___n/2_________个结点。 11.对于n个记录的集合进行冒泡排序，在最坏情况下的所需要的时间是__O(n的2次方)____________。

12.设一个闭散列表的容 量为m，用线笥探测法解决冲突要插入一个键位，若插入成功，至多要进行___m(m+1)/2_______次比较。

13.一个算法的效率可分为时间效率和_空间______效率 。

14．顺序表中的访问任意结点的时间复杂度为_ O(1)_______，因此，顺序表也称为随机存

取的数据结构。

15.设栈S和队列Q的初始状态皆为空，元素a1,a2,a3,a4,a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1,则栈S至少应该容纳___4____个元素。

16.在串S=“structure”中，以t为首字符的串有____2________个。 17．串中所含字符个数称为串的（串长）

18.前序为a,b,c且后序为c,b,a的二叉树共有____4________棵。 19.下面程序段的时间复杂度为__O(n的1/2次方)________。

X=n;y=0(n>1)

While(x>=(y+1)*(y+1) Y++;

20已知数组A[8][8]为对称矩阵，其中每一个元素占5个单元，现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，5]对应的地址为____1165_________。

21.已知广义表A=((a,b,c),(d,e,f)),从__head(tail(head(tail(A))))___________。

A

中取出原子

e

的运算是

22.循环队列用数组A[m]存放起始元素值 ，已知其头尾指针分别是front和rear,则当前队列中元素的个数是__(rear-front+m)%m_________。

4. 在左右子树均不空的二叉树中，空链域的数目是____________。 24.具有20个结点的完全二叉树的深度为__5__________。

25.若一个算法中的语句频度之和为T(n)=3720n+4nlgn,则算法的时间复杂度为

____O(lgn_)_______。

26.线性表L=（a1,a2,………,an）采用顺序存储，假定在不同的n+1个则插入一个新元素平均需要移动的元素个数为__n/2_________。

27.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_bceda_____________。

28.已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为__129_________。

29.在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为__2____。

30.循环队列用数组A[m]存放起元素值，已知其头尾指针分别是front和rear,则当前队列中元素的个数是_(rear-front+m)%m________。

31.在队列中存取数据应遵从的原则是_先进先出______。

32.串是由零个或从个字符组成的序列，一般记为___s=”a1,a2…an”__________________。 33.已知数组A[8][8]为对称矩阵，其中每个元素占5个单元 ，现将其下三角部分按行优先次序存储在起始地址为100的连续的内存单元中，则元素A[4，5]对应的地址为____195____。 34.包含n棵树的森林对应的二叉树的高度至少是____n_____。

35.已知完全二叉树的第4层有4个结点，则其叶子结点数目是__6______。 36.具有100个结点的完全二叉树的深度为___7______。 37.散列函数H（key）=key%p,p应取__素数 ____。 38.数据的基本单位是_ 数据元素_____。 39.空串的长度是__0___________。

40.二叉树的中序遍历序列与该二叉树对应的森林的__后序__________序列相同。 41.设广义表L=（a），则tail(L)=__()____________。

42.一个算法的_空间复杂度_________s(n)定义为该算法所耗费的存储空间。 43.当栈满时再做进栈运算必定产生空间溢出，简称__上溢__________。 44.通常将仅由一个或多个空格组成的串称为___空白串_______。

45.广义表运算head(((a,b),(c,d)))的结果是__(((a,b),(c,d)))_____。

46.若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为__完全二叉树_______________。 47.设顺序表的长度为n，则每个元素的平均查找长度是_______(n+1)/2_______________。 48.数据元素及其关系在计算机存储器内的表示，称为数据的__存储结构___________。 49.在栈结构中，允许插入、删除的一端称为_ 栈顶__________。 50.通过在程序中使用串可以分为_ 串常量________和串变量。

51.广义表Ls=(a1,a1,…an-1,an)的长度为__n____________________。

52.含有100个结点的树有__99__________条边。

53.数据之间的相互关系即数据的组织形式称为____数据结构________________。 .设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是_____top=0_______________。

55.串S=”I am a student”的长度是____14_______________。 56.n个结点的满二叉树的高度为_______[log2n]+1_______________。 57.具有个结点的完全二叉树的深度 为__7____________________。

58.有一个长度为20的有序表采用二分查找方法进行查找 ，共有_4______个元素的查找长度为3.

59.数据的逻辑结构在计算机存储器内的表示，称为数据的_____存储结构____________。

60.栈下溢是指在__栈空___时进行出栈操作。 二．选择题

1、数据结构有_______类逻辑结构。（ B ） A 1 B 2 C 3 D 4

2.语句X++的时间是单位时间，则语句： for(i=1;i的时间复杂度是 （ B ）

A O（1） B O（n） C O(n2) D O(n3)

3.把线性表的结点逻辑次序依次存放在一组地址连续的存储单元中，用这种方法存储的线性表简称为（ A ）

A 顺序表 B 单链表 C 双链表 D 循环链表

4.向一个栈顶指针为Top的栈中插入一个s所指向结点时，其操作步骤为（ C ） A Top->next=s; B s->next=Top->next;Top->next=s; C s->next=Top;Top=s; D s->next=Top;Top=Top->next; 5.由两个栈共享一个向量空间的好处是（ B ）

A 减少存取空间，降低下溢发生的机率 B 节省存储空间，降低上溢发生的机率 C 减少存取时间，降低上溢发生的机率 D 节省存储空间，降低下溢发生的机率 6.s1=\"abcd\则s2在s1中的位置是（ C ） A 1 B 2 C 3 D 4 7.下列传述中正确的是（ A ）

A 串是一种特殊的线性表 B 串的长度必须大于零 C 串中元素只能是字母 D 空串就是空白串

8.已知二维字符数组A8*10中，元素A[1][2]的地址为1000，则元素A[0][0]的地直为（ A ） A 988 B 979 C 987 D 982

9.对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2,则（ A ） A n0=n2+1 B n2=n0+1 C n0=2n2+1 D n2=2n0+1

10.某二叉树的前序遍历序列为IJKLMNO,中序遍历序列为JLKINMO,则后序遍历序列为（ C ）

A JLKMNOI B LKNJOMI C LKJNOMI D LKNOJMI 11.在顺序表中查找第I个元素的时间效率最高算法的时间复杂度是(A) A o(1) B o(n1/2) C o(log2n) D o(n)

12.深度为k的二叉树至少有_____A_____个。

A K个结点 B K-1个结点 C 2k- -1个结点 D 2k-1个结点 13.设有100个元素，用二分查找法进行查找时，最小比较次数是( D ) A 7 B 4 C 2 D 1 14.算法指的是（ D ）

A 计算机程序 B 解决问题的计算方法 C 排序算法 D 解决问题的有限运算序列 15.下列有关线性表的叙述中，正确的是（ A ）

A 线性表中的元素之间是线性关系 B 线性表中至少有一个元素

C 线性表中任何一个元素有且仅有一个直接前趋 D 线性表中任何一个元素有且仅有一个直接后继

16.栈与一般线性表的区别主要是在（ D ）

A 元素个数 B 逻辑结构 C 元素类型 D 插入、删除元素的位置

17.循环队列sq是满队列的条件是（B ）

A sq->rear==sq->front B sq->count==queuesize C sq->rear==0 D sq->front==0

18.下列关于串的叙述中，正确的是（ A ）

A 一个串的字符个数即该串的长度 B 一个串的长度至少是1 C 空串是由一个空格字符组成的串

D 两个串s1和s2若长度相同，则这两个串相等

19.下列广义表是线性表的有（ A ） A E=(a，（b,c）) B E=(a,E) C E=(a,b) D E=(a,L);L=() 20.若数组A[0..m-1][0..n-1]按优先顺序存储，则aij的地址为（ C ） A LOC(a11)+[j*m+1] B LOC（a11)+[j*n+1] C LOC(a11)+[(j-1)*n+i-1 D LOC(a11)+[(j-1)*m+i-1

21.若二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是（ C ） A 6 B 5 C 4 D 3

22 已知A，B，C，D四个元素依次进栈，在进栈过程中允许出栈，下列不能得到的序列为（D） A，ABCD B DCBA C CBAD D CABD

23 栈的特点是（C）

A 先进先出 B 后进后出 C 后进先出 D先进不出

24.设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较_____次（ C ）

A 9 B 8 C 7 D 6

25.逻辑结构是数据元素的（ A ）

A 关联 B 存储方式 C 结构 D数据项 26.在栈中，出栈操作的时间复杂度为（ A ）

A O（1） B O（log2n） C O(n) D O(n2)

27.为查找某一特定单词在文本中出现的位置， 可应用的串运算是（ D ） A 插入 B 删除 C 串联接 D 子中定位

28.朴素模式匹配算法在最好的情况下的运行时间是（以一次内循环为单位） （A ） A M B N C M+N D M*N

29.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元 ，且数组中每一个元素的存储地址为120，则元素A[3][4][5]的存储地址为（ B ） A 356 B 358 C 360 D 362

30.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的孩子编号为（ A ）

A 98 B 99 C 50 D 48

31.一棵二叉排序树T，用______方法进行遍历，可以 得到各结点键值的递增序列。（ B ） A 先根遍历 B 中根遍历 C 层次遍历 D 后根遍历 32.队列的特点是（ D ）

A 先进后出 B 后进先出 C 先进不出 D先进先出 33在深度为了10的二叉树中，第五层最多有结点（C） A5个B10个C16个D32个

34.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（C ） A n B n/2 C (n+1)/2 D (n-1)/2

35.散列函数有一个共同性质，即函数值 应当以________取其值域的每个值 。（ A ）

A 同等概率 B 最大概率 C 最小概率 D 平均概率

36.设函数f(n)=10n+200nlgn,g(n)=5n+500nlgn,则下列成立的式子是(C) A f(n)=O(nlgn) B g(n)=O(nlgn) C f(n)=O(g(n)) D f(n)=O(n2)

37.在表长为n的顺序表上做插入运算，平均要移动的结点数为（ B ）

A n B n/2 C n/3 D n/4

38.设长度为n的链队列用循环链表表示，若只设对指针，则出队操作的时间的复杂度为（ A ）

2

A O（1） B O（lgn） C O(n) D O(n) 39．空串是指（ B ）

A 空白串 B 长度为零的串 C 长度为1的串 D 仅由空格组成的串 40.下列说法中错误的是（ B ）

A 串是一种特殊的线性表 B 串中不能没有字符 C 串中可以有字母 D 串长大于或等于0

41.深度为k的二叉树至少有____B______个。 A 2k B 2k-1 C 2k-1 D 2k-1-1

42.一个非空广交表的表尾（ A ）

A只能是子表 B 不能是子表 C 只能是原子 D 是原子或子表 43.n个结点的满二叉树的高度是（ C ）

A n/2 B log2(n_1) C （log2n）+1 D log2n

44.一棵二叉树的先序序列是ABCDEF，则下列序列中可能是该二叉树中序序列的是（ A ） A ABCDEF B CABDEF C BDACEF D FBACDE 45.折半查找排序的时间复杂度是（D ）

A O（n2） B O(nlog2n) C O(n) D O(lon2n)

46.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ C ） A 存储结构 B 逻辑结构 C 顺序存储结构 D 链式存储结构 47.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I结点的地址为（ A ）

A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m 48.循环队列sq是空队的条件是（A ）

A sq->rear==sq->front B (sq->rear+1)%maxsize==sq->front C sq->rear==0 D sq->front==0

49.字符串“VARYPE unsigned int”若采用动态分配的顺序存储方法需要____C_____个字节（假设每种数据均占用2个字节）。 A 38 B 动态产生，视情况而定 C 40 D 42

50.广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(a)))为（ A ） A x B (a,b) C (x,(a,b)) D A

51.设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n1,n3,n4,那么当把森林T转成一棵二叉树后，其根结点的右子树上有___D______个结点。 A n1-1 B n1 C m1+n2+n3 D n2+n3+n4 52.下列陈述正确的是（ D ）

A 二叉树是度为2的有序树 B 二叉树中结点只有一个孩子时无左右之分 C 二叉树中必有度为2的结点 D 二叉树中最多只有两棵子树，并且有左右之分

53.有一个长度为12的有序表，按二分查找法对该表进行查找 ，在表内各元素等概率情况

1.5

1.5

下，查找成功所需的平均比较次数 为（ B ）

A 35/12 B 37/12 C 39/12 D 43/12

.数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（ D ）

A 索引存储方法 B 顺序存储方法 C 链式存储方法 D 散列存储方法

55.队和栈的主要区别是（ B ）

A 逻辑结构不同 B 存储结构不同 C 限定插入和删除的位置不同 D 所包含的运算个数不同

56.在连接队列执行入队操作（ D ）

A 需判别队是否空 B 需判别队是否满 C 在链表头p进行 D 在链表尾p进行 57.将数组称为随机存储结构是因为（ C ）

A 数组元素是随机的 B 随时可以对数组元素进行访问 C 对数组的任一元素的存取时间是相等的 D 数组的存储结构是不定的

58.设rear是指向非空带头结点的循环单链表的尾指针，则删除表的首结点操作可表示为（ D ）

A p=rear;rear=rear->next;dispose(p);

B rear=rear->next;dispose(p);

C rear=rear->next->next;dispose(p);

D p=rear->next->next;rear->next->next=p->next;dispose(p); 59.一个有n个结点的二叉树，空指针有（ B ） A n B n+1 C n/2 D n*2

60.采用散列技术实现表的存储和查找 ，需解决的主要问题是（ D ）

A 如何申请到足够大的空间 B如何正确认识元素之间的逻辑关系 C 如何找到一个好的查找方法 D 如何构造一个散列地址均匀分布的散列函数

61.对n 个不同的排序码进行冒泡排序，在元素无序的情况下的次数为（ D ） A n+1 B n C n_1 D n(n-1)/2

62．对线性表进行二分查找时，要求线性表必须（C ）

A 以顺序方式存储 B 以链接方式存储 C 以顺序方式存储，且结点按关键字有序排列 D 以链接方式存储，且结点按关键字有序排列 63．非线性结构中，每个结点（ D ）

A 无直接前趋 B 只有一个直接前驱和后继 C 只有一个直接前趋和个数不受的直接后继 D 有个数不受的直接前趋和后继

.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ A ）

A 访问第I个结点（I大于等于1小于等于n）和求第I个结点的直接前趋（I大于等于2小于等于n）

B 在第I个结点后插入一个新结点（I大于等于1小于等于n） C 删除第I个结点（I大于等于1小于等于n） D 将n个结点从小到大排序

65.在栈中存取数据的原则是（ B ）

A 先进先出 B 先进先出 C 后进后出 D 随意进出 66.设长度为n的链队列用单链表表示，若只设头指针 ，则入队操作的时间复杂度为（ C ） A O（1） B O（log2n） C O(n) D O(n2) 67.在目标串T[0..n-1]=”xwxxyxy”中，对模式串p[0..m-1]=”xy”进行子串定位操作的结果 是（B ）

A 0 B 2 C 3 D 5

68.广义表head(tail(((a,b),(c,d)))的运算结果 是（ B ） A （a,b,c,d） B （（a,b）,(c,d)） C (a,b)(c,d) D ((a,b))

69.在一棵度为3的树中，度为3的结点个数 为2，度为2的结点个数为1，则度为0的结点个数为（ C ）

A 4 B 5 C 6 D 7

70.采用二分查找长度为n的线性表时，每个元素的平均查找长度为（ D ） A O（n） B O(nlog2n) C O(n) D O(log2n) 71．下列各式中，按增长率由小到大的顺序排列的是（）

A．2100，lgn,(2/3)n,nn Bnlgn,lgn,2n,nn C,nlgn, nn,2100 D (2/3)n,lgn, nlgn,n! 72.4个元素a1,a2,a3,a4依次通过一个栈，在a4进栈前，栈的状态如右图所示，不可能的出栈序列是（ D ）

栈顶- >

栈底->

a1 a2 a3 2

A a4,a3,a2,a1 B a3,a2,a4,a1 C a3,a4,a2,a1 D a3,a1,a4,a2 73.若进栈序列 为a,b,c则通过入出栈操作可能得到的a,b,c的不同排列个数为（ B ） A 4 B 5 C 6 D 7

74.设A和B分另为A=“This is String” B=”is”则（ A ）

A B是A的子串 B A是B的子串 C B在A的序号为4 D A为子串 75.已知广义表的表对为a ，表尾为（b,c）,则此广义表为（A） A (a,(b,c)) B (a,b,c) C ((a),,b,c) D ((a,b,c)) 76.一个非广义表的表头（D）

A 不可能是子表 B 只能是子表 C 只能是原子 D 可以是子表或原子

77.设结点x和结点y是二叉树T中的任意两个结点，若在先序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是（C）

A x是y左兄弟 B x是y的右兄弟 C x是y的祖先 D x是y的后代 78．二叉树中第5 层上的结点个数最多为（C ） A 8 B 15 C 16 D 32

79.在有n个元素的栈中插入一个结点的时间复杂度是（B） A O(n) B O(1) C O(log2n) D O(n2)

80.要进行顺序查找，则线性表（C）

A 必须以顺序方式存储 B 必须以链接方式存储 C 顺序，链接方式存储皆可以 D 顺序、链接方式存储皆不行

81.下列四种基本的逻辑结构中，数据元素之间关系最弱的是（A） A 集合 B 线性结构 C 树形结构 D 图状结构

82.在长度为n的顺序表的第I(I大于等于1小于等于n+1)个位置上插入一个元素，元素的移动次数为（A）

A n-I+1 B n-I C I D I-1

83.当栈空时再做退栈运算也将产生溢出，称为（B）

A 上溢 B 下溢 C 链栈 D 顺序栈

84.设输入序列为a,b,c,d,借助一个栈得到的输出序列不可能是（D） A a,b,c,d B a,c,d,b C a,c,b,a D d,a,b,c

85.串是任意有限个（C）

A 符号构成的序列 B 符号构成的集合 C 字符构成的序列 D 字符构成的集合 86.如右图所示广义表是一种（D ）

A线性表 D B纯表 C 再入表 D 递归表

87.深度为6（根的层次为1）的二叉树至多有______个结点。(D) A B 32 C 31 D 63

88.对于n个记录的有序表采用二分查找 ，其平均的查找长度是量级为（A） A O（log2n） B O(nlog2n) C O(n) D O(n) .下列有关数据结构的叙述，正确的是（C）

A 线性表的线性存储结构优于链式存储结构

B 二叉树的第I层上有2i-1个结点 ，深度为k的二叉树上有2k-1个结点 C 二维数组是其数据元素为线性表的线性表 D 栈的操作方式是先进先出

90.除了考虑存储结构本身所占用的空间外，实现算法所用辅助空间的多少称为算法的（B） A 时间效率 B 空间效率 C 硬件效率 D 软件效率

91.在链队列中，若f,r分别为队首、队尾指针，则插入S所指结点的操作为（B） A f->next=c; f=s; B r->next=s;r=s; C s->next=r;r=s; D s->next=f;f=s; 92.栈是一个_____线性表结构。（B ） A 不加 B 加了的 C 推广了的 D 非 93.如右图所示广义表是一种（B ） A A线性表 B纯表 C 再入表 D 递归表

94.若二叉树根结点的层次为1，所有含有7个结点的二叉树中，最小高度为（A） A 3 B 4 C 5 D 6

95.高度为h（h>0）的满二叉树对应的森林由几棵树构成（D） A 1 B log2h C h/2 D h 96.二分查找要求被表是（C）

A 键值有序的链表 B 链表但键值不一定有序 C 键值有序的顺序表 D顺序表但键值不一定有序

97.若将数据结构形式定义为二元组（K，R），其中K是数据元素的有限集合，则R是K上（D） A 操作的有限集合 B 映象的有限集合 C 类型的有限集合 D 关系的有限集合 98.在长度为n的顺序表中删除第I个元素（1<=I<=n）时，元素移动的次数为（D） A n-I+1 B I C I+1 D n-I 99.引起循环队列队头位置发生变化的操作是（A）

A 出队 B 入队 C 取队头元素 D 取队尾元素

100.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（D）

A 243156 B 324165 C 432156 D 2351

三、解答题

2

1.请画出与右图所示二叉树对应的森林。 G C J K A E I B D F 2.假设二叉树包含的结点数据为1，3，7，2，12. （1） 画出两棵高度最大的二叉树。

（2） 画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。

3.对二叉树中的结点进行按层次进行顺序（每一层自左到右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,.请画出该二叉树。

4.设二维数组A7*6的每个元素占6个字节，且LOC(a00)=100，问A共占多少个字节？ A的终端结点A65的起始地址为何？按行和按列优先存储时，a35的起始地址分别为何？

5.一棵二叉权的先序、中序和后序遍历序列分别如下，请构造出该二叉树。 先序：ABCDEFGHIJK 中序：CBEDFAHJKIG 后序：CEFDBKJIHGA

6．已知散列函数为H(k)=k mod 13，关键值序列为19，01，23，14，55，20，84，27，68，11，10，77，处理冲突的方法为线性探测法，散列表长度为13，试画出该散列表。

7.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

8.设散列函数为h(key)=key%|0|，解决冲突的方法为线性探查，表中用“-1”表示向上单元，若删去散列表HT中的304（即令HT[1]=-1）之后，

0 1 2 3 100

HT 202 304 507 707 …… 在表HT中查找707将会发生什么？若将删去的表项标记为“-2”，查找时探查到-2继续向前搜索，探查到-1时终止找搜索。请问用这种方法删304扣能否正确地查找到707？

9.已知一棵二叉树的广义表表示为a(b(c),d(e)),请画出该出该二叉树。

10.已知散列函数为H（k）=k mod 12，关键值 序列为25，37，52，43，84，99，120，15，26，11，70，82，处理冲突的方法为线性探测法，散列表长度为12，试画出该散列表。

11.设广义表L=（（ ），（ ）），试问head(L),tail(L),L的长度、深度各为多少？

12.写出右图所示二叉树的前序、中序和后序序列。

1 2 3 4

13.已知二叉树的中序和后序遍历序列分别如下： 中序：CBEDAFIGH 后序：CEDBIFHGA 构造该二叉树。

14.设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000,问A共占多少个字节？A的终端结点a47的起始地址为何？按行和按列优先存储时，a25的起始地址分别为何？

15.已知二叉树的后根序列和中根序列如下，构造出该二叉树。 后根序列：ABCDEFG 中根序列：ACBGEDF

16.已知一个散列表如下图所示： 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12

其散列函数h(key)key%13,处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+I*h1(key))%m I=0,1,…,m-1 其中

h1(key)=key%11+1

回答下列问题：

（1） 对表中关键字35，20，33和48进行查找时，所需进行的比较次数 各为多少？ （2） 该散列表在等概率查找时查找成功的平均查找成功的平均查找长度为多少？

17.将下图森林转换成为二叉树 D

18.将森林转换成二叉树

19.假设以数组seqn[m]存放循环队列的元素，设变量rear和quelen分别指向循环队列中队尾元素的位置和元素的个数。 （1） 写出队满的条件表达式。

（2） 写出队空的条件表达式。

（3） 设m=40，rear=13,quelen=19,求队头元素的位置。 （4） 写出一般情况下队头元素位置的表达式。

B A E H F G B A C H E F I J N O P G L K M C D

20.已知一棵二叉树的中序序列 为ABCDEFG,层序序列为BAFEGCD,请画出该二叉树。

四．算法阅读题

1. 所谓二叉树T1和T2是等价的，那就是说，或者T1和T2都是空的二叉树，或者T1和

T2都是非空的二叉树，且T1和T2的根结点的值相同，同时T1和T2的根结点的左子树是等价的，且T1和T2的根结点的右子树也是等价的。下面给出了判断二叉树T1和T2是否等价的程序。 Typedef struct tnode{

Int data;

Struct tnode lchild,rchild }tnode,*bitreptr;

int equalbitre(bitreptr t1,bitreptr t2) {int equal=0

if(t1==Null&&___t2==NULL_______________equal=1; else if (t1!=Null &&(_____t2!=NULL_________;)) if(t1->data==t2->data)

if(equalbitre(t1->lchild,t2->lchild))

___equal=equalbitre(t1->rchild,te->rchild)______________________; return equal; } (1) (2) (3)

2. 下列函数完成的功能是将整数数组A的元素按值递增的次序重新排序。在空格处填入适

当的句子，使该过程能完成预期的功能。

并回答该过程使用的是什么排序方法？(冒泡法排序)

Void sort (int A[500],int n) { int i,j,x;

boolean b; b=TRUE; i=1;

while(ib=FALSE;

for(j=0;j<_____________;j++) if(_______________) {

x=A[j];A[j]=A[j+1];A[j+1]=x; _________________; } i++; }

} (1)499 (2)A[j]>A[j+1] (3)b=TREE

3. 以下算法是从Hstring为存储表示，求子串的算法，请填入合适的内容，使其成为一个

完整的算法。

Void Substr(char *s,int i,int j) {

int k;

char *q,a[100];

if(s[i-1]!=’\\0’||s[i+j-1]!=’\\0’) {for(____________________) {a[k]=s[i-1]; i++; }

for(k=0;kprintf(“%c”,_________________); printf(“\\n”);} }

main() {

char s[ ]=”dfiofidfughh”; substr(s,3,3); }

（1）k=0;k（2）a[k]

4. 下面的函数是输出二叉树的各结点，读程序并在每个空格处填写一个语句或一个表达

式。 #define max 100

typedef struct tnode{ int data;

struct tnode *rchild,*rchild;

}tnode;

typedef struct stack{ tnode *elem[max] int top; }stack;

void printtree(tnode *bt) (stack s;tnode *p;

p=______________;s.top=0; while(p||s.top!=0) {while_____________;

{s.elem[s.top++]=p;_________________________;} if(s.top>0){_____________;printf(“%d”,p->data);

p=p->rchild; } } (1)bt

(2)p

(3)p=p->lchild

(4)p=s.elem[--s.top]

5. 指出下述程序段的功能是什么？ Void Demol(seqstack *s){ Int I;arr[];n=0;

While(StackEmpty(s))arr[n++]=Pop(s); For(i=0,i当栈不为空时，将栈中元素逆置

6. 阅读下列函数arrange( ) int arrange(int a[],int l,int h,int x)

{//l和n分别为数据区的下界和上界 int i,j,t; i=l,j=h; while(iwhile(i=x)j--; while(i{t=a[j];a[j]=a[i];a[i]=t; }

if(a[i]}

写出该函数的功能。

调整整数数组a[]中的元素并返回分界值，使所有的元素均落在a[1..i]上，使所有大于等于X的元素均落在a[I+1..n]上

7. 下面是前序遍历二叉树的非递归算法。 #define M 100

void preorderf(BinTree T) {int top=0;

BinTree p,x[M]; P=T;

While(p||top)

{while(p!=NULL)

{printf(“%d\”,p->data); s[top++]=p;

__________________; }

if(______________________){p=s[--top];________________;} }

}

(1)p=p->lchild (2)top>0

(3)p=p->rchild

8. 阅读下列算法，并回答下列问题

（1） 该算法采用何咱策略进行排序？

（2） 算法中R[n+1]的作用是什么？ Typedef struct{ KeyType key;

Info Type otherinfo;

}nodeType;

typedef nodeType SqList[MAXLEN]; voidsort(SqList R,int n) {

//n小于MAXLEN-1 int k,i;

for(k=n-1;k>=1;k--) if(R[k].key>R[k+1].key) {

R[n+1]=R[k];

For(i=k+1;R[I].keyR[i-1]=R[i]; R[i-1]=R[n+1]; } }

(1)该算法采用直接插入法进行排序

(2)r[n+1]是监视哨，主要用来监视下标变量是否赿界。

9. 阅读下列函数algo,并回答问题：

（1） 假设队列q中的元素为（2，4，5，7，8），其中“2”为队头元素，写出执行函

数调用algo(&q)后的队列q;

（2） 简述算法algo的功能。 Void algo(Queue *Q) {

Stack s;

Initstack(&s);

While(!Qunue Empty(Q)) Push(&s,Deueue(Q)); While(!Stack Empty(&s)) EnQueue(Q,Pop(&s));

}

(1) 执行函数后输出的队列Q是：872,头元素是：8 (2)algo算法的功能是将队列元素逆置

10. 下面的非递归程序是将二叉树t中所有结点的左右子树进行交换，程序中用一个链接栈

存放还未处理完毕的子树的根结点地址。读程序并在每个空格处填写一个语句或一个表达式。使其成为完整的算法。 Typedef struct tnode{

Char data;

Struct tnode *lchild,*rchild; }tnode;

typedef struct snode {tnode * addr; strcut snode *link; }snode; void exchange(t) tnode * t;

{snode *top,*s; tonde *p;

top=(snode *)malloc(sizeof(snode)); _____________________; top->link=NULL;

while(_______________)

{t=_____________________; s=top;top=top->link;;free(s); if(__________________){ p=t->lchild;

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

s=(snode*)malloc(sizeof(snode)); s->addr=t->lchild; s->link=top; top=s;

s=(snode *)malloc(sizeof(snode)); s->addr=t->rchild;

s->link=top;top=s;}}} (1) top->addr=bt (2) top!=NULL

(3) top->addr

(4) t&&(t->lchild||t->rchild)

11. 下面是一个自上往下扫描的冒泡排序的伪代码算法，它采lastExchange 来记录每趟扫描

中进行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值，请在下

划线处填上适当内容，使其成为一个完整的算法。 Void Bubblesort(int a[],int n) {

int LastExchange,j,I=n-1; while(I>0) {

LastExchange=0;

For(j=0If(____________________) {x=a[I]; a[j]=a[j+1]; a[j+1]=x;

____________________; I=LastExchange; }}

(1) a[j+1]12. 下列函数是按从大到小的次序输出二叉排序树的各结点。

Void order(BinTree *t) { if(___________________) {____________________; printf(“%d”,t->data);

_____________________;

}

}

(1) t!=NULL

(2) order(t->rchild) (3) order(t->lchild)

13. 指出下述程序段的功能

void demo2(stack *s,int m) {seqstack t; int I; initstack(&t);

while(!stackempty(s)) if(I=pop(s)!=m)push(&t,i) while(!stackempty(&t)) {I=pop(&t); push(s,i);} }

功能删除S中的元素m

14. 利用栈的基本操作，写一个返回S中结点个数的算法initstacksize(seqstack s),并说明S

为何不用作为指针参数。请在空缺处填入合适的内容，使其成为一个完整的算法。 Int initstacksize(seqstack s) {

seqstack *q; q=s; int I=0;

while(________________________) {I++;

_______________________________;} return I; }

(1)(!empty(q)) (2)q=top--

15. 指出下述程序段的功能是什么 seqstack s1,s2,tmp; datatype x; ……

while(!stackempty(&s1)) {s=pop(&s1);push(&tmp,x);} while(!stackempty(&tmp))

{x=pop(&tmp); push(&s1,x); push(&s2,x);} 复制栈S1到S2

16. 设栈s={1,2,3,4,5,6,7}，其中7为栈顶元素。请写出调用algo(&s)后栈S的状态 void algo(stack *s)

{

int I=0; queue q; stack t;

initqueue(&q);initstack(&t); while(!stackempty(s)) {

if((I!=I)!=0) push(&t,pop(&s)); else

enqueue(&q,pop(&s)); }

while(!queueempty(&q)) push(&s,dequeue(&q)); while(!stactempty(&t))

push(&s,pop(&t));}

S＝(6，4，2，1，3，5，7)其中7为栈顶元素

17. 下面是以二叉链表为存储结构，分别在二叉树中查找值为X的结点及求X所在结点在

树中层次的算法。请在空缺处填上合适的内容，使算法完整。 Int h=-1, lh=1,count=0;char x=’c’; Level(BinTree *t,int h,int lh) {

if (t==NULL)h=0; else

if(________________) { h=lh;

count=h; } else

{ lh++;

level(__________________); if(h==-1)level(_________________); } }

main()

{ BinTree **newroot; printf(“\\n”);

root=create BinTree(); inorder(root); printf(“\\n”);

level(________________); printf(“%d”,count); }

(1)t->data==x

(2)t->lchild,h,lh (3)t->rchild,h,lh (4)root,h,lh

18. 指出下述程序的功能 #define n 5

typedef int keytype; typedef stuct { keytype key; } rectype;

typedef rectype seqlist[n+1]; seqlist r; resort(seqlist r) {

int I,j=n-1; rectype x;

for(I=0;I0)

{ while(r[j].key>0&&j>i) j--; x=r[I]; r[I]=r[j]; r[j]=x; } } main() { int I;

seqlist r;

for(I=0liscanf(“%d”,&r[I].key); resort(r );

for(I=0;Iprintf(“\\n%d”,r[I].key); }

功能：将数组中所有取负的关键字放在所有取负的关键字之前

19. 阅读下列函数F，并回答问题：

（1） 已知如下图所示的二叉树以二叉链表作存储结构,rt为指向根结点的指针。写出

执行函数调用F（rt）的输出结果。

Rt->

b a c d e f

（2） 说明函数F的功能 void F(BinTree T) { Stack S; If(T) {

InitStack(&S); Push(&S,NULL); While(T) {

printf(“%c”,T->data);

if(T->rchild) push(&S,T->rchild); if(T->lchild) T=T->lchild; else T=Pop(&S); } }

}

(1)输出结果：printf打印出a,b,d而栈S中依次进栈顺序是h,f,c,g,e;退材之后最终输出结果是abdegcfh

(2) 功能：利用栈的性质对二叉树进行先根遍历 20. 下述程序段的功能是什么？ CirQueue Q1,Q2//dataType 为int 型

Int x,I,m=0;

…//设Q1已经有内容，Q2已初始化过

while(!QueueEmpty(&Q1)){x=DeQueue(&Q1);EnQueue(&Q2,x);m++} for(I=0;I五．算法设计题

1. 设线性表的n个结点定义为（a0,a1,a2,…,an-1）重写顺序表上实现的插入算法：InsertList

2. 设给寂静的散列存储空间为：H[0..m],每个H[i]单元可存放一记录，选取的散列函数为

H[R-key]，其中R-key为记录关键字，解决冲突的方法为线性探测法，试编写将记录R填入表H中的算法。

3. 利用一维数组int a[n]可以对n个整数进行排序，其中一种排序算法的处理思想是将n个

整数分别作为数组a的n个元素的值，每次（即第I次）从元素a[I]-a[n-1]中挑出最小的

一个元素a[k](i≤k≤n),然后将a[I]与a[k]换位，这样反复n次完成排序，请编写实现上述算法的过程，并分析完成排序所需的次数。

4.设一棵二叉树以二叉链表为存储结构，结点结构为 Lchild 。设计一个算法，求在先根序列中处于第k个位置的结点。

5.叉链表为存储结构，写一个拷贝二叉树的算法void CopyTree(BnTree root,BinTree *newroot

Data rchild

6.设一棵二叉树以二叉链表为存储结构，结点结构为

设计一个算法求此二叉树上度为2的结点个数。

,7.设一棵二叉树以二叉链表作为存储结构，结点结构为 Lchild Data 其中data域中存放一个字符，设计一个算法按先根遍序仅打印出data域为数字的字符（即’0’≤ data≤’9’）。

8.设一棵二叉树以二叉链表作为存储结构，结点结构为

，设计一算法求二叉树的高度。

Lchild Data Rchild Rchild 历顺

Lchild Data rchild

9.设计一算法，交换二叉树所有结点的左右子树。

10.设计一算法求二叉树的叶子结点个数。