数据结构复习题.docx
《数据结构复习题.docx》由会员分享，可在线阅读，更多相关《数据结构复习题.docx（39页珍藏版）》请在冰点文库上搜索。
数据结构复习题
考试说明
考试内容：
一、绪论
数据结构的基本概念和分类、数据结构的逻辑结构、存储结构、算法、数据结构的选择和评价
二、线性表
线性表的类型定义、线性表的顺序表示和实现、线性表的链式表示和实现
三、栈和队列
栈和队列的结构特性、两种存储结构上实现栈和队列的基本操作、栈和队列在程序设计中的应用
六、树和二叉树
树、二叉树的定义、性质和存储结构、二叉树的遍历和线索化、二叉树和森林转换、最优树和哈夫曼编码。
七、图
图的定义和术语、图的存储结构、图的遍历、最小生成树、拓扑排序、最短路径问题。
九、内部排序
插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程、时间复杂度分析及其应用。
试题类型及分值：
选择题30分15题
应用题40分5题
算法设计题30分3题
一选择题
1.计算机算法指的是
（1），它必须具备
（2）这三个特性。
（1）A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法
（2）A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性
C.确定性、有穷性、稳定性D.易读性、稳定性、安全性
答案：
CB
2.下面说法错误的是（）
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A．
（1）B.
（1）,
（2）C.
（1）,（4）D.（3）
答案C
3．从逻辑上可以把数据结构分为（）两大类。
A．动态结构、静态结构B．顺序结构、链式结构
C．线性结构、非线性结构D．初等结构、构造型结构
答案C
4．以下与数据的存储结构无关的术语是（）。
A．循环队列B.链表C.哈希表D.栈
答案D
5．连续存储设计时，存储单元的地址（）。
A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续
答案A
6．下面关于线性表的叙述中，错误的是哪一个？
（）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
答案B
7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用（）存储方式最节省运算时间。
A．单链表B．双链表C．单循环链表D．带头结点的双循环链表
答案：
D
8.下面的叙述不正确的是（）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B.线性表在链式存储时，查找第i个元素的时间同i的值无关
C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比
D.线性表在顺序存储时，查找第i个元素的时间同i的值无关
答案BC
10.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A．O（n）O（n）B.O（n）O
（1）C.O
（1）O（n）D.O
（1）O
（1）
答案：
C
11.循环链表H的尾结点P的特点是（）。
A．P^.NEXT:
=HB．P^.NEXT:
=H^.NEXTC．P:
=HD．P:
=H^.NEXT
答案：
A
12．完成在双循环链表结点p之后插入s的操作是（）
A．p^.next:
=s;s^.priou:
=p;p^.next^.priou:
=s;s^.next:
=p^.next;
B．p^.next^.priou:
=s;p^.next:
=s;s^.priou:
=p;s^.next:
=p^.next;
C．s^.priou:
=p;s^.next:
=p^.next;p^.next:
=s;p^.next^.priou:
=s;
D．s^.priou:
=p;s^.next:
=p^.next;p^.next^.priou:
=s;p^.next:
=s;
答案D
13．在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为:
rlink（p）←q;llink（p）←llink（q）;llink（q）←p;（）
A．rlink（q）←pB．rlink（llink（q））←pC．rlink（llink（p））←pD．rlink（rlink（p））←p
答案B
14．在双向链表指针p的结点前插入一个指针q的结点操作是（）。
A.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
C.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
答案C
15．在单链表指针为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;
答案B
16.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。
A.23415B.54132C.23145D.15432
答案：
B
17.设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。
A.51234B.45132C.43125D.32154
答案：
D
18.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（）。
A．top:
=top+1;V[top]:
=xB.V[top]:
=x;top:
=top+1
C.top:
=top-1;V[top]:
=xD.V[top]:
=x;top:
=top-1
答案：
C
19.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈（i=1,2）栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。
A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]
答案：
B
20.用链接方式存储的队列，在进行删除运算时（）。
A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改
答案D
21.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时（）。
A．仅修改队头指针B.仅修改队尾指针
C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改
答案D
22.循环队列存储在数组A[0..m]中，则入队时的操作为（）。
A.rear=rear+1B.rear=（rear+1）mod（m-1）
C.rear=（rear+1）modmD.rear=（rear+1）mod（m+1）
答案：
D
23.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
（）
A.1和5B.2和4C.4和2D.5和1
答案：
B
25．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）
A．9B．11C．15D．不确定
答案B
26．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个
A．4B．5C．6D．7
答案C
27.有关二叉树下列说法正确的是（）
A．二叉树的度为2B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2
答案B
28.有n个叶子的哈夫曼树的结点总数为（）。
A．不确定B．2nC．2n+1D．2n-1
答案D
29.利用二叉链表存储树，则根结点的右指针是（）。
A．指向最左孩子B．指向最右孩子C．空D．非空
答案C
30．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）次序的遍历实现编号。
A．先序B.中序C.后序D.从根开始按层次遍历
答案C
32．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。
A．前序B．中序C．后序D．按层次
答案D
33．在下列存储形式中，哪一个不是树的存储形式？
（）
A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法
答案D
34．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）
A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG
答案B
35．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。
A．CBEFDAB．FEDCBAC．CBEDFAD．不定
答案A
36．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（）。
A．acbedB．decabC．deabcD．cedba
答案D
39．下述编码中哪一个不是前缀码（）。
A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）
答案B
40.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）
A．A[2i]（2i=答案D
41.图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列
C．由不同边所形成的序列D．上述定义都不是
答案：
A
42．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1B．n（n-1）/2C．n（n+1）/2D．0E．n2
答案：
B
43．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。
A．1/2B．2C．1D．4
答案：
B、C
44．用有向无环图描述表达式（A+B）*（（A+B）/A），至少需要顶点的数目为（5）。
A．5B．6C．8D．9
答案：
A
45．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（A）。
A．逆拓扑有序B．拓扑有序C．无序的
答案：
A
46．下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）。
A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表
答案：
C、BDE
47．下列哪一种图的邻接矩阵是对称矩阵？
（）
A．有向图B．无向图C．AOV网D．AOE网
答案：
B
48.下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：
深度遍历和广度遍历D．图的深度遍历是一个递归过程
答案：
C
49．无向图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,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b
答案D
50．下面哪一方法可以判断出一个有向图是否有环（回路）：
A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径
答案：
AB
51.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（）。
A.O（n）B.O（n+e）C.O（n2）D.O（n3）
答案：
B
52.
（1）.求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；
（2）.利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O（n3）；（图用邻接矩阵表示）
（3）.Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
上面不正确的是（）。
A．
（1）,
（2）,（3）B．
（1）C．
（1）,（3）D．
（2）,（3）
答案A
53．当各边上的权值（）时，BFS算法可用来解决单源最短路径问题。
A．均相等B．均互不相等C．不一定相等
答案A
54.求解最短路径的Floyd算法的时间复杂度为（）。
A．O（n）B.O（n+c）C.O（n*n）D.O（n*n*n）
答案D
55.在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O（n）B.O（n＋e）C.O（n*n）D.O（n*n*n）
答案B
56.关键路径是事件结点网络中（）。
A．从源点到汇点的最长路径B．从源点到汇点的最短路径
C．最长回路D．最短回路
答案A
57.下面关于求关键路径的说法不正确的是（）。
A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
答案C
58．下列关于AOE网的叙述中，不正确的是（）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动提前完成，那么整个工程将会提前完成
答案B
59．某内排序方法的稳定性是指（）。
A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录
C．平均时间为0（nlogn）的排序方法D．以上都不对
答案：
D
60．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。
（）
A．选择排序法B.插入排序法C.快速排序法D.堆积排序法
答案：
A
61.数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。
A．选择排序B.冒泡排序C.插入排序D.堆排序
答案：
C
62．下列序列中，（）是执行第一趟快速排序后所得的序列。
A.[68，11，18，69][23，93，73]B.[68，11，69，23][18，93，73]
C.[93，73][68，11，69，23，18]D.[68，11，69，23，18][93，73]
答案C
63．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为（）（按递增序）。
A．下面的B，C，D都不对。
B．9，7，8，4，-1，7，15，20
C．20，15，8，9，7，-1，4，7D.9，4，7，8，7，-1，15，20
答案A
64．一组记录的关键码为（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）
答案C
65.在下面的排序方法中，辅助空间为O（n）的是（）。
A．希尔排序B.堆排序C.选择排序D.归并排序
答案D
66．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（）排序。
A．冒泡B.希尔C.快速D.堆
答案C
67.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：
（）。
A.直接插入排序B.快速排序C.直接选择排序D.堆排序
答案B
68.对初始状态为递增序列的表按递增顺序排序，最省时间的是（）算法，最费时间的是（）算法。
A.堆排序B.快速排序C.插入排序D.归并排序
答案CB
69.就平均性能而言，目前最好的内排序方法是（）排序法。
A.冒泡B.希尔插入C.交换D.快速
答案D
70．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。
A．起泡排序B．快速排列C．Shell排序D．堆排序E．简单选择排序
答案D
三应用题
2.设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。
（1）能否得到输出顺序为325641的序列。
（2）能否得到输出顺序为154623的序列。
答案：
（1）能得到325641。
在123依次进栈后，3和2出栈，得部分输出序列32；然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。
得输出序列325641。
其操作序列为AAADDAADADDD。
（2）不能得到输出顺序为154623的序列。
部分合法操作序列为ADAAAADDAD，得到部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。
4.简述顺序存储队列的假溢出的避免方法及队列满和空的条件。
答案：
设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。
设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。
当front等于-1时队空，rear等于m-1时为队满。
由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。
这时若再有入队操作，会造成假“溢出”。
其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。
在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。
另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
5．将算术表达式（（a+b）+c*（d+e）+f）*（g+h）转化为二叉树。
答案：
略
6.一棵有n（n>0）个结点的d度树,若用多重链表表示,树中每个结点都有d个链域,则在表示该树的多重链表中有多少个空链域?
为什么?
答案：
n（n>0）个结点的d度树共有nd个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nd-（n-1）=n（d-1）+1个。
7.一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2（n0-1），其中n0是度为0的结点的个数。
答案：
证明：
设二叉树度为0和2的结点数及总的结点数分别为n0，n2和n，则n=n0+n2…
（1）
再设二叉树的分支数为B, 除根结点外，每个结点都有一个分支所指，则n=B+1………
（2）
度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此
（2）式可写为
n=2*n2+1……………（3）
由
（1）、（3）得n2=n0-1,代入
（1），并由
（1）和
（2）得B=2*（n0-1）。
证毕。
9．设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列：
ABDFCEGH中序遍历序列：
BFDAGEHC
（1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。
（3）将这棵二叉树转换成对应的树（或森林）。
答案：
略
10.设某二叉树的前序遍历序列为:
ABCDEFGGI，中序遍历序列为:
BCAEDGHFI：
（1）试画出该二叉树；
（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。
（3）设具有四个结点的二叉树的前序遍历序列为ａｂｃｄ；Ｓ为长度等于四的由ａ，ｂ，ｃ，ｄ排列构成的字符序列，若任取Ｓ作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？
试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。
答案：
（1）略
（2）设二叉树的前序遍历序列为P1，P2，…，Pm，中序遍历序列为S1,S2,…，Sm。
因为前序遍历是“根左右”，中序遍历是“左根右”，则前序遍历序列中第一个结点是根结点（P1）。
到中序序列中查询到Si=P1,根据中序遍历时根结点将中序序列分成两部分的原则，有：
若i=1，即S1=P1，则这时的二叉树没有左子树;否则，S1,S2,…,Si-1是左子树的中序遍历序列,用该序列和前序序列P2,P3，…，Pi去构造该二叉树的左子树。
若i=m,即Sm=P1,则这时的二叉树没有右子树;否则,Si+1,Si+2,…，Sm是右子树的中序遍历序列，用该序列和前序序列中Pi+1,Pi+2,…,Pm,去构造该二叉树的右子树。
（3）若前序序列是abcd，并非由这四个字母的任意组合（4!
=24）都能构造出二叉树。
因为以abcd为输入序列，通过栈只能得到1/（n+1）*2n!
/（n!
*n!
）=14种，即以abcd为前序序列的二叉树的数目是14。
任取以abcd作为中序遍历序列，并不全能与前序的abcd序列构成二叉树。
例如：
若取中序列dcab就不能。
该14棵二叉树的形态及中序序列略。
11．用一维数组存放的一棵完全二叉树如下图所示：
A
B
C
D
E
F
G
H
I
J
K
L
写出后序遍历该二叉树时访问结点的顺序。
答案：
HIDJKEBLFGCA
12.已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成？
请简述原因。
答案：
升级会员 