杭州电子科技大学2011数据结构期末试卷

杭州电子科技大学学生考试卷（ A ）卷
考试课程 数据结构 考试日期 2011 年 月 日 成 绩 课程号 教师号 任课教师姓名 考生姓名 学号（8位） 年级 专业 一．判断题：（每小题2分，共20分）
1．链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。 （ ）
2．数据的物理结构是指数据在计算机内的实际存储形式。 （ ）
3．线性表采用链表存储时，查找第i个元素的时间与i的值无关。 （ ）
4．将一棵树转成二叉树，根结点没有左子树。 （ ）
5．广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。 （ ）
6．完全二叉树的某结点若无左孩子，则它必是叶结点。 （ ）
7．用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。 （ ）
8．图的深度优先遍历序列和广度优先遍历序列不是唯一的。 （ ）
9．用简单选择排序算法，只需一趟扫描即可选出键值最大（或最小）的元素 。 （ ）
10. 采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。 （ ）
二．选择题：（每小题2分，共18分）
1．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A. 13 B. 33 C. 18 D. 40

2．下面关于线性表的叙述中，错误的是哪一个？（ ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。

3．循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
　4.对于深度为K的满二叉树(结点编号从1开始，根结点的层数为1)，其第K层上最后1个结点的编号为 ( )。
A.2K B.2K?1 C.2K?1?1 D.2K?1
5．一个有N个顶点的无向图最多有（ ）条边。
A.N B.N*(N?1) C.N*(N?1)/2 D.2*N
6．队列具有( )的特点，是操作受限的线性表。
A. 先进先出 B. 先进后出 C.没有特点

7. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适

位置，该排序方法称为( )排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并

　8. 在计算机内实现递归算法时所需的辅助数据结构是( )
A.栈 B.队列 C.树 D.图

9. 若一个算法的时间复杂度用O(n)表示，其中n的含义是（ ）
A．问题规模 B．语句条数 C．循环层数 D．函数数量
三．填空题：（每空2分，共12分）
1．非空的平衡二叉树，树中每个结点的左子树和右子树的深度之差的绝对值不超过________。
2．深度为h的二叉树最少有________个结点。
3．对一棵二叉排序树进行______________遍历可以得到一个有序序列。
4. 具有10个顶点的连通图，其最小生成树的边数为______。
5. 在一棵m阶B-树中，每个非叶子结点至多有______ 个关键字。
6. 快速排序平均时间复杂度为O(nlogn) ,最坏情况下时间复杂度是________ 。
四．应用题：（每小题8分，共40分）
1．已知一棵二叉树T的先序序列为：EBADCFHGIKJ，中序序列为：ABCDEFGHIJK。
（1）试画出该二叉树.
（2）若该二叉树用孩子兄弟表示法表示，试画出与此二叉树对应存储关系的树的形态。
2．设散列表长度为11，散列函数H（k）＝k MOD 11，若输入顺序为（2，4，18，23，26，7，12）。试用线性探测开放址法解决冲突构造散列表并求在等概率情况下查找成功的平均查找长度。
3．假设用于通信的电文由7个字母组成，字母在电文中出现的频率分别为5，7，9，16，23，18，22要求构建的哈夫曼树中的结点，其左孩子的权值小于右孩子权值。试为这7个字母设计哈夫曼编码。
4．给定一组关键码{18，31，16，22，51，30，24}，要求构建一个小顶堆，画出构建初始堆的过程。
5．已知带权的无向图的邻接矩阵如下图所示，其顶点集合为｛A,B，C,D，E｝。


画出该图及其最小生成树（如有多棵，只需写出其中一棵即可）。
五．算法设计：（ 每小题5分，共10分）
1．利用二叉链表作为存储结构，试编写算法求二叉树中度为2的结点个数。
//二叉树结点
template
struct BTNode{
ElemType data; //结点值
BTNode *lchild; //左孩子结点指针
BTNode *rchild; //右孩子结点指针
};

//二叉链表类
template
class BinaryTree
{
public:
BinaryTree():m_root(NULL){}
~BinaryTree()
int count(BTNode* T) //求二叉树中度为2的结点的个数
........
private:
BTNode *m_root; //二叉树根结点指针
}

（沈静老师班级用）：
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTr

ee;
int Count(BiTree pTree);











2．试写一个C++程序实现:
在带头结点的单链表中第i个数据元素之前（i的合法值为1≤i≤len+1），插入新的数据元素e，插入成功返回true，否则返回false。
template
class LinkList: public List
{
public:
LinkList();
~LinkList();
............;
bool OrderInsert( const ElemType &e, int i); //实现该函数
............;
private:
int len; //单链表长度
LinkNode *head; //head是头指针
};

// 单链表结点类
template
struct LinkNode
{
ElemType data;
LinkNode *next;
};

（沈静老师班级用）：函数形式如下：
//在带头结点的单链表第i个数据元素之前，插入新的数据元素e（i的合法值为1≤i≤len+1），插入成功返回true，否则返回false。
typedef int Status;
Status InsertList_L(LinkList L, int i, ElemType e);
??

??

??

??


座位号：

第 1 页 共 3 页