《数据结构》 样题
1、 选择填空题（每题2分）
1． 单链表中，删去p指向的结点的后继结点，可以执行( )操作实现。
A. p->link = p->link->link；
B. p->link = NULL;
C. p->link->link = NULL；
D. 以上都不是
2． 一个栈的输入序列是a,b,c,d,e，则下列哪个是合法输出序列（ ）。
A. b c d a e
B. e d a c b
C. e c a d b
D. 以上都不是
3． 设A为8×10的二维数组，每个数组元素的长度为4个字节，数组元素以行为主序存放，且数组首地址为SA，则元素A[6][8]的起始地址为（ ）。
A. SA+68
B. SA+272
C. SA+232
D. 以上都不是
4． 一组
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
的关键字为{40，80，55，45，42，85}，则利用堆排序的方法建立的初始堆（大顶堆）为（ ）。
A. 80 45 50 40 42 85
B. 85 80 55 40 42 45
C. 85 80 55 45 42 40
D. 以上都不是
5． 设有n个结点的完全二叉树顺序存放在数组A[0…n-1]中，对任意结点A[i]，若A[i]有右孩子结点，则其右孩子结点是（ ）
A. A[i/2]
B. A[2*i]
C. A[2*i+1]
D. A[2*i+2]
6． 顺序查找方法中，设置“监视哨”是为了（ ）。
A. 减少比较次数
B. 减少记录移动次数
C. 防止越界错误
D. 以上都不是
7． 以下关于“堆”的叙述，正确的是（ ）。
A. 堆是二叉排序树
B. 堆是满二叉树
C. 堆是完全二叉树
D. 以上都不是
8． 快速排序的最优时间复杂度为（ ）。
A. O(n)
B. O(n2)
C. O(nlog2n)
D. 以上都不是
9． 下面( )方法可以判断出一个有向图中是否有环（回路）。
A. 深度优先遍历
B. 拓扑排序
C. 广度优先遍历
D. 求关键路径
2、 判断题（每题2分）
1． 线性表的链式存储结构优于顺序存储结构。
2． 循环队列是允许在两端都可以插入和删除的线性表。
3． Shell排序是稳定的排序算法。
4． 二叉树是度为2的树。
5． 二叉树的先序遍历序列和中序遍历序列可以惟一确定这棵二叉树。
6． 有n（n>=1）个顶点的无向连通图最少有n条边。
7． 完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。
8． 折半查找只能在顺序表上进行。
3、 简答题
给定以下关键字序列：{31,25,49,25*,93,62,75,08,37,61,54}，完成第1、2小题。
1． 以上述关键字序列作为输入，
（1） 请画出相应的二叉排序树；
2． 请分别写出直接选择法排序、冒泡法排序、快速排序法（取第一个元素为基准元素）、Shell排序（取初始间距为5）的第一趟排序结果，使待排序序列非递减有序。
3． 请分别写出以下有向图的深度优先遍历序列、广度优先遍历序列和拓扑排序序列。
4、 程序填空题（每空3分，共24分）
1． 下面是折半查找的算法，其中有一些语句缺失，请根据算法的功能补充之。
/* 折半查找 */
/*
参数：list-关键字序列（非递减有序） */
/*
参数：size-关键字序列长度 */
/*
参数：x-待查找元素 */
/*
返回值：若查找成功则返回该元素在序列中的位置，否则返回-1 */
template
int binary_search(const ElemType* list, int size, const ElemType& x)
{
int bot,top;
// 当前查找区间，半闭半开区间：[bot,top)
int mid;
// 区间中点
bot = 0;
top = size;
while (bot < top)
{
mid = ① ;
if (list[mid] < x)
bot = mid+1;
else if (list[mid] > x)
② ;
else
return ③ ;
}
return -1;
}
2． 下面是二叉树后序线索化的非递归算法，其中有一些语句缺失，请根据算法的功能补充之。
// 数据类型定义
typedef struct _BinTreeNodeExt
{
int lthread, rthread;
// 线索标记，1为线索，0为
// 实际孩子结点指针
struct _BinTreeNodeExt *lchild, *rchild;
// 左右孩子结点指针
int data;
// 数据域
} BinTreeNodeExt;
// 结点数据类型
typedef pair
StackNodeExt;
// 堆栈结点，第一个域（first）
// 为结点（1）或树（0）标记；
// 第二个域（second）为指针
typedef stack NodeStackExt;
// 堆栈数据类型
/* 创建线索化二叉树。 */
/*
参数：root - 树根指针 */
void create_thread(const BinTreeNodeExt *root)
{
BinTreeNodeExt* q;
// q为前驱结点指针
NodeStackExt s;
// s为堆栈
int flag;
// 若为空树，直接返回。
if ( ① )
return;
q = NULL;
// 初始时整棵树入栈
s.push(StackNodeExt(0, root));
while (!s.empty())
{
// 获取栈顶元素，并出栈
flag = s.top().first;
root = s.top().second;
s.pop();
if (flag == 1)
// 视当前指针为结点指针
{
// 若root无左孩子，设置前驱线索标记
if (root->lchild == NULL)
{
// 设置root的前驱线索标记，root的前驱为q
root->lthread = 1;
② ;
}
// 若前驱结点q存在，且无右孩子，设置后继线索标记
if ( ③ )
{
// 设置q的后继线索标记，q的后继为root
q->rthread = 1;
q->rchild = root;
}
// 前驱结点指针q向后推移
④ ;
}
else
// 视当前指针为树的根指针
{
// 1: 当前根结点入栈
⑤ ;
// 2: 如有右子树，右子树根指针入栈
if (root->rchild)
s.push(StackNodeExt(0, root->rchild));
// 3: 如有左子树，左子树根指针入栈
if (root->lchild)
s.push(StackNodeExt(0, root->lchild));
}
}
return;
}
5、 编程题（2小题，共16分）
1.(10分) 编写程序，删除带头结点的单链表中值大于min且小于max（min < max）的所有元素，并释放相对应结点的空间。编写程序时，请使用以下的数据类型定义和函数原型，只需要完成该函数的实现部分即可。
// 单链表结点数据类型定义
typedef struct _listNode
{
int data;
struct _listNode* link;
} ListNode;
/*函数的原型 */
/*
参数：head- 单链表头结点指针 */
/*
参数：min、max为删除结点的取值范围*/
void DeleteNodes(ListNode* &head, int min, int max)；
2.（6分）编写一个算法（递归或非递归算法均可），统计一棵二叉树中非叶结点的个数。编写程序时，请使用以下结点数据类型定义和函数原型，只需要完成该函数的实现部分即可。
// 结点数据类型定义
typedef struct _BinTreeNode
{
int data;
// 数据域
struct _BinTreeNode *lchild, *rchild;
// 左右孩子结点指针
} BinTreeNode;
// 结点数据类型
// CountInnerNodes统计指定的二叉树中非叶结点的个数
//
root 为二叉树根结点指针；
//
函数返回值为非叶结点的个数
int CountInnerNodes(const BinTreeNode *root)；
6
5
4
3
2
1
PAGE
第 1 页 / 共 4 页
浙公网安备 33021202002483