数据结构与算法分析—期末复习题及答案

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

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

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。

A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 对线性表，在下列哪种情况下应当采用链表表示？( B )

A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )

A. 2 3 1 C. 3 1 2

B. 3 2 1 D. 1 2 3

6. 若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值 B．函数 C．指针 D．引用

8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A ）。

A．行号 B．列号 C．元素值 D．非零元素个数 10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为(C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)

二、 运算题（每题 6 分，共24分） 1. 数据结构是指数据及其相互之间的_联系。当结点之间存在M对N（M：N）

的联系时，称这种结构为__图__。

2. 队列的插入操作是在队列的___尾_进行，删除操作是在队列的_首_进行。 3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。

4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度

为___ O（1） __，在表尾插入元素的时间复杂度为___ O（n）___。

5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿128__个字节。W中第6 行的元素和第4 列的元素共占用__44_个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址__108_。 7. 二叉树是指度为2的___有序___树。一棵结点数为N的二叉树，其所有结点的度的总和是___n-1____。

8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_有序序列__。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__后缀表达式____。

9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。

10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。

11. 在线性表的散列存储中，处理冲突的常用方法有________________________和_____________________________两种。 12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。 三、 运算题（每题6分，共24分）

?0?0??0??0?5???000?10000000070000001??0?0???2?0??0??

1. 1. 已知一个6?5稀疏矩阵如下所示 试：（1） 写出它的三元组线性表；

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

2. 2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，

逐个输入各个数据而生成的二叉搜索树。

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

边结点都是按照终点序号从小到大的次序链接的，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树；

(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 4. 4. 已知一个图的顶点集V和边集E分别为：

V={1,2,3,4,5,6,7};

E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};

若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序

图6

号从小到大的次序链接的，按主教材

中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。 四、 阅读算法（每题7分，共14分） 1. 1. int Prime(int n)

{

int i=1;

int x=(int) sqrt(n);

while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0;

}

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

(2) (2) 该算法的时间复杂度是多少？ 2. 2. 写出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q;

InitQueue(Q); cout<

while(!QueueEmpty(Q)) { int k=QDelete(Q);

edgenode* p=GL[k]; while(p!=NULL) {

int j=p->adjvex; if(!visited[j])

cout<

QInsert(Q,j); }

p=p->next;

{

}

}

}

五、 算法填空（共8分）

如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) {

int low=0; int high=n-1;

while (low<=high) {

int mid=_______________________________；

if (K==A[mid].key) return mid; //查找成功，返回元素的下标

else if (K<[mid].key)

______________________________________; //在左子表上继续查找

else __________________________________; //在右子表上继续查找

}

return -1; //查找失败，返回-1 }

六、 编写算法（共8分）

HL是单链表的头指针，试写出删除头结点的算法。 ElemType DeleFront(LNode * & HL)

参考答案

6 1 3 4 5 5 5 2 5 1 5 1 -1 -2 5 7 1. 7. 有序 n-1

2. 8. 有序序列 后缀表达式（或逆波兰式） 3. 9. 2n n-1 n+1

4. 10. 2i+1 2i+2 (i-1)/2 5. 11. 开放定址法 链接法 6. 12. 快速 归并 一、 三、 运算题（每题6分，共24分）

1. 1. （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分)

6 3 图7 图8

（2） 三元组线性表的顺序存储表示如图7示。

2. 2. 如图8所示。

3. 3. DFS：?????

BFS：?????

4. 4. 拓朴排序为： 4 3 6 5 7 2 1

二、 四、 阅读算法（每题7分，共14分） 1. 1. (1) 判断n是否是素数（或质数）

（2）O（n）

2. 2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。 三、 五、 算法填空（8 分）

(low+high)/2 high=mid-1 low=mid+1 四、 六、 编写算法（8分） ElemType DeleFront(LNode * & HL) {

if (HL==NULL){ cerr<<\空表\

exit(1); }

LNode* p=HL; HL=HL->next;

ElemType temp=p->data; delete p; return temp; }

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

A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

1. 栈和队列的共同特点是( A )。

2. 用链接方式存储的队列，在进行插入运算时( D ).

A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？( D )

A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。C

A．688 B．678 C．692 D．696 5. 树最适合用来表示( C )。

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

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6. 二叉树的第k层的结点数最多为( D ).

A．2k-1 B.2K+1 C.2K-1 D. 2k-1

7. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D )

A. 1，2，3

B. 9，5，2，3

C. 9，5，3 D. 9，4，2，3

9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H

（K）=K %9作为散列函数，则散列地址为1的元素有（ D ）个，

A．1 B．2 C．3 D．4 10. 设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。

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

填空题

1. 通常从四个方面评价算法的质量：正确性 易读性 强壮性 高效率 2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为O(n) 4. 后缀算式9 2 3 +- 10 2 / -的值为___-1_。中缀算式（3+4X）-2Y/3对应的后缀算式为___3 4 X * + 2 Y * 3 / -__。

5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_2n__个指针域，其中有_n-1_个指针域是存放了地址，有__n+1_个指针是空指针。

6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_e_个和2e_个。

8. 在一个具有n个顶点的无向完全图中，包含有_ n(n-1) /2 _条边，在一个具有n个顶点的有向完全图中，包含有_ n(n-1)__条边。

9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为 （12，40） , （ ）, （74）,

（23,55，63）.

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

_ O(log2n)_，整个堆排序过程的时间复杂度为__ O(nlog2n)__。

运算题（每题 6 分，共24分）

1. 在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。

A 0 1 2 3 4 5 6 7

data next

60 5 50 7 78 2 90 0 34 4 40 1 3 2. 请画出图10的邻接矩阵和邻接表。

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

V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

图10

在最小生成树中依次得到的各条边。

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克鲁斯卡尔算法得到最小生成树，试写出

4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 四、阅读算法（每题7分，共14分）

1. LinkList mynote(LinkList L)

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

if(L&&L->next){

q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 请回答下列问题：

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

（3） 说明语句组S2的功能；

（3）设链表表示的线性表为（a1,a2, ?,an）,写出算法执行后的返回值所表示的线性表。

2. void ABC(BTNode * BT) {

if BT {

ABC (BT->left); ABC (BT->right); cout<data<<' '; } } 该算法的功能是： 算法填空（共8分）

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

bool Find(BTreeNode* BST,ElemType& item)

{

if (BST==NULL) return false; //查找失败 else {

if (item==BST->data){

item=BST->data;//查找成功 return ___________;}

else if(itemdata)

return Find(______________,item); else return Find(_______________,item); }} 编写算法（共8分）

统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x)

参考答案

运算题（每题

6分，共24分）

1. 1. 线性表为：（78，50，40，60，34，90） ?01?10??11??10?2. 2. 邻接矩阵：?01 邻接表如图11所示：

11011101010??1?1??1?0??

图11

3. 3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

4. 4. 见图12

2 4 4 2 2

2 4 4 5 4 5

8

2 3 5

4 8 图12

一、 四、 阅读算法（每题7分，共14分） 1. 1. （1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,?,an,a1） 2. 2. 递归地后序遍历链式存储的二叉树。 二、 五、 算法填空（每空2分，共8 分） true BST->left BST->right 三、 六、 编写算法（8分） int CountX(LNode* HL,ElemType x)

{ int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)

{ if (P->data==x) i++; p=p->next;

}//while, 出循环时i中的值即为x结点个数 return i; }//CountX

2 4 8 3 5 选择题

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

A n B n/2 C (n+1)/2 D (n-1)/2

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

A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 2、 3、 栈的插入和删除操作在（A ）进行。

A 栈顶 B 栈底 C 任意位置 D 指定位置

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

A 24 B 71 C 48 D 53 填空题（每空1分，共32分）

1、数据的逻辑结构被分为_集合、线性、树、图

2、一种抽象数据类型包括_数据描述 和 操作声名_两个部分。

3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，该线性表为__（38，56，25，60，42，74）___。

a 0 1 2 3 4 5 6 7 8 data next

4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为_ HL→next =NULL； HL=HL→next。

5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___前一个位置________，该循环队列的最大长度为__n-1___。

7、一棵高度为5的二叉树中最少含有__6__个结点，最多含有__63__个结点； 8、在图的邻接表中，每个结点被称为__边结点_，通常它包含三个域：一是邻接点域、权域、链域；。

60 3 56 7 42 6 38 2 74 0 25 1 4 运算题（每小题6分，共24分）

2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。 4、已知一个图的顶点集V各边集G如下：

V = {0，1，2，3，4，5，6，7，8，9}；

E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），

（5，8），（5，9），（6，7），（7，8），（8，9）}

当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。

假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。

图 深度优先序列 广度优先序列

算法填空，在画有横线的地方填写合适的内容（10分）

邻接矩阵表示时 邻接表表示时 对顺序存储的有序表进行二分查找的递归算法 。 int Binsch( ElemType A[ ],int low ,int high,KeyType K )

{

if (low <= high) {

int mid = 1

if ( K= = A[ mid ].key ) return mid; else if ( K < A[mid].key) return 2 else return 3 } else return 4

编写算法（10分）

编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，……an-1，an，则逆序链接后变为, an，an-1，……a1。 Void contrary (Lnode * & HL)

数据结构试题（答案）

三、运算题（每小题6分，共24分） 1、

划分次序 第一次 第二次 第三次 第四次 第五次 第六次

划分结果 [38 24 40] 46 [56 80 95 79] 24 [38 40] 46 [56 80 95 79] 24 38 40 46 [56 80 95 79] 24 38 40 46 56 [80 95 79] 24 38 40 46 56 79 [80 95] 24 38 40 46 56 79 80 95

2、 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 查找成功的平均查找长度：ASL SUCC=14/10= 1.4 3、此二叉树的后序遍历结果是：EDCBIHJGFA 4、

图 邻接矩阵表示时 邻接表表示时 深度优先序列 0，1，2，8，3，4，5，6，7，9 0，4，3，8，9，5，6，7，1，2 广度优先序列 0，1，4，2，7，3，8，6，5，9 0，4，1，3，7，2，8，6，9，5 20 31 23 36 12 。算法填空，在画有横线的地方填写合适的内容（10分） 1是：（low + high）/2;

2是： Binsch(A,low,mid–1,K); 3是： Binsch(A,mid+1,high,K); 4是： -1；

六、编写算法（10分） 根据编程情况，酌情给分。 {

Lnode *P=HL; HL=NULL; While (p!=null) {

Lnode*q=p; P=p→next; q→next=HL; HL=q; } }

选择题

1．算法指的是（ D ）

A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ B ） A．必须是不连续的 B．连续与否均可 C．必须是连续的

D．和头结点的存储地址相连续 3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度（ C ） A．O（1） B．O（n） C．O（m） D．O（m+n） 4．由两个栈共享一个向量空间的好处是：（ B ） A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率

C．减少存取时间，降低上溢发生的机率

D．节省存储空间，降低下溢发生的机率

5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ D ） A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 6．如下陈述中正确的是（ A ）

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

7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最

n坏情况下的时间复杂度是（ C ）

A．O（3） B．O（n） C．O（n2） D．O（n3）

10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为

0的结点个数为( C ) A．4 B．5 C．6 D．7

11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D ) A．e B．2e C．n2－e D．n2－2e

12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( C )

A．O(n) B．O(e) C．O(n+e) D．O(n*e)

16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的 存储 无关，是独立于计算机的。

17．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= p－＞next－＞next 。 18．栈顶的位置是随着 进栈和退栈 操作而变化的。

19．在串S=“structure”中，以t为首字符的子串有 12 个。

20．假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其

中B[0]存储矩阵中第1个元素a1,1,则B[31]中存放的元素是 a4,8 。

21．已知一棵完全二叉树中共有768结点，则该树中共有 384 个叶子结点。

24．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进

行的关键字比较次数为 2 。 解答题

26．画出下列广义表的共享结构图形表示 P=（（（z）,(x,y)）,((x,y),x),(z)） 27．请画出与下列二叉树对应的森林。

28．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示 a

b (1)画出该图的图形；

c （2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，d 写出相应的遍历序列。 e

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

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

回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？

（2）该散列表在等概率查找时查找成功的平均查找长度为多少？

??1当s1?s25分，共20分） 四、算法阅读题（本大题共4小题，每小题

?当s1?s2?030．下列算法的功能是比较两个链串的大小，其返回值为： ?1当s1?s2 comstr(s1,s2)=?

?01001???10010???00011????01101???10110?? 请在空白处填入适当的内容。 int comstr(LinkString s1,LinkString s2) {//s1和s2为两个链串的头指针 while(s1&&s2){

if(s1－>datedate)return－1； if(s1－>date>s2－>date)return1； ① ； ② ； }

if( ③ )return－1； if( ④ )return1； ⑤ ； }

31．阅读下面的算法

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针 if(L&&L->next){

q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next；

S2： p－>next=q；q－>next=NULL； }

return L； }

请回答下列问题：

（1）说明语句S1的功能； （2）说明语句组S2的功能；

（3）设链表表示的线性表为（a1,a2, ?,an）,写出算法执行后的返回值所表示的线性表。

32．假设两个队列共享一个循环向量空间（参见右下图），

其类型Queue2定义如下：

typedef struct{

DateType data[MaxSize]；

int front[2],rear[2]；

}Queue2；

对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。

int EnQueue (Queue2*Q,int i,DateType x)

{//若第 i个队列不满，则元素x入队列，并返回1；否则返回0 if(i<0||i>1)return 0；

if(Q－>rear[i]==Q－>front[ ① ]return0； Q－>data[ ② ]=x； Q－>rear[i]=[ ③ ];

return1；}

33．已知二叉树的存储结构为二叉链表，阅读下面算法。 typedef struct node { DateType data； Struct node * next； }ListNode；

typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) {

LinkList s；

If(T){

Inorder(T－>lchild)；

If ((!T－>lchild)&&(!T－>rchild)){

s=(ListNode*)malloc(sizeof(ListNode))； s－>data=T－>data； s－>next=Leafhead； Leafhead=s； }

Inorder(T－>rchild)； } }

对于如下所示的二叉树

（1）画出执行上述算法后所建立的结构；

（2）说明该算法的功能。

五、算法设计题（本题共10分） 34．阅读下列函数arrange()

int arrange(int a[],int 1,int h,int x) {//1和h分别为数据区的下界和上界 int i,j,t； i=1；j=h； while(i

while(i=x)j--； while(i=x)i++； if(i

{ t=a[j]；a[j]=a[i]；a[i]=t；} }

if(a[i]

（1）写出该函数的功能；

（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进

行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。

数据结构试题参考答案

三、解答题（本大题共4小题，每小题5分，共20分） 26．

图1 图2

28．该图的图形为：

深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１；

3?2?1?1?2 （２）平均查找长度ASL?530． ①S1=S1－>next ②s2=s2－>next

③s2(或s2!=NULL或s2&&!s1) ④s1(或s1!=NULL或s1&&!s2) ⑤return 0

31.（1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,?,an,a1） 32. ①(i＋1)%2(或1－i) ②Q－>rear[i]

③(Q－>rear[i]＋)%Maxsize 33.(1)Leafhead F H G D ∧ （2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以

Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至

左链接成一个链表）

五、算法设计题（本题共10分）

34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所

?9527．

四、算法阅读题（本大题共4小题，每小题5分，共20分）

有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。

（2）int f(int b[],int n) 或 int f(int b[],int n)

{ {

int p,q； int p,q；

p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； return q－p； return p－q；

} }

一、选择题

1．组成数据的基本单位是（ C）。

(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，

<3，4>，<4，1>}，则数据结构A是（C ）。

(A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合

3．数组的逻辑结构不同于下列（ D ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 (A) 2i

(B) 2i

(C) 2i

(D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操（ A ）。 (A) p->next=p->next->next (B) p=p->next

(C) p=p->next->next

(D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。

(A) 6 (B) 4 (C) 3 (D) 2

7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ C）。 (A) 100 (B) 40 (C) 55 (D) 80

8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（B ）。

(A) 3 (B) 4 (C) 5 (D) 1

9．根据二叉树的定义可知二叉树共有（B ）种不同的形态。 (A) 4

(B) 5

(C) 6

(D) 7

二、填空题(30分)

1. 设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =_ (F+1) % m_;。 2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度_ O(n)_，在链式存储结构上实现顺序查找的平均时间复杂度为__ O(n)_。

3. 设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有__2n__个指针域，__n+1_个空指针域。 4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点则在结点A的后面插入结点B的操作序列为___ s->next=p->next; s->next=s____。 5. 设无向图G中有n个顶点和e条边，则其对应的邻接表中有__n_个表头结点和__2e__个表结点。

6. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有_ m=2e 7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为_CBA___。

8. 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是_4_，编号为8的左孩子结点的编号是_16_。

9. 下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。

int index(char s[ ], char t[ ]) {

i=j=0;

while(i

if (j==strlen(t))return(i-strlen(t));else return (-1); }

10. 设一个连通图G中有n个顶点e条边，则其最小生成树上有__n-1__条边 三、应用题（30分）

1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。

2．设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 3．设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。

4．设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。

5．设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树。

四、算法设计题(20分)

1. 1. 设计判断单链表中结点是否关于中心对称算法。 2. 2. 设计在链式存储结构上建立一棵二叉树的算法。 3. 3. 设计判断一棵二叉树是否是二叉排序树的算法。

数据结构试卷参考答案 三、应用题

2. 2. 哈夫曼树略，WPL=78

01，2(5，316，42156，187，23) 3. 3. (18,5,16,19,21,23)，194. 4. 线性探测：?8?1025322768h0h1??8h231. 1. 链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。 h??10h4??25??32h5??68 链地址法：h6??27

5. 5. 深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，

3)，(3，5)，(5，6)，(5,6)} 四、算法设计题

1. 1. 设计判断单链表中结点是否关于中心对称算法。

typedef struct {int s[100]; int top;} sqstack; int lklistsymmetry(lklist *head) {

sqstack stack; stack.top= -1; lklist *p;

for(p=head;p!=0;p=p->next) {stack.top++; stack.s[stack.top]=p->data;} for(p=head;p!=0;p=p->next) if (p->data==stack.s[stack.top]) stack.top=stack.top-1; else return(0);

return(1); }

2. 2. 设计在链式存储结构上建立一棵二叉树的算法。

typedef char datatype;

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; void createbitree(bitree *&bt) {

char ch; scanf(\

if(ch=='#') {bt=0; return;}

bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); }

3. 3. 设计判断一棵二叉树是否是二叉排序树的算法。

int minnum=-32768,flag=1;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) {

if (bt!=0)

{inorder(bt->lchild); inorder(bt->rchild);}

}

if(minnum>bt->key)flag=0;

minnum=bt->key;

数据结构试卷（二）

一、选择题(24分)

1．下面关于线性表的叙述错误的是（ ）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现

2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m

3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M

4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5．设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）。 (A) 9 (B) 10 (C) 11 (D) 12

7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1

8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8

二、填空题(24分)

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

____________________和__________________________。

2. 2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。

typedef struct {int s[100]; int top;} sqstack; void push(sqstack &stack,int x) {

if (stack.top==m-1) printf(“overflow”);

else {____________________;_________________;} }

3. 3. 中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。 4. 4. 快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。 5. 5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中

度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。

6. 6. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。

7. 7. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选

法建立的初始堆为___________________________。

v1??3??2??4v2??1??3v3??1??4??28. 8. 设某无向图G的邻接表为v4??1??3，则从顶点V1开始的深度优先遍历

序列为___________；广度优先遍历序列为____________。

三、应用题(36分)

1． 1． 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单

选择排序和第4趟直接插入排序后的结果。

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

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

3． 3． 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方

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

4． 4． 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，

E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。 5． 5． 设有无向图G（如右图所示），要求给出用普里姆算法构造

最小生成树所走过的边的集合。

6． 6． 设有一组初始记录关键字为(45，80，48，40，22，78)，

要求构造一棵二叉排序树并给出构造过程。

四、算法设计题(16分)

1． 1． 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)

的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

2． 2． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和

C用链式存储结构表示。

数据结构试卷（二）参考答案

一、选择题 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C

二、填空题

1. 1. 构造一个好的HASH函数，确定解决冲突的方法 2. 2. stack.top++，stack.s[stack.top]=x 3. 3. 有序

2

4. 4. O(n)，O(nlog2n) 5. 5. N0-1，2N0+N1 6. 6. d/2

7. 7. (31，38，54，56，75，80，55，63) 8. 8. (1，3，4，2)，(1，3，2，4)

三、应用题

1. 1. (22，40，45，48，80，78)，(40，45，48，80，22，78) 2. 2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 3. 3. 2,ASL=91*1+2*2+3*4+4*2)=25/9 4. 4. 树的链式存储结构略，二叉树略

5. 5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6. 6. 略

四、算法设计题

1. 1. 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在

O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。 void quickpass(int r[], int s, int t) {

int i=s, j=t, x=r[s]; while(i

while (ix) j=j-1; if (i

r[i]=x; }

2. 2. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B

和C用链式存储结构表示。

typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) {

lklist *p,*q,*t;

for(p=ha,hc=0;p!=0;p=p->next)

{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;

if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } }

数据结构试卷（三）

一、选择题(30分)

1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构 2．下面程序的时间复杂为（ ）

for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)

3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。

(A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)；

4．设有n个待排序的记录关键字，则在堆排序中需要（ ）个辅助记录单元。 (A) 1 (B) n (C) nlog2n (D) n2

5．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21

6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。

2

(A) O(1) (B) O(log2n) (C) (D) O(n)

7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e 8. 设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1)

9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序 10.下列四种排序中（ ）的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序

二、填空殖(48分，其中最后两小题各6分)

1. 1. 数据的物理结构主要包括_____________和______________两种情况。

2. 2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉

链表作为该完全二叉树的存储结构，则共有___________个空指针域。

3. 3. 设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序

列。

4. 4. 设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素

之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。

5. 5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。 6. 6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的

关系为_________。

7. 7. __________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、

中序或后序）。

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

比较________次就可以断定数据元素X是否在查找表中。

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

度均为____________。

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

则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。 11. 11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基

准的一趟快速排序结果为___________________________。

12. 12. 设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，

则该图的一种拓扑序列为____________________。

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

句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k) {

int i,j; j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);} if (_______________________ ) return(j); else return(-1); }

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

typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree; bitree *bstsearch(bitree *t, int k) {

if (t==0 ) return(0);else while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________; }

三、算法设计题(22分)

1． 1． 设计在单链表中删除值相同的多余结点的算法。 2． 2． 设计一个求结点x在二叉树中的双亲结点算法。

数据结构试卷（三）参考答案

一、选择题

1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D

第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。

第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。

二、填空题

1. 1. 顺序存储结构、链式存储结构 2. 2. 9，501 3. 3. 5

4. 4. 出度，入度 5. 5. 0 6. 6. e=d 7. 7. 中序 8. 8. 7 9. 9. O(1)

10. 10. i/2，2i+1

11. 12. 13. 14.

11. (5，16，71，23，72，94，73) 12. (1，4，3，2)

13. j+1，hashtable[j].key==k 14. return(t)，t=t->rchild

第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。

三、算法设计题

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

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) {

lklist *p,*q,*s;

for(p=head;p!=0;p=p->next) {

for(q=p->next,s=q;q!=0; )

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } }

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

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) {

if (bt!=0 && flag==0)

if (bt->data==x) { flag=1; return;}

else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } }

void parent(bitree *bt,char x) {

int i;

preorder(bt,x);

for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf(\

else if (i<=r) printf(\}

数据结构试卷（四）

一、选择题(30分)

1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。

(A) O(n) (B) O(nlogn) (C) O(1) (D) O(n2

2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。 (A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1

3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。 (A) n (B) e (C) 2n (D) 2e 4．在二叉排序树中插入一个结点的时间复杂度为（ ）。

(A) O(1) (B) O(n) (C) O(log2

2n) (D) O(n)

5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 (A) n (B) n-1 (C) m (D) m-1

6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ 趟的分配和回收才能使得初始关键字序列变成有序序列。

）

(A) 3 (B) 4 (C) 5 (D) 8 7．设用链表作为栈的存储结构则退栈操作（ ）。 (A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈不作任何判别 8．下列四种排序中（ ）的空间复杂度最大。 (A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆

9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l

10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)

二、填空题(42分)

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

序的平均时间复杂度为_________。

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

为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。 3． 3． 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。 4． 4． 深度为k的完全二叉树中最少有____________个结点。

5． 5． 设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______

个元素开始进行筛选。

6． 6． 设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链

表作为存储结构，则该树中有_____个空指针域。 7． 7． 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________

个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。

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

中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。 9． 9． 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟

快速排序结果为______________________________。

10．10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字

序列建成的初始堆为________________________。

11．11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶

点j互为邻接点的条件是______________________。

12．12．设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上

非0元素的个数（填等于，大于或小于）。

13．13．设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后

序遍历该二叉树的序列为_____________。

14．14．设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填

上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。

typedef struct node {int key; struct node *next;} lklist; void createlkhash(lklist *hashtable[ ]) {

int i,k; lklist *s;

for(i=0;i

s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];

k=a[i] % p; s->next=hashtable[k];_______________________;

}

}

三、算法设计题(28分)

1． 1． 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单

链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 1. 2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 2. 3. 在链式存储结构上建立一棵二叉排序树。

数据结构试卷（四）参考答案

一、选择题

1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A

二、填空题

1. 1. O(n2)，O(nlog2n)

2. 2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink 3. 3. 3 4. 4. 2k-1 5. 5. n/2 6. 6. 50，51

7. 7. m-1，(R-F+M)%M 8. 8. n+1-i，n-i

9. 9. (19，18，16，20，30，22) 10. 10. (16，18，19，20，32，22) 11. 11. A[i][j]=1 12. 12. 等于 13. 13. BDCA

14. 14. hashtable[i]=0，hashtable[k]=s

三、算法设计题

1. 1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单

链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 typedef char datatype;

typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) {

lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) {

head=p->next; p->next=0;

if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}

else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } }

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

typedef struct node {int data; struct node *lchild,*rchild;} bitree; void swapbitree(bitree *bt) {

bitree *p;

if(bt==0) return;

swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p;

}

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

#define n 10

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void bstinsert(bitree *&bt,int key) {

if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); }

void createbsttree(bitree *&bt) {

int i;

for(i=1;i<=n;i++) bstinsert(bt,random(100)); }

数据结构试卷（五）

一、选择题(30分)

1．数据的最小单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。 (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，20

3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。

(A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85 4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ ）。 (A) “STRUCTURE” (B) “DATA” (C) “ASTRUCTUR” (D) “DATASTRUCTURE” 5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)

6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ ）。 (A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm (C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm

7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。 (A) 25 (B) 10 (C) 7 (D) 1

8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb

9．设输入序列是1、2、3、??、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ）。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定

10 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为

基准而得到一趟快速排序的结果是（ ）。 (A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88

(C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80

二、填空题(共30分)

1. 1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈

顶指针top2的初值为n，则判断共享栈满的条件是____________________。

2. 2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。 3. 3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括

对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。

4. 4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称

为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。

5. 5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前

序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。

6. 6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有

__________个叶子结点。

7. 7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数

之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。 8. 8. 设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言

满足的条件为_______________________________。

9. 9. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。 void bubble(int r[n]) {

for(i=1;i<=n-1; i++) {

for(exchange=0,j=0; j<_____________;j++)

if (r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if (exchange==0) return； } }

10. 10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。 struct record{int key; int others;}; int bisearch(struct record r[ ], int k) {

int low=0,mid,high=n-1; while(low<=high) {

________________________________;

if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1; }

return(0); }

三、应用题(24分)

1. 1. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为

ABDEC，要求给出该二叉树的的后序遍历序列。 2. 2. 设无向图G（如右图所示），给出该图的最小生成树上边的集

合并计算最小生成树各边上的权值之和。

3. 3. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，

要求计算出成功查找时的平均查找长度。

4. 4. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关

键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

四、算法设计题(16分)

1． 1． 设计判断两个二叉树是否相同的算法。 2． 2． 设计两个有序单链表的合并排序算法。

数据结构试卷（五）参考答案

一、选择题 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C

二、填空题

1. 1. top1+1=top2

2. 2. 可以随机访问到任一个顶点的简单链表 3. 3. i(i+1)/2+j-1 4. 4. FILO，FIFO

5. 5. ABDECF，DBEAFC，DEBFCA 6. 6. 8，64

7. 7. 出度，入度

8. 8. ki<=k2i && ki<=k2i+1 9. 9. n-i，r[j+1]=r[j]

10. 10. mid=(low+high)/2，r[mid].key>k

三、应用题

1. 1. DEBCA

2. 2. E={(1,5),(5,2),(5,3),(3,4)},W=10 3. 3. ASL=(1*1+2*2+3*4)/7=17/7 4. 4. ASL1=7/6，ASL2=4/3 四、算法设计题

1. 1. 设计判断两个二叉树是否相同的算法。

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; int judgebitree(bitree *bt1,bitree *bt2) {

if (bt1==0 && bt2==0) return(1);

else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0);

else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); }

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

void mergelklist(lklist *ha,lklist *hb,lklist *&hc) {

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;} else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; }

}

数据结构试卷（八）

一、选择题(30分)

1. 1. 字符串的长度是指（ ）。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C) 串中所含字符的个数 (D) 串中不同数字的个数 2. 2. 建立一个长度为n的有序单链表的时间复杂度为（ ） (A) O(n) (B) O(1) (C) O(n2) (D) O(log2n) 3. 3. 两个字符串相等的充要条件是（ ）。 (A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等 (C) 同时具备(A)和(B)两个条件 (D) 以上答案都不对 4. 4. 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。 (A) 99 (B) 97 (C) 91 (D) 93

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

2

(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n)

6. 6. 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中

比较元素的顺序为( )。 (A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4] (C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]

7. 7. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ ）。 (A) 8 (B) 7 (C) 6 (D) 5

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

点，则该三叉链权中有（ ）个度数为0的结点。 (A) 5 (B) 6 (C) 7 (D) 8

9. 9. 设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，

c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。 (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc 10. 10. 队列是一种（ ）的线性表。 (A) 先进先出 (B) 先进后出 (C) 只能插入 (D) 只能删除

二、判断题(20分)

1. 1. 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（ ） 2. 2. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ ） 3. 3. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存

在的块号，然后再在相应的块内进行顺序查找。（ ） 4. 4. 二维数组和多维数组均不是特殊的线性结构。（ ）

5. 5. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ ） 6. 6. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（ ） 7. 7. 非空的双向循环链表中任何结点的前驱指针均不为空。（ ）

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

度均为O(n)。（ ）

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

被访问过。（ ）

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

三、填空题(30分)

1． 1． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增

量的一趟希尔排序结束后的结果为_____________________________。

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

确的内容。

typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree; void bstinsert(bitree *&t,int k) {

if (t==0 ) {____________________________;t->data=k;t->lchild=t->rchild=0;} else if (t->data>k) bstinsert(t->lchild,k);else__________________________; }

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

的后面插入结点X需要执行的语句序列：s->next=p->next; _________________;。

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

结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。

5． 5． 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历

序列为__________。

6． 6． 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。 7． 7． 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素A[i][j]的

值等于____________。

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

选择排序结束后的结果为_____________________________。

9． 9． 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。 10． 10． 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它

们调整成初始堆只需把16与___________相互交换即可。

四、算法设计题(20分)

1. 1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。 2. 2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

数据结构试卷（八）参考答案

一、选择题 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A

二、判断题

1．对 2．错 3．对 4．错 5．错 6．对 7．对 8．对 9．对 10．对

三、填空题

1. 1. (49，13，27，50，76，38，65，97)

2. 2. t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k) 3. 3. p->next=s

4. 4. head->rlink，p->llink 5. 5. CABD 6. 6. 1，16 7. 7. 0

8. 8. (13，27，38，50，76，49，65，97) 9. 9. n-1 10. 10. 50

四、算法设计题

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

void countnode(bitree *bt,int &count) {

if(bt!=0)

{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} }

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

typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;

typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) {

int i,j; glinklistnode *p;

for(i=0;i<=n-1;i++) g2[i].firstarc=0; for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) if (g1.edge[i][j]==1) {

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p;

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } }

数据结构试卷（九）

一、选择题(30分)

1．下列程序段的时间复杂度为（ ）。

for(i=0； i

for(i=0； i

2．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。 (A) n-i (B) n+l -i (C) n-1-i (D) i

3．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（ ）。 (A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3 4．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ ）。

2

(A) O(n) (B) O(nlog2n) (C) O(n) (D) O(1og2n)

5．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（ ）。

(A) p->right=s； s->left=p； p->right->left=s； s->right=p->right； (B) s->left=p；s->right=p->right；p->right=s； p->right->left=s； (C) p->right=s； p->right->left=s； s->left=p； s->right=p->right； (D) s->left=p；s->right=p->right；p->right->left=s； p->right=s； 6．下列各种排序算法中平均时间复杂度为O(n2)是（ ）。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序

7．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ ）。 (A) n-i (B) n-1-i (C) n+l -i (D) 不能确定

8．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（ ）。 (A) 小于等于m的最大奇数 (B) 小于等于m的最大素数 (C) 小于等于m的最大偶数 (D) 小于等于m的最大合数

9．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（ ）个。 (A) 4 (B) 5 (C) 6 (D) 7 10.设完全无向图中有n个顶点，则该完全无向图中有（ ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 11.设顺序表的长度为n，则顺序查找的平均比较次数为（ ）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2

12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（ ）次比较。 (A) 1 (B) 2 (C) 3 (D) 4

13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ ）。 (A) 6 (B) 11 (C) 5 (D) 6.5

14.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（ ）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3

15.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。 (A) 4 (B) 5 (C) 6 (D) 7 二、填空题(30分)

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

面插入结点X时的操作序列为：

1) s->next=___________；2) p->next=s；3) t=p->data； 4) p->data=___________；5) s->data=t；

2． 2． 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结

点。

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

置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。

4． 4． 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排

序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。

5． 5． 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最

好选择_________排序，如果从节省存储空间的角度来考虑则最好选择________排序。 6． 6． 设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录

关键字构造的二叉排序树的平均查找长度是_______________________________。 7． 7． 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉

树的前序序列为____________________。

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

2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。

9． 9． 设一组记录关键字序列为(80，70，33，65，24，56，48)，

则用筛选法建成的初始堆为_______________________。 10． 10． 设无向图G（如右图所示），则其最小生成树上所有边的

权值之和为_________________。

三、判断题(20分)

1． 1． 有向图的邻接表和逆邻接表中表结点的个数不一定相等。( ) 2． 2． 对链表进行插入和删除操作时不必移动链表中结点。( ) 3． 3． 子串“ABC”在主串“AABCABCD”中的位置为2。( )

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

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

5． 5． 希尔排序算法的时间复杂度为O(n2)。( )

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

图中边数有关。( )

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

8． 8． 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( ) 9． 9． 顺序表查找指的是在顺序存储结构上进行查找。（ ） 10．10．堆是完全二叉树，完全二叉树不一定是堆。（ ）

五、算法设计题(20分)

1． 1． 设计计算二叉树中所有结点值之和的算法。 2． 2． 设计将所有奇数移到所有偶数之前的算法。 3． 3． 设计判断单链表中元素是否是递增的算法。

数据结构试卷（九）参考答案

一、选择题 1．A 2．A 3．A 4．C 5．D 6．D 7．C 8．B 9．C 10．A 11．C 12．C 13．D 14．A 15．A

二、填空题

1. 1. p->next，s->data 2. 2. 50 3. 3. m-1 4. 4. 6，8

5. 5. 快速，堆 6. 6. 19/7 7. 7. CBDA 8. 8. 6

9. 9. (24，65，33，80，70，56，48) 10. 10. 8

三、判断题

1．错 2．对 3．对 4．对 5．错 6．错 7．对 8．对 9．错 10．对 四、算法设计题

1． 1． 设计计算二叉树中所有结点值之和的算法。

void sum(bitree *bt,int &s) {

if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} }

2． 2． 设计将所有奇数移到所有偶数之前的算法。

void quickpass(int r[], int s, int t) {

int i=s,j=t,x=r[s]; while(i

while (i

r[i]=x; }

本文来源：https://www.bwwdw.com/article/sl0g.html