数据结构随堂测验(带答案).doc

第1次测验1. 算法的时间复杂度取决于（ C ）A问题的规模 B. 待处理数据的初态 C. A和B2. 从逻辑上可以把数据结构分为（ C ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构3. 以下属于逻辑结构的是（ C ）。A顺序表 B. 哈希表 C. 有序表 D. 单链表4. 下述哪一条是顺序存储结构的优点？（ A ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示5. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表6. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表C双链表 D仅有尾指针的单循环链表7. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。A单链表 B双链表C单循环链表 D带头结点的双循环链表8. 链表不具有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比9. 对于顺序表，访问第i位置结点和增加、删除结点的时间复杂度为（ C ）。A. O(n) O(n) B. O(n) O(1)C. O(1) O(n) D. O(1) O(1)10. 线性表以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）AO(i) BO(1) CO(n) DO(i-1)11. 下面程序段的时间复杂度是O(n) 。int i=1,k=100;while(in)k=k+1;i+=2;12. 在单链表L中，指针p所指结点有后继结点的条件是：_。13. 长度为n的顺序表，在其第i个元素（1in+1）之前插入一个元素时，需向后移动 个元素，删除第i个元素（1in）时，需向前移动_ 个元素。14. 请写出顺序表的类型定义。15. 请写出单链表的类型定义。 第2次测验一、选择题1. 对于栈操作数据的原则是（ B ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序2. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ B ）。A. 不确定 B. n-i+1 C. i D. n-i3. 若一个栈的输入序列为1,2,3,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。A. i-j-1 B. i-j C. j-i+1 D. 不确定的4. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 65. 栈在（ D ）中应用。A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，6. 一个递归算法必须包括（ B ）。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分7. 表达式a*(b+c)-d的后缀表达式是( B )。Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd8. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。A线性表的顺序存储结构 B. 队列C. 线性表的链式存储结构 D. 栈9. 用链接方式存储的队列，在进行删除运算时（ D ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改10. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。A(rear-front+m)%m Brear-front+1C(front-rear+m)%m D(rear-front)%m11. 循环队列存储在数组A0.m中，则入队时的操作为（ D ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 12. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B)A. 1和 5 B. 2和4 C. 4和2 D. 5和113. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ B ）。A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front14. 栈和队列都是（ C ）A顺序存储的线性结构 B. 链式存储的非线性结构C. 限制存取点的线性结构 D. 限制存取点的非线性结构15. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。A 6 B. 4 C. 3 D. 216. 下面关于串的的叙述中，哪一个是不正确的？（ B ）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储17. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）A求子串 B联接 C匹配 D求串长18. 串的长度是指（ B ）A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数19. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。A. 13 B. 33 C. 18 D. 4020. 设有数组Ai,j，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( B )。A. BA+141 B. BA+180 C. BA+222 D. BA+22521. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ B ）。A. 60 B. 66 C. 18000 D. 3322. 已知广义表L=（x,y,z），a，（u，t，w），从L表中取出原子项t的运算是（ D ）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）23. 广义表运算式Tail(a,b),(c,d)的操作结果是（ C ）。A. (c,d) B. c,d C. (c,d) D. d24. 设广义表L=（a,b,c），则L的长度和深度分别为（ C ）。A. 1和1 B. 1和3 C. 1和2 D. 2和325. 下面说法不正确的是( A )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 第3次测验1. 在下述结论中，正确的是（ D ）。 只有一个结点的二叉树的度为0; 二叉树的度为2； 二叉树的左右子树可任意交换; 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D2. 有关二叉树下列说法正确的是（ B ）。A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为23. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ D ）。A5 B6 C7 D84. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ）。A250 B500 C254 D505 E以上答案都不对5. 一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点。A2h B2h-1 C2h+1 Dh+16. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ A ）。Am-n Bm-n-1 Cn+1 D条件不足，无法确定7. 利用二叉链表存储树，则根结点的右指针是（ C ）。A指向最左孩子 B指向最右孩子 C空 D非空8. 在下列存储形式中，哪一个不是树的存储形式？（ D ）。A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法9. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。ACBEFDA B FEDCBA C CBEDFA D不定10. 引入二叉线索树的目的是（ A ）。A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一11. 线索二叉树是一种（ C ）结构。A逻辑 B 逻辑和存储 C物理 D线性12. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D )。A不确定 B2n C2n+1 D2n-113. 设无向图的顶点个数为n，则该图最多有（ B ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En214. 一个n个顶点的连通无向图，其边的个数至少为（ A ）。An-1 Bn Cn+1 Dnlogn15. 一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。A0 B1 Cn-1 Dn16. 在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C）倍。A1/2 B2 C1 D417. 下列哪一种图的邻接矩阵是对称矩阵？（ B ）A有向图 B无向图 CAOV网 DAOE网18. 一个有向无环图的拓扑排序序列（ B ）是唯一的。A 一定 B不一定 第4次测验1. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ A ）。A（N+1）/2 B. N/2 C. N D. （1+N）*N /22. 下面关于二分查找的叙述正确的是（ D ）。A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储3. 当采用分块查找时，数据的组织方式为（ B ）。A数据分成若干块，每块内数据有序B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同4. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低。（ C ）(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单支树 D. 结点太复杂5. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) 。A（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D. (100，80，60，90，120，130，110)6. 设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ D ）个记录。A1 B. 2 C. 3 D. 47. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）)。( AC ) （1） A17 B. 13 C. 16 D. 任意（2） A0至17 B. 1至17 C. 0至16 D. 1至16 8. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D )。 Ak-1次 B. k次 C. k+1次 D. k（k+1）/2次9. 散列表的地址区间为0-16,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。（1）元素59存放在散列表中的地址是（ D ）。A 8 B. 9 C. 10 D. 11（2）存放元素59需要搜索的次数是（ C ）。A 2 B. 3 C. 4 D. 510. 某内排序方法的稳定性是指( D )。 A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录C平均时间为0（n log n）的排序方法 D以上都不对11. 下列内部排序算法中： A快速排序 B. 直接插入排序 C. 二路归并排序 D. 直接选择排序 E. 起泡排序 F. 堆排序（1）其比较次数与序列初态无关的算法是（ CD ） （2）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，kn）的情况下，排序效率最高的算法是（ B ）（3）排序的平均时间复杂度为O(nlogn)的算法是（ ACF ）,为O(nn)的算法是（ BDE ）12. 数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( )两趟排序后的结果。( C )A选择排序 B.冒泡排序 C.插入排序 D.堆排序13. 数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。( A )A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序14. 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过