数据结构考试题1

数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C ）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。

2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。

A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。

A s→link = p→link; p→link = s;B p→link = s; s→link = q;C p→link = s→link; s→link = p;D q→link = s; s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。

A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。

A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。

所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。

A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。

A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。

10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。

A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（ A ）的表示等价。

数据结构练习试卷1(题后含答案及解析)题型有：1. 选择题选择题（每小题1分，共75分）下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将此选项涂写在答题卡相应位置上，答在试卷上不得分。

1．数据结构主要研究数据的______。

A．逻辑结构B．存储结构C．逻辑结构和存储结构D．逻辑结构和存储结构及其运算的实现正确答案：D解析：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构一般包括三方面的内容：①数据之间的逻辑关系。

从逻辑关系上描述数据，与数据的存储无关。

②数据的存储结构。

存储结构分为顺序结构和链式结构，是逻辑结构在计算机存储器中的表示，它包括数据元素的表示和关系的表示。

③数据的运算。

也就是在数据上所施加的一系列操作。

只考虑操作的功能是怎样的，暂不考虑如何实现。

综上所述，本题的正确答案为选项D。

知识模块：数据结构2．在数据结构中，结点(数据元素)及结点间的相互关系组成数据的逻辑结构。

按逻辑结构的不同，数据结构通常可分为______两类。

A．线性结构和非线性结构B．紧凑结构和稀疏结构C．动态结构和静态结构D．内部结构和外部结构正确答案：A解析：在数据结构中，结点(数据元素)及结点间的相互关系组成数据的逻辑结构。

按逻辑结构的不同，数据结构通常可分为线性结构和非线性结构两类。

本题正确答案为选项A。

知识模块：数据结构3．下面叙述不正确的是______。

A．算法的执行效率与数据的存储结构有关B．算法的空间复杂度是指执行这个算法所需要的内存空间C．算法的有穷性是指算法必须能在执行有限个步骤之后终止D．算法的时间复杂度是指执行这个算法所需要的时间正确答案：D解析：算法的时间复杂度是指执行算法所需要的计算工作量，故D选项不正确。

知识模块：数据结构4．数据的存储结构是指______。

A．数据所占的存储空间量B．数据的逻辑结构在计算机中的表示C．数据在计算机中的顺序存储方式D．存储在外存中的数据正确答案：B解析：数据的存储结构是数据元素在计算机存储器内的表示。

要求：所有的题目的解答均写在答题纸上,需写清楚题目的序号.每张答题纸都要写上姓名和学号.一、单项选择题(每小题1。

5分，共计30分）1。

数据结构是指。

A。

一种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合2. 以下算法的时间复杂度为。

void fun(int n）{ int i=1;while （i<=n)i++；}A. O（n)B. O（n)C. O(nlog2n）D。

O（log2n)3. 在一个长度为n的有序顺序表中删除元素值为x的元素时,在查找元素x时采用二分查找,此时的时间复杂度为。

A。

O（n） B. O（nlog2n）C。

O(n2） D. O(n)4. 在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为.A. O（n）B。

O（n)C. O（nlog2n）D。

O(n2)5。

若一个栈采用数组s[0。

.n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是。

A。

top++；s[top]=x； B.s[top］=x;top++；C.top-—；s［top]=x；B。

s[top］=x；top—-;6。

中缀表达式“2＊（3+4）—1”的后缀表达式是,其中＃表示一个数值的结束.A. 2#3＃4#1#*+—B. 2＃3#4＃+＊1#—C. 2#3＃4＃＊+1#—D. —+*2#3#4＃1＃7。

设环形队列中数组的下标为0~N-1，其队头、队尾指针分别为front和rear（front 指向队列中队头元素的前一个位置，rear指向队尾元素的位置）,则其元素个数为。

A。

rear-front B。

rear-front—1C. (rear—front)%N+1 D。

（rear—front+N）％N8。

若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置,队尾指针rear指向队尾元素的位置。

数据结构练习题1、在数据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构B、紧凑结构和非紧凑结构B、线性结构和非线性结构D、内部结构和外部结构2、线性表的顺序存储结构是一种_____的结构，线性表的链式存储结构是一种____的存储结构A、随机存取B、顺序存取C、索引存储D、散列存取3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址____A、必须是连续的B、部分地址必须是连续的B、一定是不连续的D、连续或不连续都可以4、在下列叙述中，正确的是____A、线性表的顺序存储结构优于链表存储结构B、二维数组是其数据元素为线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出5、一个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是___A、110B、108C、100D、1206、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是____A、edcbaB、decbaC、dceabD、abcde7、一个栈的入队序列是1，2，3，4，则队列的输出序列是____A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，18、判定一个栈ST空的(最多元素为m0)为空的条件是_____A、ST->top!=0B、ST->top= =0C、S T->top!=m0D、ST->top= =m09、判定一个栈(最多元素为m0)为满的条件是_____A、ST->top!=0B、ST->top= =0D、ST->top!=m0 D、ST->top= =m010、判定一个队列QU(最多元素为m0)为空的条件是_____A、QU->rear-QU->front= =m0B、Q U->rear-QU->front-1= =m0C、Q U->front= =QU->rearD、QU->front= =QU->rear+111、判定一个队列QU(最多元素为m0)为空的条件是_____A、QU->rear-QU->front= =m0B、QU->rear-QU->front-1= =m0C、QU->front= =QU->rearD、QU->front= =QU->rear+112、判定一个循环队列QU(最多元素为m0)为空的条件是_____A、QU->rear-QU->front= =m0B、QU->rear-QU->front-1= =m0C、QU->front= =（QU->rear+1）%m0D、QU->front! =（QU->rear+1）%m013、判定一个循环队列QU(最多元素为m0)为满的条件是_____A 、QU->rear -QU->front= =m0B 、QU->rear -QU->front -1= =m0C 、QU->front= =（QU->rear+1）%m0D 、QU->front! =（QU->rear+1）%m014、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front 和rear ，则当前队列中的元素个数是_____A 、（rear -front+m ）%mB 、rear -front+1C 、rear -front-1E 、 rear -front15、如下图所示的4棵二叉树中，____不是完全二叉树。

数据结构试卷一一、选择题20分1．组成数据的基本单位是 ;A 数据项B 数据类型C 数据元素D 数据变量2．设数据结构A=D,R,其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A 是 ;A 线性结构B 树型结构C 图型结构D 集合3．数组的逻辑结构不同于下列的逻辑结构;A 线性表B 栈C 队列D 树4．二叉树中第ii≥1层上的结点数最多有个;A 2iB 2iC 2i-1D 2i-15．设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为 ;A p->next=p->next->nextB p=p->nextC p=p->next->nextD p->next=p6．设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是 ;A 6B 4C 3D 27．将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为 ;A 100B 40C 55D 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为 ;A 3B 4C 5D 19．根据二叉树的定义可知二叉树共有种不同的形态;A 4B 5C 6D 710.设有以下四种排序方法,则的空间复杂度最大;A 冒泡排序B 快速排序C 堆排序D 希尔排序二、填空题30分1.设顺序循环队列Q0：m-1的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元素的前一个位置,队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =____________;;2.设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为___________,在链式存储结构上实现顺序查找的平均时间复杂度为___________;3.设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有________个指针域,__________个空指针域;4.设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点B的操作序列为______________________________________;5.设无向图G中有n个顶点和e条边,则其对应的邻接表中有_________个表头结点和_________个表结点;6.设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有______关系;7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为__________;8.设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1开始顺序编号,则编号为8的双亲结点的编号是___________,编号为8的左孩子结点的编号是_____________;9.下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句;int indexchar s , char t{i=j=0;whilei<strlens && j<strlent ifsi==tj{i=i+l; j=j+l;}else{i=_______; j=______;}if j==strlentreturni-strlent;else return -1;}10.设一个连通图G中有n个顶点e条边,则其最小生成树上有________条边;三、应用题30分1．设完全二叉树的顺序存储结构中存储数据ABCDE,要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列;2．设给定一个权值集合W=3,5,7,9,11,要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL;3．设一组初始记录关键字序列为19,21,16,5,18,23,要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果;4．设一组初始记录关键字集合为25,10,8,27,32,68,散列表的长度为8,散列函数Hk=k mod 7,要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表;5．设无向图G所右图所示,要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树;四、算法设计题20分1.设计判断单链表中结点是否关于中心对称算法;2.设计在链式存储结构上建立一棵二叉树的算法;3.设计判断一棵二叉树是否是二叉排序树的算法;数据结构试卷一参考答案一、选择题二、填空题1. F+1 % m2. On,On3. 2n,n+14. s->next=p->next; s->next=s5. n, 2e6. m=2e7. CBA8. 4,169. i-j+1,010. n-1三、应用题1. 链式存储结构略,前序ABDEC,中序DBEAC,后序DEBCA;2. 哈夫曼树略,WPL=783. 18,5,16,19,21,23,5,16,21,19,18,234. 线性探测：6827322510876543210ΛΛ 链地址法：276832251086543210>->->->->->-h h h h h h h 5. 深度：125364,广度：123456,最小生成树T 的边集为E={1,4,1,3,3,5,5,6,5,6}四、算法设计题1. 设计判断单链表中结点是否关于中心对称算法;typedef struct {int s100; int top;} sqstack;int lklistsymmetrylklist head{sqstack stack; = -1; lklist p;forp=head;p=0;p=p->next {++; =p->data;}forp=head;p=0;p=p->next if p->data== =; else return0;return1;}2. 设计在链式存储结构上建立一棵二叉树的算法;typedef char datatype;typedef struct node {datatype data; struct node lchild,rchild;} bitree;void createbitreebitree &bt{char ch; scanf"%c",&ch;ifch=='' {bt=0; return;}bt=bitreemallocsizeofbitree; bt->data=ch;createbitreebt->lchild; createbitreebt->rchild;}3.设计判断一棵二叉树是否是二叉排序树的算法;int minnum=-32768,flag=1;typedef struct node{int key; struct node lchild,rchild;}bitree;void inorderbitree bt{if bt=0{inorderbt->lchild; ifminnum>bt->keyflag=0; minnum=bt->key; inorderbt->rchild;} }。

《数据结构》练习题一、选择题1．一个数组元素a[i]与（ A ）的表示等价。

A ．*（a+i ） B ．a+i C ．*a+i D ．&a+ia 是存储的是数组首地址，*a 指向的就是数组第一个元素a[0],所以*（a+i ）的地址和a[i]的地址一样。

数组和指针在一定程度上本质是一样的。

2．当利用大小为N 的数组顺序存储一个栈时，假定用top==N 表示栈空，则退栈时，修改top 指针的语句是（ A ）。

A ．top++;B ．top=0;C ．top--;D ．top=N; 3．队列的删除操作是在（ A ）进行。

A ．队首B ．队尾C ．队前D ．队后队列删除元素是在队首进行，队列是进先先出，相对来说，队首元素是最先进入队列的，因此出队应该是在队首进行。

队列其实就和我们平时排队一样的4．二叉树上叶子结点数等于（ C ）。

A ．分支结点数加1B ．单分支结点数加1C ．双分支结点数加1D ．双分支结点数减15．哈希冲突是指（ D ）。

A ．两个元素具有相同的序号B ．两个元素的键值不同，而其他属性相同C ．数据元素太多D ．不同键值的元素对应于相同的存储地址6．由权值分别为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ A ）。

A ．51B ．23C ．53D ．742310 135 56 72 3(2+3)*3+5*2+(6+7)*2=517．某程序的时间复杂度为)log log 1003(22n n n n +⨯+，其数量级表示为（ B ）。

A ．O(n)B ．)log (2n n OC ．O(100)D ．)(log 2n O8．从二叉搜索树中查找一个元素时，其时间复杂度大致为（ C ）。

A ．O(n)B ．O(1)C ．)(log 2n OD ．)(2n O9．在线性表的散列存储中，若用m 表示散列表的长度，n 表示待散列存储的元素的个数，则装填因子α等于（ A ）。

数据结构练习题1⼀、单项选择题1.若⽤⼀个⼤⼩为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除⼀个元素，再加⼊两个元素后，rear和front的值分别为多少？( )A. 1和 5B. 2和4C. 4和2D. 5和1⼤⼩为6的数组：下标从0-5;从前⾯出队，从后⾯⼊队front(前⾯)=3rear(后⾯)=0当出队列中删除⼀个元素，也就是出队，即front+1:=4再插⼊两个元素，即rear+2= 2【注】循环队列中，由于⼊队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。

因此，⽆法通过条件front==rear来判别队列是"空"还是"满"。

2.循环队列A[0..m-1]存放其元素值，⽤front和rear分别表⽰队头和队尾，则当前队列中的元素数是( )。

A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front3.for（i=0；ifor（j=0；jA［i］［j］=i*j；上⾯算法的时间复杂度为( )A.O(m2)B.O(n2)C.O(m×n)D.O(m+n）4.设h是指向⾮空带表头结点的循环链表的头指针，p是辅助指针。

执⾏程序段p=h;while (p->next->next!=h)p=p->next;p->next=h;后（其中，p->next为p指向结点的指针域），则( )A. p->next指针指向链尾结点B. h指向链尾结点C. 删除链尾前⾯的结点D. 删除链尾结点5.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）A.head= =NULLB.head–>next= =NULLC.head!=NULLD.head–>next= =head6. 设顺序表有19个元素，第⼀个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )A.236B.239C.242D.2457. 若⼀棵⼆叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A ．9B ．11C ．15D ．不确定8. n 个结点的线索⼆叉树上含有的线索数为（）A ．2nB ．n －lC ．n ＋lD ．n9. 设有⼀个栈，按A 、B 、C 、D 的顺序进栈，则可能为出栈序列的是( )A.DCBAB.CDABC.DBACD.DCAB10. 归并排序中，归并的趟数是( )。

第一章绪论一．选择题1．下面关于算法说法正确的是（）A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的2．以下哪一个术语与数据的存储结构无关？（）A．栈 B．哈希表 C．线索树 D．循环队列3．算法复杂度通常是表达算法在最坏情况下所需要的计算量，O(1)的含义是（）A．算法执行一步就完成B．算法执行1秒钟就完成C．算法执行常数步就完成 D．算法执行可变步数就完成4．数据结构研究的内容是（）。

A．数据的逻辑结构 B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面5．一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。

A．确定性、可行性、有穷性 B．易读性、确定性、有效性C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性6．以下关于数据的逻辑结构的叙述中正确的是（）。

A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构7．下列时间复杂度中最坏的是（）A．O(1) B．O(n) C．O(log2n） D．O(n2)8．算法的时间复杂度取决于（）A．待处理数据的初态 B．问题的规模C．程序本身所占的空间 D．问题的规模和待处理数据的初态二．综合应用题1.有下列运行时间函数：（1）f1(n)=1000; （2）f2(n)=n2+1000n; （3）f3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间。

2.下面函数mergesort执行的时间复杂度为多少?假设函数调用为mergesort(1,n)，merge 函数时间复杂度为 O(n)void mergesort(int i,int j){int m;if(i!=j){mergesort(i,m);mergesort(m+1,j);merge(i,j,m);//本函数时间复杂度为 O(n)}}第二章线性表一．选择题1．下述哪一条是顺序存储结构的优点？（）A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。