数据结构附部分答案

1、下载可编辑一、 选择题1、下面关于线性表的叙述错误的是（C）。A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储便于插入和删除操作的实现2、栈是一种特殊的线性表，具有（B）性质A先进先出B.先进后出C.后进后出D. 顺序进出3、顺序循环队列中（数组大小为n），队头指示front指向队列的第一个元素，队尾指示rear指向队列最后一个元素的后一个位置，则循环队列中存放了n-1 个元素，即循环队列满的条件是（B）。A(rear+1)%n=front-1B.(rear+1)%n=f

2、rontC. (rear)%n=frontD.rear+1=front4、在一个单链表中，若删除p 所指结点的后续结点，则执行（A）。A p->next=p->next->next B. p=p->next;p->next->next C.p->next=p->next D.p=p->next->next5、设某二叉树中度数为0 的结点数为N0，度数为 1 的结点数为Nl ，度数为 2 的结点数为N2，则下列等式成立的是（A）。A. N0=N2+1B.N0=Nl+N2C. N0=N1+1D.N0=2N1+l6、设有 6 个结点的无向图

3、，该图至少应有（D）条边才能确保是一个连通图。A.8B.6C.7D.57、设有向无环图G中的有向边集合E=<1， 2>，<2，3>，<3，4>，<1，4> ，则下列属于该有向图 G的一种拓扑排序序列的是（A）。A.1 ，2，3，4B. 2，3，4，1C.1，4，2，3D. 1，2，4，38、已知一个有向图如下所示，则从顶点a 出发进行深度优先遍历，不可能得到的DFS序列为（A）。A.a d b e f cB. a d c e f bC.a d c e b fD.a d e f b cb.专业 .整理 .acefd下载可编辑9、适用于折半查找的表的

4、存储方式及元素排列要求是（D）A. 链式方式存储，元素无序B. 链式存储方式，元素有序C. 顺序存储方式，元素无序D. 顺序存储方式，元素有序10、设一组初始记录关键字序列为(345 ， 253， 674， 924， 627) ，则用基数排序需要进行（C）趟的分配和回收才能使得初始关键字序列变成有序序列。A.5B.4C.3D.811、栈和队列的共同特点是( A)。A. 只允许在端点处插入和删除元素B. 都是先进后出C. 都是先进先出D. 没有共同点12、用链接方式存储的队列，在进行插入运算时(D ).A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改13、以下数据

5、结构中哪一个是非线性结构？(D )A.队列B.栈C.线性表D.二叉树14、树最适合用来表示( C)。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据15、二叉树的第k 层的结点数最多为 (D ).A 2k-1B.2K+1C.2K-1D. 2 k-116、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA前序遍历先访问根，所以C 为根，在中序遍历中先访问左子树，再访问根，最后访问右子树，所以在中序序列中，C 前面的为左子树，第二个访问的是左子

6、树的根A 以此类推可得这样的一棵二叉树：.专业 .整理 .下载可编辑17、下列四种排序中（D ）的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序18、对于线性表（ 7， 34， 55， 25， 64，46，20， 10）进行散列存储时，若选用 H（ K）=K %9 作为散列函数，则散列地址为 1 的元素有（ D ）个，A1B2C3D4分别是： 55， 64， 46， 10.H（ K）= K%9，表示除以9 的余数。由于地址重叠造成冲突，所以散列存储 时，通常还要有解决冲突的办法，如线性探查法等等。19、设有 6 个结点的无向图，该图至少应有(A)条边才能确保是一个连通图

7、。A.5B.6C.7D.820、设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）个空指针域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m21.对一个算法的评价，不包括如下（B）方面的内容。A健壮性和可读性B 并行性C正确性D时空复杂度22. 在带有头结点的单链表 HL中，要向表头插入一个由指针 p 指向的结点，则执行(A ) 。A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=H

8、L;23. 对线性表，在下列哪种情况下应当采用链表表示？ ( B )A. 经常需要随机地存取元素B.经常需要进行插入和删除操作C. 表中元素需要占据一片连续的存储空间D.表中元素的个数不变24. 一个栈的输入序列为 1 2 3 ，则下列序列中不可能是栈的 输出序列的是( C)A.231B.321C.312D.12325. AOV网是一种（ D ）。A有向图B无向图C无向无环图D有向无环图26. 下面程序的时间复杂为（ 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)

9、 O(n 2)(C) O(n 3)(D) O(n 4)27设某有向图的邻接表中有n 个头结点和m个表结点，则该图中有（C）条有向边。C(A) n(B) n-1(C) m(D) m-1有向图 m 个表结点对应m条边，每条边都是有向的.专业 .整理 .下载可编辑28设连通图G中的边集E=(a ， b) ，(a ， e) ， (a ， c) ，(b ， e) ， (e ，d) ，(d ， f) ， (f ，c) ，则从顶点a 出发可以得到一种深度优先遍历的顶点序列为（B）。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb29. 快速排序在最坏情况下的时间复杂度为（ D

10、 ）。AO(log 2 n)BO(nlog 2n)C0(n)D 0(n 2 )30. 从二叉搜索树中查找一个元素时，其时间复杂度大致为 ( C ) 。A. O(n)B. O(1)C. O(log2n)D. O(n2 )解析：如果二叉搜索树为平衡二叉树，查找一个元素的最坏时间复杂度为O(log 2 n) 。二、 填空题1、数据的物理结构主要包括顺序存储和链式存储两种情况。2、设顺序线性表中有n 个数据元素，删除第i 个位置上的数据元素需要移动表中n-1个元素。则第i 个位置上插入一个数据元素需要移动表中n+1-i个元素3、用一维数组存放完全二叉树：ABCDEFGHI，则中序遍历该二叉树的结点序列

11、为（）。4、设待排序的7 记录的排序码为312 ， 126，272，226，28，165， 123 ，从小到大直接插入排序，一趟排序的结果是：（）。.专业 .整理 .下载可编辑5.数据的逻辑结构有四种基本形态，分别是_、_、 _和 _。6 一个算法的效率可分为 _时间 _效率和 _空间 _效率。7. 在树型结构中，树根结点没有 _前趋 _结点，其余每个结点的有且只有_一_个前趋驱结点；叶子结点没有 _后继 _结点；其余每个结点的后续结点可以 _多个 _。8. 对于一个有 n 个结点的二叉树，当它为一棵 _满/ 完全 _二叉树时具有最小高度，即为 _log2(N+1) _，当它为一棵单支树具有

12、_最大 _高度，即为 _n_。9. 在一棵二叉排序树上按 _中序 _遍历得到的结点序列是一个有序序列。10. 对于一棵具有 n 个结点的完全二叉树，若一个结点的编号为 i(1 i n) ，则它的左孩子结点的编号为 _2i _，右孩子结点的编号为 _2i+1 _，双亲结点的编号为 _i/2 _。11. 在线性表的散列存储中，处理冲突的常用方法有 _线性探测再散列 _和_二次探测再散列 _两种。12、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有 _2n_个指针域，其中有 _n-1 _个指针域是存放了地址，有_n+1_个指针

13、是空指针。13. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_O(log2n) _，整个堆排序过程的时间复杂度为_O(nlog2n)_ _。14.在快速排序、堆排序、归并排序中，_归并 _排序是稳定的。.专业 .整理 .下载可编辑15.设无向图 G中有 n 个顶点 e 条边，所有顶点的度数之和为m，则 e 和 m有_e=2m_关系。一个点的度数就等于该点连接的边数 , 一条边连接 2 个点 , 这两个点的度数都要加 1, 也就是说 , 有一条边总的度数就要加 2, 所以总度数是边数的 2 倍16 已知一有向图的邻接表存储结构如下：从顶点1 出发， DFS遍历的输出序列是(1 ，

14、3， 4，5， 2)，BFS遍历的输出序列是(1 ， 3， 2， 4， 5)三、应用题1、假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，请写出所有可能的出栈序列。进一个出一个，ABCD先进两个， AB进，进 C出 C, 进 D 出 D，出 B 出 A，CDBA进 A进 B，进 C进 D，出 D出 C出 B出 A，DCBA下面的不解释了，不明白你再问BCDA,BDCA,BCAD,BADC,BACD,前三个一起进CBAD,CBDA,CDBA第一个进去就出来ADCB,ACDB,ACBD一共 14种例题.专业 .整理 .下载可编辑.专业 .整理 .下载可编辑图3.2 有向图用 5 个

15、带权值 3,2,4,5,1构造的哈夫曼树的带权路径长度是（）.专业 .整理 .下载可编辑8、 设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 ,试画出从空树起，逐个输入各个数据而生成的二叉排序树。.专业 .整理 .下载可编辑四、程序填空1、如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A ,int n,KeyType K) int low=0;int high=n-1;while (low<=high)int mid=_ ；if (K=Amid.key) return mid;/查找成功，返回元素的下标else if (K&

16、lt;mid.key)_;/在左子表上继续查找else _;/在右子表上继续查找return -1;/查找失败，返回 -1答案 ：(low+high)/2high=mid-1low=mid+12循环队列的插入。循环队列数据结构定义如下：四、算法设计题1、设计算法，在顺序表test中插入元素a 到第 i 个位置。要求考虑表满情况。.专业 .整理 .下载可编辑2、设计算法，实现二叉树的递归先序遍历。3、设计算法，实现n 个整数的快速排序。4、统计出单链表HL中结点的值等于给定值X 的结点数。int CountX(LNode* HL,ElemType x) int i=0; LNode* p=HL;/i为计数器while(p!=NULL) if (P->data=x) i+;p=p->next;/while, 出循环时 i 中的值即为 x 结点个数 return i;/CountX5、设计判断两个二叉树是否相同的算法。typedef struct node datatype data; struct node *lchild,*rchild; bitree; int judgebitree(bitree *bt1,bitree *bt2) if (bt1=0 && b