2015年计算机考研数据结构测试题(二)
来源：　 15:17:43　【】　
2015年计算机考研数据结构测试题(二)，更多2015考研资讯，复习指导，经验技巧等信息，敬请关注考研网！
　　下面请看2015年考研：计算机数据结构测试题(二)
　　一、选择题(30分)
　　1.下列程序段的时间复杂度为( )。
　　for(i=0; i<M; c[i][j]="0;&#10;　　for(i=0; i<m; c[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)
　　2.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。
　　(A) n-i (B) n+l -i (C) n-1-i (D) i
　　3.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为( )。
　　(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3
　　4.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( )。
　　(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)
　　5.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为( )。
　　(A) p-&right=s; s-&left=p; p-&right-&left=s; s-&right=p-&
　　(B) s-&left=p;s-&right=p-&p-&right=s; p-&right-&left=s;
　　(C) p-&right=s; p-&right-&left=s; s-&left=p; s-&right=p-&
　　(D) s-&left=p;s-&right=p-&p-&right-&left=s; p-&right=s;
　　6.下列各种排序算法中平均时间复杂度为O(n2)是( )。
　　(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序
　　7.设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是( )。
　　(A) n-i (B) n-1-i (C) n+l -i (D) 不能确定
　　8.设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择( )。
　　(A) 小于等于m的最大奇数 (B) 小于等于m的最大素数
　　(C) 小于等于m的最大偶数 (D) 小于等于m的最大合数
　　9.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有( )个。
　　(A) 4 (B) 5 (C) 6 (D) 7
　　10.设完全无向图中有n个顶点，则该完全无向图中有( )条边。
　　(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2
　　11.设顺序表的长度为n，则顺序查找的平均比较次数为( )。
　　(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2
　　12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过( )次比较。
　　(A) 1 (B) 2 (C) 3 (D) 4
　　13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为( )。
　　(A) 6 (B) 11 (C) 5 (D) 6.5
　　14.设有向无环图G中的有向边集合E={&1，2&，&2，3&，&3，4&，&1，4&}，则下列属于该有向图G的一种拓扑排序序列的是( )。
　　(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3
　　15.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为( )。
　　(A) 4 (B) 5 (C) 6 (D) 7
　　二、填空题(30分)
　　1. 1. 设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：
　　1) s-&next=___________;2) p-&next=s;3) t=p-&
　　4) p-&data=___________;5) s-&data=t;
　　2. 2. 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。
　　3. 3. 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。
　　4. 4. 对一组初始关键字序列(40，50，95，20，15，70，60，45，10)进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。
　　5. 5. 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的角度来考虑则最好选择________排序。
　　6. 6. 设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。
　　7. 7. 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。
　　8. 8. 设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。
　　9. 9. 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_______________________。
　　10. 10. 设无向图G(如右图所示)，则其最小生成树上所有边的权值之和为_________________。
　　三、判断题(20分)
　　1. 1. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。( )
　　2. 2. 对链表进行插入和删除操作时不必移动链表中结点。( )
　　3. 3. 子串“ABC”在主串“AABCABCD”中的位置为2。( )
　　4. 4. 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( )
　　5. 5. 希尔排序算法的时间复杂度为O(n2)。( )
　　6. 6. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( )
　　7. 7. 中序遍历一棵二叉排序树可以得到一个有序的序列。( )
　　8. 8. 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )
　　9. 9. 顺序表查找指的是在顺序存储结构上进行查找。( )
　　10.10.堆是完全二叉树，完全二叉树不一定是堆。( )
　　五、算法设计题(20分)
　　1. 1. 设计计算二叉树中所有结点值之和的算法。
　　2. 2. 设计将所有奇数移到所有偶数之前的算法。
　　3. 3. 设计判断单链表中元素是否是递增的算法。
　　附件：　　
【】　|　搜索公众微信号"考研"1&&&
　　相关推荐：
文章责编：menghaichao&　看了本文的网友还看了
?&&( 18:37:30)?&&( 15:08:40)?&&( 15:05:46)?&&( 14:57:32)?&&( 11:35:47)?&&( 18:08:26)
在线名师：　　
著名政治教育专家；研究生、博士生导师；中国国家人事人才培...[]
在线名师：　　
北京师范大学英语语言美文学硕士。屠老师的课堂气氛活跃...[]
在线名师：　　
教授，毕业于北京大学，拥有计算机、数学、金融.....[]
在线名师：　　
北京外国语大学英语语言文学学士、北京大学哲学系宗教硕士...[]
? ? 　 ? ? 　 ? ? 　 ? ? 　 ? ?
? ? 　 ? ? 　 ?
? 　 ? ? 　　 ? ? 　 ? ? 　 ? ? 　 ? ?
? ? 　 ? ?
实用工具 |
| 大全 | 大全
　　　　 |
版权声明：如果网所转载内容不慎侵犯了您的权益，请与我们联系，我们将会及时处理。如转载本内容，请注明出处。
Copyright & 2004- 网　All Rights Reserved　中国科学院研究生院权威支持(北京)　电 话：010-　传 真：010-【学习交流】软院大二数据结构机考题解 - 西电软院科协的日志,人人网,西电软院科协的公共主页
#媒体部13年度微电影#传说中屌丝逆袭的《涅槃》放过，节目花絮惹得哄堂大笑。现在是B组冯宇轩、李伟轩和张涵媚主演的《檠花怒放》，欢迎欣赏~
【学习交流】软院大二数据结构机考题解
软院大二数据结构机考题解& & & & & Author:唐威 & & & & & & & & & & & & & & & & && &Editor:陈若雅，刘哲博&&
　　感谢算法组大一的同学，尤其是唐威同学为我们写出本次大二数据结构机考题解。由于机考题目过多，考察内容有重复性，若所有题目的题解全部写出，则工程量颇大且没有意义，故算法组为我们选出了几道具有代表性的题目。&&&
题意：给出n个数，进行非降排序。排序完成后输出中间k/k+1个数（n与k奇偶相同时输出中间K个数，反之输出中间k+1个数），若n&k输出no
思路：排序，然后判断奇偶是否一致，不一致直接k++，然后中间k个数的范围是(n-k)/2+1至n-(n-k)/2& （这个不会算出门右拐数学老师办公室）
代码：& &&
#include&stdio.h&
#define N 1001
//n比较小就直接选排了
void swap(int *a,int *b)
& &int c=*a;
int main()
& &int n,k,i,j;
& &int a[N];
& &scanf("%d%d",&n,&k);
& &for(i=1;i&=n;i++)
& & &scanf("%d",&a[i]);
& &for(i=1;i&n;i++)
& & &for(j=i+1;j&=n;j++)
& & & &if(a[i]&a[j])
& & & & &swap(&a[i],&a[j]);
& &if(n&k)
& & &printf("no\n");
& & & &if((n-k)%2!=0)
& & & & &k++;
& & & &for(i=(n-k)/2+1;i&n-(n-k)/2;i++)
& & & & &printf("%d ",a[i]);
& & & &printf("%d\n",a[i&n-(n-k)/2]);
& &return 0;
题意：对一个数列进行快排，求出快排过程中元素移动次数。
思路：直接写快排代码，在进行元素移动时累加答案。
#include&stdio.h&
#define N 1001
int a[N],ans;
void swap(int *a,int *b)
& &int c=*a;
void qsort(int l,int r) &//快排函数
& &int i,j,mid;
& &i=l; j=r;
& &mid=a[(i+j)/2];
& & & &while(a[i]&mid)
& & & & &i++;
& & & &while(a[j]&mid)
& & & & &j--;
& & & &if(i&=j)
& & & & & &swap(&a[i],&a[j]);
& & & & & &i++; j--;
& & & & & &ans++; & &//交换一次ans+1
& &}while(i&=j);
& &if(i&r)
& & &qsort(i,r);
& &if(j&l)
& & &qsort(l,j);
int main()
& &int n,i;
& &scanf("%d",&n);
& &for(i=1;i&=n;i++)
& & &scanf("%d",&a[i]);
& &qsort(1,n);
& &printf("%d\n",ans*2); &//按照题意，交换一次元素等于移动2次
题意：一个栈，进栈序列为1,2,3&&n.给出一个长度为n的出栈序列，判断是否可行。
思路：对于给出的出栈序列，元素k之后出栈的所有比k小的元素必须降序，否则出栈序列不可能实现（why?分析栈先进后出的特点就行）...
阅读(1623)|
已发，请大家多多转载。
人人移动客户端下载君，已阅读到文档的结尾了呢~~
大学数据结构期末考试试题&#40;有答案&#41;答案,大学,数据结构,大学试题
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
大学数据结构期末考试试题&#40;有答案&#41;
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口《数据结构》模拟试卷二_文档库
文档库最新最全的文档下载
当前位置： & 《数据结构》模拟试卷二
《数据结构》模拟试卷二
模拟试卷二
一、选择题（每小题2分，共10分）
1．若线性表最常用的操作是存取第i 个元素及其前趋的值，则采用
式节省时间。
c．单循环链表
2．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，
同一个结点的左右孩子中， 其左孩子的编号小于其有孩子的编号， 则可采用
次序的遍历实现编号。
d．从根开始的层次遍历
3．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是
的二又树。
a．空或只有一个结点
b. 高度等于其结点数
C．任一结点无左孩子
d．任一结点无右孩子
4．下列排序算法中，时间复杂度不受数据初始状态影响， 恒为 O（nlog 2n ）的是
b. 冒泡排序
c．直接选择排序
d. 快速排序
5. 下列排序算法中，
算法可能会出现下面情况：初始数据有序时，花费
的时间反而最多。
b．冒泡排序
c．快速排序
d. SHELL排序
二、判断题（每小题1分，共10分）
）在循环队列中，若尾指针Rear 大于头指针Front ，则其元素个数为
Rear - Front。
）串是n 个字母的有限序列（n >= 0）。
）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。
）二叉树只能采用二又链表来存储。
）有向图用邻接矩阵表示后，顶点i 的出度等于第i 行中非0且非加
的元素个数。
）图G 的某一最小生成树的代价一定小于其他生成树的代价。
）给定结点数的平衡二叉树的高度是唯一的。
）9阶B 树中，除报以外的任一结点中的关键字个数不少于4。
）只有在初始数据表为倒序时，冒泡排序所执行的比较次数最多。
）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将
被调到“叶子结点”上。
三、项空（每小题2分，共20分）
Word文档免费下载：
全国高等教育自学考试数据结构模拟试题2 一、单项选择题(本大题共 15 小题,每小题 2 分,共 30 分) 在每小题列出的四个备选项中只有一个是符合题目要求的,...《数据结构》期末考试试题及答案 ( 学年第 2 学期) 贵州大学理学院数学系信息与计算科学专业 一、 单项选择题 1.对于一个算法,当输入非法数据时,也...数据结构模拟试卷二_IT认证_资格考试/认证_教育专区。数据结构模拟试卷二一、填空...数据结构模拟试卷(一) 5页 免费 《数据结构》模拟试卷一 5页 免费 数据结构模...数据结构C++模拟卷子2 数据结构C++模拟卷子1期末复习数据结构C++模拟卷子1期末复习隐藏&& 第1 题.( 复合题 共计 20 分) 简答题 第 1.1 题.(主观 题 5 分...《数据结构》期末考试试题及答案 ( 学年第 2 学期) 贵州大学理学院数学系信息与计算科学专业 一、 单项选择题 1.对于一个算法,当输入非法数据时,也...数据结构模拟试卷(二)_从业资格考试_资格考试/认证_教育专区。 任何节约归根到底是时间的节约。——马克思数据结构模拟试卷(二) 学年学期 考核方式闭卷课程名称数据...数据结构模拟试卷2答案 3页 免费 《数据结构》模拟试卷二 3页 免费 数据结构模拟试卷(二) 3页 免费 长沙理工大学数据结构模拟... 4页 5财富值喜欢...1/2 专题推荐 《数据结构》模拟试卷一 《数据结构》模拟试卷三 《数据结构》模拟试卷四 《数据结构》模拟试卷五 《数据结构》模拟试卷六 《数据结构》模拟试卷七...模拟试卷一一、 单选题(每题 2 分,共 20 分) 1. 以下数据结构中哪一个是线性结构?( ) A. 有向图 B. 队列 C. 线索二叉树 D. B 树 2. 在一个单...数据结构各校研究生考题及答案下载_计算机_试卷_学海网
您现在正在浏览：&>&&>&&>&数据结构各校研究生考题及答案
数据结构各校研究生考题及答案
数据结构各校研究生考题及答案
第1章 绪论
一、选择题
1. 算法的计算量的大小称为计算的（
）。【北京邮电大学2000 二、3 （20/8分）】
2. 算法的时间复杂度取决于（ ）【中科院计算所 1998 二、1 （2分）】
A．问题的规模
B. 待处理数据的初态
3.计算机算法指的是（1），它必须具备（2） 这三个特性。
(1) A．计算方法
B. 排序方法
C. 解决问题的步骤序列
D. 调度方法
(2) A．可执行性、可移植性、可扩充性
B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性
D. 易读性、稳定性、安全性
【南京理工大学 1999 一、1（2分） 【武汉交通科技大学 1996 一、1（ 4分）】
4．一个算法应该是（
）。【中山大学 1998 二、1（2分）】
B．问题求解步骤的描述
C．要满足五个基本特性
第2章 线性表
第5章 数组和广义表
第8章 动态存储管理
第9章 集合
资料文件预览
共3文件夹，21个文件，文件总大小：4.64MB，压缩后大小：980.27KB
数据结构各校研究生考题及答案
目前最完整的数据结构1800题包括完整答案（word版本）
数据结构资料
动态存储管理答案.doc&&[52.50KB]
数组和广义表.doc&&[164.50KB]
排序.doc&&[262.50KB]
第10章 排序答案.doc&&[484.00KB]
第1章 绪论.doc&&[73.50KB]
线性表.doc&&[218.50KB]
线性表答案.doc&&[243.50KB]
栈和队列.doc&&[100.50KB]
树和二叉树答案.doc&&[781.00KB]
第9章 查找答案.doc&&[233.50KB]
图.doc&&[593.00KB]
栈和队列答案.doc&&[204.50KB]
集合.doc&&[199.50KB]
第五章 数组和广义表答案.doc&&[247.00KB]
第八章 动态存储管理.doc&&[34.50KB]
第六章树和二叉树.doc&&[507.50KB]
文件答案.doc&&[60.00KB]
文件.doc&&[47.00KB]
串.doc&&[90.50KB]
第四章 串答案.doc&&[99.00KB]
绪论答案.doc&&[51.00KB]
[ 下载 ]&&&&&（需要: 10 个学海币）&&&&&
Q: 为什么我下载的文件打不开？
A: 本站所有资源如无特殊说明，解压密码都是www.xuehai.net，如果无法解压，请下载最新的软件。
Q: 我的学海币不多了，如何获取学海币？
A: 上传优质资源可以获取学海币，详细见。
Q: 为什么我下载不了,但学海币却被扣了？
A: 由于下载人数众多，下载服务器做了并发的限制。请稍后再试，48小时内多次下载不会重复扣学海币。
下载本文件意味着您已经同意遵守以下协议
1. 文件的所有权益归上传用户所有。
2. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
3. 学海网仅提供交流平台，并不能对任何下载内容负责。
4. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
5. 本站不保证提供的下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
试卷相关下载
计算机试卷下载排行榜
计算机试卷最近更新