数据结构中的自测题个人整理

1、 算法的计算量的大小称为计算的（ B ）。 A. 效率 B. 复杂性 C. 现实性 D. 难度 一个算法应该是（ B ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 下面说法错误的是（ C ） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3) 在数据结构中，从逻辑上可以将之分为( D )。【中南大学2005一

2、.1(2分)】 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 计算算法的时间复杂度是属于一种( B )。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 可以用( D )定义一个完整的数据结构: A. 数据元素 B. 数据对象 C. 数据关系 D. 抽象数据类型 算法分析的目的是_C_。 A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 【北京理工大学2006 五.1(1分）】 设计一个“好”的算法应考虑达到的

3、目标有_ABCD_。 A. 是可行的 B. 是健壮的 C. 无二义性 D. 可读性好 【华中科技大学2006 二.3(2分）】 线性表是具有n个（ C ）的有限序列（n>0）。 【清华大学 1998 一.4（2分）】 A表元素 B字符 C数据元素 D数据项 E信息项 若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式( D )。 A.单链表 B.双向链表 C.单循环链表 D.顺序表【北京理工大学2004一.3(1分)】 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A. 单链表 B.

4、仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表 【南开大学 2000 一.3】 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( A )最节省时间。 A. 带头结点的双循环链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 单链表 【江苏大学 2006 一.3（2分）】 静态链表中指针表示的是( C ) A.下一元素的地址 B. 内存储器的地址 C.下一元素在数组中的位置 D. 左链或右链指向的元素的地址 【中南大学2003二.2 (1分)】 下述哪一条是顺序存储结构的优点？（ C ） 【江苏大学 2006 一.1（2分）】 A插入运算方便 B可方便地用于

5、各种逻辑结构的存储表示 C存储密度大 D删除运算方便 下面关于线性表的叙述中，错误的是哪一个？（ B ） 【北方交通大学2001一.14（2分）】 A线性表采用顺序存储，必须占用一片连续的存储单元 B线性表采用顺序存储，便于进行插入和删除操作 C线性表采用链接存储，不必占用一片连续的存储单元 D线性表采用链接存储，便于插入和删除操作。 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 【哈尔滨工业大学 2001 二.1（2分）】 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表 链表不具有的特点是（ B ） 【福州大学 19

6、98 一.8 (2分)】 A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ） 【南京理工大学 2000 一.3（1.5分）】 A.(1),(2) B.(1) C.(1),(2),(3) D.(2)对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。 【青岛大学 2000

7、五.1（2分）】 A. O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)单链表中，增加一个头结点的目的是为了( C ）。 【江苏大学 2005 一.3（2分）】 A使单链表至少有一个结点 B标识表结点中首结点的位置 C方便运算的实现 D说明单链表是线性表的链式存储对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（ D ）。 【北方工业大学2004一.1(3分）】 A p->right=s ; s->left=p; p->right->left=s ; s->right=p->right; B

8、 p->right=s ; p->right->left=s ; s->left=p; s->right=p->right; C s->left=p; s->right=p->right; p->right=s ; p->right->left=s ; ; D s->left=p; s->right=p->right; p->right->left=s ; p->right=s ; 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ） 【北京工商大学 2001 一

9、.5（3分）】 Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL 1. 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( B ) A. 栈 B. 队列 C. 树 D. 图【2009年全国硕士研究生入学计算机学科专业基础综合试题】 2. 设栈S和队列Q的初始状态均为空，元素a,b,c,d,e, f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是( C

10、) A. 1 B. 2 C. 3 D. 4 【2009年全国硕士研究生入学计算机学科专业基础综合试题】 1、设将整数1、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答以下问题： （1）若入栈次序为push(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop( )，则出栈的数字序列为什么？( 1 3 2 4 ) （2）能否得到出栈序列423和432？并说明为什么不能得到或如何得到。(不能，能) 下面关于串的的叙述中，哪一个是不正确的？ B A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D

11、串既可以采用顺序存储，也可以采用链式存储 串是一种特殊的线性表，下面哪个叙述体现了这种特殊性？ C A. 数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 串的长度是指（ B ） 【北京工商大学 2001 一.6 （3分）】 A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符的个数 D串中所含非空格字符的个数 设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ D ）。 【中科院计算所 1997 】 A2n-1 Bn2 C(n2/2)+(n/2) D(n2/2)+(n/2)-1 E.

12、(n2/2)-(n/2)-1 F. 其他情况 判断题： 数组是同类型值的集合。（ T ） 从逻辑结构上看，n维数组的每个元素均属于n个向量。（ T ） 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ F ） 若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是( A )。 A. 1040 B. 1042 C. 1026 D. 备选答案A，B，C都不对 【华中科技大学2004一.4(1分)】 n(n>0)个结点的树的高度: 最低是多少？ 1或者2 最高是多少？ N 有关二叉树下列

13、说法正确的是（ B ） A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 【南京理工大学 2000 一.11 （1.5分）】 5. 已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是 A A. 39 B. 52 C. 111 D. 119 【2009年全国硕士研究生入学计算机学科专业基础综合试题】 一棵124个叶结点的完全二叉树，最多有( B )个结点。 A.247 B.248 n0=124,n2=n0-1=123,n1=1 C.249; D.250; E.251 已知一棵完全二叉树中共有626

14、个结点，叶子结点的个数应为( C )。 A. 311 B. 312 C. 313 n1=1,n0=1+(2-1)*n2 D. 314 E. 其它 一个具有1025个结点的二叉树的高h为（ C ） A11 B10 C11至1025之间 D10至1024之间 一棵树高为K的完全二叉树至少有（ C ）个结点 A. 2k 1 B. 2k-1 1 C. 2k-1 D. 2k已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有 12 个叶子结点。 =1+3+8 已知二叉树的 先序序列ABDFCEHG 中序序列DBFAHECG 请构造该二叉树。 已知二叉树的 后序序列DMFBH

15、ELGCA 中序序列DBMFAHECGL 一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B D ）。 ACABDEFG BABCDEFG CDACEFBG DADCFEGB 一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( C )。 A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶子结点 D. 其中度为2的结点最多为一个 【中南大学2005一.7(2分)】 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( B )的二叉树 A空或只有一个结点 B. 高度等于其结点数 C任一结点无左孩子 D. 任一结点无右孩子

16、 【东华大学2003二.1(1分)】二叉查找树的查找效率与二叉树的( （C） 有关, 在 （C） )时其查找效率最低 (1) A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2) A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR图中有关路径的定义是（ A ）。A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列C由不同边所形成的序列 D上述定义都不是【北方交通大学