数据结构附部分答案.docx

《数据结构附部分答案.docx》由会员分享，可在线阅读，更多相关《数据结构附部分答案.docx（10页珍藏版）》请在三一办公上搜索。

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

2、C. (rear)%n=front D.rear+1=front 4、在一个单链表中，若删除p所指结点的后续结点，则执行。 A p-next=p-next-next B. p=p-next;p-next-next C.p-next=p-next D.p=p-next-next 5、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是。 A. N0=N2+1 B.N0=Nl+N2 C. N0=N1+1 D.N0=2N1+l 6、设有6个结点的无向图，该图至少应有条边才能确保是一个连通图。 A.8 B.6 C.7 D.5 7、设有向无环图G中的有向

3、边集合E=，则下列属于该有向图G的一种拓扑排序序列的是。 A.1，2，3，4 B. 2，3，4，1 C.1，4，2，3 D. 1，2，4，3 8、已知一个有向图如下所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为。 A.a d b e f c B. a d c e f b C.a d c e b f D.a d e f b c b a 第 1 页 共 11 页 c e f d 9、适用于折半查找的表的存储方式及元素排列要求是 A.链式方式存储，元素无序 B.链式存储方式，元素有序 C.顺序存储方式，元素无序 D.顺序存储方式，元素有序 10、设一组初始记录关键字序列为(345，2

4、53，674，924，627)，则用基数排序需要进行趟的分配和回收才能使得初始关键字序列变成有序序列。 A. 5 B. 4 C. 3 D. 8 11、栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 12、用链接方式存储的队列，在进行插入运算时( D ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 13、以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树 14、树最适合用来表示( C )。 A.有序数据元素 B.无序数据元素 C.

5、元素之间具有分支层次关系的数据 D.元素之间无联系的数据 15、二叉树的第k层的结点数最多为( D ). kk-1A 2-1 B.2K+1 C.2K-1 D. 2 16、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 前序遍历先访问根，所以C为根，在中序遍历中先访问左子树，再访问根，最后访问右子树，所以在中序序列中，C前面的为左子树，第二个访问的是左子树的根A以此类推可得这样的一棵二叉树： 第 2 页 共 11 页 17、下列四种排序中的空间复杂度最大。 (A) 插入排序 (B

6、) 冒泡排序 (C) 堆排序 (D) 归并排序 18、对于线性表进行散列存储时，若选用H=K %9作为散列函数，则散列地址为1的元素有个， A 1 B2 C3 D4 分别是：55，64，46，10. H= K%9，表示除以9的余数。由于地址重叠造成冲突，所以散列存储时，通常还要有解决冲突的办法，如线性探查法等等。 19、设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 20、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 21. 对一

7、个算法的评价，不包括如下方面的内容。 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=HL; 23. 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 24. 一个栈的输入序列为1 2 3，则下列序列中

8、不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 25. AOV网是一种。 A有向图 B无向图 C无向无环图 D有向无环图 26. 下面程序的时间复杂为 for t=1；for(j=1；j=i；j+) t=t*j；s=s+t； 234 (A) O(n) (B) O(n) (C) O(n) (D) O(n) 27设某有向图的邻接表中有n个头结点和m个表结点，则该图中有条有向边。 C (A) n (B) n-1 (C) m (D) m-1 有向图 m个表结点对应m条边，每条边都是有向的 第 3 页 共 11 页 28设连通图G中的边集E=(

9、a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发可以得到一种深度优先遍历的顶点序列为。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb 29. 快速排序在最坏情况下的时间复杂度为。 AO(log2n) BO(nlog2n) C0(n) D0(n2) 30. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 解析：如果二叉搜索树为平衡二叉树，查找一个元素的最坏时间复杂度为O(log2n)。 二、 填空题 1、数据的物理结构主

10、要包括 顺序存储 和 链式存储 两种情况。 2、设顺序线性表中有n个数据元素，删除第i个位置上的数据元素需要移动表 中 n-1 个元素。则第i个位置上插入一个数据元素需要移动表中 n+1-i 个元素 3、用一维数组存放完全二叉树：ABCDEFGHI，则中序遍历该二叉树的结点序列为。 4、设待排序的7记录的排序码为312，126，272，226，28，165，123，从小到大直接插入排序，一趟排序的结果是：。 第 4 页 共 11 页 5. 数据的逻辑结构有四种基本形态，分别是_、_、_和_。 6 一个算法的效率可分为_时间_效率和_空间_效率。 7. 在树型结构中，树根结点没有_前趋_结点，其

11、余每个结点的有且只有_一_个前趋驱结点；叶子结点没有_后继_结点；其余每个结点的后续结点可以_多个_。 8. 对于一个有n个结点的二叉树，当它为一棵_满/完全_二叉树时具有最小高度，即为_log2(N+1)_，当它为一棵单支树具有_最大_高度，即为_n_。 9. 在一棵二叉排序树上按_中序_遍历得到的结点序列是一个有序序列。 10. 对于一棵具有n个结点的完全二叉树，若一个结点的编号为i(1in)，则它的左孩子结点的编号为_2i_，右孩子结点的编号为_2i+1_，双亲结点的编号为_i/2_。 11. 在线性表的散列存储中，处理冲突的常用方法有_线性探测再散列_和_ 二次探测再散列_两种。 12

12、、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有_2n_个指针域，其中有_n-1_个指针域是存放了地址，有_n+1_个指针是空指针。 13. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_O(log2n)_，整个堆排序过程的时间复杂度为_O(nlog2n)_。 14. 在快速排序、堆排序、归并排序中，_归并_排序是稳定的。 第 5 页 共 11 页 15. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有_e=2m_关系。 一个点的度数就等于该点连接的边数,一条边连接2个点,这两个点的度数都要加

13、1,也就是说,有一条边总的度数就要加2,所以总度数是边数的2倍 16 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是 (1，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 第一个进去就出来 A

14、DCB,ACDB,ACBD 一共14种 例题 第 6 页 共 11 页 第 7 页 共 11 页 图3.2 有向图 用5个带权值3,2,4,5,1构造的哈夫曼树的带权路径长度是 8、 设有一个输入数据的序列是 46, 25, 78, 62, 12, 80 , 试画出从空树起，逐个输入各个数据而生成的二叉排序树。 第 9 页 共 11 页 四、程序填空 1、如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A ,int n,KeyType K) int low=0; int high=n-1; while (low=high) int mid=_； if (K

15、=Amid.key) return mid; /查找成功，返回元素的下标 else if (Kdata=x) i+; p=p-next; /while, 出循环时i中的值即为x结点个数 return i; /CountX 5、 设计判断两个二叉树是否相同的算法。 typedef struct node datatype data; struct node *lchild,*rchild; bitree; int judgebitree(bitree *bt1,bitree *bt2) if (bt1=0 & bt2=0) return(1); else if (bt1=0 | bt2=0 |bt1-data!=bt2-data) return(0); else return(judgebitree(bt1-lchild,bt2-lchild)*judgebitree(bt1-rchild,bt2-rchild); 6、 设计两个自小到大有序单链表ha，hb的合并排序算法，合并后的单链表头指针为hc。 7、实现对n个整数自小到大的直接插入排序 。 第 11 页 共 11 页