《数据结构》单元测试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)Nm 8．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B）次。
(A) 25 (B) 10 (C) 7 (D) 19. 二叉树的第k层的结点数最多为( D )。
(A)2k-1 (B) 2K+1 (C) 2K-1 (D)2k-110. 树最适合用来表示( C )。
(A)有序数据元素(B)无序数据元素(C)元素之间具有分支层次关系的数据 (D)元素之间无联系的数据个权构成一棵Huffman树，其节点总数为( A )。
(A)2n-1(B) 2n (C) 2n+1 (D)不确定12．下面程序的时间复杂为（B ）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）。
(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条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ 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．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C）。
(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 19．设某棵二叉树的中序遍历序列为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.设循环队列的元素存放在一维数组Q[0..30]中，front指向队头元素的前一个位置，rear指向队尾元素。
若front=25，rear=5，则该队列中的元素个数为11。
3.设源串S=“bcdcdcb”，模式串P=“cdcb”，按KMP算法进行模式匹配，当“S2S3S4”=“P1P2P3”，而S5≠P4时，S5应与p2比较。
[]2/1+n n S作为n阶对称矩阵A的存储空间，以行4.假设以一维数组()序为主序存储A的下三角，则元素A[6][1]的值存储在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、假设用一维数组A{0..m}作为循环队列Q的存储空间，front和rear分别表示该队列的队头和队尾指针，则该队列的队空条件是_____front == rear________,队满条件是___(rear+1) % (m+1) == front ______。
15.稀疏矩阵的存储方法主要有两个：一个是___三元组表法_____,另一个是十字链表示法。
三、解答题1、根据图的邻接表画邻接矩阵。
（12分）四、算法设计题1、设采用邻接表作为有向图的存储结构，试编写算法：计算有向图中每个顶点的出度和入度。
（20分）typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{int data;int in;int out;ArcNode *firstarc;} VNode;typedef struct{VNode vertices[NUM];int vexnum;int arcnum;}AlGraph;//获得结点的入度和出度void GetInAndOut(AlGraph &g) //开始时所有结点的入度出度为0 {int i;ArcNode *p;for(i=0; i<g.vexnum; i++){p = g.vertices[i].firstarc;while(p!=NULL){g.vertices[i].out++;g.vertices[p->adjvex].in++;p=p->nextarc;}《数据结构》各章课后作业答案第一章绪论课后作业答案1. 简述线性结构与非线性结构的不同点。
答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。
2．分析下面各程序段的时间复杂度（每小题5分，共20分）解：1.第一个for 循环执行n+1次，第二个for 循环执行n(m+1)次，A[i][j]=0;语句执行n*m 次，此程序段总的执行次数为n+1+n*(m+1)+n*m=2nm+2n+1次。
故时间复杂度为O(n*m)。
2.算法的时间复杂度是由嵌套最深层语句的执行次数决定的，本程序段嵌套最深层语句为：s+=B[i][j];它的执行次数为n 2，所以本程序段的时间复杂度是O(n 2)。
3. 该算法的基本操作是语句x++, 其语句频度为： 1111n n i i j --==∑∑=10()n i n i -=-∑=(1)2n n - 所以本程序段的时间复杂度是O(n 2)。
4.设语句执行m 次，则有3m≤nm ≤log 3n所以本程序段的时间复杂度为O(log 3n)。
第二章 线性表课后作业答案1. 填空题。
（1）在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。
（2）线性表中结点的集合是 有限 的，结点间的关系是 一对一的。
（3）向一个长度为n 的向量的第i 个元素(1≤i ≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。
（4）顺序表中逻辑上相邻的元素的物理位置 必定相邻 。
单链表中逻辑上相邻的元素的物理位置 不一定 相邻。
2.试写一算法，对单链表实现就地逆置。
分析：将单链表就地逆置，即不另外开辟结点空间，而将链表元素翻转顺序。
解：从链上依次取下结点，按照逆序建表的方法重新建表。
（2）s=0;for （i=0; i<n; i++) for(j=0; j<n; j++)s+=B[i][j]; sum=s; 答：O （n 2） （1） for (i=0; i<n; i++)for (j=0; j<m; j++)A[i][j]=0;(3) x=0;for(i=1; i<n; i++) for (j=1; j<=n-i; j++) x++;(4)i=1; while(i<=n)i=i*3;void Reverse ( LinkList &L ){p = L->next; // 原链表L->next = NULL; // 新表(空表)while ( p ) {// 从原链表中取下结点ss = p;p = p->next;// 插入L新表表头s->next = L->next;L->next = s;}}第三章栈和队列课后作业答案1、填空题。
