《数据结构单元测试1(含答案).docVIP

《数据结构》单元测试1 一、选择题（每2分，共0分） 1．数据的最小单位是（?）。(A) 数据项(B) 数据类型??? (C) 数据元素??? (D) 数据变量 2.?栈和队列的共同特点是()。(A)只允许在端点处插入和删除元素(B)都是先进后出(C)都是先进先出(D)没有共同点 3.?用链接方式存储的队列，在进行插入运算时(?? )。(A)仅修改头指针(B)头、尾指针都要修改(C)仅修改尾指针(D)头、尾指针可能都要修改 4.?以下数据结构中哪一个是非线性结构？(?? )(A)队列(B)栈(C)线性表?　　?(D)二叉树 5．函数substr(“DATASTRUCTURE”，5，9)的返回值为（?）。(A) “STRUCTURE”(B) “DATA”(C) “ASTRUCTUR”(D) “DATASTRUCTURE” 6．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（?）。(A) O(log2n)(B) O(1)(C) O(n2)(D) O(n) 7．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（?）。(A) Nl+N2+……+Nm(B) +N2+2N3+3N4+……+(m-1)Nm(C) N2+2N3+3N4+……+(m-1)Nm(D) 2Nl+3N2+……+(m+1)Nm 8．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（?）次。(A) 25(B) 10(C) 7(D) 1 9.?二叉树的第k层的结点数最多为(?? )。(A)2k-1(B) 2K+1(C) 2K-1?　　 (D)2k-1 10.?树最适合用来表示()。(A)有序数据元素(B)无序数据元素(C)元素之间具有分支层次关系的数据???(D)元素之间无联系的数据 (?? A )。 (A)2n-1 ? (B) 2n (C) 2n+1 (D)不确定 12．下面程序的时间复杂为（?） for（i=1，s=0； i=n； i++） {t=1；for(j=1；j=i；j++) t=t*j；s=s+t；}(A) O(n)(B) O(n2)(C) O(n3)(D) O(n4) 13．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（?）。(A) q=p-next；p-data=q-data；p-next=q-next；free(q)； (B) q=p-next；q-data=p-data；p-next=q-next；free(q)；(C) q=p-next；p-next=q-next；free(q)；(D) q=p-next；p-data=q-data；free(q)； 14．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（?）。(A) n，e(B) e，n(C) 2n，e(D) n，2e 15. 设某强连通图中有n个顶点，则该强连通图中至少有（?）条边。(A) n(n-1)(B) n+1(C) n(D) n(n+1) 16．下面关于线性表的叙述错误的是（?? ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 17．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（?）个空指针域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m 18．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（?）。(A) R-F(B) F-R(C) (R-F+M)％M?(D) (F-R+M)％M 19．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（?? ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA 20．设某完全无向图中有n个顶点，则该完全无向图中有（?）条边。(A) n(n-1)/2(B) n(n-1)(C) n2(D) n2-1 二、填空题（每2分，共2分） ? 在有n个结点的二叉链表中，空链域的个数为____n+1_____。 单循环链表L中指针P所指结点为尾结点的条件是____ ? p-next = L ________。?9.一棵有n个叶子结点的哈夫曼树共有___2n-1_______个结点。 有时在单链表的第一个结点之前附加一个头结点，其作用是____避免在插入和删除操作中将第一个结点看作是特殊