考试日期：2006年4月30日
一、 选择题（2分×8 = 16分）
1. 以下数据结构中，是非线性数据结构的是 。
A. 树 B. 字符串 C. 数组 D. 栈
2. 下列程序段的渐进时间复杂度为 。
for( int i=1;i<=n;i++)
for( int j=1;j<= m; j++)
A[i][j] = i*j ;
A. O(m2) B. O(n2) C. O(m*n) D. (m+n)
3. 数组A[0…5，0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址为 。
A. 1175 B. 1180 C. 1205 D.1210
4. 以下关于链式存储结构的叙述中， 是不正确的。
A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B.逻辑上相邻的结点物理上不必邻接
C.可以通过计算直接确定第i个结点的存储地址
D.插入、删除操作方便，不必移动结点
5. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、和e1，则栈S容量至少应该是 。
A. 6 B. 4 C. 3 D. 2
6. 以下关于广义表的叙述中，正确的是 。
A. 广义表是0个或多个单元素或子表组成的有限序列
B. 广义表至少有一个元素是子表
C. 广义表不可以是自身的子表
D. 广义表不能为空表
7. 先序遍历序列与中序遍历序列相同的二叉树为 。
A. 根结点无左子树的二叉树
B.根结点无右子树的二叉树
C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树
D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树
8. 在有n 个叶子结点的霍夫曼树中，其结点总数为： 。
A. n B. 2n C. 2n +1 D. 2n - 1
二、 填空题（2分×5 =10分）
1. 一个算法具有5个特性： 、 、 、有零个或多个输入，一个或多个输出。
2. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。
3. 字符串“abcd”中共有 个长度大于0的字串。
4. 广义表list=（5，（3，2，（14，9，3），（），4），2，（6，3，10））的长度及深度分别为 和 。
5. 具有n个结点的完全二叉树的高度为
三、 名词解释（24分）
（1）抽象数据类型
（2）完全二叉树
（3）堆
四、 简答题（30分）
1. 请对线性表进行顺序存储和链式存储的特点作比较。
2. 假设有一个适当大小的栈S，输入栈的序列为A，B，C，D，E。问：
（1）能否得到下列的输出序列： ① B，C，D，c语言基本名词概念E，A； ② E，A，B，C，D；
③E，D，C，B，A。
（2）写出所有可能正确的输出序列。
3. 设一棵二叉树后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，要求：
（1）画出该二叉树；
（2）写出该二叉树的先序遍历序列；
（3）画出该二叉树对应的森林。
五、 算法设计题（20分）
1. 填充下列算法的空白处，完成在不带表头结点的单链表第i个结点之前插入新元素x的操作。（8分）
int Insert ( const int x, const int i ) { //在链表第 i 个结点处插入新元素 x
listNode *p = first; int k = 0;
while ( p != NULL && k< i -1 )
{① ; k++; } //第i-1个结点
if ( p == NULL && first != NULL ) { //非空表且链短，不到i-1个节点
cout << “Invalid position for Insertation!\n”; return 0;
}
listNode *newnode= new Node(x, NULL);
if ( first == NULL || i == 0 ) { //插入空表或插在非空表前
newnode→link = first;
if ( first == NULL ) last = newnode;
② ; // 修改首指针
}
else { //插在表中或末尾
③ ;
if ( p→link == NULL ) last = newnode;
④ ;
}
return 1; //正常插入，函数返回1
}
2. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法（12分）：
（1）统计二叉树中叶子结点的个数；
（2）交换每个结点的左子女和右子女。
选做题（20分）
（西安电子科技大学2006年硕士研究生入学考试最后一题）
假设以数组seq[0…m-1]存放循环队列中的元素，同时设变量rear和quelen分别指示循环队列中的队尾元素的位置和内含元素的个数。请给出：
（1）给出循环队列的队满条件和队空条件；
（2）写出相应的入队列和出队列的算法，并分别分析其时间代价；
（3）如果用数组sequ[m…n]来存放循环队列中的元素，则（2）中的入队列和出队列的算法中的哪些语句要修改？如何修改？
哈尔滨工业大学
二00一 年研究生考试试题
考试科目：数据结构 报考专业：计算机科学与技术
一． 填空（总分：10分，每一题2分）
1． 对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________, 在给定为x的结点后插入一个新结点的时间复杂度为________。
2． 广义表（a，（a，b），d，e，( (I,j,), k) ）的长度是________, 深度是________。
3． 对于一个具有n个结点的二员树，当它为一棵________二元树时具有最小高度，当它为一棵_______时，具有最大高度。
4． 在顺序文件中，要存取第I个记录，必须先存取______个记录。
5． 求最短路径的dijkstra算法的时间复杂度为________。
二．选择填空：（总分10分，每小题2分）
1． 若某线性表最常用的操作是存取任意指定序号的元素和最后进行插入和删除运算，则利用______存储方式最节省时间。
（1） 顺序表； （2）双链表；
（3） 头结点的双循环链表；
（4） 单循环链表
2． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为______个
（1）4 （2）5 （3）6 （4）7
3． 在一个图中，所有顶点的度数之和等于所有边数______倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的_____倍
（1） 1/2 （2）2 （3）1 （4）4
4． 下列排序算法中，________,排序在某趟结束后不一定能选出一个元素放到其最终的位置上。
（1）选择 （2）冒泡 （3）归并 （4）堆
5． 散列文件使用散列函数将记录的关键字值计算转化为记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的_______方法是散列文件的关键。
（1）散列函数 （2）除余法中的质数
（3）冲突处理 （4）散列函数和冲突处理
三 回答下列问题 （总分15分，每小题3分）
1 数据结构与数据类型有什么区别？
2 什么是循环队列？
3 简述线索二元树的概念。
4 何为有向图的遍历？
5 什么是索引顺序文件？
四．分别画出和下列树对应的各个二元树。
五．试设计一个算法，判断链表L是否是递减的。
六．判断以下序列是否为堆，如果不是，则把它调整为堆。
(1) (12,24,33,65,33,56,48,92,86,70)
(2) (25,56,20,23,40,38,29,61,35,76,28,100)
七．设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O…maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。
八．假设用于通讯的电文仅有6个字母abcdef组成，字母在电文中出现的频率分别为7，19，5，16，42，11。试为这6个字母设计哈夫曼编码
九．试写一算法，判断以邻接表方式存储的有向图中是否存在有顶点Vi到顶点Vj的路
发表评论