数据结构附部分答案

更新时间：2024-06-16 11:13:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

一、选择题

1、下面关于线性表的叙述错误的是（ C ）。

A.线性表采用顺序存储必须占用一片连续的存储空间 B.线性表采用链式存储不必占用一片连续的存储空间 C.线性表采用链式存储便于插入和删除操作的实现 D.线性表采用顺序存储便于插入和删除操作的实现

2、栈是一种特殊的线性表，具有（ B ）性质 A．先进先出 B.先进后出 C.后进后出 D.顺序进出

3、顺序循环队列中（数组大小为n），队头指示front指向队列的第一个元素，队尾指示

rear指向队列最后一个元素的后一个位置，则循环队列中存放了n-1个元素，即循环队列满的条件是（ B ）。

A．(rear+1)%n=front-1 B.(rear+1)%n=front C. (rear)%n=front D.rear+1=front

4、在一个单链表中，若删除p所指结点的后续结点，则执行（ A ）。 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 ）。

A. N0=N2+1 B.N0=Nl+N2 C. N0=N1+1 D.N0=2N1+l

6、设有6个结点的无向图，该图至少应有（ D ）条边才能确保是一个连通图。

A.8 B.6 C.7 D.5

7、设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该

有向图G的一种拓扑排序序列的是（ A ）。

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.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

a 第 1 页共 11 页 c e f d

9、适用于折半查找的表的存储方式及元素排列要求是（ D ）

A.链式方式存储，元素无序 B.链式存储方式，元素有序 C.顺序存储方式，元素无序 D.顺序存储方式，元素有序

10、设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行

（ C ）趟的分配和回收才能使得初始关键字序列变成有序序列。 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.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 15、二叉树的第k层的结点数最多为( D ).

kk-1

A． 2-1 B.2K+1 C.2K-1 D. 2

16、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA

前序遍历先访问根，所以C为根，在中序遍历中先访问左子树，再访问根，最后访问右子树，所以在中序序列中，C前面的为左子树，第二个访问的是左子树的根A以此类推可得这样的一棵二叉树：

第 2 页共 11 页

17、下列四种排序中（ D ）的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序

18、对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ D ）个，

A． 1 B．2 C．3 D．4 分别是：55，64，46，10.

H（K）= K%9，表示除以9的余数。由于地址重叠造成冲突，所以散列存储时，通常还要有解决冲突的办法，如线性探查法等等。

19、设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8

20、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m

21. 对一个算法的评价，不包括如下（ 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=HL;

23. 对线性表，在下列哪种情况下应当采用链表表示？( B )

A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变

24. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )

A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 25. 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；}

234

(A) O(n) (B) O(n) (C) O(n) (D) O(n)

27．设某有向图的邻接表中有n个头结点和m个表结点，则该图中有（C ）条有向边。 C (A) n (B) n-1 (C) m (D) m-1 有向图 m个表结点对应m条边，每条边都是有向的

第 3 页共 11 页

28．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（B ）。 (A) abedfc

(B) acfebd

(D) aedfcb

29. 快速排序在最坏情况下的时间复杂度为（D ）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)

30. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。

A. O(n) B. O(1) C. O(log2n) D. O(n2)

解析：如果二叉搜索树为平衡二叉树，查找一个元素的最坏时间复杂度为O(log2n)。

二、填空题

1、数据的物理结构主要包括顺序存储和链式存储两种情况。

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. 在树型结构中，树根结点没有____前趋___结点，其余每个结点的有且只有___一___个前趋驱结点；叶子结点没有___后继__结点；其余每个结点的后续结点可以__多个_。

8. 对于一个有n个结点的二叉树，当它为一棵__满/完全__二叉树时具有最小高度，即为___log2(N+1)____，当它为一棵单支树具有_最大__高度，即为__n__。 9. 在一棵二叉排序树上按___中序____遍历得到的结点序列是一个有序序列。 10. 对于一棵具有n个结点的完全二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为____2i____，右孩子结点的编号为___2i+1_____，双亲结点的编号为___i/2_____。 11. 在线性表的散列存储中，处理冲突的常用方法有___线性探测再散列____和__ 二次探测再散列___两种。

12、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有___2n_____个指针域，其中有____n-1____个指针域是存放了地址，有____n+1____个指针是空指针。 13. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为___O(log2n)_____，整个堆排序过程的时间复杂度为__O(nlog2n)______。 14. 在快速排序、堆排序、归并排序中，___归并______排序是稳定的。

第 5 页共 11 页

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; }//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。