2014年北方工业大学数据结构期中考试卷
- 格式:doc
- 大小:70.00 KB
- 文档页数:4
数据结构期中考试试卷一、选择题(每题2分,共20分)1. 在数据结构中,线性结构的特点是什么?A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系2. 以下哪个算法不是排序算法?A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序3. 在二叉树中,度为2的节点最多有多少个子节点?A. 1B. 2C. 3D. 44. 哈希表解决冲突的方法不包括以下哪一项?A. 分离链接法B. 开放寻址法C. 链地址法D. 树形结构法5. 以下哪个不是图的遍历算法?A. 深度优先搜索B. 广度优先搜索C. 动态规划D. 克鲁斯卡尔算法6. 栈的特点是?A. 后进先出B. 先进后出C. 先进先出D. 后进后出7. 以下哪个不是二叉搜索树的性质?A. 左子树上所有节点的值小于它的根节点的值B. 右子树上所有节点的值大于它的根节点的值C. 左子树和右子树都是二叉搜索树D. 所有节点的值都相等8. 在数据库中,索引的作用是什么?A. 增加数据存储空间B. 提高数据检索效率C. 降低数据插入速度D. 减少数据存储量9. 以下哪个不是图的存储结构?A. 邻接矩阵B. 邻接表C. 树形结构D. 边列表10. 递归算法的基本思想是什么?A. 将问题分解为更小的子问题B. 重复执行相同的操作C. 将问题转化为非递归形式D. 避免使用循环结构二、填空题(每题2分,共20分)1. 在数据结构中,______是一种特殊的线性表,只允许在一端进行插入和删除操作。
2. 排序算法中,______排序的时间复杂度为O(n^2),适用于小规模数据的排序。
3. 在图的表示中,______矩阵可以有效地表示稠密图。
4. 哈希表中,______是指两个关键字通过哈希函数得到同一个哈希地址。
5. 栈和队列的主要区别在于,栈是______,而队列是先进先出。
6. 二叉树的遍历方式包括前序遍历、中序遍历和______遍历。
11-12学年2学期电⼦信息⼯程《数据结构》期中试卷11-12学年2学期电⼦信息⼯程《数据结构》期中试卷答题纸上只写班级姓名学号及每题答案。
1、单项选择题(本⼤题共30⼩题,每⼩题1分,共30分)在每⼩题列出的四个备选项中只有⼀个是符合题⽬要求的,请将其代码填写在题后的括号内。
错选、多选或未选均⽆分。
1.数据的不可分割的最⼩标识单位是()A.数据项B.数据记录C.数据元素D.数据变量2.for(i=0;ifor(j=0;jc[i][j]=0;for(i=0;ifor(j=0;jfor(k=0;kc[i][j]=c[i][j]+a[i][k]*b[k][j];上列程序的时间复杂度为()A.O(m+n×t)B.O(m+n+t)C.O(m×n×t)D.O(m×t+n)3.若线性表最常⽤的操作是存取第i个元素及其前趋的值,那么最节省操作时间的存储⽅式是()A.单链表B.双链表C.单循环链表D.顺序表4.设单链表中指针p指向结点A,要删除A之后的结点(若存在),则修改指针的操作为()A.p—>next=p—>next—>nextB.p=p—>nextC.p=p—>next—>nextD.p—>next=p5.向⼀个栈顶指针为hs的链栈中插⼊⼀个*s结点时,应执⾏的操作为()A.hs—>next=s;B.s—>next=hs;hs=s;C.s—>next=hs—>next;hs—>next=s;D.s—>next=hs;hs=hs—>next;6.设循环队列的元素存放在⼀维数组Q[0‥30]中,队列⾮空时,front指⽰队头元素的前⼀个位置,rear指⽰队尾元素。
如果队列中元素的个数为11,front的值为25,则rear应指向的元素是()A.Q[4]D.Q[15]7.定义⼆维数组A[1‥8,0‥10],起始地址为LOC,每个元素占2L个存储单元,在以⾏序为主序的存储⽅式下,某数据元素的地址为LOC+50L,则在以列序为主序的存储⽅式下,该元素的存储地址为()A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+52L8.具有n个结点的⼆叉树,拥有指向孩⼦结点的分⽀数⽬是()A.n-1B.nC.n+1D.2n9.对⼀棵有100个结点的完全⼆叉树按层序编号,则编号为49的结点,它的左孩⼦的编号为()A.99B.98C.97D.5010.有m个叶⼦结点的哈夫曼树,其结点总数是()A.2m-1B.2mC.2m+1D.2(m+1)11.有n个结点的⽆向图的边数最多为()A.n+1B.n(n-1)/2C.n(n+1)D.2n(n+1)12.设图的邻接矩阵为,则该图为()A.有向图B.⽆向图C.强连通图D.完全图13.⼆分查找算法的时间复杂度是()B.O(nlog2n)C.O(n)14.已知8个元素(34,76,45,18,26,54,92,65),按照依次插⼊结点的⽅法⽣成⼀棵⼆叉排序树,则该树的深度为()A.4B.5C.6D.715.采⽤排序算法对n个元素进⾏排序,其排序趟数肯定为n-1趟的排序⽅法是()A.插⼊和快速B.冒泡和快速C.选择和插⼊D.选择和冒泡16.从逻辑上可以把数据结构分为()A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、⾮线性结构D.初等结构、构造型结构17.关于算法的描述,不正确的是()A.算法最终必须由计算机程序实现B.所谓时间复杂度是指最坏情况下,估算算法执⾏时间的⼀个上界C.健壮的算法不会因⾮法的输⼊数据⽽出现莫名其妙的状态D.算法的优劣与算法描述语⾔⽆关18.在单链表中,存储每个结点需要有两个域,⼀个是数据域,另⼀个是指针域,指针域指向该结点的()A.直接前趋B.直接后继C.开始结点D.终端结点19.将两个各有n个元素的有序表合并成⼀个有序表,其最少的⽐较次数为()A.nB.2n-1C.2nD.n220.栈和队列共同具有的特点是()A.都是先进后出B.都是先进先出C.只允许在端点进⾏操作运算D.既能先进先出,也能先进后出21.若⽤⼀个有6个单元的数组来实现循环队列,rear和front的初值分别为0和3。
数据结构模拟试卷一. 单选题(每题1分,共14分)1.数据结构所讨论的基本数据单位是(B)。
A、数据对象B、数据元素C、数据项D、数据类2. 在数据结构的讨论中把数据结构从逻辑上分为(C)两大类。
A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构。
3.若一个算法的时间复杂度用T(n)表示,其中n的含义是( A )A.问题规模B.指令条数C.循环层数D.函数数量4. 算法分析的目的是(C)。
A. 研究算法的输入与输出之间的关系B. 找出数据结构的合理性C. 分析算法的效率以求改进算法D. 分析算法的可读性与可移植性5、采用线性链表表示一个向量时,要求占用的存储空间地址(D)A.必须是连续的B.部分地址必须是连续C. 一定是不连续的D. 可连续可不连续6. 在一个当前长度为n的顺序表中向第j个元素(1<j<=n)之前插入一个新元素时,需向后移动(B)个元素A、n-jB、n-j+1C、n-j-1D、j7、带头结点的单链表为空的判定条件可以是:(B)A、head==NULLB、head一>next==NULLC、head一>next= = headD、head!=NULL8、设单链表中指针P指向结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为(A)A、p→next=p→next→nextB、p=p→nextC、p=p→next→nextD、p→next=p9、若有一个最大长度为size,且设有队首指针front和队尾指针rear的顺序循环队列,试问判断队列满的条件应是下列哪一个语句(D)A、front==rearB、front- rear==sizeC、front+rear==size;D、front==(rear+1)%size10. 设一个栈的入栈序列为1,2,3,4,5,6,则出栈序列不可能的是(B)。
A、3,2,5,6,4,1B、1,5,4,6,2,3C、2,4,3,5,1,6D、4,5,3,6,2,111、数据结构从总体上可分为两大类,串的逻辑结构与(D)的逻辑结构不属于同一类。
作业名称:14秋《数据结构》作业4 出卷人:SA
作业总分:100 通过分数:60
起止时间:2015-1-21 10:43:09 至2015-1-22 9:11:28
学员姓名:学员成绩:100
标准题总分:100 标准题得分:100
详细信息:
题号:1 题型:单选题(请在以下几个选项中选择唯一正确答案)本题分数:5.38
内容:
具有n个结点的连通图至少有___条边。
A、n-1
B、n
C、n(n-1)/2
D、2n
标准答案:A
学员答案:A
本题得分:5.38
题号:2 题型:单选题(请在以下几个选项中选择唯一正确答案)本题分数:5.38
内容:
有一个有序表{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时,___次比较后查找成功。
A、11
B、5
C、4
D、8
标准答案:C
学员答案:C
本题得分:5.38
题号:3 题型:单选题(请在以下几个选项中选择唯一正确答案)本题分数:3.23
内容:
图形:
A、(A)
B、(B)
C、(C)
D、(D)
标准答案:D
学员答案:D
本题得分:3.23。
《数据结构》期中考试题答案一、填空题(20分,每题2分)1.逻辑结构、存储结构2.便于插入和删除操作3.方便运算的实现4.算法执行过程中所需要的基本运算次数5.存储结构6.q.next=p.next ; p.next=q7.递归算法8.抽象类或接口二、选择题(30分,每题2分)AACBB BDDCB AACAC三、问答题(50分,每题10分)1.什么是栈和队列?两者有何异同?答:栈和队列都属于线性表结构,它们是两种特殊的线性表,栈的插入和删除操作都在线性表的一端进行,所以栈的特点是“后进先出”;而队列的插入和删除操作分别在线性表的两端进行,所以队列的特点是“先进先出”。
2.采用顺序存储结构的栈和队列,在进行插入、删除操作时需要移动数据元素吗?为什么?答:采用顺序存储结构的栈和队列,在进行插入、删除操作时不需要移动数据元素,因为栈和队列均不能进行中间插入、删除操作。
3.什么是队列的假溢出?为什么顺序存储结构队列会出现假溢出?怎样解决队列的假溢出问题?链式存储结构队列会出现假溢出吗?答:顺序队列,当入队的元素个数(包括已出队元素)超过数组容量时,队列尾下标越界,数据溢出。
此时,由于之前已有若干元素出队,数组前部已空出许多存储单元,所以,这种溢出并不是因存储空间不够而产生的,称之为假溢出。
顺序队列之所以会产生假溢出现象,是因为顺序队列的存储单元没有重复使用机制。
解决的办法是将顺序队列设计成循环结构。
链式存储结构队列不会出现假溢出。
因为每次元素入队,都要申请新结点,数据不会溢出。
4.答案:(1) (a2, a4, …, ) (2)将单链表中偶数结点位置的元素值写入顺序表list5.数据的存储结构有哪两种,各有什么特点?答:数据存储结构的基本形式有两种:顺序存储结构和链式存储结构。
顺序存储结构使用一组连续的内存单元依次存放数据元素,元素在内存中的物理存储次序与它们的逻辑次序相同。
链式存储结构使用若干地址分散的存储单元存储数据元素,逻辑上相邻的数据元素在物理位置上不一定相邻,数据元素间的关系需要采用附加信息特别指定。
河北北方学院2012-2013学年第一学期期中考试试卷 《数据结构》 (供11级计算机科学与技术使用) 注意事项: 1.请按要求在试卷的密封区填写专业、班级、姓名和学号。
2.请仔细阅读各种题目的答题要求,在规定的位置填写答案。
3.不要在试卷上乱写乱画,不要在密封区填写无关的内容。
总分合计人: 复核人: 一、单选题 (每题2分,共30分) 1、下列算法是时间复杂度是___。
for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=i+j; A ) O (1) B)O (n ) C) O (log 2n )D ) D)O (n2) 2、算法指的是___。
A)计算机程序 B)解决问题的答案 C)排序算法 D)解决问题的有限运算序列 3、下面关于线性表的叙述中,错误的是___。
A)线性表采用顺序存储,必须占用一片连续的存储单元。
B)线性表采用顺序存储,便于进行插入和删除操作。
C)线性表采用链接存储,不必占用一片连续的存储单元。
D)线性表采用链接存储,便于插入和删除操作。
4、链接存储的存储结构所占存储空间:___。
A)分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针 B)只有一部分,存放结点值专业________ 班级________ 姓名__________学号________ ………………………………………密…………………………………封………………………………………线……………………………………………C)只有一部分,存储表示结点间关系的指针D)分两部分,一部分存放结点值,另一部分存放结点所占单元数5、在n 个结点的顺序表中,算法的时间复杂度是O (1)的操作是___。
A)访问第i 个结点(1≤i ≤n )和求第i 个结点的直接前驱(2≤i ≤n )B)在第i 个结点后插入一个新结点(1≤i ≤n )C)删除第i 个结点(1≤i ≤n ) D)将n 个结点从小到大排序6、线性表若采用链式存储结构时,要求内存中可用存储单元的地址 ___。
大题共4小题,每小题5分。
共20分)
请在答题卡上作答。
26.设Q是有N个存储空间的循环队列,初始状态front=rear=0,约定指针rear指向的单元始终为空,回答下列问题。
请根据最优二叉树的基本原理,采用类C语言,描述你所设计的成绩判定过程。
29.给定有向无环图G如题29图所示,写出G的5种不同的拓扑排序序列。
的单链表定义如下,其中freq域记录本结点被访问的次数,初值为0,单链表始终以freq 序。
函数f3l完成的功能是:查找给定关键字所在结点,若查找成功,则该结点的freq域加值调整结r旨位置。
请将空白处(1)~(3)补充完整。
在答题卡上作答。
回答下列问题。
五、算法设计题(本大题共l小题,共“l0分) 请在答题卡上作答。
34.已知带头结点的单链表类型定义如下:
- 10 -。
《数据结构》期中测试-2014计算机应用技术用1-12每题3分1. 以下算法的时间复杂度为( ) for( i=n-1;i>=1; - -i) for( j=1;j<=i;j++) if(a[j]>a[j+1]) a[j]与a[j+1]对换; A. O(n)B. O(n*log 2n ) C. O(log 2n ) D. O(n 2)2.下面关于线性表的叙述中,错误的是哪一个?( ) A.线性表采用顺序存储,可根据元素的序号随机访问元素 B.线性表采用顺序存储,插入操作在表尾进行时复杂度最高 C.线性表采用链式存储,插入操作在表头进行时复杂度最低 D.线性表采用链式存储,删除操作在表头进行时复杂度最低3. 设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( )最节省时间。
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表4. 设指针变量p指向双向循环链表中的某结点,能删除p所指结点的操作为( )。
A. p->next = p->prior->next; p->prior= p->next->prior; free(p); B. p->prior->next=p->next; p->next->prior=p->prior; free(p); C. free(p); p=p->next; D. 以上都不正确5. 一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i (1<=i<=n)个元素是( )。
A. 不确定B. n-i+1C. iD. n-i 6. 进行银行窗口服务业务模拟时,应该采用的数据结构为( ) A.栈 B.队列 C.树 D.图7. 对于最大容量为n的循环队列Q ,队尾指针是Q.rear ,队头是Q.front ,则队满的条件是 ( )A. (Q.rear+1) % n=Q.frontB. Q.rear=Q.front C .Q.rear+1=Q.front D. (Q.rear-1) % n=Q.front 8. 一棵完全二叉树上有1023个结点,其中叶子结点的个数是( ) A . 512 B . 511 C .513 D .前述答案均不正确 9. 关于树与其对应的二叉树说法正确的是( )A. 两者叶子数相同B. 两者深度相同C. 两者结点数相同D. 两者度为2的结点数相同10. 算术表达式a+b*(c+d/e)转为后缀表达式后为( )A.ab+cde/* B.abcde/+*+ C.abcde/*++ D.abcde*/++11. 关于Huffamn树,如下说法错误的是( )A. 多于1个叶子结点的Huffman树中不存在度为1的结点B. Huffman树中,任意调整结点左右孩子的顺序,不影响带权路径长度C. Huffamn树的带权路径长度最大D. Huffman树中,权值越大的叶子结点离根结点越近12. n个结点的线索二叉树上含有的线索数为( )A. 2nB. n-lC. n+lD. n13-18每题2分13.链式存储的优点是插入、删除元素时不会引起后续元素的移动,缺点是只能顺序访问各元素。
作业名称:14秋《数据结构》作业1 出卷人:SA
作业总分:100 通过分数:60
起止时间:2015-1-21 10:20:21 至2015-1-22 9:11:26
学员姓名:学员成绩:100
标准题总分:100 标准题得分:100
详细信息:
题号:1 题型:单选题(请在以下几个选项中选择唯一正确答案)本题分数:4.17 内容:
将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为___。
A、O(1)
B、O(n)
C、O(m)
D、O(m+n)
标准答案:C
学员答案:C
本题得分:4.17
题号:2 题型:单选题(请在以下几个选项中选择唯一正确答案)本题分数:4.17 内容:
栈和队列的共同特点是___。
A、只允许在端点处插入和删除元素
B、都是先进后出
C、都是先进先出
D、没有共同点
标准答案:A
学员答案:A
本题得分:4.17
题号:3 题型:单选题(请在以下几个选项中选择唯一正确答案)本题分数:4.17 内容:
图形:
A、(A)
B、(B)
C、(C)
D、(D)
标准答案:A
学员答案:A
本题得分:4.17。
数据结构期中试卷及答案解析考试说明考试说明:考察前五章小题,难度接近真题。
满分100分,共20道选择题,每题5分。
请在60分钟内完成。
C T(n)=n3+5000nD T(n)=2nlogn-1000n参考答案:C本题考察时间复杂度,多个项相加时,只保留最高阶项由于巴啦啦能量——“常<对<幂<指<阶”,因此T(n)=logn+5000n=O(n)T(n)=n2-8000n=O(n2)T(n)=n3+5000n=O(n3)T(n)=2nlogn-1000n=O(nlogn)所以O(n3)复杂度最大,选C。
3.下列叙述中正确的是()①线性表在链式存储时,查找第 i 个元素的时间同 i 的值成正比②线性表在链式存储时,查找第 i 个元素的时间同 i 的值无关③线性表在顺序存储时,查找第 i 个元素的时间同 i 的值成正比A. 仅①B. 仅②C. 仅③D. ①②③参考答案:A线性表在链式存储时,查找第 i 个元素的时间同 i 的值成正比。
线性表在顺序存储时,查找第 i 个元素的时间同 i 的值无关4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值,为节省时间应采用的存储方式()。
A. 单链表B. 双向链表C. 单循环链表D. 顺序表参考答案:D注意到,题目要求存取第i个元素及其前驱和后继,ABC三个选项找到第i个元素的时间复杂度均为O(n),而D选项对于这3个位置的存取的时间复杂度均为O(1),故选D。
5.静态链表中next域表示的是()A 下一个元素的地址B 下一个元素的值C 当前元素的值D 下一个元素在数组中的位置参考答案:D静态链表一般保存在数组中,它和链表最大的区别是静态链表占用一段固定的区间,所以next域只需要表示下一个元素在数组中的下标即可而不是表示下一个元素的地址,选D。
6.对于不带头结点的链栈L(next域表示该结点下一个元素),top指针指向栈顶元素(栈顶在链头方向),则x结点进栈操作为A top->next=x;top=x;B top=x;top-next=x;C top=x;x->next=top;D x->next=top;top=x;参考答案:D本题考察链栈的操作x入栈之后x下一个元素为原来的top,所以先把x->next=top,然后更新top,栈顶元素指向x。
101. 【第1章绪论】一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为____O(n)____。
102. 【第1章绪论】数据的物理结构主要包括_____________和______________两种情况。
元素的表示,关系的表示103. 【第1章绪论】for(i=1,t=1,s=0;i<=n;i++) {t=t*i;s=s+t;}的时间复杂度为_________。
O(n)104.【第2章线性表】设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为_________________________________________________________(设结点中的两个指针域分别为llink和rlink)。
p>llink->rlink=p->rlink; p->rlink->llink=p->rlink105. 【第2章线性表】设有一个顺序循环队列中有M个存储单元,则该循环队列中最多能够存储________个队列元素;当前实际存储________________个队列元素(设头指针F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置)。
M-1 ,(R-F+M)%M106. 【第2章线性表】设顺序线性表中有n个数据元素,则第i个位置上插入一个数据元素需要移动表中_______个数据元素;删除第i个位置上的数据元素需要移动表中_______个元素。
n+1-i ,n-i107. 【第2章线性表】设指针变量p指向单链表中结点A,指针变量s指向被插入的新结点X,则进行插入操作的语句序列为__________________________(设结点的指针域为next)。
s->next=p->next; p->next=s108.【第2章线性表】设F和R分别表示顺序循环队列的头指针和尾指针,则判断该循环队列为空的条件为_____________________。
北方工业大学 《数据结构II 》课程期中试卷
A 卷 2014年春季学期
开课学院: 理学院 考试方式:闭卷 考试时间:50 分钟
班级 姓名 学号 一、 单项选择题(每题4分,共24分)
1. 对一个算法的评价,不包括如下( )方面的内容。
A .健壮性和可读性
B .并行性
C .正确性
D .时空复杂度
2. 下列不属于线性结构的是( )
A. 栈
B. 队列
C. 串
D. 二叉树
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. 已知一个有向图的邻接矩阵表示,要删除所有从第i 个结点发出的边, 应该( )
A .将邻接矩阵的第i 行删除
B .将邻接矩阵的第i 行元素全部置为0
C .将邻接矩阵的第i 列删除
D .将邻接矩阵的第i 列元素全部置为0 6. 栈和队列的共同特点是( )
A .只允许在端点处插入和删除元素
B .都是先进后出
C .都是先进先出
D .没有共同点
订 线
装
二、按要求做题(15分)
LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L;L=L->next;p=L;
S1:while(p->next) p=p->next;
S2:p->next=q;q->next=NULL;
}
return L;
}
请回答下列问题:
(1)说明语句S1的功能;
(2)说明语句组S2的功能;
(3)设链表表示的线性表存放的数据为(1,2, …,10), 写出算法执行后的返回值所表示的线性表。
三.运算题(共61分)
1.(18分)(i)已知一棵二叉树的中序遍历DBGEACF,后序遍历为DGEBFCA,求这
棵二叉树及其前序遍历。
(ii) 给定一个二叉树前序和后序遍历,能恢复出二叉树吗?为什么?
(iii) 写出下面这棵树的中序和后序遍历
2.(5分) 计算运行下列程序后m的值:
n=10; m=0;
for(i=1;i<=n;i++)
for(j=2*i; j<=n; j++)
m=m+2;
3.(10分)编号为1,2,3的三辆列车,顺序开进一个链式结构的站台,则开出车站的
顺序可能有哪些?共有多少种?
4.(10分)请画出图的邻接矩阵和邻接表。
5.(18分)设给定一个权值集合W=(3, 4,5, 6,8)
(i)要求根据给定的权值集合构造一棵哈夫曼树
(ii)计算哈夫曼树的带权路径长度及相应的哈夫曼编码。
(iii)简要介绍构造哈夫曼树的算法。