首页 - 网校 - 万题库 - 美好明天 - 直播 - 导航
热点搜索
学员登录 | 用户名
密码
新学员
老学员
您现在的位置: 考试吧 > 考研 > 考研模拟试题 > 考研专业课模拟试题 > 考研专业课 > 正文

2015年计算机考研数据结构测试题及答案(四)

来源:考试吧 2014-9-4 16:39:09 要考试,上考试吧! 考研万题库
2015年计算机考研数据结构测试题(四),更多2015考研资讯,复习指导,经验技巧等信息,敬请关注考试吧考研网!

  一、选择题(30分)

  1.设某无向图有n个顶点,则该无向图的邻接表中有( )个表头结点。

  (A) 2n (B) n (C) n/2 (D) n(n-1)

  2.设无向图G中有n个顶点,则该无向图的最小生成树上有( )条边。

  (A) n (B) n-1 (C) 2n (D) 2n-1

  3.设一组初始记录关键字序列为(60,80,55,40,42,85),则以第一个关键字45为基准而得到的一趟快速排序结果是( )。

  (A) 40,42,60,55,80,85 (B) 42,45,55,60,85,80

  (C) 42,40,55,60,80,85 (D) 42,40,60,85,55,80

  4.( )二叉排序树可以得到一个从小到大的有序序列。

  (A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历

  5.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号,则编号为i结点的左孩子结点的编号为( )。

  (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1

  6.程序段s=i=0;do {i=i+1; s=s+i;}while(i<=n);的时间复杂度为( )。

  (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)

  7.设带有头结点的单向循环链表的头指针变量为head,则其判空条件是( )。

  (A) head==0 (B) head->next==0

  (C) head->next==head (D) head!=0

  8.设某棵二叉树的高度为10,则该二叉树上叶子结点最多有( )。

  (A) 20 (B) 256 (C) 512 (D) 1024

  9.设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字90需要比较的关键字个数为( )。

  (A) 1 (B) 2 (C) 3 (D) 4

  10.设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为( )。

  (A) top=top+1; (B) top=top-1;

  (C) top->next=top; (D) top=top->next;

  二、判断题(20分)

  1.不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑“溢出”情况。( )

  2.当向二叉排序树中插入一个结点,则该结点一定成为叶子结点。( )

  3.设某堆中有n个结点,则在该堆中插入一个新结点的时间复杂度为O(log2n)。( )

  4.完全二叉树中的叶子结点只可能在最后两层中出现。( )

  5.哈夫曼树中没有度数为1的结点。( )

  6.对连通图进行深度优先遍历可以访问到该图中的所有顶点。( )

  7.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。( )

  8.由树转化成二叉树,该二叉树的右子树不一定为空。( )

  9.线性表中的所有元素都有一个前驱元素和后继元素。( )

  10.带权无向图的最小生成树是唯一的。( )

  三、填空题(30分)

  1. 1. 设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为_________=p;s->right=p->right;__________=s; p->right->left=s;(设结点中的两个指针域分别为left和right)。

  2. 2. 设完全有向图中有n个顶点,则该完全有向图中共有________条有向条;设完全无向图中有n个顶点,则该完全无向图中共有________条无向边。

  3. 3. 设关键字序列为(Kl,K2,…,Kn),则用筛选法建初始堆必须从第______个元素开始进行筛选。

  4. 4. 解决散列表冲突的两种方法是________________和__________________。

  5. 5. 设一棵三叉树中有50个度数为0的结点,21个度数为2的结点,则该二叉树中度数为3的结点数有______个。

  6. 6. 高度为h的完全二叉树中最少有________个结点,最多有________个结点。

  7. 7. 设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是__________________________________。

  8. 8. 设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟简单选择排序结束后的结果的是__________________________________。

  9. 9. 设一棵二叉树的前序序列为ABC,则有______________种不同的二叉树可以得到这种序列。

  10. 10. 下面程序段的功能是实现一趟快速排序,请在下划线处填上正确的语句。

  struct record {int key;datatype others;};

  void quickpass(struct record r[], int s, int t, int &i)

  {

  int j=t; struct record x=r[s]; i=s;

  while(i

  {

  while (ix.key) j=j-1; if (i

  }

  _________________;

  }

  四、算法设计题(20分)

  1. 1. 设计在链式结构上实现简单选择排序算法。

  2. 2. 设计在顺序存储结构上实现求子串算法。

  3. 3. 设计求结点在二叉排序树中层次的算法。

  2015年考研:计算机数据结构测试题(四)答案

考研视频题库手机题库】 | 搜索公众微信号"566考研"

  相关推荐:

  2015考研招生简章专题最新文章

  2015考研专业课考试科目及题型结构

  2015考研报考指南:考研深造首选城市TOP10

  2015考研:考试吧考研政治智能题库 ※ 考试吧题库热点文章

看了本文的网友还看了
文章搜索
万题库小程序
万题库小程序
·章节视频 ·章节练习
·免费真题 ·模考试题
微信扫码,立即获取!
扫码免费使用
考研英语一
共计364课时
讲义已上传
53214人在学
考研英语二
共计30课时
讲义已上传
5495人在学
考研数学一
共计71课时
讲义已上传
5100人在学
考研数学二
共计46课时
讲义已上传
3684人在学
考研数学三
共计41课时
讲义已上传
4483人在学
推荐使用万题库APP学习
扫一扫,下载万题库
手机学习,复习效率提升50%!
版权声明:如果考研网所转载内容不慎侵犯了您的权益,请与我们联系800@exam8.com,我们将会及时处理。如转载本考研网内容,请注明出处。
官方
微信
扫描关注考研微信
领《大数据宝典》
下载
APP
下载万题库
领精选6套卷
万题库
微信小程序
帮助
中心
文章责编:menghaichao