《数据结构(题目)》由会员分享，可在线阅读，更多相关《数据结构(题目)（11页珍藏版）》请在金锄头文库上搜索。
1、一是非题1. 数据结构可用三元式表示（D，S，P）。其中：D 是数据对象，S 是 D 上的关系，P 是对 D的基本操作集。2 简单地说,数据结构是带有结构的数据元素的集合。3 判断带头结点的非空循环单链表（头指针为 L）中指针 p 所指结点是最后一个元素结点的条件是：p-next=L。4 线性表的链式存储结构具有可直接存取表中任一元素的优点。 5 线性表的顺序存储结构优于链式存储结构。6. 在单链表 P 指针所指结点之后插入 S 结点的操作是：P-next= S ; S- next = P-next;。7 对于插入、删除而言，线性表的链式存储优于顺序存储。8. 顺序存储方式的优点是存储密度大，
2、且插入、删除运算效率高。9. 对于插入、删除而言，线性表的链式存储优于顺序存储。10 线性表的顺序存储结构具有可直接存取表中任一元素的优点。11. 栈和队列是操作上受限制的线性表。12. 队列是与线性表完全不同的一种数据结构。13. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。14. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。15. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。16 队列是一种运算受限的线性表1. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所 以，二叉树是树的特殊情形。2.二叉树是一棵结点的度最大为二的树。 3. 赫夫曼树
3、中结点个数一定是奇数。4 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。5. 假设 B 是一棵树，B是对应的二叉树。则 B 的后根遍历相当于 B的后序遍历 。6. 通常，二叉树的第 i 层上有 2i-1个结点。7. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。8 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所 以，二叉树是树的特殊情形。9 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。10 由树结点的先根序列和后根序列可以唯一地确定一棵树。1 邻接多重表可以用以表示无向图，也可用以表示有向图。2 可从任意有向图中得到关于所有顶点
4、的拓扑次序。3 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。4. 关键路径是 AOE 网中源点到汇点的最短路径。5. 连通图 G 的生成树是一个包含 G 的所有 n 个顶点和 n-1 条边的子图。6. 一个无向图的连通分量是其极大的连通子图。7. 连通图的生成树是一个包含图 G 所有 n 个顶点和任意 n-1 条边的子图。8. 十字链表可以表示无向图，也可用以表示有向图。9. 邻接表可以表示有向图，也可以表示无向图。（ ）1. 二叉排序树的平均查找长度为 O(log)。2. 二叉排序树的最大查找长度与（LOG2N）同阶。3 选用好的 HASH 函数可避免冲突。4 折半查找不适用
5、于有序链表的查找。5 一般来说，折半查找不适用于有序链表的查找。6 二叉排序树的查找和折半查找的时间性能相同。1. 对于目前所知的排序方法，快速排序具有最好的平均性能。2 对于任何待排序序列来说，快速排序均快于冒泡排序。3 在最坏情况下，堆排序的时间性能是 O(nlogn),比快速排序好4 快速排序具有最好的平均时间性能，它在任何时候的时间复杂度都是 O（n log n）。选择题。从逻辑上可以把数据结构分成( )。A. 动态结构和静态结构 B. 顺序组织和链接组织C. 线性结构和非线性结构 D. 基本类型和组合类型下列程序段的时间复杂度为( )。s=i=0;while (snext=null
6、C. L-next=L D. L!=null 若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定的结点，将该结点与其后继（若存在）结点交换位置，使得经常被查找的结点逐渐移至表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。顺序表的存储结构为：typedef structElemType *elem; /数据元素存储空间，0 号单元作监视哨int length; /表长度SSTable;int search_seq(SSTable ST,KeyType key) /在顺序表 ST 中顺序查找关键字等于 key 的数据元素。/若找到，则将该元素与其后继交换位置
7、，并返回其在表中的位置，否则为 0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key) ;if( )ST.elemiST.elemi+1；return i;A. i0 B. i=0 C. inext=null C. L-next=L D. L!=null 假设用于通讯的电文仅由 6 个字符组成，字母在电文中出现的频率分别为 7, 19, 22, 6, 32, 14。 若为这 6 个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右） ，则频率为 7 的字符编码是（ ） ，频率为 32的字符
8、编码是（ ） 。a: 00 b: 01 c: 10 d: 11 e: 011 f: 110 g: 1110 h:1111 对二叉排序树（ ）可得到有序序列。 a:按层遍历 b:前序遍历 c:中序遍历 d:后序遍历设一棵二叉树 BT 的存储结构如下:1 2 3 4 5 6 7 8lchild 2 3 0 0 6 0 0 0data A B C D E F G Hrchild 0 5 4 0 8 7 0 0其中 lchild，rchild 分别为结点的左、右孩子指针域，data 为结点的数据域。则该二叉树的高度为( )；第 3 层有( )个结点（根结点为第 1 层） 。A2 B. 3 C. 4 D
9、. 5先序遍历图示二叉树可得到（ ）的序列。a)A B H D E F I C Gb)H B E D F I A C Gc)H E I F D B G C A(A) (B) (C) (H) (D) (G) (E) (F)(I)在有 n 个结点的二叉树的二叉链表表示中，空指针数 （ ） 。a.不定 b.n+1 c.n d.n-1若某二叉树有 20 个叶子结点，有 20 个结点仅有一个孩子，则该二叉树的总结点数是( )。A40 B. 55 C. 59 D. 61已知某二叉树的先序遍历次序为 abcdefg 中序遍历次序为 badcgfe，则该二叉树的后序遍历次序为（ ）。层次遍历次序为（ ）。a:
10、 abcdefg b: cdebgfa c: bdgfeca d: edcgfba .图示的三棵二叉树中( c)为最优二叉树。A) B) C) c a 2 7 a b c d d b 7 5 2 4 4 5 a b c d 7 5 2 4 已知某二叉树的后序遍历和中序遍历次序分别为 DBFGECA 和 BDACFEG。则其先序遍历次序为（ ） ，层次遍历次序为（ ） 。a: abcdefg b: abdcefg c: abcdfeg d: abcdegf 已知某树的先根遍历次序为 abcdefg 后根遍历次序为 cdebgfa。若将该树转换为二叉树,其后序遍历次序为（ ） 。a: abcdef
11、g b: cdebgfa c: cdegbfa d: edcgfba 设 x 和 y 是二叉树中的任意两个结点，若在先根序列中 x 在 y 之前，而在后根序列中 x 在 y 之后，则 x 和 y 的关系是( )。A. x 是 y 的左兄弟 B. x 是 y 的右兄弟C. x 是 y 的祖先 D. x 是 y 的子孙用三叉链表作二叉树的存储结构，当二叉树中有 n 个结点时，有( )个空指针。A. n-1 B. n C. n+1 D. n+2 1. 在有 n 个结点的二叉树（二叉链表表示）中，空指针数 。A.不定 B.n+1 C.n D.n-1对一棵完全二叉树进行层序编号。则编号为 n 的结点若存
12、在右孩子,其位序是( )。编号为 n 的结点若存在双亲,其位置是( )。a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1) 对一棵完全二叉树进行层序编号。则编号为 n 的结点若存在右孩子,其位置是( )。编号为 n 的结点若存在双亲,其位置是( )。a: n b: 2n c:2n-1 d:2n+1 e: n /2 f: 2(n+1) 设森林 F 中有三棵树，第一、第二和第三棵树的结点个数分别为 m1、m2 和 m3，则与森林 F 对应的二叉树根结点的右子树上的结点个数是( 13 )。A. m1 B. m1+m2 C. m3 D. m2+m3 下列二叉树中，( )可
13、用于实现符号不等长高效编码。a:最优二叉树 b:次优查找树 c:二叉平衡树 d:二叉排序树邻接表存储结构下图的深度优先遍历算法类似于二叉树的( )遍历。A. 先根 B. 中根 C. 后根 D. 层次设无向图 G = (V,E)和 G= (V,E)，若 G是 G 的生成树，则下面不正确的说法是( )。A. G是 G 的子图 B. G是 G 的连通分量C. G是 G 的无环子图 D. G是 G 的极小连通子图且 V= V任何一个连通图的最小生成树( 27 )。A只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在已知某无向图的邻接表如下所示； ( 19 )是其原图。 ( 20 )是按该邻接表遍历所得深度优先生成
