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

1、杭州电子科技大学学生考试卷（A ）卷考试课程数据结构考试日期2011年 月 日成绩课程号教师号任课教师姓名考生姓名学号（8位）年级专业1 .判断题：（每小题2分，共20分）1 .链栈的初始化是指开辟足够多的结点，然后置栈顶指针为NULL（）2 .数据的物理结构是指数据在计算机内的实际存储形式。（）3 .线性表采用链表存储时，查找第i个元素的时间与i的值无关。（）4 .将一棵树转成二叉树，根结点没有左子树。（）5 .广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（）6 .完全二叉树的某结点若无左孩子，则它必是 叶结点。（）7 .用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。（）8

2、 .图的深度优先遍历序列和广度优先遍历序列不是唯一的。（）9 .用简单选择排序算法，只需一趟扫描即可选出键值最大（或最小）的元素 。（）10 .采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（2 .选择题：（每小题2分，共18分）1 .设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，all为第一元素, 其存储地址为1,每个元素占一个地址空间，则 a85的地址为（）。A. 13B. 33C. 18D. 402 .下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表

3、采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。3 .循环队列存储在数组 A0.m中，则入队时的操作为（）。A. rear=rear+1B. 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.2 K B.2 K-1C.2 K-1-1D.2 K-15 . 一个有N个顶点的无向图最多有（）条边。A.N B.N*（N

4、-1） C.N*（N -1）/2D.2*N6 .队列具有（）的特点，是操作受限的线性表。A.先进先出B.先进后出C.没有特点7 .从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入 B. 选择 C. 希尔 D.二路归并8 .在计算机内实现递归算法时所需的辅助数据结构是（）A.栈B.队列C.树D.图9 .若一个算法的时间复杂度用 O（n）表示，其中n的含义是（）A.问题规模B .语句条数C .循环层数D,函数数量三.填空题：（每空2分，共12分）1 .非空的平衡二叉树，树中每个结点的左子树和右子树的深度之差的绝对值

5、不超过2.深度为h的二叉树最少有 个结点3 .对一棵二叉排序树进行 遍历可以得到一个有序序列。4 .具有10个顶点的连通图，其 最小生成树的边数为。5 .在一棵m阶B-树中，每个非叶子结点至多有个关键字。6 .快速排序平均时间复杂度为O(nlogn),最坏情况下时间复杂度是。四.应用题：(每小题8分，共40分)1 .已知一棵二叉树 T的先序序列为：EBADCFHGIKJ中序序列为：ABCDEFGHIJK(1)试画出该二叉树.(2)若该二叉树用孩子兄弟表示法表示，试画出与此二叉树对应存储关系的树的形态。2 .设散列表长度为11,散列函数H (k) k MOD1,若输入顺序为(2, 4, 18,

6、23, 26, 7, 12)。试用线性探测开放址法 解决冲突构造散列表并求在等概率情况下查找成功的平均查找K度。3 .假设用于通信的电文由7个字母组成，字母在电文中出现的频率分别为 5, 7, 9, 16, 23,18, 22要求构建的哈夫曼树中的结点，其左孩子的权值小于右孩子权值。试为这7个字母设“哈夫曼编码。4,给廿组关键码18, 31, 16, 22, 51, 30, 24,要求构建一个小顶堆，回出构建初始 世的过程。5.已知带权的无向图的邻接矩阵如下图所示，其顶点集合为A,B, C,D,日。画出该图及其最小生成树(如有多棵，只需写出其中一棵即可)。五.算法设计：(每小题5分，共10分)

7、1 .利用二叉链表作为存储结构，试编写算法求二叉树中度为2的结点个数。/二叉树结点 template<class ElemType> struct BTNodeElemTypedata;/结点值BTNode<ElemType> *lchild;/左孩子结点指针BTNode<ElemType> *rchild;/右孩子结点指针;/二叉链表类 template<class ElemType> class BinaryTree public:BinaryTree():m_root(NULL)BinaryTree()int count(BTNode<

8、;ElemType>* T)/求一叉树中度为2的结点的个数.private:BTNode<ElemType> *m_root;/一叉树根结点指针(沈静老师班级用)： typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode, *BiTree; int Count(BiTree pTree);2 .试写一个C+程序实现：在带头结点的单链表中第i个数据元素之前(i的合法值为1&i&len+1,插入新的数据元素 etruefalse template <class

9、ElemType>class LinkList: public List<ElemType> public:LinkList();LinkList();；bool OrderInsert(const ElemType &e, int i); 实现该函数 ;private:int len;/单链表长度LinkNode<ElemType> *head;head 是头指针J/单链表结点类emplate <class ElemType> struct LinkNode ElemType data;LinkNode<ElemType> *next;（沈静老师班级用）：函数形式如