数据结构模拟题目
- 格式：doc
- 大小：764.00 KB
- 文档页数：6
模拟题1
一、填空题
1. 数据结构的基本单位是 。
2. 从存储结构上讲，线性表的表示可分为 和链接两类。
3. 设顺序表长度为n，则删除第i（i = 1, 2, …, n）个元素需要移动 个元素。
4. 后缀表达式20 10 5 * ＋ 49 7 / － 的值为 。
5. 一棵二叉树中，若叶结点的个数为2005，则度为2的结点个数为 。
6. 遍历一棵二叉搜索树，将得到一个以关键字值递增排列的有序序列。
7. 5阶B树的高度为2时，树中元素个数最少为 。
8. 若有向图的拓扑排序不能输出所有的顶点，则该有向图存在 。
二、单项选择题
1. 若用单链表来表示队列,则选用 最好。 （ ）
A. 只带尾指针的非循环链表 B. 只带尾指针的循环链表
C. 只带头指针的非循环链表 D. 只带头指针的循环链表
2. 设有一个二维数组A[m][n]按行优先顺序存储，假设A[0][0]的地址是644，A[2][2]的地址是676，每个元素占1个单元，则A[4][5]的地址是 。
（ ）
A. 672 B. 626 C. 709 D. 724
3. 森林的后序遍历等价于其对应二叉树的 遍历。 （ ）
A. 先序 B. 中序 C. 后序 D. 按层
4. 具有10个顶点的连通图的深度优先搜索生成树，其边的数目为 。 （ ）
A. 9 B. 10 C. 11 D. 8
5. 下列说法错误的是 。 （ ）
A. 已知先序和中序遍历序列能唯一确定一棵二叉树
B. 已知后序和中序遍历序列能唯一确定一棵二叉树
C. 已知先序和后序遍历序列能唯一确定一棵二叉树
D. 已知先序遍历序列能唯一确定一棵二叉搜索树
6. 下列排序算法中，第一趟排序后能确定某个元素最终位置的算法是 。 （ ）
A. 直接插入排序 B. 快速排序 C. 两路合并排序 D. 以上均不对
7. 散列表采用线性探查法解决冲突会出现 现象。 （ ）
A. 二次聚集 B. 探查失败 C. 假溢出 D. 线性聚集
三、简答题
1. 给定稀疏矩阵（如下图所示），请写出该矩阵执行快速转置时用到的num[]和k[]的值。 012940300008030020100240600180007
2. 表长为11的散列表采用双散列法解决冲突，散列函数 h1(key)=key % 11，h2(key)=key %
9 +1。已知散列表目前如下：
下标 0 1 2 3 4 5 6 7 8 9
10
关键字 12 25 70
请问在该散列表中再依次插入关键字80、19、41后，散列表的情况如何？
3. 写出下图所有可能的拓扑序列。
12345
4. 使用普里姆（Prim）算法以A为源点，构造下图的最小代价生成树，要求画出构造过程中各步的结果。
CBFEAD101510685781212
5. 以37，45，25，14，91，43，27，26为输入序列构建二叉搜索树，
⑴ 画出该二叉搜索树；
⑵ 画出该二叉搜索树对应的森林。
6. 元素序列（60，21，19，7，15，28，4）按两路合并算法进行排序。
⑴ 写出各趟排序结果。
⑵ 两路合并排序平均情况下的渐近时间复杂度为多少？
7. 下图是一个三阶B-树，请画出依次删除50、10之后B-树。
5020 3560 7065 675575251036
8. 设字符集合S={A，E，I，O，U}，各字符的使用频率为W={20，10，17，5，25}。
⑴ 画出哈夫曼树；（构建新树时，新树根的左子树根的权值小于等于右子树根的权值，新树根的值是左、右子树根结点权值之和）
⑵ 求该哈夫曼树的带权路径长度。
四、程序填空题
下面的程序是顺序表的对半搜索的迭代算法，请补充完整。
template
int SeqList::BiSearch1(const T& x) const
{
int i, low=1,high=length;
while (low<=high)
{
i= ⑴ ;
if (x
else if (x>elements[i-1]) low=i+1;
else ⑶ ;
}
return 0;
}
五、程序阅读题
下面的程序是二叉树类的某个成员函数
template
void BTree::A(BTNode *p)
{ BTNode *q;
if (p)
{
q = p->lchild;
p->lchild = p->rchild;
p->rchild = q;
A(p->lchild);
A(p->rchild);
}
}
⑴ 请说明该成员函数的作用是什么？
⑵ 若指针p的指向如右上图所示，请画出执行该函数后的二叉树？
六、程序设计题(10分)
在单链表类SingleList中增加一个成员函数Print，输出单链表上所有大于x的元素。
（提示：单链表上的元素不是有序的；只要写出成员函数即可，注意成员函数的书写格式。）
1254367p模拟题2
一、填空题
1. 数据的逻辑结构是指 。
2. AOV网中的领先关系是一种拟序关系，它具有传递性和 。
3. 队列中，允许插入元素的一端称为 。
4. 后缀表达式5 3 2 * 3 ＋ 3 / ＋ 的值为 。
5. 一棵有1927个结点的二叉树，所有结点的度之和为 。
6. 具有100个结点的完全二叉树的高度是 。
7. 5阶B树中非失败结点的元素个数最多为 。
8. 10个顶点的无向图中有4条边，若采用邻接矩阵表示，则矩阵中的非0元素个数
是 个。
二、单项选择题
1. 线性表采用链表存储结构的特点是 。 （ ）
A. 结点的地址必须连续 B. 可以随机存取
C. 插入、删除操作不必移动元素 D. 需要事先估计所需存储空间
2. 设1、2、3三个元素依次进栈，则 不可能是其出栈序列。 （ ）
A. 1，2，3 B. 2，3，1 C. 3，2，1 D. 3，1，2
3. 对半搜索算法的条件是 。 （ ）
A. 顺序存储，元素有序 B. 顺序存储，元素无序
C. 链接存储，元素有序 D. 链接存储，元素无序
4. 高度为5的二叉树上，最多有 个结点。 （ ）
A. 5 B. 16 C. 31 D. 32
5. 二叉搜索树中， 是关键字值最大的结点。 （ ）
A. 先序遍历序列中的最后一个结点 B. 中序遍历序列中的最后一个结点
C. 后序遍历序列中的最后一个结点 D. 按层遍历序列中的最后一个结点
6. 有n个顶点的有向图中最多有 条边。 （ ）
A. n B. n(n-1) C. n(n+1) D. n2
7. 下列算法中， 在最坏情况下的渐近时间复杂度不高于O(nlog2n)。（ ）
A. 简单选择排序 B. 直接插入排序 C. 快速排序 D. 两路合并排序
三、简答题
1. 画出对长度为9的有序表进行对半搜索的二叉判定树，并求等概率搜索时成功搜索情况下的平均搜索长度。
2. 设有向图的邻接表如下所示，请写出该图的邻接矩阵，并且求出各个顶点的出度。 0^0^132434550^11^42^0^
3. 设有向图如下图所示，请画出该图所有的强连通分量。
246531
4. 使用普里姆（Prim）算法以A为源点，构造下图的最小代价生成树，要求画出构造过程中各步的结果。
ACBEFD75216319
5. 设一棵二叉树的先序遍历序列是ABDCEF，中序遍历序列是BDAECF，请画出该二叉树。
6. 已知二叉树如下图所示，请画出该二叉树对应的森林。
ABCDFGIEH
7. 下图是一个3阶B-树，请画出插入37之后的B-树，再画出在此基础上插入38后的B树。
20 35251936
8. 设字符集合S={A，B，C，D，E}，各字符的使用频率为W={5，7，8，9，10}。
⑴ 画出哈夫曼树；（构建新树时，新树根的左子树根的权值小于等于右子树根的权值）
⑵ 求该哈夫曼树的带权路径长度。
四、程序填空题
下面是快速排序的程序，请补充完整。
template void QSort(T A[], int left, int right)
{
int i,j;
if ( left
{
i=left; j=right+1;
do
{
do {i++;} while ( );
do {j--;} while (A[j]>A[left]);
if (i
}while (i
Swap (A[left], );
QSort (A, left, j-1);
QSort (A, j+1, );
}
}
五、程序阅读题
下面的程序是单链表类的某个成员函数
template
void SingleList::A()
{
Node *p=first,*q;
first=NULL;
while (p)
{
q=p->link;
p->link=first;
first=p;
p=q;
}
}
⑴ 请说明该成员函数的作用是什么？
⑵ 若有单链表结构如右上图所示，请画出执行该函数后的单链表结构。
六、程序设计题
在带表头结点的单链表类HeaderList中增加一个成员函数
bool HeaderList::Min(T &result) const
