2009下数据结构A(B卷)

西南交通大学2009－2010学年第(1)学期考试试卷(B) 课程代码 3200560 课程名称 数据结构A 考试时间 120 分钟 题号 一 二 三 四 五 六 七 八 九 十 总成绩 得分 阅卷教师签字： 点评：考试时间2小时，试题难度：较易 一、选择题（本大题共20小题，每小题1分，共20分） 1.顺序存储分配时，存储单元的地址【 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 2.以下属于数据的逻辑结构的术语是【 】。 A.顺序 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf B.哈希表 C.线性表 D.单链表 3.下面哪一条是顺序存储结构的优点？【 】。 A.插入运算方便 B.可方便地实现各种逻辑结构的存储表示 C.存储密度大 D.删除运算方便 4.链表存储线性表不具备的特点是【 】。 A.插入和删除不需要移动元素 B.可随机访问任何一个结点 C.不必事先估计存储空间 D.所需存储空间与线性表长度成正比 5.带头结点的双向循环链表（头指针为L）为空的判断条件是【 】。 A.L==NULL B.L->next->prior==NULL C.L->prior==NULL D.L->next==L 6.栈和队列的共同点是【 】。 A.都是先进先出 B.都是后进后出 C.只允许在端点处进行插入和删除 D.无共同点 7.输入序列是ABC，若输出序列变为CBA，经过的栈操作为【 】。 A.push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 8.设有两个串p和q，求p在q中首次出现的位置的运算称为【 】。 A.连接 B.模式匹配 C.求子串 D.求串长 9.设有一个n*n的对称矩阵，采用压缩存储，则存入内存的元素个数为【 】。 A.n*n B.n*n/2 C.n*(n+1)/2 D.(n+1)2/2 10.设有数组A[8][10]，每个元素占3个存储单元，首地址为SA，则元素[7][5]的起始地址是【 】。 A.SA+141 B.SA+144 C.SA+222 D.SA+225 11.有关二叉树下列说法正确的是【 】。 A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.一棵二叉树至少有一个结点的度为2 D.二叉树中任何一个结点的度为2 12.一棵完全二叉树有1001个结点，其中叶结点的个数为【 】。 A.250 B.500 C.254 D.以上答案均不对 13.某二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树一定是【 】。 A.空或只有一个结点 B.完全二叉树 C.二叉排序树 D.高度等于其结点数 14.具有4个顶点的无向完全图有【 】条边。 A.6 B.12 C.16 D.20 15.对某个无向图的邻接矩阵来说，【 】。 A.第i行上的非0元素个数等于第i列上非0元素个数 B.矩阵中非0元素个数等于图中的边数 C.第i行、第i列上非0元素个数等于顶点vi的度数 D.矩阵中非全0行的行数等于图中的顶点数 16.在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【 】量级相当。 A.顺序查找 B.折半查找 C.分块查找 D.前三个都不正确 17.散列表的平均查找长度【 】。 A.与冲突处理方法有关而与表的长度无关 B.与冲突处理方法无关而与表的长度有关 C.与冲突处理方法有关且与表的长度有关 D.与冲突处理方法无关且与表的长度无关 18.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的后面的方法，称为【 】。 A.希尔排序 B.归并排序 C.直接插入排序 D.直接选择排序 19.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是【 】。 A.堆排序<快速排序<归并排序 B.堆排序<归并排序<快速排序 C.堆排序>归并排序>快速排序 D.堆排序>快速排序>归并排序 20.广义表((a,b),c,d)的表尾是【 】。 A.a B.d C.c,d D.(c,d) 二、填空题（本大题共20分，每空1分） 1.在线性表的顺序存储结构中，元素间的逻辑关系是通过 决定的；在线性表的链式存储结构中，元素间的逻辑关系是通过 决定的。 2.在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需要知道 才能遍历整个链表。 3. 在一个长度为n的顺序表中删除第i个元素时，需要向前移动 个元素。 4.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 ；若只设尾指针，则出队操作的时间复杂度尾 。 5.假设将一个10×10矩阵A的下三角元素（包括对角线元素）压缩存储在一维数组C中，则C数组的大小应为______ __。 6.从循环队列中插入一个元素的操作是 。 7.一个串中 称为该串的子串。 8.当广义表A非空时，称第一个元素a1为广义表A的 ，称其余元素组成的表为广义表的 。 9.二叉树是结点的有限集合，这个结合或者为空，或者由一个根结点和 的称为 和 的二叉树构成。 10.在图G中，如果代表边的顶点偶对是 ，则称图G为有向图。 11.已知一个由向图用邻接矩阵表示，计算第i个顶点的入度的方法是 。 12.折半查找的思路是：每次将给定值与查找表中所要查找区域的 的关键字进行比较，而不是与查找表中的第一个或最后一个元素进行比较。 13.对于二叉排序树的查找，若根结点元素的关键字值大于被查找元素的关键字值，则应该在该二叉排序树的 上进行查找。 14. . 排序方法采用二分法的思想， 排序方法将数据的组织采用完全二叉树的结构。 三、判断题（本大题共10小题，每小题1分，共10分） 【 】1.数据元素是数据的最小单位。 【 】2.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据元素。 【 】3.顺序存储结构是动态存储结构，链式存储结构是静态存储结构。 【 】4.循环队列中的元素个数，可以根据队首指针和队尾指针的值计算出来。 【 】5.两个字符串相等必有串长度相等。 【 】6.哈夫曼树的结点个数不偶数。 【 】7.n个顶点的无向图至多有n(n-1)条边。 【 】8.如果表示图的邻接矩阵不是对称的，则该图一定是有向图。。 【 】9.哈希冲突是指同一个关键字对应多个不同的哈希地址。 【 】10.二分查找可以在有序的双向链表上进行。 四、解答题和填空题（本大题共6小题，共30分，其中问答题每小题5分，填空题每空2分） 1、阐述顺序表和链表存储方式的特点。 2、何谓队列上溢？何为队列假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。 3、已知某通信用电文仅由A、B、C、D、E、F、G、H、I共9个字符构成，其出现的频率分别是10，20，5，15，8，2，3，7，30，请构造其哈夫曼树及每个字符对应的哈夫曼编码。 4、设有数据集合d={1，12，5，8，3，10，7，13，9}，回答下列问题： ① 依次取d中各数据，构造一棵二叉排序树bt； ② 如何依据此二叉排序树得到d的一个有序序列。 5、下面是折半查找算法，请填空完成算法。 int search(SStable ST,KeyType key) { low=1; high=ST.length; while (low<=high) { mid= ; if(EQ(key, ST.elem[mid].key)) ; else if(LT (key, ST.elem[mid].key)) high=mid-1; else ; } return 0; } 6、下面是直接插入排序算法，请填空完成算法 void InsertSort(SeqLiat &L) { int i,j; for (i=2;i<=L.length;++i) if LT(L.r[i].key, L.r[i-1].key) { ; for (j=i-1;LT (L.r[0].key, L.r[j].key);--j) ; L.r[j+1]=L.r[0]; } } 五、算法设计（本大题共2小题，每小题10分，共20分） 1、已知由一个线性链表表示的线性表是由含三类字符（字母字符、数字字符和其它字符）的元素组成，试编写算法将该线链性表分割为三个单循环链表，其中每个循环链表表示的线性表中均只含其中一类字符。要求原链表继续保留。 2、设计一算法求出二叉树T的叶子结点的数目。 班 级 学 号 姓 名 密封装订线 密封装订线 密封装订线 PAGE 4