计数据结构期中试题.docVIP

计2006《数据结构》期中试题 班级_____________ 学号_________ 姓名____________ 成绩_______ 单项选择题（每小题2分 共28分） 在数据结构中，从逻辑上可以把数据结构分成 _____ 。 A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 2. 下面程序段的时间复杂度是______。 for(i=0;in;i++) for(j=1;jm;j++) A[i][j]=0 ； A. O(n) B. O(m+n+1) C. O(m + n) D. O(m*n) 线性表的链式存储结构是一种_____的存储结构。 A．随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 判断一个栈ST（最多元素为m0）为栈满的条件是_____ 。 A．ST-top != 0 B. ST-top == 0 C. ST-top != m0 D. ST-top == m0 一个队列的入队序列是1，2，3，4，则队列的输出序列是 _______。 A．4，3，2，1 B. 1，2，3，4 C. 1,4,3,2 D. 3, 2, 4, 1 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行 _____ 。 s-next = p; p-next = s; s-next = p-next; p-next = s; s-next = p-next; p = s; p-next = s; s-next = p; 在一个单链表中，若删除p所指结点的后续结点，则执行______ 。 p-next = p-next-next; p = p-next; p-next = p-next-next; p-next = p-next; p = p-next-next; 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删除结点的值，则执行_____ 。 A．x = HS; HS = HS-next; B. x = HS-data; C. HS = HS-next; x = HS-data; D. x = HS-data; HS = HS-next 9. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac, 它的前序遍历是_____ 。 A． acbed B. decab C. deabc D. cedba 10. 对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为.???????A. R - F ????B. n + R - F ????C. (R-F+1) mod n???? D. (n + R-F）mod n A. p指向头结点 B. p指向尾结点 C. *p的直接后继是头结点 D. *P的直接后继是尾结点 12. 广义表A = (a, (b), (), (c,d,e) )的长度为_____。 A. 4 B. 5 C. 6 D. 7 13. 一棵含18个结点的二叉树的高度至少为______。 A. 3 B. 4 C. 5 D. 6 14. 设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]中的位置为________。 A．32 B．33 C．41 D．65 15. 具有65个结点的完全二叉树的高度为_______。（根的层次号为1） A．8 B．7 C．6 D．5 真空题(每空1分 共22分) 在线性结构中，第一个结点 __没有____ 前趋结点，其余每个结点有且仅有__1__个前趋结点；最后一个结点____后续结点，其余每个结点有且仅有___个后续结点。 在树形结构中，树根结点没有__前趋___结点，其余每个结点有且仅有__1_个前趋结点；叶子结点没有__后继___结点，其余每个结点的后续结点可以___多个____。 对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运算时，可能发生栈的下溢。在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个,且存在一条从根到该结点的