《【2017年整理】数据结构练习题》由会员分享，可在线阅读，更多相关《【2017年整理】数据结构练习题（22页珍藏版）》请在金锄头文库上搜索。
1、一、 单项选择题1 关键路径是指 AOE(Activity On Edge)网中_。 (a). 最长的回路 (b). 最短的回路(c) 从源点到汇点(结束顶点)的最长路径 (d). 从源点到汇点(结束顶点)的最短路径2 以下序列中不符合堆定义的是_。 (a)(102，87，100，79，82，62，84，42，22，12，68) (b)(102 ，100 ，87，84，82 ，79，68，62，42，22，12) (c)(12，22，42，62，68，79，82，84，87，100，102) (d)(102 ，87， 42，79，82， 62，68，100，84，12，22)3 一个具有 76
2、7 个结点的完全二叉树，其叶子结点个数为_。 (a). 383 (b). 384 (c). 385 (d). 3864. 一个二叉树的前序遍历序列为 ABCDEFG，它的对称序遍历序列可能是（ ）(a). CABDEFG (b). ABCDEFG (c). DACEFBG (d). EABCDFG5. 高度为 h 的完全二叉树（仅含根结点的二叉树高度为零）的结点最少是多少（ ）(a). h1 (b). 2h1 (c). 2h+11 (d). 2h6. 对包含 n 个关键码的散列表进行检索，平均检索长度是（ ）(a). O( log2n ) (b). O( n ) (c). O(n log2n
3、) (d). 不直接依赖于 n7. 设有关键码初始序列 Q,H,C,Y,P,A,M,S,R,D,F,X，新序列F,H,C,D,P,A,M,Q,R,S,Y,X是采用下列哪种排序方法对初始序列进行第一趟扫描的结果？(a). 直接插入排序 (b). 二路归并排序 (c). 以第一元素为枢轴（或分界）元素的快速排序 (c). 基数排序8. 下列说法中错误的是 (a). n 个结点的树的各结点度数之和为 n-1 (b). n 个结点的无向图最多有 n*(n-1)条边(c). 用相邻矩阵存储图时所需存储空间大小与图的结点数有关，而与边数无关(d). 散列表中碰撞的可能性大小与负载因子有关9.堆是一种特殊的
4、数据结构，下面哪一个是堆：(a)19,75,34,26,97,56；(b)97,26,34,75,19,56；(c)19,56,26,97,34,75；(d)19,34,26,97,56,75；10.下面关于 B 树和 B+树的叙述中，不正确的是(a) B 树和 B+树都是平衡的多分树； （b）B 树和 B+树都是可用于文件的索引结构；(c) B 树和 B+树都能有效地支持顺序检索；(d) B 树和 B+树都能有效地支持随机检索；11.在数据结构中，从逻辑上可以把数据结构分成：(a)动态结构和静态结构； (b)紧凑结构和非紧凑结构；(c)线性结构和非线性结构； (d)内部结构和外部结构；12.
5、若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p1，p2，p3，pn, 那么p1=n；pi 为：(a)i； (b)n=i； (c)n-i+1； (d)不确定；13.判断一个循环队列 QU（最多元素 m0）为空的条件是：(a)QU-front = = QU-rear； (b) QU-front! = QU-rear；(c) QU-front = = (QU-rear+1)%m0； (d) QU-front ! = (QU-rear+1)%m0；14.表达式 a*(b+c)-d 的后缀表达式是(a)abcd*+-； (b)abc+*d-； (c)abc*+d-； (d)*-a+bc；15
6、.在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点，则执行：(a)s-next = p-next; p-next = s；(b)p -next = s-next; s-next = p；(c) q-next =s; s-next = p； (d) p-next =s; s-next = q；16.在一个链队中，假设 f 和 r 分别为队首和队尾指针，则插入 s 所指结点的运算是：(a) f-next = s；f=s；(b) f-next = s；r=s；(c) s-next = r；r=s；(d) s-next = f；f=s；17.将递归算法
7、转换成对应的非递归算法时，通常需要使用(a) 栈 (b) 队列(c) 链表 (d) 树18.树最适合用来表示(a) 有序数据元素 (b) 无序数据元素(c) 元素之间具有分支层次关系的数据 (d) 元素之间相关联的数据19.要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的查找方法是：(a) 分块查找 (b) 顺序查找(c) 二分查找 (d) 散列查找20.A node in a tree that does not have any children is called (a) a leaf； (b) an internal node； (c) a root； (d) an e
8、mpty node； 21.对于一棵深度为 2（仅含根结点的二叉树高度为零）的二叉树，它的总节点数：(a) 至多 7 个 (b)至多 2 个 (c) 节点数不限 (d) 至多 4 个 22.下面的伪码是对二叉树操作算法的片段：print( node )if( there is a left child ) print( left child );print data;if( there is a right child ) print( right child );这个算法是：（a）折半查找； （b）前序遍历； （c）中序遍历； （d）后序遍历；23.下面哪个序列不是折半查找（二分查找）所访问
9、的数值序列(a) 10, 20, 30, 40, 50； (b) 50, 40, 30, 20, 10； (c) 10, 20, 30, 15, 18； (d) 30, 35, 40, 45, 4224.递归函数可以调用自身多少次?(a) 至多 1 次; (b) 任意次数; (c) 0 次; (d) 至多 2 次;25.分析下面函数：int f( int n )if( n = = 0 ) return 0;if( (n & 1) = = 0 ) return f(n/2);return f(n/2) + 1;调用函数 f(10)的返回值是：(a) 1； (b) 3； (c) 5； (d) 2；
10、26.假如 n,m=0，那么下面函数的功能是：int ff( int n, int m )if( n = 0 ) return m;return ff( n-1, m*n );(a) 计算 m * (n!)； (b) 计算最大公约数； (c)计算最小公倍数； (d) 计算(m + n)!；27.总的来说，哈希方法（hashing，也称散列方法）的主要问题在于：(a)哈希函数难以计算； (b)哈希表的存取速度慢；(c)会发生冲突； (d)哈希表占很多内存；28.对于一个大小为 m 含有 n 项的哈希表，它的负载(load)因子是：(a) m - n； (b) n + m； (c) m/n； (d
11、) n/m ；29.下面对 p 的声明，那一个是指向整数的指针：(a) int *p； (b) int p； (c) int &p； (d) int *p；30.假设 Thing 是一个用户定义的类，B 是 Thing 的一个实例，对于下面的代码段Thing A = B用到了类 Thing 中的哪一个成分：(a)赋值操作符； (b)析构函数； (c)构造函数； (d)复制构造函数；31.下面对类的部分描述用于说明一种用户定义的实数实现：class RealNumber .RealNumber( float x );RealNumber( float x, float y=0 );这段代码可能错
12、在哪里?(a)在构造函数中不允许时有缺省值； (b)没有错误；(c)第二个构造函数与第一个不一致； (d)用两个实数参数无法创建一个实数；32.面向对象的程序设计最适合下面哪一种开发要求:(a)程序是一个完整的程序模块；(b)提供完善的代码复用；(c)获得高效率；(d)对封装的需求；33.对于有 n 个节点 e 条边的图，如果用邻接表表示，则计算全部入度的时间复杂度是:(a) O(n + e)； (b) O(n2)； (c) O(n3)； (d) O(n * e) ；34.结定结点的关键字序列（、） ，对它按字母的字典顺序进行排列， 快速排序的第一趟结果是：(a)（C、 B、D、A、F、E、I
13、、J、G、H ） (b)（C、B、D、A、E、F 、I 、G 、J、H ）(c)（B、A、D、E、F、G、I、J、H、C） (d)（B、C、D、A、E、F、I、J、G、H）35.计算机算法是指(a) 数值计算方法 (b) 对抽象数据结构的操作方法(c) 非数值计算方法 (d) 解决问题的有限运算序列36、对于顺序存储的队列，存储空间大小为 n，头指针为 F，尾指针为 R。若在逻辑上看一个环，则队列中元素的个数为.( )(a) R-F (b).n+R-F (c).(R-F+1)mod n (d).(n+R-F)mod n37、链表不具备的特点是( )。 A可随机访问任何一个元素 B插入、删除操作
14、不需要移动元素 C无需事先估计存储空间大小 D所需存储空间与线性表长度成正比 38、对矩阵压缩存储的主要目的是( )。 A方便运算 B节省存储空间 C 降低计算复杂度 D提高运算速度 39、判断“链式队列为空 ”的条件是 ( )（front 为头 指针，rear 为尾指针） 。Afront=NULL Brear=NULL Cfront=rear Dfront!=rear 40、关于字符串的判定语句中正确的是( )。 A字符串是一种特殊的线性表 B 串的长度必须大于零 C字符串不属于线性表的一种 C 空格字符组成的串就是空串 41、有 100 个结点的树中，其边的数目为( )。 A101 B100 C 99 D98 42、在程序的执行过程中，用 ( )结构可实现嵌套调用函数的正确返回。 A队列 B栈 C树 D图 43、已知递归函数 f(n)的功能是计算 1+ 2+n，且 n1 ，应采用的代码段是( )。Aif n=l then return 1 else return n+f(n-1) Bif n=l then return 1 else return n+f(n+1) Cif n=l then return 0 else retu
