数据结构习题及答案

青岛科技大学《数据结构》课程练习题及答案

第1章 绪论

一、选择题

1.算法的计算量的大小称为计算的（ ）。

A．效率 B.复杂性 C.现实性 D.难度

2.一个算法是（ ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 3．从逻辑上可以把数据结构分为（ ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构

C．线性结构、非线性结构 D．初等结构、构造型结构 二、判断题

1.数据元素是数据的最小单位。( )

2.数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 3.算法的优劣与算法描述语言无关，但与所用计算机有关。( )

4.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )

5.算法可以用不同的语言描述，如果用C语言来描述，则算法实际上就是程序了。( ) 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 三、填空

1.数据的物理结构包括数据元素的表示和 的表示。

2.对于给定的n个元素,可以构造出的四种逻辑结构有：集合、 和图状结构。 3.数据的逻辑结构是指 。

4.一个数据结构在计算机中 称为存储结构。 5.数据结构中评价算法的两个重要指标是 。

6.一个算法具有5个特性: 、有零个或多个输入、有一个或多个输出。 7.计算机执行下面的语句时，语句s的执行次数为 _______ 。 for(i=l；i

for(j=n;j>=i;j--)

s;

8.下面程序段的时间复杂度为________。(n>1) sum=1；for(i=0;sum

1.数据结构是一门研究什么内容的学科？

2.回答问题

（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？

（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明。 3．数据结构与数据类型有什么区别？

4．有下列运行时间函数：

（1）T1 (n)=1000; 2）T2(n)=n2+1000n; （3）T3(n)=3n3+100n2+n+1; 分别写出相应的大O表示的运算时间。

第2章 线性表

一 选择题

1.下述哪一条是顺序存储结构的优点？（ ）

1

青岛科技大学《数据结构》课程练习题及答案

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

2.下面关于线性表的叙述中，错误的是哪一个？（ ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。

3.线性表是具有n个（ ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项

4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5.链表不具有的特点是（ ）

A．插入、删除不需要移动元素 B．可随机访问任一元素

C．不必事先估计存储空间 D．所需空间与线性长度成正比 6.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。

A. O(0) B. O(1) C. O(n) D. O(n2)

7.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。

A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 8．线性表（a1,a2,?,an）以链式方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1） 9．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。

A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s; 10．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）

A．head==NULL B．head->next==NULL C．head->next==head D．head!=NULL 二、判断题

1.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 2.对任何数据结构链式存储结构一定优于顺序存储结构。( ) 3.集合与线性表的区别在于是否按关键字排序。( )

4.线性表的特点是每个元素都有一个前驱和一个后继。( ) 5.循环链表不是线性表. ( )

6.线性表就是顺序存储的表。( )

三、填空题

1.线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。

2.在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。

3.一个具有n个结点的单链表，在已知的结点后插入一个新结点的时间复杂度为_______。 4.一个具有n个结点的单链表，在给定值的结点后插入一个新结点的时间复杂度为_____。 5.顺序存储结构是通过________表示元素之间关系的；链式存储结构是通过指针表示元素之间关系的。

6.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________

2

青岛科技大学《数据结构》课程练习题及答案

7.在单链表L中，指针p所指结点有后继结点的条件是：__ 。

四、应用题

1．线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？

2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。 3．线性表（a1，a2，?，an）用顺序映射表示时，ai和ai+1（1<=i

4. 设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。

五、算法设计题

1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

2．已知非空线性链表由list指出，链结点的构造为（data,next）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。

3．设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：

（1）找出最小值结点，且打印该数值；

（2）若该数值是奇数，则将其与直接后继结点的数值交换； （3）若该数值是偶数，则将其直接后继结点删除。

第3章 栈和队列

一、选择题

1.对于栈操作数据的原则是（ ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

2.一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定 B. n-i+1 C. i D. n-i

3.若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的

4.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 5.输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）

A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop

C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 6.若栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。 A．top:=top+1; V[top]:=x B. V[top]:=x; top:=top+1

C. top:=top-1; V[top]:=x D. V[top]:=x; top:=top-1

7.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈

3

青岛科技大学《数据结构》课程练习题及答案

顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。

A.|top[2]-top[1]|=0 B.top[2]+1=top[1] C.top[1]+top[2]=m D.top[1]=top[2] 8.一个递归算法必须包括（ ）。

A.递归部分 B.终止条件和递归部分 C.递推部分 D.终止条件和递推部分

9.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 10.用链式方式存储的队列，在进行删除运算时（ ）。 A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改 11.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。

A.(rear-front+m)%m B.rear-front+1 C．(front-rear+m)%m D.(rear-front)%m 12.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A.(rear+1)%n=front B. rear=front C．rear+1=front D. (rear-l)%n=front 13.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。

A． 6 B. 4 C. 3 D. 2

14．某个车站呈狭长型，宽度只能容下一辆车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入纪录为：“进，出，进，进，进，出，出，进，进，进，出，出”。假设车辆入站的顺序为1，2，3，??，则车辆出站的顺序为（ ）。

A．1，2，3，4，5 B．1，4，3，7，6 C．1，2，4，5，7 D．1，4，3，7，2 二、判断题

1.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ ）

2.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ）

3.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。（ ）

4.栈和队列都是限制存取点的线性结构。（ ）

5.只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（ ）

6.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）

7.循环队列也存在空间溢出问题。（ ）

三、填空题

1．_______是限定仅在表尾进行插入或删除操作的线性表。

2.一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。

3.设有一个空的顺序栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，栈顶指针值是_______H。每个元素占4个字节。 4．用I表示入栈操作，O表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的I和O的操作串为_______。

5.循环队列的引入，目的是为了克服_______。 6.设循环队列用数组A[1..M]表示，队首、队尾指针分别是front和rear，判定队满的条件为_______。

7.设循环队列存放在向量sq.data[0..M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______。

4

青岛科技大学《数据结构》课程练习题及答案

四、应用题

1.有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？

2.设一数列的输入顺序为123456，若采用栈结构，并以I和O分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。

（1）能否得到输出顺序为325641的序列。 （2）能否得到输出顺序为154623的序列。

3.用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C语言写出入栈的操作。 五 算法设计题

1.假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 （1）下面所示的序列中哪些是合法的？

A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO

（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。 2.请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释） 3.试将下列递归过程改写为非递归过程。

void test(int &sum) { int x； scanf(x)；

if(x=0) sum=0 else {test(sum); sum+=x;} printf(sum)；

}

第4章 串

一、选择题

1．下面关于串的的叙述中，哪一个是不正确的？（ ）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2.若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat(replace (S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（ ）

A．ABC###G0123 B．ABCD###2345 C．ABC###G1234 D．ABC###G2345

3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A．求子串 B．联接 C．匹配 D．求串长 4．模式串t=‘abcaabbca’，该模式串的next数组的值为（ ）。

A．0 1 1 1 2 2 1 1 1 B．0 1 1 1 2 1 2 1 1 C．0 1 1 1 0 0 1 3 1 D．0 1 1 1 2 2 3 1 1 5．串的长度是指（ ）

A．串中所含不同字母的个数 B．串中所含字符的个数

5

青岛科技大学《数据结构》课程练习题及答案

C．串中所含不同字符的个数 D．串中所含非空格字符的个数

二、判断题

1．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（ ） 2．设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ） 3．串是一种数据对象和操作都特殊的线性表。（ ） 二、填空题

1．组成串的数据元素只能是________。 2．INDEX（‘DATASTRUCTURE’，‘STR’）=________。

3．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。 4．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，称P为____。 5．串是一种特殊的线性表，其特殊性表现在____。 6. 串的两种最基本的存储方式是____。

7．两个字符串相等的充分必要条件是_______。

第5章 数组和广义表

一、选择题

1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 B. 33 C. 18 D. 40

2.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i

A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i

3.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。 A. 60 B. 66 C. 18000 D. 33 4.对稀疏矩阵进行压缩存储目的是（ ）。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 5.广义表（（a,b,c,d））的表头是（ ）。

A. a B.（） C.（a,b,c,d） D.（b,c,d） 6.广义表（（a,b,c,d））的表尾是（ ）。

A. a B.（） C.（a,b,c,d） D.（b,c,d） 7.设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。

A. 1和1 B. 1和3 C. 1和2 D. 2和3 8.下面说法不正确的是( )。

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表

C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、判断题

1.从逻辑结构上看，n维数组的每个元素均属于n个向量。（ ） 2.稀疏矩阵压缩存储后，必会失去随机存取功能。（ ） 3.数组是同类型值的集合。（ ）

4.数组可看成线性结构的一种推广，与线性表一样，可以对它进行插入，删除等操作。（ ） 5.一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ ）

6

青岛科技大学《数据结构》课程练习题及答案

6.二维以上的数组其实是一种特殊的广义表。（ ）

7.若一个广义表的表头为空表，则此广义表亦为空表。（ ）

8.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ） 9.广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（ ） 三、填空题

1.数组的存储结构采用_______存储方式。

2.二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储)

3.己知三对角矩阵A【1..9,1..9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为______。 4.所谓稀疏矩阵指的是_______。

5.当广义表中的每个元素都是原子时，广义表便成了_______。

第6章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A．5 B．6 C．7 D．8

3.在下述结论中，正确的是（ ）

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④

4.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）

A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定

5．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A．250 B． 254 C．500 D．501

6.设给定权值总数有n 个，其哈夫曼树的结点总数为( )

A．不确定 B．2n C．2n+1 D．2n-1

7.有关二叉树下列说法正确的是（ ）

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

A．2I B． 2I-1-1 C． 2I-1 D．2I -1 9.一个具有1025个结点的二叉树的高h为（ ）

A．11 B．10 C．11至1025之间 D．10至1024之间 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点

A．2h B．2h-1 C．2h+1 D．h+1 11.一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）

A．?log2n?+1 B．log2n+1 C．?log2n? D．log2n-1 12．深度为h的满m叉树的第k层有（ ）个结点。(1=

A．mk-1 B．mk-1 C．mh-1 D．mh-1 13．高度为K的二叉树最大的结点数为（ ）。

7

青岛科技大学《数据结构》课程练习题及答案

A．2

k

B．2 C．2-1

k-1k

D．2-1

k-1

14. 一棵树高为K的完全二叉树至少有（ ）个结点

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

15.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）

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

A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 17．树的后根遍历序列等同于该树对应的二叉树的( ).

A. 先序序列 B. 中序序列 C. 后序序列 D从根开始按层次遍历 18．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次

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

A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 20．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是：

A、 E B、 F C、 G D、 H 21．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）

A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树

22.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )

A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点

23. 引入二叉线索树的目的是（ ）

A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 24．n个结点的线索二叉树上含有的线索数为（ ） A．2n B．n－l C．n＋l D．n 25．下述编码中哪一个不是前缀码（ ）。

A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001） 二、判断题

1.二叉树是度为2的有序树。

2.完全二叉树一定存在度为1的结点。

3.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。

4．由一棵二叉树的前序序列和后序序列可以唯一确定它。

5．完全二叉树中，若一个结点没有左孩子，则它必是树叶。

6.一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i

8. 二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊

8

青岛科技大学《数据结构》课程练习题及答案

情形.

9．树形结构中元素之间存在一个对多个的关系。

10．在二叉树中插入结点，则此二叉树便不再是二叉树了。 11．树与二叉树是两种不同的树型结构。

12.非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子

13．哈夫曼树的结点个数不能是偶数。

14．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。

15．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 三、填空题

1．二叉树由根结点，左子树，___三个基本单元组成。 2．在二叉树中，指针p所指结点为叶子结点的条件是______。

3．深度为k的完全二叉树至少有______个结点，至多有2-1个结点。

4．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是______。 5．一棵有n个结点的满二叉树有__ _个度为1的结点。

6．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。

7．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______。 8．高度为8的完全二叉树至少有______个叶子结点。

9．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。 10．具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。 11．利用树的孩子兄弟表示法存储，可以将一棵树转换为______。

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

13.在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是______。

14．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 15．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，字符c的编码是_(2)__。 四、应用题

1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

2．一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：

1）各层的结点的数目是多少？

2）编号为n的结点的双亲结点（若存在）的编号是多少？

3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？

4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。

3．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 4．若一棵树中有度数为1至m的各种结点数为n1,n2,?,nm(nm表示度数为m的结点个数)请推导出该树中共有多少个叶子结点n0的公式。

5．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。 先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G

k

9

青岛科技大学《数据结构》课程练习题及答案

后序序列 ：_ E F D B _ J I H _ A

6．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。

7．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问：

（1）T树的最大深度Kmax=?最小可能深度Kmin=? （2）T树中共有多少非叶结点？

(3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。

第7章 图

一、选择题

1．图中有关路径的定义是（ ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。

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

A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ ）条边。

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

5．n个结点的完全有向图含有边的数目（ ）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．下列哪一种图的邻接矩阵是对称矩阵？（ ）

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

A． 图的遍历是从给定的源点出发每一个顶点仅被访问一次

B． 遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程

9．无向图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．下面哪一方法可以判断出一个有向图是否有环（回路）：( ) A．广度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径

10. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。

A. O(n) B. O(n+e) C. O(n2) D. O(n3)

11．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，

E={,,,,,,,,},G的拓扑序列是（ ）。

A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7

C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7

12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。

10

青岛科技大学《数据结构》课程练习题及答案

录的_____。

5．直接插入排序用监视哨的作用是_______。 6．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。 9．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果_______。

四、应用题

1.在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。

2．在执行某种排序算法的过程中出现了关键字朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 3．在堆排序、快速排序和合并排序中：

(1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？

(2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？

(3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？

(4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 4．设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k，最好采用什么排序方法？为什么？如果有这样一个序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，对于该例使用所选择的方法实现时，共执行多少次比较？ 5．奇偶交换排序如下所述：对于初始序列A[1]，A[2],?,A[n],第一趟对所有奇数i（1<=iA[i+1]，则将两者交换；第二趟对所有偶数i（2<=iA[i+1]，则将两者交换；第三趟对所有奇数i（1<=i

(2)写出用这种排序方法对35，70，33，65，24，21，33进行排序时，每一趟的结果。 五、算法设计题：

1．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。

16

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