《大学专业试卷《数据结构》A》由会员分享，可在线阅读，更多相关《大学专业试卷《数据结构》A（7页珍藏版）》请在金锄头文库上搜索。
1、-一 一 -一 号学一 一-名姓一 一一一 一一一 级班业专 一一一 一一一 系院ir数据结构课程考试试巻适用专业：考试日期：闭卷所需时间：120分钟总分：100分一、单项选择题(共15小题，每小题2分，总共30分)1. 一种抽象数据类型包括数据和()两个部分。A.数据类型B.操作 C.数据抽象D.类型说明2. 在一个长度为n的顺序表的表尾插入一个新元素的时间复杂度为()。A. 0(1) B. O(n) C. O(n2) D. O(log2n)3. 已知L是带表头结点的单链表，删除第一个结点的语句是()。A. L 二 L-next;B. L- next 二 L- next - next;C.
2、L = L;D. L- next = L;4. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是()A.插入 B.删除 C.排序D.查找5. 若进栈序列为1, 2, 3, 4, 5, 6,且进栈和出栈可以穿插进行，则可能出现的出栈序列为()A. 3, 2, 6, 1, 4, 5B. 3, 4, 2, 1, 6, 5C. 1, 2, 5, 3, 4, 6D. 5, 6, 4, 2, 3, 16. 设串 sl=Data Structures with Java,s2=it?则子串定位函数 index(sl,s2)的值为( )。A. 15 B. 16 C. 17 D. 187. 在一个n个结
3、点有向图的邻接矩阵表示中，删除一条边需要的时间复杂度为()。A. 0(1) B. O(i)C. O(j) D. O(n)8. 二维数组A按行优先顺序存储，若数组元素A的存储地址为1087,A的存储地址为1153,贝I数组元素A的存储地址为（）A. 1207 B. 1209 C. 1211 D. 12139. 对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与（）有 关。A. n B. mC. n/mD. n*m10. 若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（）A.图中每个顶点的入度 B.图中每个顶点的出度C.图中弧的条数D.图中连通分量的数目11. 下列排序算法中，其
4、时间复杂度和记录的初始排列无关的是（）A.插入排序B.堆排序C.快速排序D.冒泡排序12. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t）,则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）A. f,c,b B. f,d,b C. g,c,b D. g,d,b13. 在一棵度为3的树中，度为3的结点个数为2,度为2的结点个数为1,则度为0 的结点个数为（）A. 4B. 5C. 6D. 714. 具有10个叶结点的二叉树中有（）个度为2的结点。A. 8B. 9C. 10D. 11 o15. 已知一棵二叉树的前序遍历结果为ABCDEF冲序遍历结果为CBAEDF,则后序遍
5、历的结果为（）。A. CBEFDA B. FEDCBA C. CBEDFA D.不定二、填空题(共10小题，每小题2分，共20分)1. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关，是独立于计算机的。2. 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和。3. 在单链表中逻辑上相邻的结点而在物理位置上相邻。4. 在有序表(12, 24, 36, 48, 60, 72, 84)中二分查找关键字72时所需进行的关键字比较次数为O5. 迷宫问题是一个回溯控制的问题，最好使用的方法来解决。6. 含n个顶点的无向连通图中至少含有条边。7. 若对关键
6、字序列(43, 02, 80, 48, 26, 57, 15, 73, 21, 24, 66)进行一趟增量为3的希尔排序，则得到的结果为。8. 已知一棵完全二叉树中共有768结点，则该树中共有个叶子结点。9. 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个 上，才会被加入到生成树中。10. 在堆排序中，对n个记录建立初始堆需要调用次调整算法。三、运算题(5小题，每小题6分，共30分)1. 一个一维数组 a10中存储着有序表(15,26,34,39,45,56,58,63,74,76),根据 折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出
7、在等概率 情况下进行成功搜索时的平均搜索长度。度为1的结点个数: 平均搜索长度：2. 已知一个图的顶点集V和边集G分别为：V= 123,4,5,6; E=vl,2,vl,3,v2,4,v2,5,v3,4,v4,5,v4,6,v5,l,v5,3,v6,5;假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号 (即数值域的值)从小到大的次序链接的，试写出：(1) 从顶点1出发进行深度优先搜索所得到的顶点序列；(2) 从顶点1出发进行广度优先搜索所得到的顶点序列。答：(1) (2)3. 已知一个数据序列为6,45,27,23,41,5,56,64,把它调整为大根堆的结果。最大堆：4.已知
8、带权图的邻接表如下所示，其中边表结点的结构为:依此邻接表存储的图，采用Prim算法画出其最小生成树的生成过程。四、算法分析题(2小题，每小题6分，共12分)1.该算法功能为：将十进制整数转换成二进制数输出。阅读算法，按标号填写 空缺的内容，要求统一填写在算法后面的标记处。其中所用函数原型说明如下：void Pop (SeqStack *S, DataType *x) ； /出栈void Push (SeqStack *S, DataType x) ； /进栈 int StackEmpty (SeqStack S) ； /判栈空 void Stacklnit (SeqStack *S) ； /栈
9、初始化typedef int DataType: #include/zSeqStack. h void conversion(int n, int r) SeqStack s:DataType x:char ch:Stacklnit(&s);wh订e (n0)n=n/r;wh订e (2)(3) printf (%d, x);(1)2.已知二叉树中的结点类型BinTreeNode定义为：typedef struct Node Datatype data;struct Node *lchild, *rchild; BinTreeNode;其中data为结点值域，lchild和rchild分别为指向
10、左、右子女结点的指针域。下 面递归函数完成的功能是从二叉排序树BST中查找值为X的结点，若查找成功 则返回结点地址，否则返回空。按标号填写空缺的内容，要求统一填写在算法后 面的标记处。BinTreeNode *SearchBST(BiTreeNode *T, DataType x) if(T=NULL|x=T-key) return (1)；if (xkey)ret urn(2)；elseret urn；五、算法设计题(1小题，每小题8分，共8分)1.阅读下列函数arrange()int arrange(int a,int l,int h,int x)/l和h分别为数据区的下界和上界int i,j,t；i=l； j=h； while(ij) while(i=x)j； while(i=x)i+；t=aj； aj=ai； ai=t； if(aix) return i； else return i-1 ；(1) 写出该函数的功能；(2) 写一个调用上述函数实现下列功能的算法：对一整型数组bn中的元素进 行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的 高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。
