华为数据结构笔试题

数据结构笔试题题目

一、 选择题

1. 下面哪种排序法对123456798在空间和时间上最优( )

A. 快速排序 B. 冒泡排序 C. 插入排序 D. 堆排序

2. 2.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（ ） A．堆排序〈 快速排序〈归并排序 B．堆排序〈 归并排序〈 快速排序 C．堆排序〉 归并排序 〉快速排序 D．堆排序 > 快速排序 > 归并排序 E．以上答案都不对

3. 3.一株二叉树的以某种遍历方式的序列为A、B、C、D、E、F、G，.若该二叉树的根结

点为E,则它的一种可能的前序遍历为____ ,相应的后序遍历为____

A. ECBADFG, BDCAFGE C. ECBADGF, EACBDGF

B. ECBADFG, EFACDBG D. EACBDGF, BDCAFGE

（常见题型，给出树的前序遍历和中序遍历，中序和后续遍历，推出二叉树） 4. 关于图和树，下面说法正确的是________

A. 树和图都允许有环

B. 图的深度遍历和广度遍历结果可能一样 C. 二叉树是每个节点都有两个孩子节点的树

D. 二叉树的前序遍历和后序遍历结果肯定不一样

5. 完成在双循

第一章 数据结构与算法

一.算法的基本概念

计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 1.算法的基本特征：可行性，确定性，有穷性，拥有足够的情报。 2.算法的基本要素：算法中对数据的运算和操作、算法的控制结构。

3.算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。 4.算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求

二.算法的复杂度

1.算法的时间复杂度：指执行算法所需要的计算工作量 2.算法的空间复杂度：执行这个算法所需要的内存空间

三.数据结构的定义

1.数据的逻辑结构：反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。

2.数据的存储结构：数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。

四.数据结构的图形表示：

在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。

五.线性结构和非线性结构

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构

数据结构

1.采用折半搜索算法长度为n的有序表时，元素的平均搜索长度为（）

A)O(n2)

B)O(nlog2n)

C)O(log2n)

D)O(n)

2.下面程序的时间复杂度为（）

for(int i=0;i

{

for(int j=0;j

{

a[i][j] = i * j;

}

}

A)O(m2);

B)O(n2);

C)O(m*n);

D)O(m+n);

3.下列叙述中，正确的是（）

A)线性表中的个元素在存储空间中的位置必须是连续的

B)线性表中的表头元素一定存储在其他元素的前面

C)线性表中的个元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面

D)线性表中的个元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的

4.已知二叉树后序遍历序列是edcfba，中序遍历序列deacbf，它的前序遍历序列是（）;

5.如果进栈序列为e1,e2,e3,e4 ，则可能的出栈序列是（）;

6.对长度为n的字符串进行字符定位运算的时间复杂度为（）;

A)O(1)

B)O(根号n)

C)O(nlog2n)

授课：XXX

D)O(n)

7.n个顶点的连通图中边得条数至少为（）

8.合并两个已经排好序的长度为n的Array,最坏情况下需要比较多少次（）

A)2n

B)2n-1

C)2n

常见的算法习题,填空题,基础知识汇总

二、填空题：

1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和___运算___________。

2、数据结构算法中，通常用时间复杂度和____空间复杂度______________两种方法衡量其效率。

3、一个算法一该具有__有穷性____,__确定性____,__可行性__,___输入___和_输出___这五种特性。

4、若频繁地对线性表进行插入与删除操作，该线性表应采用_链式___________存储结构。

5、在非空线性表中除第一个元素外，集合中每个数据元素只有一个_直接前驱______；除最后一个元素之外，集合中每个数据元素均只有一个___直接_后继_____。

6、线性表中的每个结点最多有__一个_直接___前驱和______一个直接___后继。

7、____循环__链表从任何一个结点出发，都能访问到所有结点。

8、链式存储结构中的结点包含__指针__________域，________数据_______域。

9、在双向链表中，每个结点含有两个指针域，一个指向___前驱__结点，另一个指向__后继______结点。

10、某带头结点的单链表的头指针head，判定该单链表非空的条件__head->nex

2009年全国硕士研究生入学统一考试

计算机科学与技术学科联考 计算机学科专业基础综合

考试大纲 教育部考试中心

中国学位与研究生教育学会工科工作委员会

目 录

I. 考查目标

II. 考试形式和试卷结构考查范围 III. 考查范围

数据结构 计算机组成原理 操作系统 计算机网络 IV.

试题示例

Ⅰ.考查目标

计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅱ.考试形式和试卷结构

一、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 45分 计算机组成原理 45分

- 1 -

操作系统 35分 计算机网络 25分 四、试卷题型结构

单项选择题 80分（40小题，每小题2分） 综合应用题 70分

Ⅲ.考查范围

数据结构

【考查目标】

1.理解数据结构的基本概念；掌握数据的逻辑结构

您所在位置：数据结构网络教学平台>>> 试卷汇粹>>数据结构试题汇总

一、选择题

第一二章

1．数据结构是一门研究计算机中____对象及其关系的学科。 （1）数值运算 （2）非数值运算 （3）集合 （4）非集合

2．数据结构的定义为(K，R)，其中K是____的集合。 （1）算法 （2）数据元素 （3）数据操作 （4）逻辑结构 3．算法分析的目的是____。 （1） 找出数据结构的合理性 （2） 研究算法中输入和输出的关系 （3） 分析算法的效率以求改进

（4） 分析算法的易懂性和文档性

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。 （1）s->link=p;p->next=s;

（2）s->link=p->link;p->link=s; （3）s->link=p->link;p=s;

（4）p->link=s;s->link=p;

5．在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是____。

（1）current->link=NULL (2)first->link=current

（3）first=current (

您所在位置：数据结构网络教学平台>>> 试卷汇粹>>数据结构试题汇总

一、选择题

第一二章

1．数据结构是一门研究计算机中____对象及其关系的学科。 （1）数值运算 （2）非数值运算 （3）集合 （4）非集合

2．数据结构的定义为(K，R)，其中K是____的集合。 （1）算法 （2）数据元素 （3）数据操作 （4）逻辑结构 3．算法分析的目的是____。 （1） 找出数据结构的合理性 （2） 研究算法中输入和输出的关系 （3） 分析算法的效率以求改进

（4） 分析算法的易懂性和文档性

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。 （1）s->link=p;p->next=s;

（2）s->link=p->link;p->link=s; （3）s->link=p->link;p=s;

（4）p->link=s;s->link=p;

5．在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是____。

（1）current->link=NULL (2)first->link=current

（3）first=current (

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质

2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？

4、 哈希方法的基本思想

5、 给出一不稳定排序方法名称与实例

二、 构造结果：[24分]

（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。

（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．

（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i

院、系领导 审批并签名

A / B卷 广州大学 2009-2010 学年第 二 学期考试卷

课程 数据结构 考试形式（开卷/闭卷，考试/考查）学院

系 专业 班级 学号 姓名_ 题次 分数 评分 一 10 二 20 三 10 四 30 五 30 六 七 八 九 十 总分 评卷人 100 一、单项选择题（10分，每小题1分）

1、 输出一个二维数组b[m][n]中所有元素值的时间复杂度为（ ）。

A. O(n) B. O(m+n) C. O(n2) D. O(m*n)

2、在一个长度为n的顺序表中删除一个值为x的元素时，需要比较元素和移动元素的总次数为（ ）。

A. (n+1)/2

B. n/2

C. n

D. n+1

3、 设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头结点。若想在指针p

所指结点之后插入指针s所指结点，则应执行下列哪一个操作？

A. p->rLink = s; s->lLink = p

数据结构试题B卷

一、单选题（每小题2分，共8分）

1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。

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

2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。

A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 3、 栈的插入和删除操作在（ ）进行。

A 栈顶 B 栈底 C 任意位置 D 指定位置

4、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）

A 24 B 71 C 48 D 53 二、填空题（每空1分，共32