自考数据结构导论试题真题.docxVIP

全国 2004 年 1 月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 下列数据组织形式中，（ ）的各个结点可以任意邻接。 集合 B．树形结构 C．线性结构 D．图状结构 设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ ） A．O（log n） 2 C．O(nlog n) 2 B．O(n) D．O(n2) 在线性表的下列存储结构中，读取元素花费时间最少的是（ ） 单链表C．循环链表 双链表D．顺序表 将一个头指针为 p 的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为 q=NULL; while (p!=NULL) { （ ） } p=q; r=q; q=p; p=p - next; q - next=r; q=p; r=q; p=p - next; q - next=r; r=q; p=p - next; q=p; q - next=r; q=p; p=p - next; r=q; q - next=r; 5．数组通常具有两种基本运算，即（ ） 创建和删除C．读和写 索引和修改D．排序和查找 除根结点外，树上每个结点（ ） A．可有任意多个孩子、任意多个双亲B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲 具有100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（ ）个指针域为空。 A．50 B．99 C．100 邻接表是图的一种（ ） A．顺序存储结构 C．索引存储结构 D．101 B．链式存储结构D．散列存储结构 如果无向图 G 必须进行二次广度优先有哪些信誉好的足球投注网站才能访问其所有顶点，则下列说法中不正确的是（ ） A．G 肯定不是完全图 C．G 中一定有回路 B．G 一定不是连通图 D．G 有 2 个连通分量 若构造一棵具有 n 个结点的二叉排序树，最坏的情况下其深度不会超过（ ） A．n/2 C．(n+1)/2 B．n D．n+1 若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（ ） A．该中间位置 C．该中间位置＋1 B．该中间位置－1 D．该中间位置／2 12．散列文件不能（ A．随机存取 ） B．索引存取 C．按关键字存取 D．直接存取 若检索顺序文件各个记录的概率相同，设文件占用的页块数为 n，则按关键字存取时的平均访问外存次数为（ ） A．n/2 C．n/4 B．n D．log n 下列关键码序列中，属于堆的是（ ） A．（15，30，22，93，52，71） C．（15，52，22，93，30，71） B．（15，71，30，22，93，52） D．（93，30，52，22，15，71） 15．已知 10 个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（ ） A．16，28，34，54，73，62，60，26，43，95 B．28，16，34，54，62，73，60，26，43，95 C．28，16，34，54，62，60，73，26，43，95 D．16，28，34，54，62，60，73，26，43，95 二、填空题（本大题共 13 小题，每小题 2 分，共 26 分） 请在每小题的空格中填上正确答案。错填、不填均无分。 下列程序段的时间复杂性量级是 。 for (i=1;in; i++) for (j=1; ji; j++) t=t+1; 在顺序存储的线性表（a ,a …，a ）中的第i (1≤i≤n)个元素之前插入一个元素，则 1 2 n 需向后移动 个元素。 在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现： ； sq - data[sq - top]=x； 19．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的 。 设有 k 个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i 次合并时已找到权最小的结点 x 和权次小的结点 y，用 T［x］.wt 表示结点 x 的权值，已知 T［x］.wt=m, T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为 。 在下列树中，结点 H 的祖先为