2008 2009 学年第__一_学期期末考查试卷 [A]卷.doc

南 京 信 息 职 业 技 术 学 院 试 卷 2008 / 2009 学年第__一_学期期末考查试卷 [A]卷 课程名称： 数据结构 考试时间：100分钟 命题人 边长生 2008 年 12 月 15 日 审批人 年 月 日 使用班级：90718D 成绩： 。。 题号 一 二 三 四 总分 阅卷人 得分 一、选择题（40分，每题2分） 1、数据的基本单位是 。 A．数据结构 B.文件 C.数据元素 D.数据项 2、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为 。 A．O (n) B．O (1) C．O (n2) D．O (log2 n) 3、采用链式存储结构存储时，要求占用的存储空间地址 。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.可连续可不连续 4、若让元素1，2，3依次进栈，则出栈次序不可能出现 种情况。 A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2 5、链式栈与顺序栈相比，一个比较明显的优点是 。 A. 通常不会出现栈满的情况 B. 插入操作更加方便 C. 不会出现栈空的情况 D. 删除操作更加方便 6、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。 A.110 B.108 C.100 D.120 7、在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是 。 A.p-next=s; s-prior=p; p-next-prior=s; s-next=p-next; B.s-prior=p; s-next=p-next; p-next=s; p-next-prior=s; C. p-next=s; p-next-prior=s; s-prior=p; s-next=p-next; D. s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; 8、在一个顺序队列中，队首指针指向队首元素的_ _______位置。 　　A.前一个 B.后一个 C.当前 D.末尾 9、稀疏矩阵的压缩存储可以使用下列哪种存储方式： 。 A.二维数组 B.三维数组 C.三元组 D.散列 10、设有两个串t和p，求p在t中首次出现的位置的运算叫做 。 A.求子串 B.模式匹配 C.串替换 D.串连接 11、一颗二叉树上第5层的结点数最多为 。 A .8 B.16 C. 15 D. 32 12、在一棵二叉树中，度数为2的结点数等于n2，度数为1的结点数等于n1，那么度数为0的结点数等于是_______。 A.n1+1 B.n1+2 C.n2+1 D.n2+2 13、在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点的编号 。 A.2i-1 B.2i C.2i+1 D.2i+2 14、由带权为9, 2, 5, 7的四个叶子结点构造一棵哈夫曼树，则该树的带权路径长度为 。 A.23 B.37 C.46 D.44 15、设a，b为一颗二叉树上的两个结点，在中序遍历时，a在b前的条件是： 　　A. B. a在b左方 C. a是b的祖先 D. a在b的子孙 16、在一个具有n个顶点的有向完全图中，所含的弧数为 。 A．n B.n*(n-1) C.n*(n+1) D.n*(n-1)/2 17、n 个顶点的连通图至少有 条边。 A.n-1 B.n C.n+1 D.0 18、