数据结构阶段测试(6.1).doc

南京信息工程大学滨江学院 2011 ─2012学年第2学期 数 据 结 构课程试卷 试卷类型A考试类型 闭卷 注意：1、本课程为必修，学时为102，学分为 4 2、本试卷共4页；考试时间120分钟； 出卷时间：2012年5 月 3、姓名、学号等必须写在指定地方；考试时间：2012年6月1日 4、本考卷适用专业年级：实验班2011级任课教师：耿焕同,宣文霞 题号 一 二 三 四 五 六 七 八 九 十 十一 十二 总分 得分 阅卷人 （以上内容为教师填写） 专业年级班级 学号姓名  选择题 (每小题2分，共30分) 在数据结构中，从逻辑上可以把数据结构分为 。 动态结构和静态结构 B) 紧凑结构和非紧凑结构 线性结构和非线性结构 D）内部结构和外部结构 算法分析的目的是 。 找出算法的合理性 B) 研究算法的输人与输出关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性 关于线性表的说法，下面选项正确的是 。 A)线性表的特点是每个元素都有一个前驱元素和一个后继元素 B) 线性表是具有n(n≥0)个元素的一个有限序列 C) 线性表就是顺序存储的表 D) 线性表只能用顺序存储结构实现 n个顶点的连通图中边的条数至少为 。 0??? ?? ?? B)l??? ????? ??? C) n-l??? ? ?D）n 从一个具有n个结点的单链表中检索其值等于x的结点时，在检索成功的情况下，等概率需平均比较 个元素结点？ A) n/2 B) n C) (n+1)/2 D) (n-1)/2 在一个单链表中，已知q是p的前驱结点，若在q和p之间插入结点s ，则执行 。 s-next=p-next; p-next=s; p-next=s-next; s-next=p; q-next=s; s-next=p; p-next=s; s-next=q; 从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动 ?个元素。 n-i??? ? ??? B) n-i+l?? ????C) n-i-l??? ??D)i 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是 。 abdec B) debac C)debca D)abedc 一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 4，3，2，1 B）1，2，3，4 C）1，4，3，2 D）3，2，4，1 二叉树第k层上最多有个结点 。 2k B) 2k-1 C) 2k-1 D) 2k+1 用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1．．n]中，若结点R[i]有左孩子，则其左孩子是 。 R[2i-1] B) R[2i+1] C) R[2i] D) R[2/i] 如果从无向图的任一顶点出发进行一次深度优先有哪些信誉好的足球投注网站即可访问所有顶点，则该图一定是 。 完全图 B) 连通图 C) 有回路 D) 一棵树 无向图的邻接矩阵是一个 。 对称矩阵 B) 零矩阵 C)上三角矩阵 D) 对角矩阵 己知一个有序表为(11,22,33,44,55,66,77, 88,99), 则折半查找元素22需要比较 次。 2 B) 3 C) 4 D)5 下述几种排序方法中，空间复杂度最大的是 。 简单排序 B) 堆排序 C) 快速排序 D) 归并排序 填空题 (每小题1分，共10分) 线性表是n（n=0）个数据元素的____【1】____。其中n为数据元素的个数，定义为线性表的____【2】______。当n为