数据结构和算法选择题[1]1

第1章绪论1.选择题（1）C （2）B （3）C （4）D （5）B2.判断题（1）√（2）Ⅹ（3）Ⅹ（4）Ⅹ（5）√3.简答题（1）根据数据元素之间的不同逻辑关系，通常将其划分为哪几类结构？【解答】常见的四种逻辑结构有：①集合结构：数据元素间的关系是“属于同一个集合”。

②线性结构：数据元素之间存在着一对一的关系。

③树型结构：数据元素之间存在着一对多的关系。

④图型结构：数据元素之间存在着多对多的关系。

（2）请描述线性结构中数据元素与数据元素之间的关系特点？【解答】线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。

在线性结构中，有且仅有一个元素被称为“第一个”，除第一个元素之外其他元素均有唯一一个“前驱”；有且仅有一个元素被称为“最后一个”，除最后一个元素之外其他元素均有唯一一个“后继”。

（3）请描述树形结构中数据元素与数据元素之间的关系特点？【解答】树形存储结构，就是数据元素与元素之间存在着一对多关系的数据结构。

在树形存储结构中，树的根节点没有前驱结点，其余的每个节点有且只有一个前驱结点，除叶子结点没有后续节点外，其他节点的后续节点可以有一个或者多个。

（4）常用的存储结构有哪几种，各自的特点是什么？【解答】常见的四种存储结构有：①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。

顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。

②链接存储：对逻辑上相邻的元素不要求不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。

③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点其它信息。

④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。

（5）简述算法和程序的区别。

【解答】一个算法若用程序设计语言来描述，则它就是一个程序。

算法的含义与程序十分相似，但又有区别。

一个程序不一定满足有穷性。

一、选择：(每题2分，共30分) 简单选择排序 冒泡排序 归并排序 稳定1、下列排序算法中，其中（ ）是稳定的。

堆排序 希尔排序 快速排序 基数排序 不稳定A) 堆排序，冒泡排序 B) 快速排序，堆排序 C) 直接选择排序，希尔排序 D) 归并排序，冒泡排序 2、下列排序方法中，哪一个是稳定的排序方法？（ ）A)堆排序 B)二分法插入排序 C)希尔排序 D)快速排序3、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。

A) 2 3 4 1 5 B) 5 4 1 3 2 C) 2 3 1 4 5 D) 1 5 4 3 2 4、非空循环链表head 的尾结点 *p 满足下列( )条件A)head->next==p; B)head==p; C)p->next==head; D)p->next==0 5、下列编码中属前缀码的是( )A){1,01,000,001} B){1,01,011,010} C){0,10,110,11} D){0,1,00,11} 6、对于哈希函数H(key)=key % 7,被称为同义词的关键字是( )A)36和50 B)23和39 C)15和44 D)25和517、将一个长度为n 的向量的第i 个元素删除时，需要前移( )个元素。

A) i B) n-i C) n+1 D) n-i+18、有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找62，要经过( )次比较。

A. 3 B. 6 C. 4 D. 5 9、高度为 K 的二叉树最大的结点数为（ ）。

A)2k B)2k-1 C)2k -1 D)2k-1-110、对表长为n 的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( )A) (n-1)/2 B) n/2 C) (n+1)/2 D) n11、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）A)深度优先搜索算法 B)广度优先搜索算法 C)求最小生成树的prim 算法 D)拓扑排序算法12、已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( )。

[模拟] 软件设计师数据结构与算法(一)选择题第1题：循环链表的主要优点是______。

A.不再需要头指针了B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表参考答案：D第2题：表达式a*(b+c)-d的后缀表达式为______。

A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd参考答案：B第3题：若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为______。

A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA参考答案：D第4题：无向图中一个顶点的度是指图中______。

A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数D.与该顶点连通的顶点数参考答案：C第5题：利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素30要进行______次元素间的比较。

A.4B.5C.6D.7参考答案：B第6题：在常用的描述二叉排序树的存储结构中，关键字值最大的结点______。

A.左指针一定为空B.右指针一定为空C.左、右指针均为空D.左、右指针均不为空参考答案：B第7题：一个具有n(n＞0)个顶点的连通无向图至少有______条边。

A.n+1B.nC.n/2D.n-1参考答案：D第8题：由权值为9，2，5，7的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为______。

A.23B.37C.44D.46参考答案：C第9题：在最好和最坏情况下的时间复杂度均为O(nlog₂n)且稳定的排序方法是______。

A.基数排序B.快速排序C.堆排序D.归并排序参考答案：D第10题：己知一个线性表(38，25，74，63，52，48)，假定采用散列函数h(key)=key % 7计算散列地址，并散列存储在散列表A[0，…，6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为______。

数据结构习题及答案第1章算法一、选择题1.算法的时间复杂度是指（）。

A）执行算法程序所需要的时间B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2.算法的空间复杂度是指（）。

A）算法程序的长度B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间D）算法程序中的指令条数3.下面（）的时间复杂度最好（即执行时间最短）。

logn)O(）O(n ) B）A2logn2 ) D）O(n)C）O(n24.下面累加求和程序段的时间复杂度为（）。

int sum(int a[],int n){int i, s=0;for (i=0;i<n;i++)< p="">s+=a[i];return s;}logn ) ）O(A）O(1 ) B22)）O(nC）O(n ) D中的算法，c[][]相加的结果存放到b[][]n阶矩阵5.下面是将两个n阶矩阵a[][]与。

该算法的时间复杂度为（）void matrixadd(int a[][],intb[][],c[][],int n){int i,j;for (i=0;i<n;i++)< p="">for(j=0;j<n;j++)< p="">c[i][j]=a[i][j]+b[i][j];}nlog) ）O(1 ) B）O(A22) ）O(nO( n ) DC）。

6.下面程序段的时间复杂度为（） 1int i=0,s1=0,s2=0;while(i<n)< p="">{if(i%2)s1+=i;elses2+=i;i++;}nlog) O(A）O(1 ) B）22) ）O(nC）O(n ) D ）。

7.下面程序段的时间复杂度为（int prime(int n){int i=1;int x=(int)sqrt(n);while(i<=x){i++;if(n%i==0)break;}if(i>x)return 1;elsereturn 0;}nlog) O(O(1 ) BA））2n) O(）CO(n ) D））下面程序段的时间复杂度为（8.int fun(int n){int i=1,s=1;while(s<n)< p="">{i++;s+=i;}return i;}nlog)O(n/2) BA））O(2 2n) ）O(C）O(n ) D9.下面程序段的时间复杂度为（）int i,j,m,n,a[][];for(i=0;i<m;i++)< p="">for(j=0;j<n;j++)< p="">a[i][j]=i*j;22) ）O(nA）O(m) BO(m+n) ）C）O(m*n ) D ）10. 下面程序段的时间复杂度为（int sum1(int n){int i,p=1,s=0;for(i=1;i<=n;i++){p*=i;s=s+p;}return s;}nlog) ）O(A）O(1 ) B22)O(n ) D）O(nC）二、填空题复杂度。

数据结构与算法期中考试卷（含答案）⽟林师范学院期中课程考试试卷（2010——2011学年度第⼀学期）命题教师：刘恒命题教师所在系：数计系课程名称：数据结构与算法考试专业：信计考试年级：09级⼀、单项选择题（每题2分，共30分，把正确答案填⼊表格中） 1、在数据结构中，从逻辑上可以把数据结构分成( C )。

A 、动态结构和静态结构B 、紧凑结构和⾮紧凑结构C 、线性结构和⾮线性结构D 、逻辑结构和存储结构 2、结构中的数据元素之间存在⼀个对多个的关系，称为(B )结构。

A 、线性 B 、树形 C 、图状 D 、⽹状 3、以下关于线性表的说法不正确的是(C )。

A 、线性表中的数据元素可以是数字、字符、记录等不同类型。

B 、线性表中包含的数据元素个数不是任意的。

C 、线性表中的每个结点都有且只有⼀个直接前驱和直接后继。

D 、存在这样的线性表：表中各结点都没有直接前驱和直接后继。

4、关于单链表的说法，请选出不正确的⼀项( C)。

A 、逻辑相邻、物理不⼀定相邻B 、不能随机存取C 、插⼊与删除需移动⼤量元素D 、表容量易于扩充 5、关于顺序表的说法，请选出不正确的⼀项(D )。

A 、逻辑相邻、物理相邻 B 、可实现随机存取 C 、存储空间使⽤紧凑 D 、表容量易于扩充6、设N 为正整数，试确定下列程序段中前置以记号@语句的频度为(A )。

x=91;y=100;while(y>0){@if(x>100){x-=10;y--;} else x++; } A 、1100 B 、 9100 C 、110 D 、 9107、在顺序表中删除⼀个元素，平均需要移动( C)元素，设表长为n 。

A、n/2-1 B 、n/2+1C 、n/2D 、(n+1)/28、对单链表执⾏下列程序段，请选出正确的⼀项( A)。

T=P;While(T->next!=NULL ){T —>data=T —>data*2;T=T —>next;} A 、R->data=4 B 、R->data=8C 、H->data=4D 、Q->data=79、若⼀个栈的输⼊序列是1，2，3，┅，n ，输出序列的第⼀个元素是n,则第k 个输出元素是( C)。

一、单项选择题1 某算法的时间复杂度是O(n2 ) ，表明该算法（）。

A 问题规模是n2B 问题规模与n2成正比C 执行时间等于n2D 执行时间与n2成正比2、关于数据结构的描述，不正确的是（）。

A数据结构相同，对应的存储结构也相同。

B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。

C数据结构操作的实现与存储结构有关。

D定义逻辑结构时可不考虑存储结构。

3、按排序策略分来，起泡排序属于（）。

A插入排序B选择排序C交换排序D归并排序4、利用双向链表作线性表的存储结构的优点是（）。

A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度C节省空间D便于销毁结构释放空间5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。

A 1,2,3,4B 1,3,2,4C 1,4,2,3D 4,3,2,16、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。

A按长度递减的顺序求出图的某顶点到其余顶点的最短路径B按长度递增的顺序求出图的某顶点到其余顶点的最短路径C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径D通过广度优先遍历求出图的某顶点到其余顶点的最短路径7、字符串可定义为n（ n≥ 0）个字符的有限（）。

其中，n是字符串的长度，表明字符串中字符的个数。

A集合B数列C序列D聚合8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。

在这种情况下，元素A[8][5]的起始地址为（）。

A SA+141B SA+144C SA+222D SA+2559、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。

A2B3C4D510.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。

A. n+1B. nC. n-1D. n-211.一个递归算法必须包括 __________ 。

精心整理第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现5A6{x=x-10;y--;}elsex++;（2）for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;（3）s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;（6）x=n;n108 C63.5 C1 C-1 C1 Cext=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;2,=(rear+1)%=(rear+1)%(m+1)（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。

A.(rear+1)%n====frontC．rear+1==frontD.(rear-l)%n==front（14）栈和队列的共同点是（）。

A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点（15）一个递归算法必须包括（）。

A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。

试写一个算法判定给定的字符向量是否为回文。

(提示：将一半字符入栈)根据提示，算法可设计为：0’9’0’9’0’0’9’0’0’9’0’0’0’M-1]实现循环队列，其中M是队列长度。

数据结构与算法(一)(总分78,考试时间90分钟)一、选择题1. 计算机算法指的是______，它必须具备输入、输出，可执行性、确定性和有穷性。

A. 计算方法B. 排序方法C. 解决问题的有限运算序列D. 调度方法2. 设计一个“判别在表达式中左、右括号是否配对出现”的算法，采用______ 数据结构最佳。

A. 线性表的顺序存储结构B. 栈C. 队列D. 线性表的链式存储结构3. 若对一棵二叉树进行中序遍历得到的结果是(B，D，A，G，H，E，C，F)，进行后序遍历的结果是DBHGEFCA，那么这棵二叉树进行前序遍历得到的结果是______。

A. (A，B，D，C，E，G，H，B. (A，B，D，C，E，H，G，C. (D，B，A，C，E，G，H，D. 无法确定4. 一个队列的入列序号是1，2，3，4，则队列的输出系列是______。

A. 4，3，2，1B. 1，2，3，4C. 1，4，3，2D. 3，2，4，15. 对关键字序列(11，12，13，14，15)采用对半查找算法查找关键字11，则关键字之间比较次数为______。

A. 1B. 2C. 3D. 46. 如果以链表为栈的存储结构，则出栈操作是______。

A. 必须判别栈是否为满B. 必须判别栈是否为空C. 判别栈元素的类型D. 对栈不作任何判别7. 在算法设计基本方法中，______ 是从初始条件出发，逐次推出所需求的结果。

A. 递推B. 递归C. 列举法D. 归纳法8. 分析算法的目的是______。

A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档9. 若完全二叉树共有n个结点，且从根结点开始，按层序(每层从左到右)用正整数0，1，2，…，n-1，从小到大对结点编号，则对于编号为k的结点，错误的是______。

A. 若k＞0，则该结点的父结点编号为[k/2]([]表示取整)B. 若2k＞n-1，则编号为k的结点无右子树，但可能有左子树C. 若2k+1＜=n-1，则编号为k的结点的右子结点编号为2k+1D. 若k=0，则该结点肯定没有父结点10. 用数组A[0…m-1]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为______。

国家开放大学《数据结构与算法》形考任务1-2参考答案《数据结构与算法》是“数据科学与大数据技术”专业（本科）的一门统设必修课。

课程编号：04692形考任务1一、单项选择题1.下面说法错误的是（）。

A.数据结构是指互相之间存在着一种或多种关系的数据元素的集合B.数据(Data)是指客观事物的符号表示C.数据元素是表示数据的不可分割的最小标识单位D.数据的基本单位是数据元素2.数据结构中的线性结构是指（）。

A.数据元素之间属于同一个集合B.数据元素之间存在着一对一的线性关系C.数据元素之间存在着一对多的线性关系D.数据元素之间存在着多对多的线性关系3.下列有关递归的说法错误的是（）。

A.递归需要有边界条件、递归方程两部分构成。

B.递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算。

C.递归通常把一个复杂问题层层转化为一个与原问题相似的规模较小的问题来求解。

D.只有在函数中直接调用自身才能叫做递归函数。

4.根据数据元素之间关系的不同，数据结构分为（）。

A.物理结构，逻辑结构B.集合结构，线性结构，树结构，图结构C.顺序结构，链表结构D.递归结构，普通结构5.栈S最多能容纳4个元素。

现有6个元素按A、B、C、D、E、F的顺序进栈，下列（）序列是可能的出栈序列。

A.E、D、C、B、A、FB.B、C、E、F、A、DC.B、D、C、F、E、AD.A、D、F、E、B、C6.顺序循环队列容量为50，队头表示第一个元素的位置，队尾表示最后一个元素的下一个位置，当队头为31，队尾为8的时候，队列中共有（）个元素。

A.25B.26C.27D.287.对线性表，在下列（）情况下应当采用链表表示。

A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变8.若用一个大小为8的数组来实现循环队列，且当tail和head的值分别为6，0。

当从队列中删除两个元素，再加入一个元素后，tail和head的值分别为（）。

数据结构与算法测试题+参考答案一、单选题（共80题，每题1分，共80分）1、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？A、仅有头指针的单循环链表B、双链表C、仅有尾指针的单循环链表D、单链表正确答案：C2、数据结构研究的内容是（）。

A、数据的逻辑结构B、数据的存储结构C、建立在相应逻辑结构和存储结构上的算法D、包括以上三个方面正确答案：D3、下列关于无向连通图特征的叙述中，正确的是：所有顶点的度之和为偶数边数大于顶点个数减1至少有一个顶点的度为1A、只有1B、1和2C、1和3D、只有2正确答案：A4、下面的程序段违反了算法的（）原则。

void sam(){ int n=2;while (n%2==0) n+=2;printf(“%d”,n);}A、确定性B、可行性C、有穷性D、健壮性正确答案：C5、对任意给定的含 n (n>2) 个字符的有限集 S，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。

下列叙述中，正确的是：A、出现频次不同的字符在 T2 中处于相同的层B、出现频次不同的字符在 T1 中处于不同的层C、T1 的高度大于 T2 的高度D、T1 与 T2 的结点数相同正确答案：A6、数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？A、快速排序B、选择排序C、插入排序D、冒泡排序正确答案：A7、设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。

采用线性探测法处理冲突，并将关键字序列{ 26，25，72，38，8，18，59 }依次存储到散列表中。

元素59存放在散列表中的地址是：A、11B、9C、10D、8正确答案：A8、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：A、每次划分后，先处理较短的分区可以减少递归次数B、递归次数与每次划分后得到的分区处理顺序无关C、递归次数与初始数据的排列次序无关D、每次划分后，先处理较长的分区可以减少递归次数正确答案：B9、以下数据结构中，（）是非线性数据结构。