数据结构与算法试卷A2012.doc

题 号 一 二 三 四 总分 得 分 阅卷人 得 分 一、填空题（每空2分，共12分） 1. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的________ 有限集合。 2.向一个长度为n的线性表中删除第i个元素(1≤i≤n)时，需向前移动________个元素。 3. 假设以S和X代表进栈和出栈操作，则对输入序列a,b,c,d,e进行一系列操作SSXSXSSXXX之后，得到的输出序列为________。 4. 已知循环队列的存储空间为数组A[21]，front指向队头元素的前一个位置，rear指向队尾元素，假设front和rear的值分别为8和3，则该队列的长度为________。 5.在有序表A[0…17]中，采用折半查找法查找关键字等于A[7]的元素，需比较元素的下标依次为 。 6. 在堆排序、快速排序和归并排序方法中，稳定的排序方法是 。 得 分 二、单项选择题（每小题2分，共40分） 1. 数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A.存储 B. 物理 C. 逻辑 D.物理和存储 2. 算法分析的两个主要方面是（ ） A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ ） A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B.在第i个结点后插入一个新结点（1≤i≤n） C.删除第i个结点（1≤i≤n） D. 将n个结点从小到大排序 4． 线性表Ｌ在（ ）情况下适用于使用链式结构实现。 A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入 C.Ｌ中含有大量的结点 D.Ｌ中结点结构复杂 5. 经过以下栈运算后，x的值是（ ） InitStack(s); Push(s, a);Push(s, b);Pop(s,x);GetTop(s,x); A.a B.b C.1 D.0 6. 循环队列存储在数组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) 7. 按（ ）遍历二叉排序树得到的序列是一个有序序列。 A.先序 B.中序 C.后序 D.层次 8.下面哪一方法可以判断出一个有向图是否有环（回路）（ ）. A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 9.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ ）结构。 A.栈 B.队列 C.数组 D.线性表 10． 已知关键码序列{78,19,63,30,89,84,55,69,28,83}采用基数排序，第一趟排序后的关键码序列为（ ）。 A.{19,28,30,55,63,69,78,83,84,89} B.{30,63,83,84,55,28,78,19,69,89} C.{30,63,83,84,55,78,28,19,89,69} D.以上都不正确。 11. 无向图G=（V,E）s结点，则须执行（ ） A．s-next=p-next; p-next=s B．p-next=s; s-next=p C．p-next=s-next; s-next=p D．s-next=p; p-next=s-next 13.一个无向连通图有5个顶点8条边，则生成树将要去掉（ ）条边。 A. 3 B. 4 C. 5 D. 6 14.设一棵二叉树共有50个叶子结点，则共有（ ）个度为2的结点。 A. 25 B. 49 C. 50 D. 51 15.对数据序列{15,9,7,8,20,-1,7,4}，用堆排序的筛选法建立的初始小顶堆为（ ）。 A.{-1,4,8,9,20,7,15,7}