第1页，共5页
一、 写出以下各词语的对应中文
queue 队列 singly linked lists 单链表
storge structure 数据结构 time complexity 时间复杂度
Abstract Data Type (ADT) 抽象数据类型
二、 选择题
1、在数据结构中，线性结构中元素之间存在_A___关系。
A: 一对一
B: 一对多
C: 多对一
D: 多对多
2、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的B____和运算等的学科。
A: 结构
B: 关系
C: 操作
D: 算法
3、算法分析的两个主要方面是_A___。
A: 空间复杂度和时间复杂度
B: 正确性和简明性
C: 可读性和文档性
D: 数据复杂性和程序复杂性
4、顺序表中逻辑上相邻的节点其物理位置也_A___。
A: 一定相邻
B: 不必相邻
C: 按某种规律排列
D: 无要求
5、下面两个图各表现一批数据的结构，其中 C 。
A: 左边表现的是逻辑结构，右边表现的是物理结构
B: 右边表现的是逻辑结构，左边表现的是物理结构
C: 两者表现的都是逻辑结构
D: 两者表现的都是物理结构
第2页，共5页 6、 向一个长度为n的顺序表的第i个元素（1<=i<=n）之前插入一个元素时，需向后移动___D_个元素。
A: i
B: n-i
C: n-i-1
D: n-i+1
7、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行__C__。
A: s->next=p->next; p->next=s;
B: p->next=s->next; s->next=p;
C: q->next=s; s->next=p;
哈尔滨工业大学
二〇〇七年硕士研究生考试模拟试题（二）
考试科目：计算机专业基础
适用专业：计算机科学与技术
I 数据结构（含高级语言）部分（共75分）
一、填空题（每空1分，共15分）
1. 若以{4，5，6，7，8，9，10}作为叶子结点的权值构造Huffman树，则其带权路径长度是 。
2. 假定K个关键字互为同义词，若用线性探测再散列法把这K个关键字存入散列表中，至少要进行 次探测。
3. G是一个非连通无向图，共有28条边，则该图至少有 个顶点。
4. 若一个具有N个顶点，K条边的无向图是一个森林（N>K），则该森林中必有 棵树。
5. 设S为一个长度为N的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为 。
6. 若已知一个栈的入栈序列是1，2，3，…….，n，其输出序列为123,,,......,npppp，若1pn，则ip 。
7. 循环队列用数组[0,......,1]Am存放其元素值，已知其头尾指针分别为Front和Rear，则当前队列中的元素个数为 。
8. 从一个具有N个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 个结点。
9. 在一棵树中，度为1的结点的个数为1n，度为2的结点的个数为2n，……，度为m的结点的个数为mn，则该树有 个叶子结点。
10. 二叉树的前序序列和中序序列相同的条件是 。
11. 某二叉树的中序遍历序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的前序序列为 ，该二叉树对应的森林包括 棵树。
12. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。
☆自考乐园---心境随缘，诚与天下自考人共勉！！！
☆自考乐园---分享快乐，你的快乐老家！！！☆自考乐园---引领成功，你的精神乐园！！！
☆自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.........
俱乐部名称：自考乐园;俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id，可以直接进入俱乐部）;俱乐部url地址：/club/5346389（您也可以通过此url进入俱乐部。） 自学考试《数据结构》复习指导
第一章：绪论
一、概念：
数据结构：是一门研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。
数据：是描述额观事物的数、字符以及所有能输入到计算机中被计算机程序加工处理的信息的集合。
数据元素：数据元素是数据的基本单位。（一个数据项或多个数据项（域）。数据项是数据的最小单位。结点、顶点、记录。
数据对象：是性质相同的数据元素的集合。
数据结构：研究是是数据元素之间抽象化的相互关系和这种关系在计算机中的存贮表示，并对每种结构定义各自的运算，设计出相应的算法，而且经过运算后所得的新结构一般仍然是原来的结构类型。
数据类型：是指程序设计语言中各变量可取的数据种类。
算法：是执行特定计算的有穷过程。特点：
·动态有穷·确定性·输入·输出·可行性。
第二章 线性
表和数组
概念：
一、线性表：是N个元素构成的有限序列。
顺序存贮结构：地址计算，插入、删除。
链式存贮结构：单链表，查找、插入、删除。
循环链表：
双向链表： ☆自考乐园---心境随缘，诚与天下自考人共勉！！！
☆自考乐园---分享快乐，你的快乐老家！！！☆自考乐园---引领成功，你的精神乐园！！！
☆自考乐园俱乐部，专注于自考，致力于成为全国最全，最优的自考学习交流，资料共享平台.........
《数据结构》复习重点知识点归纳
一．数据结构的章节结构及重点构成
数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，
树和二叉树，图，查找，内排，外排，文件，动态存储分配。
对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大
多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上
可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有
在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。
按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：
·概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。
·线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型
算法设计题，如果有，也是与其它章节内容相结合。
·栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考
查，也常与递归等概念相联系进行考查。
·串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的
是根据KMP进行算法分析。
·多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，
是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与
“查找，排序”等章节结合来作为大题考查。
·树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是
否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章
都曾有过出大型算法设计题的历史。
·图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型
当中，可与树一章共同构成算法设计大题的题型设计。
·查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析
型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可
以与树一章结合来考查。
