当前位置：文档之家 › 解放军信息工程大学2016年《820数据结构》考研专业课真题试卷

解放军信息工程大学2016年《820数据结构》考研专业课真题试卷

  • 格式：pdf
  • 大小：328.29 KB
  • 文档页数：5

第1页 共5页 820数据结构 （共十一题，满分150分） 一、填空题（20分，每空2分） 1.数据的存储结构可用四种基本的存储方法表示，它们分别是 、 、 和 。 2. 算法是指 。 3. 在n个结点的单链表中要删除已知结点*p，需找到它的 ，其时间复杂度为 。 4. 设串s1=‘ABCDEFG’，s2=‘PQRST’， 则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是 。 5. 设数组a[1…100]的基地址为128，每个元素占2个存储单元，采用顺序存储方式存储，则元素a[52]的存储地址为 。 6. 一个广义表为L= ((a,b),(c,d),(e,f))，则 GetHead ( GetTail ( GetTail (L))) 为 。 二、选择题（20分，每题2分） 1.设某棵二叉树的先序遍历序列为ABCDE，中序遍历序列为BADCE，则后序遍历该二叉树得到序列为（ ）。 (A)BCDEA (B) BDECA (C) ACDEB (D) BADEC 2. 设一组初始记录关键字序列(54，29，62，30，86)，以第一个记录关键字54为基准进行一趟快速排序的结果为（ ）。 (A) 29，30，54，86，62 (B) 30，29，54，86，62 (C) 29，30，62，54，86 (D) 30，29，54，62，86 3．最坏情况下，在二叉排序树中插入一个结点的时间复杂度为（ ）。 (A) O(1) (B) O(n2) (C) O(log2n) (D) O(n) 4．下列四种排序中，（ ）的空间复杂度最大。 (A) 快速排序 (B) 冒泡排序 (C) 归并排序 (D) 希尔排序 5. 设一采用顺序存储的一组元素，其关键字序列为 (2,8,21,37,51,78,89,92,99)，则用二分查找方法查找关键字为68的元素时关键字比较次数为（ ）。

合集下载

2020 年招收攻读硕士学位研究生入学统一考试试题(中国科学院大学)计算机专业综合

2020 年招收攻读硕士学位研究生入学统一考试试题(中国科学院大学)计算机专业综合

中国科学院大学

2020年招收攻读硕士学位研究生入学统一考试试题

科目名称：计算机专业综合

考生须知：

1．本试卷满分为150分，全部考试时间总计180分钟。

2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

3．试卷共16道大题，每题15分，共240分，考生可以任意选择其中10道大题

回答，并在答题纸的该题答案前标明“选做本题”。

4．如果选做的题目多于10道，则判卷将按照所选做试题的题号顺序选择前10道

大题计分，后续所做视为无效考试内容。

第一部分：《数据结构》

第一题，简答题，共15分

（1） 请给出下列程序的时间复杂度（n>0）。（2分）

void func(int n) {

int i,j;

for(i=1,j=0; j<=n; j=j+i) i++;

}

（2） 现有一个线性表的应用，线性表的元素总数不确定，其主要的操作是插入

元素、删除表尾元素、查找表尾结点和查找指定结点的前驱结点，那么请问用怎

样的数据结构比较好？请给出理由和该数据结构的C语言定义。（3分）

（3） 若循环队列存储在数组A[0..m]，头指针Front指向当前队头元素，尾指针

Rear指向当前队尾元素的下一个位置，那么当前实际存储有多少队列元素？现有

元素x需要入队，请写出元素入队的语句。（3分）

科目名称：计算机专业综合 第1页 共6页

（4） 用如下数据结构存储广义表：

typedef enum {ATOM, LIST} ElemTag;

typedef struct GLNode {

ElemTag tag;

union {

AtomType atom;

struct {struct GLNode *hp, *tp;} ptr;

}

} *Glist;

那么，对于广义表X=(A,((),(B,C)),(D,E))，给出其存储结构图，并利用Head、Tail

操作分离出元素E。（3分）

（5） 现在需要从5000个元素组成的序列中，用最快的速度挑出前10个最大的

江西师范大学计算机信息工程学院数据结构与程序设计历考研真题汇编附答案

江西师范大学计算机信息工程学院数据结构与程序设计历考研真题汇编附答案

目 录

第一部分 历年考研真题汇编 ..........................................................................................................................

2014年江西师范大学计算机信息工程学院863数据结构与程序设计考研真题....................................................................................................................................................................

2013年江西师范大学计算机信息工程学院863数据结构与程序设计考研真题....................................................................................................................................................................

第二部分 兄弟院校真题汇编 ..........................................................................................................................

2013年北京航空航天大学991数据结构与C语言程序设计考研真题 ...........................................

2012年北京航空航天大学991数据结构与C语言程序设计考研真题 ...........................................

大学课后习题答案尽在此

大学课后习题答案尽在此

3500份课后答案，很值得收藏，这里只介绍了一部分。

还有很多，可以去课后答案网（/bbs）查找。

##################【公共基础课-答案】####################

新视野大学英语读写教程答案（全）【khdaw】

/bbs/viewthread.php?tid=108&fromuid=801904

概率论与数理统计教程 (茆诗松 著) 高等教育出版社 课后答案

/bbs/viewthread.php?tid=234&fromuid=801904

高等数学（第五版）含上下册 高等教育出版社 课后答案

/bbs/viewthread.php?tid=29&fromuid=801904

新视野英语听力原文及答案 课后答案【khdaw】

/bbs/viewthread.php?tid=586&fromuid=801904

线性代数 (同济大学应用数学系 著) 高等教育出版社 课后答案

/bbs/viewthread.php?tid=31&fromuid=801904

21世纪大学英语第3册（1-4）答案【khdaw】

/bbs/viewthread.php?tid=285&fromuid=801904

概率与数理统计 第二,三版 (浙江大学 盛骤 谢式千 潘承毅 著) 高等教育出版社 课后答案

/bbs/viewthread.php?tid=32&fromuid=801904

复变函数全解及导学[西安交大 第四版]【khdaw】

/bbs/viewthread.php?tid=142&fromuid=801904

大学英语精读第三版2册课后习题答案

/bbs/viewthread.php?tid=411&fromuid=801904

线性代数(第二版)习题答案

/bbs/viewthread.php?tid=97&fromuid=801904

21世纪(第三册)课后答案及课文翻译（5-8）【khdaw】

2016年南京大学842数据结构、软件工程、操作系统和计算机网络考研真题【圣才出品】

2016年南京大学842数据结构、软件工程、操作系统和计算机网络考研真题【圣才出品】

1 / 5 十万种考研考证电子书、题库视频学习平台 圣才电子书 2016年南京大学842数据结构、软件工程、操作系统和计算机网络考研真题（回忆版） 今年专业课继去年风格大变之后，果然又一次改变了出题方式，不再像前几年的类408风格，感觉有点走回南大08年统考前命题风格，今年一道选择题都没出。 数据结构（45分） 总共四道大题，一道计算，三道算法 一、计算题 1．hash表（软院06年期末题）设散列表长度为11，散列函数H（K）＝（K的第一个字母在英文字母表中的序号，设A的序号为1）%11，若输入顺序为（B，D，M，CI，I，K，TM，X），处理冲突方法为线性探测法，要求： 1）构造此散列表。 2）对表中所有键值分别查找1次，求出总的比较次数。 二、算法题 1．长度为n的数组a[0…n－1]，编写一个算法在O（n）的时间复杂度内将数组中所有负数放在非负数前面。 2．已知first为不带表头结点的单链表的表头指针（如下图所示），链表中存储的都是

2 / 5 十万种考研考证电子书、题库视频学习平台 圣才电子书 整型数据，试写出求所有结点的data域平均值的递归函数。（软院05年数据结构期末题） 3．假设以数组Q[m]存放循环队列中的元素，同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数，试用C＋＋语言写出一个程序，给出该循环队列的类声明，给出队空条件和队满条件，并写出相应的插入元素（Add）和删除（Delete）元素的算法（用类模板，函数模板形式写）（软院04年考研原题） 软件工程（45分） 两道问答题以及三道大题 一、问答题 1．软件质量保障常用的是哪三种手段？（5分） 2．给了5个需求描述，说出他们分别是哪种类型的需求。（5分） 二、大题 1．分析ATM机的取款操作，编写他的用例。（10分） 2．分析下面代码违反了哪个面向对象原则？有什么后果？应如何改进？（10分）

文档推荐

最新文档