数据结构习题

2021-02-17 来源：乌哈旅游

数据结构上机指导书及习题册

班级：_______________ 学号：_______________ 姓名：_______________

电子与信息工程学院计算机科学系

数据结构习题

第一部分习题

第一章绪论

一、选择题

1．数据的四种基本逻辑结构是指( )

A．数组、链表、树、图形结构 B．集合、线性结构、树、图形结构 C．线性结构、链表、树、图形结构 D．线性表、链表、栈队列、数组广义表 2．数据结构中，通常采用两种方法衡量算法的时间复杂性，即( ) A．最大时间复杂性和最小时间复杂性 B．最好时间复杂性和最坏时间复杂性 C．部分时间复杂性和总体时间复杂性 D．平均时间复杂性和最坏时间复杂性 3．数据结构是（）

A．一种数据类型 B．一组性质相同的数据元素的集合

C．数据的存储结构 D．相互之间存在一种或多种特定关系的数据元素的集合 4．算法分析的目的是（）

A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 5．数据结构中所定义的数据元素，是用于表示数据的（） A．最小单位 B．最大单位 C．基本单位 D．不可分割的单位

6．下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（） A．集合 B．线性结构 C．树形结构 D．图形结构

7．数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是（ ① ）的有限集合，R是D上的（ ② ）有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象

数据结构习题

② A．操作Ｂ．映象Ｃ．存储Ｄ．关系二、填空题

1．（）是数据的基本单位，（）是数据的最小单位。

2．（）是描述客观事物的数、字符以及所有能输入到计算机中且被计算机程序加工处理的符号的集合。

3．数据结构研究数据的（）和（）以及他们之间的相互关系。数据的逻辑结构包括（）、（）、（）、（）四种基本类型。

4．算法的五个重要特性是（）、（）、（）、（）、（）。 5．一个数据结构用二元组表示时,它包括( )集合K和K上的( )集合R。 6．一个好的算法应具备（）、（）、（）、（）。

7．一个算法的时间复杂度是该算法包含的（）的多少，它是一个算法运行时间的（）；一个算法的空间复杂度是指该算法在运行过程中临时占用的（）的大小。

8．一个算法的时间复杂度通常用它的（）形式表示，当一个算法的时间复杂度与问题的规模n大小无关时，则表示为（）；成正比时，则表示为（）；成对数关系时，则表示为（）。

9．称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和( )的数量级相同。三、计算下列程序段的时间复杂度。 1． for(i=1;j<=n;i++)

for(j=1;j<=n;j++) for(k=1;k<=n;k++) x++; 2． for(i=0;i2

数据结构习题

3． i=1; while(i<=n) i=i*3; 四、算法设计题

1. 试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值．

2. 试写一算法,求出n个数据中的最大值。出最大语句频度，该算法的时间复杂度。

数据结构习题

第二章线性表

一、选择题

1．一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A． 110 B． 108 C． 100 D． 120 2．线性链表不具有的特点是（）。

A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 3．下列关于线性表的叙述中，不正确的是( ) A．线性表是n个结点的有穷序列 B．线性表可以为空表

C．线性表的每一个结点有且仅有一个前趋和一个后继 D．线性表结点间的逻辑关系是1:1的联系

4．在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( )

A．p=p->next B．p->next=p->next C．p->next=p->next->next D．p->next=p

5．假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L执行GetElem(L,i,&e)的操作结果为（）

A．23 B．56 C．89 D．76

6．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( )。 A．O(n) B．O(n／2) C．O(1) D．O(n2)

7．对线性表，在下列哪种情况下应采用链式存储结构？（） A．经常需要随机存取元素 B．经常需要进行插入和删除操作 C．表中元素的个数不变 D．表中元素需要占据一片连续的存储空间

数据结构习题

8．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行( )。

A．q->next＝p->next；p->next＝q B．p->next＝q->next；q＝p； C．q->next＝p->next；p->next＝q； D．p->next＝q->next；q->next＝p；

9．线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续或不连续都可以二、填空题

1．在含n个元素的顺序表中的第I个元素之前插入一个元素，需移动（）个元素；而删除第I个元素，则需将从第（）个元素至第（）个元素依次（）移一个位置。 2．线性链表的结点一般包括两个域，即用来存储（）的（）域；及用来存储（）的（）域。

3．双向链表中，每个结点含有两个指针域，一个指向（），另一个指向（）。 4．循环链表中，最后一个结点的指针域指向（）。

5．带头结点的单链表head为空的判定条件为（），而不带头结点的单链表head为空的判定条件（）。

6．在一个单链表中，若删除p所指结点的后续结点，则执行操作（）。 7．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则执行操作（）

8．在一个具有n个结点的有序单链表中插入一个新结点，使得仍然有序，其算法的时间复杂度为（）。

9．在双向循环链表中，在p所指结点之后插入s指针所指结点，其操作为（）。

数据结构习题

10．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用（）存储结构为宜；相反，当经常进行的是插入和删除操作时，则采用（）存储结构为宜。

11．在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=( )和p->next=( )的操作。

三、算法设计题

1．设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

2．试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2,…． an）逆置为(an, an-1,…．, a1)。

3．试写一算法，实现单链表的就地逆置(要求在原链表上进行)。

数据结构习题

4．已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。

5．（2009年考研题）已知一个带有表头结点的单链表，结点结构为data|next，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：

（1）描述算法的基本设计思想（2）描述算法的详细实现步骤

（3）根据设计思想和实现步骤，采用程序设计语言描述算法，关键之处请给出简要注释。

数据结构习题

第三章栈和队列

一、选择题

1、向顺序栈中压入新元素时，应当（）。

A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行 2．栈和队列( )

A．共同之处在于二者都是先进先出的特殊的线性表 B．共同之处在于二者都是先进后出的特殊的线性表 C．共同之处在于二者都只允许在顶端执行删除操作 D．没有共同之处

3．有关栈的描述，正确的是（）。

A．栈是一种先进先出的特殊的线性表 B．只能从栈顶执行插入、删除操作 C．只能从栈顶执行插入、栈底执行删除 D．栈顶和栈底均可执行插入、删除操作

4．栈是限定在处进行插入或删除操作的线性表 ( )。

A．端点 B．栈底 C．栈顶 D．中间

5．4个元素按A、B、C、D、顺序连续进S栈，进行Pop（S，x）元素后，x的值是 ( A． A B． B C． C D． D 6．同一个栈内各元素的类型 ( ）。

A ．必须一致 B．可以不一致C．不能一致 D．不必不一致 7．顺序栈存储空间的实现使用 ( ）。

A．链表 B．数组 C．循环链表 D．变量 8．一个顺序栈一旦说明，其占用空间的大小 ( ）。

A．已固定 B．可以改变 C．不能固定 D．动态变化

) 。

数据结构习题

9．栈与一般线性表区别主要在方面 ( ) 。

A．元素个数 B．元素类型 C．逻辑结构 D．插入、删除元素的位置 10．经过下列栈的运算后GetTop(s)的值是 ( ）。

InitStack（s）；Push（s，a）；Push（s，b）；Pop（s）； A． a B． b C． 1 D． 2 11．循环队列Sq是空队列的条件是 ( ）。

A． Sq->real==Sq->front B．（Sq->real+1）％maxsize==Sq->front C． Sq->real==0 D． Sq->front==0 12．循环队列Sq是满队列的条件是 ( ) 。

A． Sq->real==Sq->front B．（Sq->real+1）％maxsize==Sq->front C． Sq->real==0 D． Sq->front==0

13．当循环队列Sq是满队列时，存放队列元素的数组data有n个元素，则data中存放个队列元素 ( ）。

A． n B． n-1 C． n-2 D． 0 14．链栈ls是空栈的条件是 ( ）。

A． ls==null( ) B． ls->next==null C． Ls==0( ) D． ls->next==ls 15．一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）。 A． edcba B． decba C． dceab D． abcde

16．一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是（）。 A． 4，3，2，1 B． 1，2，3，4 C． 1，4，3，2 D． 3，2，4，1

17． (2009年)设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是( )

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

数据结构习题

18． (2010年)若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是( ) A:dcebfa B:cbdaef C:dbcaef D:afedcb

19． (2010年)某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（）

A．bacde B．dbace C．dbcae D．ecbad

20． (2009年)为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）

A．栈 B．队列 C．树 D．图二、填空题

1．线性表、栈和队列都是（）结构，线性表可以在（）位置插入和删除元素；对于栈只能在（）插入和删除元素；对于队列只能在（）插入和在（）删除元素。

2．栈的插入和删除只能在栈的顶端进行，进行插入的端叫做（）；所以又把栈叫做（）表；队列的插入和删除分别在两端进行，进行插入的一端叫做（），进行删除的一端叫做（）；所以又把队列称做（）表。

3．假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为( )。

4．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，则当做出栈处理是top的变化为（）。

5．在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（）。

6．在一个队列中，假定front和rear分别为对头和队尾指针，则插入*s结点的操作为（）。

数据结构习题

7．向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行（）。 8．从一个栈顶指针为hs的链栈中删除插入一个*s结点时，用X保存被删除结点的值，则应执行（）。

9．在具有n个单元的顺序存储结构的循环队列中，假定front和rear分别为队头指针和队尾指针，则判定队满的条件为（）。 10．在一个链式栈中，若栈顶指针等于NULL则为 ( )。三、简答题

1. 对于一个栈，给出输入序列A,B,C,如果输出序列由A,B,C所组成，试给出全部可能的

输出序列。

2．假设Q[1，10]是一个线性队列，初始状态为front=rear=1,画出做完下列操作后队列的头尾指针的变化情况，若不能入队，请指出其元素，并说明理由。 d,e,b,g,h入队 d,e出队

i,j,k,l,m入队 b出队 n,o,p,q,r入队

3．假设CQ[0，10]是一个循环队列，初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的变化情况，若不能入队，请指出其元素，并说明理由。 d,e,b,g,h入队 d,e出队 i,j,k,l,m入队 b出队 n,o,p,q,r入队

数据结构习题

四、算法设计题

1．按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3．2节例3—1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：

A-B*C/D+E/F

2．设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

3．以下运算实现在链栈上的进栈，请填充适当语句完成功能。 void Push（LStackTp *ls,DataType x）

{ LstackTp *p;p=malloc(sizeof(LstackTp)); ________________; p->next=ls; ________________; }

数据结构习题

4．以下运算实现在链栈上的退栈，请填充适当语句完成功能。 int Pop(LstackTp *ls,DataType *x) {LstackTp *p; if(ls!=NULL) { p=ls;

*x=________________; ls=ls->next; ________________; return(1)；}

else return(0); }

数据结构习题

第四章串、数组和广义表

一、选择题

1．二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（）

A ．700 B．1120 C．1180 D．1140

2．二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( )

A．127 B．142 C．150 D．157

3．设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]中（）位置。

A．32 B．33 C．41 D．65 4．广义表的深度是（）

A．广义表中子表个数 B．广义表括号个数 C．广义表展开后所含的括号层数 D．广义表中元素个数

5．设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（）

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

6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（）

A．1207 B．1209 C．1211 D．1213 7．以下叙述中正确的是( ) 。

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

8．设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是____。

A． BCDEF B． BCDEFG C． BCPQRST D． BCDEFEF

数据结构习题

9．串是一中特殊的线性表，其特殊性体现在（）。 A．可以顺序存储 B．数据元素是一个字符 C．可以链接存储 D．数据元素可以是多个字符二、填空题

1．字符串S1=’ABCDE’,S2=’PQRS’,则运算S=CONCAT(SUB(S1,2,LEN(S2)), SUB(S1,LEN(S2),2))后的串值为（）。 2．SUB(‘DATA STRUCTURE’,5,9)=( )．

3．计算机软件系统中，有两种处理字符串长度的方法，一种是采用（），另一种是（）。

4．串是指（）。 5．设s=’I am a teacher’,其长度是( )．

6．设有两个串p和q，求q在p中首次出现的位置的运算称作（）。

7．一维数组的逻辑结构是（），存储结构是（）；对于二维或多维数组，分为按（）和（）两种不同的存储方式。

8．对于一个二维数组A[m][n]，若按行为主序存储，则任一元素A[i][j]相对与A[0][0]的地址为（）。

9．一个广义表（（a,b）,c,d），表头为（），表尾为（）。 10．一个广义表(a,(a,b),d,e,(i,j),k)的长度为（），深度为（）。

11．一个稀疏矩阵为 0 0 2 0 则相对应的三元组线性表为（）。 3 0 0 0 0 0 1 5

0 0 0 0 12．三维数组R[c1．．d1，c2．．d2，c3．．d3]共含有（）个元素。 13．串中所含字符个数称为该串的( )。 14．tail(tail(a,b))=( )。

数据结构习题

15．设s=″I AM A ATHLETE″,t=″GOOD″，则执行下列串操作序列之后得到的sub1为( )。

substr (sub1,s,5,2)；substr(sub2,s,6,8); strcpy(t1,t); strcat(t1,sub2); strcat(sub1,t1);

16．求下列广义表操作的结果：

(1) GetTail[GetHead[((a,b),(c,d))]]=( ) (2) GetTail[GetHead[GetTail[((a,b),(c,d))]]]=( ) 三、简答题

1．设三角矩阵R= 31 0 0 0 采用压缩存储，已知R00的地址为1，每个元素

43 0 0 0 14 69 91 0 58 36 75 0 占2个字节，求R32的存储地址。 2．请画出广义表D的图形表示 D=(D,(a,b),((a,b),c),())

3．设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何? 4．求下列广义表运算的结果： (1)head ((p,h,w))

(2)tail((b,k,p,h)) (3) head (((a,b),(c,d))) (4)tail(((a,b),(c,d)))

(5)head(tail(((a,b),(c,d))))

数据结构习题

(6)tailhead)(((a,b),(c,d)))) 四、算法设计题

1．编写算法，从串s 中删除所有和串 t相同的子串。

2．编写算法，实现串的基本操作Replace(&S,T,V)。

3．写一个递归算法来实现字符串逆序存储，要求不另设存储空间。

4．假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

数据结构习题

5．假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵相加的算法：假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上，不增加A，B之外的附加空间，你的算法能否达到O（m+n）的时间复杂度？其中m和n分别为A，B矩阵中非零元的数目。

6．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。

7．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f(\"abba\")返回1，f(\"abab\")返回0；

int f( ______) {int i=0,j=0;

while (s[j]) __ _____; for(j--; i18

数据结构习题

第五章树

一、选择题

1．关于二叉树性质的描述，正确的是（）

A．二叉树结点的个数可以为0 B．二叉树至少含有一个根结点

C．二叉树若存在两个结点，则必有一个为根，另一个为左孩子

D．二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子 2．具有10个叶结点的二叉树中有（）个度为2的结点。

A．8 B．9 C．10 D．ll 3．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）

A． 250 B． 500 C．254 D．505 E．以上答案都不对 4．有关二叉树下列说法正确的是（）

A．二叉树中至少有一个结点的度为2 B．一棵二叉树的度可以小于2 C．二叉树的度为2 D．二叉树中任何一个结点的度都为2 5．二叉树的第I层上最多含有结点数为（）

A．2I B． 2I-1-1 C． 2I-1 D．2I -1 6．对于有n 个结点的二叉树, 其高度为（）

A．nlog2n B．log2n C．︱log2n」+1 D．不确定 7．一棵树高为K的完全二叉树至少有（）个结点

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

8．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。

A．先序 B．中序 C．后序 D．从根开始按层次遍历

数据结构习题

9．在下列存储形式中，哪一个不是树的存储形式？（）

A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 10．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。

A．CBEFDA B． FEDCBA C． CBEDFA D．不定 11．某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：

A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对

12．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：

A、 E B、 F C、 G D、 H 13．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点

D．左子结点，右子结点和兄弟结点 14．引入二叉线索树的目的是（）

A．加快查找结点的前驱或后继的速度 B．使二叉树的遍历结果唯一 C．为了能方便的找到双亲 D．为了能在二叉树中方便的进行插入与删除 15．对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )

A．ABCDEF B．ABECDF C．CDFBEA D．CBDAEF

数据结构习题

16．下面关于生成树的描述中，不正确的是( )

A．生成树是树的一种表现形式 B．生成树一定是连通的

C．生成树一定不含有环 D．若生成树顶点个数为n，则其边数一定为n-1 17．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）

A．9 B．11 C．15 D．不确定 18．具有4个结点的二叉树可有（）

A．4种形态 B．7种形态 C．10种形态 D．11种形态

19．(2010年)下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）

20．(2009年)已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是( )

A．39 B． 52 C． 111 D． 119

21．(2009年)将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是( )

数据结构习题

I．父子关系 II.兄弟关系

III. u的父结点与v的父结点是兄弟关系

A．只有II B． I和II C． I和III D． I、II和III 22． (2012年)若一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为b,c,d,e,a,则根结点的孩子结点 A．只有e

B．有e、b C．有e、c

D．无法确定

23． (2012年)若平衡二叉树的高度为6,且所有非叶结点的平衡因子均为1,则该平衡二叉树的结点总数为 A． 12 B． 20 二、填空题

1．假定一棵树的广义表表示为A(B(E),C(F(H,I,J),G),D),则该树的度为（），树的深度为（），终端结点的个数为（），C的双亲结点为（），其孩子结点为（）。２．对于一个具有n个结点的二叉树，当它为一棵（）二叉树时具有最小高度，即为（），当它为一棵单支树时具有（）高度，即为（）。

３．对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为（）个，其中（）个用于链接孩子结点，（）个空闲着。

４．在一棵二叉树中，度为０的结点数为n0，度为２的结点数为n2,则n0＝（）。５．一棵深度为k的满二叉树的结点总数为（），一棵深度为k的完全二叉树的结点总数的最小值为（），最大值为（）。

６．由a,b,c三个结点构成的二叉树，共有（）种不同的结构（不考虑a,b,c顺序）。７．假定一棵二叉数中，双分支结点数为12，单分支结点数为24个，则叶子结点数为（）。

８．在一棵二叉树中第4层的结点数最多为（）。

９．用顺序存储的方法将完全二叉树的所有结点逐层存放在数组R[1．．n]中，结点R[I]若有左孩子，则左孩子是结点（）。

C． 32 D． 33

数据结构习题

10．具有1000个结点的二叉树，其高度至少为（） 11．深度为5的二叉树至多有（）个结点。

12．由带权为2，9，5，7的四个叶子结点构造一棵赫夫曼树，该树的带权路径长度为（）。

13．具有n个结点的完全二叉树，其深度为___________。三、简答题

1．已知一颗树的边的集合表示为：

{（L,N）,(G,K)(G,L),(G,M),(B,E),(B,F),(D,G),(D,H),(D,I),(D,J),(A,B),(A,C), (A,D)}

请画出这棵树，并回答下列问题

（1）树的根结点是哪个？哪些是叶子结点？哪些是非终端结点？

（2）树的度是多少？各个结点的度是多少？

（3）树的深度是多少？各个结点的层数是多少？

（4）对于结点G，它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟结点和

堂兄弟结点都是哪些？

2．有7个带权结点，其权值分别为4，7，8，2，5，16，30，试以它们为叶子结点构造

一棵赫夫曼树，并计算其WPL。

数据结构习题

3．假定用于通信的电文有8个字母A,B,C,D,E,F,G,H组成，各字母在电文中出现的概率

为5%，25%，4%，7%，9%，12%，30%，8%，试为这8个字母设计赫夫曼编码。

4．一棵二叉树如图：

（1）写出对此树进行先序、中序、后序遍历时得到的结点序列。（2）画出该树的后序线索二叉树。

5．一棵二叉树的顺序存储结构如下，写出它的二叉链表存储结构。 1 2 3 4 5 6 7 8 9 10 e a f d g c 11 j 12 13 14 i 15 h 16 17 18 19 20 21 b 6．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。（1）画出该二叉树；

（2）画出与（1）求得的二叉树对应的森林。

数据结构习题

四、算法设计题

1．编写按层次顺序（同一层自左至右）遍历二叉树的算法。

2．试编写算法，对一棵二叉树,统计叶子的个数。

3．试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。

4．试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。

数据结构习题

第六章图

一、选择题

1．设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 2．一个n个顶点的连通无向图，其边的个数至少为（）。

A．n-1 B．n C．n+1 D．nlogn； 3．n个结点的完全有向图含有边的数目（）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）

4．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。

A．0 B．1 C．n-1 D．n 5．在一个无向图中，所有顶点的度数之和等于所有边数（）倍。

A．1/2 B．2 C．1 D．4 6．下列哪一种图的邻接矩阵是对称矩阵（）

A．有向图 B．无向图 C．AOV网 D．AOE网 7．下列说法不正确的是（）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程

8．G=(V,E),其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。

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

9．图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是( )

数据结构习题

A．V1V2V3V4V5 B．V1V2V3V5V4

C．V1V4V3V5V2

D．V1V3V4V5V2

10．图的邻接矩阵表示法适用于表示（）

A．无向图 B．有向图 C．稠密图 D．稀疏图 11．(2009年)下列关于无向连通图特性的叙述中，正确的是( ) I．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1

A．只有I B．只有II C．I和II D．I和III

12．(2010年)若无向图G=(V.E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是( )

A．6 B．15 C．16 D．21

13．(2010年)对下图进行拓补排序，可以得到不同的拓扑序列的个数是（） A．4 B．3 C．2 D．1 14．(2012年)下列关于最小生成树的叙述中,正确的是 I．最小生成树的代价唯一

Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 IV．使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同

A．仅I B．仅Ⅱ C．仅I、Ⅲ D．仅Ⅱ、Ⅳ

数据结构习题

二、填空题

1．设无向图G的顶点数为n，图G最少有（）条边；最多有（）条边。若G为有向图，有n个顶点，则图G最少有（）条弧，最多有（）条弧。具有n个顶点的无向完全图，边的总数为（）条；而具有n个顶点的有向完全图中，弧的总数为（）。

2．在一个图G的邻接表表示，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（）；而对于无向图而言等于该顶点的（）。

3．在一个图中，所有顶点的度数之和等于所有边数的（）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。

4．一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 5．关键路径是事件结点网络中，从源点到汇点的（）路径。

6．对于一个具有n个顶点的图，采用邻接矩阵表示该矩阵的大小为（）。 7．N个顶点的强连通图至少有（）条边。三、简答题 1．对于下图

（1）请画出其最小生成树并求出它的权；

（2）从顶点v1出发，按照普里姆算法生成最小生成树中各边的次序写出各条边。（3）按照克鲁斯卡尔算法生成最小生成树中各边的次序写出各条边。

数据结构习题

2．如下图所示的带权有向图G，试回答以下问题：

（3）给出从结点v1出发按深度优先搜索遍历图所得的结点序列，并给出按广度

优先搜索遍历图所得的结点序列。

（4）给出G的一个拓扑排序序列。

（5）给出从结点v1到结点v8的最短路径和关键路径。

3．对于下图，请给出

（6）对应的邻接矩阵，并给出1，2，3三个顶点的入度和出度。（7）邻接表表示和逆邻接表表示。（8）强连通分量。

数据结构习题

4．对下面的有向图从顶点V1开始进行遍历，试画出遍历得到的DFS生成森林和BFS生成森林。

V1 V3 V4 V2 V5 V6 V7 V8

5．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L) 、东京(T) 、墨西哥(M),下表给定了这六大城市之间的交通里程:世界六大城市交通里程表(单位:百公里)

PE N PA L T M PE 109 82 81 21 124 N 109 58 55 108 32 PA 82 58 3 97 92 L 81 55 3 95 89 T 21 108 97 95 113 M 124 32 92 89 113 （1）画出这六大城市的交通网络图; （2）画出该图的邻接表表示法; （3）画出该图用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。

数据结构习题

四、算法设计题

1．假设有向图以邻接表方式存储，编写一个算法判别顶点vi到顶点vj是否存在弧。

数据结构习题

第七章查找

一、选择题

1．适合折半查找的表的存贮方式及元素排列要求为( ) A．链式存贮元素无序 B ．链式存贮元素有序 C．顺序存贮元素无序 D ．顺序存贮元素有序

2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。

A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 3．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为（）。

A．从第0个元素往后查找该数据元素 B．从第1个元素往后查找该数据元素 C．从第n个元素往开始前查找该数据元素 D．与查找顺序无关

4．解决散列法中出现的冲突问题常采用的方法是（）。

A．数字分析法、除余法、平方取中法 B．数字分析法、除余法、线性探测法 C．数字分析法、线性探测法、多重散列法 D．线性探测法、多重散列法、链地址法

5．采用线性探测法解决冲突问题，所产生的一系列后继散列地址（）

A．必须大于等于原散列地址 B．必须小于等于原散列地址

C．可以大于或小于但不能等于原散列地址 D．地址大小没有具体限制

数据结构习题

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

A． 1，2，3 B． 9，5，2，3 C． 9，5，3 D． 9，4，2，3

7．对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。 A．1 B．2 C．3 D．4

8．(2010年)已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多是（）

A．4 B．5 C．6 D．7 二、填空题

1．采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。 2．采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。 3．二分查找的存储结构仅限于（），且是（）。

4．在分块查找方法中，首先查找（），然后再查找相应的（）。

5．对于长度为n的线性表，若进行顺序查找，则时间复杂度为（）；若采用二分法查找，则时间复杂度为（）。

6．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（）次比较后查找成功。

7．设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7

其余地址为空如用二次探测再散列处理冲突，关键为49的结点的地址为（）。三、简答题

1．设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函

数：H(key)=key%13采用开放地址法的线性探测再散列方法解决冲突，试在0—18的散列地址空间中对该关键字序列构造哈希表。

数据结构习题

2．设有一组关键字{87，25，310，08，27，132，68，95，187，123，70，63，47}，采

用哈希函数：H(key)=key%13采用链地址法解决冲突，试对该关键字序列构造哈希表。

3．已知一组元素为（45，25，80，60，18，30，12，40，70），试画出按元素输入排列

顺序而生成的一棵二叉排序树。（1）画出该二叉排序树；

（2）画出从（1）所得树中删除关键字为40点之后的二叉排序树。

4．已知一个散列表如下图所示： 0 1 2 35 3 4 20 5 6 7 33 8 9 48 10 11 12 59 其散列函数为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）该散列表在等概率查找时查找成功的平均查找长度为多少？

数据结构习题

第八章排序

一、选择题

1．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。

A．希尔排序 B．起泡排序 C．插入排序 D．选择排序 2．设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。

A．起泡排序 B．快速排序 C．堆排序 D．基数排序 3．在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）

A．插入排序 B．选择排序 C．快速排序 D．归并排序 4．一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）

A． 79，46，56，38，40，80 B． 38，46, 56，79， 40，84， C． 84，79，56，46，40，38 D． 84，56，79，40，46，38 5．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。 A． 38，40，46，56，79，84 B． 40，38，46，79，56，84 C． 40，38，46，56，79，84 D． 40，38，46，84，56，79 6．一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）。

A． 16，25，35，48，23，40，79，82，36，72 B． 16，25，35，48，79，82，23，36，40，72 C． 16，25，48，35，79，82，23，36，40，72 D． 16，25，35，48，79，23，36，40，72，82

数据结构习题

7．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。

A．希尔排序 B．起泡排序 C．插入排序 D．选择排序 8．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。

A．希尔排序 B．归并排序 C．插入排序 D．选择排序 9．用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下： ⑴ 25，84，21，47，15，27，68，35，20 ⑵ 20，15，21，25，47，27，68，35，84 ⑶ 15，20，21，25，35，27，47，68，84 ⑷ 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（）。

A．选择排序 B．希尔排序 C．归并排序 D．快速排序 10．下述几种排序方法中，平均查找长度最小的是（）。

A．插入排序 B．选择排序 C．快速排序 D．归并排序 11．下述几种排序方法中，要求内存量最大的是（）。

A．插入排序 B．选择排序 C．快速排序 D．归并排序 12．快速排序方法在（）情况下最不利于发挥其长处。

A．要排序的数据量太大 B．要排序的数据中含有多个相同值 C．要排序的数据已基本有序 D．要排序的数据个数为奇数

13．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（）

数据结构习题

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

14．(2009年)已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是( ) A．3,5,12,8,28,20,15,22,19 B．3,5,12,19,20,15,22,8,28 C．3,8,12,5,20,15,22,28,19 D．3,12,5,8,28,20,15,22,19

15．(2009年)若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( ) A．起泡排序 B．插入排序 C．选择排序 D．二路归并排序 16．(2010年)采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）

A．递归次数与初始数据的排列次序无关

B．每次划分后，先处理较长的分区可以减少递归次数 C．每次划分后，先处理较短的分区可以减少递归次数 D．递归次数与每次划分后得到的分区处理顺序无关

17．(2010年)对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下（）

第一趟：2，12，16，5，10，88 第二趟：2，12，5，10，16，88 第三趟：2，5，10，12，16，88 则采用的排序方法可能是：

A．起泡排序 B．希尔排序 C．归并排序 D．基数排序二、填空题

数据结构习题

1．在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。 2．设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。

3．一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。

4．一组记录的排序码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

5．排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。

6．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序的序列中（初始为空）的一端的方法，称为（）。

7．在堆排序和快速排序中，若原始记录接近正序或反序，则选用（），若原始记录无序，则选用（）。

8．在插入和选择排序中，若原始数据基本正序，则选用（）；若原始数据基本反序，则选用（）。

9．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为（）。

三、简答题

1．已知序列{503，87，61，908，170，897，275，653，462}，采用快速排序法对该序

列作升序时的每一趟的结果。

数据结构习题

2．已知序列{503，87，61，908，170，897，275，653，462}，采用堆排序法对该序列

作升序时的每一趟的结果。

3．已知序列{503，87，61，908，170，897，275，653，462}，采用基数排序法对该序

列作升序时的每一趟的结果。

4．已知序列{10，18，4，3，6，12，1，9，18，8}，采用希尔排序法对该序列作升序时

的每一趟的结果。

5．已知序列{10，18，4，3，6，12，1，9，18，8}，采用归并排序法对该序列作升序时

的每一趟的结果。

数据结构习题

6．以关键码序列（503,087,512,061,908,170,897,275,653,426），为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：（1）直接插入排序；

（2）希尔排序（增量d[1]=5）；（3）快速排序；（4）堆排序；（5）归并排序；（6）基数排序。

数据结构实验

第二部分实验

一、实验目的与要求

1．通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及程序调试的能力；

2．上机前要做好准备工作，包括程序框图、数据结构以及算法； 3．按时实验；

4．服从实验室老师的安排；

5．独立实验，有问题可以讨论，但不得翻版； 6．遵守实验室的各项纪律；

7．要求所编的程序能正确运行，并提交实验报告。二、实验内容

1．单链表的插入和删除 :要求单链表的数据域是字符串,完成单链表的初始化、插入、删除操作，插入时不允许重复的串插入表中。

2．栈操作 :采用顺序存储结构,完成建栈、数据元素入栈与出栈、判断栈空、判断栈满等操作。

3．二叉树操作 :采用二叉链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作等。

4．图的遍历操作 :可采用邻接矩阵或邻接表作为存储结构,完成有向图和无向图的DFS和BFS操作。

5．数据查找 :实现顺序查找、折半查找及二叉排序树上的查找算法,比较它们的查找速度。实验时所输入的数据可按有序和随机产生去组织。

6．排序 :实现直接插入、冒泡、直接选择、快速、堆、归并等排序算法,比较各种排序算法的速度。

数据结构实验

实验1 线性表基本操作

实验目的

1．熟悉C语言的上机环境，掌握C语言的基本结构。 2．定义单链表的结点类型。

3．熟悉对单链表的一些基本操作和具体的函数定义。 4．通过单链表的定义掌握线性表的链式存储结构的特点。 5．熟悉对单链表的一些其它操作

实验内容

程序1 实现单链表的定义和操作

该程序包括单链表结构类型以及对单链表操作的具体的函数定义程序中的单链表（带头结点）结点为结构类型，结点值为整型。 /* 定义DataType为int类型 */ typedef int DataType;

/* 单链表的结点类型 */ typedef struct LNode

{DataType data; struct LNode *next;

}LNode,*LinkedList;

/* 初始化单链表 */ LinkedList LinkedListInit()

/* 清空单链表 */

void LinkedListClear(LinkedList L)

/* 检查单链表是否为空 */ int LinkedListEmpty(LinkedList L)

数据结构实验

/* 遍历单链表 */

void LinkedListTraverse(LinkedList L)

/* 求单链表的长度 */

int LinkedListLength(LinkedList L)

/* 从单链表表中查找元素 */

LinkedList LinkedListGet(LinkedList L,int i)

/* 从单链表表中查找与给定元素值相同的元素在链表中的位置 */ int LinkedListLocate(LinkedList L, DataType x)

/* 向单链表中插入元素 */

void LinkedListInsert(LinkedList L,int i,DataType x)

/* 从单链表中删除元素 */

void LinkedListDel(LinkedList L,DataType x)

/* 用尾插法建立单链表 */ LinkedList LinkedListCreat( )

程序2 约瑟夫环问题

任给正整数N和K，按下述方法可以得到1,2, …,n的一个置换，将数字1,2,…,n环形排列，按顺时针方向自1开始报数，报到K时输出该位置上的数字，并使其出列。然后从他在顺时针方向的下一个数字继续报数，如此下去，直到所有的数字全部出列为止。例如N=10，K=3，则正确的出列顺序应为3，6，9，2，7，1，8，5，10，4。

数据结构实验

实验2 堆栈与队列

实验目的

1．会定义顺序栈和链栈的结点类型。 2．掌握栈的插入和删除结点在操作上的特点。 3．熟悉对栈的一些基本操作和具体的函数定义。 4．会定义顺序队列和链队列的结点类型。

实验内容

程序1 舞伴问题

问题描述：假设在周末舞会上，男士和女士进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一个配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。编写程序模拟上述舞伴配对问题。

问题分析：根据问题描述可知，新来人员将根据性别分别在队尾插入到男队或女队。排在队头的男士或女士优先出队，并与另一个队中的队头成员组成舞伴。由此可见，舞伴问题中的成员关系存在着先进先出的特点，可以采用队列这种数据结构来存储两队信息。舞伴问题中，不断有队头成员出队组成新的舞伴及新成员在队尾插入的操作，如果采用的顺序队列，由于队头元素删除后，存储空间的不可重复操作性，将导致存储空间浪费，从而造成假溢出现象的发生。根据以上分析，采用循环队列进行存储。

程序2回文数

由于输入的一个回文数可能无穷大，所以要求使用单链表存储该数。

问题描述：将用户输入的数以一个单链表的方式存储。从头扫描该单链表，将前面的一半元素入栈，若元素的总个数为奇数，则跳过中间的那个元素，然后开始循环：边退栈边在单链表中后移指针，若当前栈顶元素与单链表中当前节点的值域不相等，则退出循环。最后如果栈空且链表比较完毕，则是回文数，否则不是回文数。

数据结构实验

实验3 二叉树基本操作

实验目的

1．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。

3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4．在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。 5．掌握构造赫夫曼树以及赫夫曼编码的方法。

实验内容

程序1 二叉树的基本操作

该程序的功能是实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 /* 定义DataType为char类型 */ typedef char DataType;

/* 二叉树的结点类型 */ typedef struct BitNode

{DataType data;

struct BitNode *lchild,*rchild;

}BitNode,*BitTree;

/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT)

/* 按先序次序建立一个二叉树*/ void BinTreeCreat(BitTree *BT)

/* 检查二叉树是否为空 */ int BinTreeEmpty(BitTree *BT)

数据结构实验

/* 按任一种遍历次序（包括按先序、中序、后序、按层次）输出二叉树中的所有结点 */ void BinTraverse(BitTree *BT) /* 求二叉树的深度 */ int BinTreeDepth(BitTree BT) /* 求二叉树中所有结点数 */ int BinTreeCount(BitTree BT) /* 清除二叉树，使之变为空树 */ void BinTreeClear(BitTree *BT)

程序2 赫夫曼树和赫夫曼编码

从终端输入若干个字符，统计字符出现的频率，将字符出现的频率作为结点的权值，建立赫夫曼树，然后对各字符进行赫夫曼编码。最后打印赫夫曼树和对应的赫夫曼编码。设计要求：在程序中构造四个子程序为

int freqchar(char *text, HTree *t) /*统计字符出现的频率*/ int createhtree(HTree *t) /*根据字符出现的频率建立赫夫曼树*/ void coding(HTree *t,int head_i,char *code) /*对赫夫曼树进行编码*/ void printhtree(HTree *t,int head_i,int deep,int* path)/*中序打印树*/

数据结构实验

实验4 图的基本操作

实验目的

1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。

2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历

算法，复习栈和队列的应用。

3．掌握以邻接矩阵作为存储结构的生成图的最小生成树的普里姆算法。

实验内容

程序1图的存储与遍历

/* 定义邻接矩阵类型 */ typedef int adjmatrix[n+1][n+1];

/* 建立图的邻接矩阵 */ void CreatMatrix(adjmatrix GA)

/* 从初始点v出发深度优先遍历邻接矩阵GA表示的图 */ void DfsMatrix(adjmatrix GA,int v)

/*从初始点v出发广度优先遍历邻接矩阵GA表示的图*/ void BfsMatrix(adjmatrix GA,int v)

程序2图的存储与遍历

/* 邻接表的结点类型 */ typedef struct arc {int adjvex;

struct arc *next;}ArcNode; typedef struct VexNode {int vertex; ArcNode *firstarc;

数据结构实验

}VerNode;

typedef VerNode AdjList[MAXNODE];

/* 建立图的邻接表 */ void CreatAdjlist(AdjList GL)

/* 从初始点v出发深度优先遍历邻接表GL表示的图 */ void DfsAdjlist(AdjList GL,int v)

/*从初始点v出发广度优先遍历邻接表GL表示的图*/ void BfsAdjlist(AdjList GL,int v)

程序3

/* 定义邻接矩阵类型 */ typedef int adjmatrix[n+1][n+1];

typedef struct {int fromvex,tovex; int weight; }TreeEdgeNode;

typedef TreeEdgeNode MST[n]; /* 定义辅助数组类型 */ typedef struct {int adjvex; int lowcost; }closeedge[n];

/* 建立无向带权图的邻接矩阵 */ void CreatMatrix(adjmatrix GA,int n，int e)

/*初始化图的边集数组*/

数据结构实验

void InitEdge(EdgeNode GE,int m)

/*根据图的邻接矩阵生成图的边集数组*/ void GetEdgeSet(adjmatrix GA,EdgeNode GE)

/*按升序排列图的边集合数组*/ void SortEdge(EdgeNode GE,int m)

/*输出边集数组的每条边*/ void OutEdge(EdgeNode GE,int e)

/* 利用普里姆算法从初始点v出发求邻接矩阵表示的图的最小生成树 */ void Prim(adjmatrix GE,int v)

/* 利用克鲁斯卡尔算法从初始点v出发求邻接矩阵表示的图的最小生成树 */ void Kruskal(EdgeNode GE,EdgeNode T)

数据结构实验

实验5 查找

实验目的

1、掌握查找的不同方法，并能用高级语言实现查找算法。

2、熟练掌握顺序表和有序表的查找方法以及静态查找树的构造方法和查找算法，理解静态查找树的折半查找的方法。

3、熟练掌握二叉树的构造和查找方法。

实验内容

设计一个读入一串整数构成一棵二叉排序树算法。

实现提示：二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。插入是这样进行的：若二叉排序树为空，则待插入结点*s作为根结点插入到空树中；当二叉排序树非空，将待插结点的关键字s->key与树根的关键字t->key比较，若s->key=t->key，则说明树中已有此结点，无须插入；若s->keykey，则将待插结点*s插入到根的左子树中，否则将*s插入到根的右子树中。而子树中的插入过程又和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树中已有结点*s为止。

数据结构实验

实验6 排序

实验目的

1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。 2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。

3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

实验内容

在学生成绩管理中，经常会遇到求平均成绩，统计不及格学生成绩，统计优秀学生人数，以及按成绩对学生进行排名等。现假设有某个班级的若干名学生，每个学生都考试完成了4门课程，试对所有学生的成绩完成以下工作：

（1）求每门课程的平均成绩。

（2）输出所有有不及格课程的学生的学号、姓名、全部课程的成绩、平均成绩。（3）输出所有平均分在90分以上（含90分）的学生学号、姓名。

（4）对4门课程中的任何一门，可随意抽取1门按学生成绩采用任意一种排序方法进行排序

《数据结构》实验报告

实验名称姓名专业成绩学号班级日期实验目的实验本次共有个练习，完成个。进度本次实验的步骤或程序及运行结果（表格不够可另加附页）。实验内容

实验内容

实验分析

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

数据结构习题