[数据结构与算法]数据结构选择练习题（有解析）

前言

? ? ? ? 已经到期末了，昨天进行了一次马原考试，那时候挺紧张的，那时候虽然写完了试卷，但是有4道题是乱写的，因为我刚好没有背，希望不会挂科吧。

? ? ? ? 然后今天呢，就开始复习数据结构了，然后发现数据结构这学期进行的8次实验的选择题竟然没有答案，于是我就拿这些题目来复习，一边复习一边写一些自己解题的思路，忙了一天，终于弄完了。大家有需要拿来复习的最好复制到word里面看好吧，也可以打印出来，因为是直接从word上面复制过来的，所以字可能有些小。

选择题与答案与解析

实验1? 线性表

1、关于顺序表和链表，以下说法中正确的是（ A ）。

A. 顺序表适合指定位置的存取元素操作。

B. 链表中相邻结点的物理存储空间也是相邻的。（链表中的存储空间是随机分配的，所以空间不一定是相邻的，可以说，大部分都是不相邻的）

C. 若每个数据元素占4个字节，那么含有10个数据元素的链表总共需要40字节的存储空间。（不一定就是40个如果链表是有头节点的，那么链表的结点会有11个，所以总共需要的空间可能会超过40个字节）

D. 经过排序的顺序表和链表都可以使用二分查找算法。（链表不是顺序存储的，无法使用二分查找算法，二分查找算法需要利用的数组的下标进行操作）

2、若想在单链表中删除某结点p的直接后继（p既不是第一个结点，也不是最后一个结点），则应执行（ A? ）操作。

A. p->next = p->next->next;

B. p = p->next; p->next = p->next->next;

C. p->next = p->next;

D. p = p->next->next;

3、已知L是带头结点的单链表，则删除首元结点的语句是（? B? ）。

A. L = L->next;

B. L->next = L->next->next;

C. L = L->next->next;

D. L->next = L;

4、用链表表示线性表的优点是（ C? ）。

A. 便于随机存储（不确定，好像也是链表的特点，不确定是不是优点）

B. 花费的存储空间较顺序存储少（花费的空间不一定就少，只是链表的每个结点都会装有数据，没有空间的浪费，而当数据较少时，使用顺序表会浪费角度哦的空间）

C. 便于插入和删除（链表的常规优点）

D. 数据元素的物理顺序与逻辑顺序相同（这是顺序表的优点）

5、在单链表中，增加一个头结点的目的是为了（? C? ）。

A. 使单链表至少有一个结点

B. 标识表结点中首结点的位置

C. 方便一些操作的实现（只是为了方便在一些特殊情况下，少些几个ifelse代码）

D. 说明单链表是线性表的链式存储

6、已知单链表A的长度为m，单链表B的长度为n，若将B链接在A的末尾，在没有链尾指针的情况下，算法的时间复杂度为（ C ）

A. O(1)

B. O(m)

C. O(n)（首先要将链表A遍历一遍，找到链尾指针，然后遍历链表B，将每个结点接到链表A链尾指针的后面，因为两个循环的遍历是并列的，所以时间复杂度应该是O（MAX（n，m）），但是不确定哪个大就选O（n）了）

D. O(m+n)

7、从一个具有n个结点的有序链表中查找其值等于x的结点时，在查找成功的情况下，需要平均比较（ D ）个结点。

A. n

B. n/2

C. (n-1)/2

D. (n+1)/2

8、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，那么插入一个元素时平均要移动表中的（ D ）个元素。

A. n

B. n/2

C. (n-1)/2

D. (n+1)/2（直接进行计算，从第一个位置0开始插入，到位置n-1，依次需要移动n, n-1, n-2 … 1, 0 个，求和得：n*(n+1)/2,因为要求平均值，所以再除于n，得（n+1）/2）

9、在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（ B? ）。

A. O(n)

B. O(1)（数组的存储特性）

C. O(n2)

D. O(log n)

10、在单链表上实施插入和删除操作（ B? ）。

A. 不需移动结点，不需改变结点指针。

B. 不需移动结点，只需改变结点指针。（链表的操作特性）

C. 只需移动结点，不需改变结点指针。

D. 既需移动结点，又需改变结点指针。

11、不带表头结点的单链表head为空的判定条件是（ A? ）。

A. head == NULL;（不带头节点，说明头节点也是存数据的，所以头节点为空就表示链表为空）

B. head->next == NULL;

C. head->next == first;

D. head!=NULL;

12、带表头结点的单链表head为空的判定条件是（ B? ）。

A. head == NULL;

B. head->next == NULL;（和上一题一样的道理）

C. head->next == first;

D. head!=NULL;

13、已知单链表中结点p不是链尾结点，若在p之后插入结点s，则应执行（ D ）。

A. s->next = p; p->next = s;

B. p->next = s; s->next = p;

C. s->next = p->next; p = s;

D. s->next = p->next; p->next = s;（链表的插入和删除规则）

14、一个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）。

A. 105

B. 108

C. 110（顺着数就好）

D. 120

15、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（? C ）操作。

A. s->next = p->next; p->next = s;

B. p->next = s->next; s->next = p;

C. q->next = s; s->next = p;（链表的插入操作）

D. p->next = s; s->next = q;

实验2? 栈和队列

1、对于一个初始为空的栈s执行操作push(s, 5)，push(s, 2)，push(s, 4)，pop(s)后，栈顶元素的值是（ B ）。

A. 5

B. 2（栈的后入先出规律，插入三次：栈中元素为5、2、4，弹出一次，弹出4，所以现在栈顶元素为2）

C. 4

D. 0

2、用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1,2,3,4，为了得到出栈顺序1,3,4,2，则相应的S和X的操作序列为（ D? ）。

A. SXSXSSXX

B. SSSXXSXX

C. SXSSXXSX

D. SXSSXSXX（按着栈后入先出的规律，进行模拟操作就好）

3、已知一个栈的进栈序列为1，2，3，…，n，其输出序列的第一个元素是i，则第j个出栈元素是（? D? ）。

A. j-1

B. n-i

C. j-i+1

D. 不确定（无法确定i是哪个元素，而且也无法确定中间的出栈也入栈如何）

4、已知一个栈的进栈序列为1，2，3，…，n，其输出序列是p1，p2，p3，…，pn。若p1=3，则p2的值（ D ）。

A. 一定是1

B. 一定是2

C. 可能是1

D. 可能是2（第一个出栈的元素是3，说明3出栈是栈中的元素为1、2，所以下一个出栈的可能是2，也可能是3之后的数，但是一定不可能是1，因为2要先出栈，才能到1出栈）

5、已知一个栈的进栈序列为p1，p2，p3，…，pn，其输出序列是1，2，3，…，n。若p3=1，则p1的值（ C? ）。

A. 一定是2

B. 可能是2

C. 不可能是2（因为出栈的序列里面，2在1后面，而p3=1，说明p1不可能是2，因为p1一定会在p2之后出栈，p2才有可能是2）

D. 一定是3

6、以下有关顺序栈的操作中，正确的是（ A? ）

A. N个元素进入一个栈后，它们的出栈顺序一定与进栈顺序相反（一次性进栈完毕后再出栈）（一次性进栈完之后再出栈确实顺序相反）

B. 若一个栈的存储空间为S[n]，则对栈的进栈和出栈操作最多只能执行n次（栈的空间和栈的操作次数并没有关联，栈满了可以出栈，栈空了可以入栈，理论上是可以操作无数次的（在运行时间范围内都可以吧））

C. 栈是一种对进栈和出栈操作的次序做了限制的线性表（栈并没有对进栈和出栈的次序进行限制，只是规定了必须要先入先出而已）

D. 空栈没有栈顶指针（空栈也是有栈顶指针的，只是指向的位置可能不是数组的空间位置，如为-1或n等）

7、设链式栈中结点的结构为(data, next)，top是指向栈顶的指针。若想在链式栈中入栈一个由s所指的结点，则应执行的操作是（? B ）。

A. top->next = s;

B. s->next = top->next; top->next = s;（链式栈的有两种：头部进行入栈和出栈、尾部进行入栈和出栈。最好的链式栈应该是在头部进行入栈和出栈的。题目没说明也没影响，只是对链表的插入操作，与栈的联系较少）

C. s->next = top; top = s;

D. s->next = top; top = top -> next;

8、设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，没有其他数据成员，则该队列为满的判断条件是（ C ）。

A. Q.front == Q.rear

B. front + Q.rear >= maxSize

C. Q.front == (Q.rear+1)%maxSize(判断队列是否满队就是看队尾指针rear的下一个位置是不是队首指针front)

D. Q.rear == (Q.front+1)%maxSize

9、一个队列的进队顺序是1,2,3,4，则该队列可能的输出序列是（ A? ）。

A. 1,2,3,4（考察队列的基本性质：先进先出，所以输出顺序和输入顺序一样的）

B. 1,3,2,4

C. 1,4,2,3

D. 4,3,2,1

10、对于链式队列，在执行入队操作时（? B ）。

A. 仅修改头指针

B. 仅修改尾指针（对于链式队列，一般是尾插法，输出是将前面的结点进行输出。理论上，用头插法在前面进行入队，在尾结点那进行出队也是可以的。因为书上代码是用尾插法入队的，所以一般默认题目是尾插法入队的。尾插法入队只修改尾指针就好）

C. 头、尾指针都要修改

D. 头、尾指针可能都要修改

11、最适合用作链式队列的链表是（ B? ）。

A. 带有队头指针和队尾指针的循环单链表（用循环单链表进行操作会比较麻烦，但是也是可以的，但是因为这题要求是最合适的，用这个选项会多一步将尾结点接到头节点的操作，所以不是最合适的）

B. 带有队头指针和队尾指针的非循环单链表（用来做队列的链表，最好直接就能知道队头指针和队尾指针，因为队列的操作就只有入队和出队，这两个操作只涉及到队头和队尾，所以可以使队列的入队和出队操作时间复杂度都为O（1））

C. 只带队头指针的循环单链表

D. 只带队头指针的非循环单链表

12、最不适合用作链式队列的链表是（ A? ）。

A. 带有队头指针的双向非循环链表（使用这个链表，只知道对头指针，无法在O（1）的时间复杂度内找到队尾指针，所以出队是O（1）的，但是入队是O（n）的，比其他选项都差，所以选A）

B. 带有队头指针的双向循环链表（因为是双向循环链表，所以知道队头指针就可以知道队尾指针了，可以保证入队和出队操作时间复杂度都是O（1）的）

C. 只带队尾指针的双向循环链表（同上一个选项）

D. 只带队尾指针的循环单链表（这一个选项虽然不是双向循环链表，但是知道的是队尾指针，进行下一步操作就可以找到队头指针了，所以也可以实现入队和出队时间复杂度都是O（1），如果知道的是队头指针的循环单链表就不行了，无法在O（1）的时间内就找到队尾指针）

13、已知一个栈的进栈序列为1,2,3，…，n，其输出序列是p1，p2，p3，…，pn。若p1=n，则pi的值是（ C ）。

A. i

B. n-i

C. n-i+1（显然，最后一个入栈的元素是n，第一个出栈的元素是n，所以堆栈的操作应该是：先将序列全部入栈，中间没有出栈操作，入栈结束之后，统一进行出栈，所以输出序列刚好是逆序。然后举点例子就可以选出C了，比如，第一个p1应该是1，n-1+1=n，第二个p2应该是n-1，n-2+1=n-1，所以显然选C）

D. 不确定

14、已知一个栈的进栈序列为1,2,3，…，n，其输出序列是p1，p2，p3，…，pn。若pn=1，则pi的值是（D? ）。

A. i

B. n-i

C. n-i+1

D. 不确定（输出的最后一个元素序列是1，但是并不能像上一题一样确定输出序列刚好就是逆序的，所以中间过程的输出是无法确定的）

15、当利用大小为n的数组顺序存储一个栈时，元素存储在[0…n-1]位置上，假定用top==n表示栈空，则入栈一个元素时，首先应执行（ B? ）语句修改top值。

A. top++;

B. top--;（top==n时表示栈空，说明这个数组实现的栈是从尾部（即数组位置n-1）开始入栈的。所以入栈时，指针的操作应该时top--，所以选B）

C. top=0;

D. top=n;

16、设循环队列Q的存储容量为maxSize，队头和队尾指针分别为front和rear，则队列中元素的个数为（ D ）。

A. Q.rear - Q.front

B. Q.rear - Q.front + 1

C. (Q.rear - Q.front)%maxSize + 1

D. (Q.rear - Q.front + maxSize)%maxSize（这题经常考，因为队尾有时会跑到队头前面，所以Q.rear - Q.front有可能是负数，所以应该加上maxSize再模maxSize，具体可以拿一个例子比划一下，记一下公式就好了。需要注意的是，用数组实现队列，下标都是从0开始的，所以长度为maxSize 的队列在数组中的位置是0~maxSize-1。）

17、设一个链式队列q的队头指针和队尾指针分别为front和rear，则判断队列为空的条件是（? B? ）。

A. q.front == q.rear

B. q.front == NULL 或q.rear == NULL（和数组实现的队列不同，链表实现的队列头指针指向的位置是可以存数据的，所以q.front==NULL可以表示队列为空，而q.rear==NULL显然是可以判断队列为空的。）

C. q.rear == NULL

D. q.front != NULL

18、对一个初始为空的队列Q执行操作AddQ(Q, a)，AddQ(Q, b)，DeleteQ(Q)，DeleteQ(Q)之后，再执行IsEmpty(Q)，返回值为（ C ）。

A. a

B. b

C. true（队列进行了两次入队和两次出队操作，所以最后队列还是空的，IsEmpty（）函数是返回的类型是bool型，队列为空时返回true，所以应该选C。）

D. false?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

19、设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f，g依次进入栈S。如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b，d，c，f，e，a，g，则栈S的容量至少是（ C? ）

A. 1

B. 2

C. 3（因为队列的先入先出特性，元素在出栈再进队列，元素之间的顺序并没有改变，之所以加个队列是想同时考察一下，实际就是拿来干扰人的。题目是比较简单的，就不一一将过程写出了。栈中元素最大的时候应该是：acd和aef，所以容量至少应该是3）

D. 4

20、假设某栈的输入序列是1,2,3,4，则不可能得到的输出序列是（? B? ）。

A. 1,2,3,4（进栈后立即出栈可得到）

B. 4,1,2,3（明显不符合栈后入先出的规则，错误）

C. 4,3,2,1（先全部进栈后全部出栈可得）

D. 1,3,4,2（进栈、出栈、进栈、进栈、出栈、进栈、出栈、出栈可得）

实验3? 二叉树

1、在一棵有n个结点的树中，所有结点的度数之和为（ A ）。

A. n-1（这里要分清树和图的结点的度的区别，在树中，一个结点的度是其子树的个数；在图中，一个顶点的度是指依附于该顶点的边数（在有向图中又分成出度和入度）。所以在一棵树中，所有结点的度数之和就等于树中边的条数，因为树是不会有环的，所以树的边数一定是 结点数-1，所以应该选A）

B. n

C. n+1

D. 2n

2、在一个有m棵树的森林中，共有n个结点，那么森林中的总边数为（ C? ）。

（森林的定义：m（m>0）棵树的集合称为“森林”。对树中的每个结点而言，其子树的集合即为森林。需要注意的是，树不一定每个结点都只有两个子结点，在树中，结点的子节点有可能又1、2、3…个，只要符合树的规定。二叉树才是每个结点最多只能由两个子节点。）

A. n

B. m

C. n-m（这题是这样的：m棵相互并不相连的树组成了一个森林，假设这些树的结点个数分别为：n1，n2，n3…nm，我们又知道：一棵树的边数=树的结点树-1，所以这个森林的总边数=（n1-1）+（n2-1）+（n3-1）+…+（nm-1），因为森林是有m棵树，且森林结点总数为n，所以森林总边数=n-m。）

D. m-n

3、用数组存储完全二叉树时，下标为i的结点的左子结点的下标是（? B? ）。

A. i/2

B. 2i（用数组存储完全二叉树，下标为i的结点的左子结点的下标是2i，右子节点下标是2i+1。）

C. 2i+1

D. 2(i+1)

4、用数组存储完全二叉树时，下标为i的结点的右子结点的下标是（ C? ）。

A. i/2

B. 2i

C. 2i+1（用数组存储完全二叉树，下标为i的结点的左子结点的下标是2i，右子节点下标是2i+1。）

D. 2(i+1)

5、用数组存储完全二叉树时，下标为i的结点（根节点除外）的父结点的下标是（? A? ）。

A. i/2（显然，不多解释）

B. 2i

C. 2i+1

D. 2(i+1)

6、用数组存储完全二叉树时，根节点所存放位置的下标是（ B? ）

A. 0

B. 1（按照完全二叉树的定义，数组下标为0的位置是不放元素的。所以根节点的位置应该是1。因为如果根节点的位置不是1，是0的话，2i=0，2i+1=1，那就找不到完全二叉树的左结点了。）

C. n

D. 任意

7、具有1000个结点的完全二叉树的次底层的叶节点个数为（ A? ）。

（首先需要记住几个公式：对于深度为h的完全二叉树，结点个数为2^h-1，在第i层的结点个数为2^(i-1)。树的叶节点是度为0的结点，就是没有子结点的结点。）

A. 11（2^9-1=511<1000<2^10-1=1023，所以显然，这颗完全二叉树的深度是10。因为第10层没有满，所以这颗完全二叉树的叶节点有两个部分组成：第10层的全部结点和第9层的部分结点。这题要求的是次底层也就是第9层的叶结点数。先算第10层的叶节点数：前9层的结点数为2^9-1=511，所以这颗完全二叉树第10层的结点个数为：1000-511=489，第9层一共有2^（9-1）=256个结点，其中第10层的489个元素，其中标号为512~999的结点刚好占了第9层（489-1）/2=244个结点，剩下的第1000号结点单独占了一个，所以第9层总共被占了245个结点，所以第9层也就是次底层的叶节点个数为256-245=11个，所以选A）

B. 12

C. 24

D. 36

8、设一棵二叉树的中序遍历序列为badce，后序遍历序列为bdeca，则该二叉树前序遍历的序列是（ D ）。

A. adbec（做这类题，有一个小技巧：二叉树后序遍历的最后一个元素与先序遍历的第一个元素一定是相同的！而且先序遍历的第一个元素就是根节点！所以可以直接排除B和C。）

B. decab

C. debac

D. abcde（排序了B选项和C选项之后，最好利用先序遍历用草稿把树画出来与后序/中序遍历进行对照，最后试出来D是正确的）

9、一棵二叉树左子树的高度为4，右子树高度为5，则这棵二叉树的高度为（ C? ）。

A. 4

B. 5

C. 6（树的高度要选择最高的，所以该树的高度应该是5+1=6（右子树还要加上根节点））

D. 7

10、对某二叉树进行前序遍历的结果为abdefc，中序遍历的结果为dbfeac，则后序遍历的结果是（ B? ）。

A. dbfeac（一样的，利用先序遍历的第一个元素和后序遍历的最后一个元素相同，直接排除A和D选项）

B. dfebca（排除A和D后，因为先序遍历的第一个元素就是根节点，所以最好利用先序遍历将树画出，看符不符合中序遍历，最后结果就出来了，应该选B。）

C. bdfeca

D. bdefac

实验4? 二叉搜索树与平衡二叉树

1. 在任意一棵非空二叉搜索树T1中删除某结点v之后形成二叉搜索树T2，再将v插入T2形成二叉搜索树T3，则下列说法中正确的是（ C ）。

A. T1与T3一定相同

B. T1与T3一定不同

C. 若v是T1的叶结点，则T1与T3相同（要从二叉搜索树的定义出发，如果删除的结点是叶节点，那么应该是小于父节点或是大于父节点的数，那么删除了之后不会引起搜索树太大的变化，因为不需要变动根节点和父节点。所以当再次删除的元素插入搜索树时，最终还是会找到哪个叶节点的位置，所以T1和T3应该是相同的。）

D. 若v不是T1的叶结点，则T1与T3相同（若删除的不是叶结点，删除后一定会引起根节点或父节点的变动，而搜索树的插入操作是不会引起根节点的变动的，所以当再次将相同元素插入搜索树时，得到的搜索树一定和原来的不一样。即若v不是T1的叶结点，T1与T3一定不同）

2、二叉搜索树中的最小值结点（ C? ）。

A. 只能是根结点

B. 只能是叶结点

C. 可能是叶结点，也可能是根结点，还可能是只有右孩子的父结点（一般情况下，最小值结点会是叶节点，都是由特殊情况：当二叉搜索树只有二叉搜索树只有根节点和右子树时，根节点最小；当二叉搜索树最左边的结点有右孩子时，该右孩子的父节点最小（右孩子>父节点）。所以应该选C）

D. 可以是任何结点

3、用哪种顺序遍历二叉搜索树得到的是一个递增有序的数列（? B? ）。

A. 先序遍历

B. 中序遍历（这是一个很显然的问题，因为二叉搜索树的定义是左孩子<根节点<右孩子，中序遍历是：先遍历左子树，再遍历根节点，最后遍历右子树。所以中序遍历可以得到一个递增的有序数列。）

C. 后序遍历

D. 层序遍历

4、已知数据元素为34、76、45、18、26、54、92、65，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ B? ）。

A. 4

B. 5（二叉排序树就是二叉搜索树，与平衡二叉树不同，二叉搜索树在进行插入操作时不会变动根节点和父节点，所以说，先插入的数一定是根节点或是父节点。再按照搜索树的定义插入就可以得出深度为5。）

C. 6

D. 7

5、当一棵二叉搜索树的左、右子树都不为空时，二叉搜索树中的最大值所在结点类型是（ D? ）。此题答案不确定，只能排除A选项

A. 根结点（因为二叉搜索树的左右子树不为空，所以最大值不可能是根节点。）

B. 叶结点（最大值所在结点有可能是叶节点，当最右边的结点没有孩子时，该最右边的叶节点就是最大节点）

C. 父结点（最大值所在的结点可以是父节点，但是只能是没有右孩子，只有左孩子的父节点。）

D. 没有右孩子的结点（同样是符合的）

6、以下序列中不可能是一棵二叉搜索树的后序遍历结果的是（ B? ）

A. 1,2,3,4,5（当二叉搜索树只有左子树且左子树是线性时可得到。）

B. 3,5,1,4,2（由遍历性质可知，后序遍历的最后一个元素是根节点。而后序遍历是先遍历左子树，所以前面的数基本要小于后方的数（相对来说，并不绝对，因为），但是B选项明显前面的两个数都比后面大，明显不可能是后序遍历的结果。而C是可以得到的。）

C. 1,2,5,4,3

D. 5,4,3,2,1（当二叉搜索树只有右子树且右子树是线性时可得到。）

7、在二叉搜索树中查找元素，最坏情况下的时间复杂度是（C? ）。

A. O(log n)

B. O(n log n)

C. O(n)（当二叉搜索树变为线性时，时间复杂度变为O（n）。）

D. O(n2)

8、在平衡二叉树中查找元素，最坏情况下的时间复杂度是（ A ）。

A. O(log n)（如果是二叉搜索树，那最坏情况时间复杂度会降到O（n）；但是平衡二叉树不会，始终都会是O（log n））

B. O(n log n)

C. O(n)

D. O(n2)

9、以下说法中正确的是（ A? ）。

A. 向非空的二叉搜索树插入元素时，根结点不会变化（显然正确）

B. 向非空的平衡二叉树插入元素时，根结点不会变化（因为会进行单双旋，所以根节点有可能会变化。）

C. 从非空的二叉搜索树中删除元素时，根结点不会变化（会变化，当删除的原始是根节点（或父节点）时，一定会变化。）

D. 对平衡二叉树进行调整时，根结点一定会发生变化（只是有可能）

10、平衡二叉树进行“左-右双旋”的步骤是（ D? ）。

A. 进行两次左单旋

B. 进行两次右单旋

C. 先进行左单旋，再进行右单旋（进行右-左双旋时的操作）

D. 先进行右单旋，再进行左单旋（左-右双旋：先是左边长，然后是右边长。所以进行调整时应该从下往上调整，所以应该先进行右单旋，再进行左单旋。）

实验5? 散列查找

1. 散列存储的基本思想是根据（ C ）来决定关键字的存储地址。

A. 关键字的序号

B. 关键字的个数

C. 关键字的值（散列表定义）

D. 关键字的名称

2、使用散列函数将关键字映射为散列地址时，产生的冲突是指（ C? ）。

A. 两个关键字相同

B. 装填因子过小，关键字过少

C. 不同关键字对应到相同的存储地址（散列表定义）

D. 装填因子过大，关键字过多

3、以下关于散列函数选择原则的叙述中，不正确的是（ D?? ）。

A. 散列函数应是简单的，能在较短时间内计算出结果（设计出散列表的目的就是为了快速查找，理论上散列表进行查找的时间复杂度为O（1）。所以散列函数应是简单的，能在较短时间内计算出结果）

B. 散列函数的定义域包括全部关键字值，值域必须在表范围内（散列表的定义，显然正确）

C. 散列函数计算出来的地址应能均匀分布在整个地址空间中（散列表定义）

D. 装填因子必须限制在0.8以下（并没有明确进行要求。书上只是说实用最大装填因子因在0.5~0.85之间。所以选D。）

4、不发生冲突时，散列查找的时间复杂度是（ A? ）。

A. O(1)（散列表的定义）

B. O(log n)

C. O(n)

D. O(n2)

5、采用分离链法解决冲突时，每一个链表中各表项的（? B? ）相同。

A. 关键字值

B. 散列地址（用分离链法发生冲突，通过散列函数计算出的散列地址是一样的，只是分离链法是通过再同一散列地址开辟结点继续存数据的方法解决冲突。）

C. 元素值

D. 含义

6、假设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，则至少要进行（ D ）次探测。

A. k-1

B. k

C. k+1

D. k(k+1)/2（从小到大依次要探测1、2、3…k-1、k次，求和得k（k+1）/2，所以选D。）

7、以下哪种方法不是解决冲突的（ A? ）。

A. 数字分析法（明显与散列表无关）

B. 线性探测法

C. 双散列法

D. 平方探测法

8、已知一个线性序列{38, 25, 74, 63, 52, 48}，假定采用散列函数Hash(key)=key%7计算散列地址，散列存储在长度为7的散列表中。若采用线性探测法解决冲突，且各关键字的查找概率相等，则在该散列表上成功查找的平均查找长度为（ C ）。

A. 1.5

B. 1.7

C. 2.0（将序列中的每个元素在散列表中进行查找，最后求和再除于元素个数就得答案C。）

D. 2.3

9、上题中，查找失败的平均查找长度为（ B? ）。

A. 2.0

B. 4.0（因为只有不在散列表里的元素才会查找失败，不过也不用特别举例子放进去找，只要画出散列表，再数每个元素的位置离空位置的距离，加起来除于散列表长度就得到4了（刚好是1、2、3、4、5、6、7，相加得28，28/7=4））

C. 4.5

D. 5.0

10、以下说法中正确的是（ B? ）。

A. 使用开放定址法时，从散列表中删除某个关键字后，这个关键字就不在散列表中了（关键字还在散列表里，只是状态改变了，当有新的输入且地址相同时，这个关键字才会被覆盖掉。）

B. 散列函数相同时，使用分离链法的平均查找长度低于使用开放定址法的平均查找长度（显然正确，书上也有明显的例子）

C. 平方探测法可以探测到散列表的所有空间（是有条件的，要求散列表长度应为素数。）

D. 查找失败的平均查找长度可能小于查找成功的平均查找长度（进行查找时，只有当查到空的位置（或已被删除的位置）才会停下来表示查找失败，而查找成果，最多查找到空位置的前一个，所以每个查找失败的比较次数大部分（因为还需要看查找的元素）大于查找成功的长度，所以查找失败的平均查找长度一定大于查找成功的平均查找长度）（大概是这个道理）

实验6? 图的存储与遍历

1. 具有6个顶点的无向图至少应有（ A ）条边才能确保是一个连通图。

A. 5（如果图中任意两顶点都是连通的，则成该图是连通图。有n个顶点的无向图至少要有n-1条边才能确保是一个连通图；而有n个顶点的有向图至少需要n条边才能确保是一个强连通图。所以选A）

B. 6

C. 7

D. 8

2、设G是一个非连通无向图，有15条边，则该图至少有（ C? ）个顶点。

A. 5

B. 6

C. 7（对于有n个顶点的无向连通图来说，最多只能有n*(n-1)/2条边，解n*(n-1)/2=15得n=6，再加上一个没有任何边连接的顶点，才能使连通图变为非连通图，所以该非连通图至少有7个顶点。）

D. 8

3、以下关于无向连通图特性的叙述中，正确的是（ A?? ）。

①所有顶点的度之和为偶数

②边数大于顶点数减1

③至少有一个顶点的度为1

（所有顶点的度之和为顶点数的两倍，所以一定是偶数，①正确；边数还有可能等于顶点数-1，所以②错误；有些连通图是没有度为1的顶点的，以偏概全，③错误。所以只有①正确，选A。）

A. 只有①正确

B. 只有②正确

C. ①和②正确

D. ①和③正确

4、对于具有n（n>1）个顶点的强连通图，其有向边的条数至少是（B?? ）。

A. n+1

B. n（只有有向图才有强连通图的概念，只有无向图才有连通图的概念。强连通图和连通图概念一致，都是要两两顶点互相能够到达才能叫做强连通图/连通图。具有n个顶点的有向图至少要有n条边才能保证是强连通的。）

C. n-1

D. n-2

5、下列有关图的说法中正确的是（ D?? ）。

A. 在图结构中，顶点不可以没有任何前驱和后继（该选项的意思是，在图中不能有没有边连接的顶点，但实际上图中是可以有没有边的点的，所以A错误。）

B. 具有n个顶点的无向图最多有n(n-1)条边，最少有n-1条边（具有n个顶点的无向图最多有n(n-1)/2条边）

C. 在无向图中，边的条数是结点度数之和（在无向图中，边的条数是结点度数之和除于2）

D. 在有向图中，各顶点的入度之和等于各顶点的出度之和（正确，有向图的入度要等于出度。）

6、无向图的邻接矩阵是一个（ A? ）。

A. 对称矩阵（无向图邻接矩阵的概念。）

B. 零矩阵

C. 上三角矩阵

D. 对角矩阵

7、对于一个具有n个顶点和e条边的无向图，若采用邻接矩阵表示，则矩阵中非零元素的个数是（ B? ）。

A. e

B. 2e（无向图邻接矩阵的概念。有e条边，那邻接矩阵中应该有2e个非零元素。因为无向图中的边是无向的。）

C. e2

D. n2

8、下列说法中正确的是（ B ）。

A. 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一

B. 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一（邻接表的表示不唯一，当元素的插入顺序变化时，会使邻接表有多种写法。）

C. 一个图的邻接矩阵表示不唯一，邻接表表示唯一

D. 一个图的邻接矩阵表示不唯一，邻接表表示也不唯一

9、用邻接表存储图所用的空间大小（ C? ）。

A. 只与图的边数有关

B. 只与图的顶点数有关

C. 与图的顶点数和边数都有关（画出一个邻接表就可以看出来了，图的顶点数决定邻接表的长度，图的边数决定邻接表的宽度。）

D. 与边数的二次方有关

10、如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ B ）。

A. 强连通图（强连通图是有向图的概念。）

B. 连通图（进行一次深度优先搜索即可访问所有顶点，说明在深搜过程中没有将“绳子”拉回过，应该是连通图。）

C. 有回路

D. 一棵树

实验7? 最小生成树

1. 任何一个连通图的最小生成树（ B? ）。

A. 只有一棵

B. 有一棵或多棵（如果图中有较多的权值相同的边，那么可能会使最小生成树不唯一。）

C. 一定有多棵

D. 可能不存在

2、以下关于最小生成树的说法中正确的是（ C? ）。

A. 最小生成树是指边数最少的生成树（最小生成树是连通的、只有n-1条边的、权值和最小的生成树。）

B. 从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树（还得看会不会形成回路，能不能将所有顶点连接。）

C. 只要带权无向图中没有权值相同的边，其最小生成树就是唯一的（只要图中每条边的权值不同，那么最小权值是由各不相同的边权值相加得来的，所以该值一定唯一。）

D. 只要带权无向图中有权值相同的边，其最小生成树就不可能是唯一的（没有相同的边，最小生成树一定唯一；都是有相同的边，最小生成树就不一定不唯一。有相同的边是最小生成树唯一的必要条件。）

3、设无向图G=(V, E)和G’=(V’, E’)，如果G’是G的生成树，则以下说法错误的是（ A?? ）。

A. G’是G的连通分量（无向图的极大连通子图称为连通分量，而生成树是包含图的所有顶点的一个极小连通子图，所以A错误，D正确。极大连通子图和极小连通子图的区别是：极大连通子图含极大顶点数（保证子图连通的最大顶点数）和依附于这些顶点的所有边（再加入一个顶点就会导致不连通），极小连通子图含有极小顶点数和极小顶点数-1的边数（再减少一个点就会导致不连通）。）

B. G’是G的无环子图（一棵树的生成树一定是只有n-1条边的，经过图的所有顶点的。所以生成树是图的无环子图。子图包括有环子图和无环子图，所以B、C正确。）

C. G’是G的子图

D. G’是G的极小连通子图且V’=V

4、对于某个带权连通图构造最小生成树，以下说法中正确的是（ A? ）。

A. 该图的所有最小生成树的权值是唯一的（最小生成树的权值是一定唯一的，不管有没有相同的边。树的造型才会有可能不唯一。）

B. 具有最小权值的边一定会出现在最小生成树中（显然不一定）

C. Prim算法从不同顶点开始构造的所有最小生成树一定相同（显然不一定）

D. Prim算法和Kruskal算法构造的最小生成树一定不同（显然不一定）

5、用Kruskal算法求一个连通带权图的最小生成树，在算法执行的某个时刻，已选取的边集合TE={(1,2), (2,3), (3,5)}，要选取下一条权值最小的边，不可能选取的边是（ D? ）。

A. (2,4)

B. (3,6)

C. (1,4)

D. (1,3)（选择这条边会形成回路，所以不可能选这条边。）

6、Dijkstra算法是（? C ）求出图中从某点到其余顶点最短路径的。

A. 按长度递减顺序

B. 按长度递增顺序

C. 按深度优先遍历顺序（算法定义）

D. 按广度优先遍历顺序

7、若一个有向图的顶点不能排成一个拓扑序列，则可断定该有向图（ D? ）。

A. 是个有向无环图（无环一定可以排成拓扑序列。）

B. 是个强连通图（不一定，不能以小推大。）

C. 含有多个入度为0的顶点（与不能排成一个拓扑序列无关。）

D. 含有顶点数目大于1的强连通分量（不能排成一个拓扑序列说明有向图里含有环，所以在图中会有两个点及以上的强连通分量。）

8、若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ C ）。

A. 存在，且唯一

B. 不存在，不唯一

C. 存在，可能不唯一（矩阵中主对角线以下的元素均为零，如果这时主对角线上的元素都不为零，那么拓扑排序时唯一的；否则脱坡排序不唯一。可以举例子画图理解。）

D. 无法确定是否存在

9、在有向图G的拓扑序列中，若顶点i在顶点j之前，则以下情况不可能出现的是（ D? ）。

A. G中有边<i, j>

B. G中没有边<i, j>

C. G中有一条从顶点i到顶点j的路径

D. G中有一条从顶点j到顶点i的路径（顶点i在顶点j之前，那不可能会有从顶点j到顶点i的路径，否则i不能排在j之前。）

10、关键路径是AOE图中（ A? ）。

A. 从源点到汇点的最长路径（AOE图的定义，要找最长路径。）

B. 从源点到汇点的最短路径

C. 最长的回路

D. 最短的回路

实验8? 快速排序与归并排序

1. 若初始数据已经是排好序的，下列排序算法中最快的是（A? ）。

A. 直接插入排序（已经排好序的数据，用归并排序时间复杂度还是O（nlogn），用快排会升到O（n^2）（因为每次只能将一个元素排除），而直接插入排序因为排好序了，所以只会执行第一重循环，时间复杂度降为O（n），希尔排序的时间复杂度会大于O（n），所以这题应该选A。）

B. 希尔排序

C. 归并排序

D. 快速排序

2、在对一组记录(54, 38, 96, 23, 15, 72, 60, 45, 83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（ A? ）次。

A. 3（要移动60时的数组序列为15，23，38，54，72，96，60，45，83。所以60要与96、72、54比较才能找到位置，所以需要比较3次。）

B. 4

C. 5

D. 6

3、在下面各种排序算法中，关键字比较次数与记录初始排列无关的是（? B? ）。

A. 希尔排序

B. 冒泡排序（冒泡排序会将数组中的每个元素都与其他元素比较一次，与初始排序无关。）

C. 直接插入排序

D. 简单选择排序

4、对n个元素的数组进行（ C? ），其平均时间复杂度和最坏情况下的时间复杂度都是O(n logn)。

A. 希尔排序

B. 快速排序

C. 堆排序（只有归并排序和堆排序能一直保持O（nlogn）的时间复杂度。）

D. 简单选择排序

5、用堆排序方法排序(45, 78, 57, 25, 41, 89)，初始堆是（ B?? ）。

A. 78,45,57,25,41,89

B. 89,78,57,25,41,45（堆排序排升序需要建立大顶堆，排降序需要建立小顶堆。所以先将待排序列弄成堆，然后向上调整成大顶堆，就可以得到B选项了。）

C. 89,78,25,45,41,57

D. 89,45,78,41,57,25

6、以下说法中正确的是（? C ）。

A. 快速排序的平均时间复杂度是O(n logn)，最坏时间复杂度是O(n logn)。

B. 堆排序的平均时间复杂度是O(n logn)，最坏时间复杂度是O(n2)。

C. 冒泡排序的平均时间复杂度是O(n2)，最坏时间复杂度是O(n2)。（记忆性问题，见课本p287。）

D. 归并排序的平均时间复杂度是O(n logn)，最坏时间复杂度是O(n2)。

7、下面的（ B? ）算法的平均时间复杂度不是O(n logn)。

A. 快速排序

B. 基数排序（记忆性问题，见课本p287。）

C. 归并排序

D. 堆排序

8、下面排序算法中元素的移动次数和关键字的初始排列次序无关的是（ C ）。

A. 直接插入排序（有关）

B. 冒泡排序（移动次数与初始排列有关。）

C. 基数排序（基数排序会将待排序列进行分解，其实就是按位数（主位/次位）进行排序。与初始序列无关。）

D. 快速排序（都有关）

9、待排序数组初始为(19, 15, 12, 18, 21, 36, 45, 10)，则以19为基准元素进行一趟快速排序后的结果是（ A ）。

A. 10, 15, 12, 18, 19, 36, 45, 21（按快排步骤进行操作即可。）

B. 10, 15, 12, 18, 19, 45, 36, 21

C. 15, 10, 12, 18, 19, 36, 45, 21

D. 10, 15, 12, 19, 18, 45, 36, 21

10、要把一个降序排列的数组排成升序，哪种算法最快（D?? ）。

A. 直接插入排序（O（n^2））

B. 冒泡排序（O（n^2））

C. 快速排序（O（n^2））

D. 堆排序（O（nlogn））

结语

? ? ? ? 写完之后，我把它弄到百度网盘里匿名发到数据结构的课程群里了（因为QQ不能匿名发文件），然后群里都在夸我，我高兴坏了，心里满满的成就感啊~不枉我这一天的时光。（因为有点社恐所以匿名了）。继续加油吧~~