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

全国 2004 年 1 月高等教育自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的， 请将其代码填写在题后的 括号内。错选、多选或未选均无分。 1．下列数据组织形式中， （ ）的各个结点可以任意邻接。 A ．集合 B ．树形结构 C ．线性结构 D ．图状结构 2 ．设某二维数组 A ［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂 性的量级为（ ） A ．O （log 2n ） B ．O(n) 2 C ．O(nlog 2 n) D ．O(n ) 3 ．在线性表的下列存储结构中，读取元素花费时间最少的是（ ） A ．单链表 B ．双链表 C ．循环链表 D ．顺序表 4 ．将一个头指针为 p 的单链表中的元素按与原单链表相反的次序存放，则下列算法段 中的空白处应为 q=NULL; while (p!=NULL) { （ ） } p=q; A ．r=q; q=p; p=p - next; q - next=r; B ．q=p; r=q; p=p - next; q - next=r; C ．r=q; p=p - next; q=p; q - next=r; D ．q=p; p=p - next; r=q; q - next=r; 5 ．数组通常具有两种基本运算，即（ ） A ．创建和删除 B ．索引和修改 C ．读和写 D ．排序和查找 6 ．除根结点外，树上每个结点（ ） A ．可有任意多个孩子、任意多个双亲 B ．可有任意多个孩子、一个双亲 C ．可有一个孩子、任意多个双亲 D ．只有一个孩子、一个双亲 7 ．具有 100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、 右孩子，其余（ ）个指针域为空。 A ．50 B ．99 C ．100 D ．101 8 ．邻接表是图的一种（ ） A ．顺序存储结构 B ．链式存储结构 C ．索引存储结构 D ．散列存储结构 9 ．如果无向图 G 必须进行二次广度优先有哪些信誉好的足球投注网站才能访问其所有顶点，则下列说法中不正 确的是（ ） A ．G 肯定不是完全图 B ．G 一定不是连通图 C ．G 中一定有回路 D ．G 有 2 个连通分量 10．若构造一棵具有 n 个结点的二叉排序树，最坏的情况下其深度不会超过（ ） A ．n/2 B ． n C ．(n+1)/2 D ．n+1 11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值 的前面，下次的查找区间为从原开始位置至（