桂林电子科技大学 工程硕士 数据结构试卷

《桂林电子科技大学 工程硕士 数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、桂林电子科技大学试卷2011-2012学年第1学期课号课程名称数据结构（闭卷）适用班级（或年级、专业）计算机类在职研究生班考试时间120分钟班级学号姓名题号一二三四五六七八九十成绩满分2010164212得分评卷人一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.以下数据结构中哪一个是非线性结构？(  A)A.二叉树　　 B.队列       C.文件D.字符串2.在一个带有附加表头结点的非

2、空单链表HL中，在表头插入一个由指针p指向的结点，则执行(D)。A.HL=p;p->next=HL;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.p->next=HL->next;HL->next=p;3.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（B）A.543612B.453126C.436251D.2314564.设数组a[]作为循环队列SQ的存储空间,f为队头指针,r为队尾指针，则执行入队操作的语句为(B)A．f=f+1B.f=(f+

3、1)%mC.r=(r+1)%mD.f=(f+1)%(m+1)5.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a3,6的地址为（B）。A.15B.17C.18D.196．将一棵有80个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为32的结点的右孩子的编号为___C___。A.63B.64C.65D.667.设x是一棵树，x’是对应于x的二叉树，则x的后根遍历和x’的_B__遍历相同A.先序B.中序

4、C.后序D.都不是8.在含有10个项点有22条边的无向图的邻接矩阵中，零元素的个数为____A____。A.56B.78C.44D.229．设有15个结点的无向图，该图至少应有(   A  )条边才能确保是一个连通图。A.14     B.15        C.16    D.17510．下列排序算法中，其中（D）是稳定的。A.快速排序，冒泡排序B.堆排序，冒泡排序C.插入排序，堆排序D.归并排序，直接选择排序二、判断题（每题2分，共10分）1.无向图是一种特殊的图。(对)2．在一个有向图中，若所有节点

5、的入度之和为20，则所有的出度之和不一定为20。（对）3.在用堆排序算法排序时，如果要进行增序排序，则需要采用“小根堆”。（对）4.一组具有给定频率的字符表，对应的赫夫曼编码一定是唯一的。(错)5.无向图的邻接矩阵一定是对称的。（错）三、填空题（本大题共4小题，每空2分，共16分）请在每小题的空格中填上正确答案。错填、不填均无分。1．在一个长度为n的顺序表中在第i个位置（1<=i<=n）删除一个元素，需移动_n-i__个元素。2.已知指针p指向单链表L中的某结点，则在其后增加一个结点的语句是：______

6、__，________。3.  设T是一棵有18个顶点的树，称树中度为1的顶点为叶子，如果T的顶点的度只可能是1,2,5且T恰好有1个度为2的顶点，那么，T中有________个叶子，有________个度为5的顶点。4.任何一棵二叉树，若度为0和1的结点个数分别为13和14，则该二叉树节点的个数为_______。5.一组记录是关键字为（38，70，38′，56，40，84），则利用泡冒排序的方法，则第一轮的序列结束后得到的序列是_____；若利用希尔排序的方法，递增序列d=4,2,1,则第一轮结束后得到

7、的序列是_____。四、简答题（42分）1．设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：ABCDEFGIJK中序遍历序列：CBEGFDBAIHKJ（1）画出这棵二叉树。（6分）（2）将这棵二叉树转换成对应的树（或森林）。（6分）52．已知一个无向图如下图所示，要求用PRIM算法生成最小树（假设以③为起点，试画出构造过程）。（9分）1111132116126143610844553.假设用于通讯的电文仅由7个字母组成，字母在电文中出现的频率分别是：17，3，9，18，19，10，24。试为这7个字母

8、设计哈夫曼编码。（9分）哈夫曼树如下图：对树的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，即为所求。频率173918191024哈夫曼编码1000000000101101001114．已知待排序的序列为（553，68，213，50，667，173，890，275，653，462），试完成下列各题。（12分）(1)根据以上序列建立一个堆（画出最后堆的结果图），希望先输出最大值。(2