资源预览内容
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
亲,该文档总共6页全部预览完了,如果喜欢就下载吧!
资源描述
数据结构单元测试 1一、选择题(每题 2 分,共 40 分)1数据的最小单位是( A)。(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量2. 栈和队列的共同特点是( A )。(A)只允许在端点处插入和删除元素(B)都是先进后出 (C)都是先进先出(D)没有共同点3. 用链接方式存储的队列,在进行插入运算时( D )。(A)仅修改头指针 (B)头、尾指针都要修改(C)仅修改尾指针 (D)头、尾指针可能都要修改4. 以下数据结构中哪一个是非线性结构?( D )(A)队列 (B)栈 (C)线性表 (D)二叉树5函数 substr(“DATASTRUCTURE”,5, 9)的返回值为( A )。(A) “STRUCTURE” (B) “DATA”(C) “ASTRUCTUR” (D) “DATASTRUCTURE”6设一个有序的单链表中有 n 个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为( D)。(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)7设一棵 m 叉树中度数为 0 的结点数为 N0,度数为 1 的结点数为Nl,度数为 m 的结点数为 Nm,则 N0=( B )。(A) Nl+N2+Nm (B) 1+N2+2N3+3N4+(m-1)Nm (C) N2+2N3+3N4+(m-1)Nm (D) 2Nl+3N2+(m+1)Nm8设有序表中有 1000 个元素,则用二分查找查找元素 X 最多需要比较( B)次。(A) 25 (B) 10 (C) 7 (D) 19. 二叉树的第 k 层的结点数最多为( D )。(A)2k-1 (B) 2K+1 (C) 2K-1 (D)2 k-110. 树最适合用来表示( C )。(A)有序数据元素 (B)无序数据元素(C)元素之间具有分支层次关系的数据 (D)元素之间无联系的数据11.n 个权构成一棵 Huffman 树,其节点总数为( A )。(A)2n-1 (B) 2n (C) 2n+1 (D)不确定12下面程序的时间复杂为(B )for(i=1,s=0; inext;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 条边,则其对应的邻接表中的表头结点和表结点的个数分别为( D)。(A) n,e (B) e,n (C) 2n,e (D) n ,2e15. 设某强连通图中有 n 个顶点,则该强连通图中至少有( C)条边。(A) n(n-1) (B) n+1 (C) n (D) n(n+1)16下面关于线性表的叙述错误的是( D ) 。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现17设哈夫曼树中的叶子结点总数为 m,若用二叉链表作为存储结构,则该哈夫曼树中总共有( B)个空指针域。(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m18设顺序循环队列 Q0:M-1的头指针和尾指针分别为 F 和 R,头指针 F 总是指向队头元素的前一位置,尾指针 R 总是指向队尾元素的当前位置,则该循环队列中的元素个数为( C) 。(A) R-F (B) F-R (C) (R-F+M)M (D) (F-R+M)M19设某棵二叉树的中序遍历序列为 ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为( A ) 。(A) BADC (B) BCDA (C) CDAB (D) CBDA20设某完全无向图中有 n 个顶点,则该完全无向图中有( A)条边。(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1二、填空题(每题 2 分,共 28 分)1. 在有 n 个结点的二叉链表中,空链域的个数为_n+1_。2.设循环队列的元素存放在一维数组 Q0.30中,front 指向队头元素的前一个位置,rear 指向队尾元素。若 front=25,rear=5,则该队列中的元素个数为 11 。3.设源串 S=“bcdcdcb”,模式串 P=“cdcb”,按 KMP 算法进行模式匹配,当“S2S3S4”=“P1P2P3”,而 S5P4 时,S5 应与 p2 比较。4.假设以一维数组 作为 n 阶对称矩阵 A 的存储空间,以行2/1nS序为主序存储 A 的下三角,则元素 A61的值存储在 S_16_中。5. 单循环链表 L 中指针 P 所指结点为尾结点的条件是 _ p-next = L _。6.若一棵树中度为 1 的结点有 N1 个,度为 2 结点有 N2 个,度为 m 的结点有 Nm 个,则该树的叶结点有 1+N2+2N3+(m-1)Nm 个。7.设某二叉树的前序和中序序列均为 ABCDE,则它的后序序列是 EDCBA 。8.图的遍历方法主要是 宽度优先搜索 深度优先搜索 。9.一棵有 n 个叶子结点的哈夫曼树共有_2n-1_个结点。10.有时在单链表的第一个结点之前附加一个头结点,其作用是_避免在插入和删除操作中将第一个结点看作是特殊结点,使程序编写简单_。11.求解图的最小生成树的算法有两个,分别是 Prim 算法和Kruskal 算法 。12.对于任意一棵二叉树,如果其叶结点数为 N0,度为 1 的结点数为 N1,度为 2 的结点数为 N2,则 N0=_ N2 + 1_。13.一棵有 N 个叶子结点的 Huffman 树,共有_2n-1_个结点。14、 假设用一维数组 A0.m作为循环队列 Q 的存储空间,front和 rear 分别表示该队列的队头和队尾指针,则该队列的队空条件是_front = rear_,队满条件是_(rear+1) % (m+1) = front _。15.稀疏矩阵的存储方法主要有两个:一个是_三元组表法_,另一个是十字链表示法。三、解答题1、根据图的邻接表画邻接矩阵。 (12 分)四、算法设计题1、设采用邻接表作为有向图的存储结构,试编写算法:计算有向图中每个顶点的出度和入度。 (20 分)typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNode int data;int in;int out;ArcNode *firstarc; VNode;typedef struct VNode verticesNUM;int vexnum;int arcnum;AlGraph;/获得结点的入度和出度 void GetInAndOut(AlGraph &g) /开始时所有结点的入度出度为 0int i;ArcNode *p;for(i=0; iadjvex.in+;p=p-nextarc;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号