数据结构自测题.docx
《数据结构自测题.docx》由会员分享，可在线阅读，更多相关《数据结构自测题.docx（45页珍藏版）》请在冰点文库上搜索。
数据结构自测题
计算机与信息学院《数据结构》第一、二章自测题
一、选择题
1.计算机算法必须具备输入、输出和（B）等5个特性。
A．可行性、可移植性和可扩充性B．可行性、确定性和有穷性
C．确定性、有穷性和稳定性D．易读性、稳定性和安全性
2.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：
（D）。
A．p->next=s;s->next=p->next;B．p->next=s->next;p->next=s;
C．p->next=s;p->next=s->next;D．s->next=p->next;p->next=s;
3.数据结构在计算机内存中的表示是指（C）
A．数据结构B．数据的逻辑结构
C．数据的存储结构D．数据元素
4.L是一个带头结点的空单向循环链表，若要向L中插入一个由指针p指向的结点，则执行（B）。
A.L=p;p->next=L;B.L->next=p;p->next=L;
C.p->next=L;p=L;D.p->next=L->next;L=p;
5.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（C）最节省时间。
A.单链表B.单循环链表
C.带头结点的双循环链表D.带尾指针的单循环链表
6.在设计存储结构时，通常不仅要存储各数据元素的值，而且还要存储（C）
A.数据的处理方法B.数据元素的类型
C.数据元素之间的关系D.数据的存储方法
7.若要在0
（1）的时间复杂度上，通过两个单向循环链表的头尾相接实现合并，则应对两个循环链表各设置一个指针，分别指向（B）。
A.各自的头结点B.各自的尾结点
C.各自的第一个元素结点。
D.一个表的头结点，另一个表的尾结点
8.从逻辑上来分，数据结构可以分为（C）两大类。
A.动态结构、静态结构B.顺序结构、链式结构
C.线性结构、非线性结构D.初等结构、构造型结构
9.算法分析的两个主要方面是：
（A）
A．空间复杂性和时间复杂性B.正确性和简明性
C．可读性和文档性D.数据复杂性和程序复杂性
10.计算机算法指的是：
（C）
A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法
11.一个顺序表由（a0,a1,a2,…an-1）n个元素构成，a0存储地址是100，每个元素的长度为2，则a4元素的地址是（B）
A.110B.108C.100D.120
12.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（B）个元素。
A.8B.63.5C.63D.7
13.线性表Ｌ在（B）情况下适用于使用链式结构实现。
A.需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入
C.Ｌ中含有大量的结点D.Ｌ中结点结构复杂
14.在一个以h为头的单循环链中，p指针指向链尾的条件是（A）
A.p->next=hB.p->next=NULLC.p->next->next=hD.p->data=-1
15.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）
A．head==NULLB．head→next==NULLC．head→next==headD．head!
=NULL
16.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续或不连续都可以
17.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表
18.与单链表相比，双向链表的优点之一是（D）
A.插入、删除操作更简单B.可以进行随机访问
C.可以省略表头或表尾指针D.访问前后结点更灵活
19.在双向链表中，删除P结点的操作（A）（结点空间释放语句省略）
A.p->prior->next=p->next;p->next->prior=p->prior
B.p->prior=p->prior->prior;p->prior->prior=p;
C.p->next->prior=p;p->next=p->next->next;
D.p->next=p->prior->prior;p->prior=p->prior->prior;
20.在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（C）。
A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;
21.以下说法错误的是（D）。
A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B．顺序存储的线性表可以随机存取
C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D．线性表的链式存储结构优于顺序存储结构
22.若一个算法的时间复杂度用T（n）表示，其中n的含义是（A）
A．问题规模B．语句条数C．循环层数D．函数数量
23.将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（B）
A．O
（1）B．O（m）C．O（n）D．O（m+n）
24.对于三个函数f（n）=2008n3+8n2+96000，g（n）=8n3+8n+2008和h（n）=8888nlogn+3n2，下列陈述中不成立的是（C）
A．f（n）是0（g（n））B．g（n）是0（f（n））C．h（n）是0（nlogn）D．h（n）是0（n2）
25.指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（A）
A．p->next=r；q->next=r->next；r->next=q；
B．p->next=r；r->next=q；q->next=r->next；
C．r->next=q；q->next=r->next；p->next=r；
D．r->next=q；p->next=r；q->next=r->next；
26.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（C）
A.顺序表B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表D.单链表
27.设某线性表有n个元素，以下操作中，（A）在顺序表上实现比在链表上实现效率更高。
A.输出第i个元素（1<=i<=n）B.交换第1个元素和第二个元素的值
C.顺序输出这n个元素的值D.输出与给定值x相等的元素在线性表中的序号
28.算法的时间复杂度是指（B）
A．算法执行的绝对时间
B．随着问题规模n的增大，算法执行时间的增长趋势。
C．算法中执行语句的条数
D．获得算法执行时间的复杂程度。
29.数据结构是指（C）
A．数据的基本单位
B．性质相同的数据元素的集合
C．相互之间存在一种或多种特定关系的数据元素集合
D．描述客观事物且由计算处理的数值、字符等符号的总称
30.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（D）
A.O（n）B.O（m×n）C.O（min（m,n））D.O（max（m,n））
二、填空题
1.程序段i=1;while（i<=n）i=i*3;的时间复杂度为O（log3n）。
2.在长度为n的顺序表的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动n-i+1个元素
3.带头结点的双循环链表L为空表的条件是：
L->prior==L&&L->next==L。
4.以下程序的功能是实现带头结点的单链表数据结点逆序连接，请填空完善之。
voidreverse（LinkListh）//h为头结点指针；
{LinkListp,q;
p=h->next;h->next=NULL;
while（p_______）
{q=p;p=p->next;q->next=h->next;h->next=q________;}
}
5.数据的链式存储结构的特点是借助__指针___表示数据元素之间的逻辑关系。
6.在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是__s->next->next=p->next_和___p->next=s___。
三、判断题（请在你认为正确的后面的括号内打√，错误的打×。
）
1.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（×）
2.顺序存储方式的优点是存储密度大，且插入、删除运算效率高.（×）
3.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻（×）
4.循环链表不是线性表.（×）
5.算法的优劣与算法描述语言无关，但与所用计算机有关。
（×）
6.线性表的特点是每个元素都有一个前驱和一个后继。
（×）
四、算法设计题
1.试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
voiddelete（Linklist&L）
2.将两个递增的有序链表合并为一个递增的有序链表。
要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。
表中不允许有重复的数据。
voidMergeList_L（LinkList&La,LinkList&Lb,LinkList&Lc）
3.已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O（n）、空间复杂度为O
（1）的算法，该算法删除线性表中所有值为item的数据元素。
voidDelete_Sq（SqList&A）
4.已知一个带有表头结点的单链表，结点结构为：
假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第K位置的结点（K为正整数），若查找成功，算法输出该结点data域的值，并返回1，否则只返回0；要求：
（1）简述算法的基本设计思想；
（2）描述算法的详细实现步骤（使用C，或C++实现），关键之处给出详细解释。
5.已知非空线性链表第一个结点的指针为list，请写一个算法，将该链表中数据域值最大的那个结点移到链表的最后面。
6.若已知非空线性链表第一个结点的指针为list，请写一个算法，将该链表中数据域值最小的那个结点移到链表的最前端。
7.已知一个带有表头结点的单链表，头指针为L，请用一个尽可能高效的算法实现，在非头结点p所指元素前，插入元素e,并分析算法的时间复杂度。
8.已知一个带有表头结点的单链表，头指针为L，请用一个尽可能高效的算法实现，删除非头结点p所指元素,并分析算法的时间复杂度。
9.试设计实现在单链表中删去值相同的多余结点的算法。
10.编写算法，判断带头结点的双向循环链表L是否对称。
对称是指：
设各元素值a1,a2,...,an,则有ai=an-i+1，即指：
a1=an，a2=an-1。
。
。
。
。
。
。
结点结构为：
prior
data
next
11.已知带头结点的动态单链表L中的结点是按整数值递增排列，试写一算法将值为X的结点插入链表L中，使L仍然有序。
12.假设线性表采用顺序存储结构，编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。
13.设L为带表头结点的单链表头指针，且表中结点的值均为正整数，试编写算法，实现将表中值最小结点插入到值最大结点之前。
14.设L为一无序的整数单链表。
请设计算法,将链表L分成两个链表,一个用来存放值为奇
数的结点和一个用来存放值为偶数的结点。
15.现有一个逆序排列的数据元素序列,用带头结点的单链表存储,已知头结点的地址存在h中,请设计一个算法,能有效的按正序输出该序列。
16.己知一个数据值为整数的线性表,欲以表中第一个数据元素为参考点,将该表划分为左右两部分,使其参考点左边的每个数据元素值均小于参考点的值,而参考点右边的每个数据元素值均大于参考点的值。
请设计一个求解该问题的有效算法。
17.设有一整数序列由正数、负数组成，编写程序，通过一趟扫描处理，将所有的负数移到正数前面，只能用一个辅助单元。
写出算法思想。
18.设一单链表，结点由整型数据和指针项组成，计算链表中数据只出现1次的结点个数，要求空间复杂度为O
（1）。
编写程序，并写出算法思想。
19.设包含4个数据元素的集合S={"do"，"for"，"repeat"，"while"}，各元素的查
找概率依次为：
p1=0.35，p2=0.15，p3=0.15，p4=0.35。
将S保存在一个长度为4的顺序表中，采用折半查找法，查找成功时的平均查找长度为2.2。
请回答：
（1）若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应如何排列？
应使用
何种查找方法？
查找成功时的平均查找长度是多少？
（2）若采用链式存储结构保存S，且要求平均查找长度更短，则元素应如何排列？
应使用
何种查找方法？
查找成功时的平均查找长度是多少？
20.已知一个整数序列A=（a0,a1,…，an-1），其中0≤ai＜n（0≤i＜n）。
若存在ap=ap2=…=apm=x且m＞n/2（0≤pk例如A=（0，5，5，3，5，7，5，5），则5为主元素；又如A=（0，5，5，3，5，1，5，7），则A中没有主元素。
假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。
若存在主元素，则输出该元素；否则输出-1。
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
【解答】
（1）给出算法的基本设计思想：
（4分）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的Num。
然后重新计数，确认NumNum是否主元素。
算法可分为以下两步：
①选取候的主元素：
依次扫描所给数组中的每个整，将第一遇到Num保存到c中，记录Num的出现次数为的出现次数为1；若遇到的下一个整数仍等于NumNum，则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存c中，计数重新记为中，计数重新记为1，开始新一轮计数，即从当前位置重复上述过程直到扫描完全部组元素。
②判断c中元素是否真正的主中元素是否真正的主：
再次扫描该数组，统计c中元素出现的次数，若中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。
（2）算法实现：
（7分）
intMajority（intA[],intn）
{
inti,c,count=1;//c用来保存候选主元素，count用来计数
c=A[0];//设置A[0]为候选主元素
for（i=1;iif（A[i]==c）
count++;//对A中的候选主元素计数
else
if（count>0）//处理不是候选主元素的情况
count--;
else//更换候选主元素，重新计数
{c=A[i];
count=1;
}
if（count>0）
for（i=count=0;iif（A[i]==c）
count++;
if（count>n/2）returnc;//确认候选主元素
elsereturn-1;//不存在主元素
}
五、解答题
1.试写出将S结点插入到双向链表P结点之前的语句序列，结点结构为：
prior
data
next
计算机与信息学院《数据结构》第三、六章自测题
一、选择题
1.对于栈操作数据的原则是（B）。
A.先进先出B.后进先出C.后进后出D.不分顺序
2.设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。
A.51234B.45132C.43125D.32154
3.一个递归算法必须包括（B）。
A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分
4.设计一个判别表达式中左，右括号是否配对出现的算法，采用（D）数据结构最佳。
A．线性表的顺序存储结构B.队列
C.线性表的链式存储结构D.栈
5.用带头结点的单链表存储队列时，在进行删除运算时（B）。
A.仅修改头指针B.可能要修改尾指针
C.头、尾指针都要修改D.头、尾指针可能都要修改
6.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时（D）。
A．仅修改队头指针B.仅修改队尾指针
C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改
7.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（A）。
A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front
8.栈和队列的共同点是（C）。
A.都是先进先出B.都是先进后出
C.只允许在端点处插入和删除元素D.没有共同点
9.栈的插入和删除操作在（A）进行。
A．栈顶B．栈底C．任意位置D．指定位置
10.元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（B）
A.3B.4C.5D.6
11.已知循环队列存储在一维数组A[0..n-l]中，且队列非空时，front和rear分别指向队头元素和队尾元素。
若初始时队列为空，且要求第l个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（B）
A.0,0B.0,n-1C.n-l,0D.n-1,n-1
12.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。
若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是（C）
A.1B.2C.3D.4
13.若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到的出栈序列是（D）
A.d,c,e,b,f,aB.c,b,d,a,e,f
C.b,c,a,e,f,dD.a,f,e,d,c,b
14.某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是（C）
A.b,a,c,d,eB.d,b,a,c,eC.d,b,c,a,eD.e,c,b,a,d
15.若用一个大小为6的数组来实现循环队列，且当前的rear和front的值分别为0和3，当从队列中删除一个元素，再插入两个元素后，rear和front的值分别为（B）。
A.1，5B.2，4C.4，2D.5，1
16.最不适合用作链队的链表（A）
A．只带队头指针的非循环双链表B．只带队头指针的循环双链表
C．只带队尾指针的循环双链表D．只带队尾指针的循环单链表
17.假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（B）
A．3B．37C．50D．97
18.数组A[1…5，l…6]的每个元素占4个字节，将其按行优先次序存储在起始地址为1000的内存单元中，则元素A[4，4]的地址是（D）
A.1175B.1180C.1088D.1084
19.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为（C）
A．前序遍历B．后序遍历C.中序遍历D.层次遍历
20.在一棵高度为k的满二叉树中，结点总数为（C）
A．2k-1B．2kC．2k-1D．log2k+1
21.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（C）。
A．iB．n-iC．n-i+1D．不确定
22.链式栈结点为：
（data,link），top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（A）。
A．x=top->data;top=top->link；B．top=top->link;x=top->link；
C．x=top;top=top->link；D．x=top->link；
23.循环队列存储在数组A[0...m]中，则入队时的操作为（D）。
A.rear=rear+1B.rear=（rear+1）%（m-1）
C.rear=（rear+1）%mD.rear=（rear+1）%（m+1）
24.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（C）遍历实现编号。
A．先序B.中序C.后序D.从根开始按层次遍历
25.若一棵二叉树的前序遍历序列和后序遍历序列分别是1，2，3，4和4，3，2，1，同该二叉树的中序遍历列不会是（C）
A．1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1
26.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（B）
I．父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系
A.只有IIB.I和IIC.I和IIID.I、II和III
27.已知一棵有2011个结点的树，其叶结点的个数为1
升级会员 