数据结构复习题docx.docx
- 文档编号:9897202
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:27
- 大小:202.21KB
数据结构复习题docx.docx
《数据结构复习题docx.docx》由会员分享,可在线阅读,更多相关《数据结构复习题docx.docx(27页珍藏版)》请在冰点文库上搜索。
数据结构复习题docx
*注:
数据结构测试无答案,前三章为新题型,题号前加粗加下划线的冇答案,其余的没有答案,后面几章为1口题,都何答案,复习主要就是看书、看实验题、做题,书上的
代码得好好看。
数据结构测试
1.选择题(每题2分,共30分)
1.在数据结构中,从逻辑上可以把数据结构分成()
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
2.算法分析的冃的是()
A.给出数据结构的合理性
B.研究算法屮的输入和输出关系
C.分析算法的效率以求改进
D.分析算法的易懂性和健壮性
3.线性表中各元素之间的关系是()关系。
A.层次B.网状
C.有序D.集合
4.非空的循环单链表head的尾结点p满足()*
A・p->next==NULL
B•p->next==head
C.p==NULL
D.p==head
5.设单链表中指针p指向结点m,若要删除m之后的结点(若存在),则需修改指针的操
作为()
A・p->next=p->next->next;
B.p=p->next;
C•p=p->next->next;
D.p->next=p;
6.某线性表最常用的操作是在最后一个元索Z后插入一个元素和删除第一个元索,则采用()存储方式最节省运算吋间。
A.单链表B.仅有头指针的单循环链表
C.双链表D.仅冇尾指针的单循环链表
7•栈和队列都是()
A.顺序存储的线性结构
B.限定存取的线性结构
C.链接存収的线性结构
D.限定存储的非线性结构
8.一个栈的入栈序列是a,b,c,d,e,贝IJ栈的不可能的输出序列是()
A.edcbaB.decba
C.dceabD.abcde
9.具有n个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针,
则判断队满的条件为()
A.rear%n==frontB.front+l=rearC.rear==frontD.(rear+l)%n=front
10.两个字符串相等的条件是()
A.两串的长度相等B.两串包含的字符相同
C.两串的长度相等,并且两串包含的字符相同
D.两串的长度相等,并且对应位置上的字符相同
11.在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,则度为0的结点数为()个。
A.4B.5C.6D.7
12.设森林F对应的二义树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林
F中第一棵树的结点个数是()
A.m-nB.m-n-1C.n+1D.条件不足,无法确定
13.若下面几个符号串编码集合中,不是前缀编码的是()。
A.{0,10,110,1111}B.{11,10,001,101,0001}
C.{00,010,0110,1000}D・{b,c,aa,ac,aba,abb,abc}
14.引入二叉线索树的冃的是()
A.加快查找结点的前驱或后继的速度
B.为了能在二叉树中方便的进行插入与删除
C.为了能方便的找到双亲
D.使二叉树的遍历结果唯一
15.n个结点的线索二叉树上含有的线索数为()
A.2nB.n—1C.n+lD.n
2.填空题(每空1分,共5分)
1.一个线性表常进行存取操作,很少进行插入和删除操作时,则采用存储结构为宜。
相反,当经常进行的是插入和删除操作时,则采用存储结构为宜。
2.栈顶的位置是随着运算而变化的。
3.已知--棵哈夫曼树含有60个叶子结点,则该树小共有个非叶子结点。
4.高为h(h>0)的满二义树对应森林的山棵树构成。
3.判断题:
在你认为正确的题后()中填写T,错误的填写F(每题1分,共5分)
1.数据的逻辑结构是指数据的各数据项Z间的逻辑关系。
()
2.顺序存储方式只能用于存储线性结构。
()
3.线性表的顺序存储结构的优点是存储密度大,且插入、删除运算效率高。
()
4.将一棵树转换为二叉树后,根结点没有左子树。
()
5.完全二义树中,若一个结点没有左孩子,则必是叶结点。
()
4.简答题(每题2分,共4分)
1.简述下列算法的功能,并给出队列Q={12,34,25,4,8}在执行下列算法后的状态。
voidunknows(SqQueue&Q)
{
SqStackS;
intk;
Initstack(S);
while(Jqueueempty(Q))
{
Dequeue(Q,k);
Push(S,k);
}
while(!
stackempty(S))
{
Pop(S,k);
Enqueue(Q,k);
}
}
功能:
队列Q的值:
2.假设以二叉链表表示二叉树,其类型定义如下:
typedefstructnode{
DataTypedata;
}*BinTree;
阅读下列算法,并冋答问题:
1己知以T为根指针的二叉树如图所示,写出执行Demo2(T)Z后的返回值;
2简述算法Demo2的功能。
intDemo2(BinTreeT)
{
intd;
if(!
T)return0;
d=Demo2(T・>lchild)+Demo2(T・>rchild);
if(T・>lchild&&T・>rchild)
returnd+1;
else
returnd;
}
1返回值:
2功能:
5.算法题(每题3分,共6分)
1.设计一个算法,判断链表中数据元素是否是递减的。
2.设某棵二叉树采用二叉链表作为存储,编写一递归算法求其叶结点数。
第一章绪论
1.选择题
1.下面关于算法说法正确的是()o
A.算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C.算法的可行性是指指令不能有二义性
D.以上几个都是错误的
2.以下哪一个术语与数据的存储结构无关?
()
A.栈B.哈希表C.线索树D.循环队列
3.算法复杂度通常是表达算法在最坏情况下所需要的计算量,0
(1)的含义是()。
C.算法执行常数步就完成D.算法执行可变步数就完成
4.数据结构研究的内容是()。
A.数据的逻辑结构B.数据的存储结构
C.建立在相应逻辑结构和存储结构上的算法D.包括以上三个方而
5.一•个正确的算法应该具有5个特性,除输入、输出特性外,另外3个特性是()。
A.确定性、可行性、有穷性B.易读性、确定性、有效性
C.有穷性、稳定性、确定性D.可行性、易读性、有穷性
6.以下关于数据的逻辑结构的叙述屮正确的是()。
A.数据的逻辑结构是数据间关系的描述
B.数据的逻辑结构反映了数据在计算机中的存储方式
C.数据的逻辑结构分为顺序结构和链式结构
D.数据的逻辑结构分为静态结构和动态结构
7.
D・0(()
B.问题的规模
D•问题的规模和待处理数据的初态
下列时间复杂度中最坏的是()
A.0
(1)B.O(n)C.O(log2n)
8.算法的时I可复杂度取决于()。
A.待处理数据的初态
C.程序本身所占的空间
9.下面说法不正确的是()。
A.算法原地工作的含义是指不需要任何额外的辅助空间
B.在相同规模n下,复杂度0(n)的算法在时间上总是优于复杂度0(2》的算法
C.所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
D.同-•个算法,实现语言的级别越高,执行效率就越低
10.在存储数据时,通常不仅要存储各数据元素的值,述要存储()。
A.数据的操作方法B.数据元素的类型
C.数据元索之间的关系D.数据的存取方法
11.下列关于数据结构的说法中,正确的是()0
A.数据的逻辑结构独立于其存储结构
B.数据的存储结构独立于其逻辑结构
C.数据的逻辑结构唯一决定了其存储结构
D.数据结构仅由其逻辑结构和存储结构决左
12.nJ*以用()定义一个完整的数据结构
A.数据元素B.数据对象
C.数据关系D.抽象数据类型
13.某算法的时间复杂度为0((),表明该算法的()
A.问题规模是『B.执行的时间等于『
C.执行时间与『成正比D.问题的规模M『成正比
2.综合应用题
〔有卜-列运行时间歯数:
(1)fl(n)=l()()();
(2)f2(n)=n2+1000n;(3)f3(n)=3n3+100n2+n+l;
分别写出相应的大0表示的运算时间。
2.下面函数mergesort执彳亍的吋间复朵度为多少?
假设函数调用为mergesort(1,n),merge函数时间复杂度为0(n)
voidmergesort(inti,intj)
intm;if(i!
=j)
m=(i+j)/2;
mergesort(i,m);
mergesort(m+1zj);
merge(i,j,m);//本函数时间复杂度为0(n)
}
}
3.对于两种不同的数据结构,逻辑结构或物理结构一定不相同吗?
4.试举一例,说明对相同的逻辑结构,同一种运算在不同的存储方式下实现,其运算效率不同。
第二章线性表
1.选择题
[.下述哪一条是顺序存储结构的优点?
()
A.存储密度大B.插入运算方便
C.删除运算方便D.可方便地用于各种逻辑结构的存储表示
2.下面关于线性表的叙述中,错误的是哪一个?
()
A.线性表采用顺序存储,必须占用一片连续的存储单元。
B.
线性表采用顺序存储,便于进行插入和删除操作。
3.若某线性表授常丿IJ的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则
利用O存储方式最节省时间。
A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表
4.某线性表小最常用的操作是在最后一个元索之后插入一个元素和删除第一个元索,则采用O存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表
5.在一个长度为n的顺序表屮删除第i个元素(l<=i<=n)时,需向前移动()个元素
A.n-iB.n-i+lC.n-i-1D.i
6.
从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较()个元素结点
7.设单链表中指针p指向结点m,若要删除mZ后的结点(若存在),则需修改指针的操作为()
A•p->next=p->next->next;B.p=p->next;
C・p=p->next->next;D・p->next=p;
8.在一个单链表屮,己知q结点是p结点的前趋结点,若在q和p之间插入s结点,贝IJ须执行()
A•s->ncxt=p->ncxt;p->ncxt=s
B•q->next=s;s->next=p
C•p->ncxt=s->ncxt;s->ncxt=p
D•p->next=s;s->next=q
9.线性表的顺序存储结构是一种()的存储结构。
A.随机存取B.顺序存取C.索引存取D.散列存取
1().设线性表屮有2n个元素,()在单链表上实现要比在顺序表上实现效率更高。
A.删除所有值为x的元索
B.在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换第i个元素和第2n・i・l个元素的值(i=O,...,n-l)
11・静态链表屮指创•表示的是()
A.下一个元索的地址B.内存储器地址
C.下一个元素在数组中的位置
D.左链或右链指向的元素的地址
12.需要分配较人的空间,插入和删除不需要移动元素的线性表,具存储结构为()
A.单链表B.静态链表
C.顺序表D.双链表
二.算法设计
1.设有一个正整数序列组成的有序单链表(按递增次序有序,且允许有相等的整数存在),试编写能实现下列功能的算法(要求用最少的时间和最小的空间)
1确定在序列中比正整数x大的数冇儿个(相同的数只计算一次)
2将单链表中比正整数x小的偶数从单链表屮删除
2.
设有一个表头指针为h的单链表。
试设计一个算法,通过遍历--趟链表,将链表小所有结点的链接方向逆转,如下图所示。
要求逆转结果链表的表头指针h指向原链表的最后一个结点。
3.设计算法将一个带头结点的单链表A分解为两个貝有和同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值人于零的结点(链表A的元索类型为整型,要求B、C表利用A表的结点)。
4.假设链表A、B分别表示一个集合,试设计算法以判断集合A是否是集合B的子集,若是,则返冋1,否则返冋0,并分析算法的吋间复杂度。
5.设冇一单循环链表la,其结点冇三个域:
priordata与next,其中data为数据域,,next域指向直接后继,prior域应指向直接前驱,但H前空着。
试写一算法将此单循坏链表改造为双向循环链表。
6.设顺序表用数组A[]表示,表中元索存储在数组下标1〜m+n的范围内,前m个元索递增有序,后n个元素递增有序,设计一个算法,使得整个顺序表有序。
(1)给岀算法的基本设计思想。
(2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
7.冇一个带头结点的单链表L,设计一个算法使其元索递增冇序。
第三章栈和队列
一.选择题
1.已知栈的最人容量为4。
若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为()
A.5,4,3,2,1,6B.2,3,5,6,1,4
C.3,2,5,4,1,6D.1,4,6,5,2,3
2.在一个具有n个单元的顺序栈中,假定以地址低端(即0单元)作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为()
A.top不变B.top=0C.top—D.top++
3.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针,则判断队满的条件为()
A.rear%n==frontB.(front+l)%n==rear
C.rear%n-1==frontD・(rcar+1)%n==front
4.在具冇n个单元的顺序存储的循环队列中,假定front和rc如分别为队头指针和队尾指针,则判断队空的条件为()
A.rear%n==frontB.front+l=rear
C.rear==frontD.(rear+l)%n=front
5.在一个链队列屮,假定front和zi•分别为队首和队尾指针,则删除一个结点的操作为()
A.front二front->nextB.rear=rear->next
C.rear=front->nextD.front=rear->next
6.某堆栈的输入序列为1,2,3,…,n,输出序列的笫一个元素是n,则笫i个输出元素为()。
A.iB.n-iC.n-i+1D.哪个元素无所谓
7.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时()0
A.仅修改队头指针B.仅修改队尾指针
C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改
8.最适合用做链队列的链表(链表有头结点,有队首指针则指向头结点,有队尾指针则指向终端结点)是()。
A.只带队首指针的循环单链表。
B.只带队尾指针的循环单链表。
C.只带队首指针的非循坏单链表。
D.只带队尾指针的非循环单链表。
9.最不适合用做队列的链表是()0
A.只带队首指针的非循环双链表。
B.只带队首指针的循环双链表。
C.只带队尾指针的循坏双链表。
D.只带队尾指件的循环单链表。
10.设链表不带头结点且所有操作均在衣头进行,则下列最不合适作为链栈的是()o
A.只有表头结点指针,没有表尾指针的双向循环链表。
B.只冇表头结点指针,没冇表尾指针的循环链表。
C.只有表头结点指针,没有表尾指针的单向循环链表。
D.只有表头结点指针,没有表尾指针的单向链表。
11.一个栈的入栈序列为1,2,3,…,n,其出栈序列是pl,p2,p3,...,pn。
若p2=3,贝ljp3可能取值的个数是()。
A.n-3
B.n-2
C.n-1
D.无法确定
12.设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S。
若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfcag,则栈S的容虽至少是()。
A.1
B.2
C.3
D.4
13.栈的应用不包括()o
A.递归。
B.进制转换。
C.迷宫求解。
D.缓冲区。
2.填空题
1.线性表、栈和队列都是结构。
线性表可以在插入和删除元索;栈只能在插入和删除元索;队列只能在插入元素和删除元素。
2.假设以S和X分别表示进栈和退栈运算,则对输入序列a,b,c,d,c进行一系列栈运算SSXSXSSXXX之后,得到的输出序列为。
3.设栈S和队列Q的初始状态为空,元素a,b,c,d,e,f依次通过栈S,—个元素出栈后即进入队列Q。
若这6个元素出队列的顺序是b,d,c,f,e,a,则栈S的容量至少应该是。
3.解答题
丄•一个双向栈S是在同一向量空间内实现的两个栈,它们的栈底分别设在向量空间的两端。
试为此双向栈设计初始化InitStack(S)>入栈Push(S,i,x)和出栈Pop(S,i)等算法,其中i为0或1,用以表示栈号。
2.利用两个栈SI、S2模拟一个队列时,如何使用栈的运输实现队列的插入、删除运算。
3.简述下列算法的功能,并给出队列Q={12,34,25,4,8}在执行下列算法后的状态。
voidunknows(SqQucuc&Q)
{
SqStackS;
intk;
Initstack(S);
whilc(!
qucuccmpty(Q))
Dequeue(Q,k);
Push(S,k);
while(!
stackempty(S))
{
Pop(S,k);
Enqueue(Q,k);
}
}
功能:
队列Q的值:
4.Q是一个队列,S是一个空栈,实现将队列小的元素逆置的算法。
5.设单链表的表头指针为h,结点结构由data和next两个域构成,其中data域为字符型,试设计算法判断该链表的前n个字符是否是中心对称。
例如xyx、xyyx都是中心对称。
第四章串
1.选择题
1.若串S-software;其子串的数目是()
A.8B.37C.36D.9
2.设有两个串p和q,求q在p屮首次出现的位宜的运算称作()
A.连接B.模式匹配C.求串长D.求子串
3.设字符串S1="ABCDEFG'',S2二“PQRST",则运算:
S=CONCAT(SUBSTR(SI,2,LEN(S2));SUBSTR(SI,LEN(S2),2));后的串值为()
A.ABCDEFB.BCDEFGC.BCDPQRSTD.BCDEFEF
4.下而的说法中,只有()是正确的
A.串是一种特殊的线性表B.串的长度必须大于零
C.串中元素只能是字母D.空串就是空白串
5.两个字符串相等的条件是()
A.两串的长度相等
B.两串包含的字符相同
C.两串的长度相等,并且两串包含的字符相同
D.两串的长度相等,并且对应位置上的字符相同
2.填空题
1.串"ababcbaababd”的next函数值为,nextval函数值为。
2.子串的长度为。
第五章数组和广义表
一.选择题
1.设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到1(),数
组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为()A.BA+141B.BA+180C.BA+222D.BA+225
2.假设以行序为主序存储二维数组A=array[1..100,1..100J,设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=()
A.808B.818C.1010D.1020
3.对稀疏短阵进行压缩存储II的是O
A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的吋间复
杂度
则与如图所示三元组表对应的4X5的稀疏矩阵是(注:
二.解答题
已知一个6行5列的稀疏矩阵中非零元的值分别为:
・90,41,・76,28,-54,65,-8,它们在矩阵中的列号依次为:
1,4,5,1,2,4,5o当以带行表的三元纽表作存储结构时,其行表中的值依次为(),0,2,2,3,5(行列下标均从1开始),写出该稀疏矩阵。
第六章树和二叉树
一.选择题
1.如果在数据结构中每个数据元素只可能有一个直接前驱,但可以有多个直接后继,则该结构是()
A.栈B.队列C.树D.图
2.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数为()
A.5B.6C.7D.8
3.已知一棵含50个结点的二叉树中只有一个叶子结点,则该树中度为1的结点个数为()
A.OB.1C.48D.49
4.树的先根序列等同于与该树对应的二叉树的()
A.先序序列B.中序序列C.后序序列D.层序序列
5.用二叉链表表示具有n个结点的二叉树时,值为空的指针域的个数为()
A.n-1B.nC.n+1D・2n
6.设森林F对应的二叉树为B,它冇m个结点,B的根为p,p的右了树结点个数为n,森林F屮第一棵树的结点个数是()
A.m-nB.m-n-1C.n+1D.条件不足,无法确定
7.设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子数为()
A.5B.6C.7D.8
8.设森林F中有三棵树,笫一,笫二,第三棵树的结点个数分别为Ml,M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是()
A.MlB・M1+M2C.M3D.M2+M3
9.一棵完全二叉树上有10()1个结点,其屮叶了结点的个数是()
A.250B.500C.254D.505E.以上答案都不对
10.有n个叶子的哈夫曼树的结点总数为()
A.不确定B.2nC.2n+lD.2n-l
11.-•棵二义树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有()结点
A.2h
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习题 docx