河南工业大学
xxxx年硕士研究生入学考试试题
考试科目：数据结构共 4 页（第1 页）
注意：1、本试题纸上不答题，所有答案均写在答题纸上
2、本试题纸必须连同答题纸一起上交。
一、选择题（本题30分,每小题2分）
1. 导致栈上溢的操作是（）。
A) 栈满时执行出栈B) 栈满时执行入栈
C) 栈空时执行入栈D) 栈空时执行出栈
2. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8，j的值为1 到10，数组从内存首地址10000开始顺序存放，当用以列为主存放时，元素A[5, 8]的存储首地址为( )。
A. 10000+141
B. 10000+180
C. 10000+183
D. 10000+225
3. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。
A. (c,d)
B. c,d
C. ((c,d))
D. ((a,b),(c,d))
4. 由3 个结点可以构造出多少种不同的二叉树？（）
A. 2
B. 3
C. 4
D. 5
5. 栈和队列的共同点是（）
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点
6.一棵具有n个结点的完全二叉树的树高度（深度）是（）
A．⎣log2n⎦+1 B．log2n+1 C．⎣log2n⎦D．log2n-1
7. n个结点的线索二叉树上含有的线索数为（）
A. 2n
B. n－l
C. n＋l
D. n
8. 在下面的程序段中，对x的赋值语句的频度为（）
for(i=1;i<n;i++)
for(j=1;j<n;j++)
x=x+1;
A．O(2*n) B．O(n) C．O(n2) D．O(log2n)
9. 执行完下列语句段后，i值为：（）
int f(int x)
{ return ((x>0) ? x* f(x-1):2);}
int i ;
i =f(f(1));
A．2 B. 4 C. 8 D. 无限递归
10.下面关于串的的叙述中，哪一个是不正确的？（）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储11.对稀疏矩阵进行压缩存储目的是（）。
A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度
12．设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非
共 4 页（第 2 页）
空且不同于S本身）的个数为（）。
A．2*n-1 B．n2 C．(n2/2)+(n/2) D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1
13．有关二叉树下列说法正确的是（）
A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
14.设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
15.下列排序算法中，其中（）是稳定的。
A. 堆排序，冒泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，冒泡排序
二、是非题（本题20分,每小题2分）
1.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据元素相互之间的关系称为结构。
根据数据元素之间关系的不同特性，通常有下列四种基本结构：集合、线性结构、树形结构、图状结构（网状结构）。
2.对任何数据结构链式存储结构一定优于顺序存储结构。
3. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。
4.设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。
5.稀疏矩阵压缩存储后，必会失去随机存取功能。
6. 完全二叉树一定存在度为1的结点。
7. 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。
8. 排序算法中的比较次数与初始元素序列的排列无关。
9. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
10.散列函数越复杂越好，因为这样随机性好，冲突概率小.
三、填空题（本题20分,每小题2分）
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。
2. 循环队列的引入，目的是为了克服。
3.空格串是指，其长度等于。
4. 二叉树由，，三个基本单元组成。
5.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是
算法，最费时间的是算法。
6.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为次；当使用监视哨时，若查找失败，则比较关键字的次数为。
7. 在数据表有序时，快速排序算法的时间复杂度是。
8.深度为k的完全二叉树至少有个结点，至多有个结点。
9.数据结构中评价算法的两个重要指标是、。
10.直接插入排序用监视哨的作用是。
四、简答题（本题 40 分）
1. （5分）若一棵二叉树的中序遍历结果为DBEAFGC，前序遍历结果 ABDECFG，请画出该二叉树。
共 4 页（第 3 页）
2. （5分）用克鲁斯卡尔（KRUSKAL）方法求下面网的最小生成树，要求画出中间步骤。
（5分）
3. （10分）假设用于通信的电文由字符集{a, b, c, d, e, f, g}中的字母构成。
它们在电文中出现的频度分别为{0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04}，为这7个字母设计哈夫曼编码。
（要求画出哈夫曼树和写出编码结果，其中左子树权值小于右子树权值。
编码时左边0，右边1）
4. （10分）设哈希函数H（k）=k %7, 哈希表的地址空间是0~6，对关键字序列（19, 01, 23, 14, 55, 68, 11, 36），画出按链地址法解决冲突产生的哈希表。
5. （5分）求下图的关键路径。
（要求只画出关键路径部分，并计算关键路径长度）。
6. （5分）设待排序关键字序列{16，14，24，11，8，12，15}，请画出其堆排序的初始建堆(小顶堆)的过程。
共 4 页（第 4 页）五、算法分析(本题40分，每题20分）
1. （20分）双向链表的存储结构描述如下：
Typedef struct DuLNode{
ElemType data;
Struct DuLNode *prior;
Struct DuLNode *next;
}
请写出在带头节点的双向链表L中的第i位置之前插入元素e的算法。
其中已经定义
Struct DuLNode *GetElemp_DuL(DuLinkList &L,int i,); 表示在L中确定第i个元素的位置指针。
Status ListInsert_DuL(DuLinkList &L,int i, ElemType e)
{ Struct DuLNode *p，*s;
2.(20分)请写出先序遍历二叉树（链式存储结构）算法。
其中类型定义和Visit 函数已经如下定义。
Typedef struct BiTnode{
TElemType data;
Struct BiTnode *lchidl,*rchild; //左右孩子指针
｝BiTnode，*BoTree;
Status Visit(TElemType e)；//输出元素e的值
Status PreOrderTraverse(BiTree T，status （*visit）(TElemType e))
{
}。