__(3)___
else
__(4)___
}
for ( k=i-1;k>=j+1;k- -)
a[k+1] = (5) ;
a[j+1]=a[0];
}
}
3.设有一个头指针为head的不带头结点单向链表,p、q是指向链表中结点类型的指针
变量,p指向链表中结点a, (设链表中没有结点的数据域与结点a的数据域相同),写出相关语句。
(1).使该单向链表成为单向循环链表
(2)插入结点s,使它成为a结点的直接前驱
q=p; x=p->data;
while (__(1)___ )q=q->next;
q->next= __(2)__;
q=p; p=p->next;
while(p->data!=x)
{ q=p;
__(3)___
}
s->next=p;
__(4)___
4 .设有一个头指针为head的不带头结点单向链表,p、q是指向链表中结点类型的指针
变量,p指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同), 写出相关语句
(1)使该单向链表成为单向循环链表
(2) 删去a结点
q=p; x=p->data;
while (q->next!=NULL)q=q->next;
__(1)___
q=p; p=p->next;
while(p->data!=x)
{ q=p;
__(2)___
}
__(3)___
期末综合练习二答案
一、单项选择题
1.B 2.B 3.C 4.B 5.C 6.D 7.B 8.B 9.A 10.D 11.C 12.B 13.A 14.A 15.A 16.C 17.D 18.D 19.A 20.C 21.C 22.A 23.C 24.B 25.B 26.A 27.B 28.C 29.A 30.B
二、填空题
1. 物理(存储)
2. 线性
3. h=h->next;
4. s->next=h;
5.(d , e , (i ,j ) ,k )
6. a
7. ( a , c)
数据结构第二章试题
第2章线性表 一、选择题 1. 链表不具备的特点是()。 A.可随机访问任意结点 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件是()。 ==NULL B. head->next==NULL >next==head !=NULL 3.带头结点的单链表head为空的判定条件是()。 ==NULL B. head->next==NULL >next==head !=NULL 4.带头结点的双循环链表L为空表的条件是()。 A.L==NULL B.L->next->==NULL C.L->prior==NULL >next==L 5.非空的循环链表head的尾结点(由P所指向)满足()。 A.p->next==NULL B.p==NULL C.p->next==head ==head 6.在循环双链表的p所指结点之前插入s所指结点的操作是()。 A.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior; B.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior; C.s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s; D. s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用()存储方式最节省运算时间。 A.单链表 B.给出表头指针的单循环链表 C.双链表 D. 带头结点的双循环链表 8.某线性表最常用的操作是在最后一个结点之后插入一个节点或删除第一个结点,故采用()存储方式最节省运算时间。 A.单链表 B.仅有头结点的单循环链表 C.双链表 D. 仅有尾指针的单循环链表 9.需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是()。 A.单链表 B.静态链表 C.线性链表 D. 顺序存储结构 10.如果最常用的操作是取第i个结点及前驱,则采用()存储方式最节省时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是()。 A.O(1) B.O(n) C.O(n*n) D. O(nlog2n) 12.在一个长度为n(n>1)的单链表上,设有头和尾两个指针,执行()操作与链表的长度有关。A.删除单链表中的第一个元素 B.删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 13.设线性表有n个元素,以下算法中,()在顺序表上实现比在链表上实现效率更高。A.输出第i(0<=i<=n-1)个元素值 B.交换第0个元素与第1个元素的值 C. 顺序输出这n个元素的值 D.输出与给定值x相等的元素在线性表中的序号 14.设线性表有2n个元素,算法(),在单链表上实现比在顺序表上实现效率更高。 A.删除所有值为x的元素 B.在最后一个元素的后面插入一个新元素 C. 顺序输出前k个元素 D.交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1)
全国自学考试数据结构导论试题及答案(4套)
全国2011年1月自学考试数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在顺序表中查找第i个元素,时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n) 2.树形结构中,度为0的结点称为( ) A.树根 B.叶子 C.路径 D.二叉树 3.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={,,,,,,,,,},则图G的拓扑序列是 ( ) A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7 4.有关图中路径的定义,表述正确的是( ) A.路径是顶点和相邻顶点偶对构成的边所形成的序列 B.路径是不同顶点所形成的序列 C.路径是不同边所形成的序列 D.路径是不同顶点和不同边所形成的集合 5.串的长度是指( ) A.串中所含不同字母的个数 B.串中所含字符的个数 C.串中所含不同字符的个数 D.串中所含非空格字符的个数 6.组成数据的基本单位是( ) A.数据项 B.数据类型 C.数据元素 D.数据变量 7.程序段 i=n;x=0; do{x=x+5*i;i--;}while (i>0); 的时间复杂度为( ) A.O(1) B.O(n) C.O(n2) D.O(n3) 8.与串的逻辑结构不同的 ...数据结构是( ) A.线性表 B.栈 C.队列 D.树
02142数据结构导论201604
2016年4月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码 02142) 本试卷共6页。满分l00分,考试时间l50分钟。 考生答题注意事项: 1.本卷所有试题必须在答题卡上作答。答在试卷上无效,试卷空白处和背面均可作草稿纸。2.第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3.第二部分为非选择题。必须注明大、小题号,使用0.5毫米黑色字迹签字笔作答。4.合理安排答题空间,超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题。每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1.一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工,则适合于描述该公司组织机构的逻辑结构是 A.线性表 B.队列 C.树 D.图 2.计算n!(整数n≥0)的递归算法是:int Factorial(int n){if(n= =o)return l;else return n*Factorial(n--1);}其时闯复杂度为 A.0(n) B.0(log2n) C.O(n0) D.O(n2) 3.将一个由指针q指向的结点插在单链表中由指针P所指向的结点之后的操作是 A.p=q; B.p--:>next=q; C.q一>next=p--:>next;p-->next=q; D.p一>next—q;q-->next—p--:>next; 4. 设初始栈为空,s表示人栈操作,x表示出栈操作,则合法的操作序列是 A.sxxssxxs B.ssxsxxxs C.ssxxxssx D.sssxxxsx 5.将递归形式描述的算法改写为功能等价的非递归形式描述的算法,通常应设置的辅助结构是 A.顺序表 B.单链表C.栈 D.队列 6.设长度为n的队列用单循环链表表示(假设表尾结点为当前队列的队尾元素),若只设头指针,则入队操作、出队操作的时间复杂度分别为 A.O(n)、O(1) B.O(1)、O(1) C.O(1)、O(n) D.0(n)、0(n) 7.若采用顺序存储(一维数组)结构存储一棵如题7图所示的二叉树,根结点1的下标为l,剥结点4的下标为 A.4 B.5 C.6 D.7 8.按层序(自顶向下、从左到右)遍历二叉树时需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时,队列中所出现的元素个数最多是
数据结构期末考试复习笔记
判断: 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因 此属于同一数据对象正确 4.在线性表的顺序存储结构中,逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中,插入和删除元素时,移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A,B,C,D,可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中,任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下,不能做出出栈操作,否则产生溢出正确 13.在前序遍历二叉树的序列中,任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空: 1.在N个节点的顺序表中删除一个节点平均需要移动((N-1)/2)个节点,具体的移 动次数取决于(表长N和删除位置) 2.在单链表中除首节点外,任意节点的存储位置都由(直接前驱)节点中的指针指示 3.树中节点的最大层次称为树的(度) 4.由一颗二叉树的前序序列和(中)序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度(最小)的二叉树 6.二插排序树任意节点的关键字值(大于)其左子树中各节点的关键字值(小于)其 右子树中的各节点关键字值 7.二分查找法,表中元素必须按(关键字有序)存放 选择: 1.用单链表方式存储的线性表,储存每个节点需要两个域,一个数据域,另一个是(B 指针域) 2.设A1,A2,A3为三个节点;P,10,,2代表地址,则如下的链表存储结构称为(B 单链表) 3.单链表的存储密度(C 小于1) 4.在线性表中(B 中间元素)只有一个直接前驱和一个直接后续 5.两个指针P和Q,分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是(D P==Q) 6.在栈中存取数据的原则是(B 后进先出) 7.顺序栈判空的条件是(C top==-1) 8.串是一种特殊的线性表,其特殊性体现在(B 数据元素是一个字符) 9.求字符串T和字符串S中首次出现的位置的操作为(C 串的模式匹配) 10.深度为H的二叉树至多有(B 2H-1)个节点
数据结构第二章线性表测试题
第二章线性表 1、描述一下三个概念的区别:头指针,头结点,首元结点。并给予图示。 2、对于有头结点的单链表,分别写出定位成功时,实现下列定位语句序列。(1)定位到第i 个结点a i ; (2)定位到第i 个结点的前驱a i-1; (3)定位到尾结点; (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表,且P 结点既不是首元结点,也不是尾结点,试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点;(2)在P 结点前插入S 结点;(3)在表首插入S 结点;(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && jnext; j++;} p=head; while ( p ->next ) p=p->next; while ( p->next->next ) p=p->next; (1)s->next=p->next; p->next=s; (2)q =L ; whil e ( q ->next !=p ) q =q ->next;s->next=p 或 q ->next ; q ->next=s; (3 ) s->next=L ->next; L ->next=s; (4)q =L ; whil e ( q ->next !=NULL) q =q ->next;s->next= q ->next ; q ->next=s;
4、设计算法:在顺序表中删除值为e 的元素,删除成功,返回1;否则,返回0。 5、设计一个算法,将一个带头节点的数据域依次为a 1,a 2,…,a n (n ≥3)的单链表的所有节点逆置,即第一个节点的数据域变为a n ,…,最后一个节点的数据域为a 1。(注意:先用自然语言描述算法基本思想,然后用类C++语言描述) int Sqlist::DeleteElem( T e ) { for (i=1; i<=len g t h ; i ++) // 按值顺序查找 * i 可从0开始 if (elem[i-1]= =e) // 找到,进行删除操作 { for ( j=i; jnext; 4 LinkList* pri = NULL; //之前的节点 5 while(p){ 6 LinkList* q = new LinkList; 7 q->data = p->data; //把当前节点记录下来 8 q->next = pri; 9 pri = q; 10 head->next = q; 11 LinkList* t = p; //当前节点没用了删除掉 12 p=p->next; 13 delete(t); 14 } 15 }
自考数据结构导论复习资料
数据结构导论复习 第一章概论 1.数据:凡能被计算机存储、加工处理的对象。 2.数据元素:是数据的基本单位,在程序中作为一个整体而加以考虑和处理 3.数据项:又叫字段或域,它是数据的不可分割的最小标识单位。 4.逻辑结构需要注意的几点: ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5.数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6.四类基本逻辑结构(集合、线性结构、树形结构和图形结构)的不同特点? 答:集合中任何两个结点之间都没有逻辑关系,组织形式松散; 线性结构中结点按逻辑关系依次排列形成一条“锁链”; 树形结构具有分支、层次特性,其形态有点像自然界中的树; 图状结构最复杂,其中的各个结点按逻辑关系互相缠绕,任何两个结点都可以领接。 7.运算是在逻辑结构层次上对处理功能的抽象
8.基本运算的含义? 答:假如是S上的一些运算的集合,是的一个子集,使得中每一运算都可以“归约”为中的一个或多个运算,而中任一运算不可归约为别的运算,则称中运算为基本运算 9.数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体(S ,)。 10.数据结构涉及数据表示和数据处理两个方面 11.存储结构的含义和四种基本存储方式的基本思想? 答:存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分:存储结点、机内表示和附加设施。 存储结构包括四种存储方式,顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12.运算实现与运算的联系与区别? 答:运算指的是数据在逻辑结构S上的某种操作,运算只描述处理功能,不包括处理步骤和方法;而运算实现是指一个完成该运算功能的程序,运算实现的核心是处理步骤的规定,即算法设计。 13.算法的概念和分类? 答:算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序,使得给定类型的任何问题能在有限时间内被
数据结构 期末考试复习题及答案
1.什么是最小生成树?简述最小生成树的Prime算法的思想。 答:最小生成树就是构造一棵生成树,使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想: 从连通网络N = { V, E }中的某一顶点u0 出发,选择与它关联的具有最小权值的边(u0, v),将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路,如何判断AOV网络是否有回路? 答:在AOV网络中,如果活动vi必须在vj之前进行,则称为存在有向边;在AOV网络中不能出现有向回路,如果出现了,则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环: 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列,使得AOV网络中所有应存在的前驱和后继关系都能得到满足。(1)这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 (2)如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则该AOV 网络中必定不会出现有向环;相反,如果得不到满足要求的拓扑有序序列,则说明AOV网络中存在有向环,此AOV网络所代表的工程是不可行的。
3.为何需要采用循环队列?n个空间的循环队列,最多存储多少个元素?为什 么? 答:循环队列以克服顺序队列的"假上溢"现象,能够使存储队列的向量空间得到充分的利用,所以采用循环队列。 n个空间的循环队列,最多存储n-1个元素,那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear,而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数),因此,Q.rear所指向的数组单元处于未用状态。所以说,N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法,其删除的是那个值? 答:堆的删除算法:首先,移除根节点的元素(并把根节点作为当前结点)比较当前结点的两个孩子结点的元素大小,把较大的那个元素移给当前结点,接着把被移除元素的孩子结点作为当前结点,并再比较当前结点的孩子的大小,以此循环,直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数,则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面,删除的值为根值。 5.线索二叉树中,什么是线索,它是否唯一?可有根据什么顺序得到?
【自考真题】2018年4月数据结构导论02142试题
绝密★考试结束前 全国2018年4月高等教育自学考试 数据结构导论试题 课程代码:02142 请考生按规定用笔将所有试题的答案涂二写在答题纸上三 选择题部分 注意事项: 1.答题前,考生务必将自己的考试课程名称二姓名二准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上三 2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑三如需改动,用橡皮擦干净后,再选涂其他答案标号三不能答在试题卷上三 一二单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将 答题纸”的相应代码涂黑三错涂二多涂或未涂均无分三 1.数据的逻辑结构分为四种,其中结构最复杂的是 A.集合 B.线性结构 C.树形结构 D.图结构 2.下面程序是矩阵转置算法MM的实现过程,其时间复杂度为 const int n=3; void MM(int A[n][n]) { int i,j,temp; for(i=0;i3.设顺序表的表长为n,则删除一个元素在最坏情况下元素移动次数为 A.n-2 B.n-1 C.n D.n+1 4.带头结点的双向循环链表L为空的条件是 A.L->next==L->prior B.L->prior==NULL C.(L->next==L)&&(L->prior==L) D.(L->next==L)&&(L->prior=NULL) 5.执行进栈操作,在元素x进栈前需要进行的操作是 A.判断栈是否满,若栈未满,top值加1 B.判断栈是否空,若栈未空,top值加1 C.判断栈是否满,若栈未满,top值减1 D.判断栈是否空,若栈未空,top值减1 6.关于队列,下列叙述正确的是 A.队列的元素个数可以无穷大 B.队列中元素的类型可以不同 C.队列是一个非线性的序列 D.队列的特点是先进先出 7.设循环队列的元素存放在一维数组Q[30]中,队列非空时,front指示队列首结点的前一个位置,rear指示队列尾结点三如果队列中元素的个数为10,front的值为25,则rear应指向的元素是 A.Q[4] B.Q[5] C.Q[14] D.Q[15] 8.二叉树第i(i≥1)层上的结点数最多为 A.2i-1 B.i-1 C.2*i D.2*(i-1) 9.关于二叉链表,下列叙述正确的是 A.二叉链表是二叉树唯一的链式存储结构 B.对二叉链表的访问可以从任意结点开始 C.每个二叉链表不需要有一个指向根节点的指针 D.二叉链表的结点结构包含一个数据域和两个指针域 10.假设初始森林中共有n棵二叉树,每棵树中都仅有一个孤立的结点三将该森林构造成哈夫 曼树,则最终求得的哈夫曼树的结点数为 A.n-1 B.n C.2n-1 D.2n 11.无向图中的极大连通子图是 A.连通分量 B.生成树 C.强连通分量 D.强连通图 12.在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为 A.O(n) B.O(n+e) C.O(n2) D.O(n3)
数据结构复习资料,java数据结构期末考试
第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题(n)大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度:随着n的增加时增长函数的一般性质,这一特性基于该表达式的主项,即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次,算法的阶次是忽略该算法的增长函数中的常量和其他次要项,只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度:增长函数的界限,由增长函数的主项确定的。渐进复杂度类似的函数,归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法:与问题大小无关、执行时间恒定的增长函数称为具有O(1)的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法,从运行效率的角度来说都是等价的。 9.如果算法的运行效率低,从长远来说,使用更快的处理器也无济于事。 10.要分析循环运行,首先要确定该循环体的阶次n,然后用该循环要运行的次数乘以它。(n 表示的是问题的大小) 11.分析嵌套循环的复杂度时,必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析: 如:public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O(n),计算调用该方法的初始循环的时间复杂度,只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O(n2)。 13指数函数增长> 幂函数增长> 对数函数增长
数据结构试题及答案
一、单选题(每题2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结 点,则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?(B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种( D )。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度(B)。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为(D )参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的(A)。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为(D )。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行,删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为____O(1)_____,在表尾插入元素的时间复杂度为____O n________。
自考数据结构导论
全国2014年4月高等教育自学考试 数据结构导论试题 课程代码:02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项: 1.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中,最小的是( A ) A.O(log2n) B.O(n) C.O(n2) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外,还有( D ) A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 5.元素的进栈次序为A,B,C,D,E,出栈的第一个元素为E,则第四个出栈的元素为( C ) A.D B.C C.B D.A 6.带头结点的链队列中,队列头和队列尾指针分别为front和rear,则判断队列空的条件为( A ) A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树,结点个数最多为( A )
02142数据结构导论2010年1 月份真题及答案
2010年1月高等教育自学考试全国统一命题考试 数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是() A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec,中根遍历序列为debac,则先根遍历序列为() A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时,空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中,所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示,若只设头指针,则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中,要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序,在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)/2 8.对线性表进行二分查找时,要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储,且结点按关键字有序排列 D.以链接方式存储,且结点按关键字有序排列
9.在表长为n的顺序表上做删除运算,其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时,该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述,错误的 ...是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中,则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)%(m-1) C.rear=(rear+1)%m D.rear=(rear+1)%(m+1) 14.关于串的的叙述,不正确 ...的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储 15.对称矩阵A[N][N],A[1][1]为首元素,将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)/2]中,则任一上三角元素A[i][j]存于T[k]中,下标k为( ) A.i(i-1)/2+j B.j(j-1)/2+i C.i(j-i)/2+1 D.j(i-1)/2+l 二、填空题(本大题共13小题,每小题2分,共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1;i<=n;i++) for(j=1;j<=n;j++)
数据结构学生期末复习卷习题答案
一.是非题 (正确的打“√”,错误的打“×”。) 1. 数据结构可用三元式表示(D,S,P)。其中:D是数据对象,S是D上的关系集, P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5.邻接多重表可以用以表示无向图,也可用以表示有向图。× 6.可从任意有向图中得到关于所有顶点的拓扑次序。× 7.一棵无向连通图的生成树是其极大的连通子图。× 8.二叉排序树的查找长度至多为log2n。× 9.对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10.对于目前所知的排序方法,快速排序具有最好的平均性能。√ 11. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。√ 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。√ 15. 完全二叉树必定是平衡二叉树。√ 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。√ 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。√ 19. 二叉树中每个结点有两个子结点,而对一般的树,则无此限制,所以,二叉树是树的特殊情形。× 20. 算法的时间复杂性越好,可读性就越差;反之,算法的可读性越好,则时间复杂性就越差。× 二.选择题 1. 若对编号为1,2,3的列车车厢依次通过扳道栈进行调度,不能得到 (e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中(c)具有先进先出(FIFO)特性,( b )具有先进后出(FILO)特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 的结果是 ( d ) 。 a: ‘database’ b: ‘data-base’ c: ‘bas’ d: ‘data-basucture’
数据结构第二章练习题 - 副本
《数据结构》第二章练习题 1.单项选择题 2.1链表不具备的特点是() A 可随机访问任一结点 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与其长度成正比 2.2 不带头节点的单链表head为空的判定条件是() A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.3带头节点的单链表head为空的判定条件是() A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.4 带头结点的双循环链表L为空的条件是() A L==NULL B l->next->==NULL C L->prior==NULL D L->next==L 2.5 非空的循环单链表head尾结点(由P所指向)满足() A P->next==NULL B P==NULL C P->next==head D P==head 2.6在双循环链表中的P所指结点之前插入s所指结点的操作是() A p->prior=s;s->next=p;p->prior>next=s;s->prior=p->prior; B p->prior=s;p->prior>next=s;s->next=p;s->prior=p->prior; C s->next=p;s->prior=p->prior; p->prior=s;p->right->next=s; D s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 2.7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用()存储方式最节省运算时间 A 单链表 B 给出表头指针的单循环链表 C 双链表 D 带头结点的双循环链表 2.8某线性表最常用的操作时在最后一个结点之后插入一个结点或删除第一个结点,故采用()存储方式最节省运算时间 A 单链表B仅有头结点的单循环链表
2010年1月自考数据结构导论真题
全国2010年1月自学考试数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是() A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec,中根遍历序列为debac,则先根遍历序列为() A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时,空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中,所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示,若只设头指针,则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中,要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序,在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)/2 8.对线性表进行二分查找时,要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储,且结点按关键字有序排列 D.以链接方式存储,且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算,其平均时间复杂度为( ) A.O(1) B.O(n)
C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时,该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述,错误的 ...是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中,则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)%(m-1) C.rear=(rear+1)%m D.rear=(rear+1)%(m+1) 14.关于串的的叙述,不正确 ...的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储 15.对称矩阵A[N][N],A[1][1]为首元素,将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)/2]中,则任一上三角元素A[i][j]存于T[k]中,下标k为( ) A.i(i-1)/2+j B.j(j-1)/2+i C.i(j-i)/2+1 D.j(i-1)/2+l 二、填空题(本大题共13小题,每小题2分,共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) for(k=1;k<=n;k++) s=i+j+k; 17.在数据结构中,各个结点按逻辑关系互相缠绕,任意两个结点可以邻接的结构称为____________。
(完整word版)数据结构期末复习题
数据结构期末复习题 一、选择题 1.以下说法中不正确的是(D)。 A.数据元素是数据的基本单位 B.数据项是不可分割的最小可标识单位 C.数据可由若干个数据元素构成 D.数据项可由若干个数据元素构成 2.计算机所处理的数据一般具备某种内在联系,这是指(B)。 A.数据和数据之间存在某种关系 B.元素和元素之间存在某种关系 C.元素内部具有某种结构 D.数据项和数据项之间存在某种关系 3.在数据结构中,与所使用的计算机无关的是数据的(A)结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4.数据的逻辑结构可以分为(C)两类。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.数据的逻辑结构是指(A)关系的整体。 A.数据元素之间逻辑 B.数据项之间逻辑 C.数据类型之间 D.存储结构之间 6.以下数据结构中(D)属非线性结构。 A.栈 B.串 C.队列 D.平衡二叉树 7.以下属于逻辑结构的是(C)。 A.顺序表 B.哈希表 C.有序表 D.单链表 8.以下不属于存储结构的是(A)。 A.栈 B.线索二叉树 C.哈希表 D.双链表 9.在计算机中存储数据时,通常不仅要存储个数据元素的值,而且还要存储(C)。 A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 10.数据结构在计算机内存中的表示是指(A)。 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 11.在数据的存储结构中,一个结点通常存储一个(B)。 A.数据项 B.数据元素 C.数据结构 D.数据类型 12.在决定选择何种类型的存储结构时,一般不多考虑(A)。
数据结构试题及答案修2
试卷一 一、单选题(每题 2 分,共20分) 1. 对一个算法的评价,不包括如下()方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. AOV网是一种()。 A.有向图B.无向图C.无向无环图D.有向无环图 7. 若需要利用形参直接访问实参时,应将形参变量说明为()参数。 A.值B.函数C.指针D.引用 8. 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的()。 A.行号B.列号C.元素值D.非零元素个数 二、填空题(每空1分,共28分) 1. 数据结构是指数据及其相互之间的______________。当结点之间存在M对N(M:N)的联系时,称这种结构为_____________________。 2. 队列的插入操作是在队列的___尾______进行,删除操作是在队列的____首______进行。 3. 当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈满的条件是___top==0_____________。 4. 对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为_________,在表尾插入元素的时间复杂度为____________。 7. 二叉树是指度为2的____________________树。一棵结点数为N的二叉树,其所有结点的度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 9. 对于一棵具有n个结点的二叉树,用二叉链表存储时,其指针总数为_____________个,其中_______________个用于指向孩子,_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号,并按此编号把它顺序存储到一维数组A中,即编号为0的结点存储到A[0]中。其余类推,则A[ i ]元素的左孩子元素为________,右孩子元素为