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

1、数据结构单元测试 1一、选择题（每题2 分，共40分）数据的最小单位是（ ）。(A) 数据项(B) 数据类型 (C) 数据元素 (D) 数据变量2. 栈和队列的共同特点是( A )。(A)只允许在端点处插入和删除元素(B)都是先进后出(C)都是先进先出(D)没有共同点3. 用链接方式存储的队列，在进行插入运算时( D )。(A)仅修改头指针(C)仅修改尾指针(B)头、尾指针都要修改头、尾指针可能都要修改4. 以下数据结构中哪一个是非线性结构？( D )(A)队列 (B)栈 (C)线性表 (D)二叉树函数 substr(“DATASTRUCTURE”，5，9)的返回值为（ A ）。(B) “DA

2、TA”(D) “DATASTRUCTURE”设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。设一棵 m叉树中度数为 0 的结点数为 ，度数为 1的结点数为Nl，度数为 m的结点数为 ，则 （ ）。1 / 7(A) Nl+N2+Nm(B)1+N2+2N3+3N4+(m-1)Nm(C) N2+2N3+3N4+(m-1)Nm (D) 2Nl+3N2+(m+1)Nm设有序表中有 1000个元素，则用二分查找查找元素 X 最多需要比较（ B）次。(A) 259. 二叉树的第k层的结点数最多为( D 。(A)2k-1 (B) 2K+1 (C)2

3、-1(B) 10(C) 7(D) 1(D)2k-1K10. 树最适合用来表示( C )。(A)有序数据元素(B)无序数据元素(C)元素之间具有分支层次关系的数据 元素之间无联系的数据11.n 个权构成一棵Huffman树，其节点总数为( A 。(A)2n-112下面程序的时间复杂为（B ）for（i=1s=0；i=n；i+）for(j=1jnext；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)

4、q=p-next；p-data=q-data；free(q)；2 / 714设无向图 G中有 n 个顶点 e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。(A) ，e15. 设某强连通图中有 n (A) n(n-1) (B) n+1 (C) n (D) n(n+1)16下面关于线性表的叙述错误的是（ D (A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现17 则该哈夫曼树中总共有（B）个空指针域。(A) 2m-1(B) 2m(

5、C) 2m+1(D) 4m18设顺序循环队列Q0的头指针和尾指针分别为F 和 R，头指针 F 总是指向队头元素的前一位置，尾指针 R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为（(A) R-F(B) F-R(C) (R-F+M)M (D) M19 CABD，则后序遍历该二叉树得到序列为（ A (A) BADC(B) BCDA(C) CDAB(D) CBDA20 n (A) n(n-1)/2 (B) n(n-1) (C) n2(D) n2-13 / 7二、填空题（每题2 分，共28分）1. 在有n 个结点的二叉链表中，空链域的个数为_n+1_。2.设循环队列的元素存放在一维数组Q 中

6、，front指向队头元素的0.30前一个位置，rear 指向队尾元素。若 front=25，rear=5，则该队列中的元素个数为11。3.设源串 S=“bcdcdcb”，模式串 P=“cdcb”，按 KMP 算法进行模式匹配，当“S2S3S4”=“P1P2P3”，而 S5P4 时，S5 应与p2比较。 4.假设以一维数组作为n 阶对称矩阵A的存储空间，以行S n n1 /2序为主序存储A的下三角，则元素A 的值存储在16_中。615. 单循环链表L中指针P所指结点为尾结点的条件是_ p-next= L_。6.若一棵树中度为 1 的结点有 N1 个，度为 2 结点有 N2 个，度为 m 的 结

7、点 有 Nm 个 ， 则 该 树 的 叶 结 点 有1+N2+2N3+(m-1)Nm7.设某二叉树的前序和中序序列均为，则它的后序序列是EDCBA个。8.图的遍历方法主要是宽度优先搜索 深度优先搜索。9.一棵有n 个叶子结点的哈夫曼树共有_2n-1_个结点。10.有时在单链表的第一个结点之前附加一个头结点，其作用是_4 / 7编写简单_。112分）四、算法设计题1、设采用邻接表作为有向图的存储结构，试编写算法：计算有向图20 分）int adjvex;5 / 7ArcNode;typedef struct VNodeint data;int in;int out;ArcNode *firstarc; VNode;typedef structVNode verticesNUM;int vexnum;int arcnum;AlGraph;/获得结点的入度和出度void GetInAndOut(AlGraph &g