文档介绍：课程测试试题(卷) ---------------------- 以下为教师填写-------------------- I、命题院(部): 数学与计算机科学学院 II、课程名称: 数据结构 III、测试学期: 20-20学年度第学期 IV、测试对象: 学院专业级班 V、问卷页数( A4 ):页 VI 、答卷页数( A4 ):页 VII 、考试方式: 闭卷(开卷、闭卷或课程小论文,请填写清楚) VIII 、问卷内容: (请老师在出题时安排紧凑,填空题象征性的留出一点空格, 学生将所有的答案做在答题纸上的规定位置,并写清楚大题、小题的题号) 一、一、单选题(每题 2 分,共 20分) ,不包括如下( B)方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 . 在带有头结点的单链表 HL 中,要向表头插入一个由指针 p 指向的结点,则执行(A)。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; ,在下列哪种情况下应当采用链表表示? (B) A. 经常需要随机地存取元素 B. 经常需要进行插入和删除操作 123,则下列序列中不可能是栈的输出序列的是(C) . AOV 网是一种( D)。 ,其平均查找长度( B)。 ,应将形参变量说明为(D)参数。 ,每个单链表中的结点都具有相同的( A)。 ( C)。 A. O(log 2n)B. O(nlog 2n)C. 0(n) D. 0(n 2) 10. 10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为(D)。 A. O(n) B. O(1) C. O(log 2n) D. O(n 2) 二、二、运算题(每题 6 分,共 24分) 。当结点之间存在 M 对N(M:N)的联系时,称这种结构为_____________________ 。 . 队列的插入操作是在队列的_________ 进行,删除操作是在队列的__________ 进行。 N的数组顺序存储一个栈时,假定用 top==N 表示栈空,则表示栈满的条件是_____________________ 。 n的单链存储的线性表,在表头插入元素的时间复杂度为_________ ,在表尾插入元素的时间复杂度为____________ 。 为一个二维数组,其每个数据元素占用 4 个字节,行下标 i从0 到7,列下标 j从0到3,则二维数组 W的数据元素共占用_ _____ _个字节。W中第 6行的元素和第 4列的元素共占用_ _______ _个字节。若按行顺序存放二维数组 W ,其起始地址为 100 ,则二维数组元素 W[6 ,3]的起始地址为_ ________ _。 . 广义表 A= (a,(a,b),((a,b),c)), 则它的深度为____________ ,它的长度为____________ 。 2的____________________ 树。一棵结点数为 N的二叉树,其所有结点的度的总和是_____________ 。 . 对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个______________ 。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________ 。 . 对于一棵具有 n 个结点的二叉树,用二叉链表存储时,其指针总数为_____________ 个, 其中_______________ 个用于指向孩子, _________________ 个指针是空闲的。 10. 10. 若对一棵完全二叉树从 0开始进行结点的编号,并按此编号把它顺序存储到一维数组 A 中,即编号为 0 的结点存储到 A[0] 中。其余类推,则 A[i] 元素的左孩子