1、一是 非题 1. 数据结构 (应该是抽象数据类型 )可用三元式表示 (D， S， P)。其中： D 是数据对象， S 是D 上的关系， P 是对 D 的基本操作集。 (f) 2 简单地说 ,数据结构是带有结构的数据元素的集合。 (t) 3 判断带头结点的非空循环单链表 (头指针为 L)中指针 p 所指结点是最后一个元素结点 的条件是： p-next=L。 (t) 4 线性表的链式存储结构具有可直接存 取 表中任一元素的优点。 (f) 5 线性表的顺序存储结构优于链式存储结构。 (f) 6. 在单链表 P 指针所指结点之后插入 S 结点的操作是： P-next= S ; S- next = P-
2、next;。 (f) (顺序弄反了 S- next = P-next; P-next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。 (t) 8. 顺序存储方式的优点是存储密度大， 且插入、删除运算效率高 。 (f) 9. 栈和队列是操作上受限制的线性表。 (t) 10. 队列是与线性表 完全不同 的一种数据结构。 (f) (栈和队列是操作上受限制的线性表 ) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限 一端 进行。 (f) (两 端 ) 12. 栈和队列也是线性表。如果需要， 可对它们中的任一元素进行操作 。 (f) ( “如果需要 ,可对它们中的任一元素
3、进行操作 .” 这里的意思是在 O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。 ) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。 (f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制， 所以，二叉树是树的 特殊情形 。 (f) (二叉树和树相互 独立 ) 15 二叉树是一棵结点的度最大为二的树。 (f) (二叉树和树相互独立 ) 16 赫夫曼树中结点个数一定是奇数。 (t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面
4、。 (t) (LDR) 18 假设 B是一棵树， B是对应的二叉树。则 B的后根遍历相当于 B的后序遍历 。 (f) (后根遍历相当于中序遍历 ) 19. 通常，二叉树的第 i 层上有 2i-1 个结点。 (f) (应该为 12i-1 个 ) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 (t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。 (t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树 。 (t) 23 邻接多重表可以用以表示无向图， 也可用以表示有向图 。 (f) (只能表示无向图，有向图用十字链表 ) 24 可从 任意有
5、向图 中得到关于所有顶点的拓扑次序。 (f) (带环图没有 ) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。 (t) 26 关键路径是 AOE 网中源点到汇点的 最短 路径。 (f) (最长 ) 27 连通图 G 的生成树是一个包含 G 的 所有 n 个顶点和 n-1 条边的子图。 (f) （极大连通子图） 28 一个无向图的连通分量是其极大的连通子图。 (t) 29 十字链表 可以表示无向图 ，也可用以表示有向图。 (f) (有向图 ) 30 邻接表可以表示有向图，也可以表示无向图。 (t) 31. 二叉排序树的平均查找长度为 O(log )。 (t) 32. 二叉排序
6、树的最大查找长度与 (LOG2N)同阶。 (f) 33 选用好的 HASH 函数可 避免冲突 。 (f) (无法避免，只能减少冲突 ) 34 折半查找不适用于有序链表的查找。 (t) (因链表地址不连续 ) 35. 对于目前所知的排序方法，快速排序具有最好的平均性能。 (t) 36 对于任何待排序序列来说， 快速排序均快于冒泡排序 。 (f) (快速排序希望初始数据随机 ) 37 在最坏情况下，堆排序的时间性能是 O(nlogn),比快速排序好 (t) (堆排序与初始数据无关 ) 38 快速排序具有最好的平均时间性能， 它在任何时候的时间复杂度都是 O(n log n)。 (f) (退化到 n
7、2) 39. 字符串是数据对象特定的线性表。 (t) 40. 空串与空格串是 相同 的。 (f) (空串长度为 0，空格串长度为其长度 ) 41. 对于一棵 m 阶的 B-树 .树中每个结点 至多有 m 个关键字 .除根之外的所有非终端结点至 少有 m/2个关键字 。 (f) (至少有 m 颗子树，关键字数目至少 m-1) 42. 当二叉排序树是一棵平衡二叉树时，其平均查找长度为 O(log2n)。 (t) 43. 广义表的 表头 和表尾都是广义表。 (f) (表头可能是原子，也可能是列表，而其表尾必定为列表 ) 44 二维数组是其数据元素为线性表的线性表。 (t) 选择题。 1 从逻辑上可以
8、把数据结构分成 ( c )。 A. 动态结构和静态结构 B. 顺序组织和链接组织 C. 线性结构和非线性结构 D. 基本类型和组合类型 2 线性表 L 在 ( b )情况下适于使用链表结构实现。 A. 不需修改 L 的结构 B. 需不断对 L 进行删除、插入 C. 需经常修改 L 中结点值 D. L 中含有大量结点 3 带头结点的单链表 L 为空的判断条件是 b 。 带头结点的循环链表 L 为空的判断条件是 c 。 A. L=null B. L-next=null C. L-next=L D. L!=null 4 若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定 的
9、结点，将该结点与其后继 (若存在 )结点交换位置，使得经常被查找的结点逐渐移至 表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。 顺序表的存储结构为： typedef struct ElemType *elem; /数据元 素存储空间， 0 号单元作监视哨 int length; /表长度 SSTable; int search_seq(SSTable ST,KeyType key) /在顺序表 ST 中顺序查找关键字等于 key 的数据元素。 /若找到，则将该元素与其后继交换位置，并返回其在表中的位置，否则为 0。 ST.elem0.key=key; i=ST.length;
10、while(ST.elemi.key!=key) f ; if( G ) ST.elemiS T.elemi+1； e ； return i; A. i0 B. i=0 C. i哈夫曼树 25 已知某二叉树的后序遍历和中序遍历次序分别为 DBFGECA 和 BDACFEG。 则其先序遍历次序为 ( b )，层次遍历次序为 ( a )。 a: abcdefg b: abdcefg c: abcdfeg d: abcdegf 后序： DB FGEC A 谁后访问谁是根 L R D 中序 ： BD A CFEG L D R (A) (B) (C) (D) (E) / (F) (G) 26 已知某树的
11、先根遍历次序为 abcdefg 后根遍历次序为 cdebgfa。 若将该树转换为二叉树 ,其后序遍历次序为 ( d )。 a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba 先根： a bcdefg 后根： cdebgf a (a) (b) (f) / | (c) (d) (e) (g) 27 设 x 和 y 是二叉树中的任意两个结点，若在先根序列中 x 在 y 之前，而在后根序列中 x 在 y 之后，则 x 和 y 的关系是 ( c )。 A. x 是 y 的左兄弟 B. x 是 y 的右兄弟 C. x 是 y 的祖先 (不一定是父子 ) D. x 是 y
12、 的子孙 28 用三叉链表作二叉树的存储结构，当二叉树中有 n 个结点时，有 ( d )个空指针。 A. n-1 B. n C. n+1 D. n+2 三叉链表：较二叉链表多一双亲指针域 二叉链表： 2n - (n-1) = n+1 2n 个指针域 有效指针域 根节点双亲指针必为空，故 n+1+1=n+2 29 对一棵完全二叉树进行层序编号。则编号为 n 的结点若存在右孩子 ,其位序是 ( d )。 编号为 n 的结点若存在双亲 ,其位置是 ( a )。 a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1) 30 设森林 F 中有三棵树，第一、第二和第三棵树的结点个
13、数分别为 m1、 m2 和 m3，则与 森林 F 对应的二叉树根结点的右子树上的结 点个数是 ( d )。 A. m1 B. m1+m2 C. m3 D. m2+m3 (A) (B) (C) / / / m1 m2 m3 (A) / (左 ) (右 ) m-1 m2+m3 31 下列二叉树中， ( a )可用于实现符号不等长高效编码。 a:最优二叉树 b:次优查找树 c:二叉平衡树 d:二叉排序树 哈夫曼树 32 邻接表存储结构下图的深度优先遍历算法类似于二叉树的 ( a )遍历。 A. 先根 B. 中根 C. 后根 D. 层次 33 设无向图 G = (V,E)和 G= (V,E)，若 G是
14、 G 的生成树，则下面不正确的说法是 ( b )。 A. G是 G 的子图 B. G是 G 的连通分量 C. G是 G 的无环子图 D. G是 G 的极小连通子图且 V= V 生成树：极小 连通分量：极大 34 任何一个连通图的最小生成树 ( b )。 A只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 35 深度优先遍历图使用了数据结构 (b )，而广度优先遍历图使用了数据结构 ( c )。 A)数组 B)栈 C)队列 D)线性表 DFS：栈（递归） BFS：队列（层次） 36 已知某有向图的邻接表存储结构如图所示。 根据存储结构依教材中的算法其深度优先遍历次序为 ( d )
15、。 广度优先遍历此序为 ( c )。各强连通分量的顶点集为 ( h )。 a: abcde. b: edcba. c: ecdab. d: ecadb. e: abc 及 ed f: bc 及 aed g: ab 及 ced h: ac 及 bed 37 下列查找方法中 ( a )适用于查找单链表。 A)顺序查找 B)折半查找 C)分块查找 D)hash 查找 38 下列算法中 (c )适用于求图的最小代价生成树。 ( b )能对图作广度优先遍历。 A)DFS 算法 B)BFS 算法 C)Prim 算法 D)Dijkstra 算法 39 关键路径是指在只有一个源点和一个汇点的有向无环网中源点至
16、汇点 ( c )的路径。 a:弧的数目最多 b:弧的数目最少 c:权值之和最大 d:权值之和最小 40 哈 希表的查找效率取决于 ( d )。 a: 哈希函数 b:处理冲突的方法。 c:哈希表的装填因子。 d:以上都是 哈希函数是否均匀； 处理冲突的方法； 哈希表的装填因子。 41 在 Hash 函数 H(k)=k MOD m 中，一般来说， m 应取 ( c )。 A. 奇数 B. 偶数 C. 素数 D. 充分大的数 素数可以有效的减少 Hash 冲突 42 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕， 可采用 a 方法。 A.设置监视哨 B.链表存贮 C.二分查找 D.
17、快速查找 43 静态查找表和动态查找表的区别在于 ( b )。 A. 前者是顺序存储，而后者是链式存储 B. 前者只能进行查找操作，而后者可进行查找、插入和删除操作 C. 前者只能顺序查找，而后者只能折半查找 D. 前者可被排序，而后者不能被排序 动态查找表在查找过程中插入元素或者从查找表中删除元素 静态查找表只是查找特定元素或者检索特定元素的属性 最通俗的解释：动态查找表可以对查找表结构进行修改，而静态查找表只是查询 0 E 2 1 1 D 0 3 4 2 C 4 3 B 1 2 0 4 A 2 44 在一个含有 n 个元素的有序表上 进行折半查找，找到一个元素最多要进行 ( b )次元素
18、比较。 A log2(n) B. log2(n)+1 C. log2(n+1) D. log2(n+1)+1 折半查找每次都会把范围缩小一半，因为最后剩一个元素时，也要执行查找过程，所以 +1。 每次二分 直到最后一次才找到 就会有 2k = n / 2 得到 k = log2n + 1 45 设输入序列为 20, 45, 30, 89, 70, 38, 62， 19 依次插入到一棵 2-3 树中 (初始状态为空 )， 该 B-树为 ( b )。再删除 38，该 B-树为 ( f )。 （ 30 62 ） （ 45 ） （ 19， 20）（ 38 45 ） （ 70， 89 ） （ 30 ）
19、（ 70 ） （ 19 20） （ 38 ）（ 62 ） （ 89 ） a: b: （ 45 70 ） （ 45 ） （ 20） （ 62 ） （ 89 ） （ 20 ） （ 70 ） （ 19）（ 30 ） （ 19 ） ( 30,38 ）（ 62 ） （ 89 ） c: d: （ 30 70 ） （ 45 ） （ 19， 20） （ 45 62） （ 89 ） （ 20 ） （ 70 ） （ 19 ） （ 30 ）（ 62 ） （ 89 ） e: f: 46 根据插入次序 (80， 90， 100， 110， 85， 70， 75， 60， 72)建立二叉排序树。 图 ( a )是最终变化
20、的结果。若仍以该插入次序建立平衡二叉树。图 ( c )是最 终变化的结果。 80 80 70 90 75 90 60 75 85 100 60 70 85 100 72 110 72 110 a: b: 90 90 75 100 80 100 70 80 110 75 70 85 110 60 72 85 60 72 c: d: 47 若有序表中关键字序列为： 14， 20， 25， 32， 34， 45， 57， 69， 77， 83， 92。对其进行 折半查找，则在等概率情况下，查找成功时的平均查找长度是 ( c )。查找 32 时需进 行 ( c )次比较。 A. 1 B. 2 C. 3
21、 D. 4 48 已知哈希表地址空间为 A9，哈希函数为 H(k)=k mod 7，采用线性探测再散列处理冲突。 若依次将数据序列： 76,45,88,21,94,77,17 存入该散列表中，则元素 17 存储的下标为 ( h )； 在等概率 情况下查找成功的平均查找长度为 ( c )。 A. 0 B. 1 C. 2 D. 3 E. 4 F. 5 G. 6 H. 7 49 若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序， 则该二叉树是 ( c )。 A. 二叉排序树 B. 赫夫曼树 C. 堆 D. 平衡二叉树 50 当待排序序列的关键字次序为倒序时，若需为之进行正序
22、排序，下列方案中 ( d )为佳。 A. 起泡排序 B. 快速排序 C. 直接插入排序 D. 简单选择排序 51 下列排序算法中， ( d)算法可能会出现：初始数据有序时，花费的时间反而最多。 A. 堆排序 B. 起泡排序 C. 归并排序 D. 快速排序 52 在下列排序方法中 ， ( c )方法平均时间复杂度为 0(nlogn)， 最坏情况下时间复杂度为 0(n2)； ( d )方法所有情况下时间复杂度均为 0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 53 已知一组待排序的记录关键字初始排列如下： 56,26,86,35,75,19,77,58,48,42 下列选择中 ( d )是快速排序一趟排序的结果。 ( c )是希尔排序 (初始步长为 3)一趟排序的结果。 ( a )是初始堆 (大堆顶 )。 A)86,75,77,58,42,19,56,35,48,26. B)26,56,35,75,19,77,58,48,42,86. C)35,26,19,42,58,48,56,75,86,77. D)42,26,48,35,19,56,77,58,75,86. 三填空题
