数据结构课后习题

习题一

一、单选题

1.下列四种基本逻辑结构中，数据元素之间关系最弱的是，列队属于

A.集合B.线性结构C.树形结构D.图形结构

2.线性结构各数据元素之间存在着的关系，图形结构数据元素之间存在

__的关系。

A.无关B,一■对一,C.一■对多D.多对多

3.在数据结构中，从逻辑上看可以把数据结构分为。

A.动态结构和静态结构B.紧凑结构和非紧凑结构

C.线性结构和非线性结构D.内部结构和外部结构

4.算法中的基本操作重复执行的频度称为算法的;除了考虑存储数据结

构本身所占用的空间外，实现算法所用辅助空间的多少称为算法的O

A.时间复杂度B.空间复杂度C.硬件复杂度D软件复杂度

5.算法分析的目的是①，算法分析的两个主要方面是②o

①A.找出数据结构的合理性B.研究算法中的输入和输出关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性

②A.空间复杂度和时间复杂度B.正确性

C.可读性和文档性D.数据复杂性和程序复杂性

6.计算机算法指的是①，它必具备输入、输出和②等五个特性。

①A.计算方法B.排序方法

C.解决问题的有限运算序列D.调度方法

②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

线性表的逻辑顺序与存储顺序总是一致的，这种说法

A.正确B.不正确

8.线性表若采用链式存储结构时,要求内存中可用存储单元的地址

A.必须是连续的B.部分地址必须是连续的

C.一定是不连续的D.连续或不连续都可以

二、填空题（将正确的答案填在相应的空中）

1.数据逻辑结构包括集合、、和四种类

型，树形结构和图形结构统称为o

2.线性结构中，第一个结点前驱结点，其余每个结点有且仅有

个直接前驱结点；最后一个结点后继结点，其余每个结点有

且仅有个直接后继结点。

3.在树形结构中，树根结点没有结点，其余每个结点有且只有个

前驱结点；叶子结点没有结点，其余每个结点的后继结点可以o

4.在图形结构中，每个结点的前驱结点数和后继结点数可以。

5.线性结构中元素之间存在关系，树形结构中元素直接存在关

系，图形结构中元素之间存在关系。

6.算法的五个重要特性是、、、、

7.下列程序段的时间复杂度是

for(i=0;i<n;i++)

for(j=0;j<m;j++)

a[i皿=0;

8.下列程序段的时间复杂度是

i=s=0;

while(s<n)

(

i++；

S+=I；

)

9.下列程序段的时间复杂度是

s=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

s+=b[ij[jj;

sum=s;

10.下列程序段的时间复杂度是

i=l；

while（i<n）

i=i*3;

习题二

一、填空题

1.在一个长度为n的向量的第i个元素（l<=i<=n）之前插入一个元素时，需向

后移动个元素。

2.在一个长度为n的向量中删除第i个元素（l<=i<=n）时，需向前移动个

元素。

3.单链表是的链接存储表示。

4.在单链表中设置头结点的作用是在插入或删除第一个结点时不必对

进行处理。

5.在双链表中，每个结点有两个指针域，一个指向，另一个指向

6.在一个单链表中p所指结点之后插入一个s所指结点时，应执行

s->next=和p->next的操作。

7.非空的循环单链表head的尾结点（由p所指向）满足条件。

二、单选题

1.不带头结点的单链表head为空的判断条件是o

A.head=NULLB.head->next=NULL

C.head->next=headD.head!=NULL

2.带头结点的单链表head为空的判断条件是-

A.head=NULLB.head->next=NULL

C.head->next=headD.head!=NULL

3.非空的循环单链表head的尾结点（由p所指向）满足o

A.p->next=NULLB.p=NULL

C.p->next=headD.p=head

4.在循环双链表的p所指结点之后插入s所指结点的操作是。

A.p-<next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B.p-<next=s;p->next->prior=s;s->prior=p;s->next=p->next;

C.s->prior=p;s->next=p->next;p-<next=s;p->next->prior=s;

D.s->prior=p;s->next=p->next;p->next->prior=s;p-<next=s;

5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之

间插入S结点，则执行O

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;

C.q->next=s;s->next=p;D.p->next=s;s->next=q;

6.一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则

执行O

A.s->next=p;p->next=s;B.s->next=p->next;p->next=;

C.s->next=p->next;p=s;D.p->next=s;s->next=p;

7.在一个单链表中，若删除p所指结点的后继结点，则执行o

A.p->next=p->next->nextB.p=p->next;p->next=p->next->next

C.p->next=p->nextD.p=p->next->next

三、算法描述题

1.已知一个向量中的元素按元素值非递减有序排列，编写一个函数删除向量中

多余的值相同的元素。

2.编写一个函数将一个向量A（有"个元素，且任何元素均不为0）分拆成两个

向量，使A中大于0的元素存放在B中，小于0的元素存放在C中。

3.已知在一维数组A[l,m+n]中依次存放着两个向量（a的,..,am）和（也,

b2,……，ba）,编写一个函数将两个向量的位置互换，即把（b”b2,……,ba）

放到（ai,a2,.......，am）的前面。

4.有一个单链表（不同结点的数据值域可能相同），其头指针为head,编写一个

函数计算数据域为x的结点个数。

5.编写一个函数将不带头结点的单链表La复制成单链表Lbo

6.有一个单链表，其结点的元素值以非递减有序排列，编写一个函数删除该单

链表中多余的元素值相同的结点。

习题三

一、填空题

1.栈是限定仅在表尾进行操作的线性表，表头端称为，

表尾端称为，栈的操作特性是0

2.队列是限定仅在表尾进行和在表头端进行的线性

表，列队的操作特性是O

3.以下定义了一个顺序栈：

#defineMAXSTACK500

typedefstruct{

chardata[MAXSTACKl;

inttop;

Jsqstack;

sqstackss;

栈空的条件是：,栈满的条件是：;

栈顶元素的表达式是:,栈底元素的表达式是:。

二、简答题

1.设将整数1,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次

序插入在入栈操作之间，请回答下述问题：

(1)若入出栈次序为Push(l),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),

PopO,则出栈的数字序列是什么(这里Push(i)表示进栈，Pop()表示出栈)？

(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。

(3)请分析1,2,3,4的24种排列中，哪些序列可以通过相应的入、出栈操作

得到。

2.循环队列的优点是什么？如何判别它的空和满？

三、算法设计题

1.回文是指正读反读均相同的字符序列,如“abba"和“abdba”均是回文，

但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将

一半字符入栈。)

2.括号配对检查，输入一个只有左括号“(”和右括号“)”的序列，程序对

括号配对的正确性进行检查并给出结果。提示：配对检查算法中用到栈结构。例

如括号序列“(()())”、“()()(())”为正确配对，括号序列“()())”、“)()(”为

不正确配对等。注意：输入序列中只能出现左括号“(”和右括号“)”，序列的

语法正确性由用户保证。

请给出完整的C程序描述。

习题四

一、填空题

1.已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储

单元，并且第一个元素的存储地址是Loc(A[0][0]),则A[iJ[j]的地址是

2.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单

元，并且A[0][0]的存储地址是200,则A⑹⑵的地址是o

二、单选题

1.常对数组进行的两种基本操作是O

A.建立与删除B.索引和修改C.查找和修改D.查找与索引

2.数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1

到10,存放该数组至少需要的单元数是o

A.80B.100C.240D.270

3.数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1

到10,从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]

的起始地址为o

A.SA+141B.SA+144C.SA+222D.SA+225

4.稀疏矩阵一般的压缩存储方法有两种，即o

A.二维数组和三维数组B.三元组表和散列

C.三元组表和十字链表D.散列和十字链表

三、算法描述题

假设稀疏矩阵Am*n和Bm*n都采用三元组表，编写一个函数计算C=A+B,

要求C也采用三元组表表示。

习题五

一、简答题

1.设s="IAMASTUDENT”，

t="GOOD”，

q="WORKER”。

求：STRLEN(s),STRLEN(t),SUBSTR(s,8,7,),SUBSTR(t,2,1),

INDEX(s,"A"),INDEX(s,t),REPLACES,“STUDENT”，q)o

2.已知下列字串：

a="THIS"，f="ASMPLE"，c="GOOD"，d="NE”,b=""，g=“IS”

s=CONCAT(a,CONCAT(CONCAT(b,SUBSTR(a,3,2)),SUBSTR(f,2,

6)))

t=REPLACE(f,SUBSTR(f,3,5),c)

u=CONCAT(SUBSTR(c,3,1),d)

v=CONCAT(s,CONCAT(b,CONCAT(t,CONCAT(b,u))))

问s,t,v,STRLEN(s),INDEX(v,g),INDEX(u,g)各是什么?

3、简述下列每对术语的区别：

空串和空格串；串变量和串常量；主串和子串。

4、两个字符串相等的充要条件是什么？

5、设已知两个串为：

Si="becadcabcadf”；

82="abc"。

试求两个串长度，并判读断S2串是否是与的子串。如果S2是否是S1的子

串，指出S2在$中的起始位置。

二、算法设计题

编写算法，在顺序串上实现串的判等操作EQUAL(S,T)o设两个串分别为

S="Beijing"，T="China”,调用函数EQUAL(S,T)判断后,如果S=T,则返回

1,否则返回0.

习题六

一、判断题

1、二叉树是树的特殊情形。（）

2、二叉树的先序遍历序列中，任意节点均处在其孩子结点之前。（）

3、二叉链表是一种逻辑结构。（）

4、由二叉树的先序序列和后序序列可以唯一确定一棵二叉树。（）

5、n个结点的完全二叉树不唯一。（）

6、树的后续遍历序列与其对应的二叉树的后序遍历序列相同。（）

7、完全二叉树的某结点若无左孩子，则它必是叶子结点。（）

二、选择题

1、将一棵树t转换为孩子兄弟链表表示的二叉树h,则t的后序遍历是卜的（）

A.先序遍历B.中序遍历C.后序遍历D.层次遍历

2、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的

编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用

（）次序的遍历实现编号。

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

3、已知一•棵完全二叉树中共有768个结点，则该树中共有（）个叶子结点。

A.383B.384C.385D.386

4、先序遍历和中序遍历相同的二叉树为（）

A.只有根结点的二叉树B.根结点无左孩子的二叉树

C.一般二叉树D,只有根结点的二叉树和所有结点只有右子树的二叉树

三、简答题

1、一棵树的边集为｛（a,b）,（b,e）,（a,c）,（c,g）,（a,d）,（d,i）,（c,f）,（c,h）,（d,j）,

（i,k）｝,请画出此棵树的形态，并回答下列问题：

（1）树的根是哪个结点？哪些是叶子结点？哪些是分支结点？

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

（3）各结点的层次分别是多少？树的深度是多少？以d为根的子树深度是

多少？

（4）结点i的双亲是哪个结点？祖先是哪个结点？孩子是哪些结点？兄弟

是哪些结点？

2、树和二叉树有哪些区别？

3、已知二叉树的后序和中序序列如下，构造出该二叉树，写出它的前序遍历

序列。

后序序歹U：ABCDEFG中序序歹U：ACBGDFE

4、假设用于通信的电文由字符集｛岫,斓©胴｝中的字母构成，它们在电文中

出现的频度分别为｛0.31,,0.16,0.10,0.08,0.11,0.20,0.04）

（1）为这7个字母设计哈弗曼编码。

（2）对这7个字母进行等长编码，至少需要几位二进制数？哈弗曼编码与

等长编码相比，能使电文总长压缩多少？

四计算题

1、设计算法求二叉树的高度。

2、按要求写出算法，功能为判断一棵二叉树（采用二叉链表存储结构）是否

为完全二叉树。

习题七

-、单项选择题

1、一个有n个顶点的无向图最多有条边。

A.nB>n（n-l）C、n（n-l）/2D、2n

2、一个有4个顶点的无向完全图有条边。

A、6B、12C、16D、20

3、一个有5个顶点的连通图至少有条边

A、3B、4C、5D、6

的邻接矩阵是对矩阵。

A、有向图B、无向图C、AOV网

5、邻接表时图的一种。

A、顺序存储结构B、链接存储结构C、索引存储结构D、散列存储结构

6、采用邻接表存储的图的深度优先遍历算法类似于二叉树的o

A、前序遍历B、中序遍历C、后序遍历D、按层遍历

7、采用邻接表存储的图的广度优先遍历算法类似于二叉树的。

A、前序遍历B、中序遍历C、后序遍历D、按层遍历

8、任何一个无向连通图最小生成树。

A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在

9、一个图的表示法师唯一的，而表示是不是唯一的。

A、三元组B、邻接矩阵C、邻接表D索引

二、简答题

1、对图7.23所示有向图，回答下列问题

(1)该图是强连通图吗?若不是，则给出其强连通分量。

(2)请给出从顶点1到顶点3的所有的简单路径。

(3)请给出顶点1的度、入度和出度。

(4)请给出其邻接矩阵，邻接表及逆邻接表。

2、对图7.24所示无向图，分别给出它从顶点1出发进行深度和广度遍历得到的

顶点序列

图7.23有向图

3、对图7.25所示无向图，分别画出按普里姆算法和克鲁斯卡尔得到最小生成树

的过程。

4、对图7.26所示有向图，利用辿杰斯特拉算法，求从顶点1到其余各项点的最

短路径

5、对图7.27所示有向图,求拓扑序列。

习题八

一、单选题

1、对线性表进行二分查找时，要求线性表必须o

A、以顺序方式存储B、以链接方式存储

C、以顺序方式存储且结点按关键字有序排列

D、以链接方式存储且结点按关键字有序排列

2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度

为O

A、nB、n/2C、(n+l)/2D、(n-l)/2

3、采用二分查找长度为n的线性时，每个元素的平均查找长度为o

A>O(n2)B、O(nlong2n)C、O(n)D、O(long2n)

4、有一个序列表为(5,7,8,22,32,40,45,62,70,77,82,97,100),

当二分查找值为82的结点时-，次比较后查找成功。

A、1B、3C、4D、8

5、从一个具有n个结点的单链接表中查找其值等于x结点时，查找成功的情况

下，需平均比较个结点。

A、nB、n/2C、(n-l)/2D、(n+l)/2

二、填空题

1、假设有序线性表A[l],……，A[20]上进行二分查找，则比较一次查找成功的

结点数为，则比较二次查找成功的结点数为,则比较三次查找成

功的结点数为，则比较四次查找成功的结点数为,则比较五次查

找成功的结点数为，平均查找长度为o

2、在散列存储中，装填因子a的值越大，存取数据元素是发生冲突的可能

性;a的值越小，则发生冲突的可能性o

三.简答题、

设有一组关键字(19,01,23,14,55,20,84,27,68,11,10,77)采用哈

希函数

H(key)=key%13

1,、采用开放地址的线性探测再散列方法解决冲突，试在[0…12]的散列地址

空间中对该关键字序列构造哈希表

2、对上题中的关键字序列，采用链地址法，画出相应的哈希表

3、对有序表(5,8,27,35,45,48,57,72,89,95),采用二分查找，画出

二分查找过程的二叉判定树，并计算其平均查找长度。

四.算法设计题

1.将折半查找算法改写为递归的形式。

2.以线性探测再散列为例，给出散列表的查找算法。

习题九

一、单选题

1、在所有排序方法中、关键字比较的次数与记录的初始排列次序无关的

是O

A、希尔排序B、冒泡排序C、直接插入排序D、直接选择排序

2、没有1000个无序的元素、希望用最快的速度挑选出其中前10个最大的元素,

最好的排序法。

A、冒泡排序B、堆排序C、快速排序D、基数排序

3、排序的元素序列基本有序的前提下，效率最高的排序方法是______」

A、直接插入排序B、直接选择排序C、快速排序D、归并排序

4、一组记录的排序码