数据结构习题与实验指导

1

第一部分习题

第一章 绪论

一．单选题

1．若一个数据具有集合结构，则元素之间具有（ ）。

A．线性关系 B．层次关系 C．网状关系 D．无任何关系 2．下面程序段的时间复杂度为（ ）。 int i,j;

for(i=0;i

A．O(m2) B．O(n2) C．O(mхn) D．O(m+n) 3．执行下面程序段时，S语句被执行的次数为（ ）。 int i,j;

for(i=1;i<=n;i++) for(j=1;j<=i;j++) S;

A．n2 B．n2/2 C．n(n+1) D．n(n+1)/2

二．填空题

1．数据的逻辑结构被分为_____________、_____________、_____________和_____________四种。

2．数据的存储结构被分为_____________、_____________、_____________和_____________四种。

3．在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着_____________、_____________和_____________的联系。

4．在C语言中，一个数组a所占有的存储空间的大小即数组长度为_____________，下标为i的元素a[i]的存储地址为_____________。

5．在下面程序段中，s=s+p语句的执行次数为_____________，p*=j语句的执行次数为_____________，该程序段的时间复杂度为_____________。 int i=0,s=0; while(++i<=n) { int j,p=1;

for(j=1;j<=i;j++) p*=j; s=s+p; }

6．某算法仅含2个语句，其执行次数分别为1000n2和0. 01n3，则该算法的时间复杂度为_____________。

7．一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级表示为__________。

三．应用题

2

有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。 1．A=（K，R）其中 K={a1,a2,a3,…,an} R={}

2．B=（K，R）其中 K={a,b,c,d ,e,f,g,h}

R= {< a,b >,< b,c >,< c,d >,< d ,e >,< e,f >,< f,g >,< g,h >} 3．C=（K，R）其中 K={a,b,c,d ,e,f,g,h}

R= {< d,b >,< d,g >,< b,a >,< b ,c >,< g,e >,< g,h >,< e,f >} 4．D=（K，R）其中 K={1,2,3,4,5,6}

R= {(1,2), (2,3), (2,4), (3,4), (3,5), (3,6), (4,5), (4,6) }

第二章 线性表

一．单选题

1．下列有关线性表的叙述中，正确的是（ ）。

A．线性表中的元素之间是线性关系 B．线性表中至少有一个元素 C．线性表中任何一个元素有且仅有一个直接前驱 D．线性表中任何一个元素有且仅有一个直接后继

2．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i

3．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（ ）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i

4．在一个长度为n的顺序表中插入一个元素的时间复杂度为（ ）。 A．O(n) B．O(n/2) C．O(1) D．O(n2) 5．不带头结点的单链表的头指针为head，则该链表为空的判定条件是（ ）。 A．head ==NULL B．head->next==NULL C．head !=NULL D．head->next !=NULL

6．带头结点的单链表的头指针为head，判定该链表为非空的条件是（ ）。 A．head ==NULL B．head->next==NULL C．head !=NULL D．head->next !=NULL

7．在一个头指针为ph的单链表中，若要在结点*p之后插入一个结点*s，则应执行的语句是（ ）。

A．s->next =p->next; p->next=s; B．p->next=s; s->next =p->next; C．p->next=s->next; s->next=p; D．s->next=p; p->next=s->next; 8．在一个带头结点的循环双向链表中，若要在指针p所指向的结点之后插入一个q指针所指向的结点，则需要对q->right赋值为（ ）。

A．p->left B．p->right

3

C．p->right->right D．p-> left->left

9．在一个带头结点的循环双向链表中，若要在指针p所指向的结点之前插入一个q指针所指向的结点，则需要对p->left->right赋值为（ ）。

A．q B．p

C．p->right D．p-> left

10．在下列对顺序表进行的操作中，算法时间复杂度为为O(1)的是（ ）。

A．访问第i个元素的前驱（1

二．填空题

1．若经常需要对线性表进行插入和删除运算，则最好采用_____________存储结构；若经常需要对线性表进行查找运算，则最好采用_____________存储结构。

2．访问一个线性表中具有给定值元素的时间复杂度为_____________。

3．在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为_____________。

4．在一个单链表中删除指针p所指向结点的后继结点时，需要把_____________的值赋给p->next指针域。

5．在以HL为表头指针的带头结点的单链表和循环单链表中，链表为空的条件分别为_____________和 _____________。

6．在一个带头结点的循环单链表中,在表头插入或删除，与在其它位置插入或删除，其操作过程是_____________的。

三．算法填空与应用题

1．在带头结点的单链表H中的P结点前插入一个元素X。 void insert_linkst(Lnode *H, Lnode *P,elemtp X) { q=H;

while(q->next!=p) q= q->next;

S=( Lnode * )malloc(sizeof(_____________)); _____________=X; S->next=P;

_____________; }

2．在双向链表中的p结点前插入一个s结点，假设s已生成。 s->prior=_____________; s-> next=_____________;

p->prior-> next=_____________; p->prior =_____________; 3．设单链表的结点结构如下： typedef_char DataType struct node

4

{ DataType data; struct node *next; }

阅读下列算法f，简述算法f的功能。 int f(struct node *L) { struct node *p; int n=0; p=L; while(p)

{ if(p->next==’B’) n++; p= p->next; }

return(n); }

第三章 栈和队列

一．单选题

1．栈的插入和删除操作在（ ）进行。

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

2．假定利用数组a[N]顺序存储一个栈，用top表示栈指针，top== -1表示栈空，则当元素x进栈时所执行的操作为（ ）。

A．a[--top] =x B．a[top --]=x C．a[++top] =x D．a[top ++]=x 3．假定利用数组a[N]顺序存储一个栈，用top表示栈指针，top== -1表示栈空，并已知栈未空，则当退栈并返回栈顶元素时所执行的操作为（ ）。

A．return a[--top] B．return a[top --] C．return a[++top] D．return a[top ++]

4．当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。

A．top++ B．top-- C．top=0 D．top=N

5．假定一个链栈的栈顶指针用top表示，则当p所指向的结点进栈时，执行的操作为（ ）。

A．p->next =top； top = top->next； B．top=p; p->next= top ; C．p->next= top->next; top->next =p; D．p->next= top; top =p; 6．若让元素1、2、3、4依次进栈，则不可能的出栈次序是（ ）。 A．3421 B．3241 C．1234 D．4312

7．当利用大小为N的数组顺序存储一个队列时，若没有队列长度的变量，则该队列的最大长度为（ ）。

A．N-2 B．N-1 C．N D． N+1

8．假定一个链队的队首和队尾指针分别为front和rear，则判别队空的条件为（ ）。

A．front==rear B．front!=NULL C．rear!= NULL D．front== NULL

5

9．假定一个带头结点的循环链队的队首和队尾指针分别用front和rear表示，则判别队空的条件为（ ）。

A．front!=rear B．rear ==NULL C．front == NULL D．front== rear

10．在一个长度为N的数组空间中，顺序存储一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中的元素个数为（ ）。

A．（rear –front）%N B．（rear –front+N）%N C．（rear+N）%N D．（ front +N）%N 11．下列说法中错误的是（ ）。

A．循环队列空时，其front与rear等值 B．循环队列的任何元素都可随机存取 C．循环队列满时，其front与rear等值 D．循环队列有先进先出特征

12．在具有m个单元的循环队列中，队首指针为front，队尾指针为rear，约定少用一个元素空间，则队满的条件是（ ）。

A．front==rear B．（front+1）%m==rear C．rear+1== front D．（rear+1）%m == front

二．填空题

1．当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为_____________。

2．向一个栈顶指针为HS的链栈中插入一个新结点*p时，应执行_____________和_____________操作。

3．中缀表达式3*（x+2）-5所对应的后缀表达式为_____________。 4．后缀表达式45*32 +-的值为_____________。

6．设元素a、b、c、d依次进S栈，若要在输出端得到序列cbda，则应执行的操作序列为 push(S,a); push(S,b); push(S,c);

_____________; _____________; _____________; pop(S); pop(S);

1．在一个不设队列长度变量的顺序队列Q中，队首和队尾指针分别用front和rear表示，则判别队空的条件为_____________，判别队满的条件为_____________。

7．用S表示入栈操作，X表示入栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列SSXSXX，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作串为_____________。

8．设栈S和队列Q的初始状态为空，元素1、2、3、4、5和6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是3、5、4、6、2

6

和1，则栈S至少应该容纳_____________个元素。

三．运算题

1．有四个元素a、b、c、d依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列和所有不存在的序列。

2．假定用一维数组a[7]顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：23、45、67、80、34，其中23为队首元素，front的值为3，请画出对应的存储状态；当连续做4次出队运算后，再让15、36、48元素依次进栈，请再次画出对应的存储状态。

四．算法填空题

1．在以top为栈顶指针的链栈中插入一个元素x。 SNode * Push_L(SNode *top, ELEMTP x) { p=(SNode * )malloc(sizeof(SNode)); p->date=x;

_____________; _____________; return top; }

2．链栈出栈的算法。

SNode * pop_L(SNode *top, ELEMTP *y, int *flag) { if(top==NULL) *flag =0; else

{ p= top ;

*y =_____________; top =_____________; free(p); *flag =1; }

_____________; }

第四章 数组和广义表

一．单选题

1．二维数组A[4][4] 采用行优先的存储方法，数组元素A[0][0]的起始地址为1000，数组元素的长度为2，则元素A[2][2]的地址是（ ）。

A．1000 B．1010 C．1008 D．1020 2．二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且第一个元素A[0][0]的地址为150，则元素A[9][7]的地址为（ ）。

A．429 B．432 C．435 D．438

7

3．设一个广义表为（a,（b,c,（d,e,f））,g），则该广义表的长度为（ ）。 A．1 B．2 C．3 D．6 4．设一个广义表为（a,（b,c,（d,e,f））,g），则该广义表的深度为（ ）。 A．1 B．2 C．3 D．4

5．已知广义表的表头为a，表尾为（b,c）,则此广义表为（ ）。 A．（a，（b,c）） B．（a，b，c） C．（（a），b，c） D．（（a，b，c）） 6．在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）。

A．行号 B．列号 C．元素值 D．地址

二．填空题

1．二维数组A[i][j]（10≤i≤20，5≤j≤10）采用行为主序方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是_____________。

2．n阶三角矩阵的上三角元素值相等，进行压缩存储时，该值存储在下标为_____________数组元素中。

3．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_____________、_____________和_____________三项。

4．在稀疏矩阵所对应的三元组线性表中，每个三元组元素按________________为主序、_____________为辅序的次序排列。

5．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向_____________相同的下一个结点，right指针域指向_____________相同的下一个结点。

6．一个广义表中的元素分为____________元素和___________元素两类。 7．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为__________域和_____________域。 8．在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有_____________个域，在相应的十字链接存储中，每个结点包含有_____________个域。

三．应用题

1．已知一个6行х7列的稀疏矩阵如下图所示：

0 4 0 0 0 0 0 0 0 0 -3 0 0 1 8 0 0 0 0 0 0 0 0 0 5 0 0 0 0 -7 0 0 0 2 0 0 0 0 6 0 0 0

⑴写出它的三元组线性表； ⑵给出它的顺序存储表示；

⑶给出它的转置矩阵的三元组线性表和顺序存储表示； 2．对于广义表E（a,（a,b）,（（a,b）,c））），画出其图形，并求其长度和深度。

8

第五章 树和二叉树

一．单选题

1．一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f))，则该二叉树的高度为（ ）。

A．3 B．4 C．5 D．6 2．右图中树的度为（ ）。 A． 2 B． 3 C．5 D．8

3．高度为h的完全二叉树中，结点数最多为（ ）。 hh

A． 2h-1 B． 2h+1 C．2-1 D．2

4．已知一棵含20个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）。

A． 0 B． 1 C． 18 D．19

5．在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。 A．n B．n-1 C．n+1 D．2n

6．在一棵深度为h的完全二叉树中，所有结点个数不小于（ ）。

hh+1hh-1

A．2 B．2 C．2-1 D．2

7．在一棵深度为h的完全二叉树中，所有结点个数不大于（ ）。 A．2h B．2h+1 C．2h-1 D．2h-1

8．在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ ）。 A. (n+1)/2 B. (n-1)/2 C. n/2 D. n/2

9．在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点的编号为（ ）。

A．2i B．2i-1 C．2i+1 D．2i+2

10．在一棵完全二叉树中，若编号为i的结点存在右孩子，则右孩子结点的编号为（ ）。

A．2i B．2i-1 C．2i+1 D．2i+2

11．在一棵完全二叉树中，对于编号为i（i>1）的结点，其双亲结点的编号为（ ）。

A． (i+1)/2 B． (i-1)/2 C． i/2 D． i/2 12．一棵有16个结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（ ）。

A． 2，14 B． 2，15 C．3，14 D．3，15

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

A．24 B．48 C．72 D．53

14．利用n个值作为叶结点的权生成的哈夫曼树中共包含有（ ）个结点。

A．n B．n+1 C．2n D．2n-1

15．利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为（ ）。

A．18 B．16 C．12 D．30

9

二．填空题

1．在树形结构中，根结点没有_____________结点，其余每个结点有且只有1个前驱结点；叶子结点没有_____________结点，其余每个结点的后继结点可以_____________个。

2．若m叉树中A有3个兄弟，结点B是A的双亲，则结点B的度是_____________。 3．对于一棵具有n个结点的树，该树中所有结点的度数之和为_____________。 4．3个结点可以组成__________种不同形态的二叉树。

5．在一棵二叉树中，第5层上的结点数最多为_____________个。 6．深度为5的二叉树至多有_____________个结点。

7．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为_____________个。

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

9．对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为_____________个，其中_____________个用于指向孩子结点，_____________个指针空闲着。

10．已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，则后序遍历序列为_____________个。

11．在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对_____________个字符编码。

12．已知一棵哈夫曼树含有40个叶子结点，则该树中共有_____________个非叶子结点。

三．应用题

1．假定一棵二叉树的广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。

先序： 中序： 后序： 按层：

2．假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),d)，分别写出先根、后根、按层遍历的结果。

先根： 后根： 按层：

3．在一份电文中共使用六种字符，即a、b、c、d、e、f，它们的出现频率依次34、5、12、23、8、18，试画出对应编码哈夫曼树（要求树中左孩子结点的权值小于右孩子结点的权值），求出每个字符的哈夫曼编码，并求出传送电文的总长度。

4．将下图所示的二叉树转换成森林。

10

5．画出下图所示森林转换后所对应的二叉树（二叉树画在右边）。

第六章 图

一．单选题

1．设无向图的顶点个数为n，则该图最多有（ ）条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．n(n-1)

2．在一个具有n个顶点的无向图中，每个顶点度的最大值是（ ）。 A．n B．n-1 C．n+1 D．2(n-1)

3．在含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为（ ）。 A． e B． 2e C．n2- e D．n2-2e 4．n个顶点的连通图至少有（ ）条边。 A．n-1 B．n C．n+1 D．0

5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是（ ）。 A．上三角矩阵 B．稀疏矩阵 C．对角矩阵 D．对称矩阵 6．有向图的一个顶点的度为该顶点的（ ）。

A．入度 B．出度 C．入度与出度之和 D．（入度+出度）/2

7．有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．4 C．2 D．1

8．对于具有e条边的无向图，它的邻接表中有（ ）个弧结点。

11

A． e-1 B． e C．2(e-1) D．2 e

9．一个连通图的生成树是包含图中所有顶点的一个（ ）子图。 A．极小 B．连通 C．极小连通 D．无环

10．设有向图有n个顶点和e条边，采用邻接表作为其存储结构，在进行拓扑排序时，其时间复杂度为（ ）。

A．O(nlog2e) B．O(n+e) C．O(ne) D．O(n2)

11．已知一个图如下所示，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为（ ）。

a c b e

f d

A．a─b─c─e─d─f B．a─b─c─e─f─d C．a─e─b─c─f─d D．a─c─f─d─e─b

12．设图的邻接矩阵为 0 1 1 则该图为（ ）。 0 0 1 0 1 0

A．有向图 B．无向图 C．强连通图 D．完全图 13．下列有关图遍历的说法中不正确的是（ ）。 A．连通图的深度优先搜索是一个递归过程

B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 14．右图所示带权无向图的最小生成树的权为（ ）。

A．14 B．15 C．17 D． 18

二．填空题

1．在一个无向图中，所有顶点度数之和等于所有边数的_____________倍。 2．在一个具有n个顶点的无向完全图中，包含有_____________条边；在一个具有n个顶点的有向完全图中，包含有_____________条边。 3．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含弧结点分别为_____________和_____________个。

4．在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有_____________和 _____________结点。

5．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分

12

别为_____________和_____________。 6．在无向图的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于_____________。 7．n（n>0）个顶点的连通无向图的生成树有_____________条边。 8．能够成功完成拓扑排序的图一定是一个_____________。

三．应用题

1．对于图a、b，完成下列各题：

4 0 3 1 0 3 1 4 7 2 9 2 1 2 3 5 4 ⑴求图a中每个顶点的度，图b中每个顶点的入度； ⑵画出图a、b的邻接矩阵； ⑶画出图a、b的邻接表；

⑷画出图b的逆邻接表和十字链表。

2．已知图G的邻接表如下图所示，请按如下邻接表及遍历算法写出深度优先和广度优先遍历的顶点序列。 V0 2 1 3 ^ V1 0 V2 0 1 ^ V3 3

3．分别用普里姆和克鲁斯卡尔算法构造下图所示网络的最小生成树。 V2 4 7 8 V5 V1 6 V3 4 6 2 9 V4

4．写出下图所示的所有拓扑序列。 1

2 3

5 6 4

5．已知带权图G如下图所示，画出图G的一棵最小生成树。

13

6．对于下图，试给出： ⑴ 邻接矩阵 ⑵ 邻接表

7．已知无向图G的邻接表如下图所示，请写出从顶点V2开始的深度优先搜索序列。 0 V1 2 1 ^ 1 V2 4 3 2 0 ^ 2 V3 1 0 3 4 ^ 3 V4 1 2 4 ^ 4 V5 1 2 3 ^

第七章 查找

一．单选题

1．在一个长度为n的顺序表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为（ ）。

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

2．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为（ ）。

A．5.5 B．5 C．39/8 D．19/4

14

3．对长度为n的单链有序表，若查找每个元素的概率相等，则查找任一元素的平均查找长度为（ ）。

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

4．采用二分查找法，若当前取得的中间位置mid的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应（ ）。

A．从mid/2位置开始 B．从mid位置开始 C．从mid-1位置开始 D．从mid +1位置开始

5．对于长度为n的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长度为（ ）的值的向下取整加1。

A．log2(n+1) B．log2n C．n/2 D．(n+1)/2

6．对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（ ）。

A．20/9 B．18/9 C．25/9 D．22/9

7．对于顺序存储的有序表（5、12、20、26、37、42、46、50、64），若采用二分查找，则查找元素26的查找长度为（ ）。

A．2 B．3 C．4 D．5

8．对具有n的顺序存储的有序表，若采用二分查找，则算法的时间复杂度为（ ）。

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

9．在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为（ ）。

A．n+k B．k+n/k C．(k+n/k)/2 D．(k+n/k)/2+1

10．在一棵深度为h且具有n个元素的二叉排序树中，搜索一个元素的最大搜索长度（即经比较的结点数）为（ ）。

A． n B．log2n C．h/2 D．h

11．在由{25，30，16，48}按照依次插入结点的方法生成的一棵二叉排序树中，在等概率情况下成功搜索一个元素的平均搜索长度为（ ）。

A． 2 B．2.5 C．3 D．4

12．在下列各棵二叉树中，二叉排序树是（ ）。

13．若根据数据集合{23，44，36，48，52，73，64，58}建立散列表，采用h(K)=K%7计算散列地址，则同义词元素的个数最多为（ ）个。

A．1 B．2 C．3 D．4

15

14．对于哈希函数H（key）=key，被称为同义词的关键字是（ ）。 A．35和41 B．23和39 C．15和44 D．25和51

15．若根据数据长度为m的闭散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为d，则下一次的散列地址为（ ）。

A．d B．d+1 C．(d+1)/m D．(d+1)%m

二．填空题

1．长度为n的顺序表，采用设置岗哨方法顺序查找，若查找不成功，其查找长度为_____________。

2．以顺序查找方法从长度为n的顺序表中查找一个元素时，平均查找长度为_____________，时间复杂度为_____________。

3．以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为_____________。

4．在索引表中，每个索引项至少包含有_____________域和_____________域这两项。

5．假定对长度n=100的数据表进行索引查找，并假定每个子表的长度均为n，则进行索引查找的平均查找长度为_____________。

6．在线性表的散列存储中，装填因子α又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于_____________。

7．在线性表的散列存储中，处理冲突有_____________和_____________两种方法。

三．应用题

1．已知一组元素为（46，25，78，62，12，37，70，29）,试画出按元素排列顺序输入生成的一棵二叉排序树的过程。

2．对长度为12的有序表进行二分查找，试画出它的一棵判定树。

3．已知一棵二叉排序树的广义表表示为(28(12(,16),49(34(30),72(63))))，若从中依次删除72、12、49、28结点，试分别画出每删除一个结点后得到的二叉排序树。

第八章 排序

一．单选题

1．若对n个元素进行直接插入排序，在进行第i趟（1≤i≤n-1）排序时，为寻找插入位置最多需要进行（ ）次元素的比较。

A．i+1 B．i-1 C．i D．1

2．在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）层划分。

A．n B．n/2 C．log2n D．2n

16

3．若对n个元素进行直接选择排序，则进行任一趟排序的过程中，寻找最小值元素的时间复杂度为（ ）。

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

4．若对n个元素进行归并排序，则进行归并的趟数为（ ）。 A．n B．n-1 C．n/2 D． log2n 5．若一个元素序列基本有序，则选用（ ）方法较快。

A．直接插入排序 B．直接选择排序 C．堆排序 D．快速排序

6．若要对1000个元素排序，要求既快速又稳定，则最好采用（ ）方法。 A．直接插入排序 B．归并排序 C．堆排序 D．快速排序

二．填空题

1．每次从无序表中取出一个元素，把它插入到有序表中适当位置，此种排序方法叫做_____________排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做_____________排序。 2．假定一组纪录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为_____________。

3．快速排序在平均情况下的时间复杂度为_____________，在最坏情况下的时间复杂度为_____________。

4．快速排序在平均情况下的空间复杂度为_____________，在最坏情况下的空间复杂度为_____________。

5．对一棵二叉排序树进行中序遍历时，得到的结点序列是一个_____________。

6．从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_____________；若元素的值小于根结点的值，则继续向_____________查找；若元素的值大于根结点的值，则继续向_____________查找。

三．应用题

1．写出用快速排序方法对序列{22，21，23，5，9，40，41}进行一趟排序后的序列情况。

2．画出序列{22，21，23，5，9，40，41}用堆排序方法排序时建立的初始堆。

17

第二部分 实验指导

18

实验一

一． 实验目的：用C语言描述算法，初步掌握算法的分析方法。 二． 实验内容

1．

范例：假定一维整型数组中的每个元素值均在［0，200］区间内，分别统计落在[0，20]、[20，50]、[50，80]、[80，130]、[130，200]等各区间内的元素个数，试设计算法（用C语言函数描述），并分析算法的时间复杂度。

#include /*此头文件中含有输入、输出函数定义*/ int count(int a[],int n,int c[]) /*用数组c保存统计结果*/ { int d[]={20,50,80,130,201}; /*用于保存各区间的上限*/ int i,j;

for(i=0;i<5;i++) c[i]=0; /*数组c中各元素赋初值0*/ for(i=0;i

{ if(a[i]<0 ||a[i]>200) return 0; /*数组中数据有错，统计失败*/ for(j=0;j<5;j++)

if(a[i]

c[j]++; /*相应区间的统计值增1*/ }

return 1; /*统计成功*/ }

/*时间复杂度为O(n)*/ void main()

{ int b[]={23,10,56,125,38,44,130,98}; int d[5]; int i;

if( count(b,8,d))

for(i=0;i<5;i++) printf(\ printf(\ getch(); }

2． 用C语言函数描述下列每一个算法，并分别求出它们的时间复杂度。

1） 将一个字符串中的所有字符按相反的次序重新放置。 #include void main() {

19

char a[10];int i,j,t; gets(a); j=strlen(a);

for(i=0;i<=j/2;i++)

{t=a[i];a[i]=a[j-i-1];a[j-i-1]=t;} for(i=0;i<=j;i++) printf(\

getch(); }

2) 求一维double型数组a[n]中的所有元素之乘积。

#include void main() {

int a[10], i,sum=1; for(i=0;i<10;i++) {scanf(\}

for(i=0;i<10;i++) sum*=a[i];

printf(\ getch(); }

1）

xi计算?

i?1i?0n#include \

#include \#define x 3 void main() {

int n,i,j;float sum=0,a=1.0,t; scanf(\ for(i=0;i<=n;i++) { a=1.0;

for(j=1;j<=i;j++) a*=x;

t=a/(i+1);sum+=t;

20

rear=new; /*新结点成为新的尾结点*/ }

q=rear; }

void main() { int i;

int a[]={10,30,25,16,48,72}; struct sNode *p;

for(i=0;i<6;i++) EnQueue(q,a[i]); p=q->next; while(p!=q)

{ printf(\ p=p->next; }

printf(\ getch(); }

2． 试分别设计递归算法和非递归算法，计算1至n之间的所有整数的平方

和。

3． 假定循环链队列中只设置队尾指针，不设置队首指针，试写出循环链队

列上进行删除操作的算法。

实验四

一． 实验目的：掌握稀疏矩阵的存储结构，及其相应的运算实现。 二． 实验内容

1．范例：实现稀疏矩阵的顺序存储。 #include #include #define MaxTerms 20 typedef int ElemType; struct Triple { int row,col; ElemType val; };

struct SMatrix { int m,n,t;

struct Triple data[MaxTerms+1]; };

void InputMatrix(struct SMatrix *M)

26

{ int i,j,h,k=0; int row,col; ElemType val;

printf(\请输入稀疏矩阵的行数、列数：\\n\ scanf(\

printf(\输入三元组,行号为0输入结束：\\n\ scanf(\ while(row!=0) { k++;

i=1; /*确定新元素的插入位置*/ while(iM->data[i].row) i++; j=i;

while(row==M->data[j].row && col>M->data[j].col) j++;

for(h=k;h>j;h--) /*新元素后的元素后移*/ M->data[h]=M->data[h-1];

M->data[j].row=row; /*存储新元素*/ M->data[j].col=col; M->data[j].val=val;

printf(\再输入一个三元组,行号为0输入结束：\\n\ scanf(\ }

M->t=k; }

void main()

{ struct SMatrix MX; int i;

InputMatrix(&MX);

printf(\按行为主序输出稀疏矩阵各非零元素\\n\ for(i=1;i<=MX.t;i++)

printf(\

MX.data[i].row,MX.data[i].col,MX.data[i].val);

getch(); }

实验五

一．实验目的：掌握树的非线性特点、递归性特点和动态数据结构特点；掌握二叉树的存储结构、各种遍历算法，以及基于遍历算法的其

27

它操作的实现。 二．实验内容

1．范例：写一个算法，按先序序列建立二叉树的二叉链表，并按先序遍历二叉树。

#include #include

typedef char ElemType; /*定义元素类型为字符型*/ struct BTreeNode /*定义二叉树结点类型*/ { ElemType data;

struct BTreeNode *left,*right; };

struct BTreeNode *CreateBiTree() /*按先序序列建立二叉树的二叉链表*/ { static int i; /*i初值为零*/ struct BTreeNode *BT=NULL; ElemType ch;

if(i++==0) printf(\ /*i的值为零时屏幕提示输入*/ scanf(\

if(ch=='\\n'||ch==' ') return BT; /*ch为' '时返回空指针*/ BT=(struct BTreeNode *)malloc(sizeof(struct BTreeNode)); BT->data=ch;

BT->left=CreateBiTree(); BT->right=CreateBiTree(); return BT; }

/*注：依次输入字符：'A'、'B'、'C'、' '、' '、*/ /*'D'、'E'、' '、'G'、' '、' '、'F'、' '、' '、' '*/

void PreOrder(struct BTreeNode *BT) /*按先序序列遍历二叉树*/ { if(BT)

{ printf(\ PreOrder(BT->left); PreOrder(BT->right); } }

void main()

{ struct BTreeNode *bt; bt=CreateBiTree(); PreOrder(bt); getch(); }

2．已知二叉树中结点类型为struct BTreeNode，试编写求二叉树中结点总数的算法，结点总数值由函数返回。假定参数BT初始指向二叉树的根结点。

3．已知二叉树中结点类型为struct BTreeNode，试编写交换二叉树BT中所有

28

结点的左、右孩子指针域值的算法。

实验六

一．实验目的：掌握图的常用存储结构，以及基于这些存储结构的一些操作的实现。 二．实验内容

1．范例：由键盘输入n个顶点信息和e条弧的信息，建立有向图的顶点数组G和邻接矩阵GA，并求出顶点numb的度。 #include #include #define MaxValue 1000

#define MaxVertexNum 12 /*定义图的最大顶点数*/ #define MaxEdgeNum 20 /*定义图的最大边数*/ typedef int ElemType; /*定义ElemType类型为整型*/ typedef int VertexType;

typedef VertexType vexlist[MaxVertexNum]; /*定义存储顶点信息的数组*/ typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; /*定义存储邻接矩阵数组*/

void Create(vexlist GV,adjmatrix GA,int n,int e) { int i,j,k,w;

printf(\请输入%d个顶点数据\\n\ for(i=0;i

scanf(\

for(i=0;i

if(i==j) GA[j][j]=0;

else GA[j][j]=MaxValue; printf(\请输入%d条弧\\n\ for(k=0;k

{ scanf(\ /*输入一条弧的弧尾、弧头编号及弧上的权值。对于有向图，不输入权值。*/

GA[j][j]=w; /*若为有向图，GA[j][j]=1; */ } }

int degree(adjmatrix GA,int numb,int n) { int i,j,d1=0,d2=0;

for(j=0;j

if(GA[numb][j]!=0&&GA[numb][j]!=MaxValue) d1++; for(i=0;i

if(GA[i][numb]!=0&&GA[i][numb]!=MaxValue) d2++; return d1+d2;

29

}

void main() { int n,e,b; vexlist gv; adjmatrix ga;

printf(\请输入有向图的顶点数和弧数\ scanf(\

Create(gv,ga,n,e); /*根据键盘输入建立有向图的顶点数组和邻接矩阵*/ printf(\请输入一个顶点序号：\ while(1)

{ scanf(\

if(b>=0&&b

printf(\重新输入一个顶点序号：\ }

printf(\顶点%d的度数：%d\ getch(); }

2． 求出一个用数组表示法表示的图中所有顶点的最大出度值。

实验七

一．实验目的：熟悉建立二叉排序树的常用方法及其应用。 二．实验内容

1．范例：由数组中的元素建立二叉排序树。 #include #include

struct BTreeNode /*定义二叉排序树结点类型*/ { int key;

struct BTreeNode *left,*right; };

/*在二叉排序树中插入一个不重复元素item */ void insert(struct BTreeNode **BST,int item) { struct BTreeNode *t,*f=NULL; t=*BST;

while(t!=NULL)

{ f=t; /*t的双亲下移*/ if(item==t->key) break;

30

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