2009下数据结构A(A卷)

西南交通大学2009－2010学年第(1)学期考试试卷(A) 课程代码 3200560 课程名称 数据结构A 考试时间 120 分钟 题号 一 二 三 四 五 六 七 八 九 十 总成绩 得分 阅卷教师签字： 点评: 考试时间2小时, 试题 中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载 难度: 较易 一、选择题（本大题共20小题，每小题1分，共20分） 1.算法的计算量的大小称为计算的【 】。 A.效率 B.复杂度 C.现实性 D.难度 2.以下与数据的存储结构无关的术语是【 】。 A.循环队列 B.链表 C.哈希表 D.栈 3.下面关于线性表的叙述中，错误的是【 】。 A.线性表采用顺序存储，则必须占用一片连续的存储单元 B.线性表采用顺序存储，则便于插入和删除操作 C.线性表采用链式存储，则不必占用一片连续的存储单元 D.线性表采用链式存储，则便于插入和删除操作 4.单链表中增加一个头结点的目的是为了【 】。 A.使单链表至少有一个结点 B.标识表首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储 5.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【 】最节省时间。 A.带头结点的双向循环链表 B.单循环链表 C.带尾指针的单循环链表 D.单链表 6.队列的先进先出特征是指【 】。 A.最后插入队列的元素总是最后被删除 B.当同时进行插入、删除操作时，总是插入操作优先 C.每当有删除操作时，总要先做一次插入操作 D.每次从队中删除的元素总是最早插入的元素 7.设入栈序列为1,2,3,4,5,则可能得到的出栈序列为【 】。 A.1,2,5,3,4 B.3,1,2,5,4 C.3,2,5,4,1 D.1,4,2,3,5 8.两个串相等必有串长度相等且【 】。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个串含有字符任意 9.设A是一个n*n的对称矩阵，压缩存储到一个一维数组B[0..n(n+1)/2-1]中，则下三角部分元素ai,j在B中的位置是【 】。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 10.设有数组A[8][10]，每个元素占3个存储单元，存放该数组的存储单元数为【 】。 A.80 B.100 C.240 D.270 11.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为【 】。 A.9 B.11 C.15 D.不确定 12.一棵124个叶结点的完全二叉树，最多具有【 】个结点。 A.247 B.248 C.249 D.251 13.由8个权值构造一棵哈夫曼树，该哈夫曼树有【 】个结点。 A.15 B.16 C.17 D.14 14.一个有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【 】。 A.n B. (n-1)2 C. (n-1) D. n2 15.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，所有邻接表中结点总数为【 】 。 A.e/2 B.e C.2e D.n+e 16.对查找表进行折半查找时，要求查找表必须【 】。 A.以顺序方式存储 B.以顺序方式存储，且结点按关键字有序排列 C.以链式方式存储 D.以链式方式存储，且结点按关键字有序排列 17.以下说法错误的是【 】。 A.散列法存储的基本思想是由 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 关键字决定数据存储地址 B.散列法的结点中只包含数据元素自身的信息，不包含任何指针 C.装填因子是散列法的一个重要参数，它反映了散列表的装填程度 D.散列表的查找效率取决于散列造表的散列函数和冲突处理的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 18.在待排序的元素序列基本有序的前提下，效率最高的排序方法是【 】。 A.插入排序 B.选择排序 C.快速排序 D.归并排序 19.在下列排序方法中，要求内存量最大的方法【 】。 A.直接插入排序 B.选择排序 C.快速排序 D.归并排序 20. 广义表(a,b,c,d)的表尾是【 】。 A.b,c,d B.c,d C.d D.(b,c,d) 二、填空题（本大题共10小题，每小题2分，共20分） 1.一个算法的效率可分为 效率和 效率。 2.若一个算法中的语句频度之和为T(n)=3720n+4nlog2n，则算法的时间复杂度为 。 3.在如下图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是： 和 。 4.向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动 个元素。 5.假设以S和X分别表示进栈和出栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 。 6.循环队列的优点是 。 7.从循环队列中删除一个元素的操作是 。 8.模式串p=“abaabcac”的next值为 。、 9.设有广义表L=((),()),则GetHead(L)= ；GetTail(L)= 。 10.一棵深度为K且具有2k-1个结点的二叉树称为 。这类二叉树的特点是，二叉树的每一层结点的个数都为 。 11.已知完全二叉树的第7层有10个叶结点，则整棵二叉树的结点为 。 12.在图G中，如果代表边的顶点偶对是 ，则称图G为无向图。 13.在分块查找方法中，首先查找 ，然后再查找相应的 。 14.在插入和选择排序中，若初始数据基本正序，则选用 ，若初始数据基本反序，则选用 。 三、判断题（本大题共10小题，每小题1分，共10分） 【 】1.具有存取任一数据元素的时间相等且为O(1)这一特点的存储结构称为随机存取结构。 【 】2.线性表采用链式存储结构时，结点的存储空间可以使是不连续的。 【 】3.线性表的长度是线性表所占存储空间的大小。 【 】4.栈是实现函数调用所必需的数据结构。 【 】5.两个字符串相等则各位置上字符必须对应相等。 【 】6.完全二叉树中，若一个没有左孩子，则它必定是叶结点。 【 】7.一棵树中的叶结点数一定等于与其对应的二叉树的叶结点数。 【 】8.连通分量是无向图的极小连通子图。 【 】9.在二叉排序树中，每个结点的关键字比左孩子的关键字大，比右孩子的关键字小。 【 】10.哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。 四、解答题和填空题（本大题共6小题，共30分，其中问答题每小题5分，填空题每空2分） 1、若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？ 2、对于一个栈，其输入序列是A，B，C，试给出全部可能的输出序列。 3、设有如下图所示的二叉树，给出其前序、中序和后序遍历结果。 4.画出对长度为10的有序表进行折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。 5、下面是线性表的单链表的存储结构的数据元素插入算法，请填空完成算法。 Status Listinsert_L(Linklist L,int i,Elemtype e) { p=L; j=0; while (p&&ji-1) return ERROR; s=(LinkList)malloc(sizeof(ListNode)); ; ; p->next=s; return OK; } 6、下面是快速排序算法的任意子系列L.r[low..high]的一趟划分算法，请填空完成算法。 int partition(Sqlist &L,int low,int high) { L.r[0]= L.r[low]; pivotkey=L.r[low].key; while (low